基于粗糙集理论的属性约简算法研究

《基于粗糙集理论的属性约简算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要属性约简是数据挖掘预处理中非常重要的一步，它通过减少信息的维数提高数据挖掘算法的效率。粗糙集理论是一种刻画不确定性和不完整性知识的数学工具。属性约简是粗糙集理论应用中的基本问题。　Wong.S.K.M和Ziarko.W已经证明找出一个信息系统决策表的最小约简是NP-hard问题。在人工智能中，解决这类问题的一般方法是采用启发式搜索。以属性重要性作为启发式信息，减小搜索空间。基于属性重要性的约简算法如MIBARK算法，在度量属性重要性时，要多次将不同的条件属性进行组合，计算其与决策属性之间的互信息，需要的计算量很大。　基于提高约简效率的

2、考虑，以属性频率作为选择属性的启发信息，用过滤差别矩阵得到属性频率，论文基于MIBARK提出了改进算法。实验表明，在获得相同属性约简的前提下，改进算法中属性的频率信息与差别矩阵可以同时生成，避免了计算各属性组合与决策属性之间的互信息，从而减少了计算量并提高计算速度。　在不同的系统中和不同的环境下，用户对属性约简的实际要求和兴趣是不一样的，目前的属性约简算法普遍没有考虑用户的决策需求。为了满足用户的实际需要，提出了一种面向用户的属性近似约简算法。该算法利用条件熵度量属性的重要性，不计算条件属性的核，直接在条件属性的基础上约简。　实例分析表明，

3、该算法的计算量较少，用户还可以根据实际决策需求更改阈值，得到满足不同精度要求的约简结果。　　　　关键词：粗糙集，属性约简，属性重要性，频率，差别矩阵，熵　　　　3AbstractAttributereductionisoneofimportantstepinpreprocessingofdatamining,itimprovestheefficiencyofthedataminingalgorithmbyreducingthedimensionsoftheinformation.Roughsettheoryisamathematicalto

4、olusedfordealingwithvaguenessanduncertainty.Attributereductionisalsooneofthebasictopicsintheroughsettheoryfield.IthasbeenprovedbyWong.S.K.MandZiarkothatcomputingtheminimalreductionofdecisiontableisaNP-hardproblem.Inartificialintelligence,approachingtotheseproblemsisheurist

5、icsearching.Thesignificanceofattributeisusedastheheuristicinformationtoreducesearchingspace.MIBARKisanattributereductionalgorithmbasedonsignificanceofattribute.Definingthesignificanceofattributes,itrequiresverybigcalculatingquantity.Becauseitisnecessarytocalculatemutualinf

6、ormationsbetweenthecombinationsofdifferentconditionattributesandthedecisionattributesformanytimes.Inordertoimprovetheefficiencyofthealgorithm,usingfrequencyastheheuristicinformationofattributesselection,gettingfrequencyofattributesfromthefiltereddiscernibilitymatrix,animpr

7、ovedalgorithmbasedonMIBARKisproposedinthispaper.Theexperimentshowsthatthisalgorithm,obtainingthesamereductionasMIBARKalgorithm,cangetfrequencyinformationofattributesanddiscernibilitymatrixatthesametime,andneednotcalculatemutualinformations.Soitrequireslesscomputationaleffo

8、rt,andthespeedofcomputingisimproved.Inthedifferentsystemsandenvironments,theuser’sactuald