3.1 分類與決策樹概述3.1.1 分類與預測分類是一種應用非常廣泛的數據挖掘技術，應用的例子也很多。例如，根據信用卡支付歷史記錄，來判斷具備哪些特征的用戶往往具有良好的信用；根據某種病癥的診斷記錄，來分析哪些藥物組合可以帶來良好的治療效果。這些過程的一個共同特點是：根據數據的某些屬性，來估計一個特定屬性的值。例如在信用分析案例中，根據用戶的“年齡”、“性別”、“收入水平”、“職業”等屬性的值，來估計該用戶“信用度”屬性的值應該取“好”還是“差”，在這個例子中，所研究的屬性“信用度”是一個離散屬性，它的取值是一個類別值，這種問題在數據挖掘中被稱為分類。還有一種問題，例如根據股市交易的歷史數據估計下一個交易日的大盤指數，這里所研究的屬性“大盤指數”是一個連續屬性，它的取值是一個實數。那么這種問題在數據挖掘中被稱為預測。總之，當估計的屬性值是離散值時，這就是分類；當估計的屬性值是連續值時，這就是預測。3.1.2 決策樹的基本原理1.構建決策樹通過一個實際的例子，來了解一些與決策樹有關的基本概念。表3-1是一個數據庫表，記載著某銀行的客戶信用記錄，屬性包括“姓名”、“年齡”、“職業”、“月薪”、.、“信用等級”，每一行是一個客戶樣本，每一列是一個屬性（字段）。這里把這個表記做數據集D。銀行需要解決的問題是，根據數據集D，建立一個信用等級分析模型，并根據這個模型，產生一系列規則。當銀行在未來的某個時刻收到某個客戶的貸款申請時，依據這些規則，可以根據該客戶的年齡、職業、月薪等屬性，來預測其信用等級，以確定是否提供貸款給該用戶。這里的信用等級分析模型，就可以是一棵決策樹。在這個案例中，研究的重點是“信用等級”這個屬性。給定一個信用等級未知的客戶，要根據他/她的其他屬性來估計“信用等級”的值是“優”、“良”還是“差”，也就是說，要把這客戶劃分到信用等級為“優”、“良”、“差”這3個類別的某一類別中去。這里把“信用等級”這個屬性稱為“類標號屬性”。數據集D中“信用等級”屬性的全部取值就構成了類別集合：Class=“優”，“良”，“差”。在決策樹方法中，有兩個基本的步驟。其一是構建決策樹，其二是將決策樹應用于數據庫。大多數研究都集中在如何有效地構建決策樹，而應用則相對比較簡單。構建決策樹算法比較多，在Clementine中提供了4種算法，包括C&RT、CHAID、QUEST和C5.0。采用其中的某種算法，輸入訓練數據集，就可以構造出一棵類似于圖3.1所示的決策樹。一棵決策樹是一棵有向無環樹，它由若干個節點、分支、分裂謂詞以及類別組成。節點是一棵決策樹的主體。其中，沒有父親節點的節點稱為根節點，如圖3.1中的節點1；沒有子節點的節點稱為葉子節點，如圖3.1中的節點4、5、6、7、8。一個節點按照某個屬性分裂時，這個屬性稱為分裂屬性，如節點1按照“年齡”被分裂，這里“年齡”就是分裂屬性，同理，“職業”、“月薪”也是分裂屬性。每一個分支都會被標記一個分裂謂詞，這個分裂謂詞就是分裂父節點的具體依據，例如在將節點1分裂時，產生兩個分支，對應的分裂謂詞分別是“年齡=40”。另外，每一個葉子節點都被確定一個類標號，這里是“優”、“良”或者“差”。基于以上描述，下面給出決策樹的定義：由此可以看出，構建一棵決策樹，關鍵問題就在于，如何選擇一個合適的分裂屬性來進行一次分裂，以及如何制定合適的分裂謂詞來產生相應的分支。各種決策樹算法的主要區別也正在于此。2.修剪決策樹利用決策樹算法構建一個初始的樹之后，為了有效地分類，還要對其進行剪枝。這是因為，由于數據表示不當、有噪音等原因，會造成生成的決策樹過大或過度擬合。因此為了簡化決策樹，尋找一顆最優的決策樹，剪枝是一個必不可少的過程。通常，決策樹越小，就越容易理解，其存儲與傳輸的代價也就越小，但決策樹過小會導致錯誤率較大。反之，決策樹越復雜，節點越多，每個節點包含的訓練樣本個數越少，則支持每個節點樣本數量也越少，可能導致決策樹在測試集上的分類錯誤率越大。因此，剪枝的基本原則就是，在保證一定的決策精度的前提下，使樹的葉子節點最少，葉子節點的深度最小。要在樹的大小和正確率之間尋找平衡點。不同的算法，其剪枝的方法也不盡相同。常有的剪枝方法有預剪枝和后剪枝兩種。例如CHAID和C5.0采用預剪枝，CART則采用后剪枝。預剪枝，是指在構建決策樹之前，先制定好生長停止準則（例如指定某個評估參數的閾值），在樹的生長過程中，一旦某個分支滿足了停止準則，則停止該分支的生長，這樣就可以限制樹的過度生長。采用預剪枝的算法有可能過早地停止決策樹的構建過程，但由于不必生成完整的決策樹，算法的效率很高，適合應用于大規模問題。后剪枝，是指待決策樹完全生長結束后，再根據一定的準則，剪去決策樹中那些不具一般代表性的葉子節點或者分支。這時，可以將數據集劃分為兩個部分，一個是訓練數據集，一個是測試數據集。訓練數據集用來生成決策樹，而測試數據集用來對生成的決策樹進行測試，并在測試的過程中通過剪枝來對決策樹進行優化。3.生成原則在生成一棵最優的決策樹之后，就可以根據這棵決策樹來生成一系列規則。這些規則采用“If.，Then.”的形式。從根節點到葉子節點的每一條路徑，都可以生成一條規則。這條路徑上的分裂屬性和分裂謂詞形成規則的前件（If部分），葉子節點的類標號形成規則的后件（Then部分）。例如，圖3.1的決策樹可以形成以下5條規則：If（年齡40）and（職業=“學生” or 職業=“教師”）Then 信用等級=“優”If（年齡=40）and（月薪=40）and（月薪=1000 and 月薪=40）and（月薪3000）Then 信用等級=“優”這些規則即可應用到對未來觀測樣本的分類中了。3.2 ID3、C4.5與C5.0ID3算法是最有影響力的決策樹算法之一，由Quinlan提出。ID3算法的某些弱點被改善之后得到了C4.5算法；C5.0則進一步改進了C4.5算法，使其綜合性能大幅度提高。但由于C5.0是C4.5的商業版本，其算法細節屬于商業機密，因此沒有被公開，不過在許多數據挖掘軟件包中都嵌入了C5.0算法，包括Clementine。3.2.1 ID31.信息增益任何一個決策樹算法，其核心步驟都是為每一次分裂確定一個分裂屬性，即究竟按照哪一個屬性來把當前數據集劃分為若干個子集，從而形成若干個“樹枝”。ID3算法采用“信息增益”為度量來選擇分裂屬性的。哪個屬性在分裂中產生的信息增益最大，就選擇該屬性作為分裂屬性。那么什么是信息增益呢？這需要首先了解“熵”這個概念。熵，是數據集中的不確定性、突發性或隨機性的程度的度量。當一個數據集中的記錄全部都屬于同一類的時候，則沒有不確定性，這種情況下的熵為0。決策樹分類的基本原則是，數據集被分裂為若干個子集后，要使每個子集中的數據盡可能的“純”，也就是說子集中的記錄要盡可能屬于同一個類別。如果套用熵的概念，即要使分裂后各子集的熵盡可能的小。例如在一次分裂中，數據集D被按照分裂屬性“年齡”分裂為兩個子集D1和D2，如圖3.2所示。2.ID3算法的流程ID3算法是一個從上到下、分而治之的歸納過程。ID3算法的核心是：在決策樹各級節點上選擇分裂屬性時，通過計算信息增益來選擇屬性，以使得在每一個非葉節點進行測試時，能獲得關于被測試樣本最大的類別信息。其具體方法是：檢測所有的屬性，選擇信息增益最大的屬性產生決策樹節點，由該屬性的不同取值建立分支，再對各分支的子集遞歸調用該方法建立決策樹節點的分支，直到所有子集僅包括同一類別的數據為止。最后得到一棵決策樹，它可以用來對新的樣本進行分類。下面通過一個實例來了解一下決策樹的構建過程。表3-2是一個假想的銀行貸款客戶歷史信息（略去了客戶姓名），包含14個樣本。現要求以這14個樣本為訓練數據集，以“提供貸款”為類標號屬性，用ID3算法構造決策樹。3.ID3算法的性能分析ID3算法是一種典型的決策樹分析算法，后來發展的許多決策樹算法都是以ID3算法為基礎發展而來的。ID3算法的優點在于它構建決策樹的速度比較快，它的計算時間隨問題的難度只是線性地增加，適合處理大批量數據集。同時，ID3算法的缺點也是突出的，包括以下幾點。（1）ID3算法對訓練樣本的質量的依賴性很強，訓練樣本的質量主要是指是否存在噪聲和是否存在足夠的樣本。（2）ID3算法只能處理分類屬性（離散屬性），而不能處理連續屬性（數值屬性）。在處理連續屬性時，一般要先將連續屬性劃分為多個區間，轉化為分類屬性。例如“年齡”，要把其數值事先轉換為諸如“小于30歲”、“3050歲”、“大于50歲”這樣的區間，再根據年齡值落入了某一個區間取相應的類別值。通常，區間端點的選取包含著一定的主觀因素和大量的計算。（3）ID3算法生成的決策樹是一棵多叉樹，分支的數量取決于分裂屬性有多少個不同的取值。這不利于處理分裂屬性取值數目較多的情況。因此目前流行的決策樹算法大多采用二叉樹模型。（4）ID3算法不包含對樹的修剪，無法對決策樹進行優化。正因為ID3還存在著許多不足的地方，Quinlan對ID3算法進行了改進，并于1993年提出了ID3的改進算法C4.5。3.2.2 C4.5C4.5算法的核心思想與ID3完全相同，但在實現方法上做了更好的改進，并增加了新的功能。主要包括：采用“增益比例”來選擇分裂屬性、對連續屬性的處理、對樣本屬性值缺失情況的處理、規則的產生、交叉驗證等。1.用“增益比例”來選擇分裂屬性如前所述，ID3是采用“信息增益”來選擇分裂屬性的。雖然這是一種有效地方法，但其具有明顯的傾向性，即它傾向于選擇具有大量不同取值的屬性，從而產生許多小而純的子集。尤其是關系數據庫中作為主鍵的屬性，每個樣本都有一個不同的取值。如果以這樣的屬性作為分裂屬性，那么將產生非常多的分支，而且每一個分支產生的子集的熵均為0（因為子集中只有一個樣本！）。顯然，這樣的決策樹是沒有實際意義的。因此，Quinlan提出使用增益比例來代替信息增益。2.連續屬性的處理ID3最初的定義假設數據集的各屬性都必須是離散的。如果有連續屬性，則可以采用劃分區間的方法來離散化。假如在前面的例子中，屬性“年齡”由于是連續型屬性，被劃分為“50”3個區間，這樣屬性“年齡” 的不同取值就只有3個了，這就是被離散化的過程。在C4.5中，算法采用另外一種方法來實現連續屬性的離散化。設數據集中有一連續屬性Y，現要測試是否可以選用該屬性來對數據集進行分裂以及如何分裂（即通過計算信息增益或增益比例來確認Y是否可以作為分裂屬性，如果可以，還要確定分裂謂詞）。例如在表3-3所示的訓練數據集中，如果要計算“年齡”屬性的信息增益，則首先將不同的屬性值排序20，25，28，40，46，55，56，58，60，65，70，那么可能的閾值集合為20，25，28，40，46，55，56，58，60，65，從中一一取出，并形成分裂謂詞，例如取出“20”，形成謂詞“20”，用它們劃分訓練數據集，然后計算信息增益或增益比例。3.處理有缺失值的樣本ID3是基于所有屬性值都已經確定這一假設的。但是在實際應用中，經常會因為搜集樣本時有的樣本數據不完整，或者輸入數據是有人為的誤差等原因，一個數據集中會有某些樣本缺少一些屬性值。例如在表3-3中，有兩個樣本的“收入水平”缺失了（用“？”代替）。在用一個屬性對數據集進行劃分時，必須知道一個樣本屬于哪一類（以便于計算每類有多少個樣本，進而計算該屬性的信息增益），這是根據這個樣本的屬性值來決定的，但是由于屬性值缺失，那么該如何判斷這個樣本屬于哪一類呢？C4.5并不會武斷地將一個有缺省值的樣本拋棄（當然，樣本數量很大的時候可以這么做），也不會隨意地將它分配到某個類別中去。C4.5會根據其他已知屬性值來計算一個有缺失值的樣本屬于某個類別的概率，這個樣本可以屬于每一個類，只是概率不同而已。例如，在表3-3的14個樣本中，“收入水平”有兩個缺失值，其他的12個樣本的分布如表3-4所示。4.樹的修剪C4.5采用的修剪方法是所謂的“后剪枝”，即待決策樹完全生長結束之后，再來修剪掉那些對分類精度貢獻不大的葉子節點。對于某個節點，計算該節點分裂之前的誤分類損失（由于錯誤地預測了樣本的類別而導致的損失）和分裂成子樹之后的誤分類損失，如果分裂后的誤分類損失沒有得到顯著降低，就可以考慮修剪掉這棵子樹。在計算分類精度之前，用戶可以自行定義各種誤分類損失的權重，例如“A類樣本被誤分類為B類導致的損失”比“B類樣本誤分類為A類導致的損失”要大得多，在這種情況下就可以通過設置誤分類損失的權重來加以區分。5.規則的產生C4.5提供了將決策樹模型轉換為If-Then規則的算法。規則存儲于一個二維數組中，每一行代表一個規則。表的每一列代表樣本的一個屬性，列的值代表了屬性的不同取值。例如，0和1分別代表“小于等于閾值”和“大于閾值”。如果列值為-1，則代表規則中不包含該屬性。6.交叉驗證分類是有監督學習，通過學習可以對未知的數據進行預測。在訓練過程開始之前，將一部分數據保留下來，在訓練之后，利用這部分數據對學習的結果進行驗證，這種模型評估方法稱為交叉驗證。如果將這個“學習-驗證”的過程重復k次，就稱為k次迭代交叉驗證。首先將所有訓練數據平均分成k份，每次使用其中一份作為測試樣本，其余的k-1份數據作為學習樣本，然后選擇平均分類精度最高的樹作為最后的結果。通常，分類精度最高的樹并不是節點最多的樹。另外，交叉驗證還可以用于決策樹的修剪。k次迭代交叉驗證非常適合訓練樣本書目比較少