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称为信息系统的属性集(特征集); 对象x∈U在属性a∈AT下的值称为属性值, 表示为a(x).若信息系统中所有属性值均为数值型数据, 则该信息系统又称为数值型信息系统NIS=(U, AT).

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

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

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

(1)

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

(2)

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

对于x₁, x₂, x₃∈U, 对象之间的距离满足:

1) d(x₁, x₂)≥0, 仅当x₁=x₂时, d(x₁, x₂)=0;

2) d(x₁, x₂)=d(x₂, x₁);

3) d(x₁, x₃)≤ d(x₁, x₂)+d(x₂, x₃).

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

(3)

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

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

定义3^[19]  数值型信息系统NIS=(U, AT), 设U={x₁, x₂, ..., x_n}, 属性集B₁, B₂⊆AT在该信息系统下确定的邻域关系分别为N_B1^U和N_B2^U, 在论域U上诱导的邻域粒化分别为U/N_B1^U和U/N_B2^U.在论域U下, 属性集B₂关于属性集B₁的邻域粒化条件熵为

(4)

邻域粒化条件熵满足0≤ E^U(B₂|B₁)≤1-1/n.此外, 对于数值型决策信息系统NDIS=(U, C∪D), 论域U在等价关系R_D^U下确定的决策粒化为U/R_D^U={[x₁]_D^U, [x₂]_D^U, ..., [x_n]_D^U}.决策属性D关于属性集B₁的邻域粒化条件熵为

(5)

对于数值型信息系统NIS=(U, AT), 属性集B₁ ⊆B₂⊆AT, 且B₁和B₂在该信息系统确定的邻域关系分别为N_B1^U和N_B2^U, D关于属性集B₁和B₂的邻域粒化条件熵分别为E^U(D|B₁)和E^U(D|B₂), 满足E^U(D|B₂)≤ E^U(D|B₁).

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

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

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

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

Step 1:初始化redc=∅, E^U(D|∅)=1.

Step 2:对于∀a_i∈C-redc, 计算属性a_i关于redc的属性重要度s_redc(a_i), 其中

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

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

Step 5:返回约简集redc.

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

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

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

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

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

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

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

(6)

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

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

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

(7)

证明  1)对于对象x₁, 若x₁∈l_i(2≤ i≤ m-3), 设原点对象为x₀, 则根据定义4有i-1 < d_B(x₁, x₀)/δ ≤ i, 即(i-1)δ < d_B(x₁, x₀)≤ iδ.对于对象x₂, 若x₂∈l_i+2(2≤ i≤ m-3), 则满足(i+1)δ < d_B(x₂, x₀) ≤(i+2)δ, 因此有d_B(x₂, x₀)-d_B(x₁, x₀)>δ.根据三角不等式有d_B(x₂, x₀)-d_B(x₁, x₀) < d_B(x₁, x₂), 即d_B(x₁, x₂)> δ, 所以∀x∈l_i+2, x∉ n_B^U(x₁).可进一步推出∀x∈l_{t≥ i+2}均有d_B(x₁, x)>δ, 同理∀x∈ l_{t≤ i-2}也均有d_B(x₁, x)>δ.所以x∈l_i(2≤ i≤ m- 1), 邻域粒n_B^U(x)可直接计算为n_B^U(x)={y∈l_i-1∪ l_i∪l_i+1|d_B(x, y)≤δ}.

2) 对于对象x₁∈l₁, 根据式(1)可以得出∀x∈l_{t≥ 3}均有d_B(x₁, x)>δ.所以若x∈l₁, 则对象x的邻域粒可计算为n_B^U(x)={y∈l₁∪l₂|d_B(x, y)≤δ}.

3) 对于对象x₁∈l_m, 根据式(1)可以得出∀x ∈l_{t≤ m-2}均有d_B(x₁, x)>δ.所以若x∈l_m, 则对象x的邻域粒可计算为n_B^U(x)={y∈l_m-1∪l_m|d_B(x, y) ≤δ}.

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

例1  表 1为数值型信息系统NIS=(U, AT), 其中论域U包含5个对象, 属性集AT={a₁, a₂, a₃}.

令邻域半径δ=0.1, 距离函数选取为欧氏距离.根据定义4可以得到表 1信息系统的分层集为

其中: l₁=l₂=∅, l₃={x₅}, l₄={x₁}, l₅={x₃}, l₆={x₂, x₄}.

按照定理1的方法, 对于对象x₁ ∈ l₄, 计算x₁的邻域只需要考察l₃、l₄和l₅中的对象, 计算可得n_AT^U(x₁) ={x₁, x₅}.对于对象x₂∈l₆, 计算x₂的邻域只需要考察l₅和l₆中的对象, 计算可得n_AT^U(x₂)={x₂, x₄}.同理可计算出其他对象的邻域为n_AT^U(x₃)={x₃}, n_AT^U(x₄)={x₂, x₄}, n_AT^U(x₅)={x₁, x₅}.

根据定义2的方法计算每个对象的邻域粒.对于对象x₁, 有

对象x₁的邻域粒为n_AT^U(x₁)={x₁, x₅}.同样可得

与定理1的计算结果相同, 从实例角度证明了定理1的正确性.

根据定理1中基于分层方法的快速邻域粒化计算, 在此基础上提出数值型信息系统对象增加时的邻域粒化增量式更新方法.

定义5  对于数值型信息系统NIS=(U, AT), 设U={x₁, x₂, ..., x_n}, 属性集B⊆AT, 邻域半径为δ, 令属性集B在论域U上确定的分层集为L_B^U= {l₁, l₂, ..., l_m}.当一个新的对象集ΔU加入信息系统时, 新的信息系统表示为NIS'=(U', AT), 其中U'=U∪ΔU.那么论域U'上新的分层集为

(8)

其中

x₀表示原点对象.

定义5表明, 当信息系统的对象发生增加时, 不需要对更新后的整个信息系统重新建立分层集, 只需在原来分层集的基础上进行更新和扩展, 这样便减少了大量的重复计算.

定理2  对于数值型信息系统NIS=(U, AT), 设U={x₁, x₂, ..., x_n}, 属性集B⊆AT, 邻域半径为δ.属性集B在该信息系统确定的邻域关系为N_B^U, 并且基于分层计算方法得到的邻域粒化为U/N_B^U = {n_B^U(x₁), n_B^U(x₂), ..., n_B^U(x_n)}.当新的对象集ΔU ={x_n+1, x_n+2, ..., x_n+u}加入信息系统时, 新的信息系统为NIS'=(U', AT), 其中U'=U∪ΔU.设N_B^U'为在新的信息系统确定的邻域关系, 则新的邻域粒化为

(9)

其中n_B^U'(x_n+1), n_B^U'(x_n+2), ..., n_B^U'(x_n+u)按照定理1方法进行计算.同时∀x∈U更新为

(10)

证明  当信息系统NIS=(U, AT)有新的对象集ΔU加入时, 原先论域U上的邻域粒化U/N_B^U将会发生改变, 即新的对象集ΔU的加入会使得论域U中对象的邻域发生增加.对于对象y∈ΔU, 如果对象x ∈ U且x ∈ n_B^U'(y), 则表明d_B(x, y)≤ δ, 即y∈n_B^U'(x), 又y∉ n_B^U(x), 所以n_B^U'(x)=n_B^U(x)∪{y}.因此有n_B^U'(x)=n_B^U(x)∪{y|x∈n_B^U'(y), ∀y ∈ΔU}.

当新的对象集加入后, 非增量式的邻域粒化计算方法是重新计算论域中每个对象的邻域粒, 而定理2所示的增量式计算方法中, 对新加入的对象按照定理1的方法快速计算出邻域粒, 然后对于原来论域的邻域粒化, 只需要更新部分对象的邻域粒, 最终得到整个新论域的邻域粒化.事实上, 新对象的邻域粒计算与原来论域邻域粒化的更新可以同步进行, 因此定理2中的增量式邻域粒化计算具有很高的效率.

例2  在例1的基础上, 对表 1的信息系统加入一个对象集{x₆, x₇}, 新的信息系统NIS'=(U', AT)如表 2所示.

由于对象集{x₆, x₇}的加入, 需要对原来信息系统的邻域粒化结果进行更新, 设x₀为原点距离, ⌈d_AT(x₆, x₀)/δ⌉=7, ⌈d_AT(x₇, x₀)/δ⌉=5, 新论域U'的分层集扩展至7层, 即

按照定义5的更新方法可以得到

同时计算出对象x₆和x₇的邻域粒分别为n_AT^U'(x₆)={x₂, x₄, x₆}, n_AT^U'(x₇)={x₁, x₃, x₇}.根据定理2有

对象x₅满足n_AT^U'(x₅)=n_AT^U(x₅).

2.2 邻域粒化条件熵的增量式更新

第2.1节提出了一种基于分层集模型的邻域粒化快速计算方法, 并运用该分层集模型建立了当信息系统对象集增加时的邻域粒化增量式更新.本节将在邻域粒化增量式更新方法的基础上, 提出邻域粒化条件熵的增量式更新, 为后面增量式属性约简算法的提出提供铺垫.

为了研究过程的清晰和直观, 采用其他学者的研究思路^{[9, 11, 16-17]}, 首先分析只有一个对象加入信息系统后, 邻域粒化条件熵的增量式更新, 然后在此基础上进一步探索多个对象加入后的增量式更新.

定理3  对于数值型决策信息系统NDIS=(U, C∪D), 设U={x₁, x₂, ..., x_n}, 属性集B⊆C, 邻域半径为δ.属性集B在论域U上诱导出的邻域粒化为U/N_B^U={n_B^U(x₁), n_B^U(x₂), ..., n_B^U(x_n)}, 决策属性D关于B在论域U下的邻域粒化条件熵为E^U(D|B).当新的对象x_n+1加入信息系统后, 新的信息系统为NIS'=(U'=U∪{x_n+1}, AT), B在论域U'上诱导出的邻域粒化为U'/N_B^U'={n_B^U'(x₁), n_B^U'(x₂), ..., n_B^U'(x_n+1)}, 决策属性D关于B在论域U'下的邻域粒化条件熵为E^U' (D|B).则有

(11)

证明  由定义3, 有

当对象x_n+1加入后, U'=U∪{x_n+1}.令Φ=n_B^U'(x_n+1), Ψ=U'-n_B^U'(x_n+1), 根据定理2可知Ψ表示增加x_n+1后U中邻域粒不发生变化的对象集, 因此可以推出∀x∈Ψ, n_B^U'(x)=n_B^U(x), 同时有n_B^U'(x)∩[x]_D^U'=n_B^U(x)∩[x]_D^U.那么

由定理2, 对于y ∈ U, 若y ∈ n_B^U'(x_n+1), 则n_B^U'(y) =n_B^U(y)∪{x_n+1}, 所以对于∀y∈Φ-{x_n+1}, 均有|n_B^U'(y)|=|n_B^U(y)|+1, 并且当对象y与对象x_n+1有相同的决策值时, |n_B^U'(y)∩[y]_D^U'|=|n_B^U(y)∩[y]_D^U|+1, 显然在Φ-{x_n+1}中有|n_B^U'(x_n+1)∩[x_n+1]_D^U'|-1个对象满足该条件, 所以有

根据集合的运算关系满足

因此

简单整理后即可得到定理3中的结果.

定理3给出了当信息系统增加一个对象后, 原邻域粒化条件熵与新邻域粒化条件熵之间的增量更新关系, 并且在原条件熵的基础上, 只需要计算增加进来的对象邻域粒和决策类, 便可得到新的条件熵结果, 这样避免了对原论域中对象邻域粒的重复计算, 大大提高了动态环境下的处理效率.

定理3给出的是增加一个对象后条件熵的递推关系, 当信息系统增加多个对象时, 可通过该递推关系推导出增加多个对象时的条件熵增量更新关系.

定理4  对于数值型决策信息系统NDIS=U, C∪D, 设U={x₁, x₂, ..., x_n}, 属性集B⊆C, 邻域半径为δ.决策属性D关于B在论域U下的邻域粒化条件熵为E^U(D|B).当包含u个对象的新对象集ΔU={x_n+1, x_n+2, ..., x_n+u}加入信息系统后, 新的信息系统为NIS'=(U'=U∪ΔU, AT), 决策属性D关于B在论域U'下的邻域粒化条件熵为E^U'(D|B).则有

(12)

其中: U_i=U∪{x_n+1, x_n+2, ..., x_n+i}, 即U'=U_u; n_B^U'(x_n+i)为对象x_n+i在论域U_i上的邻域粒; [x_n+i]_D^U_i为对象x_n+i在论域U_i上的决策类.

证明  为了简便, 记E^U_i(D|B)=E^U_i.由定理3有

则有

依此计算有

即

定理4表明, 当信息系统加入多个对象时, 只需要依次对每个加入的对象计算出邻域粒和决策类, 并且对象x_n+1在U∪{x_n+1}下进行计算, 对象x_n+2在U∪{x_n+1, x_n+2}下进行计算, 对象x_n+i在U∪{x_n+1, x_n+2, ..., x_n+i}下进行计算, 因此在计算过程中, 可以逐步计算邻域粒, 即对于多个对象, 可以依次加入信息系统.加入一个对象后便立即在当时的信息系统中计算邻域粒和决策类, 这样当所有对象添加完毕, 整个邻域粒化条件熵便可以直接得出.

2.3 增量式属性约简算法

根据第2.2节的增量式邻域粒化条件熵, 基于文献[19]所提出的邻域粒化条件熵的数值型信息系统属性约简算法, 可以针对论域不断增大的动态数值型信息系统提出邻域粒化条件熵的增量式属性约简算法.在提出算法前, 首先探究数值型信息系统论域增大后, 其邻域粒化条件熵的变化情况.同样地, 首先分析只有一个对象加入信息系统后邻域粒化条件熵的变化.

设数值型决策信息系统NDIS=(U, C∪D), U ={x₁, x₂, ..., x_n}, 属性集B⊆C, 邻域半径为δ.决策属性D关于B在论域U下的邻域粒化条件熵简记为E^U.当新的对象x_n+1加入信息系统后, 新的信息系统为NDIS'=(U'=U∪{x_n+1}, C∪D), 决策属性D关于B在论域U'下的邻域粒化条件熵简记为E^U'.由定理3, 有

对两个邻域粒化条件熵相减, 即

由定义3, 有0≤ E^U≤1-1/n, 令k=|n_B^U'(x_n+1)-[x_n+1]_D^U'|, 经过整理可以得到

由于n_B^U'(x_n+1)-[x_n+1]_D^U'⊆U, 即0≤ k≤ n, 有

−2n + 1/n + 1 ≤ 2(k − n) + 1/n + 1 ≤ 1/n + 1, 2(k-n)+1/n+1的值可能为正、或负、或0, E^U'-E^U的值也如此.因此可以得出, 当信息系统增加一个对象后, 其邻域粒化条件熵的变化是不可确定的, 可能会增大也可能会减小, 或者可能不变.该结论可直接推广到当信息系统有多个对象加入的情形.

在本文所提出的增量式属性约简中, 初始信息系统的属性约简采用算法1, 但当信息系统有新的对象集加入时, 信息系统发生更新, 传统的非增量式属性约简在进行属性约简时, 对新的信息系统直接处理, 即重新运用算法1对新的信息系统进行属性约简, 这样随着数据的规模逐步增大, 属性约简的耗时会越来越大.本文所提出的属性约简算法采用增量式学习的方法, 在原来信息系统属性约简的基础上, 增量式地计算新的信息系统的约简, 能够大幅度提高计算效率.具体的增量式属性约简算法如算法2所示.

算法2  邻域粒化条件熵的增量式属性约简(IARNGCE).

输入: 1)初始时数值型决策信息系统NDIS=(U, C∪D), |U|=n, 邻域半径δ; 2) NDIS中条件属性集C的约简集redc; 3)邻域粒化条件熵E^U(D|C), E^U(D|redc); 4)增加的对象集ΔU={x_n+1, x_n+2, ..., x_n+u}, 并令新的数值型决策信息系统为NDIS' =(U', C∪D), 其中U'=U∪ΔU.

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

Step 1:初始化E^U'(D|C)=1, E^U'(D|redc)=1.

Step 2:根据E^U(D|C)和E^U(D|redc), 按照定理4增量式计算E^U'(D|C)和E^U'(D|redc).

Step 3:判断E^U'(D|C)与E^U'(D|redc)之间的大小关系, 如果E^U'(D|C) < E^U'(D|redc), 则转至Step 4, 如果E^U'(D|C)=E^U'(D|redc), 则转至Step 7.

Step 4:对于∀a∈C-redc, 计算每个属性对应的邻域粒化条件熵E^U'(D|redc∪{a}).

Step 5:选择满足下列条件的属性, 记为a^*:

Step 6:若E^U'(D|redc) - E^U'(D|redc∪{a^*}) > 0, 则redc=redc∪{a^*}, 并进入Step 4, 否则进入Step 7.

Step 7: redc'=redc, 返回约简集redc'.

在算法2的Step 2中, 初始时E^U(D|C)与E^U(D|redc)的值是相等的, 按照定理4分别增量式更新至E^U'(D|C)和E^U'(D|redc).根据之前的分析, 信息系统论域增大, 虽然邻域粒化条件熵的变化是不确定的, 但必定满足E^U'(D|C)≤ E^U'(D|redc), 因此在Step 3中, 需要具体判断E^U'(D|C)与E^U'(D|redc)之间的大小关系.如果它们相等, 则达到算法的终止条件, 返回约简集, 如果E^U'(D|C)≤ E^U'(D|redc), 则需要在剩余的属性中继续搜索属性, 直至满足终止条件.

在算法2所示的增量式属性约简中, 论域的分层集是整个邻域粒化条件熵计算的基础, 根据定义4, 对于属性集B⊆C在论域U建立分层集的时间复杂度为O(|B||U|), 加入新的对象集ΔU后, 更新分层集所需要的时间复杂度为O(|B||ΔU|).设分层集的每一层平均包含k个对象, 那么基于分层集计算单个对象邻域所需的时间复杂度为O(3k). Step 2中论域U的分层集已在初始信息系统属性约简时建立, 时间复杂度为O(|C||ΔU|+|redc||ΔU|+6k|ΔU|). Step 3的时间复杂度为O(1).假设从初始约简集redc至新的约简集redc'增加了c个属性, 那么Step 4~Step 6的时间复杂度为O(|C-redc|(2|redc||U'|+6k'|U'|))+O((|C-redc|-1)(2(|redc|+1)|U'|+6k'|U'|))+...+O((|C-redc|-c)(2(|redc|+c)|U'|+6k'|U'|)), 其中k'表示U'分层集中每层的平均对象数.通常c的值较小, 因此通过整理和计算可得出整个算法2的时间复杂度为O(|C-redc'|(|redc'|+k')|U'|).相比较于算法1的非增量式属性约简, 所提出的算法在时间复杂度方面具有更高的效率.

3 实验分析

本节将进行一系列实验以验证所提出算法的增量式属性约简性能.实验主要分为两部分:第1部分是将所提出的邻域粒化条件熵增量式属性约简算法与邻域粒化条件熵非增量式属性约简算法对同一组数据集进行动态数据集的属性约简, 从而验证所提出算法的有效性; 第2部分是将所提出的算法与其他同类型增量式属性约简算法对同一组数据集进行属性约简比较, 从而验证所提出算法的优越性.

准备工作如下.从UCI机器学习标准数据集库中选取7个数值型数据集, 如表 3所示.这7个数据集都是静态的数据集, 但是本文所提出的是动态数据集的属性约简方法.为了构造出数据集对象增加的动态性, 将整个数据集的对象集大致平均分成10个等份, 随机选取其中一份作为初始数据集, 然后依次从剩余的每份中随机选取一份对象集加入数据集中, 这样便模拟出数据集中对象集9次动态增加的情形.实验中的所有算法采用JDK1.8进行编程实现, 算法代码运行在Intel Core(TM) i7 3770 3.4 GHz CPU, DDR3 1600 MHz 8 G内存的Windows 10个人主机上.

3.1 与邻域粒化条件熵非增量式属性约简算法比较

本文所提出的邻域粒化条件熵增量式属性约简算法(记为IARNGCE)是在邻域粒化条件熵非增量式属性约简算法(记为ARNGCE)的基础上提出的, 在本小节将这两种算法对表 3中的数据集进行属性约简比较.两种算法均采用条件熵度量进行属性分类性能的评估, 并且令两种算法对各个数据集设定相同的邻域半径δ=0.2, 距离度量函数选取为欧氏距离, 因此两种算法对同一数据集的属性约简结果是一样的, 只需要比较其属性约简时间性能. 图 2为两种算法在所有数据集每次动态更新时属性约简的时间消耗比较.

由图 2可见, 当横坐标为0时, ARNGCE和IARNGCE的属性约简用时是相同的, 这是由于在初始数据集的属性约简时, IARNGCE算法同样采用ARNGCE算法进行约简.当数据集开始动态增加后, 两种算法的属性约简用时发生了明显变化, 对于规模较小的数据集, 如数据集Wdbc、Hill_Valley和Mess, 刚开始的一至两次更新, ARNGCE算法的属性约简时间稍高于IARNGCE算法, 但是当数据集更新次数较多时, ARNGCE算法的约简用时大幅度高于IARNGCE算法.对于规模较大的数据集, 如数据集Wall和Magic, 随着数据集动态更新, IARNGCE算法的约简用时总是大幅度小于ARNGCE算法, 这是由于ARNGCE算法是一种非增量式的属性约简, 当数据集更新后, ARNGCE算法在计算邻域粒化条件熵时需要进行大量的邻域粒重复计算, 而IARNGCE算法进行的是增量计算, 理论分析已表明所提出的增量计算方法避免了大量的重复计算, 相比较于ARNGCE算法, 实验结果验证了IARNGCE算法对动态数据集属性约简的有效性.

3.2 与同类型增量式属性约简算法比较

选取近年来提出的同类型增量式属性约简算法与本文所提出的邻域粒化条件熵增量式属性约简算法进行实验对比, 从而验证所提出算法的增量式属性约简的优越性.参与比较的算法分别为离散型信息系统对象增加的增量式属性约简算法^[9](记为IAR-1)、基于变精度粗糙集模型的离散型信息系统增量式属性约简算法^[13](记为IAR-2)、基于知识粒度的离散型信息系统增量式属性约简算法^[11](记为IAR-3)和邻域粗糙集模型的增量式更新算法^[23](记为IAR-4).由于文献[23]给出了邻域粗糙集上下近似的增量更新, 实验中采用依赖度进行增量式属性约简.另外, IAR-1算法、IAR-2算法和IAR-3算法是针对离散型信息系统的增量式属性约简算法, 在进行实验时需要将表 3中的数据集进行数值型数据离散化处理. IAR-4算法和本文所提出的IARNGCE算法可以直接处理数值型数据, 但是算法中都含有一个参数, 即邻域半径δ, 该值取值不同, 对属性约简结果将产生一定的影响^[18].根据目前已有的研究结果^[18], 邻域半径选取为[0.1, 0.3]之间较为适宜, 取为0.2进行实验.

由于实验是将每个数据集的对象集分割成多份, 然后通过逐份添加的方式模拟构造出对象集的动态增加, 进行比较的5种增量式算法对数据集的每次更新都会得到相应的属性约简结果.实验共模拟出9次数据集动态更新, 为了简便, 展示9次属性约简集大小的平均值, 如表 4所示.

由表 4可见, 各个属性约简算法选择出的平均约简集大小均小于原数据集属性全集的大小, 部分数据集的平均约简集大小远小于属性全集, 如数据集Hill_Valley和Biodeg.这表明数据集中存在很多不相关属性, 这些不相关属性对分类学习是不重要的, 需要剔除以简化数据结构.比较5种算法的实验结果可以发现, IAR-4算法和IARNGCE算法得到的平均约简集均小于其余3种算法, 这是由于其余3种算法是基于离散型数据集的, 而表 3数据集在进行离散化的过程中改变原来数值型数据的取值分布, 同时引入量化误差, 改变了原有知识空间的粒化结果, 使得在属性约简的过程中选择出了更多的属性.比较IAR-4算法和IARNGCE算法的平均属性约简结果可以发现, IARNGCE算法在相当一部分数据集的平均约简集更小, 是由于条件熵在属性约简方面的优越性^{[19, 24]}, 它通过信息论的视角去评估属性, 尤其在数值型数据中优于邻域粗糙集模型的依赖度评估, 因此选择出的属性更精简.

分类精度是评估数据集中属性集分类性能的一种重要体现, 为了比较各个增量式属性约简算法得到的约简集的优劣, 实验通过支持向量机分类器(SVM)和朴素贝叶斯分类器(NB)分别对各个数据集每次更新后得到的属性约简结果进行分类训练, 并评估出相应的分类精度.由于有多个属性约简结果, 实验将多个结果分类精度的平均值作为对应算法的分类精度结果, 两种分类器的分类精度结果分别如表 5和表 6所示, “*”表示5种算法分类精度的最大值.

由表 5和表 6可见, 大部分约简集的分类精度高于原始属性集的分类精度, 这更加表明数据集普遍存在着大量的不相关属性以及剔除这些属性的必要性.比较表 5和表 6的5种增量式属性约简结果的分类精度可见, IAR-1算法和IARNGCE算法的分类精度在整体上比其他3种算法要高, 这是由于两种算法均采用信息熵模型对属性进行评估, 选择出的属性对分类具有更好的性能.比较IAR-1算法与IARNGCE算法之间的分类精度可以发现, IARNGCE算法在大部分数据中的分类精度更高, 如表 5的Wdbc、Biodeg和Yeast等, 表 6的Wdbc、Wall和Magic等.这是由于IARNGCE是直接处理数值型数据的算法, 对于数值型数据的属性约简, 本文所提出的IARNGCE算法能够选择出更优的属性约简结果.

图 3为5种算法在各个数据集上增量式属性约简时间消耗比较结果.由图 3可见, 5种算法在数据集每次更新属性约简时有不同的运行时间情况.其中IAR-4算法在所有数据集中时间消耗最高, 这是由IAR-4算法的增量机制决定的, 当数值型信息系统有新对象加入, IAR-4算法在计算新对象的邻域时, 需要将整个论域遍历计算一遍, 因此消耗较多的运行时间. IAR-1算法和IAR-2算法的时间消耗大致位于中间位置, 而IARNGCE算法和IAR-3算法在大部分数据集中拥有较低的时间消耗, 这是由于IAR-1算法和IAR-2算法是针对离散型数据的增量式计算, 计算新对象的信息粒时虽然不必比较整个论域, 但是同样需要比较很多其他对象. IAR-3算法基于粒计算模型的知识粒度进行增量式属性约简, 不需要进行上下近似的增量计算, 只需对增加的对象进行等价类的处理, 因此其处理效率略高于IARNGCE算法. IARNGCE算法采用分层的方法进行信息粒计算, 只需要比较相邻对象层对象, 极大地减小了计算量, 具有很高的计算效率.

综合第3.1节和第3.2节两部分的实验结果可以证明, 所提出的IARNGCE算法在数值型信息系统的增量式属性约简方面具有更高的有效性和优越性.

4 结论

增量式属性约简是针对动态变化数据集的一种属性约简方法, 目前的增量式属性约简研究只限于离散型信息系统.邻域粗糙集模型是粒计算理论中处理数值型信息系统的一种有效工具, 本文在邻域粒化条件熵的基础上提出了一种信息系统对象增加时的增量式属性约简算法.首先在数值型信息系统中建立一种分层的邻域粒化计算, 然后基于该方法给出邻域粒化的增量式计算, 最后进一步提出邻域粒化条件熵的增量式更新, 并设计出相对应的增量式属性约简算法. UCI数据集的实验结果表明了所提出算法对于数值型数据增量式属性约简的有效性和优越性.

本文所提出的增量式属性约简是针对信息系统对象集不断增加的情形, 接下来将针对属性不断增加的情形进行增量式属性约简的研究.