控制与决策  2019, Vol. 34 Issue (10): 2061-2072  
0

引用本文 [复制中英文]

赵小龙, 杨燕. 基于邻域粒化条件熵的增量式属性约简算法[J]. 控制与决策, 2019, 34(10): 2061-2072.
[复制中文]
ZHAO Xiao-long, YANG Yan. Incremental attribute reduction algorithm based on neighborhood granulation conditional entropy[J]. Control and Decision, 2019, 34(10): 2061-2072. DOI: 10.13195/j.kzyjc.2018.0138.
[复制英文]

基金项目

安徽省高校自然科学研究重点项目(KJ2016A107, KJ2017A645);安徽省高校质量工程项目(2016JXTD019, 2015GXK123.)

作者简介

赵小龙(1974-), 男, 副教授, 从事人工智能、算法设计和粒计算等研究, E-mail: zhaoxiaolong1974@163.com;
杨燕(1964-), 女, 教授, 博士, 从事计算智能、数据挖掘和集成学习等研究, E-mail: yyang@swjtu.edu.cn

通讯作者

赵小龙, E-mail: zhaoxiaolong1974@163.com

文章历史

收稿日期:2018-01-28
修回日期:2018-03-21
基于邻域粒化条件熵的增量式属性约简算法
赵小龙 1, 杨燕 2     
1. 安徽工业经济职业技术学院 计算机与艺术学院,合肥 230051;
2. 西南交通大学 信息科学与技术学院,成都 610031
摘要:增量式属性约简是针对动态型数据的一种重要的数据挖掘方法, 目前已提出的增量式属性约简算法大多基于离散型数据构建, 很少有对数值型数据进行相关的研究.鉴于此, 提出一种数值型信息系统中对象不断增加的增量式属性约简算法.首先, 在数值型信息系统中建立一种分层的邻域粒化计算方法, 并基于该方法提出邻域粒化的增量式计算; 然后, 在邻域粒化增量式计算的基础上给出邻域粒化条件熵的增量式更新方法, 并基于该更新机制提出对应的增量式属性约简算法; 最后, 通过实验分析表明所提出算法对于数值型数据的增量式属性约简具有更高的有效性和优越性.
关键词增量式学习    粒计算    属性约简    数值型数据    邻域粒化    条件熵    
Incremental attribute reduction algorithm based on neighborhood granulation conditional entropy
ZHAO Xiao-long 1, YANG Yan 2     
1. College of Computer and Art, Anhui Technical College of Industry and Economy, Heifei 230051, China;
2. School of Information Science & Technology, Southwest Jiaotong University, Chengdu 610031, China
Abstract: Incremental attribute reduction is an important data mining method for dynamic data. The incremental attribute reduction algorithms proposed at present are mostly based on discrete data construction, but the related study for numeric data is few. Therefore, an incremental attribute reduction algorithm for object constantly increasing in numeric information system is presented. Firstly, a hierarchical neighborhood computing method is established in numeric information system, and the incremental computing of neighborhood granulation based on this method is proposed. Then, on the basis of neighborhood granulation incremental computing, the incremental updating method of neighborhood granulation conditional entropy is given, and the corresponding incremental attribute reduction algorithm is proposed on account of this updating mechanism. Finally, experimental analysis shows that the proposed algorithm has higher effectiveness and superiority for the incremental attribute reduction of numerical data.
Keywords: incremental learning    granular computing    attribute reduction    numeric data    neighborhood granulation    conditional entropy    
0 引言

属性约简[1]在机器学习和数据挖掘等领域中又称为特征选择, 是降低数据复杂度和数据维度的一种重要的数据处理方法, 在不降低数据集分类性能的情况下, 对数据集中的不相关属性进行鉴别和剔除.粗糙集理论[2]作为一种重要的粒计算模型[3], 目前已成为数据集属性约简的一种常用方法[4-5].

在现实的大数据环境下, 数据无时无刻都在产生, 因此各类应用系统里的数据集不是静止不变的, 而是处于不断动态变化之中.传统的属性约简算法都是针对静态的数据集而设计[4-5], 这些算法在处理动态变化的数据集时需要进行大量的重复计算[6], 因此效率较为低下.为了改善这一局限性, 一种新形式的属性约简方法被提出, 称为基于增量式学习的属性约简方法, 即增量式属性约简[7].该方法通过对更新后的信息系统进行增量计算, 从而达到对动态数据处理的时效性[8].

数据集对象(样本)的不断增加是数据集动态变化的一种常见形式, 基于这类问题, 学者们提出了多种增量式属性约简算法.如Liang等[9]利用条件熵作为启发式函数, 在离散型信息系统中提出了对象集增加的增量式属性约简算法. Jing等[10]从多粒化视角提出了高维数据的对象集动态增加的属性约简算法, 同时利用粒计算模型中的知识粒度提出了两种增量式属性约简算法[11]. Raza等[12]在粗糙集模型下提出了属性集依赖度的增量更新, 并提出了对应的特征选择算法. Chen等[13]运用变精度粗糙集模型在离散型信息系统提出了对应的增量式属性约简.冯少荣等[14]利用差别矩阵解决对象增加时的增量计算问题.钱进等[15]也提出了一种新形式的增量式属性约简算法.在不完备信息系统中, Liu等[16]通过矩阵的方法提出了一种增量式属性约简算法; Shu等[17]提出了不完备信息系统中依赖度的增量式计算, 并在此基础上提出相应的增量式属性约简算法.

数值型数据是一种常见的数据形式, 然而在目前所提出的增量式属性约简算法中, 大多是基于离散型的数据构建, 很少有人提出基于数值型数据的增量式属性约简算法, 这促使本文对数值型数据的增量式属性约简进行研究.在粗糙集理论中, 邻域粗糙集[18]是处理数值型数据的一种强大的工具, 它通过在数值型信息系统中构建邻域关系, 基于邻域关系对信息系统的论域进行邻域粒化, 最后基于粒化后的信息粒进行粗糙计算[18].因此, 本文通过邻域粗糙集模型来建立数值型数据的增量式属性约简.

邻域关系将数值型数据诱导出一组邻域粒化, Zhao等[19]在邻域粒化的基础上提出了邻域粒化条件熵模型, 并构造出数值型数据的属性约简算法, 实验表明了该算法的有效性.关于邻域粒化的计算方面, Liu等[20]利用排序方法提出了一种高效的邻域粒化计算方法.本文在此基础上提出一种当信息系统对象集增加时的邻域粒化分层增量式计算; 然后在该增量式计算的基础上, 提出邻域粒化条件熵的增量式学习机制, 并基于该机制提出相应的增量式属性约简算法; 最后通过一系列的实验来验证所提出的增量式属性约简算法的有效性和优越性.

1 基本理论

在分类学习任务中, 通常格式化的数据集表示为一个信息系统IS=(U, AT)的形式.其中: U称为该信息系统的论域, U中每个元素x称为信息系统的对象(样本); AT称为信息系统的属性集(特征集); 对象xU在属性a∈AT下的值称为属性值, 表示为a(x).若信息系统中所有属性值均为数值型数据, 则该信息系统又称为数值型信息系统NIS=(U, AT).

在数值型信息系统NIS=(U, AT)中, 若属性集AT满足AT=CDCD=∅, 其中C为该信息系统的条件属性集, D为该信息系统的决策属性集, 即该数据集的类属性, 其属性值均为离散值.则这类信息系统称为数值型决策信息系统NDIS=(U, CD).

在粒计算理论[3]中, 邻域粗糙集模型[18]是处理数值型信息系统的一种有效工具.在邻域粗糙集模型中, 通过邻域关系对信息系统论域进行邻域粒化, 其粒化结果称为论域的一个粒结构, 然后基于粒化结果对目标知识进行逼近计算.

定义1[18]  数值型信息系统NIS=(U, AT), 属性集B⊆AT在该信息系统确定的邻域关系NBU

(1)

其中: δ为非负常数, 在邻域粗糙集模型中称为邻域半径; dB(x, y)为对象xy之间的距离, 在机器学习和模式识别中, 距离度量通常采用闵可夫斯基距离

(2)

p通常取1, 2和∞三种形式, p=2是熟悉的欧氏距离.

对于x1, x2, x3U, 对象之间的距离满足:

1) d(x1, x2)≥0, 仅当x1=x2时, d(x1, x2)=0;

2) d(x1, x2)=d(x2, x1);

3) d(x1, x3)≤ d(x1, x2)+d(x2, x3).

定义2[18]  数值型信息系统NIS=(U, AT), 设U={x1, x2, ..., xn}, 属性集B⊆AT在该信息系统确定的邻域关系为NBU, 那么NBU可以将论域U诱导出一个邻域粒化U/NBU, 表示为

(3)

其中: nBU(x)为对象xU关于邻域关系NBU在论域U下的邻域类, 或称为邻域粒, nBU(x)={yU|(x, y)∈NBU}; NBU导出的邻域粒化U/NBU称为论域U的一个粒结构.

近年来, Liang等[21]在信息系统中引入了信息论理论, 并在信息系统中提出了信息熵的概念.在此基础上, 学者们在信息系统中各类粒计算模型下提出了多种推广信息熵的概念[22].其中Zhao等[19]在数值型信息系统的邻域粒化中提出了条件熵模型.

定义3[19]  数值型信息系统NIS=(U, AT), 设U={x1, x2, ..., xn}, 属性集B1, B2⊆AT在该信息系统下确定的邻域关系分别为NB1UNB2U, 在论域U上诱导的邻域粒化分别为U/NB1UU/NB2U.在论域U下, 属性集B2关于属性集B1的邻域粒化条件熵为

(4)

邻域粒化条件熵满足0≤ EU(B2|B1)≤1-1/n.此外, 对于数值型决策信息系统NDIS=(U, CD), 论域U在等价关系RDU下确定的决策粒化为U/RDU={[x1]DU, [x2]DU, ..., [xn]DU}.决策属性D关于属性集B1的邻域粒化条件熵为

(5)

对于数值型信息系统NIS=(U, AT), 属性集B1B2⊆AT, 且B1B2在该信息系统确定的邻域关系分别为NB1UNB2U, D关于属性集B1B2的邻域粒化条件熵分别为EU(D|B1)和EU(D|B2), 满足EU(D|B2)≤ EU(D|B1).

上述是邻域粒化条件熵一个重要的性质, 它表明随着属性集的增加, 决策属性关于该属性集的邻域粒化条件熵是单调不增的, 这是构造属性约简算法的一个必要条件[4, 18-20, 22], 它保证邻域粒化条件熵能够收敛, 最后属性约简算法才得以终止.因此, Zhao等[19]提出了基于邻域粒化条件熵的属性约简算法, 具体如算法1所示.

算法1  邻域粒化条件熵属性约简(ARNGCE).

输入:数值型决策信息系统NDIS=(U, CD), 邻域半径δ;

输出:条件属性集C的约简集redc.

Step 1:初始化redc=∅, EU(D|∅)=1.

Step 2:对于∀aiC-redc, 计算属性ai关于redc的属性重要度sredc(ai), 其中

Step 3:对于Step 2中的所有属性ai, 选出属性重要度最大的属性, 并记为a*.

Step 4:对于属性a*, 若sredc(a*)>0, 则redc=redc ∪{a*}, 进入Step 2;若sredc(a*) = 0, 则进入Step 5.

Step 5:返回约简集redc.

算法1通过邻域粒化条件熵作为启发式函数来搜索属性, 并不断进行迭代, 直到EU(D|C)=EU(D|redc)算法终止, 此时redc即为条件属性集C的约简, 且算法1的时间复杂度主要集中在邻域粒化的计算上, 每个邻域的计算需要消耗O(|C||U|)的时间, 因此论域中所有对象进行邻域计算的时间复杂度为O(|C||U|2), 整个算法1的时间复杂度为O(|C|2|U|2).

2 邻域粒化条件熵的增量式属性约简

文献[19]通过理论和实验证明, 基于邻域粒化条件熵的属性约简具有更高的约简性能.由于该算法是非增量式的, 只能处理静态的信息系统.为了能够对动态的数据集进行增量式属性约简, 针对数值型信息系统对象不断增加的情形, 提出一种基于邻域粒化条件熵的增量式属性约简.

增量式属性约简的关键是计算的高效性, 当有新数据加入, 新的信息系统在属性约简时只需对新进数据进行计算, 而不对已经计算过的数据进行重复运算, 这样便能满足数据处理的时效性, 达到动态数据的处理需求[6-17].文献[20]运用排序的方式提出了一种快速邻域计算方法, 本节在此基础上, 提出一种邻域粒化的分层增量式计算, 并提出邻域粒化条件熵的增量式学习机制, 最后基于该机制提出相应的增量式属性约简算法.

2.1 邻域粒化的分层增量式计算

Liu等[20]提出的排序方法提高了邻域粒化的计算效率, 本节将该方法进一步改进, 提出一种高效的邻域粒化方法, 并应用于邻域粒化的增量式计算中.

定义4  数值型信息系统NIS=(U, AT), 将信息系统中的所有属性值归一化为非负值, 即∀xU, ∀a∈AT满足a(x)≥0.设属性集B⊆AT, 邻域半径为δ.基于属性集B在论域U上定义一个包含m个对象集的分层LBU={l1, l2, ..., lm}, 其中

(6)

其中: x0U是人为构造的一个特定对象, 称为原点对象, 满足∀aB, a(x0)=0;dB(x, x0)为对象xx0之间的距离度量; m的大小取决于论域中对象与原点对象之间距离的最大值; li为论域经过分层后的第i个分层集, li内部的对象x与原点对象x0之间的距离位于区间(δ(i-1), δi], 即论域的分层事实上是将整个论域分成多个部分, 同一个部分中的对象与原点对象之间的距离位于同一个区间.同时应当注意,可能存在liLBU满足li=∅.

通过定义4可以看出, 在论域U上定义的分层集LU相当于对论域中所有对象按照与原点对象的距离分成不同的层次.这样做的直接好处是在进行对象邻域粒计算时, 可以大幅度减小计算量.

定理1  数值型信息系统NIS=(U, AT), 设属性集B⊆AT, 邻域半径为δ.论域U上确定的分层集为LBU={l1, l2, ..., lm}, 对象x的邻域粒可以计算为

(7)

证明  1)对于对象x1, 若x1li(2≤ im-3), 设原点对象为x0, 则根据定义4有i-1 < dB(x1, x0)/δi, 即(i-1)δ < dB(x1, x0)≤ iδ.对于对象x2, 若x2li+2(2≤ im-3), 则满足(i+1)δ < dB(x2, x0) ≤(i+2)δ, 因此有dB(x2, x0)-dB(x1, x0)>δ.根据三角不等式有dB(x2, x0)-dB(x1, x0) < dB(x1, x2), 即dB(x1, x2)> δ, 所以∀xli+2, xnBU(x1).可进一步推出∀xlti+2均有dB(x1, x)>δ, 同理∀xlti-2也均有dB(x1, x)>δ.所以xli(2≤ im- 1), 邻域粒nBU(x)可直接计算为nBU(x)={yli-1lili+1|dB(x, y)≤δ}.

2) 对于对象x1l1, 根据式(1)可以得出∀xlt≥ 3均有dB(x1, x)>δ.所以若xl1, 则对象x的邻域粒可计算为nBU(x)={yl1l2|dB(x, y)≤δ}.

3) 对于对象x1lm, 根据式(1)可以得出∀xltm-2均有dB(x1, x)>δ.所以若xlm, 则对象x的邻域粒可计算为nBU(x)={ylm-1lm|dB(x, y) ≤δ}.

通过定理1可以看出, 将论域进行分层后, 某一层内对象x邻域粒的计算只需分析前一层、本层和后一层的对象集即可, 其余层内的对象与对象x的距离肯定是超过邻域半径δ的, 因此无需像定义2那样, 将整个论域遍历一遍, 这样可以大幅度减小计算量, 提高计算