中国企业运筹学知识发现中属性约简算法的研究*刘银山吴孟达王丹( 国防科技大学理学院数学与系统科学系，湖南长沙4 1 0 0 7 3 )擒要：知识发现中数据约简是一个重要的研究课题，本文基于粗糙集理论对数据约简进行研究，考虑到区分矩阵存在大量冗余数据，提出了最筒区分矩阵( t h eS i m p l e s tD i s c e r n i b i l i t yM a t r i x ) 的概念，最简区分矩阵的非空元素个数与区分矩阵的非空元素个数相比非常小，以致在最筒区分矩阵上花费较少时间和空间可以计算出所有的最小约筒。最后，对U C I 数据实验结果说明该算法的有效性。关键词：粗糙集约简区分矩阵最筒区分矩阵一、引言粗糙集理论是由波兰学者P a w l a k 于1 9 8 2 年提出的，是一种刻划具有不完整性和不确定性信息的全新数学工具，它是从复杂信息系统中导出规则、发现知识、挖掘信息的有力工具。现在，基于粗糙集理论的方法已成为知识发现( K D D ) 主流方法之一。其中属性约简问题是粗糙集理论的一个核心问题【2 6J 。属性约简，就是在保证知识库分类能力不变的条件下，删除其中不相关或不重要的属性，不仅不会改变决策表的分类或决策能力，反而会提高系统潜在知识的清晰度。目前，人们已在理论上证明了计算所有的约简组合甚至计算一个最小约简都是一个N P 完备问题 3 】，因此很难通过枚举法求出问题的所有约简或所有最小约简。目前关于决策表的属性约简题已提出了许多启发式算法【5 6 】，这些算法通常按照某种标准衡量属性的重要性，然后按照贪心算法依次在剩余的属性中挑选最重要的属性，直到挑选出的属性能够保持原条件属性集的分类能力，没被挑选的属性则被看作是冗余的。按照衡量属性重要性的标准，启发式属性约简算法可分为基于分明矩阵的、基于信息熵的和基于近似度的三类。但启发式算法往往不能得到系统的所有约简，还存在效率和最小属性约简的完备性问题。而基于区分矩阵和区分函数构造算法 4 “】能够计算出所有的属性约简，这种算法的基本思路是：利用区分矩阵导出区分函数，然后求解区分函数的合取范式，该范式中的每一个析取项即为决策系统的一个约简。这种算法直观，易于理解，但由于在区分矩阵中存在大量的冗余元素，降低了属性约简算法的效率。本文基于区分矩阵存在大量冗余元素考虑，提出了最简区分矩阵的概念，最简区分矩阵的非空元素个数与区分矩阵的非空元素个数相比大量减少，且对于计算属性约简最简区分矩阵与区分矩阵是等价的，所以在最简区分矩阵上可以高效地计算出所有的约简，由于我们感兴趣的是最小约简，所以在实现算法的时候只关注了所有的最小约简，故可以从中经过比较选择最有利于研究解决问题的最小约简，该算法可以保证最小约简是完备的，从而改变了各种启发式算法对某些数据只能求出一个近似最小约简的弊端。在P 41 6 G I - I z 的P C 机上用V C + + 6 0 实现了该算法，并选取了1 0 组经典的U C I 数据进行了实验，大多数的数据都能在1 秒以内的运行时间内求出所有的最小属性约简。二、相关概念定义1四元组S = ( U ，A V ，) 是一个知识表达系统，其中U 表示对象的非空有限集合，称为论域；A =cu d ，Cn d l = 移，C 称为条件属性集，d 称为决策属性；V = 。故v 口，v 口是属性n 的值域；，表示是u A v 是一个信息函数，它为每个对象的每个属性赋予一个信息值，即：Va 。A ，z U ，f ( z ，a ) V 。我们将具有条件属性和决策属性的知识表达系统称为决策系统。本课题得到国防科大基础项目研究基金资助( G C 0 3 0 0 2 0 0 3 )- 1 2 8 。_ A S k o w r o n 于1 9 9 2 年提出一种用区分矩阵表示知识的方法4 。，这种表示有很多有利条件，特别是用它可以解释和便于计算数据核和约简。决策系统的区分矩阵定义为M = ( 聊“) 。，区分矩阵是一个对称矩阵，其中：脚： ：cJ 口曩口刁L 墨，乃【， d 一d 弓Li 1 ：首先让m 。与核理( A ) 中元素作 运算，如果m o 不被吸收，就让m i 依次与W 7 中元素作 运算，同时简化W 7 ，如果m d 仍不被吸收，则W 7 = WUm 和四、实验结果与分析1 算例例：以气象状态决策系统为例，表1 是由气象状态决策表生成的区分矩阵所有非空的元素，即全空间，其中U = “1 ，“2 ，u 1 4 ，C = a l ，a 2 ，a 3 ，a 4 。表1气象决策决策表的区分矩阵所有非空的元素U 3l z 4U 5u 71 2 9“1 0“l l甜1 2“1 3M 1a 1a l a 2a l a 2c 1 3a l a 2 a 3 a 4a 2 a 3a l a 2 a 3a 2 a 3 a 4口l a 2 a 4a l a 3“2a l a 4a l a 2 a 4a l a 2 a 3 a 4 a l a 2 a 3a 2 a 3 1 2 4a l a 2 a 3 a 4a 2 口3口l a 2ala3a0 4t 6a l a 2 a 3 a 4a 2 a 3 a 4a 4a 1a l a 4a 2 a 4a l a 2a l a 2 a 3a l a 2 a 4“ 81 2 1 a 2a l a 2a 2 a 3 f 1 4 口1 a 2 a 3 a 4a 2 a 3a l a 3a 3 a 4n l a 4a l a 2 a 3U 1 4a l a 2 a 4a 4a 2 a 3 a 4a l a 2 a 3 a l a 2 a 3 a 4a 3 a 3a l a 3a l a 4a l a 2 1 2 3 a 4对气象决策系统执行算法1 ，有c o r e ( A ) = a 1 ，口4 ，W = a 2 a3 ，S W = c o r e ( A ) UW = a l ，a 4 ，口2 n 3 ， 鬻1 0 0 = 杀1 0 0 = 6 6 7 ，简空间的元素个数相对于全空间的元素个数只有6 6 7 ，可见从区分矩阵到最简区分矩阵剔除了大量无用的信息，从而很容易可以得到决策系统的约简 a ，1 2 ：，n 4 与 a l ，a 3 ，n 4 。2 U C I 数据实验及其分析在P 41 6 G H z 的P C 机上用V C + + 6 0 实现了该算法，并选取了机器学习中l O 组经典的U C I 数据( 数据 来源于h t t p ：删s g i C O r n t e c h m l c d b ) 进行了实验，实验结果如表2 所示。- - - 1 3 0 - 知识发现中属性约简算法的研究表2l O 组U C I 数据特征及其约简算法结果数据名称S W所有最小约简 运行时间WS W核Ul IAw( 个数长度)R a n d 2 0 1 3 4 4 s2 4 3 63 9 31 6 1 3 无核5 8 1 0 0 2 1L e d 2 4 1 8 2 8 S1 7 9 6 45 4 23 0 2 无核1 7 5 7 2 0 0 2 5L e d 7 0 0 3 9 S1 7 9 1 770 0 4 9 6123 45671 7 2 0 0 8M o n k l 一l o c a l 0 0 3 1 S3 8 4 49O 2 3 无核9 5 1 2 4 1 8M o n k 2 一l o c a l 0 0 6 1S6 7 2 01 l0 1 6 无核4 6 1 6 9 1 8Z o o 0 0 3 5 s3 8 7 31 40 3 6 61 37 5 1 0 1 1 7S o y b e a n s m a l l0 2 5 5 s3 4 88 72 5 无核4 2 3 1 3 6L u n g c a n c e F 3 0 9 1s2 5 52 4 89 7 2 5 无核6 9 4 2 8 5 7V i 把 0 1 5 7 52 1 3 4 41 2O 0 6 12 3 91 11 31 61 8 3 0 0 1 7V b 把一打v i ? e 0 1 4 1 S2 0 2 4 11 9O 0 9 121 11 31 7 2 9 0X1 7注：核所在列的数字代表属性下标。从实验数据来看，该算法高效的关键是简空间对全空间做到了最有效的“无损压缩”，这种压缩实际上是C 1 i ，I 对满足约简的约束条件式( 3 b ) 极小化得到约束条件式( 4 b ) 的过程，且不会造成约简的不确定性。亳并越小，计算所有最小约简效率就越高。从实验结果来看，本文的计算所有最小属性约简的算法非常有效：第一，该算法速度快。对于U C I 大部分数据都能在1 秒以内求出所有的最小约简。对于数据L e d 2 4 ，生成的简空间S W 中含有元素个数有5 4 2 个，而且本身这个数据的最小约简个数有1 7 5 个，用1 8 秒的时间运算出结果是正常的，也说明了该算法在时间方面的优越性。第二，该算法节省了空间。该算法使用吸收算子无需生成庞大的区分矩阵直接在简空间做遍历，不但加快了计算约简的速度，而且也不用大量空间存放数据。第三，该算法能求出所有的最小属性约简。从理论上来说该算法可以求出所有的约简，由于我们只感兴趣的是最小约简，且若要求出所有约简，对于含有2 4 个条件属性的数据L e d 2 4 ，由它产生的筒空间S W 中含有元素( 属性组合) 有5 4 2 个，在它基础上求出所有约简是一个N P 难题，这也是当决策系统数据量比较大时，我们直接对问题1 进行有效求解是很困难的。 C U ，l 本算法还有一定的不足之处，当数据不能有效的压缩，如数据L u n g c a ，：l c e ? “ ，名并是9 7 2 5 ，就如同直接在全空间上计算所有的最小约简，对只有2 8 个对象5 7 个属性的数据花费了3 秒多的时间，相比与其他数据效率是比较低的。五、结束语人们常常希望获得知识约简尽可能的简洁形式( 即极小属性集尽可能的小) ，这也是机器学习中很多归纳- 1 3 1 中国企业运筹学学习方法所追求的目标之一。由于大部分属性约简方法使用启发式的属性选择方法进行搜索，而各种选择方法都是一种偏向，有它的局限性，只能求出一个约简或者是次最小约简。本文提出的基于最简区分矩阵的计算所有最小属性约简的高效算法简单易操作，充分考虑区分矩阵存在的冗余元素，只保留计算所有属性约简的最小信息量，最大程度的节省时间和空间。且能在最短时间内求出所有最小约简，给解决问题有了比较选择的空间，比现有的启发式约简算法和基于区分矩阵和区分函数构造算法有一定的优越性。参考文献 1 P a w l a k ZR o u g hS e t s M I n t e r n a t i o n a lJ o u r n a lo fC o m p u t e ra n dI n f o r m a t i o ns c i e n c e ，1 9 8 2 ，1 1 ：2 4 1 3 5 6 2 YYY a o O ng e n e r a l i z i n gr o u g hs e t st h e o r y C R o u g hs e t s ，f u z z ys e t s ，d a t am i n i n ga n dg r a n u l a rc o m p u t i n g C h o n g q i n g ，C h i n a ，2 0 0 3 ：4 4 5 1