计算机工程

• 人工智能及识别技术 • 上一篇    下一篇

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

朱金虎1,2,徐章艳1,2,乔丽娟1,2,谢小军1,2,王婷1,2   

  1. (1.广西多源信息挖掘与安全重点实验室,广西 桂林 541004;2.广西师范大学 计算机科学与信息工程学院,广西 桂林 541004)
  • 收稿日期:2015-08-20 出版日期:2016-08-15 发布日期:2016-08-15
  • 作者简介:朱金虎(1990-),男,硕士研究生,主研方向为数据挖掘、粗糙集理论及其应用;徐章艳,教授;乔丽娟、谢小军、王婷,硕士研究生。
  • 基金项目:

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

Rule Acquisition Algorithm Based on Enriching Discernibility Matrix

ZHU Jinhu  1,2,XU Zhangyan  1,2,QIAO Lijuan  1,2,XIE Xiaojun  1,2,WANG Ting  1,2   

  1. (1.Guangxi Key Lab of Multi-source Information Mining and Security,Guilin,Guangxi 541004,China; 2.College of Computer Science and Information Technology,Guangxi Normal University,Guilin,Guangxi 541004,China)
  • Received:2015-08-20 Online:2016-08-15 Published:2016-08-15

摘要:

基于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

中图分类号: