基于rough+set的属性约简算法的研究

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

1、摘要科技的飞速发展，需要处理的信息量迅速增加，迫切需要一种能从大量科学数据中发现有价值知识的有效方法。知识发现是研究如何从大量的、模糊的、随机的数据中，提取隐含在其中的信息。RoughSet是由波兰学者Plawlak.Z在1982年提出的应用于不确定知识领域数据挖掘的一个数学工具。基于RoughSet的属性约简是知识发现的重要内容，也是一个NP-hard问题。总结了基于RoughSet的一些属性约简算法，并且详细分析了算法的时间复杂度和空间复杂度。在此基础之上，分析了其中最常用的面向支持度的属性约简算法MSA(MaximumSupp

2、ortAlgorithm)。它的局限性在于选择了偏好特征。选择了重要规则集中具有最高支持度的特征而不是所有潜在规则中具有最高质量的特征。换句话说，它仅考虑了潜在规则的局部最佳而没有考虑全局最佳。训练集可能属于许多分类。MSA偏好于某一个分类。它将产生一些系列带有偏差分布式支持度的规则。更进一步，MSA算法有时对两个具有相同大小的正域和多数重要规则的支持度丧失判断能力。基于上述讨论，提出了一种基于Rough　Set的启发式算法IMSA(ImprovedMaximumSupportAlgorithm)来克服上述缺点，且重新定义了启发函数。

3、最后，开发了一个简易的属性约简的实验系统RSS，在属性约简算法方面，实现了MSA算法和本文提出的算法；在单个功能方面，实现了分类和近似集等重要概念的求取。利用本系统进行实验分析，得出本文提出的算法在性能方面有了较大提高。　关键词：RoughSet理论;属性约简;启发函数;区分矩阵IAbstractWiththedevelopmentofscienceandtechnology,theinformationthatneedtoprocessisincreasingrapidly.Itisimportanttofindausefulmet

4、hodtoobtainvaluableinformationfromagreatdealofdata.KnowledgeDiscoveryistheprocessthroughwhichwecanextracthiddenbutusefulknowledgefromhalf-backedandrandomdata.RoughSetisanewmathematicaltooltodealwithuncertainandfuzzyknowledge.PolandscholarnamedPawlak.Zfirstlyproposedthet

5、heoryofroughsetin1982.TheattributereductionbasedonRoughSetistheimportantcontentinKnowledgeDiscovery.ItisalsoaNP-hardquestion.SomeusefulattributereductionalgorithmsbasedonRoughSethavebeensummarized.Thetimecomplexityandspacecomplexityofthesealgorithmshavebeenanalyseddetai

6、ledly.ThesupportorientedalgorithmthatproposedbyZhongiscalledMaximumSupportAlgorithm(MSA).Thelimitationofthisalgorithmisthatitselectsthepreferablefeaturesthatcausethehighestsupportofthemostsignificantrulesratherthanthehighestoverallqualityofthepotentialrules.Inotherwords

7、,itonlyconsidersalocaloptimuminsteadofaglobaloptimumofthepotentialrules.Moreover,sometimesthisalgorithmfailstomakeachoicebetweentwosetsoffeatureswhentheyhavethesamesizeofpositiveregionandsupportofthemostsignificantrule.ThispaperproposedanewalgorithmcalledIMSA(ImprovedMa

8、ximumSupportAlgorithm.toresolvetheseshortcomings.WehavedefinedanewheuristicfunctioncalledWeightSupportHeuristi