1.6.2　基于數據的決策樹

1.6.2.1　數據與信息

圖1.13　數據和信息

數據和信息（圖1.13）是相似的概念，但它們不是一回事。數據和信息的主要區別在于數據是“部分”，而信息是“整體”。

數據一詞的定義簡單來說就是“事實和數字”。每一個數據都是一個簡單的事實，本身并沒有什么意義。數據這個詞可以用來表示單一的事實，也可以表示一個事實的集合。它來自拉丁語datum，意思是“給定的東西”。datum一詞在技術上仍是數據的正確單數形式，但很少使用。

什么是信息？信息的定義很簡單，就是“收到或得到的消息或知識”。信息是我們對事實進行處理、解釋和組織后的結果。這個詞來自拉丁語īnfōrmātiō，意思是“構成或概念”。

數據和信息這兩個術語在不同的語境中有不同的含義，它們之間的主要區別是：

●數據是事實的集合，而信息是如何在上下文中理解這些事實。

●數據是無組織的，而信息是有結構的或有組織的。

●信息依賴于數據。

在計算機的世界里，數據是輸入，或者說我們告訴計算機做什么或保存什么。信息是輸出，或者說計算機如何解釋數據并向我們顯示所要求的行動或指令。

數據通常存在于信息之前，但很難說哪個更有用。例如，如果信息的處理或組織方式有偏差或不正確，它就沒有用，但數據仍然有用。

數據挖掘是將原始數據轉化為有用信息的過程。自信息時代開始以來，數據的積累和存儲變得更加容易和廉價。遺憾的是，隨著機器可讀數據量的增加，理解和利用這些數據的能力卻沒有跟上其增長的步伐。

數據挖掘依賴于有效的數據收集、存儲和處理。數據挖掘除了包含原始分析步驟外，還涉及數據管理、數據預處理、模型和推理、度量、復雜度、結構后處理、可視化和在線更新等方面。實際的數據挖掘任務是對大量數據進行半自動或自動分析，以提取以前未知的、有趣的模式，如數據分組（聚類分析）、異常數據（異常檢測）和依賴關系（關聯規則挖掘、順序模式挖掘）等。這些模式可以被視為對輸入數據的一種總結，并可用于進一步的分析或者用于機器學習和預測。

數據分析和數據挖掘的區別在于，數據分析用來檢驗數據集上的模型和假設，比如分析營銷活動的效果，而不管數據量有多大；相反，數據挖掘是利用機器學習和統計模型來發現大量數據中的秘密或隱藏模式。

從數據中人工提取模式的歷史已經有幾個世紀了。早期識別數據模式的方法包括貝葉斯定理（18世紀）和回歸分析（19世紀）。計算機技術的普及和日益強大極大地提高了數據收集、存儲和操作能力。隨著數據集的規模和復雜程度的增加，直接的“人工”數據分析越來越多地被間接的、自動化的數據處理所取代，這得益于計算機科學特別是機器學習領域的發現，如神經網絡、聚類分析、遺傳算法（20世紀50年代）、決策樹和決策規則（20世紀60年代）以及支持向量機（20世紀90年代）。數據挖掘是應用這些方法的過程，它彌補了從應用統計學和人工智能（通常提供數學背景）到數據庫管理的差距，利用數據庫中數據存儲和索引的方式，更有效地執行實際的學習和發現算法，使這種方法能夠應用于越來越大的數據集。

數據挖掘主要可以分為兩大類：面向驗證的（驗證用戶的假設）和面向發現的（自主發現新的規則和模式）。而后者可以進一步細分為兩個子類：描述方法和預測方法。描述方法側重于理解基礎數據的運行方式，如聚類、摘要或可視化等；而預測方法則旨在建立一個行為模型，用于獲取新的和未見過的樣本，并預測與樣本相關的一個或多個變量的值。然而，一些面向預測的方法也可以促進對數據的理解。預測方法主要有分類和回歸兩種。回歸方法將輸入空間映射到一個實值域，例如，可以根據給定特征預測對某一產品的需求。分類方法則將輸入空間映射到預定義的類別中，例如，用于將抵押貸款消費者分為好的（按時全額還貸）和壞的（延遲還貸），將電子郵件分配到“垃圾郵件”或“非垃圾郵件”，根據觀察到的病人特征（性別、血壓、是否存在某些癥狀等）進行診斷。

決策樹是一種預測模型，可以用來表示分類方法和回歸方法。當決策樹用于分類任務時，被稱為分類樹；用于回歸任務時，被稱為回歸樹。分類樹用于根據對象或實例的屬性值（如顏色、溫度、濕度或風力）將其分為一組預定義的類或行為（如打網球/不打網球），常用于金融、營銷、工程和醫學等應用領域，但并不試圖取代現有的傳統統計方法。回歸樹，顧名思義，就是用樹模型解決回歸問題，每一片葉子都輸出一個預測值。回歸問題多用來預測一個具體的數值，如房價、氣溫、PM2.5值等。

下面，我們基于Hunt算法，看看簡單的分類決策樹的構建和應用。

1.6.2.2　基于Hunt算法的分類決策樹的簡單示例

Hunt算法是許多決策樹算法的基礎，反映了決策樹“分而治之”的學習策略和基本思想。

從原則上講，給定一個訓練數據集，通過各種屬性的組合能夠構造出指數級數量的決策樹，找出最佳的決策樹在計算上是不可行的，所以決策樹是復雜度和效率之間權衡的產物。

如今實用的決策樹都采用貪心算法策略。在選擇劃分的數據屬性時，采用一系列局部最優決策來構造決策樹。其中的基礎就是Hunt算法。在Hunt算法中，通過遞歸的方式建立決策樹。主要的操作包括如下兩個通用過程：

1）假設數據集D中的全部數據都屬于一個類y，并將該節點標記為節點y。

2）假設數據集D中包括屬于多個類的訓練數據，并選擇一個屬性將訓練數據劃分為較小的子集。對于根據所選屬性設定的測試條件的每一個輸出，創建一個子節點，并依據測試結果將D中的記錄數據分布到各個子節點中，然后對每一個子節點反復執行這兩個過程。對子節點的子節點依舊遞歸調用這兩個過程，直至最后停止。

我們使用表1.3中的數據集對決策樹基礎算法的過程做詳細說明。

表1.3　關于是否購買汽車的數據

圖1.14　劃分年齡屬性的決策樹示意圖

首先，數據集D內的樣本不屬于同一個類別，且沒有在任一屬性A上取值相同。所以，我們需要選擇劃分屬性來作為決策樹的節點向下展開。如圖1.14所示，我們選擇年齡屬性作為根節點，并根據年齡屬性的不同取值（20~30、30~40、40~50）將樣本劃分為三部分。

根據年齡屬性進行劃分后，每個取值將原數據集D劃分為相應的子集，每個子集擁有各自的正類樣本和負類樣本。對于每個子集，我們可以在剩余屬性中繼續選擇劃分屬性，將決策樹向下延伸。同時，在年齡屬性的子節點中，我們發現30~40路徑對應的子樣本全為正類，那么我們就可以將該子樣本節點標記為正類“是”，且將該子節點設置為葉子節點，不再向下延伸。

重復上述操作，如圖1.15、圖1.16和圖1.17所示。圖1.17就是我們在該數據集下最終構造出的決策樹。

圖1.15　進一步劃分貸款屬性的決策樹示意圖

圖1.16　進一步劃分汽車價格屬性的決策樹示意圖

圖1.17　最終構造出的決策樹

對于構造及應用分類決策樹的整個過程，我們可以用圖1.18來描述。首先，使用訓練數據集，通過引入對應的決策樹分類算法來進行訓練，得到決策樹模型，也就是前面步驟中得到的每個葉子節點都代表一個分類的決策樹。接著，我們可以使用得到的模型來進行預測，即預測給定的數據對應的類別。

圖1.18　決策樹的訓練及預測過程示意圖

對于決策樹的預測，我們使用測試集的數據，如圖1.18所示。對于其中每一條要預測的數據，我們從年齡根節點屬性出發搜索決策樹，如圖1.19所示。

圖1.19　搜索決策樹過程的開始階段

根據年齡屬性的取值（如圖1.20所示），進入子節點是否貸款屬性，如圖1.21和圖1.22所示。

圖1.20　搜索決策樹的根節點——年齡屬性

圖1.21　根據年齡屬性值進入下一分支

圖1.22　搜索決策樹的下一節點——是否貸款屬性

在是否貸款屬性的判斷中，依照同樣的方法尋找下一個子節點。由于到達的子節點為類型節點（即葉子節點），故決策樹搜索結束，得到該條數據所屬的最終類型為“是”。如圖1.23、圖1.24所示。

圖1.23　根據是否貸款屬性值進入下一分支

圖1.24　獲得該條數據的最終預測結果