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

Efficient attribute reduction algorithm for an incomplete decision table based on knowledge granulation

作　　者：乔丽娟[1,2] 徐章艳[1,2] 谢小军[1,2] 朱金虎[1,2] 陈晓飞[2] 李娟[2] 

机构地区：[1]广西师范大学广西多源信息挖掘与安全重点实验室,广西桂林541004 [2]广西师范大学计算机科学与信息工程学院,广西桂林541004

出　　处：《智能系统学报》2016年第1期129-135,共7页CAAI Transactions on Intelligent Systems

基　　金：国家自然科学基金资助项目(61262004;61363034;60963008);广西自然科学基金资助项目(2011GXNSFA018163);大学生创新资助项目(201410602099)

摘　　要：知识粒度是属性约简的有效方法,但对于大型的决策表,计算知识粒度过于费时,算法效率不高。在引入粒度差别矩阵后,设计了一个计算粒度差别矩阵中条件属性出现频率的函数,有效地降低粒度差别矩阵的存储空间,根据此函数设计了一个高效属性约简算法。新算法使得时间复杂度与空间复杂度都降为O(K|C||U|)(其中K=max{|Tc(xi)|,xi∈U}和O(|U|)。最后通过实例仿真说明了此算法的高效性和可行性。The use of knowledge granularity is an effective attribute reduction approach. But for a large decision table,computing knowledge granularity is so time-consuming that the algorithm is not efficient for practical use.After the introduction of the discernibility matrix of granularity,a function was designed for calculating the occurrence frequency of condition attributes in the matrix. In this paper,we design an efficient attribute reduction algorithm based on the granularity discernibility matrix. The new algorithm reduces the time and space complexities to O（ K ｜C ｜ ｜ U ｜）（ K = max{ ｜ Tc（ xi） ｜,xi∈U}） and O（ ｜ U｜）,respectively. The results from our simulation example verify that the proposed algorithm is feasible and highly efficient.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]