邓志轩 郑忠龙 邓大勇

大数据时代下，数据快速扩展，在生产实践中获得的属性越来越多.一部分属性可能是冗余的或与分类任务无关，在进行任何进一步数据处理之前都需要将它们删除.属性约简(或特征选择) 是一种用于减少属性的技术.其目的是找到最佳属性子集来预测样本类别.属性约简还可以促进数据可视化和数据理解[1].

属性约简过程中存在一个关键问题:属性评估.如何有效地评估属性是最重要的步骤之一，它直接影响分类器的性能.迄今为止已经提出了许多属性评估准则，例如信息熵[2]、依赖性[1]、相关性[3]和一致性[4]等.通常，不同的评估标准可能导致不同的最佳特征子集.但是，每项措施都旨在确定特征子集的区分能力.

粗糙集理论[5-6]是一种有效属性约简工具，产生了增量式约简[7]、动态约简[8]、多决策表约简[9]和并行约简[10-11]等属性约简方法.但是，传统粗糙集模型仅适用于非数值型数据.需要对数值型特征进行离散化，而离散化会带来信息损失.

研究者们通过拓展粗糙集模型来解决这一问题，如邻域粗糙集[12-21]、模糊粗糙集[22-25]等.文献[13-14]基于邻域信息粒子逼近，提出了邻域信息决策模型和数值型属性的选择算法，能够无须离散化而直接处理数值型属性，解决了离散化带来的信息损失问题，使粗糙集模型得以更方便地处理现实生活中大量存在的数值型变量.后继的研究者引入加权依赖度[15]、局部粗糙集[16]、模糊邻域与模糊决策[17]、Fish swarm 算法[12，18]等丰富了邻域粗糙集理论，并将其应用推广于多标记数据的特征选择[19]、并行属性约简[20]、动态图像分类[21]等方面.但并未考虑如何处理包含多个领域数据的数据集，而不同类型数据的处理准则和要求有所不同，如果放在同一个信息表中处理，处理结果往往不尽如人意.

F-粗糙集[26-29]是第一个动态粗糙集模型，其子集可以很好地表示不同情况下的概念，从而解决处理包含多个领域数据的动态属性约简问题.其后研究结合了模糊粗糙集[28]，初步应用于非数值型数据.F-粗糙集比较突出的应用在于概念漂移探测[29]，但相对较缺少非数值型数据处理方面的应用.

为了更好地解决邻域粗糙集和F-粗糙集所遇到的问题.本文结合邻域粗糙集和F-粗糙集的优势，提出了一种新的粗糙集模型—F-邻域粗糙集.首先定义F-邻域粗糙集的邻域关系，使用邻域决策子系统来表示不同情况.然后，使用F-属性依赖度和属性重要度矩阵来评估属性.充分考虑了在多种情况下同一概念的不同，同时克服了邻域粗糙集模型和F-粗糙集模型的缺陷.最后设计了两个属性约简算法，证明了约简结果的等价性，并说明了它们的适用范围.实验结果表明，相对于邻域粗糙集、F-粗糙集和主成分分析(Principal component analysis，PCA)，本文算法能获得更好的分类准确率.

1 基础知识

本节简单介绍邻域粗糙集[13-14]和F-粗糙集[26-27]的基本概念.

1.1 邻域粗糙集

在信息系统IS=(U，A) 中，U={x1，x2，···，xn}为实数空间上的非空有限集合.如果A为条件属性，d为决策属性，则称(U，A，d) 为一个决策系统.

定义1[13].对于xk ∈U，定义xk的邻域为

1.2 F-粗糙集

F-粗糙集是一个拥有多个信息表(或决策表)的粗糙集模型，它与其他粗糙集模型具有很好的兼容性.下面介绍F-粗糙集的基本概念.用FIS={ISi:ISi=(Ui，A)，i=1，2，···，n}表示信息系统簇，与其对应的决策系统簇用F表示，其中，ISi=(Ui，A)，而DTi=(Ui，A，d).

图1 概念X 在FIS 中的上近似、下近似、边界区域、负区域Fig.1 Concept X in the FIS upper approximation，lower approximation，boundary region，and negative region

2 F-邻域粗糙集

本节结合邻域粗糙集和F-粗糙集，定义了F-邻域粗糙集的基本概念，包括F-邻域上下近似、边界区域等;提出F-邻域依赖度并证明其单调性，提出属性重要度矩阵.

注2.数据类型为数值型，或者混合数据类型，即有些是数值型，另一些是非数值型.

2.1 F-邻域粗糙集的基本概念

F-邻域粗糙集继承了F-粗糙集的动态性.不同的信息子系统包含的信息是不一样的，随着时间或空间的变化而变化，F-邻域粗糙集与F-粗糙集一样包含了这些变化信息，而且可以研究这些变化.

例1.设F={NDT1，NDT2}，邻域决策系统NDTi=(Ui，A，d)，a，b，c是条件属性，d是一个决策属性，f(x，a) 表示样本在属性a上的取值，具体各个样本在属性a，b，c，d上的取值如表1 和表2所示.

概念X的邻域δ(x) 在NDT1和NDT2中是不同的，当指定邻域大小为0.5 时(为了方便计算采用欧氏距离)，x在条件属性{a，b，c}下的邻域计算式为

表1 邻域决策子系统NDT1Table 1 A neighborhood decision subsystem NDT1

表2 邻域决策子系统NDT2Table 2 A neighborhood decision subsystem NDT2

2.2 F-邻域并行约简

F-邻域粗糙集的属性约简，结合了邻域粗糙集处理连续型数据和F-粗糙集的动态性的优点，可以对数值型数据和动态变化的数据进行约简.

通过定义7 将并行约简的概念扩展到邻域决策系统中，定义8 和定义9 是对邻域决策系统属性重要度的扩展，假设F中只含有一个邻域决策系统，那么，F-邻域属性重要度即为该决策系统的邻域属性重要度.F-邻域粗糙集的属性重要度有以下性质:

性质1.B1是邻域决策子系统NDT ∈F的一个约简，则存在一个F-邻域并行约简B2使得B1⊆B2.

性质2.如果a为一个邻域决策子系统NDT ∈F的核属性，则a为F-邻域并行约简的核属性.

性质3.如果a为F-邻域并行约简的核属性，则存在一个邻域决策子系统NDT ∈F，使得a为NDT的核属性.

性质1～3 可以根据F-邻域并行约简、核属性的定义直接得出.

定理1.在一个邻域决策系统簇F中，F-邻域依赖度γ(F，B，d) 具有单调性，如果B1⊆B2⊆··· ⊆A，则γ(F，B1，d)≤γ(F，B2，d)≤··· ≤γ(F，A，d).

因为γ(F，B，d) 的单调性，根据文献[30]中的定律1，γ(F，B，d) 可以作为属性约简准则，由此可得到定理2.

定理2.在一个邻域决策系统簇F中，B ⊆A是F的邻域并行约简，当且仅当B ⊆A满足下面两个条件:

2) 证明确保F-邻域并行约简的最小性.

假设存在S ⊂B，使得γ(F，S，d)=γ(F，A，d).根据1) 可知:POS(F，S，d)=POS(F，A，d)，即S是F的F-邻域并行约简，与B ⊆A是F的F-邻域并行约简矛盾. □

根据以上性质和定理，还可以得到以下两个命题:

命题1.给定一个邻域决策子系统簇F，a ∈B⊆A.如果σ(B，a)=0，则属性a可以被约简.

σ(B，a)=0 表明，如果属性a被约简，F的所有决策子系统也能保持正域不变.

命题2.给定一个邻域决策子系统簇F，a ∈A，若σ(A，a)＞0，则属性a为F-邻域并行约简的核属性.

σ(A，a)＞0 表明，如果属性a被约简，至少有一个邻域决策子系统不能保持正区域不变，所以属性a为F-邻域并行约简的核属性.

2.3 属性重要度矩阵

第2.1 节已经构建了F-邻域并行约简的概念.本小节引入属性重要度矩阵并证明F-邻域属性重要度和属性重要度矩阵构建的约简准则等价.

文献[27]所提出的属性重要度矩阵是求并行约简的一种方法，基于此我们构造了F-邻域并行约简，属性重要度矩阵的定义如下:

定义11.F是一个邻域决策系统簇，NDTi=(Ui，A，d)∈F，i=1，2，···，n，B ⊆A，B关于F的属性重要度矩阵定义为

其中，σij=σ(aj，Ui)=γi(Ui，B，d)－γi(Ui，B－{aj}，d)，aj ∈B，n表示F中邻域决策子系统的个数，m表示条件属性的个数.矩阵H[B，F]的行表示不同的属性在同一邻域决策子系统下的属性重要度，列表示相同的属性在不同邻域决策子系统下的属性重要度.

定理3.在一个邻域决策系统簇F中，B ⊆A是F的F-邻域并行约简，当且仅当B ⊆A满足下面两个条件:

i)POS(F，B，d)=POS(F，A，d);

ii) 属性重要度矩阵H[B，F]中没有全零的列.

证明.条件i) 确保了F-邻域正区域保持不变;条件ii) 确保了F-邻域并行约简的最小性.

1) 条件i) 由定义9 直接得出;

2) 证明确保F-邻域并行约简的最小性.

反设:属性重要度矩阵H[B，F]中有全零的列，使得B ⊆A是F的F-邻域并行约简.由于σij=γi(Ui，B，d)－γi(Ui，B－{aj}，d)，σij=0 说明属性aj在Ui中对依赖度无影响，若aj所对应的列元素全为零，表明σj=γ(F，B，d)－γ(F，B－{aj}，d)=0，则有B－{aj} ⊂B，γ(F，B－{aj}，d)=γ(F，B，d)，与定理2 矛盾.

定理2 的约简准则等价于定理3 的约简准则，定理2 中第1 部分的证明已得出定理2 与定理3 的条件i) 等价;H[B，F]中没有全零的列，由定理3可知B中所有属性对γ(F，B，d) 都有影响，则有任意S ⊂B，γ(F，S，d)(F，B，d)⇔γ(F，S，d)/=γ(F，A，d).

因为定理2 和定理3 的约简准则等价，所以可以用F-邻域属性重要度和邻域属性重要度矩阵来求得F-邻域并行约简，两种方法求得的约简结果是相同的，具体算法可见第3.2 节.

为了求属性约简，需要定义H的改进矩阵H′，改进矩阵H′定义如下.

定义12.F是一个邻域决策系统簇，NDTi=(Ui，A，d)∈F，i=1，2，···，n，B ⊆A，B关于F的改进属性重要度矩阵定义为

H′是H的改进矩阵，若aj ∈B，则σ′ij=0，这意味着随着B中包含的属性越多，H′就越稀疏.如果B中的属性随时间变化而增多，直到POS(F，B，d)=POS(F，A，d)，也就是H′为零矩阵为止，这就是一个增量式约简过程.

3 约简算法

属性约简是粗糙集理论最重要的应用之一，而并行约简是属性约简的一个重要延伸.并行约简是在若干个信息子系统(或决策子系统) 中寻找稳定的、泛化能力强的条件属性约简.基于属性重要度，有以下F-邻域并行约简算法(算法1)，本算法借鉴了文献[27]算法的思想，根据属性集A中各元素在邻域决策子表簇F中的属性重要度找到属性核，然后通过属性重要度找到其他属性.

算法1 首先从局部的邻域决策子表中计算出决策属性对条件属性的依赖度和条件属性的属性重要度，得出各个子表的核属性，然后，从邻域决策子表簇整体出发，计算出条件属性的属性重要度，最后，得出原属性集的一个F-邻域并行约简.

算法1 的时间复杂度主要由F-邻域属性重要度和步骤4 的时间复杂度决定.其中计算一个条件属性的F-邻域属性重要度的时间复杂度为U代表决策子表中数据的个数，m代表条件属性的个数.在最坏的情况下，步骤4 需计算次F-邻域属性重要度.因此算法1 的时间复杂度为

基于属性重要度矩阵，有以下F-邻域并行约简算法(算法2)，根据属性重要度矩阵H(A，F) 找到属性核B，然后通过建立B的改进属性重要度矩阵H′找到其他属性，直到H′(P，F) 为零矩阵为止.

算法2 是根据定义13 和定义14 构造F-邻域并行约简算法.邻域并行约简P先从空集开始，通过计算不同(相同) 的属性在同一(不同) 邻域决策子系统下的属性重要度建立属性重要矩阵，先从中选出所有子系统中属性重要度都不为零(即矩阵H中没有零元素的列) 所对应的属性加入P中，然后计算改进属性重要度矩阵H′把非零元素个数最多的列所对应的属性加入P中，直到H′为零矩阵.该算法保证了对正区域有影响的属性不会被删除.

算法2 的时间复杂度主要是由建立矩阵以及改进矩阵组成，使用与算法1 相同的方法计算属性重要度，它的时间复杂度为O(mUlogU)，其中，U代表决策子表中数据的个数，m代表条件属性的个数，那么建立一个属性重要度矩阵的时间复杂度为O(nm2U′logU′)，其中，U′代表F中最大子表的数据个数，n代表子表个数.在最坏的情况下，改进的矩阵的个数为m，因此算法2 的时间复杂度为O(nm3U′logU′)，略高于算法1.

算法1 和算法2 的约简结果是相同的，所以在大部分情况下使用算法1 或算法2 并没有区别.算法1 使用的F-邻域属性重要度表明属性对邻域决策系统簇整体的影响;算法2 使用的属性重要度矩阵表明属性对邻域决策系统簇中各个子系统的影响.当实验需要测量属性对邻域决策系统簇的影响时应该使用算法1，实验需要测量属性对各个决策子系统的影响时应该使用算法2，实验对以上两个数据都需要时应该同时使用算法1 和算法2.

4 实验结果

本节在UCI 数据集、真实数据集以及MATLAB 生成数据集上进行实验，通过对比实验，验证了相对于邻域粗糙集、F-粗糙集和PCA，F-邻域粗糙集在分类准确率上都具有优势.

4.1 数据集

本节设计了一些实验来测试所提出的F-邻域粗糙模型的性能，使用UCI 数据库(http://archive.ics.uci.edu/ml/datasets.html) 中Iris 等9 个数据集;两个真实数据集Cevaluation，Rapequality;一个MATLAB 生成数据集Generated data.Cevaluation 数据集来自于国内某高校研二、研三的研究生综合测评数据，包含240 个样本和26 个属性，其中研二和研三的综合测评计分规则不同.Rapequality数据集用于描述油菜加工品质，包含138 个样本和26 个属性.如表3 所示.

4.2 实验设置

实验的目的是验证F-邻域粗糙集约简的有效性，并通过对比约简后属性子集的分类质量揭示它的可行性.由于本次实验使用算法1 与算法2的约简结果的等价性，在实验中使用的算法为算法2.实验的评估是使用决策树模型中比较稳定的CART 分类器，以10 折交叉验证计算分类准确率，以分类准确率的高低为标准.同时为了构造邻域决策系统簇F，对每个数据集进行了分块，每一块都作为一个邻域决策系统.实验选取δ=0.1，δ=0.05，δ=0.01 三个邻域参数进行验证，所有算法在MATLAB R2018a 上实现.

表3 数据集描述Table 3 Description of datasets

4.3 实验结果与分析

先与NRS 进行比较，目的是为了比较NRS 与NPRMS 的约简质量.因此，计算两种算法基于CART 分类器在δ=0.1，δ=0.05，δ=0.01 下的分类准确率，如表4～6 所示.

从表4～6 中可以发现，在3 个参数下，除了abalone 数据集在邻域0.1 和0.05 下没有约简，其他情况下两种方法都能有效地减少属性.虽然在除soy，Iris，wine 和Cevaluation 之外的数据集上，F-邻域并行约简(NPRMS) 的约简属性子集数目要高于NRS，但是在wpbc，sonar，debrecen，EEGEye和Generated data 数据上，NPRMS 仅仅多出了一个属性，在分类准确率上则提升了5～17.5 个百分点不等.其在这些数据集上分类准确率的大幅提升可以表明，NPRMS 在这些数据集上的性能要优于NRS.值得注意的是在Rapequality 数据集上，当参数为0.1 和0.5 时，NPRMS 和NRS 的约简完全相同;当参数为0.01 时，NPRMS 的约简子集还是没有变化，NRS 则减少了两个属性，降低了3个百分点的分类准确率.在Rapequality 数据集上，NPRMS 有效地保留了决策子系统中的有效信息，而NRS 约简掉两个属性时分类准确率出现了明显降低，说明NRS 在参数为0.01 的约简中丢失了有效信息，NPRMS 的表现符合我们为了有效地保留有效信息而把F-粗糙集引入邻域粗糙集的初衷.

表4 δ=0.1 时两种算法约简的结果Table 4 Results of two algorithm reductions when δ=0.1

表5 δ=0.05 时两种算法约简的结果Table 5 Results of two algorithm reductions when δ=0.05

由于F-粗糙集并行约简(OPRMAS)[29]不能直接处理数值型数据，先把数据进行离散化处理，再通过OPRMAS 算法约简，根据约简结果从原数据中挑选出这些属性数据，经过CART 分类器判别得到最后结果.我们选取邻域参数δ=0.01 时，NRS与NPRMS 的结果与之进行比较.PCA 是经典的特征选择方法，其对于条件属性的特征选择不需要决策属性，所以我们在使用PCA 进行降维时，去除了数据中的决策属性，在判别分类准确率时，再将决策属性加入已降维的数据进行判别;其还可以控制保留属性的数目，为了方便比较，将PCA 保留属性的数目设置为与NPRMS 相同.

从表7 和图2 中可以看出，在NRS 和NPRMS选择合理的邻域参数的情况下，NRS，OPRMAS，PCA，NPRMS 四种方法的属性数目和分类准确率比较.NPRMS 较于NRS 分类准确率有所提升，且约简子集数目并未显著增加，特别是在Cevaluation 上，由于其研一、研二两部分测评规则的不同，NRS 表现得并不好，而OPRMAS 和NPRMS 的约简效果明显优于NRS 和PCA;虽然OPRMAS在sonar，spambase 和EEGEye 上分类准确率要高于NPRMS，但其在sonar 和spambase 上的约简子集中属性数目多于NPRMS，在EEGEye 上更是并未减少数据集原本的属性数目，而在Cevaluation 上两种方法虽然约简结果相同，但NPRMS 比OPRMAS 少了离散化的步骤，因此具有一定优势.

表6 δ=0.01 时两种算法约简的结果Table 6 Results of two algorithm reductions when δ=0.01

表7 在各个数据集中三种算法约简的结果Table 7 Results of three algorithmic reductions in each dataset

图2 在各个数据集中算法的分类准确率Fig.2 Classification accuracy of algorithms in each dataset

造成以上实验结果的原因有:1) NRS 算法由于邻域半径造成的信息丢失等原因，所得的并不是最优约简，而NPRMS 是动态约简，可以有效地减少信息损失;2) 在样本数量多属性数目少的数据集中，离散化带来信息损失尤为明显，使OPRMAS 在这类数据集上的约简效果较差，甚至可能并无约简效果，而NPRMS 不需要离散化，保留了必要的信息，从而可以实现较好的约简;3) 在有的数据集中包含多种规则，NRS 等大部分算法并没有考虑这种情况，只是把其当作一般的数据集一样约简，所以其约简后的分类准确率并不理想;而OPRMAS 正是基于这种情况而诞生的算法，这种数据集下它的约简效果较好是可以预见的;NPRMS 结合了OPRMAS这方面的优点，也能较好地适用于该类数据集的约简.

NPRMS (或 NPRAS) 相 较 于 NRS 和OPRMAS，准确率有所提升，其性质又决定了其具有更广泛的适用范围，因此F-邻域并行约简更具优势.

5 结论与展望

减少冗余属性可以提高分类性能并降低分类成本.在本文中，首先介绍了两种粗糙集模型:F-粗糙集和邻域粗糙集.由于两种粗糙集模型都具有自身的优势，但双方都未考虑对方的优点，因此提出了F-邻域粗糙集.该模型结合了两个粗糙集模型的优势，是一个无需离散化处理数值型数据的动态粗糙集模型.最后，用F-属性重要度和属性重要度矩阵来评估属性，使用它们来设计属性约简算法，并说明两种算法的相同点和不同点.实验结果表明两种算法能获得较高的分类准确率.实验中还发现决策子系统的划分对所提出的两种属性约简算法的性能的影响较大.应该根据属性数目和数据项数目为每个数据集选择合适的决策子系统划分.

未来的工作可能包括:1) 如何将所提出的模型应用于具有不确定性的分类学习和推理领域;2) 在所提出的模型中，在数据集中划分决策子系统对所提出算法的性能具有重要影响.它需要由用户提前划分.如何为每个数据集自动自动划分决策子系统的最佳解决方案也是一项有意义的工作.