基于邻域关系粗糙集和不确定性的增量属性约简方法

吴晓雪，李 艳

(1.河北大学 数学与信息科学学院,河北 保定 071002;2.北京师范大学 (珠海) 应用数学与交叉科学研究中心,广东 珠海 519000)

传统粗糙集[1-2]基于等价关系通过上下近似刻画不精确概念,只能处理符号值属性。很多后续研究引入不同的二元关系,如邻域关系[3-7]、模糊关系[8]、容差关系[9]、优势关系[10]等,建立了相应的粗糙集模型,能够处理更多的数据类型。其中,邻域关系通过引入邻域半径直接处理连续值属性。Hu等人将邻域关系引入粗糙集,提出了邻域粗糙集模型[3]；Wang等人提出了一种邻域分辨指数来表示邻域关系的分辨信息,引入信息熵的相关变体,设计了特征选择算法[4]；Sun等人提出了一种新的基于勒贝格和邻域粗糙集熵测度的属性约简方法,以有效地处理连续性数值问题[5]；Chen等人构造了一种基于变精度模糊邻域粗糙集的多标签属性约简方法,可处理多种类型的数据且能够容忍噪声影响[6]；Hu等人在邻域关系中引入不同的权值,设计了一种贪婪搜索算法来选择相关性较高的属性子集[7]。

在实际应用中,数据通常随时间的推移而变化。增量方法在数据对象和属性发生任何变化时,可通过对已有信息的重用有效减少计算耗费,快速更新约简。目前相关工作主要针对对象集(即样本集)、属性集、属性值的变化[11-13]这3个方面进行研究。在邻域关系粗糙集中,Hu等人提出了一种基于矩阵的邻域多粒度粗糙近似表示方法和相应的动态约简更新策略[14];Wang等人在有序信息系统中提出了一种优势特征矩阵获取策略,避免了原始属性之间的重复比较,从而在对象集和属性集同时变化时高效地更新约简[15]。对具有混合类型特征的动态数据,Shu等人提出了一种基于邻域熵的增量特征选择算法,添加和删除多个对象时可快速更新约简[16]。

然而,现有增量方法一般使用全部的变化样本参与增量计算,未考虑对象所携带的分布信息(样本在特征空间所处的区域),其潜在假设是认为这些变化的样本对更新约简的影响是均等的,导致增量算法的耗费仍然会较大。实际上,数据集中各样本对分类的重要程度往往是不同的,不确定性建模相关研究表明,样本的不确定性大小会对分类性能产生重要影响[17-18]。而属性约简本质是在保持数据分类能力的基础上尽可能去除冗余属性,因此，不同样本对属性约简贡献程度也会不同。

基于这个认识,很多工作通过样本选择来降低约简的计算复杂度。如杨习贝等人在启发式属性约简中使用K均值聚类算法对样本进行选择[19];Wang则提出了一种基于样本抽取和优先级的属性约简方法[20];Wang等人将样本选择的方法引入基于分辨矩阵的属性约简中,减少了参与约简的样本数量,在保证分类能力前提下明显降低了算法的时间和空间耗费[21]。这些工作都认为处于边界区域的样本对属性约简有重要的影响，而边界样本往往具有较大的不确定性,因此，可考虑使用不确定性大小来体现样本对约简结果的重要程度。但是，这些研究只是在静态的信息系统中进行属性约简,尚未考虑添加的样本对动态信息系统约简更新的影响。当样本集发生变化时,增量算法只需要在原有约简基础上进行更新计算,不同于原始的约简过程。本研究的主要思路是进一步考虑动态信息系统中所添加的样本对约简增量更新的影响,提出在增量算法之前加入一个样本筛选的过程,从而只选择贡献程度较大的样本参与增量计算。在邻域粗糙集属性约简的增量方法中,目前尚未发现有结合样本选择的研究,本文在现有工作基础上,基于不确定性度量对样本进行刻画和划分,结合样本选择建立新的增量方法,进一步降低现有算法的计算代价。

本研究的主要工作为:第一,在邻域关系粗糙集模型的增量约简方法中考虑分布在不同区域的样本对更新约简的影响；第二,结合不确定性和分类器结果对样本的重要性进行类型划分,更准确地刻画样本对约简结果的贡献程度大小；第三,针对不同类型的样本提出不同的更新策略,建立相应的约简更新算法。本文为连续值信息系统提供了新的增量方法,可以在保持分类性能不变的情况下,进一步提高约简的效率,同时对丰富不确定性理论也有着重要的意义。

1 邻域关系粗糙集中的基本概念

定义1称NIS=(U,A,V,f,ε)是一个邻域信息系统[22],其中，U={x1,x2,…,xn}是非空的对象集,称为论域;A={a1,a2,…,am}是非空的属性集;V是所有属性值的集合,即V=∪a∈AVa;f:U×A→V是信息函数;ε是邻域阈值参数,以此来确定邻域的大小。

若A=C∪D,其中C为条件属性集合,D为决策属性集合,则称NDS=(U,C∪D,V,f,ε)为邻域决策信息系统。

定义2[22]设邻域决策信息系统为NDS=(U,C∪D,V,f,ε),xi∈U,B⊆C。在特征空间B中,xi的邻域εB(xi)定义为

εB(xi)={xj|xj∈U,ΔB(xi,xj)≤ε)}。

(1)

其中，Δ是距离函数，使用邻域便于处理连续值属性。

(2)

(3)

定义4[22]基于定义3中的上下近似,论域U被划分为3个区域,分别为正域POSB(X)、边界域BNDB(X)和负域NEGB(X),定义为

(4)

(5)

(6)

定义5[22]给定邻域决策信息系统NDS，对于∀B⊆C,若满足以下条件,则称属性集B为属性集C的属性约简，

POSB(D)=POSC(D)，

(7)

∀a∈B,满足POSB-{a}(D)≠POSC(D)。

(8)

2 基于邻域关系粗糙集和样本不确定性的增量属性约简方法

2.1 样本不确定性与属性约简之间关系的初步分析

决策系统中处于边界域的样本携带较大不确定性(不一致度),一般会降低决策系统分类能力。已有研究也表明数据本身的不确定性会显著影响分类器的泛化性能[23-24]。而属性约简本质是在保持数据本身的分类能力的前提下最大程度去除冗余属性,因此,我们认为在一个信息系统中增加不确定性大的样本对约简结果也会有重要的影响。本节通过在人工数据集上的实验对此做初步验证。

前期研究发现数据的样本不一致度、边界复杂性和分类器输出不确定性有着很强的相关性[25]。因此，可采用模糊k近邻分类器(FKNN)的输出不确定性衡量样本的不确定性大小(见定义10)。样本的输出向量中每个分量为该样本属于每个类的隶属程度，易知,隶属于每个类的程度越接近,不确定性越大,越不容易分辨该样本的类别(即易被分错)，这样的样本大多数处于类别的边界区域。在动态决策系统中,若这种不确定性大的样本被加入或删除,原决策表的分类能力容易发生变化。因此，在约简的更新计算中,不能忽略变化的对象集中不确定性大的样本。相反,样本的输出不确定性越小,说明该样本越容易通过其他样本确定其所属类别,当此类样本发生变化时,对分类性能影响较小。另一方面,易被分错的样本一般处于样本分布比较复杂的区域,或者是噪音样本,其对约简更新也可能有重要的影响。

接下来针对分布在不同区域的样本对属性约简的影响进行初步的实验分析。采用人工生成高斯分布的数据集,包含300个20维的样本,类别为3类,邻域半径设为0.1。基于HANDI算法[4]计算得原始约简集为{1,4,8},其中，数字为属性的序号。通过在数据集上添加若干不同区域的样本构成动态信息系统,重新计算约简观察不同样本对约简的影响。图1中实心三角代表的样本是在原始数据集中新增加的样本,样本的3种颜色代表它们的标签类别。

根据加入样本所处区域和FKNN的分类结果，分3种情况来讨论。图1A中新加入的样本分布在靠近同类类簇中心的密集区域，或者处于同类簇稀疏区域但远离其他异类簇,出现概率大,该区域的样本往往不确定性小且被正确分类,称为第1类样本。加入后在新的数据集上重新计算约简,发现结果保持原始约简{1,4,8}不变,说明此类样本对约简更新的贡献较小,若需要进一步降低计算耗费,此类样本可以不参与约简的更新。图1B中新添加的样本分布在类边界区域或者分布在异类样本的密集区域(可能为异常点或噪音),该区域的样本特点是不确定小但容易被错误分类,称为第2类样本。加入后重新计算约简,结果更新为{1,4,5,8}，说明处于该区域的样本对约简更新有一定的影响,为保持分类能力应参与约简的更新过程,但此类样本出现的概率一般很小。图1C中新加入的样本分布在类边界区域,且不确定性较大,称为第3类样本。加入样本后约简结果更新为{1,3,8,10}，说明处于该区域的样本对约简更新有较大的影响,贡献程度较大,应参与约简的更新。

图1 不同区域样本对属性约简的影响结果

在随机生成的数据集上进行反复实验,从加入单样本和多样本两个方面,进行了600轮约简的更新计算,对添加样本前后约简的对比发现，在3种情况下均有类似结果,即第1类样本对约简影响最小,第2类和3类样本影响较大,但第2类样本出现的概率最小,总体影响低于第3类(不确定性大的样本)。在这3类样本中,一般第1类样本出现的可能性最高,占的比重最大,如果在约简更新中忽略此类样本的影响,则应该能够明显降低更新代价。

2.2 相关概念和更新策略

2.2.1 相关概念 根据2.1节的分析和初步验证,本文在文献[4]中非增量算法的基础上,建立基于不确定性和邻域关系粗糙集的增量属性约简方法。

定义6在邻域决策信息系统NDS=(U,C∪D,V,f,ε)中,样本间的相似关系可以用矩阵来表示,相似矩阵表示为RB=(rij)n×n。

(9)

其中：xi和xj是U中的两个样本，记xl=[xl1,xl2,…，xls]T,l=i,j；B⊆C；ε是邻域半径,是控制样本相似性的阈值。

使用邻域分辨指数表示邻域关系的分辨信息,并引入条件分辨指数等变体用于计算分辨信息的变化。它们与香农熵及其变体有相似的性质。

定义7[4]给定邻域决策信息系统NDS，B⊆C，ε是邻域半径,RB表示属性集B的邻域相似矩阵。属性B的邻域分辨指数定义为

(10)

邻域分辨指数用来衡量特征子集区分能力的不确定性,通过计算邻域关系的基数直接得到,复杂度比香农熵小。

(11)

其中，0≤Hε(B1|B2)≤logn；|*|表示集合或关系*的基数。

邻域分辨指数用于衡量关系或属性集的区分能力，属性集的条件分辨指数越小,属性集的分辨能力越强,属性集的重要度越大。根据以上定义,通过在已有约简结果的基础上,进行属性集的增加或减少,可以改变邻域分辨指数的大小,通过计算之间的差值来进行属性集重要度的判定。

定义9[4]设邻域决策信息系统NDS=(U,A,V,f,ε),B⊆C,a∈C-B,关于B和D,属性a的重要度定义为

SIG(a,B,D)=Hε(D|B)-Hε(D|B∪{a})。

(12)

属性的重要度SIG越大,则越重要。集合C是条件属性集,B⊆C,若属性集B是约简集,则满足如下性质:

Hε(D|B)≤Hε(D|C)，

Hε(D|B-{a})>Hε(D|B)，∀a∈B。

使用模糊k近邻(FKNN)计算不确定性,好处是模糊k近邻引入了类别隶属度的概念,样本不只属于某一类,而是以一定比例隶属于多个类别,比k近邻更加准确。

定义10给定邻域决策信息系统NDS,设有n个决策类。对任意U中样本x,使用模糊k近邻(FKNN)分类器对此样本的输出向量[u1,u2,…,un]计算不确定性，

(13)

其中ui∈[0,1],ui为样本x对第i类的隶属程度。易知,Uncerni∈[0,log2n]。

2.2.2 样本划分和更新策略 首先,在原始数据集上事先训练FKNN和SVM分类器,使用FKNN输出结果计算样本不确定性(定义10),并设定区分不确定性大小的阈值。使用SVM分类器确定样本分类的正确与否,将加入的样本可粗略分为以下3类。

1)不确定性小且被正确分类的样本。该类型的样本大部分分布在类内样本密集区域,少部分分布在同类稀疏区域但离其他异类较远,该类型样本对属性约简的贡献度较小,对约简集的更新没有影响或影响较小。

2)不确定性小且被错误分类的样本。该类型的样本一般是边界点,极少数情况是噪音,分布在边界区域,但周围异类样本点较多,该类型样本对属性约简的贡献度高于第一类样本,对约简集的更新影响也较大。

3)不确定性大的样本。该类型的样本一般属于边界样本,对属性约简的贡献度大,不管是被正确还是错误分类,都对约简集的更新有不可忽视的影响。

针对不同类别的样本,采取不同的策略。

1)对于第1类样本,即不确定性小于阈值且被正确分类的样本,忽略其对约简的影响,不参与属性约简的更新。此类样本占数据集大多数,出现概率大,因此，可假设在动态变化的对象集中也占最大比例。

2)对于第2类样本,即不确定性小且被错误分类的样本,为保持系统分类能力考虑其影响，此类样本参与属性约简的更新。

3)对于第3类样本,即不确定性大的样本,不能忽略其对分类和约简的贡献,应参与属性约简的更新。

2.3 增量算法步骤

根据2.2节的更新策略,对于加入的样本,提出了基于不确定性和邻域关系粗糙集的增量属性约简方法(incremental attribute reduction method based on uncertainty and neighborhood relation rough set,简称为IAUNR),算法如下。

输出 新的约简集red(U∪UX)。

样本的筛选过程:在NDS中的约简集redU上计算UX的不确定性大小和样本分类正确与否,将其分为3种类型;若新增样本UX全部属于第1种类型,则直接加入原数据集中,不进行约简的更新,转到步骤20);否则,将属于其他两类的样本保留,记为数据集X,用于约简的更新,转到步骤1)。

初始化:B=A-redU,start=1；

1) 计算H(U∪X)(D|C)和H(U∪X)(D|red)。判断H(D|red)和H(D|C)的大小关系,若H(D|red)-H(D|C)≤δ,则转至步骤20)，否则转至步骤2)。

2)while start

3) for eachai∈B

5) 计算重要度

SIG(ai,red(U∪X),D)=

Hε(D|red(U∪X))-

Hε(D|red(U∪X))∪{ai});

6) end for

7) 找出最大SIG(akred(U∪X),D)对应的属性ak

8) if SIG(ak,red(U∪X),D)>δ

9) red(U∪X)←red(U∪X)∪{ak};

10)B←B-red(U∪X)；

11) else

12) start=0;

13) end if

14) end while

∥检查是否有冗余属性

15) for eachai∈red(U∪X)

16) ifHε(D|red)-

Hε(D|red(U∪X)-{ai})≥δ

17) red(U∪X)←red(U∪X)-{ai}；

18) end

19) end

20) return red(U∪X)=red(U∪X)。

算法时间复杂度分析:IAUNR算法在其非增量算法的约简集red的基础上进一步考虑约简更新,并使用贡献度较大的样本集进行约简的更新。对于N维的样本集,计算邻域相似关系的时间复杂度为ΔN=C-red,最坏的时间复杂度为(ΔN+ΔN2)/2。

3 实验结果与分析

为验证此增量算法的有效性,使用UCI数据库[26]中的11个数据集来评估算法,如表1所示。本节包含了5组实验结果,分别为：①所提出增量算法IAUNR与非增量算法[4]的约简时间比较;②IAUNR与现有4种增量算法的约简时间比较;③IAUNR与非增量算法以及4种对比算法在分类精度上的比较;④5种增量方法约简率的比较;⑤不确定性阈值对结果的影响分析。实验中的所有算法在Matlab 2016b中执行,并在Intel Core i5-10210U CPU和16GB RAM的硬件环境中运行。

表1 实验数据集

参数邻域半径ε和δ的设置参见文献[4]，ε通过调整参数的值从0到1,步长为0.05,为每一个数据集选择一个最优的特征子集;参数δ用于终止算法主循环,需提前设置,通常来说,随着参数δ值的减小,约简数目应随之增多,本文设置δ为0.001。在后面3.2节与现有相关增量方法的比较中,有关邻域的实验参数设置也按照以上方法。分类精度基于10次10倍交叉验证,对训练集进行属性约简,在约简后的数据上训练分类器得到精度,取每次精度的平均值作为最终结果。

3.1 与非增量算法的约简时间比较

为了构造数据集对象增加的动态性,根据原始数据集中3类样本的分布随机产生符合该数据集分布的样本集,每次生成该数据集总数的10%添加至原始数据集,进行了5次增量实验,并在不同的数据集上与非增量算法进行比较。本文所提出的增量算法是基于邻域分辨指数的启发式算法(HANDI)。图2展示了非增量算法和增量算法在9个数据集上的时间消耗的对比。由于Wpbc和wine数据集、 electrical和Segmentation数据集的增长趋势相似,篇幅限制,省略了Wpbc和electrical数据集的折线图。

从图2可以看出，所提出的增量算法IAUNR在所使用的数据集上都明显降低了非增量算法(HANDI)所消耗的时间,并且随着增量数目的增多,差距越来越明显。随着样本增多,IAUNR的时间增长趋势比HANDI算法缓慢的多。不难理解,出现这个结果的原因是非增量算法在每次新增样本集时,都要重新计算约简集,而IAUNR充分利用了已有的约简信息，不必重新从头计算;另一个原因是IAUNR算法考虑了不同区域样本对属性约简更新的贡献程度,只选用贡献程度大的样本进行属性约简的更新,大大减少了样本的规模,提高了约简的效率。其中，wine、Credit、Segmentation、Wdbc、biodeg在增加越来越多的样本时,时间耗费比较稳定,说明加入样本集之前的约简形成的分类结果已达到了一个较高精度,加入的样本集对现有的约简结果影响不大,故约简结果没有发生变化,需要的计算量很小,仅需运行2.3节中算法的步骤1)。其他数据集随增量次数的增多时间变化较大,取决于每次所增加的样本对影响约简更新的程度大小。

图2 非增量算法和增量算法约简时间比较

3.2 与现有增量方法的约简时间比较

为了验证本文所提增量算法的性能,选择了4种相关增量算法进行比较,分别是一种分组增量特征选择方法(GIARC)[27]、基于知识粒度的增量属性约简方法(IARC)[28]、基于邻域粒化条件熵的增量式属性约简算法(IARNGCE)[29]、以及文献[28]和[30]中邻域关系知识粒度增量约简算法的变体(NIARC)。GIARC和IARC算法是针对等价关系的增量方法,在使用之前,首先要用k均值聚类方法对数据进行离散化处理;NIARC算法是在IARC算法的基础上引入邻域的概念,用于处理连续性数值。以上增量算法中新增的样本与3.1节中新增的样本相同,进行了5次增量实验,实验结果取5次增量实验时间消耗的平均值。由于数据集规模的大小不同,时间消耗存在较大差异,故将11个数据集分为3组进行结果对比(见图3)。

图3 IAUNR与现有增量方法的约简时间比较

结果表明,本文所提的IAUNR算法在大部分数据集上的时间消耗较小,在4个数据集上所用时间最少,在7个数据集上接近最优,仅次于最少时间。IARC算法在7个数据集上的时间消耗最少,因为IARC是基于等价关系的, 只需对新增的样本进行等价类的计算, 运行速度快, 但不能直接处理连续值数据,同时， 离散化会丢失信息, 导致分类精度受到影响(见3.3节中分类精度的对比结果)。 其他3个算法的时间消耗相对较大, GIARC虽然是基于等价关系的增量算法,不需要考虑整个论域,但仍需要对增加的全部样本进行处理,且计算较IARC复杂;IARNGCE算法采用分层的方法进行计算,不需要计算加入的样本与其他全部样本的距离,但仍需要考虑全部变化的样本;NIARC算法是在IARC算法的基础上引入邻域的概念,也需对新增的全部样本进行处理。而IAUNR算法只选用贡献度较大的样本进行属性约简的更新,而在一般情况下,贡献度比较大的样本处于边界区域或者是异常点,出现的几率小，大部分新增样本在增量计算中被忽略,这样就极大地减少了时间的消耗。注意到在较大数据集如Segmentation、electrical上,IAUNR的时间消耗也是较少的,只有在Musk数据集上IARNGCE和IARC接近,获得了最快的约简更新,可能的原因是所生成的新增样本对该算法属性约简的影响较小,不需要大量的计算。总体来说，IAUNR算法在属性约简更新上的时间消耗有着优越性。

3.3 分类精度比较

本节使用约简后数据集上的分类精度体现和评估属性约简的质量。对3.1节和3.2节中涉及的6个算法,可以基于某种分类器通过10倍交叉验证计算得到对应的分类精度，这里选择了SVM作为分类算法。一种非增量算法和5种增量算法的约简后精度结果详见表2。其中,每一列代表相应算法在各数据集上进行5次增量约简后的平均分类精度,用均值±标准差的形式来表示,最后一行是各算法的总体平均精度。最优精度加黑进行标注。

从表2可以看出,在11个数据集上以及6种算法中,IAUNR的平均精度是最高的,在8个数据集上均达到最优分类精度,另外在biodeg和Sonar两个数据集上表现次优,略低于最高精度。其次是NIARC算法,平均精度比IAUNR低约1%,但仅在1个数据集上取得最高精度。然后是IARNGCE算法,在2个数据集上达到最高精度,平均精度比IAUNR约低2%。GIARC和IARC算法的约简后分类精度在6种算法中表现最差,原因是这两个算法是基于等价关系的增量方法,对所增加的样本集进行了离散化处理,破坏了原有样本集属性取值的连续性,所以精度明显低于其他算法。与非增量HANDI算法相比,5种增量算法中除去GIARC和IARC,其他3种算法均取得了更高的约简后精度。IAUNR在9个数据集上优于HANDI算法的精度,这表明IAUNR算法在极大减少时间消耗的基础上,还保持了良好的分类性能。

表2 约简后的6种算法精度比较

结合3.2节和3.3节的实验结果，本文所提的IAUNR增量算法在11个数据集上取得了最好的分类精度,约简更新的时间仅高于基于等价关系的增量算法IARC,但显然能比IARC生成更好的属性约简。

3.4 约简中属性数目的比较

约简中所含属性数量可以反映约简算法去除冗余信息的能力。表3显示了6种算法经过5次增量实验的平均约简数目。非增量算法HANDI的结果是在每次变化后的数据集上重新计算的,可视为其他算法的一个基准。

表3 约简中属性数目比较

可以看出,6种算法去除了数据集中的大部分属性,且在5种增量算法中,IAUNR的平均约简数目(6.85)是最少的,其次是NIARC算法(8.73),再次是IARNGCE算法(8.91)。与非增量HANDI算法相比,IAUNR约简中平均属性数目只多了0.41,在3个数据集上达到最少,1个数据集上属性数目相等。可见IAUNR算法在保持了分类精度优势的同时,还有着很强的约简能力。GIARC和IARC的约简中属性数目较多的原因是对数据集进行了离散化处理,为保持原始分类能力需要包含更多的属性。IARNGCE和NIARC也表现出了较好的约简能力,但提取的属性数目仍然明显多于IAUNR,可能的原因包括其自身算法的分类能力低于IAUNR算法,而且这两个算法没有加入检查冗余属性的操作。

3.5 IAUNR算法中不确定性阈值对增量算法的影响

在IAUNR算法中,不确定性阈值对3类样本的划分有着直接的影响,而且主要影响的是不确定性大的样本(第3类)。根据第2节可知,不确定性阈值变大,则第3类样本减少,参与更新计算的样本减少会降低时间耗费,但可能会引起精度的降低。由于一般情况下,大多数样本属于第1类样本,尤其是当原始约简结果已经具有较高的精度时,不确定性区间在较小范围内的变动，对属性约简的更新影响不大。但是，当现有的信息系统比较复杂时,即第2种和第3种类型样本集的数量本身比较多时,那么不确定性大且被正确分类的样本数较多,此时选择比较准确的不确定性阈值是非常重要的,理想的阈值既可以使得参与更新的样本集规模尽可能达到最小,大大减少计算量,又可以有效地更新属性约简,使其分类能力达到最大。

本文在选用模糊k近邻(FKNN)计算不确定性时,使用的是k个近邻中每类样本占k值的比例,是一个由离散值计算出的结果,得到的也是离散的不确定性值,即阈值可在有限个离散值中选取。

为简单讨论不同阈值对结果的影响,本节采用随机生成3个高斯分布的样本集,分别有200、250、200个样本,原始属性有20个,类别数分别有3、3、4类。分别加入随机产生的100、50、100个样本到原数据集中。本实验主要研究不确定性阈值对增量算法的影响,不考虑其他参数,故统一设置邻域半径为0.1,FKNN中k取3。首先，根据定义10计算全部情况的不确定性大小,对一个样本的3-近邻共有3种分布[0,0,3]，[0,1,2]，[1,1,1],可对应不同不确定性大小分别约等于0、0.918 3、1.585 0。取[0,1,2]所对应的0.918 3作为不确定性阈值,然后将阈值增大,取[1,1,1]所对应的1.585 0作为对比。实验结果如表4，其中,原属性约简结果指增量前的属性结果。

表4的实验结果表明,当不确定性阈值增大时,由于参与更新计算的样本减少,因此，所消耗的时间有所减少,但同时可能会因为信息丢失导致分类精度有所下降。通过上述实验结果可知,本文在11个采用的数据集上根据二分类问题选取的不确定性阈值是倾向于保留更多样本,减少精度损失。当然阈值的选择与类别数有密切的关系,类别数越多,可选择的不确定性离散值也越多。

表4 不同不确定性阈值的比较

4 结语

增量方法是应对当今大数据快速变化的一个重要方法,邻域粗糙集框架下研究连续值属性也具有重要意义。考虑不同区域样本对属性约简贡献程度不同的问题,本文提出了基于不确定性和邻域关系粗糙集的增量属性约简方法,使用不确定性和分类器结果衡量样本的贡献大小,将其分为3种不同类型,并给予不同的更新策略。当样本增加时,只选择重要的样本参与约简的更新计算,提出了相应的增量属性约简算法,并通过大量实验结果表明该算法的有效性。相比现有的增量方法,所提方法可处理连续值信息系统,进一步降低了约简更新的时间代价,同时保持了很好的分类精度。需要进一步讨论的问题是，针对类别数量较多、具有复杂边界数据集上的不确定阈值的选择和优化;另外,本文的增量方法是针对有监督样本增加的情形,接下来将进一步探究无监督样本加入时的增量属性约简问题。