《一种改进的基于差别矩阵的知识挖掘方法》由会员分享，可在线阅读，更多相关《一种改进的基于差别矩阵的知识挖掘方法（3页珍藏版）》请在金锄头文库上搜索。
1、计算机科学2 0 0 6 V 0 1 3 3 N o 8 ( 增刊)一种改进的基于差别矩阵的知识挖掘方法* ) AM e t h o do fK n o w l e d g eM i n i n gB a s e do nD i s c e r n i b i l i t yM a t r i x杨莉萍陈仪香( 上海师范大学数理信息学院上海2 0 0 2 3 4 )A b s t r a c tK n o w l e d g em i n i n gi so n eo ft h em o s ti m p o r t a n tp r o b l e m si ni n f o r m a t
2、 i o ns y s t e m I nt h i sp a p e r ，w ea d v a n c eam e t h o do fk n o w l e d g em i n i n gb a s e do nR o u g hS e tT h e o r y ，a n dp r o v i d ea ni m p r o v ea l g o r i t h mw h i c hp r o d u c e st h eS k o w r o nD i s c e r n i b i l i t yM a t r i x A f t e ru s i n gt h i sa l g
3、o r i t h m ，w ec a na b s t r a c tt h ei m p o r t a n tm e s s a g e sf r o md e c i s i o nt a b l eq u i c k l ya n dc o n v e n i e n t l y K e y w 叭l sK n o w l e d g em i n i n gr o u g hs e t ，D e c i s i o nr u l e ，D i s c e r n i b i l i t ym a t r i x1引言粗糙集( R o u g hS e t ) 是一种新的处理不精确、
4、不完全和不相容知识的数学理论 1 2 。其中属性约简是重要的研究内容之一，而很多属性约简都是从核开始的，于是求核就成了属性约简的关键步骤。为了求出决策表中的核属性，人们采用依次去掉决策表中的条件属性的方法，但是却总是被复杂的计算量所困扰，于是H U 等提出了一种基于差别矩阵的求解核属性的方法 3 ，该方法可以有效地减少计算量，提高求解核属性的效率，但是在某些情况下却不能得到正确的核，于是叶东毅等人改进了H U 的差别矩阵 4 ，并证明其求核方法是正确的，但该方法在定义差别矩阵中的每个矩阵元素时又增加了计算的复杂度。于是本文中，我们对H U 的差别矩阵生成过程进行改进，并提出相应算法。具体做法为
5、：先将原始决策表分为完全相容和完全不相容决策表；其次分别利用本文所提出的算法对这两张子表进行分析，从中提炼出约简的决策规则，使得从决策表中挖掘出重要信息变得更快更方便。这个算法已成功地用在自适应智能形成的实现r 5 。2 相关概念定义1 1 2 , 3 S 一( U ，A ) 为一信息系统，且C ，DA ，是两属性子集，分别称为条件属性和决策属性，且C U D = A ，C A D = d p ，则该信息系统称为决策表。定义2 1 - 2 3差别矩阵是粗糙集理论中一个非常重要的概念，用于信息表的属性约简。差别矩阵的定义如下：设s 为决策表，论域U 一 x 1 ，X 2 ，) ( 1 1 1 )
6、 是研究对象，条件属性C = e ，e z ，c n ) ，决策属性D = d 。，d z ，“) 。定义差别矩阵元素为f a E Ca ( x i ) a ( x j ) AD ( ) 【i ) D ( X j )“峋由上述条件不满足时决策表S 的差别函数定义为一I I ( x y ) 6 u x u a ( x ，y ) 差别函数的极小析取范式中的所有合取式是C 的所有D 约简。其中的核属性定义如下：C o r e D ( C ) 一 a 。C If ( x ，a ) = a ) ，其中于x ，YU 利用差别矩阵来表达知识有许多优点，它将信息表中关于属性区分的信息浓缩进一个矩阵中，可以用于
7、信息表的属性约简。3 改进的差别矩阵生成方法通过分析，我们发现，如果根据差别矩阵计算后得到的知识约简不止一个的话，那么由不同的知识约简所得到的规则约简在大多数情况下是不同的。因为当存在不止一种知识约简，而人们又选择其中一种知识约简形式时，实质上已经人为删去了某些条件属性，即此时已经添加了人为的因素在其中，而在通常情况下，我们总是希望能尽量减少人为干预，最大限度地挖掘出原始数据中的重要信息。而在原来的知识约简方法中，除非将在不同的约简属性集基础上得到的决策规则集合进行合并，否则丢失某些信息是必然的，而这样就又会增加不少的运算量。于是在本文中，我们设计了针对S k o w r o n 差别* )
8、本文得到了国家自然科学基金( 6 0 2 7 3 0 5 2 ) 以及上海市教委研究基金( 0 5 1 ) Z 0 6 ) 的资助。杨莉萍硕L 研究生，研究方向：知识智能处理。陈仪香博上生导师研究方向：软f ，I 理论，知识智能处理。3 0 8 矩阵生成过程的改进，希望能从原始的数据中挖掘出尽可能多的信息，而又尽量不丢失重要信息。在大多数的文献中，差别矩阵的生成是用于知识约简，对规则的约简则无能为力，但是如果我们对差别矩阵做进一步深入的分析，却发现我们完全可以类似地利用差别矩阵进行属性约简的方法应用于属性值的约简，思路为将差别矩阵中第i 行进行属性约简处理，而后将属性用第i 行记录对应的属性值
9、替换，即得属性值约简，该方法与基于差别矩阵属性约简的差别在于：属性约简在整个差别矩阵中找属性的最小组合，而属性值约简是在差别矩阵的每一行中找属性最小组合，从而保证了约简后的规则与所有其它对象的规则不产生冲突。由于当差别矩阵应用于不相容决策表时可能会造成核属性求解错误，于是本文中，我们先判断：若原始决策表为不相容决策表，则首先将决策表分为完全相容和完全不相容决策表。我们先分析完全相容决策表。在此基础上，我们经过认真分析与实践，研究出具体的算法如下：算法R e d u c t i o n ：输入：决策表，设有n 条记录，m 个条件属性) ；S t e p l ：令i O ；S t e p 2 ：依
10、次比较第i 条记录的决策属性值与第j ( j i + 1 ，n ) 条记录的决策属性值，若决策属性值相同，贝0a i j 一中，否则转S t e p 3 ；S t e p 3 ：依次比较第i 条记录的条件属性值与第j ( j i + 1 ，n ) 条记录的条件属性值，若对应的条件属性值不同，则记录下该属性，直到比较完所有的条件属性，将该元素记为a i j ，转S t e p 4 ；S t e p 4 ：比较a i j 是否包含于第i 行中的某个元素a m n ，若是，则删除a m n ，若第i 行中的某个元素包含于a j ，则删除a 巧，若都不是，则保留a i j ，转S t e p 5 ；S
11、 t e p 5 ：若j n ，则令j = j + 1 ，转S t e p l ，生成第i 条记录的下一个元素，否则转S t e p 6 ；S t e p 6 ：若i n ，则令i i + 1 ，转S t e p l ，生成差别矩阵的下一行元素，否则，转S t e p 7 ；S t e p 7 ：差别矩阵的所有元素生成结束；S t e p 8 ：删除所有行中元素均为空的行；S t e p 9 ：令i = 1 ( 指向第1 行) ，D i 一面；S t e p l 0 ：若第i 行中含有度为1 的元素，则将其加入D i 中，转S t e p l l ；否则，转S t e p l 2 ；S t e
12、 p l l ：检测在第i 行中是否还有其它元素，若没有，转S t e p l 3 ，若有，则转S t e p l 2 ；S t e p l 2 ：统计第i 行中其余属性在该行中不同元素中出现的次数，找出出现频率最高的属性，使其加入D i 中，并删除该行中出现该属性的元素，若此时第i行的所有元素为空，则转S t e p l 3 ，否则，转S t e p l 2 ；S t e p l 3 ：则第i 条记录即可以由D i 来表示；S t e p l 4 ：若i 没有指向最后一条记录，则令i i + 1 ，D i 一击，转S t e p l 0 ，否则，结束；输出：决策表中已经经过约简的决策规则。此
13、算法中，我们只要生成一次差别矩阵，就能实现单条规则的所有约简。对于一些不必要的元素马上删除，这样就避免了无意义的比较，节省了大量的时间和存储空间，而对结果的正确性却没有丝毫影响。以我们的一自适应智能体形成为例 6 ，有如下一决策表。狼数量U ( a )l5253040556272从差别矩阵的生成过程我们可以看出其是对称矩阵。所以人们一般采用上三角或下三角矩阵的形式来表述，为了论述方便，我们将差别矩阵填充完整，如下所示。接下来，我们采用本文改进的算法R e d u c t i o n ，得最终的差别矩阵，见下表。1m由由西由a , b ，d3a , da由d西击5b ，db由咖由由我们由上表，可
14、直接得到原始决策表的所有决策规则的约简形式为：狼数量( 5 ) A 总诱惑力值( 1 0 ) 一成功否H P ( 4 0 ) VH P ( 3 5 ) 一成功否狼数量( O ) H P ( 2 0 ) 一成功是总诱惑力值( 6 0 ) V 总诱惑力值( 2 5 ) 一( 下转第3 1 8 页)3 0 9 蝴否否是否是是是哪加於加雌龇幻加加加加需。mm 豁筋总力6饥饥巾饥由巾aaa；叫b由州由由4 e 由d 由h h3础a由d由由4a2由出a由B h。由由神由州Ul23456m R N A 时，会导致m R N A 链的断裂，断裂片断逐渐消失，重新变成游离的核苷酸( 图5 ) 。图5 m R N
15、 A 被核糖核酸酶降解由上述的A n a l o g - C e l l 的基本执行过程可以看出，该电子细胞模型已在图形显示方面生动、形象地模拟了全部基因表达过程，并且符合第三节叙述的关于基因表达的生物学原理，因此模型的设计是完全合理的。这里限于篇幅只给出一些模拟结果，具体的模拟过程、模型的建模设计以及为实现模拟过程设计的算法等等，请参照作者的另一篇文章A n a l o g - C e l l ：一种新的电子细胞图形模型m 3 。5 进一步的工作A n a l o g - C e l l 模型进一步的模拟工作主要包括以下几个方面：( 1 ) 实现对基因表达过程中物质与能量产生及消耗的数据统计
16、。目前为止，A n a l o g - C e l l 只是完成了基因表达图形方面的模拟，而电子细胞技术研究的最终目的是要通过模拟细胞内的生化过程来发现生物学的新规律，或者用细胞生命活动体现出来的生命特征来帮助计算机实现智能。那么对与生命现 象相关的生化过程进行数据统计，并以曲线的形式直观地体现在窗口中供学者们研究，就变得格外重要。( 2 ) 加人多种酶及调节因子，真实地模拟它们在真核细胞基因表达过程中如何控制反应的进行。目前A n a l o g - C e l l 已实现一些主要酶及因子的调节作用，但仍然有许多因子没有加人到模型中来。如果能在模型中反映出所有与基因表达有关的因子的调节作用，对于进一步了解基因表达过程的调控将起到重要作用。( 3 ) 实现用户接口。为了使A n a l o g - C e l l 模型真正地可以用来观察细胞内某个基因表达的过程并发现其中的某些规律，应当实现用户接口使用户可以输入从生
