帶你讀《資料挖掘導論（原書第2版）》之三：分類：基本概念和技術

點選檢視第一章 點選檢視第二章

第3章 分類：基本概念和技術

人類具有分類事物的天賦，例如過濾垃圾郵件資訊之類的日常任務，或者在望遠鏡圖像中識别天體這類更為特殊的任務（參見圖3.1）。雖然對于隻有少數幾個屬性的小而簡單的資料集，通常通過手動分類就足以解決，但對更大和更複雜的資料集，仍然需要自動化解決方案。

本章介紹了分類的基本概念，并描述了其中的一些關鍵問題，如模型過拟合、模型選擇和模型評估等。雖然使用到了稱為決策樹歸納的分類技術來說明這些主題，但本章中的大部分内容也适用于其他分類技術，第4章會進行介紹。

3.1　基本概念

圖3.2顯示了分類的總體思路。分類任務的資料由一組執行個體（記錄）組成。每個這樣的執行個體都以元組（x，y）為特征，其中x是描述執行個體的屬性值集合，y是執行個體的類别标簽。屬性集x可以包含任何類型的屬性，而類别标簽y必須是可分類的。

分類模型（classification model）是屬性集和類别标簽之間關系的抽象表示。正如在接下來的兩章中将會看到的那樣，該模型可以用許多方式來表示，例如樹、機率表，或簡單地用一個實值參數的向量表示。形式上，我們可以在數學表達上把它作為一個目标函數f，它将輸入屬性集x并産生一個對應于預測類别标簽的輸出。說明如果f（x)=y，則該模型可正确地對執行個體（x，y）進行分類。

表3.1顯示了分類任務的屬性集和類别标簽的各種例子。垃圾郵件過濾和惡性良性腫瘤鑒定是二分類問題的例子，其中每個資料執行個體可以分為兩類之一。如果類的數量大于2，如在星系分類示例中那樣，那麼它被稱為多分類問題。

我們用以下兩個例子來說明分類的基本概念。

例3.1 脊椎動物分類　表3.2顯示了将脊椎動物分為哺乳動物、爬行動物、鳥類、魚類和兩栖動物的樣本資料集。屬性集包括脊椎動物的特征，如體溫、表皮覆寫和飛行能力。該資料集也可用于二分類任務，如哺乳動物分類，可将爬行動物、鳥類、魚類和兩栖類分為一類，稱為非哺乳動物。

例3.2 貸款借款人分類　預測貸款人是否可以償還貸款或拖欠貸款的問題。表3.3展示了用于建立分類模型的資料集。屬性集包括借款人的個人資訊，如婚姻狀況和年收入，而類别标簽則表明借款人是否拖欠了貸款。

分類模型在資料挖掘中擔當兩個重要角色。首先，它被用作預測模型（predictive model）來對先前未标記的執行個體進行分類。一個好的分類模型必須以快速的響應時間提供準确的預測。其次，它作為一個描述性模型（descriptive model）來識别區分不同類别執行個體的特征。這對于諸如醫療診斷的關鍵應用特别有用，因為如果無法證明如何做出這樣的決定，就稱不上是一個預測模型。

例如，由表3.2所示的脊椎動物資料集顯示的分類模型可用于預測以下脊椎動物的類别标簽：

此外，它可以用作描述性模型來幫助确定将脊椎動物定義為哺乳動物、爬行動物、鳥類、魚類或兩栖動物的特征。例如，該模型可能會将生育後代的哺乳動物确定為恒溫脊椎動物。

關于前面的例子有幾點值得注意。首先，雖然表3.2中顯示的所有屬性都是定性的，但對于可用作預測變量的屬性類型沒有限制。另一方面，類别标簽必須是标稱類型。這将分類與其他預測模組化任務（如回歸）區分開來，其中預測值通常是定量的。有關回歸的更多資訊可以在附錄D中找到。

另一點值得注意的是，可能并非所有屬性都與分類任務相關。例如，脊椎動物的平均長度或重量可能不适用于哺乳動物分類，116因為這些屬性對于哺乳動物和非哺乳動物都可以展現相同的值。這種屬性通常在預處理期間被丢棄。其餘屬性可能無法自行分類，是以必須與其他屬性一起使用。例如，體溫屬性不足以區分哺乳動物和其他脊椎動物。當它與“胎生”一起使用時，哺乳動物的分類顯著改善。但是，如果包含附加屬性（例如表皮覆寫），則該模型變得過于具體，并且不再涵蓋所有哺乳動物。尋找區分不同類别執行個體的最佳屬性組合是建構最優分類模型的關鍵挑戰。

3.2　一般的分類架構

分類是将标簽配置設定給未标記資料執行個體的任務，分類器用于執行此類任務。分類器（classifier）通常按照上一節所述的模型進行描述。該模型是使用給定的一組執行個體建立的，這組執行個體稱為訓練集（training set），其中包含每個執行個體的屬性值以及類别标簽。學習給定訓練集分類模型的系統化方法稱為學習算法（learning algorithm）。使用學習算法從訓練資料建立分類模型的過程稱為歸納（induction）。這個過程通常也被描述為“學習一個模型”或“建立一個模型”。在未知的測試執行個體上應用分類模型來預測它們的類别标簽的過程稱為演繹（deduction）。是以，分類過程涉及兩個步驟：将學習算法應用于訓練資料以學習模型，然後應用模型将标簽配置設定給未标記的執行個體。圖3.3說明了分類的一般架構。

分類技術（classification technique）是指分類的一般方法，例如将在本章中研究的決策樹技術。像大多數其他分類技術一樣，這種分類技術由一系列相關模型和一些用于學習這些模型的算法組成。在第4章中，我們将研究其他分類技術，包括神經網絡和支援向量機。

對術語的兩點說明。首先，術語“分類器”和“模型”通常被認為是同義詞。理想情況下，分類技術建構單一的全局模型。但是，雖然每個模型都定義了一個分類器，但并不是每個分類器都由一個模型定義。某些分類器（如k-最近鄰分類器）不會建構顯式模型（見4.3節），117而其他分類器（如內建分類器）會合并模型集合的輸出（見4.10節）。其次，術語“分類器”通常用于更一般的含義來表示分類技術。是以，例如，“決策樹分類器”可以指決策樹分類技術或使用該技術建構的特定分類器。幸運的是，“分類器”的含義通常在上下文中較為清晰。

在圖3.3所示的總體架構中，歸納和演繹步驟應該分開進行。事實上，正如将在3.6節中讨論的那樣，訓練集和測試集應該是互相獨立的，以確定歸納模型能夠準确預測以前從未遇到過的執行個體的類别标簽。具有這種預測性見解的模型被稱為具有良好的泛化性能（generalization performance）。模型（分類器）的性能可以通過比較執行個體的預測标簽和真實标簽來評估。這些資訊可以在一個稱為混淆矩陣（confusion matrix）的表格中總結出來。

表3.4描述了二分類問題的混淆矩陣。每個條目fij表示來自第i類的預測為類j的執行個體的數量。118例如，f01是從類0錯誤地預測為類1的執行個體的數量。模型進行的正确預測的數量是（f11+f00）并且不正确預測的數量是（f10+f01）。

盡管混淆矩陣提供了确定分類模型性能的資訊，但将這些資訊彙總為單個資料可以更友善地比較不同模型的相對性能。這可以使用諸如準确率（accuracy）這樣的評估度量（evaluation metric）來完成：

對于二分類問題，模型的準确率由下式給出：

錯誤率（error rate）是另一個相關度量，對于二分類問題，其定義如下：

大多數分類技術的學習算法用于學習獲得測試集最高準确率或等同地最低錯誤率的模型。我們将在3.6節重新讨論模型評估這個主題。

3.3　決策樹分類器

本節介紹一種稱為決策樹分類器的簡單分類技術。為了說明決策樹如何工作，考慮使用表3.2所示的脊椎動物資料集區分哺乳動物和非哺乳動物的分類問題。119假設科學家發現了一個新物種。我們如何判斷它是哺乳動物還是非哺乳動物？一種方法是提出關于物種特征的一系列問題。我們可能會問的第一個問題是該物種是冷血還是恒溫的。如果它是冷血的，那肯定不是哺乳動物，否則，它不是鳥類就是哺乳動物。在後一種情況下，我們需要提出一個後續問題：物種的雌性是否會生下後代？答案是肯定的是哺乳動物，而答案是否定的可能是非哺乳動物（除了産卵的哺乳動物，如鴨嘴獸和刺食蟻獸）。

前面的例子說明了如何通過詢問關于測試執行個體屬性的一系列精心制作的問題來解決分類問題。每次收到答案時，我們都可以提出後續問題，直到能夠确定其類别标簽。可将這一系列問題及其可能的答案組織成稱為決策樹的分層結構。圖3.4給出了一個決策樹如何對哺乳動物進行分類的例子。該樹有三種類型的結點：

• 根結點，沒有傳入連接配接和零個或多個傳出連接配接。
• 内部結點，每個結點隻有一個輸入連接配接和兩個或更多的傳出連接配接。
• 葉結點或終端結點，每個結點隻有一個輸入連接配接并且沒有輸出連接配接。

決策樹中的每個葉結點都與一個類别标簽相關聯。非終端（non-terminal）結點包括根結點和内部結點，包含使用單個屬性定義的屬性測試條件（attribute test condition）。屬性測試條件的每個可能結果都與該結點的一個子結點相關聯。例如，圖3.4中顯示的樹的根結點使用屬性“體溫”來定義一個屬性測試條件，該條件具有兩個結果，即恒溫和冷血，産生兩個子結點。

給定一個決策樹，可以很簡單地對測試執行個體進行分類。從根結點開始，我們應用其屬性測試條件，并根據測試結果按照适當的分支進行操作。這将導緻我們轉移到另一個内部結點或葉結點，該結點應用了新屬性測試條件。一旦到達葉結點，我們将與該結點關聯的類别标簽配置設定給測試執行個體。舉例來說，圖3.5描繪了用于預測火烈鳥的類别标簽的路徑。該路徑終止于标記為“非哺乳動物”的葉結點。

3.3.1　建構決策樹的基本算法

許多可能的決策樹由特定資料集建構。雖然其中一些樹比其他樹好，但由于搜尋空間的指數級别上升，尋找最佳樹的代價是昂貴的。有效的算法已經開發出來，可以在合理的時間内歸納出具有合理準确率的決策樹，盡管不是最優的。這些算法通常采用貪心政策，以自頂向下的方式生成決策樹，也就是是對劃分訓練資料時要使用的屬性進行一系列局部最優決策。最早的方法之一是Hunt算法，它是目前許多決策樹分類器實作的基礎，包括ID3、C4.5和CART。本小節介紹了Hunt算法，并描述了建構決策樹時必須考慮的一些設計問題。

1. Hunt算法

在Hunt算法中，決策樹是以遞歸方式生長的。該樹最初包含與所有訓練執行個體關聯的單個根結點。如果某個結點與來自多個類的執行個體相關聯，則會使用由拆分标準（splitting criterion）确定的屬性測試條件進行擴充。為屬性測試條件的每個結果建立一個子葉結點，并根據測試結果将與父結點關聯的執行個體分發給子結點。此結點擴充步驟可以遞歸應用于每個子結點，隻要它具有多個類的标簽即可。如果與某個葉結點相關的所有執行個體都具有相同的類别标簽，則該結點不會進一步擴充。每個葉結點都會配置設定一個類别标簽，該标簽在與該結點關聯的訓練執行個體中出現的頻率最高。

為了說明算法的工作原理，以表3.3中顯示的貸款人分類問題訓練集為例。假設我們應用Hunt的算法來拟合訓練資料。該分類問題的初始決策樹隻有一個結點，如圖3.6a所示。标記為“拖欠貸款者=否”，意味大多數貸款者都按時歸還貸款。訓練該樹的錯誤率為30％，因為10個訓練執行個體中有3個“拖欠貸款者=是”的類别标簽。因為葉結點包含來自多個類的訓練執行個體，是以可進一步擴充。

将“有房者”作為拆分訓練執行個體的屬性。選擇該屬性作為屬性測試條件的理由将在後面讨論。圖3.6b展示了“有房者”屬性的二進制劃分。“有房者=是”的所有訓練執行個體都傳播到根結點的左子結點，其餘傳播到右子結點。之後将Hunt算法遞歸地應用于每個子結點。由于所有與此結點關聯的執行個體都具有相同的類别标簽，是以将左子結點标記為“拖欠貸款者=否”的葉結點。122右子結點具有來自每個類别标簽的執行個體。是以，我們進一步拆分。圖3.6c和d展示了遞歸擴充右子結點生成的子樹。

如上所述，對Hunt算法做出了一些簡化的假設，然而在實踐中往往是不正确的。在下文中，我們将對這些假設進行描述并簡要讨論一些處理它們的可能方法。

1） 如果任何訓練執行個體都不具有特定的屬性值，則在Hunt算法中建立的一些子結點可以為空。處理該情況的方法是将它們中的每個結點聲明為葉結點，與該結點的父結點相關聯的訓練執行個體的類别标簽出現得最為頻繁。

2） 如果與一個結點相關的所有訓練執行個體具有相同的屬性值，但具有不同的類别标簽，則不能進一步擴充該結點。處理這種情況的方法是将該結點聲明為葉結點，并為其配置設定與該結點關聯的在訓練執行個體中出現最頻繁的類别标簽。

2.決策樹歸納的設計問題

Hunt算法是以貪心政策增長決策樹的通用方法。為了實作該算法，有兩個必須解決的關鍵設計問題。

1） 什麼是拆分标準？在每次遞歸中，必須選擇一個屬性，将與結點關聯的訓練執行個體劃分為與其子結點關聯的較小子集。拆分标準決定選擇哪個屬性作為測試條件以及如何将訓練執行個體配置設定給子結點。這将在3.3.2節和3.3.3節中讨論。

2） 什麼是終止标準？隻有當與結點相關的所有訓練執行個體具有相同的類别标簽或具有相同的屬性值時，基本算法才會停止擴充結點。雖然這些條件已經足夠，但即使葉結點包含來自多個類的訓練執行個體，也有理由更早地終止擴充結點。該過程被稱為提前終止，且确定何時應該終止擴充結點的條件被稱為終止标準。3.4節讨論了提前終止的優點。

3.3.2　表示屬性測試條件的方法

決策樹歸納算法必須為表達屬性測試條件提供方法，為不同屬性類型提供相應結果。

二進制屬性　二進制屬性的測試條件産生兩個可能的輸出，如圖3.7所示。

标稱屬性　由于标稱屬性可以有多個屬性值，是以它的測試條件可以用兩種方式表示，如圖3.8所示的多路劃分和二進制劃分。對于多路劃分（見圖3.8a），其輸出數取決于該屬性不同值的個數。例如，如果婚姻狀況有三個不同的屬性值——單身、已婚和離異，其測試條件将産生三路劃分。也可以将标稱屬性采用的所有值分成兩組來建立二進制劃分。例如，某些決策樹算法（如CART）隻産生二進制劃分，124這些算法可建立k個屬性值二進制劃分的2k-1-1種方法。圖3.8b說明了将婚姻狀況的屬性值分為兩個子集的三種不同方式。

序數屬性　序數屬性也可以産生二進制或多路劃分。隻要分組不違反屬性值的有序性，就可以對序數屬性值進行分組。125圖3.9顯示了基于襯衣尺碼屬性劃分訓練記錄的各種方法。圖3.9a和圖3.9b顯示的分組保留了屬性值之間的順序，而圖3.9c顯示的分組違反了這一性質，因為它将屬性值小号和大号分為一組，而将中号和超大号分為另一組。

連續屬性　對于連續屬性，測試條件可以表示為比較測試（例如A

3.3.3　選擇屬性測試條件的方法

可以用來确定屬性測試條件優劣的度量方法有很多。這些度量方法試圖優先考慮将訓練執行個體劃分為子結點中更純子集的屬性測試條件，這些子結點通常具有相同的類别标簽。由于包含同一類的訓練執行個體的結點不需要進一步擴充，是以屬性更純的結點是有意義的。相反，不純的結點包含來自多個類的訓練執行個體，可能需要多級擴充，進而極大地增加了樹的深度。較大的樹是我們不希望看到的，因為它們更容易受到模型過拟合的影響，這種情況可能會降低未知情況下的分類性能，這将在3.4節中讨論。與較小的樹相比，它們難以解釋，且會使訓練和測試時間更長。

在下文中，我們提出了測量結點不純性和其子結點集合不純性的不同方法，這兩種情況都将用于确定結點的最佳屬性測試條件。

1.單結點的不純性度量

127結點的不純性度量，即度量共有結點的資料執行個體的類别标簽的差異程度。以下是可用于評估結點t不純性的度量示例：

其中，pi（t)是結點t屬于類i的訓練執行個體的相對頻率，c是類的總個數，并且在計算熵時，0 log2 0=0。如果一個結點包含來自單個類的執行個體，并且該結點具有來自多個類的等比例執行個體的最大不純性，則以上三個度量都給出零不純性度量。

圖3.11比較了二分類問題不純性度量的相對大小。由于隻有兩個類，是以p0（t)+p1（t)=1。p表示屬于其中一個類的執行個體所占的比例。當所有三個度量都屬于一個類時（即，p0（t)=p1（t)=0.5）得到最大值，當所有執行個體屬于一個類時，度量得到最小值（即p0（t)或p1（t)等于1）。下面的例子說明了當我們改變類别分布時，不純性度量的值是如何變化的。

基于以上計算，結點N1具有最低的不純性路徑成本，随後是N2和N3。該例與圖3.11一同展示了不純性度量的一緻性，即如果結點N1的熵比結點N2低，那麼N1的基尼指數（Gini index）和誤差率也将低于N2。128盡管它們一緻，但屬性選擇仍然因不純性度量而不同（參見習題6）。

2.子結點的集合不純性

設想一個屬性測試條件，該條件将包含N個訓練執行個體的結點拆分為k個子結點{v1，v2，…，vk}，其中每個子結點表示由屬性測試的k個結果之一産生的資料劃分條件。設N（vj)為與不純性為I（vj）的子結點vj相關聯的訓練執行個體的數量。由于父結點中的訓練執行個體在N（vj)N次數内到達結點vj，是以可以通過對子結點的不純性度量進行權重求和來計算子結點的集合不純性，如下所示：

例3.3 權重熵　考慮圖3.12a和b所示的貸款借款人分類問題的候選人屬性測試條件。對屬性“有房者”進行劃分将産生兩個子結點，其權重熵計算如下：

另一方面，對于“婚姻狀況”的劃分，三個子結點的權重熵由下式給出：

是以，“婚姻狀況”的權重熵低于“有房者”。

3.确定最佳屬性測試條件

為了确定屬性測試條件的優劣，我們需要比較父結點（在劃分之前）的不純性和子結點的不純性的權重程度（分裂之後）。它們的差異越大，測試條件越好。這種差異（Δ）也稱為屬性測試條件的純度增益（gain），定義如下：

其中I（父結點）是劃分前結點的不純性，I（子結點）是劃分後結點的權重不純性度量。可以證明，由于I（父結點）≥I（子結點），對于上述任何合理的度量，增益是非負的。增益越高，子結點相對于父結點的類越純潔。決策樹學習算法中的分裂準則選擇最大增益的屬性測試條件。請注意，在給定結點處最大化增益相當于最小化其子項的權重不純性度量，因為對于所有候選屬性測試條件，I（父結點）是相同的。最後，當熵用作不純性度量時，熵的差異通常稱為資訊增益（information gain）——Δinfo。

在下文中，我們将給出說明性的方法來确定定性或定量屬性的最佳屬性測試條件。

4.定性屬性的劃分

考慮圖3.12顯示的前兩個候選分組，涉及的定性屬性為有房者和婚姻狀況。在父結點處的初始類分布為（0.3，0.7），由于訓練資料中有3個執行個體為是，7個執行個體為否，是以有：

有房者和婚姻狀況的資訊增益分别為：

由于婚姻狀況的權重熵較低，是以其資訊增益較高，将被考慮用于劃分。

5.定性屬性的二進制劃分

考慮僅使用二進制劃分和基尼指數作為不純性度量來建構決策樹。圖3.13顯示了屬性有房者和婚姻狀況的4個候選劃分标準的例子。由于訓練集中有3名借款人違約，另有7名借款人償還了貸款（見圖3.13中的表格），是以劃分前的父結點的基尼指數為

如果選擇有房者作為劃分屬性，則子結點N1和N2的基尼指數分别為0和0.490。這些子結點的權重平均基尼指數是

此處的權重代表配置設定給每個子結點訓練執行個體的比例。使用有房者作為劃分屬性的增益為0.420-0.343=0.077。同樣，也可以對屬性婚姻狀況應用二進制劃分。但是，由于婚姻狀況是一個具有三種結果的标稱屬性，是以有三種可能的方式對屬性值進行二進制劃分。圖3.13顯示了每個候選二進制劃分的子結點的權重平均基尼指數。根據這些結果，有房者和使用婚姻狀況的二進制分組顯然是最好的候選，因為它們都産生最低的權重平均基尼指數。如果屬性值的二進制劃分不違反順序屬性，則二進制劃分也可用于序數屬性。

6.定量屬性的二進制劃分

考慮為上述拖欠貸款分類問題确定最佳二進制劃分“年收入≤τ”的問題。正如之前讨論的那樣，盡管τ可以在訓練集中年收入的最小值和最大值之間取任意值，但隻需将訓練集中觀察到的年收入值視為候選劃分位置就足夠了。對于每個候選τ，訓練集被掃描一次以計算年收入小于或大于τ的借款人數量及其類别比例。然後，我們可以計算每個候選劃分位置的基尼指數，并選擇産生τ的最小值。在每個候選劃分位置計算基尼指數需要O（N）次操作，其中N是訓練執行個體的數量。由于最多有N個候選，是以該暴力法的計算複雜度為O（N2）。通過使用如下所述的方法（參見圖3.14中的說明），可以将此問題的計算複雜度降至O（NlogN）。在這種方法中，首先根據年收入将訓練執行個體排序，所需時間為O（NlogN）。從兩個相鄰的排過序的屬性值中選擇中間值作為候選劃分點，得到候選劃分點為55000美元、65000美元、72500美元等。對于第一位候選，由于無年收入低于或等于55000美元，年收入<55000美元的子結點的基尼指數等于零。相比之下，年收入大于55000美元的結點有3個執行個體是是，7個是否，該結點的基尼指數是0.420。第一候選劃分位置τ=55000美元的權重平均基尼指數等于0×0+1×0.420=0.420。

對于第二個候選τ=65000，通過簡單更新上一個候選的類分布，就可得到該候選的類分布。這是因為，當τ從55000美元增加到65000美元時，隻有一個受此變化影響的訓練執行個體。通過檢查受影響的訓練執行個體的類别标簽，可以獲得新的類分布。例如，當τ增加到65000美元時，133訓練集中隻有一個借款人，年收入為60000美元，受此變化影響。由于借款人的類别标簽為否，是以類别否的計數從0增加到1（年收入≤65000美元），并從7減少到6（年收入>65000美元），如圖3.14所示。是類的分布保持不變。新的候選劃分的基尼指數為0.400。

重複此過程直至算出所有候選的基尼指數。最佳劃分位置對應于産生最低基尼指數的點，即τ=97500美元。由于可以在O（1）時間内計算每個候選劃分位置的基尼指數，如果所有值保持排序，找到最佳劃分位置的時間複雜度為O（N），一次操作需要O（NlogN）時間。是以這種方法的計算複雜度為O（NlogN），比暴力法所花費的O（N2）時間小得多。通過僅考慮位于不同類别标簽的兩個相鄰排序執行個體之間的候選劃分位置，可以進一步減少計算量。例如，我們無須考慮位于60000美元至75000美元之間的候選劃分位置，因為年收入在此範圍内的三個執行個體（60000美元，70000美元和75000美元）都具有相同的類别标簽。對比位于此範圍之外的劃分位置，選擇此範圍内的劃分位置隻會增加不純性的程度。是以，在τ=65000美元和τ=72500美元的候選劃分位置可以忽略。同樣，我們也無須考慮候選劃分位置87500美元、92500美元、110000美元、122500美元和172500美元，因為它們位于兩個相鄰且具有相同标簽的執行個體之間。該政策将需考慮的候選劃分位置的數量從9減少到2（不包括兩個邊界情況τ=55000美元和τ=230000美元）。

7.增益率

熵和基尼指數等不純性度量存在一個潛在的局限，即它們更容易選擇具有大量不同值的定性屬性。圖3.12給出了表3.3列出的劃分資料集的三個候選屬性。如上所述，選擇屬性婚姻狀況優于選擇屬性有房者，因為前者提供了更大的資訊增益。但是，如果将它們與顧客ID進行比較，後者因為權重熵和基尼指數等于零，會生成資訊增益更大的最純劃分。然而，顧客ID并不是一個很好的劃分屬性，因為它對每個執行個體都有唯一的值。即使包含顧客ID的測試條件将準确對訓練資料中的每個執行個體進行分類，我們也不能将此類測試條件用于含有未知顧客ID的新測試執行個體中。134這個例子表明單一的低不純性結點不足以找到良好的屬性測試條件。正如我們将在3.4節中讨論的，子結點越多，決策樹越複雜，更容易出現過拟合。是以，在決定最佳屬性測試條件時，還應該考慮劃分屬性産生的子結點數量。

有兩種方法可以解決這個問題。一種方法是僅生成二進制決策樹，進而避免使用不同數量的劃分來處理屬性。決策樹分類器（如CART）就是使用此政策。另一種方法是修改劃分标準以考慮屬性生成的劃分數量。例如，在C4.5決策樹算法中，使用稱為增益率（gain ratio）的度量來補償産生大量子結點的屬性。這一度量的計算如下：

其中，N（vi）是配置設定給結點vi的執行個體數量，且k是劃分的總數。劃分資訊測量将結點劃分成子結點的熵，并評估劃分是否會導緻大量相同大小的子結點。例如，如果每個劃分具有相同數量的執行個體，則i：N（vi）N=1k并且劃分資訊等于log2k。這說明如果屬性産生大量的劃分，則其劃分資訊也很大，進而降低了增益率。

例3.4 增益率　考慮習題2中給出的資料集。我們希望從性别、車型和顧客ID三個屬性中選出最佳屬性測試條件。劃分前的熵為：

如果使用性别作為屬性測試條件：

如果使用車型作為屬性測試條件：

如果使用顧客ID作為屬性測試條件：

是以，盡管顧客ID具有最高的資訊增益，但其增益率低于車型，因為前者會産生更大數量的劃分。

3.3.4　決策樹歸納算法

算法3.1給出了決策樹歸納算法的僞代碼。該算法的輸入是一組訓練執行個體集E和屬性集F。該算法遞歸地選擇最優屬性來劃分資料（步驟7），并擴充樹的葉結點（步驟11和12）直到滿足結束條件（步驟1）。算法的細節如下。

1) createNode（)函數通過建立一個新結點來擴充決策樹。決策樹的結點要麼具有測試條件，表示為node.test_cond，要麼具有類别标簽，表示為node.label。

2) find_best_split（)函數确定應當選擇哪個屬性作為劃分訓練執行個體的測試條件。劃分屬性的選擇取決于使用哪種不純性度量來評估劃分。常用的措施包括熵和基尼指數。

3) Classify（)函數确定要配置設定給葉結點的類别标簽。對于每個葉結點t，令p（it)表示該結點上屬于類i的訓練執行個體所占的比例。136配置設定給葉結點的标簽通常是在與此結點關聯的訓練執行個體中最常出現的标簽。

其中，argmax傳回最大化p（it)的類i。p（it)除了提供确定葉結點的類别标簽所需的資訊之外，還可以用來估計配置設定到葉結點t的執行個體屬于類别i的機率。4.11.2節和4.11.4節讨論，如何使用這種機率估計，來确定在不同代價函數下決策樹的性能。

4) stopping_cond（)函數通過檢查所有執行個體是否具有相同的類别标簽，或相同的屬性值來決定是否終止決策樹的增長。由于決策樹分類器采用自頂向下的遞歸劃分方法來構模組化型，是以随着樹深度的增加，與結點關聯的訓練執行個體的數量也會減少。是以，葉結點包含的訓練執行個體可能太少，以至于無法對其類别标簽做出統計上顯著的決定。這被稱為資料碎片（data fragmentation）問題。避免此問題的一種方法是，當與結點關聯的執行個體數量低于某個門檻值時，137不允許劃分結點。3.5.4節會讨論使用更系統的方法來控制決策樹的大小（葉結點的數量）。

3.3.5　示例：Web機器人檢測

現考慮區分Web機器人的通路模式與人類使用者的通路模式的任務。Web機器人（也稱為網絡爬蟲）是一種軟體程式，通過跟蹤從最初的一組種子URL中提取的超連結，從一個或多個網站自動檢索檔案。這些程式已被應用于各種用途，從代替搜尋引擎搜集Web網頁到執行一些更惡意的活動，如制造垃圾郵件、在線上廣告中制造點選欺詐。

Web機器人檢測問題可以轉換為二分類任務。分類任務的輸入資料是一個Web伺服器日志，138圖3.15a顯示了一個樣例。日志檔案中的每一行對應于用戶端（即人類使用者或Web機器人）對Web伺服器所做的請求。Web日志中記錄的字段包括用戶端的IP位址、請求的時間戳、請求檔案的URL、檔案的大小以及使用者代理。使用者代理是包含有關用戶端辨別資訊的字段。對于人類使用者，使用者代理字段指定用于提取檔案的Web浏覽器或移動裝置的類型，而對于Web機器人，它應在技術上包含爬蟲程式的名稱。然而，Web機器人可能會通過聲明與已知浏覽器相同的使用者代理字段來隐藏其真實身份。是以，使用者代理不是檢測Web機器人的可靠方式。

建構分類模型的第一步是精确定義資料執行個體和關聯屬性。一種簡單的方法是将每個日志條目視為資料執行個體，并将日志檔案中的相應字段用作其屬性集。但是，這種方法由于幾個原因而不夠可靠。首先，許多屬性是标稱值，并且取值範圍廣泛。例如，日志檔案中唯一的用戶端IP位址、URL和引用連結的數量可能非常大。這些屬性對于建構決策樹是不可取的，因為它們的劃分資訊非常大（參見式（3.9））。另外，可能無法對包含的IP位址、URL或參考者的測試執行個體進行分類，這些執行個體不存在于訓練資料中。最後，通過将每個日志條目視為一個單獨的資料執行個體，我們忽略了用戶端檢索的網頁序列這一關鍵資訊，即可以幫助區分Web機器人通路與人類使用者的通路。

将每個Web會話視為資料執行個體是一種更好的選擇。Web會話是客戶在通路網站期間發出的一系列請求，每個Web會話都可以模拟為有向圖，其中結點對應于網頁，邊對應于将一個網頁連接配接到另一個網頁的超連結。圖3.15b顯示了日志檔案中給出的第一個Web會話的圖形表示。每個Web會話都可以使用一些關于含有歧視性資訊圖形的有意義的屬性進行表示。圖3.15c顯示了從圖中提取的一些屬性，包括紮根于網站入口處的相應樹的深度和寬度。例如，圖3.15b所示的樹的深度和寬度都等于2。

3.15c顯示的派生屬性比日志檔案中給出的原始屬性包含更多資訊，因為它們表示了用戶端在網站上的行為。由于Web機器人（1級）和人類使用者（0級）的會話數量相等，是以使用該方法建立了一個包含2916個執行個體的資料集。其中10％的資料用于訓練，139其餘90％用于測試。生成的決策樹如圖3.16所示，該決策樹在訓練集上的錯誤率為3.8％，在測試集上的錯誤率為5.3％。除了低錯誤率之外，決策樹還顯示了一些有趣的屬性，有助于區分Web機器人與人類使用者：

1) Web機器人的通路往往是廣泛但淺顯的，而人類使用者的通路往往更集中（視野狹窄但深入）。

2) Web機器人很少檢索與網頁關聯的圖像頁面。

3) 由Web機器人産生的會話往往很長，并且包含大量請求頁面。

4) 由于人類使用者檢索的網頁通常由浏覽器緩存，是以Web機器人比人類使用者更可能對同一網頁重複請求。

3.3.6　決策樹分類器的特征

以下是對決策樹歸納算法的重要特征的總結。

1) 适用性：決策樹是建構分類模型的非參數化方法。這種方法不需要任何關于管理資料的類别和屬性機率分布的先驗假設，是以适用于各種各樣的資料集。它也适用于連續可分類資料，而不需要通過二值化、标準化或規範化将屬性轉換為通用表示。與第4章描述的某些二分類器不同，它也可以處理多分類問題，而不需要将它們分解為多個二分類任務。決策樹分類器的另一個吸引人的特點是誘導樹，特别是較短的樹，相對容易解釋。對許多簡單的資料集，樹的準确率也與其他分類技術相當。

2) 表達能力：決策樹為離散值函數提供了一個通用表示。換句話說，它可以編碼任何離散值屬性的函數。這是因為每個離散值函數都可以表示為一個指派表，其中每個離散屬性的唯一組合都被賦予一個類别标簽。由于每個屬性組合可以表示為決策樹中的一個葉結點，我們總能找到一個決策樹，其葉結點處的标簽配置設定與原始函數的配置設定表相比對。當某些獨特的屬性組合可以由同一葉結點表示時，決策樹還可以幫助提供緊湊的函數表示。例如，圖3.17顯示了涉及四個二進制屬性的布爾函數（A∧B）∨（C∧D）的配置設定表，進而導緻總共24=16個可能的配置設定。圖3.17中的樹顯示了此配置設定表的壓縮編碼。不需要具有16個葉結點的完全生長的樹，可以使用僅具有7個葉結點的更簡單的樹對函數進行編碼。盡管如此，并非所有離散值屬性的決策樹都可以被簡化。一個值得注意的例子是奇偶校驗函數，當其布爾屬性中存在偶數個真值時，其值為1，否則為0。這種函數的精确模組化需要一個帶有2d個結點的完整決策樹，其中d是布爾屬性的數量（請參閱習題1）。

3) 計算效率：由于決策樹的數量可能非常大，是以許多決策樹算法采用基于啟發式的方法來指導它們在廣闊的假設空間中進行搜尋。例如，3.3.4節介紹的算法使用自頂向下的貪心遞歸劃分政策來生成決策樹。對于許多資料集，即使訓練集的規模非常大，這種技術也能快速建構合理的決策樹。此外，一旦建構了決策樹，可迅速對測試記錄進行分類，最壞情況下的複雜度為O（ω），其中ω是樹的最大深度。

4) 處理缺失值：在訓練集和測試集中，決策樹分類器都可以通過多種方式處理缺失的屬性值。當測試集有缺失值時，如果給定的測試執行個體缺少劃分結點屬性的值，則分類器必須決定遵循哪個分支。C4.5決策樹分類器采用機率劃分法（probabilistic split method），根據缺失屬性具有特定值的機率将資料執行個體配置設定給劃分結點的每個子結點。相比之下，CART算法使用替代拆分法（surrogate split method），142将劃分屬性值缺失的執行個體根據其他非缺失替代屬性的值配置設定給其中一個子結點，其中所述的其他非缺失替代屬性劃分最類似于基于缺失屬性的劃分。CHAID算法使用了另一種稱為獨立類法（separate class method）的方法，将缺失值視為與劃分屬性的其他值不同的單獨分類值。圖3.18顯示了處理決策樹分類器中缺失值的三種不同方式的示例。處理缺失值的其他政策基于資料預處理，其中有缺失值的執行個體在分類器被訓練之前，利用模式（對于分類屬性）或平均值（對于連續屬性）進行估算或丢棄。

在訓練過程中，如果屬性ν在某個與結點相關的訓練執行個體中為缺失值且該屬性用于劃分，則需要一種方法來測量純度增益。一種簡單的方法是在計算與每個子結點關聯的執行個體的計數中排除具有缺失值ν的執行個體，并為每個可能的結果ν生成該執行個體。此外，如果選擇ν作為結點上的屬性測試條件，則可以使用上述任何方法将缺失值ν的訓練執行個體傳播到子結點，以處理測試執行個體中的缺失值。

5) 處理屬性之間的互相作用：屬性被認為是互相作用的，一起使用時能夠區分類别，但是它們單獨使用隻能提供很少或不提供資訊。由于決策樹中劃分标準的本質是貪心的，這些屬性可能會與其他不太有效的屬性一起使用，這可能導緻生成非必要的更為複雜的決策樹。是以，當屬性之間存在互相作用時，決策樹可能表現不佳。

為了說明這一點，考慮圖3.19a所示的三維資料，其中包含來自兩個類的資料點，一個類包含2000個，在圖中表示為“+”和“o”。圖3.19b顯示了涉及屬性X和Y的二維空間中兩個類的分布，這是XOR布爾函數的噪聲版本。可以看到，盡管這兩個類在這個二維空間中很好地分離，但是這兩個屬性單獨使用時都沒有足夠的資訊來區分這兩個類。例如，以下屬性測試條件的熵（X≤10和Y≤10）接近于1，表明單獨使用時，X和Y都不會減少不純性度量。是以表明X和Y是互相作用的屬性。資料集還包含第三個屬性Z，其中兩個類均勻分布如圖3.19c和3.19d所示，可得出任何涉及Z的劃分的熵都接近1。是以，Z可能被選作劃分有互相作用但有效的屬性X和Y。為了進一步說明這個問題，讀者可以參考本章的例3.7和本章最後的練習7。

6) 處理不相關的屬性：如果屬性對分類任務無用，則屬性無關緊要。由于不相關的屬性與目标類别标簽的關聯性很差，它們在純度上幾乎沒有增益，是以将被其他更相關的特性所忽略。由此可知，少量不相關屬性的存在不會影響決策樹建構過程。然而，并非所有提供很少或無增益的屬性都不相關（見圖3.19）。如果分類問題是複雜的（例如涉及屬性之間的互相作用）并且存在大量不相關的屬性，那麼在樹生長過程中可能會意外地選擇這些屬性中的一些，因為它們在一些偶然情況下可能會提供比相關屬性更好的增益。特征選擇技術可以通過預處理過程消除不相關的屬性來幫助提高決策樹的準确性。3.4節會探讨大量不相關屬性的問題。

7) 處理備援屬性：如果屬性與資料中的另一個屬性強相關，則該屬性是多餘的。由于備援屬性在被選擇用于劃分時顯示出相似的純度增益，是以在決策樹算法中隻有其中一個屬性被選為屬性測試條件。由此可知，決策樹可以處理備援屬性的存在。

8) 使用直線劃分：本章到目前為止描述的測試條件一次隻涉及一個屬性。是以，樹的生長過程可以看作将屬性空間劃分為不相交區域的過程，直到每個區域包含相同類别的記錄為止。不同類别的兩個相鄰區域之間的邊界稱為決策邊界（decision boundary)。圖3.20顯示了決策樹以及二分類問題的決策邊界。由于測試條件隻涉及單個屬性，是以決策邊界是直線，即平行于坐标軸。這限制了決策樹在表示具有連續屬性資料集的決策邊界時的表達能力。圖3.21顯示了一個涉及二分類的二維資料集，該資料集不能通過其屬性測試條件，基于單個屬性定義的決策樹對資料進行完全分類。資料集中的二分類是由兩個傾斜的高斯分布生成的，分别集中在（8，8）和（12，12）處。真正的決策邊界用對角虛線表示，而決策樹分類器産生的直線決策邊界用粗實線表示。相反，傾斜決策樹（oblique decision tree）可以通過允許使用多個屬性指定測試條件來克服這個限制。例如，圖3.21所示的二分類資料可以很容易地用具有單個根結點的測試條件x+y<20的傾斜決策樹表示。

盡管傾斜決策樹具有更強的表達能力，可以生成更緊湊的樹，但尋找最佳測試條件的計算量更大。

9) 不純性測量的選擇：應該指出，不純性測量的選擇通常對決策樹分類器的性能沒有影響，因為許多不純性測量值彼此非常一緻，如圖3.11所示。相反，用于修剪樹的政策對最終樹的影響大于不純性度量的選擇。

3.4　模型的過拟合

目前提出的分類模型學習方法試圖在訓練集上顯示最低誤差。但是，正如下面的例子将要展現的那樣，有的模型即使能夠很好地覆寫訓練資料，但它仍然可能表現出較差的泛化性能，這種現象稱為模型的過拟合（model overfitting）。

例3.5 決策樹的過拟合和欠拟合　考慮圖3.22a所示的二維資料集。資料集中的執行個體屬于兩個類，分别标記為“+”和“o”，每個類都有5400個執行個體。所有屬于“o”類的執行個體服從均勻分布。在“+”類中，5000個執行個體的生成服從高斯分布，并通過機關方差法集中在（10，10)處，而其餘400個執行個體的采樣與“o”類一樣服從均勻分布。由圖3.22a可知，通過繪制一個以（10，10）為中心的适當大小的圓，可以很大程度地将“+”類與“o”類區分開來。為了生成這個二維資料集的分類器，随機抽取10%的資料進行訓練，剩餘90%用于測試。圖3.22b所示的訓練集看起來非常有代表性。我們使用基尼指數作為不純性度量來構造決策樹，通過遞歸将結點擴充到子結點，直到每個葉結點都是純的，以此增加樹的規模（葉結點數），詳見3.3.4節。

圖3.23a顯示了樹的大小從1到8變化時，訓練集和測試集錯誤率的變化趨勢。樹在最初隻有一個或兩個葉結點時，錯誤率都很高。這種情況稱作模型欠拟合（model undertting）。若學習的決策樹過于簡單，則會導緻欠拟合，以緻無法充分表示屬性與類别标簽之間的真實關系。随着将樹的大小從1增加到8，我們有兩個發現。首先，由于較大的樹能夠表示更複雜的決策邊界，是以錯誤率會降低。其次，訓練集和測試集的錯誤率十分接近，這表明訓練集在性能上足以代表泛化性能。随着進一步将樹的大小從8增加到150，訓練錯誤率繼續穩定下降，直至最終達到零，如圖3.23b所示。然而，與此形成鮮明對比的是，測試錯誤率在樹的規模到達某一值時停止下降，之後開始增加。一旦樹的規模變得太大，訓練錯誤率将不再足以評估測試集的錯誤率。此外，随着樹的規模不斷增大，訓練錯誤率和測試錯誤率之間的差距不斷擴大。這種看起來有悖直覺的現象被稱為模型過拟合（model overfitting）。

模型過拟合的原因

模型過拟合指的是在追求訓練錯誤率最小化的過程中，選擇了一種過于複雜的模型，這種模型捕捉到了訓練資料中的特定模式，但是沒能擷取到整體資料中屬性和類别标簽之間的本質關系。為了說明這一點，圖3.24給出了兩棵大小分别為5和50的決策樹及其相應的決策邊界（陰影矩形表示配置設定給“+”類的區域）。可以看出，大小為5的決策樹顯得非常簡單，它的決策邊界為最佳決策邊界提供了一個合理的近似值，在這種情況下，它對應于以（10，10）處的高斯分布為中心的圓。149雖然它的訓練和測試錯誤率非零，但是它們十分接近，這表明在訓練集中學習到的模式能很好地泛化到測試集。另一方面，規模為50的決策樹比規模為5的決策樹看上去更複雜，同時具有繁複的決策邊界。例如，一些陰影矩形（配置設定給“+”類）試圖覆寫輸入空間中僅包含一個或兩個“+”類訓練執行個體的狹窄區域。需要注意的是，150這類區域中的“+”執行個體在訓練集中具有高度特異性，因為這些區域主要由整體資料集中的“-”執行個體占據。是以，為了完美拟合訓練資料，規模為50的決策樹開始調整以适配測試集中的特定模式，導緻在獨立選擇的測試集上性能較差。

影響模型過拟合的因素有很多。在下文中，我們簡要說明兩個主要因素：有限的訓練規模和過高的模型複雜度。盡管它們并非詳盡無遺，但它們之間的互相影響可以幫助解釋大多數現實應用中常見的過拟合現象。

1.有限的訓練規模

需要注意的是，由有限個執行個體組成的訓練集僅能對整體資料進行有限表示。是以，從訓練集中學習得到的模式不能完全代表整體資料的實際模式，進而導緻模型過拟合。一般來說，随着我們增大訓練集的規模（訓練執行個體的數量），從訓練集中學習得到的模式與整體資料的實際模式越來越類似。是以，通過增大訓練規模可以減少過拟合的影響，如下例所示。

例3.6 訓練規模的影響　假設使用的訓練執行個體數量是例3.5實驗中使用的兩倍。具體地，我們使用20％的資料進行訓練，剩下的資料用于測試。圖3.25b顯示了樹的大小從1變化到150時的訓練和測試錯誤率。該圖的變化趨勢與圖3.23b顯示的變化趨勢存在兩個主要差別（僅使用10％的資料用于訓練時）。首先，盡管兩個圖中的訓練錯誤率都随着樹規模的增大而減小，但當我們使用兩倍規模的訓練資料時，訓練錯誤率的下降速率要小得多。其次，對于給定大小的樹，當我們使用兩倍訓練資料時，訓練與測試錯誤率之間的差距要小得多。這些差異表明，相比于使用10%的資料進行訓練學習得到的模式，使用20%的資料進行訓練得到的模式具有更好的泛化能力。

圖3.25a顯示了用20%的資料進行訓練時，大小為50的樹的決策邊界。對于相同大小的樹，與使用10%的訓練資料（見圖3.24d）學習的結果相反，我們可以看到決策樹沒有捕獲訓練集中“+”類噪聲執行個體的特定模式。相反，具有50個葉結點的高模型複雜度常被用于學習以（10，10)為中心的“+”類執行個體的邊界。

2.高模型複雜度

通常，較為複雜的模型能夠更好地表示資料中的複雜模式。例如，與葉結點數較少的決策樹相比，具有較多葉結點的決策樹可以表示更複雜的決策邊界。但是，一個過于複雜的模型傾向于學習訓練集中的特定模式，而這類模型不能很好地概括那些隐藏的執行個體。是以，對于高度複雜的模型，應謹慎使用，避免出現過拟合現象。

從訓練集中需要推導出的參數個數是模型複雜度的一種度量方式。例如，在決策樹構造過程中，内部結點的屬性測試條件數量與從訓練集中推導出的模型參數數量一緻。具有大量屬性測試條件（導緻更多葉結點）的決策樹具有更多的“參數”，是以更為複雜。

給出一類模型以及一定數量的參數，一個學習算法試圖篩選出令訓練集的評價矩陣（例如，準确率）最大化的最佳參數值組合。152如果參數值的組合數很多（是以複雜度更高），學習算法需要通過有限的訓練集，從大量可能的組合中篩選出最佳組合。在這種情況下，學習算法很有可能篩選出一個虛假的參數組合，由于随機因素導緻了評價矩陣最大化。這類似于統計學中的多重比較問題（multiple comparisons problem）（也稱多重測試問題）。

為了說明多重比較問題，考慮對未來10個交易日股市漲跌進行預測的任務。如果一位股票分析師的預測隻是随機猜測，那麼對于任意交易日的預測，其準确率都是0.5。然而，在10次預測中至少正确9次的機率為

該機率是極低的。

假設我們要從200位股票分析師中挑選出一位投資顧問。政策是挑選出在未來10個交易日中，能做出最多正确預測的分析師。這種政策的缺點是，假設所有分析師的預測都是随機産生的，那麼至少有一人正确預測不少于9次的機率為1-（1-0.0107)^200=0.8847這是非常高的。盡管對于每個分析師，正确預測不小于9次的機率都很低，但綜合考慮後，至少找到一個這樣的分析師的機率是很高的。然而，我們無法確定這樣一個分析師在未來能通過随機猜測的方法一直做出正确的預測。

多重比較問題與模型過拟合有什麼關系呢？在學習分類模型的過程中，每個參數值組合都相當于一個分析師，而訓練執行個體的數量相當于天數。類似于挑選出在連續日内，預測準确率最高的分析師的任務，學習算法的任務是挑選出最适配訓練集的參數值組合。如果參數組合很多，但訓練規模很小，最有可能的原因是學習算法選取了虛假的參數組合，這些組合由于随機因素導緻了高的訓練準确率。在下面的例子中，我們将闡述在構造決策樹的過程中，因多重比較所導緻的過拟合現象。

例3.7 多重比較和過拟合　考慮圖3.26中包含了500個“+”類執行個體和500個“o”類執行個體的二維資料集，其類似于圖3.19表示的資料。在這個資料集中，二維（X-Y）屬性空間将兩個類的分布清晰地分割開，但是這兩個屬性（X或Y）單獨的資訊量均不足以區分這兩個類。是以，基于X屬性或Y屬性的任意值對資料集進行劃分，會使不純性度量接近于0。但是，如果同時使用X和Y屬性作為劃分依據（例如，在（X，Y)取值為（10，10)時進行劃分)，則可以有效地對這兩個類進行劃分。

圖3.27a顯示了學習不同大小決策樹時的訓練和測試錯誤率，其中，30%的資料用于訓練，其餘的用于測試。我們可以看到，在葉結點數很少的時候，兩個類就可以很容易被分開。圖3.28顯示了具有6個葉結點的樹的決策邊界，樹杈按其在樹中出現的順序進行編号。值得注意的是，雖然分割1和3後獲得的增益微乎其微，但是在它們之後對（2，4，5）進行劃分可以提供巨大的增益，進而使得對這兩個類的區分是有效的。

假設我們在二維資料X-Y中添加100個不相關屬性。從這一合成資料中學習決策樹将具有挑戰性，因為在每個内部結點上進行劃分選擇時，候選屬性的數量将從2個增加到102個。由于候選屬性的測試條件繁多，很可能因為多重比較問題，使得内部結點選擇虛假的屬性測試條件。圖3.27b顯示了向訓練集添加100個不相關屬性後的訓練誤差和測試誤差。155可以看到，即使使用50個葉結點，測試錯誤率也保持在接近0.5的水準，而訓練錯誤率持續下降，最終變為0。

3.5　模型選擇

現有許多可行的分類模型，它們具有不同層次的模型複雜性，可用于捕獲訓練資料中的模式。在這些可選項中，我們需要選擇的是泛化錯誤率最低的模型。模型選擇（model selection）指的是選擇出複雜度适合且可以很好地泛化到隐藏的測試執行個體的模型。如上節所述，訓練錯誤率不能可靠地作為模型選擇的唯一标準。下面，我們将介紹三種通用的方法來評估模型的泛化能力，以此用于模型選擇。本節主要講述如何在決策樹歸納中使用這些方法的特定政策。

3.5.1　驗證集應用

值得注意的是，我們總是可以通過“樣本外”估計來評估模型的泛化錯誤率，例如，可以在一個單獨的驗證集（validation set）上對模型進行評估，該集合未被用于模型訓練。由于驗證集未被用于訓練模型，是以驗證集的錯誤率（稱為驗證錯誤率）比訓練錯誤率更能說明泛化性能。以下将介紹驗證錯誤率在模型選擇中的應用。

給定一個訓練集D.train，我們可以将D.train劃分為兩個更小的子集——D.tr和D.val，其中，D.tr用于訓練，而D.val作為驗證集。例如，将D.train的23作為D.tr用于訓練，剩餘13作為D.val用于計算驗證錯誤率。對于任何經過D.tr訓練的分類模型m，我們可以通過D.val評估它的驗證錯誤率——errval（m)。其中，errval（m)值最小的模型即為首選模型。

驗證集的使用為模型選擇提供了一種通用的方法。然而，這種方法具有一個局限性，它對從D.train中獲得的D.tr和D.val的大小很敏感。如果D.tr的規模很小，可能會導緻學習到一個性能不佳的分類模型，156這是因為較小的訓練集不能很好地代表整體資料。另一方面，如果D.val的規模很小，使用驗證錯誤率選擇模型将變得不可靠，因為它僅在少量執行個體上進行計算。

例3.8 驗證錯誤　在下面的示例中，我們示範了在決策樹歸納中使用驗證集的一種可行方法。對于圖3.30生成的決策樹，圖3.29顯示了其葉結點上的預測标簽。位于葉結點下的計數表示驗證集中到達該結點的資料執行個體比例。根據結點的預測标簽，左樹的驗證錯誤率為

，右樹的驗證錯誤率為

。基于它們的驗證錯誤率，右樹比左樹更适合。

3.5.2　模型複雜度合并

由于模型越複雜，發生過拟合的可能性越大，是以模型選擇方法不僅要考慮訓練錯誤率，還要考慮模型的複雜度。這一政策來源于衆所周知的奧卡姆剃刀原理（Occam’s razor），也就是所謂的節儉原則（principle of parsimony）。它表明，如果兩個模型具有相同的誤差，157較簡單的模型将優于較複雜的模型。在評估泛化性能的同時考慮模型複雜度的一般方法如下所示。

給定一個訓練集D.train，考慮學習一個屬于模型M的分類模型m。例如，如果M代表所有可能的決策樹的集合，那麼m可以對應一個從訓練集中學習到的特定決策樹。我們對m的泛化錯誤率gen.error（m)有興趣。如前文所述，當模型複雜度較高時，m的訓練錯誤率train.error（m，D.train)會低估gen.error（m)。是以，我們在使用訓練錯誤率的同時，還使用模型M的複雜度complexity（M)來表示gen.error（m)函數，如下所示：

其中，α是一個超參數，用于協調最小化訓練錯誤和降低模型複雜度。一個過大的α取值在評估過程中更強調模型複雜度對泛化性能的影響。可以使用3.5.1節描述的利用驗證集的方法選擇合适的α值。例如，可以周遊α的所有可取值，從訓練集的一個子集D.tr中學習到一個模型，然後通過一個獨立的子集D.val計算得到模型的驗證錯誤率。最後選擇使驗證錯誤率最低的α取值。

式（3.11）提供了一種可行的方法，将模型複雜度納入對泛化性能的評估中。該方法成為許多用于評估泛化性能的技術的核心，例如結構風險最小化原則、赤池資訊準則（Akaike’s Information Criterion，AIC）、貝葉斯資訊準則（Bayesian Information Criterion，BIC）。結構風險最小化原則是學習支援向量機的基礎，該部分會在第4章進行探讨。有關AIC和BIC的更多細節，請參閱參考文獻。

下面将介紹兩種不同的方法來評估模型的複雜度complexity（M)。前者專門用于決策樹模型，而後者适用于任何類型的模型，更為通用。

1.決策樹複雜度評估

決策樹的複雜度可以用葉結點數與訓練執行個體數的比值進行評估。設k為葉結點數，Ntrain為訓練執行個體數。決策樹的複雜度可用kNtrain表示。直覺上，對于大規模的訓練集，我們可以學習到一種具有大量葉結點的決策樹，而其複雜度又不會太高。決策樹T的泛化錯誤率可由式（3.11）計算得出，具體如下：

其中，err（T)是決策樹的訓練誤差，Ω是權衡減小訓練誤差和最小化模型複雜度的超參數，類似于式（3.11）中使用的α。Ω可以看作為了防止訓練誤差，每添加一個葉結點的成本。在決策樹歸納的文獻中，上述評估泛化錯誤率的方法也稱為悲觀誤差估計（pessimistic error estimate）。稱其為悲觀是因為它假設泛化錯誤率比訓練錯誤率要差（通過增加模型複雜性的懲罰項）。與之相對，簡單地使用訓練錯誤率來評估泛化錯誤率，被稱為樂觀誤差估計（optimistic error estimate）或再代入估計（resubstitution estimate）。

例3.9 泛化錯誤率估計　考慮圖3.30中的兩棵二叉決策樹TL和TR。這兩棵樹由相同的訓練資料生成的，159TL是通過擴充了TR的三個葉結點生成的，葉結點上的計數表示訓練執行個體的類分布。如果根據到達葉結點的大多數訓練執行個體标記該結點，則左樹的訓練錯誤率為err（TL)=424=0.167，右樹的訓練錯誤率為err（TR)=624=0.25。僅根據訓練錯誤率進行評估，認為TL優于TR，即使TL比TR更複雜（即包含更多的葉子結點）。

現假設每個葉結點的成本Ω=0.5。然後，TL的泛化錯誤率估計為

TR的泛化錯誤率估計為

由于TL的泛化錯誤率較低，是以依舊認為TL優于TR。需要注意的是，Ω=0.5意味着如果一個結點增加了至少一個訓練執行個體的預測，那麼這個結點應該擴充出兩個子結點，因為擴充結點的成本比對訓練執行個體進行分類的成本更低。此外，如果Ω=1，TL的泛化錯誤率為errgen（TL)=1124=0.458，TR的泛化錯誤率為errgen（TR)=1024=0.417。此時由于TR的泛化錯誤率更低，是以認為TR優于TL。這個例子說明了基于泛化錯誤率估計對決策樹進行選擇時，Ω的不同取值會改變我們的選擇偏好。然而，對于一個給定的Ω取值，悲觀誤差估計提供了一種方法，用于對未知測試執行個體的泛化性能進行模組化。驗證集有助于Ω取值的選擇。

2.最小描述長度原則

另一種合并模型複雜性的方法是基于資訊理論的方法，即最小描述長度原則（Minimam Description Length，MDL）。圖3.31中的示例闡明了這種方法。在該示例中，A和B都被分類配了一組屬性值x已知的執行個體。假設A知道所有執行個體中哪些類别标簽為y，而B不知道。A希望向B發送包含類别标簽資訊的消息，與B實作類資訊共享。消息包含Θ（N)位的資訊，其中N表示執行個體數量。

或者，A可以不直接發送類别标簽資訊，而是根據執行個體建構一個分類模型，将其傳給B。然後B可以利用該模型來确定執行個體的類别标簽。如果該模型的準确率是100%，那麼傳輸的成本等于模型編碼所需的比特數。否則，A還必須傳遞關于哪些執行個體被模型錯誤分類的資訊，以便B能夠重新生成相同的類别标簽。是以，總傳輸成本，即消息的描述長度為

右邊的第一項是對被錯誤分類的執行個體進行編碼所需的位數，第二項是對模型進行編碼所需的位數。α是一個用于平衡錯誤的執行個體分類和模型之間相對成本的超參數。需要注意這個方程和式（3.11）中計算泛化錯誤率的通式之間的相似之處。一個好的模型，其總描述長度要小于編碼整個類别标簽序列所需的比特數。此外，給定兩個對比模型，總描述長度較小的模型更好。習題10給出了一個如何計算決策樹的總描述長度的示例。

3.5.3　統計範圍估計

除了使用式（3.11）的方法估計模型的泛化錯誤率，還可對模型的訓練錯誤率進行統計修正，用以表明模型的複雜性。如果訓練錯誤率的機率分布是可用的或可被假設的，就可以對訓練錯誤率進行統計修正。例如，可以假設決策樹中葉結點所送出的錯誤數量服從二項分布。是以，我們可以計算用于模型選擇的訓練錯誤率上限，如下面的示例所示。

例3.10訓練錯誤率的統計界限　考慮圖3.30所示的二叉決策樹的最左側分支。觀察到TR最左側的葉結點擴充出了TL中的兩個子結點。在分裂之前，結點的訓練誤差為27=0.286。通過用正态分布近似二項分布，可以得到訓練誤差e的上界，如下式所示：

其中，α是置信水準，zα2是标準正态分布的标準值，N是用于計算e的訓練執行個體總數。當α=25%，N=7，e=27時，錯誤率的上界為eupper（7，27，0.25)=0.503，對應于7×0.503=3.521的誤差。如果擴充出這些結點的子結點，如TL所示，那麼這些子結點的訓練錯誤率分别為14=0.250和13=0.333。使用式（3.13)，這些錯誤率的上界分别為eupper（4，14，0.25)=0.537和eupper（3，13，0.25)=0.650。子結點的整體訓練誤差為4×0.537+3×0.650=4.098，大于TR中對應結點的估計錯誤率，是以認為不應該劃分TR的葉結點。

3.5.4　決策樹的模型選擇

基于以上介紹的通用方法，我們提出了兩種常用的決策樹歸納模型選擇政策。

預剪枝（早停規則）　在這種方法中，在生成一個完美适配整個訓練集的完全樹之前，樹生長算法就會停止。162為此，必須使用更為嚴格的停止條件。例如，在泛化錯誤率估計中，觀察到增益下降到某個門檻值以下時，停止擴充葉結點。泛化錯誤率的估計可以使用前面三小節給出的任何方法來計算，例如使用悲觀誤差估計、檢驗誤差估計或統計界限。預剪枝的優勢在于避免了與過度複雜的子樹的相關計算，該子樹的複雜源于過度拟合訓練資料。然而，該方法的一個主要缺點是，使用現有的劃分準則即使沒有獲得明顯的增益，但随後的劃分可能會得到更好的子樹。如果由于決策樹歸納的貪婪性質而使用預剪枝，則不會得到這樣的子樹。

後剪枝　在這種方法中，決策樹首先增長到它的最大規模。之後再對樹進行剪枝，該步驟以自下而上的方式對完全樹進行修剪。修剪可以通過用一個新的葉結點替代一個子樹或者使用最常用的分支子樹方法（稱為子樹提升方法）來完成，該葉結點的類别标簽是從隸屬于該子樹的多數類執行個體中确定的（稱為子樹替換方法）。當超過某個門檻值時，觀察到泛化錯誤率估計不再進一步改善，剪枝步驟終止。同樣，泛化錯誤率的估計可以使用前面三小節中給出的任何方法來計算。與預剪枝相比，後剪枝傾向于給出更好的結果，因為後剪枝是基于完全樹給出剪枝決策，這與預剪枝不同，後者可能會因提前終止樹的生長而受到影響。但是，對于後剪枝，在對子樹進行剪枝時，可能會浪費用于生成完全樹的額外計算。

圖3.32展示了3.3.5節中給出的Web機器人檢測示例簡化後的決策樹模型。請注意使用子樹提升方法時，在depth=1處生根的子樹被一個breadth≤7，width>3且MultiP=1的樹分支替換。另一方面，使用子樹替換方法時，對應于depth>1且MultiAgent=0的子樹被替換為配置設定給類0的一個葉結點。depth>1且MultiAgent=1的子樹保持不變。

3.6　模型評估

上一節讨論了幾種模型選擇方法，可用于從訓練集D.train中學習分類模型。在這裡，我們讨論估計其泛化性能的方法，例如，D.train之外的未知執行個體的性能。這個過程被稱為模型評估（model evaluation）。

請注意，3.5節讨論的模型選擇方法也使用訓練集D.train計算泛化性能的估計值。然而，這些估計值是未知執行個體性能的偏向名額，因為它們被用來指導分類模型的選擇。例如，如果使用驗證錯誤率進行模型選擇（如3.5.1節所述），會特意選擇能得到最少驗證集錯誤的模型作為結果。是以，驗證錯誤率可能會低估真正的泛化錯誤率，不能可靠地用于模型評估。

模型評估的正确方法是在被标注的測試集上，對學習模型的性能進行評估，且這些測試集未在模型選擇的任何階段被使用。這可以通過将整個被标記的執行個體集合D劃分為兩個不相交的子集來實作，D.train用于模型選擇，而D.test用于計算測試錯誤率errtest。下面将介紹把D劃分為D.train和D.test的兩種不同方法，并計算測試錯誤率errtest。

3.6.1　保持方法

劃分有标記資料集的最基礎技術就是保持方法，其中标記集合D被随機劃分為兩個不相交的集合，即訓練集D.train和測試集D.test。然後使用3.5節中介紹的模型選擇方法，從D.train歸納得到分類模型，并用其在D.test中的錯誤率errtest估計泛化錯誤率。用于訓練和測試的資料保留比例主要由分析師決定，例如，三分之二用于訓練，三分之一用于測試。

類似于3.5.1節将D.train劃分為D.tr和D.val時所面臨的權衡，在标記資料集中，選擇用于訓練和測試的正确比例是十分重要的。如果D.train的規模很小，使用數量不足的訓練執行個體可能學習到錯誤的分類模型，進而導緻對泛化性能的估計有偏差。另一方面，如果D.test的規模很小，那麼errtest可能不太可靠，因為它是基于少量測試執行個體計算出的。此外，當我們将D随機劃分為D.train和D.test時，errtest可能會有很大的變化。

保持方法可以多次重複後獲得測試錯誤率的分布，這種方法稱為随機子采樣（random subsampling）或重複保持方法。該方法生成的錯誤率分布有助于了解errtest的方差。

3.6.2　交叉驗證

交叉驗證是一種廣泛應用于模型評估的方法，旨在有效地利用D中所有的标記執行個體進行訓練和測試。為了說明這種方法，假設給定一個有标記的集合，将其随機地劃分為三個相同大小的子集S1、S2和S3，如圖3.33所示。第一次運作時，使用子集S2和S3訓練模型（顯示為空白塊），165并在子集S1上測試模型。是以，在第一次運作計算中，S1上的測試錯誤率表示為err（S1)。類似地，在第二次運作中，使用S1和S3作為訓練集，S2作為測試集，并計算測試錯誤率err（S2)。最後，在第三次運作中，使用S1和S2作為訓練集，S3作為測試集，并計算測試錯誤率err（S3)。總的測試錯誤率由所有運作中的子集測試錯誤率之和除以總的執行個體數後得到。這種方法被稱為三重交叉驗證。

k重交叉驗證方法一般指将标記資料D（大小為N）分割成k個相等大小的分區（或子類）的方法。在第i次運作中，D的一個分區作為D.test（i)用于測試，其餘的分區作為D.train（i)用于訓練。使用D.train（i)學習得到模型m（i)，并在D.test（i)上獲得測試錯誤率之和errsum（i)。該過程重複k次。總測試錯誤率errtest的計算如下：

是以資料集中的每個執行個體恰好用于一次測試、（k-1)次訓練。每次運作使用（k-1)/k部分的資料進行訓練，用1k部分的資料進行測試。

k重交叉驗證中k的正确選擇取決于問題的若幹特征。較小的k值使得每次運作時的訓練集較小，這将導緻所用得到的泛化錯誤率估計，比在整個标記集上訓練的模型的預期更大。166另一方面，k的取值過高會導緻每次運作時的訓練集過大，這降低了泛化錯誤率估計中的偏置。在極端情況下，當k=N時，每次運作隻使用一個資料執行個體進行測試，其餘的資料用于測試。這種k重交叉驗證的特殊情況稱為留一法（leave-one-out）。這種方法的優點是能盡可能多地利用訓練資料。但是，如習題11所示，留一法可能會在一些特殊情況下産生十分具有誤導性的結果。此外，對于大型資料集，留一法在計算上會很昂貴，因為交叉驗證程式需要重複N次。對于大多數實際應用，k在5到10之間進行選擇，可提供估計泛化錯誤率的合理方法，因為每次重複都能夠利用80％到90％的标記資料進行訓練。

如上所述，k重交叉驗證方法産生單一泛化錯誤率估計，而不提供關于估計方差的任何資訊。為了獲得這些資訊，可以對每種可能的k個資料分區運作k重交叉驗證，以此根據每個分區的計算，獲得測試錯誤率分布。使用所有可能的劃分的平均測試誤差，能得到更穩健的泛化錯誤率估計。這種估計泛化錯誤率及其方差的方法稱為完全交叉驗證（complete cross-validation）法。盡管這樣的估計非常穩健，但當資料集規模很大時，要得到所有可能的k個分區，通常代價太過昂貴。更實際的解決方案是多次重複交叉驗證方法，每次都随機将資料劃分為k個不同的分區，并使用平均測試錯誤率作為泛化錯誤率的估計。注意，由于留一法的方法隻有一種劃分可能，是以不可能估計出泛化錯誤率的方差，這是該方法的另一個限制。

k重交叉驗證不能保證每個分區中正負執行個體的比例與其在整個資料集中的比例相等。對于該問題，一個簡單的解決方法是在k個分區中，執行正負執行個體的分層抽樣，這種方法稱為分層交叉驗證（stratified cross-validation）。

在k重交叉驗證中，每次運作都會學習到不同的模型，然後對于這k個模型，聚合各模型在其測試子類上的性能，計算出總體測試錯誤率errtest。是以，errtest不反映這k個模型中任何一個模型的泛化錯誤率。相反，在一個與訓練子類N（k-1)k大小一樣的訓練集上，167它反映了模型選擇方法的預期泛化錯誤率。這與保持方法中計算的errtest不同，後者完全對應于從D.train上學習的特定模型。是以，盡管交叉驗證法有效地利用了D中的每個資料執行個體進行訓練和測試，但該方法計算出的errtest并不能代表在特定D.train上學習到的單一模型的性能。

盡管如此，errtest在實踐中，通常用于估計基于D建構的模型的泛化錯誤率。其中一個原因是當訓練子類的大小接近整體資料集時（當k很大時），errtest類似于在與D大小相同的資料集上學習到的模型的預期性能。例如，當k為10時，每個訓練子類占整體資料的90%。然後，errtest應該接近在超過90%的整體資料上學習到的模型的預期性能，即接近在D上學習到的模型的預期性能。

3.7　超參數的使用

超參數是學習算法的參數，需要在學習分類模型之前确定。例如式（3.11）中出現的超參數α，為友善起見，此處繼續使用該參數進行講解。該等式用于估計模型選擇方法的泛化錯誤率，用于明确表示模型的複雜性（見3.5.2節）。

其他有關超參數的示例，請參閱第4章。

與正常模型參數（例如決策樹内部結點中的測試條件）不同，超參數（例如α）不會出現在用于對未标記樣本進行分類的最終分類模型中。然而，超參數的取值需要在模型選擇期間被确定，該過程稱為超參數選擇（hyper-parameter selection），同時模型評估期間也需要考慮超參數。幸運的是，稍微修改前一節中描述的交叉驗證方法，就可以有效地完成這兩項任務。

3.7.1　超參數選擇

在3.5.2節中，使用驗證集來選擇α，這種方法普遍适用于超參數。設p是從有限區間P={p1，p2，…pn}中選取的超參數。168将D.train劃分為D.tr和D.val。對于每個超參數的取值pi，可以在D.tr上習得模型mi，并在D.val上獲得模型的驗證錯誤率errval（pi)。設p'是驗證錯誤率最低時的超參數值。然後選擇p'對應的m'作為最終分類模型。

盡管上述方法有用，但僅使用了整體資料的一個子集D.train進行訓練，一個子集D.val進行驗證。3.6.2節中介紹的交叉驗證架構解決了這兩個問題，盡管這種方法常用于模型評估。這裡将指出如何使用交叉驗證方法進行超參數選擇。為了介紹這種方法，将D.train分成三個部分，如圖3.34所示。每次運作時，其中一個子類作為D.val用于驗證，剩餘兩個子類作為D.tr用于訓練，每個超參數的取值為pi。對三個子類中的錯誤率求和，以此計算對應于每個pi的總體驗證錯誤率。之後，選擇驗證錯誤率最低時的超參數p'，并使用它在整個訓練集D.train上習得模型m'。

算法3.2概括了上述使用k重交叉驗證架構進行超參數選擇的方法。在第i次交叉驗證中，第i個子類的資料作為D.val（i)用于驗證（步驟4），而D.train中的其餘資料作為D.tr（i)用于訓練（步驟5）。然後，對于每個超參數的取值pi，在D.tr（i)上學習一個模型（步驟7），并應用于D.val（i)以計算其驗證誤差（步驟8）。這用于計算在所有子集上使用pi習得的模型對應的驗證錯誤率（步驟11）。驗證錯誤率最低時的超參數p'（步驟12）用于在整體訓練集D.train上學習最終模型m'（步驟13）。169是以，在該算法結束時，可以獲得超參數的最佳選擇以及最終的分類模型（步驟14），這兩者都是通過有效利用D.train中的每個資料執行個體獲得的。

3.7.2　嵌套交叉驗證

上一節提供了一種有效利用D.train中的所有執行個體來學習分類模型的方法，該方法需要進行超參數選擇。該方法可以在整個資料集D上習得最終分類模型。然而，在D上使用算法3.2隻能得到最終分類模型m'，不能估計模型的泛化性能errtest。回想一下，算法3.2使用的驗證錯誤率不能用于估計泛化性能，因為它們是用于指導最終模型m'選擇的。但是，為了計算errtest，我們可以再次使用交叉驗證架構來評估在整個資料集D上的性能，如3.6.2節所述。在這種方法中，每次交叉驗證運作時，D都被劃分為用于訓練的D.train和用于測試的D.test。當涉及超參數時，可以在每次運作時，使用算法3.2在D.train上訓練模型，進而在模型選擇“内部”使用交叉驗證。這種方法稱為嵌套交叉驗證（nested cross-validation）或雙重交叉驗證。算法3.3描述了有超參數的情況下，使用嵌套交叉驗證估計errtest的完整過程。

圖3.35将集合D劃分為D.train和D.test後使用三重交叉驗證，對該方法進行了說明。在該方法的第i次運作中，其中一個子類作為測試集D.test（i)，剩餘兩個子類作為訓練集D.train（i)。這在圖3.35中表示為第i個“外部”運作。為了使用D.train（i)選擇模型，在每次内部運作中（即疊代，共三次），将D.train（i)劃分為D.tr和D.val，然後再次使用“内部”三重交叉驗證架構。如3.7節所述，我們可以使用内部交叉驗證架構來選擇最佳超參數值p'（i)，并在D.train（i)上學習得到分類模型m'（i)。然後我們可以在D.test（i)上應用m'（i)，獲得第i個外部運作的測試誤差。通過在每個外部運作中重複該過程，我們可以計算出整個标記集D的平均測試錯誤率errtest。請注意，在上述方法中，内部交叉驗證架構用于模型選擇，而外部交叉驗證架構用于模型驗證。

3.8　模型選擇和評估中的陷阱

有效地應用模型選擇和評估，可作為學習分類模型以及評估其泛化性能的優秀工具。然而，在實際環境中有效地使用它們時，存在一些會導緻錯誤的或有誤導性的結論的陷阱。其中一些陷阱很容易了解，也很容易避免，而其他一些陷阱本質上非常微妙，難以捕捉。在下文中，我們将介紹其中的兩個陷阱，并讨論用于避免它們的最佳措施。

3.8.1　訓練集和測試集之間的重疊

對于一個沒有瑕疵的模型選擇和評估方案，基本要求之一是用于模型選擇的資料（D.train）必須與用于模型評估的資料（D.test）分開。如果兩者之間存在重疊，在D.test上計算得到的測試錯誤率errtest不能代表未知執行個體的性能。使用errtest比較分類模型的有效性可能會産生誤導，因為過于複雜的模型可能會由于模型過拟合而顯示出錯誤的errtest低取值（參見本章習題12）。

為了說明確定D.train和D.test之間不重疊的重要性，考慮屬性都是不相關的标記資料集，即這些屬性與類别标簽沒有關系。使用這些屬性時，認為分類模型沒有随機猜測的執行效果好。但是，如果測試集包含的資料執行個體（即使是少量的）用于訓練，則過于複雜的模型的性能可能比随機分類器表現得更好，即使屬性是完全無關的。正如第10章将闡述的那樣，這種情況實際上可以作為評判标準，用于檢測由于實驗設定不當而導緻的過拟合。如果模型對不相關屬性顯示出比随機分類器更好的性能，它也能展現訓練集和測試集之間的潛在回報。

3.8.2　使用驗證錯誤率作為泛化錯誤率

驗證錯誤率errval在模型選擇過程中起着重要作用，因為它提供了模型在未用于模型訓練的執行個體D.val上的“樣本外”誤差估計。是以，與用于模型選擇和超參數取值的訓練錯誤率相比（分别于3.5.1節和3.7節所述），172errval是更好的度量标準。但是，一旦驗證集用于選擇分類模型m'，errval就不再能反映出m'在未知執行個體上的性能。

為了明晰使用驗證錯誤率作為泛化性能估計時的陷阱，考慮使用驗證集D.val，從值域P中選擇出取值為p的超參數的問題。如果P中的可取值數量非常大并且D.val的規模很小，則可以随機在D.val上選擇出性能良好的超參數p'。請注意此問題與3.4.1節讨論的多重比較問題的相似性。盡管使用p'學習的分類模型m'具有較低的驗證錯誤率，但它缺乏在未知測試執行個體上的普适性。

估計模型m'的泛化錯誤率的正确方法是使用獨立選擇的測試集D.test，而該測試集未以任何方式用于影響m'的選擇。根據經驗，在模型選擇過程中不應檢查測試集，以確定不存在任何形式的過拟合。如果從标記資料集的任意部分獲得了可以改進分類模型的助力，即使是以間接的方式，那麼在測試期間也必須丢棄該部分資料。

3.9　模型比較

比較不同分類模型性能時的一個困難是，觀察到的性能差異是否具有統計顯著性。例如，考慮兩個分類模型MA和MB。假設在包含30個執行個體的測試集上進行評估時MA的準确率為85％，而MB在另一個包含5000個執行個體的測試集上的準确率為75％。基于這些資訊，MA是比MB更好的模型嗎？此示例提出了兩個關于性能名額統計顯著性的關鍵問題：

1) 盡管MA具有比MB更高的準确率，但它是在較小的測試集上進行測試的。我們可以在多大程度上認為MA實際上的準确率是85％？

2) 是否有可能解釋為，由于測試集的組成發生了變化，造成了MA和MB準确率之間的差異？

第一個問題涉及對模型準确率置信區間的估計。第二個問題涉及對觀測偏差統計顯著性的測試。本節的其餘部分将對這些問題進行研究。

3.9.1　估計準确率的置信區間

為了确定準确率置信區間，我們需要建構樣本準确率的機率分布。本節描述了通過二項式随機實驗模拟分類任務，進而獲得置信區間的方法。以下描述了該實驗的特征：

1) 随機實驗由N個獨立試驗組成，每個試驗有兩種可能的結果：成功或失敗。

2) 每次試驗的成功機率p是不變的。

二項式實驗的一個例子是計算硬币投擲N次時正面朝上的次數。如果X是在N次試驗中觀察到的成功次數，那麼X取特定值的機率由均值為Np、方差為Np（1-p)的二項式分布給出：

例如，如果擲币是公平的（p=0.5），并投擲50次，那麼出現20次正面朝上的機率為：

如果實驗重複多次，則預期的正面朝上的平均次數為50×0.5=25，方差為50×0.5×0.5=12.5。

對測試執行個體類别标簽的預測任務也可看作二項式實驗。給定一個包含N個執行個體的測試集，設X為模型正确預測的執行個體數，p為模型實際準确率。如果預測任務被模拟為二項式實驗，則X符合二項式分布，其均值為Np、方差為Np（1-p)。可以證明，實驗準确率acc=XN也符合二項式分布，其均值為p、方差為p（1-p)N（見習題14）。當N足夠大時，二項式分布可以通過正态分布來近似。根據正态分布，acc的置信區間推導如下：

其中，

是在置信水準（1-α）上通過标準正态分布獲得的上限和下限。由于标準正态分布關于Z=0對稱，是以

。重新排列該不等式，則p的置信區間如下：

下表顯示了不同置信水準下Zα2的值：

例3.11 準确率的置信區間　在100個測試執行個體上進行評估時，考慮精度為80％的模型。在95％置信水準下，其真實準确率的置信區間是多少？根據上面給出的表，95％的置信水準對應于Zα2=1.96。将該項代入式（3.16）可得到71.1％～86.7％的置信區間。下表顯示了執行個體數N增加時的置信區間：

注意，當N增加時，置信區間變得更緊密。

3.9.2　比較兩個模型的性能

考慮兩個模型M1和M2，分别在兩個獨立的測試集D1和D2上進行評估。設n1表示D1中的執行個體數，n2表示D2中的執行個體數。另外，假設M1在D1上的錯誤率為e1，M2在D2上的錯誤率為e2。我們的目标是測試從e1和e2之間觀察到的差異是否具有統計學意義。

假設n1和n2足夠大，則可以使用正态分布來估計錯誤率e1和e2。如果觀察到的錯誤率差異表示為d=e1-e2，則d也符合正态分布，175其均值為dt（真實內插補點）且方差為σ2d。方差d計算如下：

其中，

是錯誤率的方差。最後，在（1-α)％置信水準下，可以證明真實差異dt的置信區間如下式：

例3.12 顯著性檢測　考慮本節開頭描述的問題。當測試執行個體數N1=30時，模型MA的錯誤率e1=0.15；當測試執行個體數N2=5000時，模型MB的錯誤率e2=0.25。觀察到的錯誤率差異為d=0.15-0.25=0.1。在此示例中，我們正在執行雙側檢驗以檢查dt=0或dt≠0。觀察到的錯誤率差異的估計方差計算如下：

或σd=0.0655。将該值代入式（3.18），在95％置信水準下獲得dt的置信區間，如下：

當區間跨越零值時，可以得出結論，即觀察到的差異在95％置信水準下沒有統計學意義。

在什麼樣的置信水準下我們可以拒絕dt=0的假設呢？為此，我們需要确定

的值，使得dt的置信區間不跨越零值。可以将前面的計算反過來，尋找

的值，使得

。更換d和σd的值使得

<1.527。該值在

時最先出現（雙側檢驗時）。結果表明，零假設會在93.6％或更低的置信水準下被拒絕。

文獻注釋

早期的分類系統被用于組織各種對象集合，從生物體到無生命體。這樣的例子比比皆是，從亞裡士多德的物種編目，到杜威十進制。以及國家圖書館的書籍分類系統。這樣的任務通常需要相當多的人力，以識别要分類的對象的屬性，并将它們組織成易于區分的類别。

随着統計學和計算能力的發展，自動分類已成為深入研究的主題。經典統計中的分類研究有時稱為判别分析（discriminant analysis），其目标是基于對應的特征來預測對象的組成員關系。一種著名的經典方法是Fisher的線性判别分析［142］，該方法旨在找到資料的線性投影，進而在不同類别的對象之間産生最佳劃分。

許多模式識别問題也需要區分不同類别的對象。例如語音識别、手寫字元識别和圖像分類等。對模式識别分類技術的應用感興趣的讀者可以參考Jain等［150］和Kulkarni等［157］綜述文章，或Bishop［125］、Duda等［137］和Fukunaga［143］的經典模式識别書籍。分類問題也是神經網絡、統計學習和機器學習的主要研究課題。在Bishop［126］、Cherkassky和Mulier［132］、Hastie等［148］、Michie等［162］以及Murphy［167］和Mitchell［165］的書中有關于統計學和機器學習分類問題的深入讨論。最近幾年也釋出了許多公開的分類軟體包，可以嵌入Java（Weka［147］)和Python（scikit-learn［174］)等程式設計語言中。

決策樹歸納法的概述可以在Buntine［129］、Moret［166］、Murthy［168］和Safavian等［179］綜述文章中找到。一些著名的決策樹算法的示例包括CART［127］、ID3［175］、C4.5［177］和CHAID［153］。ID3和C4.5都使用熵測量作為它們的劃分函數。Quinlan［177］對C4.5決策樹算法進行了深入讨論。CART算法由Breiman等人［127］實作并使用基尼指數作為其劃分函數。CHAID［153］使用統計χ2檢驗來确定決策樹生長過程中的最佳劃分。

本章介紹的決策樹算法假設每個内部結點的劃分條件隻包含一個屬性。傾斜決策樹可以使用多個屬性，在單個結點中形成屬性測試條件［149,187］。Breiman等［127］在其CART實作中提供了一個使用屬性線性組合的選項。Heath等［149］、Murthy等［169］、Cantú-Paz和Kamath［130］，以及Utgoff和Brodley［187］提出了生成傾斜決策樹的其他方法。盡管傾斜決策樹有助于提高模型的表達能力，但同時也讓決策樹歸納的計算過程具有了一定的挑戰性。在不使用傾斜決策樹的情況下提高決策樹表達能力的另一種方法是構造歸納（constructive induction）［161］。該方法通過從原始資料建立複合特征來簡化學習複雜劃分函數的任務。

除了自頂而下的方法，其他生成決策樹的政策還包括Landeweerd等［159］、Pattipati和Alexandridis［173］的自頂而上方法，以及Kim和Landgrebe［154］的雙向方法。Schuermann和Doster［181］以及Wang和Suen［193］提出使用軟劃分标準（soft splitting criterion）來解決資料碎片問題。在該方法中，每個執行個體以不同的機率指派到決策樹的不同分支。

模型過拟合是必須解決的重要問題，以確定決策樹分類器在先前未标記的資料執行個體上具有同樣良好的性能。許多作者已經研究過模型過拟合問題，包括Breiman等［127］、Schaffer［180］、Mingers［164］、Jensen和Cohen［151］。雖然噪聲的存在通常被認為是過拟合的主要原因之一［164,170］，但Jensen和Cohen［151］認為過拟合是由于無法補償多重比較問題而出現的現象。

Bishop［126］和Hastie等［148］對模型過拟合進行了很好的讨論，将其與著名的理論分析架構聯系起來，稱為偏置方差分解［146］。在該架構中，學習算法的預測被認為是訓練集的函數，随着訓練集的改變而變化。然後根據其偏置（使用不同訓練集獲得的平均預測的誤差）、方差（使用不同訓練集獲得的預測的差異）和噪聲（問題中固有的不可簡化誤差）來描述模型的泛化錯誤率。欠拟合模型被認為具有高偏置但低方差，而過拟合模型被認為具有低偏置但高方差。盡管偏置方差分解最初是針對回歸問題提出的（其中目标屬性是連續變量），但Domingos［136］已經提出了适用于分類的統一分析方法。第4章介紹內建學習方法時，将更詳細地讨論偏置方差分解。

為了提供用于解釋學習算法的泛化性能的理論架構，已經提出了各種學習原則，例如可能近似正确（PAC）學習架構［188］。在統計學領域，已經提出了許多在模型的拟合程度和複雜度之間進行權衡的性能估計方法。178其中最值得注意的是Akaike的資訊準則［120］和貝葉斯資訊準則［182］。它們都對模型的訓練錯誤率使用校正項，以此降低複雜模型的評分。另一種廣泛用于測量一般模型複雜性的方法是VC（Vapnik-Chervonenkis）次元［190］。對于任何可能的點分布，某類函數C的VC次元定義為可以被屬于C的函數破壞的最大點數（每個點可以與其餘點區分開）。VC次元奠定了結構風險最小化原則的基礎［189］，該原理廣泛用于許多學習算法，例如将在第4章中詳細讨論的支援向量機。

奧卡姆的剃刀原則通常被認為是奧卡姆的哲學家威廉提出的。Domingos［135］告誡不要将奧卡姆剃刀誤解為比較具有相似訓練錯誤率，而不是泛化錯誤率的模型。Breslow和Aha［128］以及Esposito等［141］給出了關于避免過拟合的決策樹修剪方法的綜述。一些典型的修剪方法包括減低誤差的剪枝［176］、悲觀誤差修剪［176］、最小誤差修剪［171］、臨界值修剪［163］、代價複雜度修剪［127］和基于誤差的修剪［177］。Quinlan和Rivest提出使用最小描述長度原則對決策樹進行剪枝［178］。

本章中關于交叉驗證誤差估計重要性的讨論來自第7章中提到的Hastie等［148］。其也是了解“交叉驗證的正确和錯誤方法”的極好方法，類似于本章3.8節中關于陷阱的讨論。Krstajic等［156］提供了關于使用交叉驗證進行模型選擇和評估的一些常見陷阱的綜合讨論。

最初的用于模型評估的交叉驗證方法由Allen［121］、Stone［184］和Geisser［145］各自獨立提出。盡管交叉驗證可用于模型選擇［194］，但其用于模型選擇的方法與用于模型評估時的方法完全不同，正如Stone［184］所強調的那樣。多年來，兩種用法之間的差別經常被忽略，導緻了錯誤的發現。使用交叉驗證時常見的錯誤之一是使用整個資料集（例如，超參數調整或特征選擇）179而不是在每個交叉驗證運作的訓練子類“内”執行預處理操作。Ambroise等用許多基因表達研究作為例子，提供了在交叉驗證之外進行特征選擇時出現的選擇偏置的廣泛讨論［124］。Allison等［122］也提供了評估微陣列資料模型的可用指導。

Dudoit和van der Laan［138］較長的描述了用于超參數調整的交叉驗證協定的使用。這種方法稱為“網格搜尋交叉驗證”。正如本章3.7節所讨論的，對超參數選擇和模型評估使用交叉驗證的正确方法被Varma和Simon廣泛讨論［191］。這種組合方法在現有文獻中被稱為“嵌套交叉驗證”或“雙重交叉驗證”。近期，Tibshirani和Tibshirani［185］提出了一種新的超參數選擇和模型評估方法。Tsamardinos等［186］将這種方法與嵌套交叉驗證進行了比較。他們的實驗發現，平均而言，這兩種方法都能提供模型性能的保守估計，而Tibshirani和Tibshirani方法的計算效率更高。

Kohavi［155］進行了廣泛的實證研究，以比較使用不同估計方法（如随機子采樣和k重交叉驗證）獲得的性能名額。他們的結果表明，最佳估計方法是10重折疊分層的交叉驗證。

模型評估的另一種方法是重抽樣法，由Efron于1979年提出［139］。在該方法中，訓練執行個體在被複制過的标簽集中進行采樣，即先前被選擇為訓練集的一部分執行個體同樣可能再次被選擇。如果原始資料具有N個執行個體，則可以看出大小為N的重抽樣樣本包含原始資料中大約平均為63.2％的執行個體。未包含在自助程式示例中的執行個體将成為測試集的一部分。用于獲得訓練集和測試集的重抽樣程式重複b次，導緻測試集在第i次運作時具有不同的錯誤率err（i)。為了獲得整體錯誤率errboot，.632重抽樣（.632 bootstrap）方法将err（i)與從包含所有标記示例的訓練集獲得的錯誤率errs結合起來，如下所示：

Efron和Tibshirani等［140］提供了交叉驗證和被稱為632+規則的重抽樣方法之間的理論和實證比較。

雖然上面提出的.632重抽樣法提供了對其估計中的低方差的泛化性能的穩健估計，但是在某些條件下它可能對高度複雜的模型産生誤導性的結果，如Kohavi［155］所指出的例子。這是因為整體錯誤率并非真正的樣本外錯誤估計，因為它取決于訓練錯誤率errs，如果存在過拟合，則該值可能非常小。

目前的技術（如C4.5）要求整個訓練資料集都能裝入記憶體。為開發決策樹歸納算法的并行和可伸縮的版本，已經做了大量的工作。已提出的算法包括Mehta等［160］的SLIQ、Shafei等［183］的SPRINT、Wang和Zaniolo［192］的CMP、Alsabti等［123］的CLOUDS、Gehrke等［144］的RainForest和Joshi等［152］的ScalParC。關于資料分類和其他資料挖掘任務的并行算法綜述在文獻［158］中給出。最近，在計算統一裝置架構（CUDA）［131,134］和MapReduce［133,172］平台上實作大規模分類器已有廣泛的研究。

參考文獻

習題

1.為4個布爾屬性A、B、C和D的奇偶函數畫一棵完全決策樹。可以簡化該決策樹嗎？

2.考慮表3.5中二分類問題的訓練樣本。

（b) 計算屬性顧客ID的基尼指數值。

（c) 計算屬性性别的基尼指數值。

（d) 計算使用多路劃分屬性車型的基尼指數值。

（e) 計算使用多路劃分屬性襯衣尺碼的基尼指數值。

（f) 下面哪個屬性更好，性别、車型還是襯衣尺碼？

（g) 解釋為什麼屬性顧客ID的基尼指數值最低，但卻不能作為屬性測試條件。

3.考慮表3.6中的二分類問題的訓練樣本集。

（a) 整個訓練樣本集關于類屬性的熵是多少？

（b) 關于這些訓練樣本，a1和a2的資訊增益是多少？

（c) 對于連續屬性a3，計算所有可能的劃分的資訊增益。

（d) 根據資訊增益，哪個是最佳劃分（在a1、a2和a3中）？

（e) 根據分類錯誤率，哪個是最佳劃分（在a1和a2中）？

（f) 根據基尼指數，哪個是最佳劃分（在a1和a2中）？

4.證明：将結點劃分為更小的後繼結點之後，結點熵不會增加。

5.考慮如下二分類問題的資料集。

（a) 計算按照屬性A和B劃分時的資訊增益。決策樹歸納算法将會選擇哪個屬性？

（b) 計算按照屬性A和B劃分時的基尼指數。決策樹歸納算法将會選擇哪個屬性？

（c) 從圖3.11可以看出熵和基尼指數在區間［0，0.5］都是單調遞增的，而在區間［0.5，1］都是單調遞減的。有沒有可能資訊增益和基尼指數增益支援不同的屬性？解釋你的理由。

6.考慮使用某些屬性測試條件将父結點P拆分為兩個子結點C1和C2。每個結點上标記的訓練執行個體的組成總結在下表中。

（a) 計算父結點P的基尼指數和錯誤分類的錯誤率。

（b) 計算子結點的權重基尼指數。如果将基尼指數用作不純性測量，你會考慮這個屬性測試條件嗎？

（c) 計算子結點的權重錯誤分類率。如果使用錯誤分類率作為不純性測量，你會考慮這個屬性測試條件嗎？

7.考慮如下訓練樣本集。

（a) 用本章所介紹的貪心算法計算兩層的決策樹。使用分類錯誤率作為劃分标準。決策樹的總錯誤率是多少？

（b) 使用X作為第一個劃分屬性，兩個後繼結點分别在剩餘的屬性中選擇最佳的劃分屬性，重複步驟（a)。所構造的決策樹的錯誤率是多少？

（c) 比較（a)和（b)的結果。評述在劃分屬性選擇上啟發式貪心法的作用。

8.下表彙總了具有3個屬性A、B、C，以及兩個類标号+、-的資料集。建立一棵兩層決策樹。

（a) 根據分類錯誤率，哪個屬性應當選作第一個劃分屬性？對每個屬性給出列聯表和分類錯誤率的增益。

（b) 對根結點的兩個子結點重複以上問題。

（c) 最終的決策樹錯誤分類的執行個體數是多少？

（d) 使用C作為劃分屬性，重複（a)（b)和（c)。

（e) 使用（c)和（d)中的結果分析決策樹歸納算法的貪心本質。188

9.考慮圖3.36中的決策樹。

（a) 使用樂觀方法計算決策樹的泛化錯誤率。

（b) 使用悲觀方法計算決策樹的泛化錯誤率。（為了簡單起見，使用在每個葉結點增加因子0.5的方法。）

（c) 使用提供的驗證集計算決策樹的泛化錯誤率。這種方法叫作降低誤差剪枝（reduced error pruning)。

10.考慮圖3.37中的決策樹。假設産生決策樹的資料集包含16個二進制屬性和3個類C1、C2和C3。

根據最小描述長度原則計算每棵決策樹的總描述長度。

• 樹的整體描述長度由下式給出：Cost（tree,data)=Cost（tree)+Cost（datatree)
• 樹的每個内部結點用劃分屬性的ID進行編碼。如果有m個屬性，為每個屬性編碼的代價是log2m個二進位。
• 每個葉結點使用與之相關聯的類的ID編碼。如果有k個類，為每個類編碼的代價是log2k個二進位。
• Cost（tree)是對決策樹的所有結點編碼的開銷。為了簡化計算，可以假設決策樹的總開銷是對每個内部結點和葉結點編碼的開銷總和。
• Cost（datatree)是對決策樹在訓練集上的分類錯誤編碼的開銷。每個錯誤用log2n個二進位編碼，其中n是訓練執行個體的總數。

根據MDL原則，哪棵決策樹更好？

11.該練習受到文獻［155］的啟發，突出了留一法模型評估過程的一個已知局限性。考慮一個包含50個正執行個體和50個負執行個體的資料集，其中屬性是完全随機的，不包含有關類别标簽的資訊。是以，在該資料上學習的任何分類模型的泛化錯誤率預計均為0.5。考慮一個分類器，它将訓練執行個體的多數類别标簽（通過使用正标簽作為預設類）配置設定給所有測試執行個體，不管其屬性值如何。這種方法叫作多數誘導分類器。使用以下方法确定此分類器的錯誤率。

（a) 留一法。

（b) 雙重分層交叉驗證法，其中每個子類的類别标簽比例與整體資料保持相同。

（c) 從上面的結果來看，哪種方法能夠更可靠地評估分類器的泛化錯誤率？190

12.考慮一個包含100個資料執行個體的标記資料集，該資料執行個體被随機分為A和B兩組，每組包含50個執行個體。我們使用A作為訓練集來學習兩個決策樹，T10具有10個葉結點，T100具有100個葉結點。資料集A和B的兩個決策樹的準确率如表3.7所示。

（a) 根據表3.7中顯示的準确率，你認為哪個分類模型在未知執行個體上具有更好的性能？

（b) 現在，在整個資料集（A+B)上測試了T10和T100，發現T10在資料集（A+B)上的分類準确率為0.85，而T100在資料集（A+B)上的分類準确率為0.87。根據這些新資訊和表3.7中的觀察結果，你最終會選擇哪個分類模型進行分類？

13.考慮如下測試分類法A是否優于另一個分類法B的方法。設N是資料集的大小，pA是分類法A的準确率，pB是分類法B的準确率，而

是兩種分類法的平均準确率。為了測試分類法A是否顯著優于B，使用如下Z統計量：

如果Z>1.96，則認為分類法A優于分類法B。

表3.8在不同的資料集上比較3個不同分類法的準确率：決策樹分類法、樸素貝葉斯分類法和支援向量機。（後兩種分類法将在第4章中進行介紹。）

用下面3×3的表格來彙總表3.8中給定的分類法在資料上的分類性能：

表格中每個單元的内容包含比較行與列的兩個分類器時的赢、輸和平局的數目。

14.設X是一個均值為Np、方差為Np（1-p)的二進制随機變量。證明比率X/N也服從均值為p、方差為p（1-p)/N的二項式分布。