示例學(xué)習(xí)的擴(kuò)張矩陣算法描述課件

示例學(xué)習(xí)的擴(kuò)張矩陣算法描述

報(bào)告人：姜寧示例學(xué)習(xí)的擴(kuò)張矩陣算法描述主要內(nèi)容相關(guān)概念介紹基于擴(kuò)張矩陣的FCV算法描述

FCV算法改進(jìn)進(jìn)一步的工作主要內(nèi)容相關(guān)概念介紹相關(guān)概念介紹選擇子：是形為[Xj≠Aj]的關(guān)系語句，AjDj；其中Xj為第j個(gè)屬性，Dj為第j個(gè)屬性的屬性值集合，Aj

為Dj中的一個(gè)值.公式（項(xiàng)）：是選擇子的合取式，即[Xj≠Aj]，其中J{1,….,n}.規(guī)則：是公式的析取式，即Li，其中Li為公式.舉例：（a1!=0且a4!=1）||（a3!=0且a1!=2）相關(guān)概念介紹選擇子：是形為[Xj≠Aj]的關(guān)系語句，Aj相關(guān)概念介紹擴(kuò)張矩陣：已知正例e+=<V1+,…,Vn+>及反例矩陣NE.對(duì)于每個(gè)jN(屬性集合)，用“死元素”*對(duì)Vj+在NE中第j列的所有出現(xiàn)做代換，這樣得到的矩陣叫做e+在反例集NE背景下的擴(kuò)張矩陣，記為EM（e+），e+叫做該擴(kuò)張矩陣的種子.相關(guān)概念介紹擴(kuò)張矩陣：已知正例e+=<V1+,…,Vn+>及相關(guān)概念介紹公共路徑：在一個(gè)擴(kuò)張矩陣中，由分別來自不同行的m個(gè)非死元素連接組成它的一條路（徑）；在兩個(gè)以上的擴(kuò)張矩陣中，具有相同值的對(duì)應(yīng)的非死元素叫做他們的公共元素；只由公共元素組成的路叫做它們的公共路.具有公共路的兩個(gè)擴(kuò)張矩陣叫做相交的，否則叫做不相交的.最大復(fù)合：由最多的一組相交擴(kuò)張矩陣所具有的公共路叫做最大公共路.由最大公共路形成的公式叫做最大復(fù)合.相關(guān)概念介紹公共路徑：在一個(gè)擴(kuò)張矩陣中，由分別來自不同行的mx1x2x3x1x2x31000101200201031201104100112PENEx1x2x3x1x2x311*11*12*1**10311*110411211*EM(e1+)EM(e2+)相關(guān)概念介紹x1x2x3x1x2x3100010120020103120擴(kuò)張矩陣算法描述啟發(fā)式算法FCV這里引用星期六什么天氣適合打高爾夫球的例子來對(duì)算法進(jìn)行簡單的描述（符號(hào)值離散化）.擴(kuò)張矩陣算法描述啟發(fā)式算法FCV

PENE#a1a2a3a4#a1a2a3a4310001000042100200015221062211712118010090210142101102110110111121101131010擴(kuò)張矩陣算法描述PENE#a1a2a3a4#a1a2a3a431000100擴(kuò)張矩陣算法描述正例集PE和反例集NE的評(píng)價(jià)矩陣PEM和NEM如下表.評(píng)價(jià)矩陣PEM的元素PEM[i,j]就是正例集PE中第j個(gè)特征為i的例子數(shù).PEMNEMa1a2a3a4a1a2a3a402236032421446310213233221擴(kuò)張矩陣算法描述正例集PE和反例集NE的評(píng)價(jià)矩陣PEM和NE擴(kuò)張矩陣算法描述要求排斥反例多而正例少，設(shè)排斥的正例數(shù)為Pe，排斥的反例數(shù)為Ne，即Pe/Ne最少.For(i=0;i<N;i++),For(j=0;j<F;j++)求PEM[i,j]/NEM[i,j]最小值. 第一輪求得的最小值為2/3，i=0，j=1.這樣正例中被排斥的例子為9,11,反例被排斥的例子為1,2,8.PENE擴(kuò)張矩陣算法描述要求排斥反例多而正例少，設(shè)排斥的正例數(shù)為Pe擴(kuò)張矩陣算法描述PEMNEMa1a2a3a4a1a2a3a400235000101434210112232221第一輪下來反例矩陣還有例子剩余，因此繼續(xù)建立剩余所有正例和剩余所有反例的評(píng)價(jià)矩陣.如下表.擴(kuò)張矩陣算法描述PEMNEMa1a2a3a4a1a2a3a4擴(kuò)張矩陣算法描述第二輪求得i=1,j=4.正例集中被排除例子7,12,反例集中被排除例子為6,14.這樣反例集剩余例子為0.第一步篩選完成.建立剩余正例集(3,4,5,10,13)和所有反例集(1,2,6,8,14)的擴(kuò)張矩陣，尋找公共路即公式.具體實(shí)現(xiàn)時(shí)，沒有必要生成一個(gè)個(gè)擴(kuò)張矩陣，而只要在一個(gè)反例矩陣NE中，根據(jù)擴(kuò)張矩陣定義中填充死元素的特點(diǎn)，搜索公共路上的元素即可。EM(NE)#a1a2a3a415033025033516242518503301423351擴(kuò)張矩陣算法描述第二輪求得i=1,j=4.正例集擴(kuò)張矩陣算法描述

公共元素：a1=0,a4=1.從公共元素中挑選選擇子組成包含最少選擇子的公式. 第一步訓(xùn)練到的公式為a1!=0且a4!=1.擴(kuò)張矩陣算法描述公共元素：a1=0,a4=1.擴(kuò)張矩陣算法描述第二步建立擴(kuò)張矩陣如下表(正例集包含7,9,11,反例集包含1,2,6,8,14).

公共元素：a1=2,a3=0,a2=0.訓(xùn)練到的公式為：a3!=0,a1!=2.EM(NE)#a1a2a3a411303022130301632

10181230214322301擴(kuò)張矩陣算法描述第二步建立擴(kuò)張矩陣如下表(正例集包含7,9,擴(kuò)張矩陣算法描述第三步建立擴(kuò)張矩陣如下表（正例集包含12,反例集包含1,2,6,8,14）.

得到的公式為：a3!=0,a1!=2.EM(NE)#a1a2a3a411010210116110181110141111擴(kuò)張矩陣算法描述第三步建立擴(kuò)張矩陣如下表（正例集包含12,反擴(kuò)張矩陣算法描述此訓(xùn)練集訓(xùn)練到的規(guī)則為：（a1!=0且a4!=1）或（a3!=0且a1!=2）或（a3!=0且a1!=2）擴(kuò)張矩陣算法描述此訓(xùn)練集訓(xùn)練到的規(guī)則為：算法改進(jìn)

FCV算法中，Step1建立正、反例評(píng)價(jià)矩陣后，Step２主要是尋找正、反例評(píng)價(jià)矩陣中對(duì)應(yīng)元素比值(即PEM[i,j]/NEM[i,j])最小時(shí)，相應(yīng)的[i,j]值，即當(dāng)前評(píng)價(jià)矩陣中，aj=i時(shí)覆蓋正例最少，覆蓋反例最多。因?yàn)榘補(bǔ)j=i的正例排除在本次尋找最大復(fù)合之外，所以aj=i必是建立的擴(kuò)張矩陣的公共元素；同時(shí)每次建立擴(kuò)張矩陣尋找最大復(fù)合之前都是要求排除最少的正例，排除所有反例；所以考慮在建立評(píng)價(jià)矩陣篩選正、反例子過程中，記錄這些公共元素組成公式，省去通過建立擴(kuò)張矩陣得到公式這一步。算法改進(jìn)FCV算法中，Step1建立正、反例評(píng)價(jià)例子演示中，需要兩次建立評(píng)價(jià)矩陣來排除最少的正例和所有反例。第一次建得的評(píng)價(jià)矩陣中使PEM[i,j]/NEM[i,j]最小的屬性值為a1=0，第二次求得的屬性值為a4=1；刪除a1=0和a4=1的正例后，未被排除的正例集合和整個(gè)反例集建立擴(kuò)張矩陣得到的公式為a1!=0&&a4!=1，恰好是兩次評(píng)價(jià)矩陣中PEM[i,j]/NEM[i,j]最小的屬性值取否。算法改進(jìn)例子演示中，需要兩次建立評(píng)價(jià)矩陣來排除最少的正例和所有反例。實(shí)驗(yàn)結(jié)果Dataset#Att#class#Rec#rulesselectorsTestAccuracyTestVarianceBalance-Scale53625FCV96.6837.987.30%0.006383IFCV96.6831.290.65%0.003869Heart142270FCV13.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實(shí)驗(yàn)結(jié)果Dataset#Att#class#Rec#rule進(jìn)一步的工作讀一些關(guān)于擴(kuò)張矩陣和其他方法結(jié)合的論文，例如遺傳算法、粗糙集等，希望能和其他算法結(jié)合而更好的提取規(guī)則，以適用于在不同特點(diǎn)的數(shù)據(jù)庫上更好的提取規(guī)則進(jìn)一步的工作讀一些關(guān)于擴(kuò)張矩陣和其他方法結(jié)合的論文，參考文獻(xiàn)[1]洪家榮.示例學(xué)習(xí)的擴(kuò)張矩陣?yán)碚揫J].計(jì)算機(jī)學(xué)報(bào)1991.6,14(6):401-410.[2]陳彬,洪家榮.示例學(xué)習(xí)的最大復(fù)合問題及算法[J].計(jì)算機(jī)學(xué)報(bào),1997.2,20(2):139-144.[3]王亞東,郭茂祖,張寶昌.一個(gè)新的基于擴(kuò)張矩陣的規(guī)則抽取覆蓋算法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),2000.8,32(4):123-126.[4]洪家榮.示例式學(xué)習(xí)及多功能學(xué)習(xí)系統(tǒng)AE5[J].計(jì)算機(jī)學(xué)報(bào),1989,12(2):98-105.[5]TomM.Mitchel.MachineLearning[M].北京：機(jī)械工業(yè)出版社，2003.3.[6]郭茂祖,洪家榮.示例學(xué)習(xí)的擴(kuò)張圖方法[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào),1998.2,30(1):65-67.參考文獻(xiàn)[1]洪家榮.示例學(xué)習(xí)的擴(kuò)張矩陣?yán)碚揫J].示例學(xué)習(xí)的擴(kuò)張矩陣算法描述

報(bào)告人：姜寧示例學(xué)習(xí)的擴(kuò)張矩陣算法描述主要內(nèi)容相關(guān)概念介紹基于擴(kuò)張矩陣的FCV算法描述

FCV算法改進(jìn)進(jìn)一步的工作主要內(nèi)容相關(guān)概念介紹相關(guān)概念介紹選擇子：是形為[Xj≠Aj]的關(guān)系語句，AjDj；其中Xj為第j個(gè)屬性，Dj為第j個(gè)屬性的屬性值集合，Aj

為Dj中的一個(gè)值.公式（項(xiàng)）：是選擇子的合取式，即[Xj≠Aj]，其中J{1,….,n}.規(guī)則：是公式的析取式，即Li，其中Li為公式.舉例：（a1!=0且a4!=1）||（a3!=0且a1!=2）相關(guān)概念介紹選擇子：是形為[Xj≠Aj]的關(guān)系語句，Aj相關(guān)概念介紹擴(kuò)張矩陣：已知正例e+=<V1+,…,Vn+>及反例矩陣NE.對(duì)于每個(gè)jN(屬性集合)，用“死元素”*對(duì)Vj+在NE中第j列的所有出現(xiàn)做代換，這樣得到的矩陣叫做e+在反例集NE背景下的擴(kuò)張矩陣，記為EM（e+），e+叫做該擴(kuò)張矩陣的種子.相關(guān)概念介紹擴(kuò)張矩陣：已知正例e+=<V1+,…,Vn+>及相關(guān)概念介紹公共路徑：在一個(gè)擴(kuò)張矩陣中，由分別來自不同行的m個(gè)非死元素連接組成它的一條路（徑）；在兩個(gè)以上的擴(kuò)張矩陣中，具有相同值的對(duì)應(yīng)的非死元素叫做他們的公共元素；只由公共元素組成的路叫做它們的公共路.具有公共路的兩個(gè)擴(kuò)張矩陣叫做相交的，否則叫做不相交的.最大復(fù)合：由最多的一組相交擴(kuò)張矩陣所具有的公共路叫做最大公共路.由最大公共路形成的公式叫做最大復(fù)合.相關(guān)概念介紹公共路徑：在一個(gè)擴(kuò)張矩陣中，由分別來自不同行的mx1x2x3x1x2x31000101200201031201104100112PENEx1x2x3x1x2x311*11*12*1**10311*110411211*EM(e1+)EM(e2+)相關(guān)概念介紹x1x2x3x1x2x3100010120020103120擴(kuò)張矩陣算法描述啟發(fā)式算法FCV這里引用星期六什么天氣適合打高爾夫球的例子來對(duì)算法進(jìn)行簡單的描述（符號(hào)值離散化）.擴(kuò)張矩陣算法描述啟發(fā)式算法FCV

PENE#a1a2a3a4#a1a2a3a4310001000042100200015221062211712118010090210142101102110110111121101131010擴(kuò)張矩陣算法描述PENE#a1a2a3a4#a1a2a3a431000100擴(kuò)張矩陣算法描述正例集PE和反例集NE的評(píng)價(jià)矩陣PEM和NEM如下表.評(píng)價(jià)矩陣PEM的元素PEM[i,j]就是正例集PE中第j個(gè)特征為i的例子數(shù).PEMNEMa1a2a3a4a1a2a3a402236032421446310213233221擴(kuò)張矩陣算法描述正例集PE和反例集NE的評(píng)價(jià)矩陣PEM和NE擴(kuò)張矩陣算法描述要求排斥反例多而正例少，設(shè)排斥的正例數(shù)為Pe，排斥的反例數(shù)為Ne，即Pe/Ne最少.For(i=0;i<N;i++),For(j=0;j<F;j++)求PEM[i,j]/NEM[i,j]最小值. 第一輪求得的最小值為2/3，i=0，j=1.這樣正例中被排斥的例子為9,11,反例被排斥的例子為1,2,8.PENE擴(kuò)張矩陣算法描述要求排斥反例多而正例少，設(shè)排斥的正例數(shù)為Pe擴(kuò)張矩陣算法描述PEMNEMa1a2a3a4a1a2a3a400235000101434210112232221第一輪下來反例矩陣還有例子剩余，因此繼續(xù)建立剩余所有正例和剩余所有反例的評(píng)價(jià)矩陣.如下表.擴(kuò)張矩陣算法描述PEMNEMa1a2a3a4a1a2a3a4擴(kuò)張矩陣算法描述第二輪求得i=1,j=4.正例集中被排除例子7,12,反例集中被排除例子為6,14.這樣反例集剩余例子為0.第一步篩選完成.建立剩余正例集(3,4,5,10,13)和所有反例集(1,2,6,8,14)的擴(kuò)張矩陣，尋找公共路即公式.具體實(shí)現(xiàn)時(shí)，沒有必要生成一個(gè)個(gè)擴(kuò)張矩陣，而只要在一個(gè)反例矩陣NE中，根據(jù)擴(kuò)張矩陣定義中填充死元素的特點(diǎn)，搜索公共路上的元素即可。EM(NE)#a1a2a3a415033025033516242518503301423351擴(kuò)張矩陣算法描述第二輪求得i=1,j=4.正例集擴(kuò)張矩陣算法描述

公共元素：a1=0,a4=1.從公共元素中挑選選擇子組成包含最少選擇子的公式. 第一步訓(xùn)練到的公式為a1!=0且a4!=1.擴(kuò)張矩陣算法描述公共元素：a1=0,a4=1.擴(kuò)張矩陣算法描述第二步建立擴(kuò)張矩陣如下表(正例集包含7,9,11,反例集包含1,2,6,8,14).

公共元素：a1=2,a3=0,a2=0.訓(xùn)練到的公式為：a3!=0,a1!=2.EM(NE)#a1a2a3a411303022130301632

10181230214322301擴(kuò)張矩陣算法描述第二步建立擴(kuò)張矩陣如下表(正例集包含7,9,擴(kuò)張矩陣算法描述第三步建立擴(kuò)張矩陣如下表（正例集包含12,反例集包含1,2,6,8,14）.

得到的公式為：a3!=0,a1!=2.EM(NE)#a1a2a3a411010210116110181110141111擴(kuò)張矩陣算法描述第三步建立擴(kuò)張矩陣如下表（正例集包含12,反擴(kuò)張矩陣算法描述此訓(xùn)練集訓(xùn)練到的規(guī)則為：（a1!=0且a4!=1）或（a3!=0且a1!=2）或（a3!=0且a1!=2）擴(kuò)張矩陣算法描述此訓(xùn)練集訓(xùn)練到的規(guī)則為：算法改進(jìn)

FCV算法中，Step1建立正、反例評(píng)價(jià)矩陣后，Step２主要是尋找正、反例評(píng)價(jià)矩陣中對(duì)應(yīng)元素比值(即PEM[i,j]/NEM[i,j])最小時(shí)，相應(yīng)的[i,j]值，即當(dāng)前評(píng)價(jià)矩陣中，aj=i時(shí)覆蓋正例最少，覆蓋反例最多。因?yàn)榘補(bǔ)j=i的正例排除在本次尋找最大復(fù)合之外，所以aj=i必是建立的擴(kuò)張矩陣的公共元素；同時(shí)每次建立擴(kuò)張矩陣尋找最大復(fù)合之前都是要求排除最少的正例，排除所有反例；所以考慮在建立評(píng)價(jià)矩陣篩選正、反例子過程中，記錄這些公共元素組成公式，省去通過建立擴(kuò)張矩陣得到公式這一步。算法改進(jìn)FCV算法中，Step1建立正、反例評(píng)價(jià)例子演示中，需要兩次建立評(píng)價(jià)矩陣來排除最少的正例和所有反例。第一次建得的評(píng)價(jià)矩陣中使PEM[i,j]/NEM[i,j]最小的屬性值為a1=0，第二次求得的屬性值為a4=1；刪除a1=0和a4=1的正例后，未被排除的正例集合和整個(gè)反例集建立擴(kuò)張矩陣得到的公式為a1!=0&&a4!=1，恰好是兩次評(píng)價(jià)矩陣中PEM[i,j]/NEM[i,j]最小的屬性值取否。算法改進(jìn)例子演示中，需要兩次建立評(píng)價(jià)矩陣來排除最少的正例和所有反例。實(shí)驗(yàn)結(jié)果Dataset#Att#class#Rec#rulesselectorsTestAccuracyTestVarianceBalance-Scale53