文档介绍：哈希快速属性约简算法本课题得到国家自然科学基金(60803053, 60675049),浙江省自然科学基金项目(Y106414),国家“八六三”高技术研究发展计划项目基金(2008AA04Z209),国家博士后科学基金(20081459)资助,武器装备预研基金(9140A06050609JW0402)资助,刘勇,男,博士,讲师,研究方向为人工智能,信息处理. E-mail: ******@.. 熊蓉,女,副教授,研究方向为智能机器人. 褚健,男,教授,研究方向为智能控制.
刘勇熊蓉褚健
(浙江大学工业控制国家重点实验室杭州 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 plexity 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 plexity is O(|C|2|U/C|), we also prove this algorithm plete. 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],首先计算数据集的差别矩阵和差别函数,然后通过求差别矩阵中所有项的最小析取范式来获得约简。该算法的优点在于直观,易于理解,而且能够很容易地计算出核与所有约简。但这个算法也存在着不足之处