示例学习的扩张矩阵算法描述课件.ppt

1、示例学习的扩张矩阵算法描述 报告人：姜宁主要内容 相关概念介绍 基于扩张矩阵的FCV算法描述 FCV算法改进 进一步的工作相关概念介绍选择子：是形为XjAj的关系语句，Aj Dj ；其中Xj为第j个属性， Dj为第j个属性的属性值集合， Aj 为Dj中的一个值.公式（项）：是选择子的合取式，即 XjAj ，其中 J 1,.,n.规则：是公式的析取式，即 Li，其中Li为公式. 举例：（a1!=0 且a4!=1）|（ a3!=0 且a1!=2 ）Jji1t 相关概念介绍扩张矩阵：已知正例e+=及反例矩阵NE.对于每个j N(属性集合)，用“死元素”*对Vj+在NE中第j列的所有出现做代换，这样得

2、到的矩阵叫做e+在反例集NE背景下的扩张矩阵，记为EM（e+），e+叫做该扩张矩阵的种子. 相关概念介绍公共路径：在一个扩张矩阵中，由分别来自不同行的m个非死元素连接组成它的一条路（径）；在两个以上的扩张矩阵中，具有相同值的对应的非死元素叫做他们的公共元素；只由公共元素组成的路叫做它们的公共路.具有公共路的两个扩张矩阵叫做相交的，否则叫做不相交的.最大复合：由最多的一组相交扩张矩阵所具有的公共路叫做最大公共路.由最大公共路形成的公式叫做最大复合.x1x2x3x1x2x31000101200201031201104100112PENEx1x2x3x1x2x311*11*12*1*10311*11

3、0411211*EM(e1+)EM(e2+)相关概念介绍扩张矩阵算法描述启发式算法FCV 这里引用星期六什么天气适合打高尔夫球的例子来对算法进行简单的描述（符号值离散化）. PENE#a1a2a3a4#a1a2a3a4310001000042100200015221062211712118010090210142101102110110111121101131010扩张矩阵算法描述扩张矩阵算法描述 正例集PE和反例集NE的评价矩阵PEM和NEM如下表.评价矩阵PEM的元素PEMi,j就是正例集PE中第j个特征为i的例子数.PEMNEMa1a2a3a4a1a2a3a402236032421446

4、310213233221扩张矩阵算法描述 要求排斥反例多而正例少，设排斥的正例数为Pe，排斥的反例数为Ne，即Pe/ Ne最少. For(i=0;iN;i+),For(j=0;jF;j+)求PEMi,j/NEMi,j最小值. 第一轮求得的最小值为2/3，i=0，j=1.这样正例中被排斥的例子为9,11,反例被排斥的例子为1,2,8.PENE扩张矩阵算法描述PEMNEMa1a2a3a4a1a2a3a400235000101434210112232221第一轮下来反例矩阵还有例子剩余，因此继续建立剩余所有正例和剩余所有反例的评价矩阵.如下表.扩张矩阵算法描述 第二轮求得i=1,j=4.正例集中被排

5、除例子7,12,反例集中被排除例子为6,14.这样反例集剩余例子为0.第一步筛选完成. 建立剩余正例集(3,4,5,10,13)和所有反例集(1,2,6,8,14)的扩张矩阵，寻找公共路即公式.具体实现时，没有必要生成一个个扩张矩阵，而只要在一个反例矩阵NE中，根据扩张矩阵定义中填充死元素的特点，搜索公共路上的元素即可。EM(NE)#a1a2a3a41 5 03302 5 033 5 16242 5 18 5 033014233 5 1扩张矩阵算法描述 公共元素：a1=0,a4=1. 从公共元素中挑选选择子组成包含最少选择子的公式.第一步训练到的公式为a1!=0 且 a4!=1.扩张矩阵算法描

6、述 第二步建立扩张矩阵如下表(正例集包含7,9,11,反例集包含1,2,6,8,14). 公共元素：a1=2,a3=0,a2=0. 训练到的公式为：a3!=0,a1!=2.EM(NE)#a1a2a3a411 3 0 3 0221 3 0 3 016 3 2 1 01812 3 0214 3 22 3 01扩张矩阵算法描述 第三步建立扩张矩阵如下表（正例集包含12,反例集包含1,2,6,8,14 ）. 得到的公式为：a3!=0,a1!=2.EM(NE)#a1a2a3a411010210116110181110141111扩张矩阵算法描述 此训练集训练到的规则为： （a1!=0 且 a4!=1）或

7、（ a3!=0 且 a1!=2 ） 或（ a3!=0 且 a1!=2 ）算法改进 FCV算法中，Step1建立正、反例评价矩阵后，Step主要是寻找正、反例评价矩阵中对应元素比值(即PEMi,j/NEMi,j)最小时，相应的i,j值，即当前评价矩阵中，aj=i时覆盖正例最少，覆盖反例最多。因为把aj=i的正例排除在本次寻找最大复合之外，所以aj=i必是建立的扩张矩阵的公共元素；同时每次建立扩张矩阵寻找最大复合之前都是要求排除最少的正例，排除所有反例；所以考虑在建立评价矩阵筛选正、反例子过程中，记录这些公共元素组成公式，省去通过建立扩张矩阵得到公式这一步。 例子演示中，需要两次建立评价矩阵来排除

8、最少的正例和所有反例。第一次建得的评价矩阵中使PEMi,j/NEMi,j最小的属性值为a1=0，第二次求得的属性值为a4=1；删除a1=0和a4=1的正例后，未被排除的正例集合和整个反例集建立扩张矩阵得到的公式为a1!=0 & a4!=1，恰好是两次评价矩阵中PEMi,j/NEMi,j最小的属性值取否。算法改进实验结果Dataset#Att#class#Rec#rulesselectorsTest AccuracyTest VarianceBalance-Scale 53625FCV96.6837.987.30%0.006383IFCV96.6831.290.65%0.003869Heart1

9、42270FCV13.490.789.26%0.001769IFCV13.497.389.98%0.000956Hatehi202155FCV7.834.986.00%0.004525IFCV7.835.787.00%0.003663Tic-tac-toe102958FCV19.8115.598.86%0.000184IFCV19.8113.899.38%0.000156Mushroom2328124FCV213.9100.00%0.000000IFCV213.9100.00%0.000000进一步的工作进一步的工作 读一些关于扩张矩阵和其他方法结合的论文，例如遗传算法、粗糙集等，希望能和其他

10、算法结合而更好的提取规则，以适用于在不同特点的数据库上更好的提取规则参考文献参考文献1 洪家荣.示例学习的扩张矩阵理论J.计算机学报1991.6,14(6):401-410.2 陈彬,洪家荣.示例学习的最大复合问题及算法J.计算机学报,1997.2,20(2):139-144.3 王亚东,郭茂祖,张宝昌.一个新的基于扩张矩阵的规则抽取覆盖算法J.哈尔滨工业大学学报,2000.8,32(4):123-126.4 洪家荣.示例式学习及多功能学习系统AE5J.计算机学报,1989,12(2):98-105.5 Tom M.Mitchel.Machine LearningM.北京：机械工业出版社，2003.3.6 郭茂祖,洪家荣.示例学习的扩张图方法J.哈尔滨工业大学学报,1998.2,30(1):65-67.