资源描述：
《一种快速计算HU差别矩阵的属性约简算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、小型微型计算机系统2008年10月第10期JournalofChineseComputerSystemsVol129No.102008一种快速计算HU差别矩阵的属性约简算法1,2111徐章艳,杨炳儒,宋 威,侯 伟1(北京科技大学信息工程学院,北京100083)2(广西师范大学计算机系,广西桂林541004)E2mail:xyzwlx72@yahoo.com.cn摘 要:在已有的基于HU差别矩阵的属性约简算法中,一般是以差别矩阵中的元素作为启发信息而设计的,其时间复杂度为22).O(ûCûûUû为降低该属性约简算法的时间复杂度,首先引入简化决策表的定义,并设计了一个求简
2、化决策表的算法,其时间复杂度为O(ûCûûUû).然后在简化决策表的基础上,定义了差别区域,并给出基于差别区域的属性约简定义,同时证明了基于差别区域的属性约简与基于差别矩阵的属性约简等价.在此基础上,以快速缩小简化决策表的搜索空间为目的,定义了一个新的、较为合理的、度量属性重要性的公式,并给出了它的递归计算方法,其时间复杂度为O(UöCû).最后以属性重要性为启发信息,2设计了一个基于差别矩阵的快速属性约简算法,其时间复杂度降为max(O(ûCûûUû,O(ûCûûUöCû)),并用一个实例说明了新算法的高效性.理论分析与实验表明,新算法具有较好的扩展性.关键词:粗糙集
3、;简化决策表;差别矩阵;差别区域;属性重要性;属性约简;算法复杂度中图分类号:TP18文献标识码:A文章编号:100021220(2008)1021820208QuickAlgorithmofComputingAttributeReductionofHU'sDiscernibilityMatrix1,2111XUZhang2yan,YANGBing2ru,SONGWeiHOUWei1(SchoolofInformationEngineering,UniversityofScienceandTechnologyBeijing,Beijing100083,China)2(D
4、epartmentofComputer,GuangxiNormalUniversity,Guilin541004,China)Abstract:Theelementsofdiscernibilitymatrixareusedastheheuristicinformationbyalltheexistingattributereductionalgo222).TolowertherithmsbasedonHU'sdiscernibilitymatrix.ThetemporalcomplexityofthiskindofalgorithmisO(ûCûûUûtemporal
5、complexity,firstly,thesimplifieddecisiontableisintroduced,andanalgorithmwithtemporalcomplexityO(ûCûûUû)forcalculatingthesimplifieddecisiontableisdesignedaccordingly.Secondly,thedefinitionofdiscernibilityregionbasedonthesimplicitydecisiontableisproposed.Atthesametime,theattributereduction
6、definitionbasedondiscernibilityregionisprovided.Anditisprovedthattheattributereductionbasedondiscernibilityregionisequivalenttothatbasedondiscernibilitymatrix.Basedontheseconditions,toreducethesearchspaceofsimplifieddecisiontable,anewreasonableformulaformea2suringthesignificanceofattribu
7、teisdefined.Andthenarecursivealgorithm,whosetemporalcomplexityisO(ûUöCû),forcomputingthesignificanceofattribute,isproposed.Thirdly,usingproposedthesignificanceofattributeasheuristicinforma2tion,anefficientattributereductionbasedonthesignificanceofattributeisproposed,andth
