资源描述：
《基于分治法的快速确定规则获取算法_胡峰》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第23卷第3期模式识别与人工智能Vo.l23No.32010年6月PR&AIJun2010*基于分治法的快速确定规则获取算法胡峰王国胤(西南交通大学信息科学与技术学院成都610031)(重庆邮电大学计算机科学与技术研究所重庆400065)摘要值约简是Rough集
2、理论研究的一个重要内容,目前已有的算法很难快速处理大数据集.文中通过在属性空间上对论域对象的分解,提出一种基于分治法的快速确定规则获取算法,并给出实例说明.该算法可直接从离散2的决策表获取确定决策规则,在数据服从均匀分布的条件下,算法的时间复杂度低于n,适合大数据集的确定规则获取.实验结果说明算法的高效性.关键词粗集,决策表,值约简,分治法中图法分类号TP181QuickAlgorithmforCertainRuleAcquisitionBasedonDivideandConquerMethod
3、HUFeng,WANGGuoYin(SchoolofInformationScienceandTechnology,SouthwestJiaotongUniversity,Chengdu610031)(InstituteofComputerScienceandTechnology,ChongqingUniversityofPostsandTelecommunications,Chongqing400065)ABSTRACTValuereductionisaveryimportantissueinr
4、oughsettheory.Manyefficientalgorithmshavebeendeveloped,however,fewofthemcanprocesshugedatasetsquickly.Inthispaper,aquickalgorithmforcertainruleacquisitionbasedondivideandconquermethodisdevelopedbydividinguniverseobjectsinattributespace.Theproposedalgor
5、ithmisillustratedbyacaseresearchaswel.lAcertainrulesetcanbegotquicklyfromadiscretedecisiontableinthisalgorithm.Ifthedatasetisinuniformdistribution,the2timecomplexityofthealgorithmislessthann,whichisfittoprocesslargedatasetsefficiently.Experimentresults
6、showitshighefficiency.KeyWordsRoughSe,tDecisionTable,ValueReduction,DivideandConquerMethod*国家自然科学基金项目(No.60573068,60773113)、重庆市重点自然科学基金项目(No.2008BA2017)、重庆市杰出青年基金项目(No.2008BA2041)和重庆市教育委员会科学技术研究项目(No.KJ090512)资助收稿日期:2009-03-09;修回日期:2009-11-12作者简介胡峰,男
7、,1978年生,博士研究生,副教授,主要研究方向为智能信息处理.Emai:lhufeng@cqupt.edu.cn.王国胤,男,1970年生,教授,博士生导师,主要研究方向为智能信息处理.350模式识别与人工智能23卷间上对决策表论域进行分解,得到论域的一个覆盖,1引言然后分别对各子集进行求解,最后将各子集的解进[1-3]行合并从而得到原问题的解.该算法在识别率上与Rough集理论由波兰逻辑学家Z.Pawlak已有确定规则获取算法接近,但是在处理大数据集于1982年提出.由于它能有效分析
8、和处理不精确、时效率更高,当数据服从均匀分布时,算法的时间复不一致、不完整等各种不完备信息,并能从中揭示潜2杂度低于n.在的规律,近年来在机器学习、数据挖掘等多个领域得到广泛应用.在基于粗集理论的规则获取研究中,许多学者2Rough集的基本概念已提出各种研究方法.文献[4]提出一种基于投影[10]定义1(决策表)一个决策表S=!U,A=C计算决策规则的算法.文献[5]提出一种基于决策∀D,V,f#,其中,U是对象的集合,也称为论域;A=矩阵的值约简算法.文献[6]
