基于不可辨识矩阵的值约简算法

摘要: 属性值约简是粗糙集理论的重要研究课题之一，很多学者对它进行研究并提出了不同的算法，但由于值约简是NP-hard问题， 目前还没有高效的方法.根据可辨识矩阵的定义，提出了不可辨识矩阵，将其运用到属性值约简的问题中.实验结果验证了此算法的可行性和有效性，能节省循环比较时间，提高计算速度.

关键词: 粗糙集；不可辨识矩阵；值约简；规则

中图分类号:TP 311.13

文献标志码:A文章编号:1672-8513(2011)06-0508-03

An Algorithm for Value Reduction Based on Indiscernibility Matrix

LUO Qiujin，CHENG Ronghua,NA Jing

（School of Statistics and Mathematics, Yunnan University of Finance and Economics, Kunming 650221, China）

Abstract: The value reduction is an important research topic in the rough set theory, and many researchers have studied it and put forward different algorithms of value reduction．Because the value reduction algorithm is a NP-hard problem，there is no effective algorithm at present．Based on the definition of identifiable matrix, this paper puts forward an indiscernibility matrix and applies it to the problem of value reduction. It is proved in the experiment that this algorithm saves time on circular comparing and increases computing speed.

Key words: rough set；indiscernibility matrix；value reduction；rules

值约简是粗糙集理论[1-2]的核心内容之一，是在属性约简的基础上对决策表的进一步简化.通过属性约简，可以将决策表中对决策分类不必要的属性省略，从而实现决策表的简化，这有利于从决策表中分析发现对决策分类起作用的属性[3].但是，属性约简只是在一定程度上去掉了决策表中的冗余属性，但是还没有充分去掉决策表中的冗余信息，导致我们不能从中得到令人满意的决策规则.为此，我们还需对决策表进行值约简[4].

值约简的过程就是对每一条记录中的冗余条件属性值进行筛选并删除的过程.一直以来属性值约简倍受粗糙集研究者的关注，也取得了很大的进展[5-6].但由于值约简算法是NP-hard问题，目前还没有高效的值约简算法.

文献［3］中刘清等提出的值约简算法对属性值进行逐条分析，考察规则中是否存在可约简的属性值，然后找到值核，从而生成最简决策规则.此算法在规则获取时具有太大的盲目性，花费了大量的时间用在规则的约简上[7].

针对上述问题，本文考虑将属性约简中起到重要作用的可辨识矩阵引入到值约简中，结合值约简问题自身的一些特点，对可辨识矩阵进行改进，生成不可辨识矩阵，利用该矩阵可以比较快速地找到值核，进而化简每条规则的值约简函数，得到每条规则的值核属性以及最简产生式规则.

1 粗糙集的基本概念[5-6]

定义1 一个信息表知识表达系统S可以表示为：S=，其中：U是对象的非空有限集，即论域；Q=C∪D是属性的非空有限集，子集C和D分别称为条件属性集和决策属性集；V=∪a∈QVa是属性a的值域集；f:U×QV是一个信息函数，它指定U中每一个对象x的属性值.

定义2 属性集R(RQ)，不可分辨关系定义为：

ind(R)={(x,y)∈U2|a∈R,f(x,a)=f(y,a)}，论域U在条件属性集C上形成的划分U/ind(D)={X1,X2,…,Xm}称为条件分类集，论域U在决策属性集D上形成的划分U/ind(D)={Y1,Y2,…,Yp}称为决策分类集.

本算法的核心是在可辨识矩阵的基础上提出不可辨识矩阵的概念：

定义6 不可辨识矩阵

令决策表系统S=(U,Q,V,f)，Q=C∪D是属性集合，子集C={ai|i=1,…,m}和分别称为条件属性集和决策属性集，U={x1,x2,…,xn}为论域，将U按决策属性值划分为一组等价类，记为U/ind(D)={Y1,Y2,…,Yp}，ai(xj)是记录xj在条件属性ai上的取值.则不可辨识矩阵可表示为：

MYt=(mij)={ak,ak(xi)|ak∈C∧ak(xi)=ak(xj)}，

其中i≠j且xi,xj∈Yt， t=1,2,…,p.

根据不可辨识矩阵的定义可知：

1）不可辨识矩阵是一个依主对角线对称的矩阵，在考虑不可辨识矩阵的时候，只需要考虑其上三角（或下三角）的部分就可以了；

2）根据决策属性不同的取值，分别生成对应的不可辨识矩阵；

3）同一矩阵内的元素记录的是得到同一决策属性值的2个样本中相同的条件属性及其取值.

2.2 改进算法的基本思想

不可辨识矩阵中的元素可以作为产生相应决策规则的一条依据，那么可考虑对矩阵中的元素进行约简，以得到最简的决策规则，其基本思想是：首先从矩阵中属性组合数最小的元素出发，考察该条规则是否为真，如果为真则该元素为值核，并将同一矩阵中所有包含该规则的元素进行全部约简；如果该条规则为假，则将该元素删除，然后再用同样的方法考察矩阵中属性组合数较大的元素，最后完成对不可辨识矩阵的约简，使得约简后的矩阵元素就对应一条最简的决策规则.

2.3 基于不可辨识矩阵的值约简算法

4 结语

本算法是建立在不可辨识矩阵所形成规则基础上的一种最简规则获取方法.本文算法比原有方法[3]生成的规则更简，并且整个过程具有良好的理论基础.其主要时间开销集中在找到最少的取值相同的元素集合上，而此过程只与条件属性的个数有关，所以，若决策属性值增加，则生成的矩阵会增加，但是对时间和空间的复杂度的影响并不大.若不可辨识矩阵是一个稀疏矩阵，则本文方法可以取得很好的效果.在实际应用中，一般情况下最简规则的前件一般含项不多，因此，寻找最少元素交集为空的元素集合所需时间很少，使用本文算法可以得到较理想的结果.

参考文献:

［1］PAWLAK Z．Rough sets［J］. International Journal of Information and Computer Science，1982，11(5)：341-356．

［2］PAWLAK Z．Rough set approach to multi-attribute decision analysis［J］．European Journal of Operational Research，1994．72(3)：443-459．

［3］刘清．Rough集及Rough推理［M］.北京：科学出版社，2001：57-60．

［4］罗秋瑾，陈世联.基于值约简和决策树的最简规则提取算法［J］.计算机应用，2005, 25（8）：1853-1855.

［5］王国胤.Rough集理论与知识获取［M］.西安：西安交通大学出版社，2001：51，147-152.

［6］张文修．粗糙集理论与方法［M］.北京：北京科学工业出版社，2001：3-24．

［7］舒芬，王加阳.一种改进的规则分辨矩阵及其属性值约简方法［J］.计算机工程与应用，2007，43（32）：77-79.

［8］常犁云，王国胤，吴渝．一种基于Rough Set理论的属性约简及规则提取方法［J］．软件学报，1999，10(11)：1206-1211.

［9］王珏，王任．基于Rough Set的“数据浓缩”［J］．计算机学报，1998，21(5)：393-400.

［10］成蓉华．吴兆兵．随机信息系统中基于不可辨识矩阵的属性约简［J］．云南民族大学学报：自然科学版，2007，16(4)：324-326.