分類技術(或稱分類)是根據輸入數據集建立分類模型的系統方法。分類的例子包括決策樹分類、基於規則的分類、神經網絡、支持向量機和樸素貝葉斯分類。
首先，我們需要壹個訓練集，這個訓練集是由類標簽壹致的記錄組成的。訓練集用於建立分類模型，然後將其應用於測試集，該測試集由具有未知類別標簽的記錄組成。
根據模型的正確性和錯誤的測試記錄計數來評估分類模型的性能，並且這些計數被存儲在稱為混淆矩陣的表中。表4-2描述了二元分類問題的混合滑移矩陣。表中的每個條目fij表示具有實際類別號I但被預測為類別j的記錄的數量。例如，f01表示最初屬於類別0但被錯誤地分類為類別1的記錄的數量。根據混淆矩陣中的條目，分類模型正確預測的樣本總數為(f11+f00)，而錯誤預測的樣本總數為(f10+f01)。
類似地，分類模型的性能可以用錯誤率來表示，其定義如下:
為了解釋決策樹分類的工作原理，考慮上壹節介紹的脊椎動物分類問題的簡化版。這裏我們不把脊椎動物分為五個不同的種類，只考慮兩類:哺乳動物和非哺乳動物。假設科學家發現了壹個新物種，如何判斷它是哺乳動物還是非哺乳動物？壹種方式是根據物種的特征提出壹系列問題。第壹個問題可能是物種是冷血動物還是溫血動物。如果是冷血動物，那麽物種肯定不是哺乳動物；否則，要麽是鳥，要麽是哺乳動物。如果是恒溫，就需要問:這個物種是雌性繁殖的嗎？如果是，那壹定是哺乳動物，否則可能是非哺乳動物(鴨嘴獸和針鼴除外，它們產卵)。
上面的例子表明，分類問題可以通過提出壹系列關於檢查記錄屬性的精心構思的問題來解決。每回答壹個問題，後續的問題就會接踵而至，直到我們得到記錄的類標簽。這壹系列的問題以及這些問題的可能答案可以用決策樹的形式組織起來，決策樹是由節點和有向邊組成的層次決策樹。圖4-4顯示了哺乳動物的分類問題，樹包含三種節點。
根節點沒有內邊，但有零個或多個外邊。
壹個內部節點只有壹條輸入邊和兩條或多條輸出邊。
葉節點或終端節點。只有壹個邊緣向內，但沒有邊緣向外。
在決策樹中，每個葉節點都有壹個類別標簽。非終端節點(包括根節點和內部節點)包含屬性測試條件以分離具有不同特征的記錄。例如，在圖44中，在根節點處，體溫的屬性用於區分冷血脊椎動物和溫血脊椎動物。因為所有冷血脊椎動物都是非哺乳動物，所以使用壹個名為非嘴哺乳動物的葉節點作為根節點的右子節點。如果脊椎動物的體溫是恒定的，那麽胎生就是用來區分哺乳動物和其他溫血動物(主要是鳥類)的。
壹旦構造了決策樹，對檢查記錄進行分類就相當容易了。從樹的根節點開始，測試條件被用於檢查記錄，並且根據測試結果，選擇適當的分支，並且沿著這個分支，要麽到達另壹個內部節點，並且使用新的測試條件，要麽到達壹個葉節點。到達葉節點後，將葉節點的類標題分配給檢查記錄。例如，圖45示出了路徑，通過該路徑決策樹被用於預測火烈鳥的類別標簽，並且該路徑在類別標題為非哺乳動物的葉節點處結束。
在Hunt算法中，將訓練記錄劃分為相對純凈的子集，遞歸建立決策樹。隨它去吧是與節點T相關聯的訓練記錄集，y={y1，y2…，yc}是類標簽。Humt算法的遞歸定義如下:
(1)如果中的所有記錄都屬於同壹個類，則T是壹個葉節點，用。
(2)如果包含屬於多個類的記錄，請選擇壹個屬性測試條件將記錄劃分為更小的子集。對於測試條件的每個輸出，都會創建壹個子節點，並且中的記錄會根據測試結果分發到子節點。然後，對於每個子節點，遞歸調用該算法。為了解釋算法是如何實現的，考慮以下問題:預測貸款申請人是按時還款還是拖欠貸款。對於這個問題，可以通過考察之前借款人的貸款記錄來構建訓練數據集。在圖4-6所示的例子中，每條記錄都包含出借人的個人信息和借款人是否拖欠付款的類別標簽。
這個分類問題的初始決策樹只有壹個節點，類別標簽為“違約者=否”(見圖4-7a)，表示大部分貸款人按時還款。但是，樹需要進壹步細化，因為根節點包含兩個類的記錄。根據“所有者”測試條件，這些記錄被分成更小的子集，如圖4-7b所示。選擇屬性測試條件的原因將在後面討論。目前我們假設這是劃分數據的最佳標準。接下來，對根節點的每個子節點遞歸調用Hunt算法。從圖4-6給出的訓練數據集可以看出，所有有房的借款人都按時還款了，所以根節點的左子節點是標記為“債務人=否”的葉節點(見圖4-7b)。對於正確的孩子，我們需要繼續遞歸調用Hunt算法，直到所有記錄都屬於同壹個類。每個遞歸調用形成的決策樹如圖4-7c和圖4-7d所示。
如果屬性值的每種組合都出現在訓練數據中，並且每種組合都有算法，則是有效的。但對於大多數實際情況來說，這些假設過於苛刻，所以需要附加條件來處理以下情況。
(1)在算法的第二步中創建的子節點可能為空，即沒有與這些節點相關聯的記錄。如果沒有訓練記錄包含與此類節點相關聯的屬性值組合，則可能會發生這種情況。此時節點變成了葉節點，類標簽是其父節點上訓練記錄中的大部分類。
(2)第二步，如果與d關聯的所有記錄都有相同的屬性值(除了目標屬性)，就無法進壹步劃分這些記錄。在這種情況下，該節點是壹個葉節點，其標簽是與該節點相關聯的訓練記錄中的大多數類。
決策樹歸納的學習算法必須解決以下兩個問題。
如何拆分訓練記錄？樹增長過程的每個遞歸步驟都必須選擇壹個屬性測試條件，以將記錄分成更小的子集。為了實現這壹步，算法必須提供為不同類型的屬性指定測試條件的方法，並提供客觀的度量來評估每個測試條件。
(2)如何停止分裂過程？需要壹個結束條件來終止決策樹的生長過程。壹種可能的策略是拆分節點，直到所有記錄都屬於同壹個類或者所有記錄都具有相同的屬性值。盡管這兩個條件足以終止決策樹歸納算法，但是可以使用其他標準來提前終止樹生長過程。提前終止的優勢將在第4.4.5節討論。
決策樹歸納算法必須提供壹種方法來表示不同類型屬性的測試條件及其相應的輸出。
二元屬性的測試條件二元屬性產生兩種可能的輸出，如圖4-8所示。
由於名義屬性有多個屬性值，它的測試條件可以用兩種方式表達，如圖4-9所示。對於多路徑分割(圖4-9a)，輸出數取決於屬性的不同屬性值的數量。例如，如果屬性婚姻狀況有三個不同的屬性值——單身、已婚和離婚，那麽它的測試條件將產生壹個三向劃分。另壹方面，有些決策樹算法(如CART)只產生二元劃分，它們考慮所有+1的方法來創建k個屬性值的二元劃分。圖4-9b顯示了將婚姻狀況的屬性值分成兩個子集的三種不同的分組方法。
序數屬性序數屬性也可以產生二元或多元除法，屬性值只要不違反序數屬性值的順序就可以分組。圖410顯示了根據技術照片屬性劃分訓練記錄的不同方法。圖4-10a和圖4-10b中的分組保持了屬性值之間的序數關系，而圖4-10c中所示的分組違反了這壹性質，因為它把小和大分成壹組，把中、大數放在另壹組。
連續屬性對於連續屬性，測試條件可以是具有二進制輸出的比較測試(A
有許多指標可用於確定劃分記錄的最佳方式。這些度量是由劃分前後記錄的類別分布定義的。設p(i|t)表示給定節點T中屬於I類的記錄的比例，有時我們省略節點T，直接用它來表示這個比例。在兩類問題中，任意節點的類分布都可以寫成(，)，其中=1-。例如，考慮圖4-12中的測試條件，除法前的類分布為(0.5，0.5)，因為每個類的記錄數相等。如果用性別屬性劃分數據，子節點的類分布分別為(0.6，0.4)和(0.4，0.6)。雖然劃分後兩個類的分布不再均衡，但是子節點中仍然包含兩個類的記錄:如果按照第二個屬性vehicle type劃分，則以更高的純度劃分。
選擇最佳劃分的度量通常基於劃分後子節點的不純程度。雜質程度越低，階級分布越傾向。例如，類分布為(0，1)的節點雜質為零，而平衡分布為(0.5，0.5)的節點雜質最高。雜質指標的例子包括:
圖4-13顯示了二元分類問題的不純測度比較，p表示記錄屬於其中壹類的比例。從圖中可以看出，三種方法在類分布均衡時(即p=0.5時)都達到最大值，在所有記錄都屬於同壹類時(p = 1或0)達到最小值。下面我們給出三個雜質測量方法的計算實例。
為了確定測試條件的效果，我們需要比較父節點(劃分前)和子節點(劃分後)的不純程度。差異越大，測試條件的效果越好。增益4是可用於確定除法效果的標準:
考慮圖4-14中的圖表。假設有兩種方法可以將數據分成更小的子集。在除法之前，Gimi索引等於0.5，因為屬於兩個類的記錄數量相等。如果選擇屬性A劃分數據，節點N1的Gi指數等於0.4898，而N2的Gimi指數等於0.480，派生節點的基尼指數加權平均值為(7/12)×0.4898+(5/2)×0.480 = 0.486。同樣，我們可以計算出屬性B的基尼指數加權平均值為0.371。因為屬性B具有較小的基尼指數，所以屬性A是優選的..
熵和基尼指數等雜質度量往往有利於具有大量不同值的屬性。圖4-12顯示了三種可選的測試條件，並劃分了本章練習2中的數據集。與第二個測試條件相比，很容易看出車輛模型似乎提供了壹種更好的劃分數據的方法，因為它產生了更純的派生節點。但是，如果將這兩個條件與客戶D進行比較，後者似乎會產生更純粹的劃分，但客戶D並不是壹個預測屬性，因為每個樣本在該屬性上的值都是唯壹的。即使在不太極端的情況下，也不希望產生大量的輸出測試條件，因為與每個分區相關聯的記錄太少，無法做出可靠的預測。
有兩種策略可以解決這個問題。第壹種策略是將測試條件限制為二分劃分，這是CART等決策樹算法采用的策略。另壹個策略是修改評估劃分的標準，並考慮由屬性測試條件生成的輸出數量。例如，決策樹算法C4.5使用稱為增益比的分區標準來評估分區。增益率定義如下:
決策樹建立後，可以對其進行剪枝，以減小決策樹的規模。如果決策樹太大，就容易受到所謂的過擬合現象的影響。修剪通過修剪初始決策樹的分支，有助於提高決策樹的泛化能力。過擬合和樹修剪將在4.4節中詳細討論。
Web挖掘是利用數據挖掘技術從Web訪問日誌中提取有用的模式。這些模式可以揭示站點訪問者的壹些有趣的特征:例如，壹個人經常訪問壹個網站並打開壹個介紹相同產品的頁面。如果商家提供壹些優惠或者免運費，這個人很可能會購買這個產品。
在Web使用挖掘中，區分用戶訪問和Web機器人訪問是非常重要的。Web robot(也稱為Web crawler)是壹個軟件程序，它可以自動跟蹤網頁中嵌入的超鏈接，定位並獲取互聯網上的信息。這些程序安裝在搜索索引的入口處，收集索引網頁所需的文檔。在應用Web挖掘技術分析人類瀏覽習慣之前，需要過濾掉Web機器人的訪問權限。
下面是決策樹歸納算法的重要特征的總結。
(1)決策樹歸納是壹種構造分類模型的非參數方法。換句話說，它不需要任何先驗假設，也不假設類和其他屬性服從某種概率分布(不像第五章介紹的壹些技術)。
(2)尋找最佳決策樹是NP完全的。許多決策樹算法使用啟發式方法來指導假設空間的搜索。例如，4.3.5節中介紹的算法使用貪婪的自頂向下遞歸劃分策略來構建決策樹。
(3)開發的決策樹構造技術不需要昂貴的計算成本，即使訓練集很大，也能快速建立模型。另外，決策樹壹旦建立，對未知樣本的分類速度非常快，最壞情況下的時間復雜度為O(w)，其中w是樹的最大深度。
(4)決策樹相對容易解釋，尤其是小決策樹。在許多簡單數據集上，決策樹的準確率也可以媲美其他分類算法。
(5)決策樹是學習離散值函數的典型代表。但不能很好地推廣到壹些具體的布爾問題。壹個著名的例子是奇偶函數，當奇數(偶數)布爾屬性為真時，其值為0(1)。這種函數的精確建模需要壹個具有2 d節點的完整決策樹，其中d是布爾屬性的數量(參見本章中的練習1)。
(6)決策樹算法對噪聲幹擾相當魯棒，特別是在采用了避免過擬合的方法後。避免過度擬合的方法將在第4.4節中介紹。
(7)元冗余屬性不會對決策樹的準確性產生不利影響。如果壹個屬性與數據中的另壹個屬性密切相關，則該屬性是多余的。在這兩個冗余屬性中，如果其中壹個被選作除法屬性，另壹個將被忽略。但是，如果數據集包含許多不相關的屬性(即對分類任務無用的屬性)，那麽在構建樹的過程中可能會意外地選擇壹些不相關的屬性，從而產生壹個龐大的決策樹。通過在預處理階段刪除不相關的屬性，特征選擇技術可以幫助提高決策樹的準確性。我們將在4.4.3節中檢查過多不相關屬性的問題。
(8)由於大部分決策樹算法采用自頂向下的遞歸劃分方法，所以沿著樹往下的記錄會越來越少。在葉節點，可能記錄太少，無法統計判斷葉節點所代表的類別。這就是所謂的數據碎片問題。解決這個問題的壹個可行方法是當樣本數小於某個值時停止分裂。
(9)決策樹中的子樹可能多次重復，如圖4-19所示，這使得決策樹過於復雜，可能更難解釋。當決策樹的每個內部節點依賴於單個屬性測試條件時，就會發生這種情況。由於大多數決策樹算法采用分而治之的策略，在屬性空間的不同部分可以使用相同的測試條件，這就導致了子樹重復的問題。
(10)到目前為止，本章介紹的測試條件壹次只涉及壹個屬性。這樣，決策樹的生長過程就可以看作是將屬性空間劃分為互不相交的區域，直到每個區域只包含同類記錄的過程(見圖4-20)。兩個不同類別的相鄰區域之間的邊界稱為決策邊界。由於試紙條涉及單壹屬性，決策邊界是壹條直線，即平行於“坐標軸”，限制了決策樹對連續屬性間復雜關系的建模能力。圖4-21顯示了壹個數據集，使用壹個每次只涉及壹個屬性的測試條件的決策樹算法很難對其進行有效分類。
斜決策樹可以克服上述限制，因為它允許測試條件涉及多個屬性。圖4-21中的數據集可以很容易地用斜決策樹來表示，它只有壹個節點，其測試條件如下:
x+y & lt；1
雖然這種技術具有更強的表達能力，可以產生更緊湊的決策樹，但為給定節點尋找最佳測試條件的計算可能相當復雜。
構造歸納提供了另壹種將數據劃分為同質非矩形區域的方法(參見2.3.5節)，這種方法創建復合屬性，並表示現有屬性的算術或邏輯組合。新的屬性提供了更好的區分類別的能力，並將其擴展到決策樹歸納之前的數據集。與斜決策樹不同，構造歸納並不昂貴，因為在構造決策樹之前，只需要壹次性確定屬性的所有相關組合。相比之下，當擴展每個內部節點時，斜決策樹需要動態確定正確的屬性組合。但是構造歸納會產生冗余屬性，因為新創建的屬性是已有屬性的組合。
(11)的研究表明，雜質度量方法的選擇對決策樹算法的性能影響不大，因為很多度量方法是相互壹致的，如圖4-13所示。事實上，與雜質度量的選擇相比，樹修剪對最終決策樹的影響更大。