乔丽娟，徐章艳，谢小军，朱金虎，陈晓飞，李娟

(1.广西师范大学 广西多源信息挖掘与安全重点实验室,广西 桂林 541004； 2.广西师范大学 计算机科学与信息工程学院,广西 桂林 541004)

基于知识粒度的不完备决策表的属性约简算法

乔丽娟1, 2，徐章艳1, 2，谢小军1, 2，朱金虎1, 2，陈晓飞2，李娟2

(1.广西师范大学 广西多源信息挖掘与安全重点实验室,广西 桂林 541004； 2.广西师范大学 计算机科学与信息工程学院,广西 桂林 541004)

摘要：知识粒度是属性约简的有效方法，但对于大型的决策表，计算知识粒度过于费时，算法效率不高。在引入粒度差别矩阵后，设计了一个计算粒度差别矩阵中条件属性出现频率的函数，有效地降低粒度差别矩阵的存储空间，根据此函数设计了一个高效属性约简算法。新算法使得时间复杂度与空间复杂度都降为O(K|C||U|)(其中K=max{|Tc(xi)|, xi∈U}和O(|U|)。最后通过实例仿真说明了此算法的高效性和可行性。

关键词：属性约简；知识粒度；不完全决策表；条件属性频率；差别矩阵；启发信息

中文引用格式：乔丽娟，徐章艳，谢小军，等.基于知识粒度的不完备决策表的属性约简算法[J]. 智能系统学报， 2016, 11(1): 129-135.

英文引用格式：QIAO Lijuan, XU Zhangyan, XIE Xiaojun，et al. Efficient attribute reduction algorithm for an incomplete decision table based on knowledge granulation[J]. CAAI Transactions on Intelligent Systems, 2016, 11(1): 129-135.

波兰的数学家Pawlak在20世纪80年代提出的粗糙集是一种新型的用来处理不完全、不精确与不相容的数学工具和理论[1-2]。经过了30多年的研究和发展，粗糙集理论已在知识发现、数据挖掘、模式识别等领域得到了大量应用[3-4]。属性约简作为粗糙集理论的重要研究内容，已被广大学者所研究，提出了围绕完备决策表的属性约简算法，但是现实生活中的数据往往存在误差，缺失及多源等特征。……