资源描述：
《哈希快速属性约简算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《计算机学报》2009年8期哈希快速属性约简算法本课题得到国家自然科学基金（60803053,60675049），浙江省自然科学基金项目（Y106414），国家“八六三”高技术研究发展计划项目基金（2008AA04Z209），国家博士后科学基金（20081459）资助，武器装备预研基金（9140A06050609JW0402）资助，刘勇，男，博士，讲师，研究方向为人工智能，信息处理.E-mail:yongliu@iipc.zju.edu.cn.熊蓉，女，副教授，研究方向为智能机器人.褚健，男，教授，研究方向为智能控制.刘勇熊蓉褚健（浙江大学工业控制国家重点实验室杭州310027）（
2、浙江大学智能系统与控制研究所杭州310027）摘要从决策系统的不一致情况出发，给出了不一致度的概念及其性质，并证明了不一致记录与正区域的等价关系。在此基础上，提出了基于哈希的正区域计算方法，时间复杂度下降为O(
3、U
4、)，利用不一致情况的性质设计了一个基于不一致记录数的属性重要性测量参数，用新的测量参数设计了一个基于二次哈希的约简算法，其复杂度下降为O(
5、C
6、2
7、U/C
8、),并证明采用该测量参数所获得约简的完备性。最后通过实验证明本文正区域算法和约简算法的高效性。关键词粗糙集；正区域；约简；哈希;不一致度中图分类号TP18QuickAttributeReductionAlgorith
9、mwithHashLIUYongXIONGRongCHUJian(StateKeyLab.ofIndustrialControlTechnology,ZhejiangUniversity,Hangzhou310027)(InstituteofCyber-SystemsandControl,ZhejiangUniversityHangzhou310027)AbstractThispaperpresentstheconceptandpropertyofinconsistencyfromtheinconsistentconditionofdecisionsystem.Italsopres
10、entstherelationshipbetweenthepositiveregionandinconsistentrecords.AhashbasedalgorithmtocalculatingpositiveregionhasbeenpresentedanditstemporalcomplexitydecreasestoO(
11、U
12、).Basedonthecharacteristicsofinconsistency,anewattributemeasurehasbeenintroduced,thenacorrespondingreductionalgorithmwithtwice
13、-hashispresented,anditstemporalcomplexityisO(
14、C
15、2
16、U/C
17、),wealsoprovethisalgorithmiscomplete.Theefficiencyofouralgorithmsisprovedbytheexperiments.Keywordsroughset;positiveregion;reduction;hash;inconsistency1引言求信息系统的约简和最小约简是粗糙集理论研究中的基本问题之一。与其它数据降维的方法[1,2]相比，使用粗糙集方法进行约简的优势在于能够保持其数据本身的语义特征（Semantic
18、features）[3]。许多学者都对属性约简问题进行过研究[3-9]，其中已经公认的结论是求解信息系统最短约简是一个NP难问题[8]。通常情况下，约简算法并不需要计算出信息系统的所有约简，仅需获得用户感兴趣或者可用的约简即可。依据粗糙集理论中获取约简方法的不同，常用的计算方法有Greedy法和差别矩阵法。在Greedy法[5]中，待求约简集通常初始化为核（Core）[5,10]或空集（NULL）[3]，然后依次扫描剩下的属性，从中选取一个使得分类质量增益最大的属性，并把该属性加入到待求约简集中，直到当前候选集计算出的分类质量等于所有条件属性计算出的分类质量。13《计算机学报》20
19、09年8期差别矩阵（也称为差异矩阵或分明矩阵、区分矩阵）法[11-13]，首先计算数据集的差别矩阵和差别函数，然后通过求差别矩阵中所有项的最小析取范式来获得约简。该算法的优点在于直观，易于理解，而且能够很容易地计算出核与所有约简。但这个算法也存在着不足之处，即，由于在矩阵中会出现大量的重复元素（或元素之间存在着包含关系），这就大大降低了属性约简算法的效率。通常此类算法的复杂度为，其中
20、C
21、为属性个数，
22、U
23、为数据纪录数。上述约简方法中差别矩阵方法计算过程需耗费巨大的时
