属性约简算法carrdg的改进及其实现技术研究

《属性约简算法carrdg的改进及其实现技术研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、厦门大学硕士学位论文属性约简算法CARRDG的改进及其实现技术研究姓名：陈可赢申请学位级别：硕士专业：软件工程指导教师：曾文华20081101摘要摘要从海量数据中获取信息是具有挑战和现实意义的课题，其中的关键技术之一在于如何消除数据中的冗余信息。属性约简为解决该问题提供了有效途径，其目的是在保持已有数据信息分类能力不变的前提下，消除冗余属性，使高维数据降为低维数据，从而降低信息处理的难度与复杂性。因此，属性约简在数据挖掘、机器学习、知识发现、决策支持等领域具有重要意义。本文是在对属性约简算法CA

2、RRDG的理论研究基础上，对属性约简算法CARRDG的实现与验证技术进行进一步研究。本文不仅完全实现了属性约简算法CARRDG，而且用六种典型的UCI机器学习数据验证了算法CARRDG的正确性与高效性。本文针对属性约简算法CARRDG在实现技术层面上的可改进之处，在原有的三种约简分辨图深度优先搜索原则(成员独占原则、友人劝阻原则、陌生人吸纳原则)的基础上，增加了新的深度优先搜索原则——阻挡层阻挡原则。由于采用了恰当的数据结构与实现技术，阻挡层阻挡原则不会增加算法实现的复杂性，也几乎不会增加程序的

3、运行时问。相反，实验结果表明，阻挡层阻挡原则对于某些大型信息系统的约简分辨图的剪枝效率甚至超过了成员独占原则与友人劝阻原则。本文首先介绍了属性约简算法CARRDG及其改进方法，然后以总体设计、主要数据结构设计与实现、约简分辨图的创建与实现、核属性集的计算与显示、启发式深度优先搜索原则的实现为主线，详细阐述了改进型属性约简算法CARRDG实现的思想、技术与过程，最后介绍了实验结果分析。本文所实现的属性约简算法CARRDG的程序具有通用性与实用性。对于大多数现实中的信息系统，只要符合基本格式要求，程

4、序都能快速地计算出其所有属性约简。属性约简算法CARRDG本质上解决的是数学领域中析取范式与合取范式的相互转换问题。因此，本文实现属性约简算法CARRDG的程序也可以解决这类数学问题，从而具有广阔的应用领域。关键词：属性约简；约简分辨图；数据挖掘AbstractInformationacquisition，especiallyforlargescaleofdata，hasbecomeachallengingandmeaningfulsubject．Oneoftherelativekeytechn

5、ologiesistoeliminateredundantinformationinthedata．Fortunately，attributereductprovidesaneffectivewaytoreachthetargetwhilekeepingtheinherentclassificationcapabilityofthedataunchanged．Inthisway，highdimensionaldatamaybecomelowdimensionaldataSOthatthediff

6、icultyandcomplexityofinformationprocessingarereduced．ThisdissertationcanbeviewedasanexhibitionoffruitsabouttheimplementingandverifyingtechnologiesfortheattributereductalgorithmCARRDG，whosetheoreticalstudyhasbeendeveloped．Themaincontributionofthisdiss

7、ertationisnotonlytoimplementthealgorithmCARRDG，butalsotoverifyitscorrectnessandeffectivenessbyusingsixtypicaldataformachinelearning．Furthermore，inadditiontotheexistedthreeheuristicdeep—firstsearchingprinciple(MemberExecutivePrincipleMEP，FriendPersuad

8、ePrincipleFPP，StrangerEnterPrincipleSEP)basedonreductdiscernibilitygraph。anewheuristicsearchingprinciple—————BlockingLayerBlockPrinciple(BLBP)——hasbeenproposedtoimprovetheefficiencyofthealgorithmCARRDG．Sincethereasonabledatastructureshavebeendevelope