基于浓缩差别矩阵的规则获取算法  

Rule Acquisition Algorithm Based on Enriching Discernibility Matrix

作　　者：朱金虎[1,2] 徐章艳[1,2] 乔丽娟[1,2] 谢小军[1,2] 王婷[1,2] 

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

出　　处：《计算机工程》2016年第8期170-177,共8页Computer Engineering

基　　金：国家自然科学基金资助项目(60963008;61363034;61262004);广西壮族自治区自然科学基金资助项目(2011GXNS FA018163);广西壮族自治区大学生创新基金资助项目(201510602164)

摘　　要：基于HU的差别矩阵方法不仅构造费时且占用空间大,使得执行效率不高。利用元素间两两比较的方法构造浓缩差别矩阵的算法则时间复杂度过高,不适用大数据的处理。而将差别元素压缩存储在一棵FP树上,却无法去除无用的元素。为此,引入二叉树的思想,对短差别集依次建树,长差别集依次进行比较查找,提出一种改进的浓缩差别矩阵算法,在此基础上,给出扩展的二进制差别矩阵,直接从矩阵中提取规则。实验结果证明,该算法不仅降低了时间复杂度,还能够去掉无用元素,减少存储空间。Currently, the discernibility matrix method which is based on HU is not only time-consuming but also takes up a lot of storage space, so that the efficiency of the method is not high. Some scholars use the method of pairwise comparisons between elements to construct the enriching discernibility matrix algorithm. However, the time complexity is too high. It is not suitable for the processing of big data. There are many other methods which store the discernibility element in a compressed FP tree,but they cannot get rid of those unwanted elements. For this reason, this paper introduces the idea of binary tree,gives a method of a short discernibility set to establish binary tree and a long discernibility set to seek and compare in the binary tree, and puts forward an improved enriching discernibility matrix algorithm. On this basis,it proposes the extended binary discernibility matrix, and directly extracts rules from the matrix. Experimental results show that the acquisition algorithm of the enriching discernibility matrix not only reduces the time complexity but also gets rid of the unwanted elements and reduces the storage space.

关 键 词：粗糙集 浓缩差别矩阵 二叉树 扩展的二进制差别矩阵 规则获取 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]