(哈希快速属性约简算法.docVIP

哈希快速属性约简算法 刘勇 熊蓉 褚健 （浙江大学工业控制国家重点实验室 杭州 310027） （浙江大学智能系统与控制研究所 杭州 310027） 摘要 从决策系统的不一致情况出发，给出了不一致度的概念及其性质，并证明了不一致记录与正区域的等价关系。在此基础上，提出了基于哈希的正区域计算方法，时间复杂度下降为O(|U|)，利用不一致情况的性质设计了一个基于不一致记录数的属性重要性测量参数，用新的测量参数设计了一个基于二次哈希的约简算法，其复杂度下降为O(|C|2|U/C|),并证明采用该测量参数所获得约简的完备性。最后通过实验证明本文正区域算法和约简算法的高效性。 关键词 粗糙集；正区域；约简；哈希; 不一致度 中图分类号 TP18 Quick Attribute Reduction Algorithm with Hash LIU Yong XIONG Rong CHU Jian (State Key Lab. of Industrial Control Technology, Zhejiang University, Hangzhou 310027) (Institute of Cyber-Systems and Control, Zhejiang University Hangzhou 310027) Abstract This paper presents the concept and property of inconsistency from the inconsistent condition of decision system. It also presents the relationship between the positive region and inconsistent records. A hash based algorithm to calculating positive region has been presented and its temporal complexity decreases to O(|U|). Based on the characteristics of inconsistency, a new attribute measure has been introduced, then a corresponding reduction algorithm with twice-hash is presented, and its temporal complexity is O(|C|2|U/C|), we also prove this algorithm is complete. The efficiency of our algorithms is proved by the experiments. Keywords rough set; positive region; reduction; hash; inconsistency 1 引言 求信息系统的约简和最小约简是粗糙集理论研究中的基本问题之一。与其它数据降维的方法[1, 2]相比，使用粗糙集方法进行约简的优势在于能够保持其数据本身的语义特征（Semantic features）[3]。许多学者都对属性约简问题进行过研究[3-9]，其中已经公认的结论是求解信息系统最短约简是一个NP难问题[8]。 通常情况下，约简算法并不需要计算出信息系统的所有约简，仅需获得用户感兴趣或者可用的约简即可。依据粗糙集理论中获取约简方法的不同，常用的计算方法有Greedy法和差别矩阵法。 在Greedy法[5]中，待求约简集通常初始化为核（Core）[5,10]或空集（NULL）[3]，然后依次扫描剩下的属性，从中选取一个使得分类质量增益最大的属性，并把该属性加入到待求约简集中，直到当前候选集计算出的分类质量等于所有条件属性计算出的分类质量。 差别矩阵（也称为差异矩阵或分明矩阵、区分矩阵）法[11-13]，首先计算数据集的差别矩阵和差别函数，然后通过求差别矩阵中所有项的最小析取范式来获得约简。该算法的优点在于直观，易于理解，而且能够很容易地计算出核与所有约简。但这个算法也存在着不足之处，即，由于在矩阵中会出现大量的重复元素（或元素之间存在着包含关系），这就大大降低了属性约简算法的效率。通常此类算法的复杂度为，其中|C|为属性个数，|U|为数据纪录数。 上述约简方法中差别矩阵方法计算过程需耗费巨大的时间和空间，故不常采用。其它方法中都需要频繁计算决策表的正区域，因而计算正区域的时间复杂度直接决定了约简算法的时间复杂度。 通常采用的正区域计算方法时间复杂度为，文献[14]中基于快速排序思想给出了一种