基于抽样的随机约简算法

张照星　刘威　张鹏　范英　康凯　刘阳明　施一琳　徐骁

摘要：属性约简作为粗糙集理论的一个重要应用被较多学者关注。然而，由于其计算复杂度与数据的规模成平方级增长，基于粗糙集的属性约简在大规模数据上的应用效率较低。考虑到随机抽样是降低大规模数据的计算的一种有效的统计方法，因而我们将其引入约简算法中，提出一种随机约简算法，从而大幅提升了属性约简的效率。该算法的主要贡献是基于最小冗余和最大相关的选择属性过程中引入了随机抽样的思想。首先，在每次选择最重要属性时，并不需要在所有的示例上计算依赖度，而是随机选了部分示例，从而既选择了最大相关的属性，又大大降低了算法的计算复杂度。其次，在选择属性的过程中，每次迭代的样本是不同的，而且样本之间具有较少的信息交叉，从而选取了最小冗余的属性。最后，通过数值实验，我们比较了随机约简算法与非随机约简算法的性能。

关键词：随机抽样；模糊粗糙集；属性约简

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2017）33-0013-03

数据的爆炸性增长，带来了数据挖掘技术的飞快进步。而在实际问题中，数据缺失，数据收集不精确，数据粒度过于粗糙等都会导致不确定数据的产生。不确定数据挖掘成为一个热门的研究方向。波兰科学家Z.Pawlak提出的粗糙集理论，其不需要太多的专业知识也能很容易地被人理解，是集合理论的一般化扩展[1-2]。

文献[9]主要利用增量学习的方式提高执行速度。在[9]中，提出了基于粗糙集理论的增强式学习方法，将数据集分为几块，依次把数据块加入运算，从而原始的大规模数据的运算量可以有效地降低。基于此增量的思想，约简在每次数据块加入的过程中被更新。这种基于已获得约简结果学习新的数据集的约简方法，即避免的重复运算，又使得大规模数据集上的约简成为可能。不同与增量学习算法，有不少学者研究了按照分布式的思路来解决大规模数据集中的粗糙集问题。但是，从统计学的角度出发，随机抽样可以在基于粗糙集理论的大规模数据应用中发挥作用。

本文将模糊粗糙集和随机抽样的基本方法结合，提出了基于抽样的随机约简算法，来解决大规模数据的属性約简问题。本文的主要安排如下。第一节我们回顾了模糊粗糙集及其约简；第二节构造了基于随机抽样的随机粗糙模型，并理论分析了样本与总体的依赖度统计意义上的差别与联系，并据此提出了随机约简的定义。第三节基于最大相关和最小冗余的思想设计了随机约简的算法。第四节我们给出算法的数值实验评估。最后在第五节总结了全文。

1 模糊粗糙集及其约简

在本节中，我们简单回顾一些模糊粗糙集和其经典的约简算法。关于该理论的更多细节，可以参考文献[3-7]。

1.1 模糊粗糙集

数据集可以描述成一个决策表，表示成一个三元组[DT=]。这里U是一个非空示例集[{x1，x2，…，xn}]。每个示例用一组条件属性[{a1，a2，…，am}]来描述，记为A，另外有一组决策属性，记为D。决策属性将论域划分为m个决策类[UD]=[{D1，D2，…，Dq}]，这里[U=i=1qDi]，且任意两个决策类[Di]与[Dj]相交为空。特别地，如果[x∈Di]，则记[Di=Dx]。即[Dx]表示[x]属于该决策类。

假设B是A的一个子集。两个示例的相似度和距离定义如下。

定义1.1：给定决策表[DT=]，[?B?A]和[xi，xj∈U]，[xi]和[xj]的相似度记为[rB（xi ，xj）]，[xi]和[xj]的距离记为[dBxi，xj]。它们的定义如下：

[dBxi，xj=maxkak（xi）-ak（xj），ak∈B]；

[rB（xi，xj）=1-dB（xi，xj）]。

[rB（?，?）]即为属性子集B所描述的模糊相似关系，它满足自反性、对称性和三角传递性。

如果A是可以模糊化的（如连续值属性），那么决策表DT=表示的是一个模糊决策表。在模糊决策表上，粗糙集被推广为模糊粗糙集。模糊粗糙集是融合了粗糙集和模糊集的概念而提出的理论。模糊粗糙集不仅将近似对象从离散集扩展到了模糊集，而且将等价关系扩展到了模糊相似关系。模糊粗糙集重新定义了上下近似概念，如下。

定义1.2：给定模糊决策表DT=和[?B?A]，示例[x∈U]属于[Dk]类的上、下近似定义如下：

[BDkx=infu∈Umax1-rBx，u，Dku，x∈U]

[BDkx=supu∈UminrBx，u，Dku，x∈U]

上述定义是一般化的模糊糙集的定义在特定的模糊相似关系[rB（?，?）]下的具体的形式，它的几何意义为示例的下近似是距离其最近的异类点的距离，上近似是距离其最远的同类点的相似度。为了便于理解，本文的接下来的工作均是基于定义2的模糊粗糙集展开。采用类似的方法，本文的工作可以推广至一般化的模糊粗糙集。

传统粗糙集理论中，正域是下近似的并。在模糊粗糙集中，模糊正域的定义如下。

定义1.3：给定模糊决策表DT=和[?B?A]，示例[x∈U]的模糊正域定义如下

[POSUBx=sup0

继而，决策属性D对条件属性子集[B?A]的依赖度可以定义如下。

定义1.4：给定模糊决策表DT=和[?B?A]，决策属性D对于属性子集B的依赖度定义如下：

[γUB=x∈UPOSUB（x）|U|]

该定义可以度量属性子集[B?A]在整个决策表中的重要性程度，有如下性质。

性质1.1：[γUB≤γUA]；[limB→AγUB=γUA].

1.2 基于依赖度的属性约简算法

约简的核心思想是找到一个最小的属性子集，该属性子集可以区分所有的具有不同决策类的示例对。即约简拥有和全集相同的辨识信息。约简的定义如下，更多的细节，可以参考[6-8]。

定义1.5：给定模糊决策表DT=和[?B?A]，当B满足以下条件时，

（1） [?a∈B，γU（B-a）<γUB]；

（2）[γUB=γUA；]

此时，我们称B是模糊决策表的一个约简。

基于依赖度经典的非增量属性约简算法，简写为CAR，已被提出得到广泛的应用[1，2]。

[算法1：经典约简算法（CAR） 输入：[DT=] 输出：redu 1： LET[lef=A；B=?； γUB=0]； 2： 计算[γUA] 3： WHILE[γUB<γUA]，DO 4：[a={a∈lef|γUB∪a=maxγUB∪ai，ai∈lef}；] 5：[B=B∪a；]

6： [lef=lef-a] 7： ENDWHILE 8： LET[redu=B， i=0] 9： WHILE[ i

在该算法中，第一个while循环中每次迭代找到一个具有最大依赖度增量的属性，在第二个while循环中删除其中的冗余属性。不管是一个while循环，还是第二个while循环。每次迭代均需在整个数据集的所有的示例上计算依赖度，该计算的复杂度为[O（n2）]。因此，当数据规模巨大时，该经典的约简算法效率低下甚至不可行。

2 随机粗糙集

经典的模糊粗糙集的下近似的几何意义为：对于[? x∈U]，其下近似值是到异类点的最小距离。而这意味着计算任意示例的下近似值的计算需要遍历整个数据集的所有示例。当数据规模变得巨大时，计算开销巨大。因此本文拚弃遍历所有的示例的做法，而是随机抽取一定的示例，构成样本集，计算样本集上的随机近似值。并讨论其性質，分析随机近似算子与经典算子之间的关系。

定义 2.1：给定一个决策表[DT=]，从[U]中随机抽取[n]个示例构成一个样本S， 则[?B?A]，[?x∈S]，x属于[Di]的随机下、上近似的定义如下：

[RBDix=infu∈Smax1-rBx，u，Diu]；

[RBDix=supu∈Smin {rBx，u，Di（u）}].

备注：为保持类标的分布不变，在本文随机抽样一般采用比例分层抽样法。即样本S上的类标比例与总体[U]上的类标比例一致。

随机约简可以定义为如下形式：

定义 2.2：给定决策表[DT=]，在论域中随机抽样得到若干样本[S={S1，S2，…，Sn}]；已知属性子集[B?A]，若B满足下述条件，那么，称B为一个随机约简（其中[α∈[0，1]]）。

（1） [?Si∈S，γSiA-γSiB<α]；

（2） [?Bi∈B，?Si∈S，γSiA-γSiB-Bi<α]

定义2.2定义了一个使得辨识信息在多个样本上依赖度几乎不变的最小条件属性子集。

3 随机约简算法

在经典算法中，每次迭代中添加属性需要在U上做全量的计算，找到某一个属性使得依赖度增加最大。如果U规模很大，那么在每次迭代的时间代价很大，针对这一问题，基于以上提出的随机粗糙约简的定义，我们提出一个随机约简算法（RAR）。

在RAR中，从论域中按照分层比例抽样的方式抽取了足够大的样本集，在这个样本集上前向搜索。找到使得依赖度增加最大的那个属性，添加到约简中；最终在N次抽样后，基于约简的随机依赖度和基于全部属性的随机依赖度相差不大时，我们认为找到了一个随机约简。具体过程如下算法 2。

[算法2：随机约简算法（RAR） 输入：[DT=]， [N]（终止轮次），[ k]（样本数），

[f1]（样本合格阈值），[f2]（结果合格阈值） 输出：redu 1：LET[lef=A；redu=?；repeat=0；γp=0]； 2：WHILE [repeatγp and |γc-γpγc|

9：End IF 10：ELSE 11：[redu=redu∪a；] 12：[lef=lef-a；] 13：[γp=γc；]

14：[repeat=0]；

15：ENDIF 16：ENDWHILE 17：RETURNredu； ]

算法2（RAR）的设计基于最大相关和最小冗余的思想。最大相关通过寻找在每次迭代中依赖度增量最大的属性实现。最小冗余通过选择信息交叉最小的样本来实现。

RAR算法区别于CAR的不同之处在于，其两者有着不同的终止条件，并且在每次迭代的过程中，只是在抽样所得的样本上进行计算，这就大大减少了每次迭代的计算；在CAR中，计算[γUB]的时间复杂度为[O（U2）]。在每迭代中，都需要遍历全部的候选属性集lef=A。因此，在每次迭代中找到一个候选属性的时间复杂[O（|A|U2]）。而在RAR中，计算[γSB]的时间复杂度为[O（S2]），因而，在RAR中，每次迭代找到一个候选属性的时间复杂度为[O（AS2）]。