周世睿,郭 星
（安徽大学 计算机科学技术学院，安徽，合肥 230000）
摘 要：随着粗糙集理论在诸多领域的广泛应用，特别是针对海量数据应用粗糙集理论，对于实时性有了更高要求，在这种情况下针对求核与属性约简也提出了更高的要求，目前有许多粗糙集求核算法，但是在时间复杂度或者空间复杂度上都或多或少有着缺陷.本研究利用基数排序和二分法的思想设计了一种快速求核算法，其时间复杂度为O(|U||C|2)通过实验，证明了算法的正确性和高效性.
教育期刊网 http://www.jyqkw.com
关键词 ：粗糙集；基数排序；二分法；核
中图分类号：TP181 文献标识码：A 文章编号：1673-260X（2015）05-0006-03
1 引言
Rough粗糙集理论是波兰数学家Pawlak[1]在1982年提出的，是一种描述模糊与处理不确定数学问题的数学工具，由于无需先验知识，并且可以从规模巨大的数据中挖掘出隐含的信息，被广泛应用于人工智能、模式识别、数据挖掘等领域.启发式属性约简算法由于时间复杂度低，速度较快，因而应用较为广泛.求核作为常见启发式算法的重要步骤，重要程度不言而喻.
Skowron在1995年最早提出了基于差别矩阵的求核算法，Hu[2,3]等人对此算法加以改进.叶东毅[4]利用实例证明了Hu算法在对不一致决策表求核中存在错误，在改进差别矩阵的基础上，给出了一个新的差别矩阵的定义和求核方法；赵军[5]等基于决策系统的一致性，提出了一种不需要建立差别矩阵的核属性计算方法，但是该方法在处理不相容策表时，具有很大的局限性，为了解决因决策表的不相容性导致所求得的核出现错误的问题，闫德勤等将决策表规范化后再构造差别矩阵，然后利用规范化后建立的差别矩阵求核属性，其时间复杂度为O(|U||C|2)；杨明[7]提出了一种改进的差别矩阵及其求核方法.徐章艳[8]等给出了简化的差别矩阵的定义，并设计了一种求核算法，算法的时间复杂度被降为max(O(|U/C|2|C|),O(|U||C|)但以上方法均需要创建差别矩阵或者简化的差别矩阵,如果样本的对象集很大，差别矩阵就要占用很多的空间，增加了计算量和计算时间，影响了计算效率[11,12]在本论文中的将介绍一种快速求核算法，该算法可以对不一致粗糙集求核，避免HU算法在不一致粗糙集求核中存在的问题，并且有较好的时间复杂度.本算法首先对不一致粗糙集进行预处理，通过修改不一致决策表内决策属性属性值，将不一致决策表转化为一致性决策表，并证明该一致性决策表的核属性等同于不一致决策表核属性.然后进行求核.并通过UCI数据集的实验证明本文的求核算法有较好的时间、空间复杂度.
2 基本定义
定义1[1] 称五元组S=(U,A∪d,V,f)为信息系统，其中U为所有对象形成的非空有限集合，称为论域；A为属性的有限集合，d为决策属性.
定义2[2] 若P?哿U，且P不等于空集，则P中所有等价关系的交集也是一个等价关系，称为P上的不可分辨关系，记为IND(P)，且有IND(P)=∩[X]R.表示与等价关系族P相关的知识，称为K中关于U的P的基本知识即P的基本集.为简单起见，我们用U/P代替U/IND(P)，IND(P)的等价类称为知识的基本概念或基本范畴.
5 .结论
本文将基数排序与二分法结合，提出了一种新的求核算法，并通过例子证明了该算法的正确性.本算法时间复杂度为O(|C||U|2).由于本算法不需求取差别矩阵，空间复杂度与时间复杂度都较优.
教育期刊网 http://www.jyqkw.com
参考文献：
〔1〕Pawlak Z.rough sets [J].International of computer and information I science,1982,11(5):341-356.
〔2〕Hu X, Cercone N.Learning in relational databases:.rough set approach[J]Computational intelligence, 1995, 11(2): 323-338.
〔3〕Skowron A, Rauszer C.The discernibility matrices and functions in information systems[M]/Intelligent Decision Support .Springer Nether lands,1992:331-362.
〔4〕叶东毅，陈昭炯.一个新的差别矩阵及其求核方法[J].电子学报，2002,30(7):1086-1088.
〔5〕赵军，土国撤，吴中福，等.一种高效的属性核计算方法[J].小型微型计算机系统，2003,24(11):1950-1953.
〔6〕闫德勤，刘菲斐.属性约简中的差别矩阵与近似精度[J].小型微型计算机系统，2005,26(11):1975-1977.
〔7〕杨明.一种基J飞改进差别矩阵的属性约简增量式更新算法[J].计算机学报，2007,30(5):815-822.
〔8〕徐章艳，杨炳儒，宋威.一个基于差别矩阵的快速求核算法[J].计算机工程与应用,2006,42(6):4-6.
〔9〕葛浩，李龙澎，杨传健.向向数据删除的核属性更新算法[J].控制与决策,2012,27(5).
〔10〕蒋瑜，王嘉响.一种快速属性核求解算法「J].计算机工程与应用，2011,47(26):53-54.
〔11〕钱文彬，杨炳儒，徐章艳，等.一种高效的核属性动态更新算法[J].计算机科学，2012,39(7):210-214.
〔12〕胡秦斌.一种基于决策信息系统的求核属性算法[J].微电子学与计算机，2012,29(007):23-25.
〔13〕张文修，吴伟志，梁吉业，等.粗糙集理论和方法[M].北京:科学出版社，2001.