几种属性约简算法的比较与分析.PDF

计算机科学2005Vo1.32%.8A 几种属性约简算法的比较与分析” ComparisonandAnalysisofSeveralAlgorithmsofAttributeReduction 张东星 苗夺谦 杜伟林 李道国 (同济大学计算机科学与工程系 上海200092) AbstractAttributeReductionplaysanimportantroleinRoughsetstheory,whichdescribesessenceofknowledge indecisiontables.Theperformanceaboutdifferentalgorithmswhichappliedtothesamedatasetisverydifferent. Inthispaper,Theperformanceofseveralexistingalgorithmsisdiscussed,comparedandanalysed.Thescaleofdata setwhicheachalgorithmadaptstoisaddressed. KeywordsAttributereduction,Mutualinformation,Discernibilitymatrix,Roughsets 们先来分析一下现有的求核的算法，一种是基于正 1 引言 域的方法，另外是基于差别矩阵的方法 粗糙集理论[13(RoughSets)是Z.Pawlak于20 算法2.1基于正域的方法1[13 世纪80年代提出的，它是一种处理模糊的和不确定 输人:决策表T=(U,CUD)，其中C,D分别 知识的数学工具，其主要思想是在保持分类能力不 为条件属性集和决策属性集。 变的前提下，通过知识约简，导出决策和分类规则。 输出:核Core(CD), 到现在为止，粗糙集理论已成功地应用于数据挖掘， 步骤: 机器学习，决策分析等众多领域之中。 ①令R=0，计算PO凡(D); 属性约简是粗糙集理论的核心内容之一，它刻 ②对每一个aEC，计算PO昆一e)《(D)，如果 画了决策表中知识的本质部分，通常情况下，近似空 POSe(D)=e-POSG{,}(D)，则R=RU(a); 间中的属性并不是同等重要的，甚至某些属性是冗 ③令Core(C,D)=R即为所求。 算法2.2基于差别矩阵的方法C[al 余的，当近似空间中的数据是随机采集的时候，其冗 输人:决策表T=(U,CUD)，其中C,D分别为 余属性更为普遍。冗余属性的存在，一方面是对资 条件属性集和决策属性集。 源的浪费(需要大量的存储空间);另一方面，也会干 输出:核Core(C,D), 扰人们做出正确而简洁的决策。因此有必要对属性 步骤: 进行约简。 ①先求差别矩阵MuXa(其中n表示决策表T 属性之间的依赖程度决定了属性是否可以进行 中的对象的个数)，其中: 约简，根据属性依赖度定义的属性重要度往往是属 M(i,j)， 性约简的重要启发式信息。综观