共现邻域关系下的属性约简研究

毛振宇 ,窦慧莉* ,宋晶晶,3 ,姜泽华 ,王平心

（1.江苏科技大学计算机学院，镇江，212003；2.江苏科技大学理学院，镇江，212003；3.数据科学与智能应用福建省高校重点实验室，漳州，363000）

作为一种常用的粒计算方法，邻域信息粒化［1-4］因其处理连续型甚至混合型数据的有效性受到广大学者的关注与青睐.事实上邻域信息粒化的核心机制就是从样本之间的距离出发，通过给定一个半径来约束样本间的相似性程度，最终确立合适的邻域关系.不难发现，该过程中指定的半径对最终的信息粒化结果有不容忽视的影响，而不恰当的半径设置往往造成负面的影响，譬如，指定半径较大时不同类别的样本极有可能落入同一邻域，从而引起邻域中信息的不精确或不一致.针对该现象，Yang et al［5］提出一种伪标记邻域信息粒化策略，参考样本在条件属性上相似性程度的前提下，进一步对生成的样本伪标记加以考虑，该策略能够在一定程度上减缓半径较大时邻域中信息的不精确或不一致问题.

然而，不同的半径会使邻域关系或伪标记邻域关系产生不同的区分能力，值得注意的是这两种区分能力的产生仅仅依赖样本间的距离以及半径的大小，而忽视了邻域信息粒内部不同样本所对应的邻域之间的结构关系［6］.鉴于此，本研究引入邻域之间的距离度量，提出一种新型的共现邻域信息粒化机制，以期能够深入挖掘邻域信息粒之间的内在关联与隐含关系；在此基础上分别给出两种类型的上下近似算子，进而实现了共现邻域粗糙集模型与伪标记共现邻域粗糙集模型；此外，还利用前向贪心搜索策略［7-12］求解了两种模型下的约简结果.

1 基础知识

1.1 邻域粗糙集粗糙集理论中，一个决策系统可以表示为二元组，其中U是所有样本组成的非空有限集合，即论域；AT是所有条件属性集合；D是决策属性且AT∩D=∅.U/IND(D)={X1，X2，…，XN} 表示根据决策属性D所诱导出的论域上的划分，∀Xi∈U/IND(D)，Xi表示第i个决策类且1≤i≤N.

定义1给定一个决策系统DS，∀B⊆AT，对于一个邻域半径δ，邻域关系可以定义为：

其中，disB(x，y)(∀x，y∈U)表示利用条件属性B所提供的信息计算得到样本x与样本y之间的距离.

∀x∈U，根据式（1），不难得到样本x关于B的邻域如下：

因此，{NB(x)：∀x∈U} 表示一个由条件属性B诱导的邻域粒化结果.

定义2给定一个决策系统DS，U/IND(D)={X1，X2，…，XN}，∀B⊆AT，D关于B的上近似和下近似可以定义为：

其中，∀Xi∈U/IND()D，决策类Xi的上近似和下近似可以定义为：

定义2 所示的上、下近似集刻画了目标概念的粗糙性.从这一角度出发，可以进一步量化地描述数据中的目标概念的确定性程度.因此通过定义2，Pawlak 给出如下所示的近似质量概念.

定义3给定一个决策系统DS，∀B⊆AT，D关于B的近似质量定义如下：

其中，|X|表示集合X的基数.

显然0 ≤γ(B，D)≤1 成立.γ(B，D)表示根据条件属性B，确定属于某一个决策类别的样本占全部样本的比例.

1.2 伪标记邻域粗糙集在传统邻域模型中，邻域粒化的结果和近似质量度量与邻域半径是紧密相关的.当半径较大时，不同决策类别的样本可能会出现在同一邻域范围内，这极有可能降低邻域分类器的性能.针对这一问题，Yang et al［5］提出一种伪标记邻域建模方法，在构造邻域信息粒的过程中引入伪标记策略，通过样本之间的距离和伪标记属性来共同区分样本.

定义4给定一个伪标记决策系统DSPL，∀B⊆AT，对于一个邻域半径δ，伪标记邻域关系可以定义为：

根据式（8），不难得到样本x关于B的伪标记邻域形如下：

对比式（1）和式（8），不难得到邻域关系和伪标记邻域关系之间存在形如的关系，即伪标记邻域关系比邻域关系更细；进一步，再通过式（2）和式（9），∀x∈U，显然成立，即伪标记邻域比邻域更小.

定义5给定一个伪标记决策系统DSPL，U/IND(D)={X1，X2，…，XN}，∀B⊆AT，D关于B的伪标记邻域上近似和下近似定义为：

其中，∀Xi∈U/IND(D)，决策类Xi的伪标记邻域上近似和下近似可以定义为：

类似邻域决策系统中的近似质量，根据定义5 可以得到伪标记邻域近似质量的定义如下所示.

定义6给定一个伪标记决策系统DSPL，∀B⊆AT，D关于B的伪标记邻域近似质量定义如下：

显然0≤γPL(B，D)≤1 成立.伪标记邻域近似质量的值越大，表示样本的不确定程度越低.

2 共现邻域

通过上节所示的两种邻域关系可以观察到，不同的半径会使邻域关系或伪标记邻域关系产生不同的区分能力，但这两种区分能力的产生仅仅依赖于样本间的距离以及半径的大小，而忽视了邻域信息粒内部不同样本所对应的邻域之间的结构关系.具体描述如图1 所示.

图1 邻域结构Fig.1 Neighborhood structure

观察图1，不难发现样本y1与y2属于同一个决策类别，且y2落入了y1的邻域.但是，y1所示的邻域中包含了大量的“方框”样本，而y2所示的邻域中却包含了大量的“三角”样本，因此这两个邻域在结构上是有显著差异的；并且y2被囊括在y1的邻域中，其合理性值得商榷.为解决这一问题，下文提出共现邻域的概念.

2.1 共现邻域粗糙集在式（1）所示邻域关系的基础上，进一步考虑邻域信息粒内部不同样本所对应的邻域之间的结构关系，可以定义如下所示的共现邻域关系.

定义7给定一个决策系统DS，∀B⊆AT，对于一个邻域半径δ，共现邻域关系可以定义为：

其中，DIS(NB(x)，NB(y))表示样本x的邻域与样本y的邻域之间的距离，α为设定的阈值.

根据Jiang and Chen［6］提出的邻域间距离的形式，DIS(NB(x)，NB(y))可表示为：

定义7 表示共现邻域关系的两个约束条件：（1）样本间的距离小于或等于给定半径；（2）样本邻域之间的距离小于或者等于给定阈值.

根据式（15），可以得到x关于B的共现邻域：

性质1给定一个决策系统DS，∀B⊆AT，CNB⊆NB成立.

证 明根据式（1）和式（15）的表现形式，CNB的约束条件显然比NB的约束条件更苛刻，因此CNB⊆NB显然成立.

性质2给定一个决策系统DS，∀B⊆AT，CNB(x)⊆NB(x)成立.

证 明根据式（2）和式（17）的表现形式以及性质1，CNB(x)的约束条件显然比NB(x)的约束条件更苛刻，因此CNB(x)⊆NB(x)显然成立.

从上述性质可知，和邻域关系相比，共现邻域关系有更高的分辨能力.

定义8给定一个决策系统DS，U/IND(D)={X1，X2，…，XN}，∀B⊆AT，D关于B的共现邻域上近似和下近似可以定义为：

其中，∀Xi∈U/IND(D)，决策类Xi的共现邻域上近似和下近似可以定义为：

性质3给定一个决策系统DS，∀Xi∈U/成立.

证 明∀x∈-NB()Xi，根据式（6）可以得到NB(x)⊆Xi，再通过性质2，可知CNB(x)⊆NB(x)成 立，因 此 显 然 有CNB(x)⊆Xi，进 而成立，即

定义9给定一个决策系统DS，∀B⊆AT，D关于B的共现邻域近似质量定义如下：

显然0 ≤γCN(B，D)≤1 成立.当∅时，共现邻域近似质量会达到最小值0；当时，共现邻域近似质量会达到最大值1.

性质4给定一个决策系统DS，∀B⊆AT，有γCN(B，D)≥γ(B，D)成立.

证 明根据性质3 所示的结果，性质4 显然成立.

上述命题表示与传统邻域相比较，采用共现邻域的方法可以得到一个更高的近似质量.

2.2 伪标记共现邻域粗糙集在式（8）所示伪标记邻域关系的基础之上，进一步考虑样本邻域信息粒内部不同样本所对应的邻域之间的结构关系，可以定义如下所示的伪标记共现邻域关系.

定义10给定一个伪标记决策系统DSPL，∀B⊆AT，对于一个邻域半径δ，则伪标记共现邻域关系可以定义为：

定义10 表示了伪标记共现邻域关系的三个约束条件：（1）样本之间的距离小于或者等于给定半径；（2）样本之间的伪标记值相等；（3）样本邻域之间的距离小于或者等于给定阈值.

根据式（23），可以得到样本x关于B的伪标记共现邻域：

类似共现邻域中的近似质量，根据定义11，可以得到伪标记共现邻域近似质量的定义如下所示.

定义12给定一个伪标记决策系统DSPL，∀B⊆AT，D关于B的伪标记共现邻域近似质量定义如下：

性质8给定一个伪标记决策系统DSPL，∀B⊆AT，有(B，D)成立.

证 明根据性质7 所示的结果，性质8 显然成立.

上述命题表示与伪标记邻域相比较，采用伪标记共现邻域的方法可以得到一个更高的近似质量.

2.3 共现邻域求解算法由以上论述可知，共现邻域与传统邻域相比，其所对应的二元关系更严格；类似地，伪标记共现邻域与伪标记邻域相比，其所对应的二元关系也更严格.以下给出一个具体的算法流程用于求解共现邻域关系，伪标记共现邻域关系的求解过程类似可得.

上述算法的时间复杂度为O(|U|2∙ |B|)，其中|U|为论域中样本数目，|B|为使用的条件属性数目，具体分析如下：

（1）步骤2 计算论域中每一个样本的邻域，此时需要求得论域中任意两个样本之间的距离，因而该步骤的时间复杂度为O(|U|2∙ |B|).

（2）步骤3 考虑了邻域结构之间的关系，且通过利用邻域距离来刻画不同样本的邻域之间的相似性程度，该步骤的时间复杂度为O(|U|2).因为对于任意一个样本x，在最坏的情况下，其邻域囊括了论域U中的所有样本且这些样本的邻域也都为U本身.

综上，算法整体时间复杂度为O(|U|2∙ |B|).

3 实验分析

为验证共现邻域方法的有效性，从UCI 数据集中选取12 组数据，基本信息如表1 所示.

表1 数据集的描述Table 1 Discription of datasets

为了对比分析四种不同方法：传统邻域关系（NR）、共现邻域关系（CNR）、伪标记邻域关系（PLNR）、伪标记共现邻域关系（PLCNR），分别利用这些关系所构建的粗糙集依据近似质量这一度量准则进行属性约简［13-19］的求解，约简的求解进程都采用前向贪心搜索策略.实验选取20 个不同的半径δ，分别为0.025，0.05，0.075，…，0.5，采用五折交叉验证的方法，用于对比各种方法下的约简率以及约简中属性的分类准确率.

在共现邻域关系的构造中，将阈值α设置为所有邻域距离的平均值.在约简的约束条件构造中，还设置了两个不同的约束条件以实现近似约简［20］的目的，即近似质量保持不变（ε=1），近似质量高于原始属性近似质量值的95%（ε=0.95）.

3.1 约简率对比表2 展示了四种不同方法在不同阈值ε下的约简率结果比较，表中下画线表示相同阈值下，NR 方法与CNR 方法对比时较大的约简率结果，PLNR 方法与PLCNR 方法对比时较大的约简率结果.这些约简结果是在20 个半径下利用五折交叉验证得到结果的均值.约简率越高，表示删除的冗余属性就越多.

观察表2，不难得出以下结论：

（1）无论ε取值为1 还是0.95，和传统邻域关系相比，采用共现邻域关系的方式能够得到较高的约简率，这意味着采用共现邻域的方法有助于删掉更多的冗余属性.类似地，与伪标记邻域关系相比，采用伪标记共现邻域关系的方式亦能够得到较高的约简率.

（2）当ε从1 降低为0.95 时，无论采用哪一种方法，约简率都能得到提升.这主要是因为当ε降低时，属性约简中的约束条件会进一步放宽.例如，当采用NR 方法时，若ε=1，则12 个数据上的平均约简率为0.4173，而ε=0.95 时，12 个数据上的平均约简率为0.4940.

3.2 分类准确率对比在本组实验中，采用KNN（K=3）分类器和SVM 分类器，利用约简结果对测试集数据进行分类，并且计算分类准确率，最后求得分类准确率的平均值和最大值.分类准确率均值结果如表3 与表4 所示，分类准确率最大值结果如表5 与表6 所示.表中下画线表示相同阈值下，NR 方法与CNR 方法对比时较大的分类准确率，PLNR 方法与PLCNR 方法对比时较大的分类准确率.

从表3 和表4 中可以看出，无论是采用KNN分类器还是SVM 分类器，利用传统邻域关系与共现邻域关系所求得的约简，其对应的平均分类准确率差异甚微，这一现象在伪标记情形下也依然存在.换言之，针对属性约简这一问题，虽然3.1 节的结果表明了共现邻域方法能够删除较多的冗余属性，但最终的结果在绝大部分情况下并不会降低平均分类准确率.

表2 四种方法在不同阈值下的约简率Table 2 The reduction rate of four methods under different thresholds

表3 四种方法在不同阈值下的KNN 分类准确率均值Table 3 The average KNN classification accuracies of the four methods under different thresholds

从表5 和表6 可以看出，无论是采用KNN 分类器还是SVM 分类器，利用传统邻域关系与共现邻域关系求得的约简，其对应的最大分类准确率差异甚微，这一现象在伪标记情形下也依然出现.换言之，针对属性约简这一问题，虽然共现邻域方法能够删除较多的冗余属性，但最终的结果在绝大部分情况下并不会降低最大分类准确率.

表4 四种方法在不同阈值下的SVM 分类准确率均值Table 4 The average SVM classification accuracies of the four methods under different thresholds

表5 四种方法在不同阈值下的KNN 分类准确率最大值Table 5 The maximum KNN classification accuracies of the four methods under different thresholds

4 结论

在粗糙集方法中，针对已有的邻域关系和伪标记邻域关系忽略不同样本所对应的邻域结构之间的差异性这一问题，提出一个共现邻域的策略，并且定义了共现邻域关系、伪标记共现邻域关系，构建相应的粗糙集模型，继而讨论了不同关系下粗糙集模型之间的内在联系.实验结果表明，相较于传统邻域关系与伪标记邻域关系，采用共现邻域关系与伪标记共现邻域关系，计算约简结果，可以获得一个较高的约简率，并且所得到的约简并不会显著降低分类的准确率.下一步的工作：

表6 四种方法在不同阈值下的SVM 分类准确率最大值Table 6 The maximum SVM classification accuracies of the four methods under different thresholds

（1）本研究仅仅选择了近似质量这一个度量准则，后续可以考虑邻域决策错误率、条件熵等其他度量准则，从而可以得到更好的约简结果来提高后续分类准确率.

（2）本研究从邻域之间的结构关系出发，实现了共现邻域求解方法，下一步还可以在模糊粒［21］结构框架下，设计共现模糊关系.