康 猛，蒙祖强

（广西大学计算机与电子信息学院，广西南宁 530004）

0 引言

1982 年，波兰数学家Pawlak 提出了粗糙集理论［1］，它是继概率论、模糊集、证据理论之后的又一个处理不确定性问题的数学工具。自粗糙集理论提出以来，属性约简［2］一直是粗糙集领域的重点研究内容之一。属性约简本质上是一个搜索寻优问题，但最小属性子集的搜索是一个不确定多项式（Non-deterministic Polynomial，NP）问题［3］，因此学者们致力于用启发式搜索算法寻找属性约简的次优解。目前，国内外学者已经提出了许多属性约简算法，典型的有：基于正区域的属性约简［4-7］、基于差别矩阵的属性约简［8-10］、基于信息熵的属性约简［11-14］等。然而，这些算法普遍存在约简结果分类精度低、时空复杂度高等问题。

利用区分矩阵设计属性约简算法具有直观易理解的优点。区分矩阵的元素是能够区分该元素对应的两个实例的属性集合。若属性能够区分的对象越多，即区分能力越强，则它对论域的划分就越细，知识粒度就越小，该属性就越重要，因此，利用属性的区分能力来决定属性的重要性是一种合理的方法；但区分矩阵存在计算复杂度高和存储开销大等问题。为提高约简算法效率，文献［15］提出了一种利用二进制区分矩阵降低时间开销的约简算法；文献［16］提出了一种基于集中有序区分集的属性约简算法，将时空复杂度分别降低为max｛O（|C||U′pos||U/C||MsCount|），O（|C|2|MsCount|）｝和O（|MsCount|）（其中C为条件属性集，U为论域，U′pos为简化的决策表，MsCount为简化决策表差别集的基数）；文献［17］为了降低区分矩阵法的计算复杂度，利用快速计数排序算法处理数据，构建了改进的区分矩阵，给出了一种新的属性约简算法；文献［18］对基于优势的粗糙集方法进行扩展，提出了优势可辨矩阵的概念，进一步提出了一种基于优势区分矩阵的属性约简算法；文献［19］提出了一种新的属性质量度量方法和相对区分度，从区分的角度提出了一种新的属性约简算法；文献［20］针对决策系统中的不可区分关系及可区分关系，给出相应的协调集判定定理，进而借助区分矩阵及区分函数给出属性约简方法；文献［21］设计了一种更简化的区分矩阵，不需要生成所有的形式化决策上下文，进一步提出了一种新的形式化决策上下文属性约简方法，降低了算法的时空复杂度。

上述算法［15-21］几乎都是通过优化区分矩阵或通过划分等价类计算属性的区分能力来降低算法的时空复杂度，但是没有考虑到区分矩阵的构建及区分能力的计算都具有很高的时空复杂度。针对这一不足，本文在区分关系的基础上，定义了条件区分能力，给出了基于条件区分能力的属性约简算法；又利用大数定律将条件区分能力扩展为局部条件区分能力，加快了属性重要度的计算，进而提出了一种基于局部条件区分能力的高效属性约简算法。实验结果表明，本文算法具有更低的时空复杂度。

1 基本概念

定义1［1］形式上，四元组IS=〈U，A，V，f〉表示一个信息系统，其中：U为非空有限集合，称为论域；A为属性集，若A=C∪D，C∩D=∅，则C为条件属性集，D为决策属性集；V为值域；f：U×A→V为信息函数，表示每个对象的每个属性对应一个属性值。具有条件属性集和决策属性集的信息系统称为决策表，简记为IS=〈U，A〉或IS=〈U，C∪D〉。

定义2［1］在信息系统IS=〈U，A〉中，对于给定属性集P⊆A，P在IS上的不可区分关系记为IND（P），定义如下：

IND（P）=｛（x，y）∈U×U|a∈P，f（x，a）=f（y，a）｝

对于，x∈U，令［x］=｛y∈U|（x，y）∈IND（P）｝，显然，［x］称为等价类；令U/P=｛［x］|x∈U｝，称为U的一个划分。

P在IS上的区分关系记为DIS（P），定义如下：

DIS（P）=｛（x，y）∈U×U|∃a∈P，f（x，a）≠f（y，a）｝

对于，（x，y）∈DIS（P），（x，y）称为P的区分对。本文将IND（P）和DIS（P）分别称为不可区分集和区分集。

定义3［1］设U为一个论域，P为定义在U上的一个等价关系簇。如果每个关系R∈P在P中都是绝对必要的，则称关系簇P是独立的；否则，称关系簇P是相互依赖的。

定义4［1］在信息系统IS=〈U，C∪D〉中，对于给定属性集B⊆C，如果IND（B）=IND（C）且B是独立的，则称B是C的一个约简。B中所有必要关系的集合称为B的核，记为core（B），则core（B）=∩red（B）。

定义5在决策表IS=〈U，C∪D〉中，假设U=｛x1，x2，…，xn｝是论域，C=｛a1，a2，…，am｝为条件属性，D=｛d｝为决策属性，令ai（xj）是样本xj在属性ai上的取值，定义矩阵M=（mij|i，j=1，2，…，n），其中：

mij表示区分矩阵中第i行第j列的元素，矩阵M称为区分矩阵。

2 条件区分能力

本章主要介绍条件区分能力的相关定义、定理，并给出相关算法。

2.1 区分能力

在粗糙集理论中，知识被认为是属性的识别能力，同一等价类中的对象不能相互区分，而不同等价类中的对象可以相互区分。因此，给定属性集的知识内容可以量化为其在论域上的可区分对的总数，即属性集在论域上的区分集大小。属性的区分集越大，该属性的区分能力越强，反之越弱。

定义6在信息系统IS=〈U，A〉中，对给定属性集B⊆A，B的区分能力记为E（B），定义如下：

E(B)=|DIS(B)|

属性约简要求保持原知识库分类能力不变，这种分类能力在决策表中是指条件属性集相较于决策属性集的分类能力。因此，当某个可区分对不属于决策属性集的区分集DIS（D）时，即使它属于某个条件属性a的区分集DIS（｛a｝）也是没有意义的，即条件属性的区分能力受制于决策属性。因此，在约简过程中，需要利用在决策属性区分集的基础上条件属性的区分集大小来衡量属性的重要性。

定义7在信息系统IS=〈U，C∪D〉中，对于给定属性集B⊆C，B在D上的条件区分集记为DIS（B|D），定义如下：

DIS（B|D）=DIS（B）∩DIS（D）

B在D上的条件区分能力记为E（B|D），定义如下：

E（B|D）=|DIS（B|D）|

定义8在信息系统IS=〈U，C∪D〉中，对给定属性集B⊆C，B是C相较于D的一个约简的充要条件为：

1）E（B|D）=E（C|D）；

2）B′⊂B，E（B′|D）

定理1若Q⊆P，则DIS（Q）⊆DIS（P），DIS（Q|D）⊆DIS（P|D），E（Q）≤E（C），E（Q|D）≤E（C|D）。

证明 由定义2 易得。

定理2令red为C的一个约简，对于给定的属性集red1，red2⊆red，如果red1⊂red2，则E（red1|D）

证明 因red1⊂red2，不妨设as∉red1∧as∈red2，由定理1 可知，E（red1|D）≤E（red1∪｛as｝|D）≤E（red2|D）。假设E（red1|D）=E（red2|D），则E（red1|D）=E（red1∪｛as｝|D），结合定义8 可得，as∉red，与条件as∈red2⊆red矛盾，故假设不成立，因此E（red1|D）

定理3在信息系统IS=〈U，A〉中，对于给定属性集P，Q⊆A，令U/P=｛Xi|i=1，2，…，p｝，Xi/Q=｛Xij|j=1，2，…，qi｝，则有：

证明 由定义2 和定义7 可知，E（Q）-E（P|Q）=|DIS(Q)-DIS(P)∩DIS(Q)|=|{(x，y)∈U×U|∃aq∈Q，ap∈P，f(x，aq)≠f(y，aq)∧f(x，ap)=f(y，ap)}|。因同一等价类间不可相互区分，不同等价类间可以互相区分，故对于Xi∈U/P，｛（x，y）∈Xi×Xi｝等价于｛（x，y）∈U×U|ap∈P，f（x，ap）=f（y，ap）｝，因此E（Q）-E（P|Q）=|{(x，y)∈Xi×Xi|∃aq∈Q，f(x，aq)≠f(y，aq)}|。对于Xi∈U/P，Q在Xi上的区分集为Xi/Q中不同等价类间的对象组成的可区分对的集合，因此Q在Xi上的区分集大小为不同等价类大小乘积之和，即，因此

2.2 基于条件区分能力的属性约简算法

传统基于区分矩阵的方法利用吸收率逐一对比区分矩阵中的元素，直到区分矩阵元素全为空集时终止，算法比较耗时。本文依据定理3，通过划分等价类计算属性的条件区分能力，以条件区分能力衡量属性重要性，从而实现约简，这样大大减少了实例间相互比较的次数，提高了约简效率。依据定理2，在约简中并不需要计算E（C|D），由于E（red|D）是随属性子集red严格递增，因此，当E（red|D）不再增加时，算法终止即可。

据此，本文构造了基于条件区分能力的约简算法。该算法描述如下。

在算法1 中，初始约简集red为空，每次选取条件区分能力最强的属性加入到red中，并逐步减小论域，直到red的条件区分能力不再增加时算法结束，从而得到约简。由于属性集的条件区分能力是依据定理3 通过划分等价类计算的，因此，算法1 的总计算复杂度为。

3 局部条件区分能力

目前，国内外学者们设计的属性约简算法，一般都是基于贪心策略进行属性选取的，每次选取最重要的属性加入到约简集red中，这就要计算每个属性在整个论域中的重要性，这种属性选取的要求太过严苛。实际上，就最终约简结果redend而言，并不是一定要严格按照属性重要性顺序加入到red中，而是满足在选取属性时，存在ai∈redend-red对任意aj∈C-redend，使得E（｛ai｝|D）≥E（｛aj｝|D）即可。退一步而言，即使上述条件不存在，也会得到C的另外一个约简。因此，本文在区分集DIS（D）上随机抽取k个可区分对组成局部区分集DISk（D），利用属性在DISk（D）上的条件区分能力进行属性选取。

定义9在信息系统IS=〈U，A〉中，A=C∪D，对于给定属性集P⊆A，P在IS上的局部区分集记为DISk（P），定义如下：

DISk（P）=rand（DIS（P），k）

其中：rand（*，k）表示从*中随机抽取k个元素；k为局部区分集大小。P的局部区分能力记为DISk（P），定义如下：

Ek(P)=|DISk(P)|

对于给定属性集B⊆C，B的局部条件区分能力记为Ek（B|D），定义如下：

Ek(B|D)=|DIS(B)∩DISk(D)|

定理4伯努利大数定理［22］。设μ是n次独立实验中事件A 发生的次数，且事件A 在每次实验中发生的概率为p，则对任意正数ε，有

定理4 表明，当n足够大时，事件A 出现的频率几乎接近于其发生的概率，即频率的稳定性。该定理为抽样调查中，用样本成数估计总体成数的理论依据。

定理5令p1=E（B|D）/E（D），p2=Ek（B|D）/Ek（D），则当k→∞时，p1=p2。

证明 由定理4 易得。

算法1 以条件区分能力衡量属性重要度，从而实现约简。然而当数据规模较大或条件属性较多时，对属性重要度的计算耗时太长。文献［19］中定义了相对区分度，利用相对区分度重新设计了属性重要性的衡量标准，也同样存在属性重要度计算耗时太长的问题。

本文依据定理5，通过构建局部区分集计算属性的局部条件区分能力，选择局部条件区分能力最强的属性加入到约简集中，将每个属性重要度的计算复杂度降低为O（k），有效地提高了约简效率。同时，当区分集（DIS（D）-DIS（red|D））的大小低于预设局部区分集大小k时，将区分集（DIS（D）-DIS（red|D））作为局部区分集计算属性的局部条件区分能力，从而保证了约简的正确性。依据定理2，当E（red|D）不再增加时，算法终止即可。

据此，本文构造了基于局部条件区分能力的约简算法。该算法描述如下。

由定义2 和定理3 可知，DIS（D）-DIS（red|D）可以通过划分等价类（U′/red）/D计算，计算复杂度为。在选取局部区分集时，每一次对可区分对的抽取需要先从U′/red中加权抽取一个等价类Xred，再从Xred/D中加权抽取两个等价类X1、X2，最后分别从X1、X2中随机抽取一个实例，组成一个可区分对加入到局部区分集中，所以步骤2）的总计算复杂度为。在选择属性过程中，由于属性重要度的计算依据是基于局部区分集计算的局部条件区分能力，所以步骤3）～4）的总计算复杂度为。步骤 5）计算复杂度为，低于步骤2）。综上，算法2的总计算复杂度为。若将局部区分集大小k视为常数，则算法2 的总计算复杂度为。不难发现，利用局部条件区分能力可以有效地降低属性选取的计算时间，提高约简效率。

事实上，对于一个确定的信息系统，每个属性的区分能力和条件区分能力都是固定不变的，而其局部条件区分能力可能会因选取属性的不稳定在约简过程中发生相对变化。上文中提到只要满足在选取属性时，存在ai∈redend-red对任意aj∈C-redend，使得E（｛ai｝|D）≥E（｛aj｝|D）即可，那么局部条件区分能力就不会发生相对变化；否则会得到C的另外一个约简。这种不稳定的关键在于局部区分集大小k的选取，因为k值决定了局部样本能否体现出属性间条件区分能力的真实大小关系。在固定k值条件下，属性间的条件区分能力相差越大，局部样本体现属性间条件区分能力的真实大小关系的效果越好，反之越差；对于同一个信息系统，k值越大，局部样本体现属性间条件区分能力的真实大小关系的效果越好，反之越差。不难发现，属性间条件区分能力的相对关系与信息系统的大小无关，即k与U无关。此外算法2 的约简过程中，只需要额外存储局部区分集即可，空间复杂度为O（|U|）。因此，算法2 更适用于海量数据属性约简。

4 实验与结果分析

为了验证本文算法的有效性和实用性，本文选取UCI 机器学习数据库（http：//www.ics.uci.edu）中的5 个数据集：Tictac-toe、Kr-vs-kp、Mushroom、Letter 和Connect 进行实验。采用基于区分度的高效前向属性约简算法（efficient Forward Attribute Reduction algorithm from Discernibility View，FARDV）［19］、基于k近邻属性重要度和相关系数的属性约简算法（attribute reduction algorithm based onk-Nearest Neighbor attribute importance and Correlation Coefficient，K2NCRS）［23］、基于正区域排序升序决策表的快速正区域约简算法（Fast Positive Region reduction Algorithm based on positive region sort ascending decision table，FPRA）［7］与本文算法1、2 进行对比实验。实验运行的硬件环境为Intel i7-8750H 2.20 GHz CPU和8 GB 内存。本实验使用Python3.6.6 实现，采用PyCharm 2020 作为实验平台进行实验。

表1 数据集描述Tab.1 Description of datasets

本文共设计4 个实验如下：

实验1 利用FAR-DV、算法1、算法2（k=1 000）分别对每个数据集进行属性约简，比较三种算法的约简结果和分类精度（使用支持向量机（Support Vector Machines，SVM）和分类回归树（Classification And Regression Tree，CART）两种分类器）。

实验2 采用递增序列k值，记录不同k值下算法2 约简结果的分类精度，与FAR-DV、算法1 约简结果的分类精度进行对比。

实验3 采用递增序列k值，对比FAR-DV、算法1 和不同k值下算法2 的属性选取顺序。

实验4 利用FAR-DV、K2NCRS、FPRA、算法1、算法2（k=1 000）分别对每个数据集进行属性约简，比较五种算法的约简时间。

实验1 的实验结果如表2～3 所示。从表2～3 可看出：在约简率上，三种算法完全一致；在约简结果的分类精度上，算法2 略优于算法1 和FAR-DV。这表明条件区分能力进行属性约简的正确性，同时也验证了利用局部条件区分能力进行属性约简的有效性。

表2 三种算法的约简结果Tab.2 Reduction results of three algorithms

表3 三种算法约简结果的分类精度Tab.3 Classification accuracies of reduction results of three algorithms

实验2 的实验结果如图1～2 所示。实验2 在SVM、CART两种分类器上比较了三种算法约简结果的分类精度。在图1～2 中，FAR-DV 与算法1 约简结果一致，故使用同一条折线表示。图1～2 的结果表明：当局部区分集大小k超过某个特定值时，算法2 约简结果的分类精度逐渐趋向于FAR-DV和算法1 约简结果的分类精度，即随着局部区分集大小k的增大，局部条件区分能力逐渐趋向于条件区分能力，与本文定理5 相符。

图1 SVM上三种算法的约简结果分类精度的比较Fig.1 Comparison of classification accuracy of reduction results of three algorithms on SVM

实验3 中，由于不同的数据集的数据规模、属性间区分能力不同，因此不同的数据集的约简结果趋于稳定所对应的临界k值不同。为了体现算法2 的约简结果及属性选择顺序随k值增加而变化的过程，对不同数据集采用了不同的k值区间和步长。其中数据集Mushroom 采用了k值区间［10，170］，步长为20；其他数据集采用了k=100，以及k值区间［500，4 000］，步长为500。实验3 的实验结果如表4～5 所示。对比表2 与表4～5 可得：随着局部区分集大小k的增大，算法2 的约简结果、约简率、属性选择的顺序都逐渐趋向于算法1。这进一步验证了利用局部条件区分能力进行属性约简的有效性。

表4 算法2在Tic-tac-toe、Letter和Mushroom数据集上的约简结果Tab.4 Reduction results of algorithm 2 on Tic-tac-toe，Letter and Mushroom datasets

表5 算法2在Kr-vs-kp和Connect数据集上的约简结果Tab.5 Reduction results of algorithm 2 on Kr-vs-kp and Connect datasets

实验4 的实验结果如表6 所示。从表6 可看出，在约简效率上，算法2 明显优于其他四种算法：当数据规模较大或条件属性较多时，FAR-DV、K2NCRS、FPRA 和算法1 在约简效率上有了明显的局限性，而算法2 依然能够快速地得到有效的约简；相较于其他四种算法，算法2 在Kr-vs-kp、Mushroom、Letter 上的约简效率平均提高了10 倍以上，在Connect 上的约简效率最低提高了约20 倍。本次实验验证了算法2 适用于海量数据属性约简。

表6 五种算法在不同数据集上的运行时间对比 单位：sTab.6 Comparison of running time of five algorithms on different datasets unit：s

图2 CART上三种算法的约简结果分类精度的比较Fig.2 Comparison of classification accuracy of reduction results of three algorithms on CART

5 结语

本文针对目前约简算法时空复杂度高、无法高效处理海量数据的问题，构造了条件区分能力进行属性约简，提出了基于条件区分能力的属性约简算法，并利用大数定律将条件区分能力扩展为局部条件区分能力，有效地减少了属性重要性的计算时间，提出了基于局部条件区分能力的属性约简算法，将计算复杂度降为。利用局部条件区分能力进行属性选择，可以极大限度地降低约简过程中计算时间和空间上的耗费，非常适用于海量数据的属性约简。但在属性约简过程中，局部条件区分能力的不稳定问题还需要进一步研究。