摘要：

基于HU的差别矩阵方法不仅构造费时且占用空间大,使得执行效率不高。利用元素间两两比较的方法构造浓缩差别矩阵的算法则时间复杂度过高,不适用大数据的处理。而将差别元素压缩存储在一棵FP树上,却无法去除无用的元素。为此,引入二叉树的思想,对短差别集依次建树,长差别集依次进行比较查找,提出一种改进的浓缩差别矩阵算法,在此基础上,给出扩展的二进制差别矩阵,直接从矩阵中提取规则。实验结果证明,该算法不仅降低了时间复杂度,还能够去掉无用元素,减少存储空间。

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

Abstract:

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.

Key words: rough set, enriching discernibility matrix, binary tree, extended binary discernibility matrix, rule acquisition

中图分类号: 

• TP301.6