属性约简

粗糙集的几种属性约简算法分析

分类:默认栏目

2006.6.16 10:32 作者：万富 | 评论：0 | 阅读：1628

陈淑 珍，基于粗集的几种属性约简算法分析，武 汉 工业学院学报，Vol.2 4No.3，Sep .20 05 1.1 利用差别矩阵求最小约简

差别 矩 阵 (Discernibility Matrix)是由波兰华沙大学的著名数学家Skowron[21 提出来的，利用这个工具，可以将存在于复杂的信息系统中的全部不可区分关系表达出来。利用 差 别 矩阵求取最小约简的一个前提是:在数据表的预处理阶段要先对不相容的记录进行处理，即差别矩阵不处理不相容记录。预处理的方法如将冲突的记录数除以记录总数，得到一个粗糙度的量度，该量度可以作为数据表的一个特征。

通过 差 别 矩阵可以很方便地求取核属性，以核属性为出发点，再求取差别函数的最小析取范式，则求析取范式的运算就可以得到很大的简化。而最后得到的每个析取分量对应着一个约简。因此，一定可以得到最小约简。

但该 算 法 的缺陷十分明显:首先，当论域的对象与属性的规模较大时，差别矩阵将占有大量的存储空间口(n的二次方);其次，差别函数的化简本身就是一个NP一hard问题，因此只要数据集稍大一点，就不具备可操作性。 1.2 基于属性依赖度约简算法

求取 所 有 约简是一个NP一hard问题，因此运用启发信息来简化计算以找出最优或次优约简显然是一种可取的方法。

许多 启 发 式约简算法的基本步骤都是:由信息系统或决策表的核为起始点，然后根据属性重要性的某种测度，依次选择最重要的属性加人核中，直到满足终止条件。便得到信息系统或决策表的一个约简(更确切的说，是包含约简的一个属性集)。 一个 信 息 系统中的所有属性对于决策来说并不是同等重要的，在粗集理论中，属性重要性可通过相依度来体现。

决策 属 性 D对于属性R(R属于C)的相依度y(R,D)定义为[3]:显然 有 ，O <,y(R,D), l,y(R,D)给出了决策D对属性R之间相依性的一种测度。它反映了属性R对于决策D的重要程度。在已知条件R的前提下，一个属性R对于决策D的重要度SGF(a,R,D)可以定义为如下的差值:SGF = (a ,R,D)=y(R+{a},D)一y(R,D),SG F= ( a,R,D)反映了把属性a加到R后，R 与D之间相依度的增长程度。事实上，属性对于R与之间相依性的影响越强，则SGF= (a,R,D)的值就越大。 1.3 基于条件信息嫡约简算法

基于 属 性 依赖度的启发式约简方法在实际应用中遇到的一个重大困难是属性间不确定关系的表达。粗糙集约简表达的是属性间的确定性关系，正区域之外等价类族表达的属性间关系并不被粗糙集认可，因此除要求属性满足确定性关系外，挑选有强烈概率因果关系的属性集具有十分意义。

为了 描 述 概率因果关系，人们在处理这类数据时，在约简算法中引人信息嫡来度量属性重要度。 事实 上 基 于信息嫡与基于属性依赖度的启发式算法也是不完备的。

应 当指 出 的是以上所分析的两种算法都只是搜索次优解的算法，采用属性重要性方法的约简算法并不能保证一定能够找到信息系统的最优解。出现这种情况的原因在于属性的“组合爆炸”。在信息系统中各个属性并不是孤立存在的，而是存在着互相之间的联系和影响。某些属性虽然它们的单个重要性都很小，但是当这些属性组合在一起时，却能对整个信息系统的正确分类产生很大的作用，而这一点有时仅仅凭借单个属性的重要性评价方法是很难发现的，因为那些重要性很小的属性很难被约简算法所选择。尽管采用每次属性扩张后都动态调整各属性重要性的办法能够在一定程度上克服这一问题，但还是无法从根本上解决问题。

利 用 启 发式算法的确能够提高约简的求解速度，而且在解空间不复杂的情况下有可能得到最优解或次优解，但在解空间较复杂或属性间关系较为复杂的情况下，用这些方法找到的解极有可能陷人局部最优解，这种算法并非对所有的知识表达系统都适用。 1.4 基于遗传算法的属性约简

遗传 遗 传 算法是一种自适应随机搜索方法，其搜索方式不是由单一的方向或结构，它将多个个体作为可能的解并考虑搜索空间全局范围内的抽样，从而导致以更大的可能性收敛到全局最优解，因此，人们把遗传算法引人粗集属性约简。

算法 通 过 用计算机模拟生物进化过程，使群体不断优化，并在变化过程中找出最优解。在遗传算法中，适应度函数的设计是整个GA算法的核心步骤，由于几个遗传算子都依赖于染色体的适应度值，因此适应度函数的设计目标，在很大程度上决定着迭代收敛的方向。 而粗 糙 集 的属性约简主要是为了求得最小的约简属性集。这样，在保证属性集满足一定精度的情况下，使其属性个数最小，即最终所

需的结果是满足分类要求的最简属性集合。所以适应函数设计的最终目的应包含了以下两个目标函数:①必须满足分类质量，通常要求必须是约简。②这个约简所包含的属性个数要尽量少。

文献 〔 7〕 所规定的适应度函数为m 一 L Cscore( r) =se一一-r+子入

其中，。为染色体的长度，Lr为染色体中1的个数，Cr为染色体所代表的属性约简与差别矩阵中的元素进行合取之后不为0的元素个数(若为某一项为0，表示该属性集不能区分该项所对应的两个对),K=nx ( n一1)/2 ，即差别矩阵的子项数。

该适 应 度 函数体现了染色体追求两个目标的趋向，用染色体覆盖差别矩阵中元素的个数作为该染体相对于决策属性的分类能力的大小，再通过约简中包含属性的个数来控制染色体的长度。

但完 成 c r运算的代价太高，要遍历整个差别矩阵，因此时间复杂度为0(mxn2)，同时该算法要求保留差别矩阵，故空间开销为O(n2)。 文献 【 8] 所规定的适应度函数:m 一 Lsco re ( r ) =一一一r+kPopsizex m x n x lo gen) 。 在迭代次数Gen和种群大小Popsize已定的前提下，算法的运算时间是和论域大小n成近似线性的倍数增长，而不是平方数增长。

我们 选 择 了UCI数据库中的部分测试数据，采用二进制编码方式得到了如表3的结果(这里迭代次数Gen=50，Popsize二30，交叉率p。为0. 7，变异率pm为。.05)。通过对算法复杂度的分析和实验结果，可以证实随着论域个数的增大，运算时间是呈近似线性倍数增长。

但是 由 于 遗传算法是一种自适应的随机搜索算法，其性能分析一直是该领域的研究重点。相对于其鲜明的生物基础，其数学基础还不够完善，如缺乏完整的遗传算法收敛性理论，Holand的模式定理尚不能清楚地解释遗传算法的早熟现象和欺骗问题，遗传算法的搜索效率及其时间复杂性等。因此基于遗传算法的粗糙集属性约简算法还有待于遗传算法自身理论的不断完善。 其中 ， R 为染色体所对应的属性集，D为决策属，k=袱R,D)即属性集R的依赖度。

该 函数 将 属性依赖度引人适应度函数，而属性依赖度表明决策属性对染色体所对应属性集的依赖性，反映着属性的分类能力。同时，该函数通过了Lr来控制染色体的长度，同样体现着两大准则。

我们 知 道 ，利用堆排序后的数据，可以使等价类运算的时间复杂度由。(mxn2)降为。(m x n x1092n) ，故求y(R,D)的时间复杂度就为0(mxnx1092n) 。 因此，相对于上面的方法，从计算时间上看，该算法有一定的优势，可行性更高。

设迭 代 次 数为Gen，种群大小为Popsize，信息系统S=(U,A)，则我们看遗传算子的运算时间，三个遗传算子都是基于概率思想的运算。在染色体适应度值已求出来的情况下，它们的运算时间只和种群的大小Popsize,E( 及染色体的基因位数IAI= m相关，在最坏的情况下为。(Posize x m十。，)，因此，这个算法效率的关键是适应度函数的求取。

而初 始 适 应度函数的关键就是求取条件属性相对于决策属性的依赖度，其时间复杂度为0(mxnxlo gen) ，其中IAI = m,IUI= no所 以 ，整 个GA算法的时间复杂度为0( Genx2 结论属性 约 简 的目标就是求得最优约简，但找出一

个信息系统的最小约简是NP一hard问题。对启发式算法的改进只是对属性重要度的评定准则的修改，并不能改变贪心算法易落人局部最优的趋向;而基于遗传算法的属性约简虽然做到了并行搜索，同时缩小了搜索空间，但其收敛方向的控制还是个棘手的问题，同时，该算法也并不能保证搜索方向不落人局部最优。因此寻求快速的约简算法仍然是今后 的主要研究目标。