1、2020/6/25,1,第三章 分類方法 內(nèi)容提要,分類的基本概念與步驟 基于距離的分類算法 決策樹分類方法 貝葉斯分類 實(shí)值預(yù)測(cè) 與分類有關(guān)的問(wèn)題,2020/6/25,2,分類的流程,根據(jù)現(xiàn)有的知識(shí)，我們得到了一些關(guān)于爬行動(dòng)物和鳥類的信息，我們能否對(duì)新發(fā)現(xiàn)的物種，比如動(dòng)物A，動(dòng)物B進(jìn)行分類？,2020/6/25,3,分類的流程,步驟一：將樣本轉(zhuǎn)化為等維的數(shù)據(jù)特征（特征提?。?。 所有樣本必須具有相同數(shù)量的特征 兼顧特征的全面性和獨(dú)立性,2020/6/25,4,分類的流程,步驟二：選擇與類別相關(guān)的特征（特征選擇）。 比如，綠色代表與類別非常相關(guān)，黑色代表部分相關(guān)，灰色代表完全無(wú)關(guān),2020/6/

2、25,5,分類的流程,步驟三：建立分類模型或分類器（分類）。 分類器通?？梢钥醋饕粋€(gè)函數(shù)，它把特征映射到類的空間上,2020/6/25,6,如何避免過(guò)度訓(xùn)練,分類也稱為有監(jiān)督學(xué)習(xí)(supervised learning),與之相對(duì)于的是無(wú)監(jiān)督學(xué)習(xí)(unsupervised learning),比如聚類。 分類與聚類的最大區(qū)別在于，分類數(shù)據(jù)中的一部分的類別是已知的，而聚類數(shù)據(jù)的類別未知。 建立分類模型需要學(xué)習(xí)一部分已知數(shù)據(jù)，如果訓(xùn)練時(shí)間過(guò)長(zhǎng)，或者預(yù)測(cè)模型參數(shù)太多而樣本較少，將導(dǎo)致過(guò)度訓(xùn)練(overfitting)。,2020/6/25,7,如何避免過(guò)度訓(xùn)練,避免過(guò)度訓(xùn)練最重要一點(diǎn)是，模型的參數(shù)量

3、應(yīng)遠(yuǎn)小于樣本的數(shù)量。 應(yīng)建立訓(xùn)練集(training set)和測(cè)試集(test set)。 訓(xùn)練集應(yīng)用于建立分類模型 測(cè)試集應(yīng)用于評(píng)估分類模型 K折疊交叉驗(yàn)證(K-fold cross validation)：將初始采樣分割成K個(gè)子樣本(S1，S2,.,Sk)，取K-1個(gè)做訓(xùn)練集，另外一個(gè)做測(cè)試集。交叉驗(yàn)證重復(fù)K次，每個(gè)子樣本都作為測(cè)試集一次，平均K次的結(jié)果，最終得到一個(gè)單一估測(cè)。,2020/6/25,8,分類模型的評(píng)估,真陽(yáng)性(True Positive)： 實(shí)際為陽(yáng)性 預(yù)測(cè)為陽(yáng)性 真陰性(True Negative)：實(shí)際為陰性 預(yù)測(cè)為陰性 假陽(yáng)性(False Positive)： 實(shí)際

4、為陰性 預(yù)測(cè)為陽(yáng)性 假陰性(False Negative)：實(shí)際為陽(yáng)性 預(yù)測(cè)為陰性 預(yù)測(cè)是否正確 預(yù)測(cè)結(jié)果 比如預(yù)測(cè)未知?jiǎng)游锸区B類還是爬行動(dòng)物，陽(yáng)性代表爬行動(dòng)物，陰性代表非爬行動(dòng)物，請(qǐng)大家闡述 TP=10，TN=8，F(xiàn)N=3，F(xiàn)P=2是什么意義,2020/6/25,9,分類模型的評(píng)估,靈敏度(Sensitivity)： TP/(TP+FN) 也稱為查全率(Recall) 數(shù)據(jù)集共有13只爬行動(dòng)物，其中10只被正確預(yù)測(cè)為爬行動(dòng)物，靈敏度為10/13 特異度(Specificity): TN/(TN+FP) 數(shù)據(jù)集有10只非爬行動(dòng)物，其中8只被預(yù)測(cè)為非爬行動(dòng)物，特異度為8/10 精度(Precis

5、ion): TP/(TP+FP) 分類器預(yù)測(cè)了12只動(dòng)物為爬行動(dòng)物，其中10只確實(shí)是爬行動(dòng)物，精度為10/12 準(zhǔn)確率(Accuracy): (TP+TN)/(TP+TN+FN+FP) 數(shù)據(jù)集包含23只動(dòng)物，其中18只預(yù)測(cè)為正確的分類，準(zhǔn)確率為18/23,2020/6/25,10,分類模型的評(píng)估,對(duì)于非平衡(unblanced)的數(shù)據(jù)集,以上指標(biāo)并不能很好的評(píng)估預(yù)測(cè)結(jié)果。 非平衡的數(shù)據(jù)集是指陽(yáng)性數(shù)據(jù)在整個(gè)數(shù)據(jù)集中的比例很小。比如，數(shù)據(jù)集包含10只爬行動(dòng)物，990只爬行動(dòng)物，此時(shí)，是否預(yù)測(cè)正確爬行動(dòng)物對(duì)準(zhǔn)確率影響不大。 更平衡的評(píng)估標(biāo)準(zhǔn)包括馬修斯相關(guān)性系數(shù)(Matthews correlatio

6、n coefficient)和ROC曲線。 馬修斯相關(guān)性系數(shù)定義為,2020/6/25,11,分類模型的評(píng)估,ROC曲線通過(guò)描述真陽(yáng)性率(TPR)和假陽(yáng)性率(FPR)來(lái)實(shí)現(xiàn)，其中TPR=TP/(TP+FN), FPR=FP/(FP+TN)。 大部分分類器都輸出一個(gè)實(shí)數(shù)值(可以看作概率),通過(guò)變換閾值可以得到多組TPR與FPR的值。,2020/6/25,12,第三章 分類方法 內(nèi)容提要,分類的基本概念與步驟 基于距離的分類算法 決策樹分類方法 貝葉斯分類 實(shí)值預(yù)測(cè) 與分類有關(guān)的問(wèn)題,2020/6/25,13,基于距離的分類算法的思路,定義4-2 給定一個(gè)數(shù)據(jù)庫(kù) D=t1，t2，tn和一組類C=C

7、1，Cm。假定每個(gè)元組包括一些數(shù)值型的屬性值：ti=ti1，ti2，tik，每個(gè)類也包含數(shù)值性屬性值：Cj=Cj1，Cj2，Cjk，則分類問(wèn)題是要分配每個(gè)ti到滿足如下條件的類Cj： sim(ti，Cj)=sim(ti，Cl) ，ClC，ClCj， 其中sim(ti，Cj)被稱為相似性。 在實(shí)際的計(jì)算中往往用距離來(lái)表征，距離越近，相似性越大，距離越遠(yuǎn)，相似性越小。 距離的計(jì)算方法有多種，最常用的是通過(guò)計(jì)算每個(gè)類的中心來(lái)完成。,2020/6/25,14,基于距離的分類算法的一般性描述,算法 4-1通過(guò)對(duì)每個(gè)樣本和各個(gè)類的中心來(lái)比較，從而可以找出他的最近的類中心，得到確定的類別標(biāo)記。,算法 4-1

8、 基于距離的分類算法 輸入：每個(gè)類的中心C1，Cm；待分類的元組t。 輸出：輸出類別c。 （1）dist=；/距離初始化 （2）FOR i:=1 to m DO （3） IF dis(ci，t)dist THEN BEGIN （4） c i； （5） distdist(ci，t)； （6） END.,2020/6/25,15,基于距離的分類方法的直觀解釋,（a）類定義,（b）待分類樣例,（c）分類結(jié)果,2020/6/25,16,距離分類例題,C1=(3,3,4,2), C2=(8,5,-1,-7), C3=(-5,-7,6,10); 請(qǐng)用基于距離的算法給以下樣本分類： (5,5,0,0) (5

9、,5,-5,-5) (-5,-5,5,5),2020/6/25,17,K-近鄰分類算法,K-近鄰分類算法（K Nearest Neighbors，簡(jiǎn)稱KNN）通過(guò)計(jì)算每個(gè)訓(xùn)練數(shù)據(jù)到待分類元組的距離，取和待分類元組距離最近的K個(gè)訓(xùn)練數(shù)據(jù)，K個(gè)數(shù)據(jù)中哪個(gè)類別的訓(xùn)練數(shù)據(jù)占多數(shù)，則待分類元組就屬于哪個(gè)類別。,算法 4-2 K-近鄰分類算法 輸入： 訓(xùn)練數(shù)據(jù)T；近鄰數(shù)目K；待分類的元組t。 輸出： 輸出類別c。 （1）N=； （2）FOR each d T DO BEGIN （3） IF |N|K THEN （4） N=N d； （5） ELSE （6） IF u N such that sim(t，u

10、)sim(t，d) THEN BEGIN （7） N=N - u； （8） N=N d； （9） END （10）END （11）c=class to which the most u N.,2020/6/25,18,KNN的例子,姓名 性別 身高(米) 類別 Kristina 女 1.6 矮 Jim 男 2 高 Maggie 女 1.83 高 Martha 女 1.88 高 Stephanie 女 1.7 矮 Bob 男 1.85 中等 Kathy 女 1.6 矮 Dave 男 1.7 矮 Worth 男 2.2 高 Steven 男 2.1 高 Debbie 女 1.8 高 Todd 男

11、1.82 中等 Kim 女 1.7 中等 Amy 女 1.75 中等 Wynette 女 1.73 中等,只使用身高做特征，K=3，對(duì)于樣本應(yīng)屬于哪個(gè)類別？ 僅使用同性別樣本做訓(xùn)練，K=3，對(duì)于樣本應(yīng)屬于哪個(gè)類別？,2020/6/25,19,第三章 分類方法 內(nèi)容提要,分類的基本概念與步驟 基于距離的分類算法 決策樹分類方法 貝葉斯分類 實(shí)值預(yù)測(cè) 與分類有關(guān)的問(wèn)題,2020/6/25,20,決策樹表示與例子,年齡？,學(xué)生？,是,信用？,40,否,是,良好,一般,是,否,是,否,2020/6/25,21,決策樹表示與例子,決策樹（Decision Tree）的每個(gè)內(nèi)部結(jié)點(diǎn)表示一個(gè)屬性（特征），每

12、個(gè)分枝代表一個(gè)特征的一個(gè)（類）取值； 每個(gè)樹葉結(jié)點(diǎn)代表類或類分布。 決策樹分類方法采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點(diǎn)進(jìn)行屬性的比較，從而判斷從該結(jié)點(diǎn)向下的分枝，在決策樹的葉結(jié)點(diǎn)得到結(jié)論。 從決策樹的根到葉結(jié)點(diǎn)的一條路徑就對(duì)應(yīng)著一條規(guī)則，整棵決策樹就對(duì)應(yīng)著一組規(guī)則。 決策樹分類模型的建立通常分為兩個(gè)步驟： 決策樹生成 決策樹修剪,2020/6/25,22,決策樹生成算法描述,算法 4-3 Generate_decision_tree(samples, attribute_list) /*決策樹生成算法*/ 輸入：訓(xùn)練樣本samples，由離散值屬性表示；輸出：一棵決策樹。 （1） 創(chuàng)建結(jié)

13、點(diǎn)N； （2） IF samples 都在同一個(gè)類C THEN 返回N 作為葉結(jié)點(diǎn)，以類 C標(biāo)記； （3） IF attribute_list為空 THEN 返回N作為葉結(jié)點(diǎn)，標(biāo)記為samples中最普通的類；/多數(shù)表決 （4） 選擇attribute_list中具有最高信息增益的屬性test_attribute； （5） 標(biāo)記結(jié)點(diǎn)N為test_attribute； （6） FOR test_attribute的每個(gè)取值ai 由結(jié)點(diǎn)N長(zhǎng)出一個(gè)條件為test_attribute=ai的分枝； （7）設(shè)si是samples 中test_attribute =ai的樣本的集合；/一個(gè)劃分 （8）IF

14、 si 為空 THEN 回退到test_attribute的其它取值； （9）ELSE 加上一個(gè)由Generate_decision_tree(si， attribute_list-test_attribute)返回的結(jié)點(diǎn)；,2020/6/25,23,決策樹修剪算法,基本的決策樹構(gòu)造算法沒有考慮噪聲，因此生成的決策樹完全與訓(xùn)練集擬合。在有噪聲情況下，將導(dǎo)致過(guò)分?jǐn)M合（Overfitting），即對(duì)訓(xùn)練數(shù)據(jù)的完全擬合反而使對(duì)現(xiàn)實(shí)數(shù)據(jù)的分類預(yù)測(cè)性能下降。 比如每個(gè)樣本都是一個(gè)葉子節(jié)點(diǎn)。 現(xiàn)實(shí)世界的數(shù)據(jù)一般不可能是完美的，可能缺值（Missing Values）；數(shù)據(jù)不完整；含有噪聲甚至是錯(cuò)誤的。 剪

15、枝是一種克服噪聲的基本技術(shù)，同時(shí)它也能使樹得到簡(jiǎn)化而變得更容易理解。有兩種基本的剪枝策略。,2020/6/25,24,決策樹修剪算法,預(yù)先剪枝（Pre-Pruning）：在生成樹的同時(shí)決定是繼續(xù)對(duì)不純的訓(xùn)練子集進(jìn)行劃分還是停機(jī)。 后剪枝（Post-Pruning）：是一種擬合+化簡(jiǎn)（fitting-and-simplifying）的兩階段方法。首先生成與訓(xùn)練數(shù)據(jù)完全擬合的一棵決策樹，然后從樹的葉子開始剪枝，逐步向根的方向剪。剪枝時(shí)要用到一個(gè)測(cè)試數(shù)據(jù)集合（Tuning Set或Adjusting Set），如果存在某個(gè)葉子剪去后能使得在測(cè)試集上的準(zhǔn)確度或其他測(cè)度不降低（不變得更壞），則剪去該葉子

16、；否則停機(jī)。理論上講，后剪枝好于預(yù)先剪枝，但計(jì)算復(fù)雜度大。,2020/6/25,25,決策樹修剪算法,構(gòu)造好的決策樹的關(guān)鍵在于如何選擇屬性進(jìn)行樹的拓展。研究結(jié)果表明，一般情況下,樹越小則樹的預(yù)測(cè)能力越強(qiáng)。由于構(gòu)造最小的樹是NP-難問(wèn)題，因此只能采取用啟發(fā)式策略來(lái)進(jìn)行。 屬性選擇依賴于各種對(duì)例子子集的不純度（Impurity）度量方法，包括信息增益（Informatin Gain）、信息增益比（Gain Ratio）、Gini-index、距離度量（Distance Measure）、J-measure等。,2020/6/25,26,ID3算法,ID3是一個(gè)著名決策樹生成方法： 決策樹中每一個(gè)非

17、葉結(jié)點(diǎn)對(duì)應(yīng)著一個(gè)非類別屬性(特征)，樹枝代表這個(gè)屬性的值。一個(gè)葉結(jié)點(diǎn)代表從樹根到葉結(jié)點(diǎn)之間的路徑對(duì)應(yīng)的記錄所屬的類別屬性值。 每一個(gè)非葉結(jié)點(diǎn)都將與屬性中具有最大信息量的非類別屬性相關(guān)聯(lián)。 采用信息增益來(lái)選擇能夠最好地將樣本分類的屬性。 對(duì)ID3算法采用如下方式講解： 給出信息增益對(duì)應(yīng)的計(jì)算公式； 通過(guò)一個(gè)例子來(lái)說(shuō)明它的主要過(guò)程。,2020/6/25,27,信息增益的計(jì)算,設(shè)S是s個(gè)數(shù)據(jù)樣本的集合，定義m個(gè)不同類Ci（i=1，2，m），設(shè)si是Ci類中的樣本的數(shù)量。對(duì)給定的樣本S所期望的信息值由下式給出： 其中pi是任意樣本屬于Ci的概率： si / s 。 例題：數(shù)據(jù)集有4個(gè)類，分別有8個(gè)，4

18、個(gè)，2個(gè)，2個(gè)樣本，求該數(shù)據(jù)集的信息值。 問(wèn)題：信息值的取值范圍是什么？,2020/6/25,28,信息增益的計(jì)算,例題：數(shù)據(jù)集有2個(gè)類，求該數(shù)據(jù)集的信息值。,2020/6/25,29,信息增益的計(jì)算,設(shè)屬性A具有個(gè)不同值a1, a2, , av ，可以用屬性A將樣本S劃分為 S1, S2, , Sv ，設(shè)Sij 是Sj中Ci類的樣本數(shù)，則由A劃分成子集的熵由下式給出： 有A進(jìn)行分枝將獲得的信息增益可以由下面的公式得到：,使用屬性 后的信息值,未使用屬性 的信息值,2020/6/25,30,信息增益的計(jì)算,例題：數(shù)據(jù)集有2個(gè)類。 使用是否學(xué)生作為屬性，求該屬性的信息增益。 使用信用狀況作為屬性

19、，求該屬性的信息增益。,2020/6/25,31,ID3算法的例子,選擇信息增益最大的屬性特征作為根節(jié)點(diǎn)。 Gain(年齡)=0.342 Gain(收入)=0 Gain(是否學(xué)生)=0.333 Gain(信用狀況)=0,年齡？,？,？,是,40,2020/6/25,32,ID3算法的例子,對(duì)于 P(Cj|X)，對(duì)任意的j=1，2，m，ji。,2020/6/25,48,樸素貝葉斯分類(續(xù)),根據(jù)貝葉斯定理： 由于P(X)對(duì)于所有類為常數(shù)，只需要P(X|Ci)*P(Ci)最大即可。 注意，類的先驗(yàn)概率可以用P(Ci)=Si/S計(jì)算，其中Si是類Ci中的訓(xùn)練樣本數(shù)，而S是訓(xùn)練樣本總數(shù)。 因此問(wèn)題就轉(zhuǎn)

20、換為計(jì)算P(X|Ci)。,2020/6/25,49,樸素貝葉斯分類(續(xù)),給定具有許多屬性的數(shù)據(jù)集，計(jì)算P(X|Ci)的計(jì)算量可能非常大且不易計(jì)算。為降低計(jì)算P(X|Ci)的難度，可以做類條件獨(dú)立的樸素假定。給定樣本的類標(biāo)號(hào)，假定屬性值相互條件獨(dú)立，即在屬性間，不存在依賴關(guān)系。這樣 P(收入低,是學(xué)生, 信用良好|買電腦)= P(收入低|買電腦)*P(是學(xué)生|買電腦)*P(信用良好|買電腦),2020/6/25,50,樸素貝葉斯分類(續(xù)),其中概率P(x1|Ci)，P(x2|Ci)，P(xn|Ci)可以由訓(xùn)練樣本估值。 如果Ak是離散屬性，則P(xk|Ci)=sik|si，其中sik是在屬性A

21、k上具有值xk的類Ci的訓(xùn)練樣本數(shù)，而si是Ci中的訓(xùn)練樣本數(shù)。 如果Ak是連續(xù)值屬性，則通常假定該屬性服從高斯分布。因而， 是高斯分布函數(shù)， 而分別為平均值和標(biāo)準(zhǔn)差。,2020/6/25,51,樸素貝葉斯分類(續(xù)),例題：計(jì)算 P(收入低|不買電腦) P(是學(xué)生|不買電腦) P(信用良好|不買電腦) 假設(shè) 收入，是否學(xué)生，信用狀況互相獨(dú)立，計(jì)算 P(收入低，是學(xué)生，信用良好|不買電腦),2020/6/25,52,樸素貝葉斯分類(續(xù)),對(duì)未知樣本X分類，也就是對(duì)每個(gè)類Ci，計(jì)算P(X|Ci)*P(Ci)。樣本X被指派到類Ci，當(dāng)且僅當(dāng)P(Ci|X) P(Cj|X)，1jm，ji，換言之，X被指

22、派到其P(X|Ci)*P(Ci)最大的類。,2020/6/25,53,樸素貝葉斯分類舉例,數(shù)據(jù)樣本有屬性年齡，收入，是否學(xué)生和信用狀況。類標(biāo)號(hào)屬性”是否買電腦“有兩個(gè)不同值是，否。設(shè)C1對(duì)應(yīng)于類”買電腦”；則C2對(duì)應(yīng)于類”不買電腦”。 我們希望分類的未知樣本為: X=（”年齡=30”，”收入=中”，”是學(xué)生”，”信用一般”）,2020/6/25,54,樸素貝葉斯分類舉例,我們需要最大化P(X|Ci)*P(Ci)，i=1，2。 每個(gè)類的先驗(yàn)概率P(Ci)可以根據(jù)訓(xùn)練樣本計(jì)算： P(C1)=P(買電腦）= P(C2)=P(不買電腦）= 計(jì)算P(X|Ci) P（年齡=30,收入=中,是學(xué)生,信用一般

23、|買電腦) P（年齡=30,收入=中,是學(xué)生,信用一般|不買電腦),2020/6/25,55,樸素貝葉斯分類舉例,P（年齡=30,收入=中,是學(xué)生,信用一般|買電腦)= P（年齡=30|買電腦)* P（收入=中|買電腦)* P（是學(xué)生|買電腦)* P（信用一般|買電腦) P（年齡=30,收入=中,是學(xué)生,信用一般|不買電腦)= P（年齡=30|不買電腦)* P（收入=中|不買電腦)* P（是學(xué)生|不買電腦)* P（信用一般|不買電腦),2020/6/25,56,樸素貝葉斯分類舉例,假設(shè)屬性之間獨(dú)立 P（年齡P（X|不買電腦)，因此對(duì)于樣本X，樸素貝葉斯分類預(yù)測(cè)為是。,2020/6/25,57,

24、第三章 分類方法 內(nèi)容提要,分類的基本概念與步驟 基于距離的分類算法 決策樹分類方法 貝葉斯分類 基于規(guī)則的分類 與分類有關(guān)的問(wèn)題,2020/6/25,58,使用IF-THEN規(guī)則分類,使用規(guī)則的分類法是使用一組IF-THEN規(guī)則進(jìn)行分類。 IF 條件 THEN 結(jié)論 比如 IF (年齡20 AND 學(xué)生=是) THEN買電腦=是 IF的部分稱為前提，THEN的部分稱為規(guī)則的結(jié)論 規(guī)則可以用它的覆蓋率和準(zhǔn)確率來(lái)評(píng)價(jià) ncovers是條件(前提)覆蓋的樣本數(shù)，ncorrect是規(guī)則正確分類的樣本數(shù)。,2020/6/25,59,使用IF-THEN規(guī)則分類,規(guī)則(收入=低)(信用狀況良好)(是否買電

25、腦=是)的覆蓋率為3/8,而它測(cè)準(zhǔn)確率為1/3。 規(guī)則(信用狀況=良好)(是否買電腦=否)的覆蓋率為7/8,而它測(cè)準(zhǔn)確率為4/7。,2020/6/25,60,使用IF-THEN規(guī)則分類,如果一個(gè)規(guī)則R被一個(gè)樣本X滿足，則稱規(guī)則R被X觸發(fā)。 比如X =(年齡=18，是學(xué)生，信用良好) R為 IF(年齡20 AND 學(xué)生=是) THEN買電腦=是 則X的類別為 買電腦 如果一個(gè)樣本X同時(shí)觸發(fā)了多個(gè)規(guī)則，我們需要制定解決沖突的策略。 規(guī)模序 激活具有最多屬性測(cè)試的觸發(fā)規(guī)則 規(guī)則序 將規(guī)則按重要性進(jìn)行排序，按順序進(jìn)行促發(fā) 如果一個(gè)樣本X無(wú)法促發(fā)任何規(guī)則 建立一個(gè)缺省或者默認(rèn)規(guī)則,2020/6/25,6

26、1,使用決策樹來(lái)提取規(guī)則,決策樹的規(guī)則是互斥與窮舉的 互斥意味著規(guī)則不會(huì)存在沖突，因此每個(gè)樣本只能促發(fā)一個(gè)規(guī)則 窮舉意味著一個(gè)樣本總能促發(fā)一個(gè)規(guī)則 由于每個(gè)樹葉對(duì)應(yīng)一個(gè)一條規(guī)則，提取的規(guī)則并不比決策樹簡(jiǎn)單。,年齡？,信用狀況？,收入？,是,40,否,是,是,否,良好,一般,高,低,2020/6/25,62,使用順序覆蓋算法的規(guī)則歸納,在提取規(guī)則時(shí)，一個(gè)現(xiàn)實(shí)的問(wèn)題是是否需要對(duì)現(xiàn)有規(guī)則進(jìn)行拓展， IF (年齡20) THEN買電腦 是否需要拓展為 IF (年齡。 AQR允許測(cè)試做=，。Selectors的合取被稱為復(fù)合（Complex），Complexes之間的析取被稱為覆蓋（Cover）。如果一

27、個(gè)表達(dá)式對(duì)某個(gè)樣本為真，則我們稱其為對(duì)這個(gè)樣本的一個(gè)覆蓋。這樣，一個(gè)空Complex覆蓋所有的樣本，而一個(gè)空Cover不覆蓋任何樣本。 在AQR中，一個(gè)新樣本被區(qū)分是看其屬于哪個(gè)推導(dǎo)出來(lái)的規(guī)則。如果該樣本只滿足一條規(guī)則，則這個(gè)樣本就屬于這條規(guī)則；如果該樣本滿足多條規(guī)則，則被這些規(guī)則所預(yù)測(cè)的最頻繁的分類被賦予這條規(guī)則；如果該樣本不屬于任何規(guī)則，則其分類為樣本集中最頻繁的分類。,2020/6/25,85,AQR算法描述,算法 4-5 AQR 輸入：正例樣本POS； 反例樣本NEG。 輸出：覆蓋COVER。 （1） COVER= ；/初始化COVER為空集 （2） WHILE COVER does

28、not cover all positive examples in POS DO BEGIN （3） Select a SEED；/選取一個(gè)種子SEED，例如沒有被COVER覆蓋的一個(gè)正樣例 （4） Call procedure STAR（SEED，NEG）； /產(chǎn)生一個(gè)能覆蓋種子而同時(shí)排除所有反例的星 （5） Select the best Complex BEST from the STAR according to user-defined criteria； /*從星中選取一個(gè)最好的復(fù)合*/ （6） Add BEST as an extra disjuct to COVER /*把最

29、好的復(fù)合與COVER合取，形成新的COVER*/ （7） END （8） RETURN COVER. 在算法AQR中調(diào)用了過(guò)程STAR，來(lái)排除所有的反例，產(chǎn)生覆蓋種子的星。,2020/6/25,86,AQR算法描述(續(xù)),算法 4-6 STAR 輸入：種子SEED；反例NEG。 輸出：星STAR。 （1）初始化STAR為空Complex （2）WHILE one or more Complexes in STAR covers some negative examples in NEG BEGIN /*如果STAR中的一個(gè)或多個(gè)Complex覆蓋NEG中的負(fù)樣例*/ （3）Select a n

30、egative example Eneg covered by a Complex in STAR；/*選取一個(gè)被STAR中的Complex覆蓋的負(fù)樣例*/ （4）Let EXTENSION be all Selectors that cover SEED but not ENEG；/*令EXTENSION為那些覆蓋SEED但不覆蓋ENEG的Selectors；*/ （5）Let STAR be the set xy|xSTAR，yEXTENSION； /*令STAR= xy|xSTAR，yEXTENSION；*/ （6） Remove all Complexes in STAR subsum

31、ed by other Complexes in STAR；/*從STAR中除去被其他Complexes所包含的Complexes；*/ （7）Remove the worst Complexes from STAR UNTIL size of STAR is less than or equal to user-defined maximum （maxstar）/*刪除STAR中最壞的Complex直到STAR的大小等于或小于用戶定義的最大數(shù)目maxstar*/ （8）END （9）RETURN STAR. /*返回一系列覆蓋SEED但不覆蓋NEG的規(guī)則*/,2020/6/25,87,AQR

32、算法舉例,假設(shè)現(xiàn)有一個(gè)訓(xùn)練集，其包含兩種屬性： size （屬性值：micro，tiny，mid，big，huge，vast） type （屬性值：bicycle，motorcycle，car，prop，jet，glider） 現(xiàn)有正例、反例樣本分別如表4-6，表4-7所示：,下面給出用AQR算法對(duì)giant 2-wheeler類的規(guī)則進(jìn)行獲取過(guò)程，具體步驟如下： （）COVER=。 （）空cover不覆蓋任何樣本，進(jìn)入循環(huán)。 （）一開始COVER并沒有覆蓋任何正例，假定從正例中選取的SEED 為 size=huge，type =bicycle 。 （）調(diào)用STAR（SEED，NEG）去產(chǎn)生一

33、個(gè)覆蓋SEED但不包含NEG的STAR集合； 初始化STAR為空，即STAR=。 空的complex覆蓋所有樣例，STAR覆蓋多個(gè)負(fù)樣例，進(jìn)入循環(huán)。 a ) 選取一個(gè)被STAR中的復(fù)合覆蓋的負(fù)樣例ENEG，假定被選取的是 Eneg= size= tiny， type = motorcycle 。 b ) 使EXTENSION為所有覆蓋SEED但不覆蓋ENEG的選擇，則EXTENSION包括size= huge和type =bicycle，則又根據(jù)STAR=xy|xSTAR，yEXTENSION，因此，STAR= size=hugetype =bicycle 。 c ) 在這里定義maxstar

34、為2，可不對(duì)STAR進(jìn)行精簡(jiǎn)。 d ) 接著選取另一個(gè)被STAR中的復(fù)合覆蓋的負(fù)樣例ENEG，顯然已經(jīng)沒有這樣的負(fù)樣例，因此，STAR= size=hugetype =bicycle 。 從STAR（SEED，NEG）返回。,反例樣本 size type class Tiny motorcycle conventional transportation tiny car conventional transportation mid car conventional transportation micro jetfast plane Tiny jetfast plane Mid jetfas

35、t plane,正例樣本 size type class Huge bicycle giant 2-wheeler Huge motorcycle giant 2-wheeler,2020/6/25,88,AQR算法舉例,（5）BEST= size=hugetype =bicycle ，COVER = size=hugetype =bicycle 。 （6）顯然COVER不能覆蓋所有的正例，從正例中選取另一個(gè)SEED= size=huge，type = motorcycle。 （7）調(diào)用STAR（SEED，NEG）去產(chǎn)生一個(gè)覆蓋SEED但不包含NEG的STAR集合。 初始化STAR為空，即ST

36、AR=； 空的complex覆蓋所有樣例， 所以STAR覆蓋負(fù)樣例，進(jìn)入循環(huán)； a ) 假定被選取的是Eneg= size= tiny， type = motorcycle ； b ) 使EXTENSION為所有覆蓋SEED但不覆蓋Eneg的選擇，則EXTENSION包括size= huge，則又根據(jù)STAR=xy|xSTAR，yEXTENSION，因此，STAR= size=huge； c ) 接著選取另一個(gè)被STAR中的復(fù)合覆蓋的負(fù)樣例Eneg，顯然已經(jīng)沒有這樣的負(fù)樣例，因此，STAR= size=huge； d ) 接著選取另一個(gè)被STAR中的復(fù)合覆蓋的負(fù)樣例ENEG，顯然已經(jīng)沒有這樣的

37、負(fù)樣例，因此，STAR= size=hugetype =bicycle 。 從STAR（SEED，NEG）返回。 （8）BEST=size=huge，將BEST添加到COVER中，COVER = size=hugetype =bicycle size=huge= size=huge。 （9）這時(shí)，COVER已經(jīng)覆蓋到全部的正例，則算法結(jié)束。輸出規(guī)則為gaint 2-wheeler size=huge。,假設(shè)現(xiàn)有一個(gè)訓(xùn)練集，其包含兩種屬性： size （屬性值：micro，tiny，mid，big，huge，vast） type （屬性值：bicycle，motorcycle，car，prop，

38、jet，glider） 現(xiàn)有正例、反例樣本分別如表4-6，表4-7所示：,反例樣本 size type class Tiny motorcycle conventional transportation tiny car conventional transportation mid car conventional transportation micro jetfast plane Tiny jetfast plane Mid jetfast plane,正例樣本 size type class Huge bicycle giant 2-wheeler Huge motorcycle gi

39、ant 2-wheeler,2020/6/25,89,CN2算法描述,CN2使用一種基于噪音估計(jì)的啟發(fā)式方法，使用這種方法可以不用對(duì)所有的訓(xùn)練樣本進(jìn)行正確的區(qū)分，但是規(guī)約出的規(guī)則在對(duì)新數(shù)據(jù)的處理上有很好的表現(xiàn)。,算法 4-7 CN2 輸入：E /*E為訓(xùn)練樣本*/ 輸出：RULE_LIST /*返回一個(gè)覆蓋若干樣例的規(guī)則*/ （1） Let RULE_LIST be the empty list； /* 初始化RULES_LIST為空；*/ （2） REPEAT （3） Let BEST_CPX be Find_Best_Complex（E）； /*尋找最佳的規(guī)則Find_Best_Compl

40、ex（E）并將其結(jié)果放入BEST_CPX中；*/ （4） IF BEST_CPX is not nil THEN BEGIN （5） Let E be the examples covered by BEST_CPX；/*令E為BEST_CPX覆蓋的所有樣例*/ （6） Remove from E the examples E covered by BEST_CPX； /*從訓(xùn)練樣本E中除去E，即E=E-E；*/ （7） Let C be the most common class of examples in E； /*令C為樣本子集E中最頻繁的分類標(biāo)號(hào)；*/ （8） Add the rul

41、e if BEST_CPX then class=C to the end of RULE_LIST； /*將規(guī)則if BEST_CPX then class=C添加到RULES_LIST中*/ （9） END （10）UNTIL BEST_CPX is nil or E is empty. /*直到BEST_CPX為空或者訓(xùn)練樣本E為空*/ （11）RETURN RULE_LIST 算法CN2需要通過(guò)調(diào)用函數(shù)Find_Best_Complex，它的描述寫成下面算法4-8。,2020/6/25,90,CN2算法描述(續(xù)),算法 4-8 Find_Best_Complex 輸入：E /*E為訓(xùn)練

42、樣本*/ 輸出：BEST_CPX /*返回最佳的規(guī)則BEST_CPX */ （1） Let the set STAR contain only the empty Complex； /*初始化集合STAR為空Complex；*/ （2） Let BEST_CPX be nil； /*初始化BEST_CPX為空*/ （3） Let SELECTORS be the set of all possible Selectors； /*集合SELECTOR為所有可能的選擇*/ （4） WHILE STAR is not empty DO BEGIN （5） Let NEWSTAR be the set

43、 xy|xSTAR，yEXTENSION； /*令NEWSTAR= xy|xSTAR，yEXTENSION；*/ （6） Remove all Complexes in NEWSTAR that are either in STAR or are null； /*從NEWSTAR中除去包括在STAR中的Complex或者為空的Complex*/ （7） FOR every complex Ci in NEWSTAR （8） IF Ci is statistically significant when tested on E and better than BEST_CPX according

44、 to user-defined criteria when tested on E /*如果Ci在統(tǒng)計(jì)上有意義， 并且對(duì)訓(xùn)練集E測(cè)試后符合用戶定義的條件且優(yōu)于BEST_CPX*/ （9） THEN replace the current value of BEST_CPX by Ci； /*將BEST_CPX替換為Ci*/ （10） REPEAT remove worst Complexes from NEWSTAR （11） UNTIL size of NEWSTAR is = user-defined maximum maxstar； /*逐步移去在NEWSTAR中最壞的complex直

45、到NEWSTAR的大小等于或小于用戶 定義的最大數(shù)目maxstar*/ （12） Let STAR be NEWSTAR； /*令STAR=NEWSTAR*/ （13）END （14）RETURN BEST_CPX。/*返回BEST_CPX*/,2020/6/25,91,FOIL算法,FOIL學(xué)習(xí)系統(tǒng)已經(jīng)被廣泛地應(yīng)用在邏輯規(guī)約領(lǐng)域。FOIL是用來(lái)對(duì)無(wú)約束的一階Horn子句進(jìn)行學(xué)習(xí)。一個(gè)概念的定義是由一系列的子句組成，而其中每一個(gè)子句描述了一種證明一個(gè)樣本是這個(gè)概念的實(shí)例的唯一方法。每個(gè)子句由一些文字的析取組成。 FOIL由一系列的外部定義的斷言開始，其中之一被確定為當(dāng)前學(xué)習(xí)的概念，而其他作為背

46、景文字。FOIL從這些外部定義的斷言中獲取一系列包括文字的子句。 FOIL算法由一個(gè)空子句開始查找，其不斷的向當(dāng)前的子句中追加文字直到?jīng)]有負(fù)樣例被子句所覆蓋。之后，F(xiàn)OIL重新開始一個(gè)子句的查找，直到所有的正樣例均被已經(jīng)生成的子句所覆蓋。FOIL計(jì)算每一個(gè)外部定義斷言的信息熵（Information Gain）和合法的變量（Legal Variabilization）用來(lái)決定哪一個(gè)文字添加到子句中。,2020/6/25,92,一階Horn子句的主要術(shù)語(yǔ),一階Horn子句所涉及的主要術(shù)語(yǔ)有： 所有表達(dá)式由常量（如Mary、23或Joe）、變量（如x）、謂詞（如在Female（Mary）中的Fem

47、ale和函數(shù)（如在age（Mary）中的age）組成； 項(xiàng)（Term）為任意常量、任意變量或任意應(yīng)用到項(xiàng)集合上的函數(shù)。例如，Mary，x，age（Mary），age（x）； 文字（Literal）是應(yīng)用到項(xiàng)集合上的任意謂詞或其否定。例如，F(xiàn)emale（Mary），Greater_than（age（Mary），20）； 基本文字（Ground Literal）是不包括任何變量的文字； 負(fù)文字（Negative Literal）是包括否定謂詞的文字； 正文字（Positive Literal）是不包括否定謂詞的文字； 子句（Clause）是多個(gè)文字的析取式，M1Mn，其中所有變量是全程量化的；,2020/6/25,93,一階Horn子句的表達(dá),Horn子句是一個(gè)如下形式的表達(dá)式： H(L1Ln）。 其中，H，L1，L2，Ln為正文字。H被稱為Horn子句的頭（Head）或推論（Consequent）。文字合取式L1L2.Ln被稱為Horn子句的體（Body）或者先行詞（Antecedents）。 置換（Substitution）是一個(gè)將某些變量替換為某些項(xiàng)的函數(shù)。例如，置換x/3，y/z把變量x替換為項(xiàng)3并且把變量y替換為項(xiàng)z。給定一個(gè)置換和一個(gè)文