粗糙集并行约简算法研究.pdf

《粗糙集并行约简算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、RESEARCHoNALGOR玎删S0FnU池LELREDUCTSThesisSubmittedtoZhejiangNormalUniversityinpartialfulfillmentoftherequirementforthedegreeofMasterofEngineeringbyDianxunYhn(ComputerSoftwareandTheory)ThesisSupervisor：DayongDengApril，2012粗糙集并行约简算法研究摘要粗糙集理论利用上近似集和下近似集的概念解决了经典逻辑理论中模糊概念的可计算性问题，因此它

2、在处理不完全、不精确数据时有其独到的优势：1)粗糙集理论不需要先验知识；2)相对其它不确定性理论更加客观、精确；3)同其它不确定性理论有很强的互补性。正是因为这些优点，从提出之日起近三十年来，粗糙集理论得到了充分的研究和广泛的应用。经过多年的发展，粗糙集理论的有效性得到了充分的验证，理论框架也日趋完备，但如何在一个动态变化的数据集中求得一个稳定的约简这一难题一直未能得到很好的解决。虽然动态约简理论的出现为解决这个难题指明了一个很好的方向，但是由于其时间复杂度是指数级的，动态约简算法只能在那些条件属性较少的数据上求约简，而且由于动态约简算法本身不完

3、备，得到的约简结果有可能为空，这大大限制了它的应用范围。为了解决如何在较小的时间复杂度之内找到尽可能稳定的约简这一难题，邓大勇提出了并行约简理论。并行约简算法和动态约简算法类似，都是将一个决策系统拓展成若干个子决策表，然后再将子表的约简结果进行整合，最终得到一个尽可能稳定的约简。和动态约简穷举式搜索子决策表的全部约简然后进行结果整合不同的是，并行约简可以利用启发式信息作为判断属性优劣的标准，在计算过程中就能够判断出条件属性的好坏，因而不需要计算子表的全部约简，所以并行约简算法的时间复杂度是多项式级的。而且并行约简是一个完备的理论，它在定义层面就已

4、经避免了约简结果为空这种情况的出现。除此之外，并行约简相比动态约简还有一个优点就是它可以利用粗糙集理论所有己取得的成果。本文对并行约简理论进行了深入研究，提出了～种改进的并行约简算法，新算法的时间复杂度不变但得到的约简结果长度更小。然后我们将并行约简由代数意义拓展到信息论意义下，提出了信息论意义下的并行约简概念及其相应算法，并探讨了它的相关性质。最后我们探讨了并行约简和动态约简之间的一致性和差异性，将它们进行了统一。具体而言，本文做了如下工作：(1)第l章对粗糙集理论进行了简单的综述；第2章引入了粗糙集理论的一些基本概念和知识，比较分析了三种比较

5、简单常用且与并行约简算法相关的决策表属性约简算法。(2)第3章深入研究了邓大勇提出的并行约简概念及其相应算法。因为基本概念和算法框架都是以代数论知识为基础构建起来的，所以第3章中介绍的并行约简又叫代数意义下的并行约简。(3)第4章提出了一种改进的代数并行约简算法，优化了原算法的属性挑选策略，改进后的算法时间复杂度不变但求得的约简结果更加精简、稳定。虽然在理论上改进后的算法和改进前算法具有相同的时间复杂度，但由于约简结果更加精简、算法迭代次数更少，实际实验时改进后的算法的时间开销比改进前的算法小了不少。(4)第5章将并行约简理论由代数论拓展到了信息

6、论，用信息论中的概念和知识定义了信息论意义下的并行约简概念。信息论意义下的并行约简算法沿用了代数论意义下的并行约简算法的算法框架，只是属性重要度的衡量方式和算法的截止条件做了变化，因此该算法的时间复杂度和代数意义下的并行约简相同。信息论意义下的并行约简主要意义在于处理不一致数据集时可以保留更多的分类信息。最后我们从理论上探讨了信息论并行约简和代数并行约简的一致性和差异性，将二者同动态约简做了有机统一。关键词：粗糙集；决策表；约简；并行约简；代数；信息论IIRESEARCHONALGORITHMSOFPARAI，LELREDUCTSINROUGHS

7、ETSABSTRACTBydefiningtheconceptsofupperapproximationandlowerapproximation，roughsetsmakethevaguedegreecomputable．Soithasparticularadvantageswhenitwasusedtodealwithincompleteandimprecisedata：1)Needingnoprioriknowledge；2)Moreobjectiveandprecise；31Highlycomplementarywithothertheo

8、riesofuncertainty．Duetotheseadvantages，roughsetstheoryhasbeenfullyde