1、第四章 分類分類任務的輸入數(shù)據(jù)數(shù)記錄的集合。每條記錄也稱實例或者樣例，用元祖（x,y）表示，其中x是屬性的集合，而y是一個特殊的集合，支出樣例的類標號（也稱為分類屬性或者是目標屬性）。屬性主要是離散的，但是屬性也可以包含連續(xù)特征。但是類標號必須是離散屬性，這正是區(qū)分分類與回歸（regression）的關鍵特征?；貧w數(shù)一種預測建模任務，其中目標屬性y是連續(xù)的。分類（calssification）分類的任務就是通過學習得到一個目標函數(shù)（target function）f，把每個屬性集x映射到一個預先定義的類標號y。目標函數(shù)也稱分類模型（classification）。描述性建模 分類模型可以作為解

2、釋性的工具，用于區(qū)分不同類中的對象預測性建模 分類 模型還可以用于未知記錄的類標號。分類技術非常適合預測或者描述二元或標稱類型的數(shù)據(jù)集，對于敘述分類（如把人類分為高收入、中收入低收入組），分類技術不太有效，因為分類技術不考慮隱含在目標類中的序關系。如子類與超類的關系（例如，人類和猿都是靈長類的動物，而靈長類是哺乳類的子類）也被忽略。決策樹歸納決策樹是有一種由節(jié)點和有向邊組成的層次結構。書中包含三種節(jié)點.根節(jié)點(root node)，它沒有入邊，但有零條或多條出邊。內(nèi)部節(jié)點（internal node），恰有一條入邊和兩條或多條出邊。葉節(jié)點（leaf node）或終結點（reminal node

3、），橋由一條入邊和兩條或多條出邊。非哺乳類體溫胎生哺乳動物葉節(jié)點 內(nèi)部節(jié)點冷血恒溫是否非哺乳動物圖 4-4 哺乳動物分類問題決策時 如何建立決策樹Hunt算法在Hunt算法中，通過訓練記錄相機劃分成較純的子集，以遞歸方式建立決策樹。設Dt是與節(jié)點t相關聯(lián)的訓練記錄集，而y=y1y2yc是類標號，Hunt算法的遞歸定義如下：（1） 如果Dt中所有的記錄都屬于同一個類yt，則t是葉節(jié)點，則用yt標記。（2） 如果Dt中包含屬于多個類的記錄，則選擇一個屬性測試條件（attribute test condition），將記錄劃分成較小的子集。對于測試條件的每個輸出，創(chuàng)建一個子女節(jié)點，并根據(jù)測試結果將D

4、t中的記錄分布到子女節(jié)點中，然后，對于每個子女節(jié)點，遞歸的調(diào)用該算法。如果屬性值的每種組合都在訓練數(shù)據(jù)中出現(xiàn)，并且美中組合都有唯一的類標號，則Hunt算法是有效的。但是對于大多數(shù)實際情況，這些假設都太苛刻了。因此徐福佳的條件來處理一下的情況。（1） 算法的第二步所創(chuàng)建的子女節(jié)點可能為空，即不存在與這些相關聯(lián)的記錄。如果沒有一個訓練記錄包含與這樣的節(jié)點相關聯(lián)的屬性值組合，這種情形就肯能發(fā)生，這時該節(jié)點成為一個葉節(jié)點，類標號為其父節(jié)點上訓練記錄中的多數(shù)類。（2） 在第二步，如果與Dt相關聯(lián)的所有記錄都具有相同的屬性值（目標屬性除外），則不可能進一步劃分這些記錄。在這種情況下，該節(jié)點為葉節(jié)點，其標號

5、與該節(jié)點相關聯(lián)的訓練記錄中的多數(shù)類。決策樹歸納的設計問題，決策樹歸納必須解決以下兩個問題：（1）如何分裂訓練記錄？樹增長過程中的每個遞歸步都必須選擇一個屬性測試條件，將記錄劃分成較小的子集。因此算法必須提供為不同類型的屬性指定測試條件的方法，并且提供評估美中測試條件的客觀度量。（2）如何停止分裂過程？終止決策樹生長的過程的兩個策略：分裂節(jié)點，知道所有記錄都屬于同一個類，或者所有記錄都具有相同的屬性值。盡管兩個結束條件對于結束決策樹歸納算法都是充分的，但還是可以提前終止生長。選擇最佳劃分的度量選擇最佳劃分的度量通常是根據(jù)劃分后子女節(jié)點不純性的程度。不純的程度越低，類分布就越傾斜。不純性度量的例子

6、包括： Entropy(t) = -i=0c-1p(i|t)logzp(i|t) Gini(t) = 1-i=0c-1pit2 Classfication error(t) = 1-maxpit其中c是類的個數(shù)，并且在計算熵時，。以上三種方法都是在類均衡時達到最大值，當所有記錄都屬于同一類時，達到最小值。為了確定測試條件的效果，我們需要比較父結點（劃分前）的不純程度和子女結點（劃分后）的不純程度。它們的差越大，測試條件的效果就越好，帶來的增益定義如下：其中，I(.)是給定結點的不純性度量，N是父結點上的記錄總數(shù)，k是屬性值的個數(shù)。是與子女結點相關聯(lián)的記錄的個數(shù)。對于所有的測試條件來說，I(pa

7、rent)是一個不變值，所以最大化增益等價于最小化子女結點的不純性度量的加權平均。當選擇熵作為不純性度量時，熵的差就是所謂信息增益（information gain）。二元屬性劃分：以下表為例計算。父結點C06C16Gini=0.5分類AN1N2C042C133Gini=0.486分類BN1N2C015C142Gini=0.371Gini(A)=(7/12)*Gini(N1)+(5/12)*Gini(N2)Gini(B)=(5/12)*Gini(N1)+(7/12)*Gini(N2)Gini(N1)和Gini(N2)由2.4中的第二個公式計算標稱屬性的劃分：與二元劃分類似，只不過多計算一些結點

8、而已。一般來說，多路劃分的Gini指標比二元劃分都小，因為二元劃分實際上合并了多路劃分的某些輸出，自然降低了自己的純度。連續(xù)屬性的劃分：總體思路是把連續(xù)屬性劃分為若干個區(qū)間，在套用1、2中的思路。但在這之前，如果先對訓練記錄按照分類屬性進行排序，能夠把時間復雜度從降低至。其他還有一些可以考慮的優(yōu)化方案：如僅考慮位于具有不同類標號的兩個相鄰記錄之間的候選劃分點。增益率熵和Gini指標等不純性度量趨向有利于具有大量不同值得屬性。這樣，即使在不太極端情形下，也不會希望產(chǎn)生大量輸出的測試條件，因為與每個劃分相關聯(lián)的記錄太少，以致不能做出可靠的預測。解決該問題的策略有兩種。第一種是限制測試條件只能是二元

9、劃分（CART），另一種策略是修改評估劃分的標準，把屬性測試條件產(chǎn)生的輸出數(shù)也考慮進去。如，C4.5的增益率（gain ratio）定義如下：其中，劃分信息，而k是劃分的總數(shù)。決策樹歸納算法首先，給出下表算法稱作TreeGrowth的決策樹歸納算法的框架。該算法的輸入是訓練記錄集E和屬性集F。算法遞歸地選擇最優(yōu)的屬性來劃分數(shù)據(jù)（步驟7），并擴充樹的葉結點（步驟11和步驟12），知道滿足結束條件（步驟1）。算法 決策樹歸納算法的框架TreeGrowth(E,F)1: if stopping_cond(E,F)=true then2: leaf=createNode()3: leaf. label

10、=Classify(E)4: return leaf5: else6: root=createNode()7: root. test_cond=find_best_split(E,F)8: 令V=v | v是root. test_cond的一個可能的輸出9: for 每個vV do10: = e| root. test_cond(e)=v, 并且eE11: child=TreeGrowth(,F)12: 將child作為root的派生結點添加到樹中，并將邊(root-child)標記為v13: end for14: end if15: return root以上算法的細節(jié)如下：1. 函數(shù)cre

11、ateNode()為決策樹建立新的結點。決策樹的結點或一個測試條件，記作node. test_cond，或者是一個類標號，記作node. Label。2. 函數(shù)find_best_split()確定應當選擇哪個屬性作為劃分訓練記錄的測試條件。3. 函數(shù)Classify()為葉結點確定類標號，對于每個葉結點t，令p( i | t)表示該節(jié)點上屬于類i的訓練記錄所占的比例，在大多數(shù)情況下，都將葉結點指派到具有多數(shù)記錄的類：其中，操作argmax返回最大化p(i|t)的參數(shù)值。P(i|t)還可用來估計分配到葉結點t的記錄屬于類i的概率。4. 函數(shù)stopping_cond()通過檢查是否所有的記錄都

12、屬于同一個類，或者都具有相同的屬性值，決定是否終止決策樹的增長。終止函數(shù)的另一種方法是，檢查記錄數(shù)是否小于某個最小閾值。建立決策樹后，可以進行樹剪枝（tree-pruning），以減小決策樹的規(guī)模。決策樹過大容易造成過分擬合（overfitting）。算法特點下面是對決策樹歸納算法重要特點的總結。1. 決策樹歸納是一種構建分類模型的非參數(shù)方法。它不需要任何先驗假設，不假定類和其他屬性服從一定的概率分布。2. 找到最佳的決策樹是NP完全問題。3. 已開發(fā)的構建決策樹技術不需要昂貴的計算代價。決策樹一旦建立，未知樣本的分類非常快，最壞情況的時間復雜度O(w)，其中w是數(shù)的最大深度。4. 決策樹相對

13、容易解釋。5. 決策樹是學習離散值函數(shù)的典型代表。但是，它不能很好的推廣到某些特定的布爾問題。6. 決策樹算法對于噪聲的具有很好的健壯性（魯棒性），采用避免過分擬合的方法之后尤其如此。7. 冗余屬性不會對決策樹的準確率造成不利影響。然而，數(shù)據(jù)集中的不相關屬性會對其造成影響。8. 可能造成數(shù)據(jù)碎片問題（data fragmentation）。9. 子樹可能在決策樹中重復多次。10. 決策邊界（decision boundary，兩個不同類的相鄰區(qū)域之間的邊界稱作決策邊界）可能不平行于x, y軸。此時，就會涉及到斜決策樹（oblique decision tree）和構造歸納（constructi

14、ve induction，書2.3.5節(jié)，會產(chǎn)生冗余屬性）的相關問題。11. 不純性度量方法的選擇對決策樹算法的性能影響很小。模型的過擬合分類模型的誤差大致分為兩種：訓練誤差（training error）和泛化誤差（generalization error）。一般來說，訓練誤差隨模型的復雜度增加而降低，泛化誤差與之相反。過擬合現(xiàn)象：模型過于追求對訓練記錄的擬合程度而失去了對未知數(shù)據(jù)的預測和泛化能力。反之，如果訓練集很小，則可能造成擬合補足的現(xiàn)象。造成過擬合的原因噪聲導致的過分擬合：由于某些離群點和特殊的訓練記錄導致的模型復雜度增加，從而導致模型的泛化能力和預測能力下降。缺乏代表性樣本導致的過

15、分擬合：根據(jù)少量訓練記錄做出分類決策的模型也容易受過分擬合的影響。由于訓練數(shù)據(jù)缺乏具有代表性的樣本，在沒有多少訓練記錄的情況下，學習算法仍然繼續(xù)細化模型就會產(chǎn)生這樣的模型。多重比較（multiple comparison procedure）過程的學習算法導致的過分擬合：設是初始決策樹，是插入屬性x的內(nèi)部結點后的決策樹。原則上，如果觀察到的增益(，)大于某個預先定義的閾值，就可以將x添加到樹中。如果只有一個屬性測試條件，則可以通過足夠大的閾值來避免插入錯誤的結點。然而，在實踐中，可用的屬性終止測試條件不止一個，并且決策樹算法必須從候選集中選擇最佳屬性來劃分數(shù)據(jù)。在這種情況下，算法實際上是使用多

16、重比較過程來決定是否需要擴展決策樹。更具體地說，這是測試(，)，而不是測試(，)。隨著候選個數(shù)k的增加，找到(，)的幾率也在增加。除非根據(jù)k修改增益函數(shù)或閾值，否則算法會不經(jīng)意間在模型上增加一些欺騙性的結點，導致模型過分擬合。大量的候選屬性和少量的訓練記錄最后可能導致模型的過分擬合。泛化誤差估計1. 再代入估計再代入估計方法假設訓練數(shù)據(jù)集可以很好地代表整體數(shù)據(jù)，因而，可以使用訓練誤差（又稱再代入誤差）提供對泛化誤差的樂觀估計。但是，訓練誤差通常是泛化誤差的一種很差的估計。2. 結合模型復雜度估計一般來說，模型越是復雜，出現(xiàn)先過擬合的幾率就越高。這種策略與應用眾所周知的奧卡姆剃刀（Occams

17、razor）或節(jié)儉原則（principle of parsimony）一致。奧卡姆剃刀：給定兩個具有相同泛化誤差的模型，較簡單的模型比較復雜的模型更可取。悲觀誤差評估：第一種方法明確使用訓練誤差與模型復雜度罰項（penalty term）的和計算泛化誤差。結果泛化誤差可以看作模型的悲觀誤差估計（pessimistic error estimate）。例如，設n(t)是結點t分類的訓練記錄數(shù)，e(t)是被誤分類的記錄數(shù)。決策樹T的悲觀誤差估計可以用下式計算：其中，k是決策樹的結點數(shù)，e(T)是決策樹的總訓練誤差，是訓練記錄數(shù)，是每個結點對應的罰項。最小描述長度原則：另一種結合模型復雜度的方法是基

18、于稱作最小描述長度（minimum description length, MDL）原則的信息論方法。為了解釋說明該原則，考慮下圖中的例子。在該例中，A和B都是已知屬性x值得給定記錄集。另外，A知道每個記錄的確切類標號，而B卻不知道這些信息。B可以通過要求A順序傳送類標號而獲得每個記錄的分類。一條消息需要(n)比特的信息，其中n是記錄總數(shù)。另一種可能，A決定建立一個分類模型，概括x和y之間的關系。在傳遞給B前，模型用壓縮形式編碼。如果模型的準確率是100%，那么傳輸?shù)拇鷥r就等于模型編碼的代價。否則，A還必須傳輸哪些數(shù)據(jù)被模型錯誤分類信息。傳輸?shù)目偞鷥r是：其中，等式右邊的第一項是模型編碼的開銷，

19、而第二項是誤分類記錄編碼的開銷。根據(jù)MDL原則，我們尋找最小化開銷函數(shù)的模型。3. 估計統(tǒng)計上界泛化誤差也可以用訓練誤差的統(tǒng)計修正來估計。因為泛化誤差傾向于比訓練誤差大，所以統(tǒng)計修正通常是計算訓練誤差的上界。具體計算和證明會涉及到概率論和數(shù)理統(tǒng)計的知識。4. 使用確認集在該方法中，我們把原始的訓練數(shù)據(jù)集分為兩個較小的子集，一個自己用于訓練，而另一個稱作確認集，用于估計泛化誤差。該方法通常用于參數(shù)控制獲得具有不同復雜度模型的分類技術。通過調(diào)整學習算法中的參數(shù)（如決策樹剪枝的程度），直到學習算法產(chǎn)生的模型在確認集上達到最低的錯誤率，可以估計最佳模型的復雜度。雖然該方法為評估模型在未知樣本上的性能提

20、供了較好的辦法，但用于訓練的記錄減少了。處理決策樹中的過擬合先剪枝（提前終止規(guī)則）：樹增長算法在產(chǎn)生完全擬合整個訓練數(shù)據(jù)集的完全增長的決策樹之前就停止決策樹的生長。這種方法的優(yōu)點在于避免產(chǎn)生過分擬合訓練數(shù)據(jù)的過于復雜的子樹，然而，很難為提前終止選取正確的閾值。閾值太高將導致擬合不足的模型，而閾值太低就不能充分地解決過分擬合的問題。此外，即便使用已有的屬性測試條件得不到顯著的增益，接下來的劃分也可能產(chǎn)生較好的子樹。后剪枝：在該方法中，初始決策樹按照最大規(guī)模生長，然后進行剪枝的步驟，按照自底向上的方式修剪完全增長的決策樹。修剪的方法有兩種：1. 用新的葉結點替換子樹，該葉結點的類標號有子樹下記錄中

21、的多數(shù)類決定。2. 用子樹中最常使用的分支代替子樹（常見的有子樹提升（subtree raising）和子樹替換（subtree replacement）。當模型不能改進時，終止剪枝步驟。分類器性能評估和比較分類器性能評估保持方法（holdout）：將被標記的原始數(shù)據(jù)分成兩個不相交的集合，分別稱為訓練集和檢驗集。在訓練數(shù)據(jù)集上歸納分類模型，在檢驗集上評估模型的性能。兩者的比例通常是1:1或1:2。保持方法的局限性：第一，用于訓練的被標記樣本較少；第二，模型可能高度依賴于訓練集和檢驗集的組成；最后，訓練集和檢驗集不再是互相獨立的。因為訓練集和檢驗集源于同一個數(shù)據(jù)集，在一個子集中超出比例的類在另一

22、個子集就低于比例，反之亦然。隨機二次抽樣（random subsampling）：多次重復保持方法來改進對分類器性能的估計，這種方法稱作隨機二次抽樣。設是第i次迭代的模型準確率，總準確率是隨機二次抽樣也會遇到一些與保持方法同樣的問題。交叉驗證（cross-validation）：在方法中，每個記錄用于訓練的次數(shù)相同，并且恰好檢驗一次。K折交叉檢驗定義如下：把數(shù)據(jù)分為大小相同的k份，在每次運行，選擇其中一份作為檢驗集，而其余的作為訓練集，該過程重復k次，使得每份數(shù)據(jù)都用于檢驗恰好一次?？傉`差是所有k次運行的誤差之和。留一（leave-one-out）方法是k折交叉檢驗的特殊情況，即每個檢驗集只有一個記錄。注意：以上三種方法中，訓練記錄采取的都是不放回抽樣。自助法（bootstrap）：自助方法中，訓練記錄采用有放回抽樣。如果原始數(shù)據(jù)有N個記錄，可以證明，平均來說，大小為N的自助樣本大約包含原始數(shù)據(jù)中63.2%的記錄。沒有抽中的記錄成為檢驗集的一部分，將訓練集建立的模型應用到檢驗集上，得到資助樣本準確率的一個估計。抽樣過程重復b次，產(chǎn)生b個自助樣本。按照如何計算分類器的總準確率，有幾種不同的自助抽樣方法。常用的方法之一是.632自助（.632 bootstrap），它通過組合每個自助樣本的準確率（）和由包含所有標記樣本的訓練集計算的準確率（）