第3章

分類與預測第3章

分類與預測主要內容分類與決策樹概述ID3、C4.5與C5.0CART主要內容分類與決策樹概述分類VS.預測分類和預測是兩種數據分析形式，用于提取描述重要數據類或預測未來的數據趨勢的模型分類：預測類對象的分類標號（或離散值）根據訓練數據集和類標號屬性，構建模型來分類現有數據，并用來分類新數據預測：建立連續函數值模型比如預測空缺值，或者預測顧客在計算機設備上的花費典型應用欺詐檢測、市場定位、性能預測、醫療診斷分類是一種應用非常廣泛的數據挖掘技術分類與預測的區別：當估計的屬性值是離散值時，這就是分類；當估計的屬性值是連續值時，這就是預測。分類VS.預測分類和預測是兩種數據分析形式，用于提取描述分類和預測---示例分類銀行貸款員需要分析數據，來弄清哪些貸款申請者是安全的，哪些是有風險的（將貸款申請者分為“安全”和“有風險”兩類）我們需要構造一個分類器來預測類屬編號，比如預測顧客屬類預測銀行貸款員需要預測貸給某個顧客多少錢是安全的構造一個預測器，預測一個連續值函數或有序值，常用方法是回歸分析分類和預測---示例分類數據分類——一個兩步過程(1)第一步，也成為學習步，目標是建立描述預先定義的數據類或概念集的分類器分類算法通過分析或從訓練集“學習”來構造分類器。訓練集由數據庫元組（用n維屬性向量表示）和他們相對應的類編號組成；假定每個元組屬于一個預定義的類訓練元組：訓練數據集中的單個元組學習模型可以用分類規則、決策樹或數學公式的形式提供數據分類——一個兩步過程(1)第一步，也成為學習步，目標是數據分類——一個兩步過程(2)第二步，使用模型，對將來的或未知的對象進行分類首先評估模型的預測準確率對每個測試樣本，將已知的類標號和該樣本的學習模型類預測比較模型在給定測試集上的準確率是正確被模型分類的測試樣本的百分比測試集要獨立于訓練樣本集，否則會出現“過分擬合”的情況數據分類——一個兩步過程(2)第二步，使用模型，對將來的或第一步——建立模型訓練數據集分類算法IFrank=‘professor’ORyears>6THENtenured=‘yes’分類規則第一步——建立模型訓練數分類算法IFrank=‘pro第二步——用模型進行分類分類規則測試集未知數據(Jeff,Professor,4)Tenured?第二步——用模型進行分類分類規則測試集未知數據(Jeff,監督學習VS.無監督學習監督學習（用于分類）模型的學習在被告知每個訓練樣本屬于哪個類的“指導”下進行新數據使用訓練數據集中得到的規則進行分類無監督學習（用于聚類）每個訓練樣本的類編號是未知的，要學習的類集合或數量也可能是事先未知的通過一系列的度量、觀察來建立數據中的類編號或進行聚類監督學習VS.無監督學習監督學習（用于分類）數據預測的兩步過程數據預測也是一個兩步的過程，類似于前面描述的數據分類對于預測，沒有“類標號屬性”要預測的屬性是連續值，而不是離散值，該屬性可簡稱“預測屬性”E.g.銀行貸款員需要預測貸給某個顧客多少錢是安全的預測器可以看作一個映射或函數y=f(X)其中X是輸入；y是輸出，是一個連續或有序的值與分類類似，準確率的預測，也要使用單獨的測試集數據預測的兩步過程數據預測也是一個兩步的過程，類似于前面描述3.1決策樹概述決策樹(DecisionTree)

一種描述概念空間的有效的歸納推理辦法。基于決策樹的學習方法可以進行不相關的多概念學習，具有簡單快捷的優勢，已經在各個領域取得廣泛應用。決策樹是一種樹型結構，其中每個內部結點表示在一個屬性上的測試，每個分支代表一個測試輸出，每個葉結點代表一種類別。3.1決策樹概述決策樹(DecisionTree)決策決策樹學習是以實例為基礎的歸納學習。從一類無序、無規則的事物（概念）中推理出決策樹表示的分類規則。概念分類學習算法：來源于Hunt,Marin和Stone于1966年研制的CLS學習系統，用于學習單個概念。1979年,J.R.Quinlan給出ID3算法，并在1983年和1986年對ID3進行了總結和簡化，使其成為決策樹學習算法的典型。Schlimmer和Fisher于1986年對ID3進行改造，在每個可能的決策樹節點創建緩沖區，使決策樹可以遞增式生成，得到ID4算法。1988年，Utgoff在ID4基礎上提出了ID5學習算法，進一步提高了效率。1993年，Quinlan進一步發展了ID3算法，改進成C4.5算法。另一類決策樹算法為CART，與C4.5不同的是，CART的決策樹由二元邏輯問題生成，每個樹節點只有兩個分枝，分別包括學習實例的正例與反例。其基本思想是以信息熵為度量構造一棵熵值下降最快的樹，到葉子節點處的熵值為零，此時每個葉節點中的實例都屬于同一類。決策樹學習是以實例為基礎的歸納學習。決策樹學習采用的是自頂向下的遞歸方法。決策樹的每一層節點依照某一屬性值向下分為子節點，待分類的實例在每一節點處與該節點相關的屬性值進行比較，根據不同的比較結果向相應的子節點擴展，這一過程在到達決策樹的葉節點時結束，此時得到結論。從根節點到葉節點的每一條路經都對應著一條合理的規則，規則間各個部分（各個層的條件）的關系是合取關系。整個決策樹就對應著一組析取的規則。決策樹學習算法的最大優點是，它可以自學習。在學習的過程中，不需要使用者了解過多背景知識，只需要對訓練例子進行較好的標注，就能夠進行學習。如果在應用中發現不符合規則的實例，程序會詢問用戶該實例的正確分類，從而生成新的分枝和葉子，并添加到樹中。決策樹學習采用的是自頂向下的遞歸方法。樹是由節點和分枝組成的層次數據結構。節點用于存貯信息或知識，分枝用于連接各個節點。樹是圖的一個特例，圖是更一般的數學結構，如貝葉斯網絡。

決策樹是描述分類過程的一種數據結構，從上端的根節點開始，各種分類原則被引用進來，并依這些分類原則將根節點的數據集劃分為子集，這一劃分過程直到某種約束條件滿足而結束。

根結點個子大可能是松鼠可能是老鼠可能是大象在水里會吱吱叫鼻子長脖子長個子小不會吱吱叫鼻子短脖子短可能是長頸鹿在陸地上可能是犀牛可能是河馬樹是由節點和分枝組成的層次數據結構。節點用于存貯信息或知識，可以看到，一個決策樹的內部結點包含學習的實例，每層分枝代表了實例的一個屬性的可能取值，葉節點是最終劃分成的類。如果判定是二元的，那么構造的將是一棵二叉樹，在樹中每回答一個問題就降到樹的下一層，這類樹一般稱為CART（ClassificationAndRegressionTree）。判定結構可以機械的轉變成產生式規則。可以通過對結構進行廣度優先搜索，并在每個節點生成“IF…THEN”規則來實現。如圖6-13的決策樹可以轉換成下規則：

IF“個子大”THENIF“脖子短”THENIF“鼻子長”THEN可能是大象形式化表示成

根結點個子大可能是松鼠可能是老鼠可能是大象在水里會吱吱叫鼻子長脖子長個子小不會吱吱叫鼻子短脖子短可能是長頸鹿在陸地上可能是犀牛可能是河馬可以看到，一個決策樹的內部結點包含學習的實例，每層分枝代表了構造一棵決策樹要解決四個問題：收集待分類的數據，這些數據的所有屬性應該是完全標注的。設計分類原則，即數據的哪些屬性可以被用來分類，以及如何將該屬性量化。分類原則的選擇，即在眾多分類準則中，每一步選擇哪一準則使最終的樹更令人滿意。設計分類停止條件，實際應用中數據的屬性很多，真正有分類意義的屬性往往是有限幾個，因此在必要的時候應該停止數據集分裂：該節點包含的數據太少不足以分裂，繼續分裂數據集對樹生成的目標(例如ID3中的熵下降準則)沒有貢獻，樹的深度過大不宜再分。通用的決策樹分裂目標是整棵樹的熵總量最小，每一步分裂時，選擇使熵減小最大的準則，這種方案使最具有分類潛力的準則最先被提取出來構造一棵決策樹要解決四個問題：預測變量目標變量記錄樣本類標號屬性類別集合：Class={“優”，“良”，“差”}決策樹的基本原理預測變量目標變量類標號屬性類別集合：Class={“優”，“根節點葉子節點分裂屬性分裂謂詞每一個葉子節點都被確定一個類標號根節點葉子節點分裂屬性分裂謂詞每一個葉子節點都被確定一個類每一個節點都代表了一個數據集。根節點1代表了初始數據集D其它節點都是數據集D的子集。例如，節點2代表數據集D中年齡小于40歲的那部分樣本組成的數據集。子節點是父節點的子集。

If(年齡<40)and(職業=“學生”or職業=“教師”)Then信用等級=“優”If(年齡<40)and(職業!=“學生”and職業!=“教師”)Then信用等級=“良”If(年齡≥40)and(月薪<1000)Then信用等級=“差”If(年齡≥40)and(月薪≥1000and月薪≤3000)Then信用等級=“良”If(年齡≥40)and(月薪>3000)Then信用等級=“優”每一個節點都代表了一個數據集。決策樹是指具有下列三個性質的樹：每個非葉子節點都被標記一個分裂屬性Ai；每個分支都被標記一個分裂謂詞，這個分裂謂詞是分裂父節點的具體依據；每個葉子節點都被標記一個類標號Cj∈C。任何一個決策樹算法，其核心步驟都是為每一次分裂確定一個分裂屬性，即究竟按照哪一個屬性來把當前數據集劃分為若干個子集，從而形成若干個“樹枝”。決策樹是指具有下列三個性質的樹：熵，是數據集中的不確定性、突發性或隨機性的程度的度量。當一個數據集中的記錄全部都屬于同一類的時候，則沒有不確定性，這種情況下的熵就為0。決策樹分裂的基本原則是，數據集被分裂為若干個子集后，要使每個子集中的數據盡可能的“純”，也就是說子集中的記錄要盡可能屬于同一個類別。如果套用熵的概念，即要使分裂后各子集的熵盡可能的小。3.2ID3、C4.5與C5.0熵，是數據集中的不確定性、突發性或隨機性的程度的度量。3.2ID3=>C4.5=>C5.0RossQuinlanID31986年C4.51993年C5.01998年2011年獲得KDD創新獎/Personal///download.html/ID3=>C4.5=>C5.0RossQuinlan數據集D被按照分裂屬性“年齡”分裂為兩個子集D1和D2

信息增益:Gain(D,年齡)=H(D)–[P(D1)×H(D1)+P(D2)×H(D2)]數據集D被按照分裂屬性“年齡”分裂為兩個子集D1和D2信顯然，如果D1和D2中的數據越“純”，H(D1)和H(D2)就越小，信息增益就越大，或者說熵下降得越多。按照這個方法，測試每一個屬性的信息增益，選擇增益值最大的屬性作為分裂屬性。顯然，如果D1和D2中的數據越“純”，H(D1)和H(D2)信息熵計算舉例令C1對應“是”，C2對應“否”。那么C1有9個樣本，C2有5個樣本，所以數據集D的熵為：信息熵計算舉例令C1對應“是”，C2對應“否”。那么C1有9決策樹歸納策略(1)輸入數據劃分D是訓練元組和對應類標號的集合attribute_list,候選屬性的集合Attribute_selection_method，指定選擇屬性的啟發性過程算法步驟樹以代表訓練樣本的單個節點（N）開始如果樣本都在同一個類，則該節點成為樹葉，并用該類標記否則，算法調用Attribute_selection_method，選擇能夠最好的將樣本分類的屬性；確定“分裂準則”，指出“分裂點”或“分裂子集”。決策樹歸納策略(1)輸入決策樹歸納策略(2)對測試屬性每個已知的值，創建一個分支，并以此劃分元組算法使用同樣的過程，遞歸的形成每個劃分上的元組決策樹。一旦一個屬性出現在一個節點上，就不在該節點的任何子節點上出現遞歸劃分步驟停止的條件劃分D（在N節點提供）的所有元組屬于同一類沒有剩余屬性可以用來進一步劃分元組——使用多數表決沒有剩余的樣本給定分支沒有元組，則以D中多數類創建一個樹葉決策樹歸納策略(2)對測試屬性每個已知的值，創建一個分支，屬性選擇度量屬性選擇度量是一種選擇分裂準則，將給定類標號的訓練元組最好的進行劃分的方法理想情況，每個劃分都是“純”的，即落在給定劃分內的元組都屬于相同的類屬性選擇度量又稱為分裂準則常用的屬性選擇度量信息增益增益率Gini指標屬性選擇度量屬性選擇度量是一種選擇分裂準則，將給定類標號的訓信息增益(1)S是一個訓練樣本的集合，該樣本中每個集合的類編號已知。每個樣本為一個元組。有個屬性用來判定某個訓練樣本的類編號假設S中有m個類，總共s個訓練樣本，每個類Ci有si個樣本(i＝1,2,3...m)，那么任意一個樣本屬于類Ci的概率是si/s，那么用來分類一個給定樣本的期望信息是：信息增益(1)S是一個訓練樣本的集合，該樣本中每個集合的類信息增益(2)一個有v個值的屬性A{a1,a2,...,av}可以將S分成v個子集{S1,S2,...,Sv}，其中Sj包含S中屬性A上的值為aj的樣本。假設Sj包含類Ci的sij個樣本。根據A的這種劃分的期望信息稱為A的熵A上該劃分的獲得的信息增益定義為：具有高信息增益的屬性，是給定集合中具有高區分度的屬性。所以可以通過計算S中樣本的每個屬性的信息增益，來得到一個屬性的相關性的排序。信息增益(2)一個有v個值的屬性A{a1,a2,...,a若以“年齡”作為分裂屬性，則產生三個子集（因為該屬性有三個不同的取值），所以D按照屬性“年齡”劃分出的三個子集的熵的加權和為：其中有一個子集的熵為0若以“年齡”作為分裂屬性，則產生三個子集（因為該屬性有三個不同理，若以“收入水平”為分裂屬性：同理，若以“收入水平”為分裂屬性：若以“有固定收入”為分裂屬性：若以“VIP”為分裂屬性：若以“有固定收入”為分裂屬性：以“年齡”作為分裂屬性，所得信息增益最大。葉子節點以“年齡”作為分裂屬性，所得信息增益最大。葉子節點第3章-分類與決策樹分析課件ID3的主要缺點ID3算法只能處理分類屬性（離散屬性），而不能處理連續屬性（數值屬性）。在處理連續屬性時，一般要先將連續屬性劃分為多個區間，轉化為分類屬性。例如“年齡”，要把數值事先轉換為諸如“小于30歲”、“30至50歲”、“大于50歲”這樣的區間，再根據年齡值落入了某一個區間取相應的類別值。通常，區間端點的選取包含著一定的主觀因素。ID3生成的決策樹是一棵多叉樹，分支的數量取決于分裂屬性有多少個不同的取值。這不利于處理分裂屬性取值數目較多的情況。因此目前流行的決策樹算法大多采用二叉樹模型。ID3的主要缺點ID3算法只能處理分類屬性（離散屬性），而不ID3是采用“信息增益”來選擇分裂屬性的。雖然這是一種有效的方法，但其具有明顯的傾向性，即它傾向于選擇具有大量不同取值的屬性，從而產生許多小而純的子集。尤其是關系數據庫中作為主鍵的屬性，每一個樣本都有一個不同的取值。如果以這樣的屬性作為分裂屬性，那么將產生非常多的分支，而且每一個分支產生的子集的熵均為0（因為子集中只有一個樣本！）。顯然，這樣的決策樹是沒有實際意義的。因此，Quinlan提出使用增益比例來代替信息增益。3.2.2C4.5ID3是采用“信息增益”來選擇分裂屬性的。雖然這是一種有效的設S代表訓練數據集，由s個樣本組成。A是S的某個屬性，有m個不同的取值，根據這些取值可以把S劃分為m個子集，Si表示第i個子集（i=1,2,…,m），|Si|表示子集Si中的樣本數量。那么：稱為“數據集S關于屬性A的熵”。設S代表訓練數據集，由s個樣本組成。A是S的某個屬性，有m個用來衡量屬性A分裂數據集的廣度和均勻性。樣本在屬性A上的取值分布越均勻，Split_Info(S,A)的值就越大。增益比例的定義為：增益比例消除了選擇那些值較多且均勻分布的屬性作為分裂屬性的傾向性。用來衡量屬性A分裂數據集的廣度和均勻性。樣本在屬性A上的取值連續屬性的處理

設屬性Y有m個不同的取值，按大小順序升序排列為v1<v2<,…,<vm。從{v1,v2,…,vm-1}中選擇一個vi作為閾值，則可以根據“Y≤vi”和“Y>vi”將數據集劃分為兩個部分，形成兩個分支。顯然，{v1,v2,…,vm-1}就是可能的閾值的集合，共(m-1)個元素。把這些閾值一一取出來，并根據“Y≤vi”和“Y>vi”把訓練數據集劃分為兩個子集，并計算每一種劃分方案下的信息增益或增益比例，選擇最大增益或增益比例所對應的那個閾值，作為最優的閾值。可以看出，如果選擇連續屬性作為分裂屬性，則分裂后只有兩個分支，而不象離散屬性那樣可能會有多個分支（由離散屬性的取值個數決定）。

連續屬性的處理設屬性Y有m個不同的取值，按大小順序升序排列第3章-分類與決策樹分析課件如果要計算“年齡”屬性的信息增益，則首先將不同的屬性值排序{20,25,28,40,46,55,56,58,60,65,70}那么可能的閾值集合為{20,25,28,40,46,55,56,58,60,65,70}，從中一一取出，并形成分裂謂詞，例如取出“20”，形成謂詞“≤20”和“>20”，用它們劃分訓練數據集，然后計算信息增益或增益比例。如果要計算“年齡”屬性的信息增益，則首先將不同的屬性值排序{處理有缺失值的樣本

C4.5并不會武斷地將一個有缺失值的樣本拋棄,也不會隨意地將它分配到某個類別中去。“收入水平”的值，取為“高”的概率為3/12，取為“中”的概率為5/12，取為“低”的概率為4/12。S1（收入水平=“高”）的樣本數量為：3+2×(3/12)；處理有缺失值的樣本C4.5并不會武斷地將一個有缺失值的樣本3.2.4C5.0算法C5.0是經典的決策樹模型的算法之一，可生成多分支的決策樹，目標變量為分類變量使用c5.0算法可以生成決策樹（decisiontree）或者規則集（rule

sets）。C5.0模型根據能夠帶來最大信息增益（informationgain）的字段拆分樣本。第一次拆分確定的樣本子集隨后再次拆分，通常是根據另一個字段進行拆分，這一過程重復進行直到樣本子集不能再被拆分為止。最后，重新檢驗最低層次的拆分，那些對模型值沒有顯著貢獻的樣本子集被剔除或者修剪。

3.2.4C5.0算法C5.0是經典的決策樹模型的算法C5.0的優點優點：C5.0模型在面對數據遺漏和輸入字段很多的問題時非常穩健。C5.0模型通常不需要很長的訓練次數進行估計。C5.0模型比一些其他類型的模型易于理解，模型推出的規則有非常直觀的解釋。C5.0也提供強大的增強技術以提高分類的精度。C5.0算法選擇分支變量的依據以信息熵的下降速度作為確定最佳分支變量和分割閥值的依據。信息熵的下降意味著信息的不確定性下降C5.0的優點優點：舉例：在Clementine中應用C5.0這里，以學生參加某次社會公益活動的數據（文件名為Students.xls）為例，講解C5.0算法的具體實現操作。分析目標是，研究哪些因素將顯著影響到學生參與社會公益活動。其中，是否參加為輸出變量，除編號以外的變量均為輸入變量。舉例：在Clementine中應用C5.0這里，以學生參加某數據流如下：數據流如下：一、建立模型第一步建立數據源，第二步選擇Modeling卡中的C5.0節點并將其連接到恰當位置，鼠標右擊該節點，彈出下面窗口。模型名稱（Modelname）輸出類型（Outputtype）：此處指定希望最終生成的模型是決策樹還是規則集。群體字符（Groupsymbolics）。如果選擇該選項，C5.0會嘗試將所有與輸出字段格式相似的字符值合并。如果沒有選擇該選項，C5.0會為用于拆分母節點的字符字段的每個值創建一個子節點。使用自舉法（Useboosting）：提高其精確率。這種方法按序列建立多重模型。第一個模型以通常的方式建立。隨后，建立第二個模型，聚焦于被第一個模型錯誤分類的記錄。以此類推，最后應用整個模型集對樣本進行分類，使用加權投票過程把分散的預測合并成綜合預測。TheNumberoftrials選項允許控制用于助推的模型數量。一、建立模型第一步建立數據源，第二步選擇Model交叉驗證（Cross－validate）：如果選擇了該選項，C5.0將使用一組基于訓練數據子集建立的模型，來估計基于全部數據建立的模型的精確度。如果數據集過小，不能拆分成傳統意義上的訓練集和測試集，這將非常有用。或用于交叉驗證的模型數目。模式（Mode）：對于簡單的訓練，絕大多數C5.0參數是自動設置。高級訓練模式選項允許對訓練參數更多的直接控制。第3章-分類與決策樹分析課件簡單模式選項（simple）偏好（Favor）：在accuracy下，C5.0會生成盡可能精確的決策樹。在某些情況下，這會導致過度擬和。選擇Generality（一般化）項以使用不易受該問題影響的算法設置。期望噪聲百分數（Expectednoise（%））：指定訓練集中的噪聲或錯誤數據期望比率。簡單模式選項（simple）高級模式選項修剪純度（pruningseverity）：決定生成決策樹或規則集被修剪的程度。提高純度值將獲得更小，更簡潔的決策樹。降低純度值將獲得更加精確的決策樹。子分支最少記錄數（Minimumrecordsperchildbranch）：子群大小可以用于限制決策樹任一分支的拆分數。只有當兩個或以上的后序子分支包括來自訓練集的記錄不少于最小記錄數，決策樹才會繼續拆分。默認值為2，提高該值將有助于避免噪聲數據的過度訓練。全局修剪（Useglobalpruning）：第一階段：局部修建第二階段：全局修剪排除屬性（Winnowattributes）：如果選擇了該選項，C5.0會在建立模型前檢驗預測字段的有用性。被發現與分析無關的預測字段將不參與建模過程。這一選項對有許多預測字段元的模型非常有用，并且有助于避免過度擬和。高級模式選項圖1指定錯誤歸類損失錯誤歸類損失允許指定不同類型預測錯誤之間的相對重要性。錯誤歸類損失矩陣顯示預測類和實際類每一可能組合的損失。所有的錯誤歸類損失都預設設置為1.0。要輸入自定義損失值，選擇Usemisclassificationcosts，然后把自定義值輸入到損失矩陣中。圖1指定錯誤歸類損失錯誤歸類損失允許指定不同類型預測錯誤之具體設置具體設置執行結果執行結果二、預測結果為觀測C5.0對每個樣本的預測結果，可在流管理器的Models卡中，鼠標右擊C5.0模型結果，選擇彈出菜單中的AddToStream，并將模型結果連接到數據流中，然后連接Table節點查看預測結果，如下圖所示：二、預測結果為觀測C5.0對每個樣本的預測結果，可在三、C5.0模型評價三、C5.0模型評價CART分類回歸樹CART(ClassificationandRegressionTrees)1984<<ClassificationandRegressionTrees>>L.Breiman，J.Friedman，R.Olshen和C.Stone/~breiman//~jhf//~olshen/目標變量是類別的---分類樹目標變量是連續的---回歸樹CART分類回歸樹CART(ClassificationaCART二元劃分二叉樹不易產生數據碎片，精確度往往也會高于多叉樹，所以在CART算法中，采用了二元劃分不純性度量分類目標：Gini指標、Towing、orderTowing連續目標：最小平方殘差、最小絕對殘差剪枝：用獨立的驗證數據集對訓練集生長的樹進行剪枝CART二元劃分三個步驟生成最大樹生成一棵充分生長的最大樹樹的修剪根據修剪算法對最大樹進行修剪，生成由許多子樹組成的子樹序列子樹評估從子樹序列中選擇一棵最優的子樹作為最后的結果。

三個步驟生成最大樹分類與回歸樹

(ClassificationAndRegressionTrees,CART)

是一種產生二叉決策樹的技術.

分類樹與回歸樹下面有兩個重要的思想:

第一個:遞歸地劃分自變量空間的想法;

第二個:用驗證數據進行剪枝的想法.分類與回歸樹一遞歸劃分自變量空間遞歸劃分

用Y表示因變量(分類變量);

用X1,X2,…,XP表示自變量.

通過遞歸的方式把關于X的P維空間劃分為不重疊的矩形.一遞歸劃分自變量空間遞歸劃分劃分步驟:

首先:一個自變量被選擇,例如Xi和Xi的一個值Si,若選擇Si把P維空間分為兩部分:一部分包含的點都滿足Xi<=Si;另一部分包含的點滿足Xi>Si.其次:再把上步中得到的兩部分中的一個部分,通過選擇一個變量和該變量的劃分值以相似的方式再劃分.重復上述步驟,直至把整個X空間劃分成的每個小矩形都盡可能的是同構的.劃分步驟:

例示遞歸劃分的過程例1（Johnson和Wichern）乘式割草機制造商意欲發現一個把城市中的家庭分成那些愿意購買乘式割草機和不愿意購買的兩類的方法。在這個城市的家庭中隨機抽取12個擁有者和12個非擁有者的家庭作為樣本。這些數據如表1所示。這里的自變量是收入（X1）和草地面積（X2）。類別變量Y有兩個類別：擁有者和非擁有者。表1例示遞歸劃分的過程第3章-分類與決策樹分析課件CART如何選擇劃分點?

對于一個變量劃分點是一對連續變量值的中點.

例如:X1可能劃分點是{38.1,45.3,50.1…,109.5};X2可能劃分點是{14.4,15.4,16.2…23}.

這些劃分點按照能減少雜質的多少來分級.

雜質度量方法:Gini指標.

矩形A的Gini不純度可定義為:

其中K=1,2,…C,來表示類,Pk是觀測點中屬于類K的比例.

CART如何選擇劃分點?雜度

在ID3算法中，用“熵”來度量數據集隨機性的程度。在CART中我們把這種隨機性的程度稱為“雜度”（impurity，也稱為“不純度”），并且用“吉尼”(gini)指標來衡量它。雜度在ID3算法中，用“熵”來度量數據集隨機性的程度。吉尼指標設t是決策樹上的某個節點，該節點的數據集為S，由s個樣本組成，其類標號屬性具有m個不同的取值，即定義了m個不同的類Ci（i=1,2,…,m）。設屬于類Ci的樣本的個數為si。那么這個節點的吉尼指標這樣來計算：吉尼指標設t是決策樹上的某個節點，該節點的數據集為S，由s雜度削減

由于CART算法生成的是一棵二叉樹，所以對于節點t來說，分裂后將產生兩個子節點tL和tR，設這兩個子節點的雜度分別為gini(tL)和gini(tR)，那么，在此次分裂過程中的雜度削減為：雜度削減由于CART算法生成的是一棵二叉樹，所以對于節點t計算雜度削減計算雜度削減停止準則

以下任何一個規則被滿足，節點將不再分裂這個節點是“純”的，即這個節點的所有樣本都屬于同一類別；對于每一個屬性（不包括類標號屬性），節點中的所有樣本都有相同的值；當前節點所在的深度已經達到“最大樹深度”（如果定義有）；這個節點的樣本數量小于“父分支中的最小記錄數”（如果定義有）；這個節點分裂后產生的子節點中包含的樣本數量小于預定義的“子分支中的最小記錄數”（如果定義有）；分裂產生的雜度削減小于預定義的“最小雜度削減”（如果定義有）

停止準則以下任何一個規則被滿足，節點將不再分裂選擇草地面積變量X2=19做第一次分割,由(X1,X2)組成的空間被分成X2<=19和X2>19的兩個矩形.選擇草地面積變量X2=19做第一次分割,由(X1,X2)組成選擇收入變量X1=84.75選擇收入變量X1=84.75第3章-分類與決策樹分析課件我們能看到遞歸劃分是如何精煉候選矩形,使之變得更純的算法過程.最后階段的遞歸分析如圖5所示我們能看到遞歸劃分是如何精煉候選矩形,使之變得更純的算法過程這個方法被稱為分類樹的原因是每次劃分都可以描述為把一個節點分成兩個后續節點.

第一次分裂表示為樹的根節點的分支,如圖6這個方法被稱為分類樹的原因是每次劃分都可以描述為把一個節點分樹的前三次劃分如圖7樹的前三次劃分如圖7整個樹如下圖8整個樹如下圖8二用驗證數據進行剪枝CART過程中第二個關鍵的思想是用獨立的驗證數據集對根據訓練集生成的樹進行剪枝.CART剪枝目的:生成一個具有最小錯誤的樹.為什么要剪枝呢?

因為:1在樹生成過程中可能存在不能提高分類純度的劃分節點.2存在過擬合訓練數據.二用驗證數據進行剪枝CART過程中第二個關鍵的思想是用獨立的第3章-分類與決策樹分析課件樹的修剪葉子節點過多，則樹的復雜度高。葉子節點過少，則誤分類損失大。代價復雜度

CART算法仍然使用后剪枝。在樹的生成過程中，多展開一層就會有多一些的信息被發現，CART算法運行到不能再長出分支為止，從而得到一棵最大的決策樹。然后對這棵大樹進行剪枝。樹的修剪葉子節點過多，則樹的復雜度高。CART算法仍然使用最佳剪枝樹如下圖10所示最佳剪枝樹如下圖10所示3.3.4在Clementine中應用CART這里，以電信客戶數據（文件名為Telephone.sav）為例，討論分類回歸樹的具體操作以及如何通過交互操作控制決策樹的生長和剪枝過程。分析目標是，找到影響客戶流失的重要因素，以實現客戶流失的事前控制。3.3.4在Clementine中應用CART數據流數據流建模建模分類結果分類結果

分析結論1在流管理器的Models卡中，鼠標右擊所得到的CART模型，選擇彈出菜單中的Brower項瀏覽默寫結果并選擇Generate菜單下的FilterNode項。于是，會在數據流編輯區自動生成一個Filter節點，將它連到數據流的恰當位置，可看到下圖結果：從圖中可知，只有性別對客戶流失的影響不大，其他因素都有影響。應該注意到，這棵決策樹是代價復雜度最小的，但針對本例的分析目標，可適當減少復雜性、降低精度，以找到更主要的影響因素。分析結論1在流管理器的Models卡中，鼠標右擊所Chi-SquareAutomaticInteractionDetectionCHAID提供了一種在多個自變量中自動搜索能產生最大差異的變量方案。不同于C＆R樹和QUEST節點，CHAID分析可以生成非二叉樹，即有些分割有兩個以上的分支。CHAID模型需要一個單一的目標和一個或多個輸入字段。CHAID分析，是一種用卡方統計，以確定最佳的分割，建立決策樹的分類方法。3.4CHAID算法（卡方自動交叉檢驗）Chi-SquareAutomaticInteractiCHAID的適用范圍

當預測變量是分類變量時，CHAID方法最適宜。對于連續型變量，CHAID在缺省狀態下將連續變量自動分為10段處理，但是可能有遺漏。CHAID的適用范圍當預測變量是分類變實例：以電信客戶數據Telephone.sav為例,討論CHAID具體操作。實例：以電信客戶數據Telephone.sClementine決策樹算法

C&RT、CHAID、C5.0的區別Clementine決策樹算法

C&RT、CHAID、C5.決策樹(decisiontree)

優點：

1)可以生成可以理解的規則；

2)計算量絕對來說不是很大；

3)可以統治連續和種類字段；

4)決策樹可以清晰的顯示哪些字段比較首要。

缺點：

1)對連續性的字段比較難預測；

2)對有時間順次的數據，處理困難。決策樹(decisiontree)優點：

1)可一、C5.0算法優點：

1)面對數據遺漏和輸入字段很多的問題時非常穩健；

2)比一些其他類型的模型易于理解，模型推出的規則有非常直觀的解釋。

一、C5.0算法優點：

1)面對數據遺漏和輸入字段很多的二、C&RT

優點：

（1）可自動忽略對主要變量沒有貢獻的屬性變量；

（2）在面對諸如存在缺失值、變量數多等問題時C&RT顯得非常穩健（robust）；

（3）比其他模型更易于理解，決策推理可以表示成IF…THEN的形式。二、C&RT

優點：

（1）可自動忽略對主要變量沒有貢獻的屬三、CHAID優點：

（1）可產生多分枝的決策樹；

（2）主要變量可以定距或定類；

（3）從統計顯著性角度斷定分支變量和分割值，進而優化樹的分枝經過。

三、CHAID優點：

（1）可產生多分枝的決策樹；

（2）主第3章

分類與預測第3章

分類與預測主要內容分類與決策樹概述ID3、C4.5與C5.0CART主要內容分類與決策樹概述分類VS.預測分類和預測是兩種數據分析形式，用于提取描述重要數據類或預測未來的數據趨勢的模型分類：預測類對象的分類標號（或離散值）根據訓練數據集和類標號屬性，構建模型來分類現有數據，并用來分類新數據預測：建立連續函數值模型比如預測空缺值，或者預測顧客在計算機設備上的花費典型應用欺詐檢測、市場定位、性能預測、醫療診斷分類是一種應用非常廣泛的數據挖掘技術分類與預測的區別：當估計的屬性值是離散值時，這就是分類；當估計的屬性值是連續值時，這就是預測。分類VS.預測分類和預測是兩種數據分析形式，用于提取描述分類和預測---示例分類銀行貸款員需要分析數據，來弄清哪些貸款申請者是安全的，哪些是有風險的（將貸款申請者分為“安全”和“有風險”兩類）我們需要構造一個分類器來預測類屬編號，比如預測顧客屬類預測銀行貸款員需要預測貸給某個顧客多少錢是安全的構造一個預測器，預測一個連續值函數或有序值，常用方法是回歸分析分類和預測---示例分類數據分類——一個兩步過程(1)第一步，也成為學習步，目標是建立描述預先定義的數據類或概念集的分類器分類算法通過分析或從訓練集“學習”來構造分類器。訓練集由數據庫元組（用n維屬性向量表示）和他們相對應的類編號組成；假定每個元組屬于一個預定義的類訓練元組：訓練數據集中的單個元組學習模型可以用分類規則、決策樹或數學公式的形式提供數據分類——一個兩步過程(1)第一步，也成為學習步，目標是數據分類——一個兩步過程(2)第二步，使用模型，對將來的或未知的對象進行分類首先評估模型的預測準確率對每個測試樣本，將已知的類標號和該樣本的學習模型類預測比較模型在給定測試集上的準確率是正確被模型分類的測試樣本的百分比測試集要獨立于訓練樣本集，否則會出現“過分擬合”的情況數據分類——一個兩步過程(2)第二步，使用模型，對將來的或第一步——建立模型訓練數據集分類算法IFrank=‘professor’ORyears>6THENtenured=‘yes’分類規則第一步——建立模型訓練數分類算法IFrank=‘pro第二步——用模型進行分類分類規則測試集未知數據(Jeff,Professor,4)Tenured?第二步——用模型進行分類分類規則測試集未知數據(Jeff,監督學習VS.無監督學習監督學習（用于分類）模型的學習在被告知每個訓練樣本屬于哪個類的“指導”下進行新數據使用訓練數據集中得到的規則進行分類無監督學習（用于聚類）每個訓練樣本的類編號是未知的，要學習的類集合或數量也可能是事先未知的通過一系列的度量、觀察來建立數據中的類編號或進行聚類監督學習VS.無監督學習監督學習（用于分類）數據預測的兩步過程數據預測也是一個兩步的過程，類似于前面描述的數據分類對于預測，沒有“類標號屬性”要預測的屬性是連續值，而不是離散值，該屬性可簡稱“預測屬性”E.g.銀行貸款員需要預測貸給某個顧客多少錢是安全的預測器可以看作一個映射或函數y=f(X)其中X是輸入；y是輸出，是一個連續或有序的值與分類類似，準確率的預測，也要使用單獨的測試集數據預測的兩步過程數據預測也是一個兩步的過程，類似于前面描述3.1決策樹概述決策樹(DecisionTree)

一種描述概念空間的有效的歸納推理辦法。基于決策樹的學習方法可以進行不相關的多概念學習，具有簡單快捷的優勢，已經在各個領域取得廣泛應用。決策樹是一種樹型結構，其中每個內部結點表示在一個屬性上的測試，每個分支代表一個測試輸出，每個葉結點代表一種類別。3.1決策樹概述決策樹(DecisionTree)決策決策樹學習是以實例為基礎的歸納學習。從一類無序、無規則的事物（概念）中推理出決策樹表示的分類規則。概念分類學習算法：來源于Hunt,Marin和Stone于1966年研制的CLS學習系統，用于學習單個概念。1979年,J.R.Quinlan給出ID3算法，并在1983年和1986年對ID3進行了總結和簡化，使其成為決策樹學習算法的典型。Schlimmer和Fisher于1986年對ID3進行改造，在每個可能的決策樹節點創建緩沖區，使決策樹可以遞增式生成，得到ID4算法。1988年，Utgoff在ID4基礎上提出了ID5學習算法，進一步提高了效率。1993年，Quinlan進一步發展了ID3算法，改進成C4.5算法。另一類決策樹算法為CART，與C4.5不同的是，CART的決策樹由二元邏輯問題生成，每個樹節點只有兩個分枝，分別包括學習實例的正例與反例。其基本思想是以信息熵為度量構造一棵熵值下降最快的樹，到葉子節點處的熵值為零，此時每個葉節點中的實例都屬于同一類。決策樹學習是以實例為基礎的歸納學習。決策樹學習采用的是自頂向下的遞歸方法。決策樹的每一層節點依照某一屬性值向下分為子節點，待分類的實例在每一節點處與該節點相關的屬性值進行比較，根據不同的比較結果向相應的子節點擴展，這一過程在到達決策樹的葉節點時結束，此時得到結論。從根節點到葉節點的每一條路經都對應著一條合理的規則，規則間各個部分（各個層的條件）的關系是合取關系。整個決策樹就對應著一組析取的規則。決策樹學習算法的最大優點是，它可以自學習。在學習的過程中，不需要使用者了解過多背景知識，只需要對訓練例子進行較好的標注，就能夠進行學習。如果在應用中發現不符合規則的實例，程序會詢問用戶該實例的正確分類，從而生成新的分枝和葉子，并添加到樹中。決策樹學習采用的是自頂向下的遞歸方法。樹是由節點和分枝組成的層次數據結構。節點用于存貯信息或知識，分枝用于連接各個節點。樹是圖的一個特例，圖是更一般的數學結構，如貝葉斯網絡。

決策樹是描述分類過程的一種數據結構，從上端的根節點開始，各種分類原則被引用進來，并依這些分類原則將根節點的數據集劃分為子集，這一劃分過程直到某種約束條件滿足而結束。

根結點個子大可能是松鼠可能是老鼠可能是大象在水里會吱吱叫鼻子長脖子長個子小不會吱吱叫鼻子短脖子短可能是長頸鹿在陸地上可能是犀牛可能是河馬樹是由節點和分枝組成的層次數據結構。節點用于存貯信息或知識，可以看到，一個決策樹的內部結點包含學習的實例，每層分枝代表了實例的一個屬性的可能取值，葉節點是最終劃分成的類。如果判定是二元的，那么構造的將是一棵二叉樹，在樹中每回答一個問題就降到樹的下一層，這類樹一般稱為CART（ClassificationAndRegressionTree）。判定結構可以機械的轉變成產生式規則。可以通過對結構進行廣度優先搜索，并在每個節點生成“IF…THEN”規則來實現。如圖6-13的決策樹可以轉換成下規則：

IF“個子大”THENIF“脖子短”THENIF“鼻子長”THEN可能是大象形式化表示成

根結點個子大可能是松鼠可能是老鼠可能是大象在水里會吱吱叫鼻子長脖子長個子小不會吱吱叫鼻子短脖子短可能是長頸鹿在陸地上可能是犀牛可能是河馬可以看到，一個決策樹的內部結點包含學習的實例，每層分枝代表了構造一棵決策樹要解決四個問題：收集待分類的數據，這些數據的所有屬性應該是完全標注的。設計分類原則，即數據的哪些屬性可以被用來分類，以及如何將該屬性量化。分類原則的選擇，即在眾多分類準則中，每一步選擇哪一準則使最終的樹更令人滿意。設計分類停止條件，實際應用中數據的屬性很多，真正有分類意義的屬性往往是有限幾個，因此在必要的時候應該停止數據集分裂：該節點包含的數據太少不足以分裂，繼續分裂數據集對樹生成的目標(例如ID3中的熵下降準則)沒有貢獻，樹的深度過大不宜再分。通用的決策樹分裂目標是整棵樹的熵總量最小，每一步分裂時，選擇使熵減小最大的準則，這種方案使最具有分類潛力的準則最先被提取出來構造一棵決策樹要解決四個問題：預測變量目標變量記錄樣本類標號屬性類別集合：Class={“優”，“良”，“差”}決策樹的基本原理預測變量目標變量類標號屬性類別集合：Class={“優”，“根節點葉子節點分裂屬性分裂謂詞每一個葉子節點都被確定一個類標號根節點葉子節點分裂屬性分裂謂詞每一個葉子節點都被確定一個類每一個節點都代表了一個數據集。根節點1代表了初始數據集D其它節點都是數據集D的子集。例如，節點2代表數據集D中年齡小于40歲的那部分樣本組成的數據集。子節點是父節點的子集。

If(年齡<40)and(職業=“學生”or職業=“教師”)Then信用等級=“優”If(年齡<40)and(職業!=“學生”and職業!=“教師”)Then信用等級=“良”If(年齡≥40)and(月薪<1000)Then信用等級=“差”If(年齡≥40)and(月薪≥1000and月薪≤3000)Then信用等級=“良”If(年齡≥40)and(月薪>3000)Then信用等級=“優”每一個節點都代表了一個數據集。決策樹是指具有下列三個性質的樹：每個非葉子節點都被標記一個分裂屬性Ai；每個分支都被標記一個分裂謂詞，這個分裂謂詞是分裂父節點的具體依據；每個葉子節點都被標記一個類標號Cj∈C。任何一個決策樹算法，其核心步驟都是為每一次分裂確定一個分裂屬性，即究竟按照哪一個屬性來把當前數據集劃分為若干個子集，從而形成若干個“樹枝”。決策樹是指具有下列三個性質的樹：熵，是數據集中的不確定性、突發性或隨機性的程度的度量。當一個數據集中的記錄全部都屬于同一類的時候，則沒有不確定性，這種情況下的熵就為0。決策樹分裂的基本原則是，數據集被分裂為若干個子集后，要使每個子集中的數據盡可能的“純”，也就是說子集中的記錄要盡可能屬于同一個類別。如果套用熵的概念，即要使分裂后各子集的熵盡可能的小。3.2ID3、C4.5與C5.0熵，是數據集中的不確定性、突發性或隨機性的程度的度量。3.2ID3=>C4.5=>C5.0RossQuinlanID31986年C4.51993年C5.01998年2011年獲得KDD創新獎/Personal///download.html/ID3=>C4.5=>C5.0RossQuinlan數據集D被按照分裂屬性“年齡”分裂為兩個子集D1和D2

信息增益:Gain(D,年齡)=H(D)–[P(D1)×H(D1)+P(D2)×H(D2)]數據集D被按照分裂屬性“年齡”分裂為兩個子集D1和D2信顯然，如果D1和D2中的數據越“純”，H(D1)和H(D2)就越小，信息增益就越大，或者說熵下降得越多。按照這個方法，測試每一個屬性的信息增益，選擇增益值最大的屬性作為分裂屬性。顯然，如果D1和D2中的數據越“純”，H(D1)和H(D2)信息熵計算舉例令C1對應“是”，C2對應“否”。那么C1有9個樣本，C2有5個樣本，所以數據集D的熵為：信息熵計算舉例令C1對應“是”，C2對應“否”。那么C1有9決策樹歸納策略(1)輸入數據劃分D是訓練元組和對應類標號的集合attribute_list,候選屬性的集合Attribute_selection_method，指定選擇屬性的啟發性過程算法步驟樹以代表訓練樣本的單個節點（N）開始如果樣本都在同一個類，則該節點成為樹葉，并用該類標記否則，算法調用Attribute_selection_method，選擇能夠最好的將樣本分類的屬性；確定“分裂準則”，指出“分裂點”或“分裂子集”。決策樹歸納策略(1)輸入決策樹歸納策略(2)對測試屬性每個已知的值，創建一個分支，并以此劃分元組算法使用同樣的過程，遞歸的形成每個劃分上的元組決策樹。一旦一個屬性出現在一個節點上，就不在該節點的任何子節點上出現遞歸劃分步驟停止的條件劃分D（在N節點提供）的所有元組屬于同一類沒有剩余屬性可以用來進一步劃分元組——使用多數表決沒有剩余的樣本給定分支沒有元組，則以D中多數類創建一個樹葉決策樹歸納策略(2)對測試屬性每個已知的值，創建一個分支，屬性選擇度量屬性選擇度量是一種選擇分裂準則，將給定類標號的訓練元組最好的進行劃分的方法理想情況，每個劃分都是“純”的，即落在給定劃分內的元組都屬于相同的類屬性選擇度量又稱為分裂準則常用的屬性選擇度量信息增益增益率Gini指標屬性選擇度量屬性選擇度量是一種選擇分裂準則，將給定類標號的訓信息增益(1)S是一個訓練樣本的集合，該樣本中每個集合的類編號已知。每個樣本為一個元組。有個屬性用來判定某個訓練樣本的類編號假設S中有m個類，總共s個訓練樣本，每個類Ci有si個樣本(i＝1,2,3...m)，那么任意一個樣本屬于類Ci的概率是si/s，那么用來分類一個給定樣本的期望信息是：信息增益(1)S是一個訓練樣本的集合，該樣本中每個集合的類信息增益(2)一個有v個值的屬性A{a1,a2,...,av}可以將S分成v個子集{S1,S2,...,Sv}，其中Sj包含S中屬性A上的值為aj的樣本。假設Sj包含類Ci的sij個樣本。根據A的這種劃分的期望信息稱為A的熵A上該劃分的獲得的信息增益定義為：具有高信息增益的屬性，是給定集合中具有高區分度的屬性。所以可以通過計算S中樣本的每個屬性的信息增益，來得到一個屬性的相關性的排序。信息增益(2)一個有v個值的屬性A{a1,a2,...,a若以“年齡”作為分裂屬性，則產生三個子集（因為該屬性有三個不同的取值），所以D按照屬性“年齡”劃分出的三個子集的熵的加權和為：其中有一個子集的熵為0若以“年齡”作為分裂屬性，則產生三個子集（因為該屬性有三個不同理，若以“收入水平”為分裂屬性：同理，若以“收入水平”為分裂屬性：若以“有固定收入”為分裂屬性：若以“VIP”為分裂屬性：若以“有固定收入”為分裂屬性：以“年齡”作為分裂屬性，所得信息增益最大。葉子節點以“年齡”作為分裂屬性，所得信息增益最大。葉子節點第3章-分類與決策樹分析課件ID3的主要缺點ID3算法只能處理分類屬性（離散屬性），而不能處理連續屬性（數值屬性）。在處理連續屬性時，一般要先將連續屬性劃分為多個區間，轉化為分類屬性。例如“年齡”，要把數值事先轉換為諸如“小于30歲”、“30至50歲”、“大于50歲”這樣的區間，再根據年齡值落入了某一個區間取相應的類別值。通常，區間端點的選取包含著一定的主觀因素。ID3生成的決策樹是一棵多叉樹，分支的數量取決于分裂屬性有多少個不同的取值。這不利于處理分裂屬性取值數目較多的情況。因此目前流行的決策樹算法大多采用二叉樹模型。ID3的主要缺點ID3算法只能處理分類屬性（離散屬性），而不ID3是采用“信息增益”來選擇分裂屬性的。雖然這是一種有效的方法，但其具有明顯的傾向性，即它傾向于選擇具有大量不同取值的屬性，從而產生許多小而純的子集。尤其是關系數據庫中作為主鍵的屬性，每一個樣本都有一個不同的取值。如果以這樣的屬性作為分裂屬性，那么將產生非常多的分支，而且每一個分支產生的子集的熵均為0（因為子集中只有一個樣本！）。顯然，這樣的決策樹是沒有實際意義的。因此，Quinlan提出使用增益比例來代替信息增益。3.2.2C4.5ID3是采用“信息增益”來選擇分裂屬性的。雖然這是一種有效的設S代表訓練數據集，由s個樣本組成。A是S的某個屬性，有m個不同的取值，根據這些取值可以把S劃分為m個子集，Si表示第i個子集（i=1,2,…,m），|Si|表示子集Si中的樣本數量。那么：稱為“數據集S關于屬性A的熵”。設S代表訓練數據集，由s個樣本組成。A是S的某個屬性，有m個用來衡量屬性A分裂數據集的廣度和均勻性。樣本在屬性A上的取值分布越均勻，Split_Info(S,A)的值就越大。增益比例的定義為：增益比例消除了選擇那些值較多且均勻分布的屬性作為分裂屬性的傾向性。用來衡量屬性A分裂數據集的廣度和均勻性。樣本在屬性A上的取值連續屬性的處理

設屬性Y有m個不同的取值，按大小順序升序排列為v1<v2<,…,<vm。從{v1,v2,…,vm-1}中選擇一個vi作為閾值，則可以根據“Y≤vi”和“Y>vi”將數據集劃分為兩個部分，形成兩個分支。顯然，{v1,v2,…,vm-1}就是可能的閾值的集合，共(m-1)個元素。把這些閾值一一取出來，并根據“Y≤vi”和“Y>vi”把訓練數據集劃分為兩個子集，并計算每一種劃分方案下的信息增益或增益比例，選擇最大增益或增益比例所對應的那個閾值，作為最優的閾值。可以看出，如果選擇連續屬性作為分裂屬性，則分裂后只有兩個分支，而不象離散屬性那樣可能會有多個分支（由離散屬性的取值個數決定）。

連續屬性的處理設屬性Y有m個不同的取值，按大小順序升序排列第3章-分類與決策樹分析課件如果要計算“年齡”屬性的信息增益，則首先將不同的屬性值排序{20,25,28,40,46,55,56,58,60,65,70}那么可能的閾值集合為{20,25,28,40,46,55,56,58,60,65,70}，從中一一取出，并形成分裂謂詞，例如取出“20”，形成謂詞“≤20”和“>20”，用它們劃分訓練數據集，然后計算信息增益或增益比例。如果要計算“年齡”屬性的信息增益，則首先將不同的屬性值排序{處理有缺失值的樣本

C4.5并不會武斷地將一個有缺失值的樣本拋棄,也不會隨意地將它分配到某個類別中去。“收入水平”的值，取為“高”的概率為3/12，取為“中”的概率為5/12，取為“低”的概率為4/12。S1（收入水平=“高”）的樣本數量為：3+2×(3/12)；處理有缺失值的樣本C4.5并不會武斷地將一個有缺失值的樣本3.2.4C5.0算法C5.0是經典的決策樹模型的算法之一，可生成多分支的決策樹，目標變量為分類變量使用c5.0算法可以生成決策樹（decisiontree）或者規則集（rule

sets）。C5.0模型根據能夠帶來最大信息增益（informationgain）的字段拆分樣本。第一次拆分確定的樣本子集隨后再次拆分，通常是根據另一個字段進行拆分，這一過程重復進行直到樣本子集不能再被拆分為止。最后，重新檢驗最低層次的拆分，那些對模型值沒有顯著貢獻的樣本子集被剔除或者修剪。

3.2.4C5.0算法C5.0是經典的決策樹模型的算法C5.0的優點優點：C5.0模型在面對數據遺漏和輸入字段很多的問題時非常穩健。C5.0模型通常不需要很長的訓練次數進行估計。C5.0模型比一些其他類型的模型易于理解，模型推出的規則有非常直觀的解釋。C5.0也提供強大的增強技術以提高分類的精度。C5.0算法選擇分支變量的依據以信息熵的下降速度作為確定最佳分支變量和分割閥值的依據。信息熵的下降意味著信息的不確定性下降C5.0的優點優點：舉例：在Clementine中應用C5.0這里，以學生參加某次社會公益活動的數據（文件名為Students.xls）為例，講解C5.0算法的具體實現操作。分析目標是，研究哪些因素將顯著影響到學生參與社會公益活動。其中，是否參加為輸出變量，除編號以外的變量均為輸入變量。舉例：在Clementine中應用C5.0這里，以學生參加某數據流如下：數據流如下：一、建立模型第一步建立數據源，第二步選擇Modeling卡中的C5.0節點并將其連接到恰當位置，鼠標右擊該節點，彈出下面窗口。模型名稱（Modelname）輸出類型（Outputtype）：此處指定希望最終生成的模型是決策樹還是規則集。群體字符（Groupsymbolics）。如果選擇該選項，C5.0會嘗試將所有與輸出字段格式相似的字符值合并。如果沒有選擇該選項，C5.0會為用于拆分母節點的字符字段的每個值創建一個子節點。使用自舉法（Useboosting）：提高其精確率。這種方法按序列建立多重模型。第一個模型以通常的方式建立。隨后，建立第二個模型，聚焦于被第一個模型錯誤分類的記錄。以此類推，最后應用整個模型集對樣本進行分類，使用加權投票過程把分散的預測合并成綜合預測。TheNumberoftrials選項允許控制用于助推的模型數量。一、建立模型第一步建立數據源，第二步選擇Model交叉驗證（Cross－validate）：如果選擇了該選項，C5.0將使用一組基于訓練數據子集建立的模型，來估計基于全部數據建立的模型的精確度。如果數據集過小，不能拆分成傳統意義上的訓練集和測試集，這將非常有用。或用于交叉驗證的模型數目。模式（Mode）：對于簡單的訓練，絕大多數C5.0參數是自動設置。高級訓練模式選項允許對訓練參數更多的直接控制。第3章-分類與決策樹分析課件簡單模式選項（simple）偏好（Favor）：在accuracy下，C5.0會生成盡可能精確的決策樹。在某些情況下，這會導致過度擬和。選擇Generality（一般化）項以使用不易受該問題影響的算法設置。期望噪聲百分數（Expectednoise（%））：指定訓練集中的噪聲或錯誤數據期望比率。簡單模式選項（simple）高級模式選項修剪純度（pruningseverity）：決定生成決策樹或規則集被修剪的程度。提高純度值將獲得更小，更簡潔的決策樹。降低純度值將獲得更加精確的決策樹。子分支最少記錄數（Minimumrecordsperchildbranch）：子群大小可以用于限制決策樹任一分支的拆分數。只有當兩個或以上的后序子分支包括來自訓練集的記錄不少于最小記錄數，決策樹才會繼續拆分。默認值為2，提高該值將有助于避免噪聲數據的過度訓練。全局修剪（Useglobalpruning）：第一階段：局部修建第二階段：全局修剪排除屬性（Winnowattributes）：如果選擇了該選項，C5.0會在建立模型前檢驗預測字段的有用性。被發現與分析無關的預測字段將不參與建模過程。這一選項對有許多預測字段元的模型非常有用，并且有助于避免過度擬和。高級模式選項圖1指定錯誤歸類損失錯誤歸類損失允許指定不同類型預測錯誤之間的相對重要性。錯誤歸類損失矩陣顯示預測類和實際類每一可能組合的損失。所有的錯誤歸類損失都預設設置為1.0。要輸入自定義損失值，選擇Usemisclassificationcosts，然后把自定義值輸入到損失矩陣中。圖1指定錯誤歸類損失錯誤歸類損失允許指定不同類型預測錯誤之具體設置具體設置執行結果執行結果二、預測結果為觀測C5.0對每個樣本的預測結果，可在流管理器的Models卡中，鼠標右擊C5.0模型結果，選擇彈出菜單中的AddToStream，并將模型結果連接到數據流中，然后連接Table節點查看預測結果，如下圖所示：二、預測結果為觀測C5.0對每個樣本的預測結果，可在三、C5.0模型評價三、C5.0模型評價CART分類回歸樹CART(ClassificationandRegressionTrees)1984<<ClassificationandRegressionTrees>>L.Breiman，J.Friedman，R.Olshen和C.Stone/~breiman//~jhf//~olshen/目標變量是類別的---分類樹目標變量是連續的---回歸樹CART分類回歸樹CART(ClassificationaCART二元劃分二叉樹不易產生數據碎片，精確度往往也會高于多叉樹，所以在CART算法中，采用了二元劃分不純性度量分類目標：Gini指標、Towing、orderTowing連續目標：最小平方殘差、最小絕對殘差剪枝：用獨立的驗證數據集對訓練集生長的樹進行剪枝CART二元劃分三個步驟生成最大樹生成一棵充分生長的最大樹樹的修剪根據修剪算法對最大樹進行修剪，生成由許多子樹組成的子樹序列子樹評估從子樹序列中選擇一棵最優的子樹作為最后的結果。

三個步驟生成最大樹分類與回歸樹

(ClassificationAndRegressionTrees,CART)

是一種產生二叉決策樹的技術.

分類樹與回歸樹下面有兩個重要的思想:

第一個:遞歸地劃分自變量空間的想法;

第二個:用驗證數據進行剪枝的想法.分類與回歸樹一遞歸劃分自變量空間遞歸劃分

用Y表示因變量(分類變量);

用X1,X2,…,XP表示自變量.

通過遞歸的方式把關于X的P維空間劃分為不重疊的矩形.一遞歸劃分自變量空間遞歸劃分劃分步驟:

首先:一個自變量被選擇,例如Xi和Xi的一個值Si,若選擇Si把P維空間分為兩部分:一部分包含的點都滿足Xi<=Si;另一部分包含的點滿足Xi>Si.其次:再把上步中得到的兩部分中的一個部分,通過選擇一個變量和該變量的劃分值以相似的方式再劃分.重復上述步驟,直至把整個X空間劃分成的每個小矩形都盡可能的是同構的.劃分步驟:

例示遞歸劃分的過程例1（Johnson和Wichern）乘式割草機制造商意欲發現一個把城市中的家庭分成那些愿意購買乘式割草機和不愿意購買的兩類的方法。在這個城市的家庭中隨機抽取12個擁有者和12個非擁有者的家庭作為樣本。這些數據如表1所示。這里的自變量是收入（X1）和草地面積（X2）。類別變量Y有兩個類別：擁有者和非擁有者。表1例示遞歸劃分的過程第3章-分類與決策樹分析課件CART如何選擇劃分點?

對于一個變量劃分點是一對連續變量值的中點.

例如:X1可能劃分點是{38.1,45.3,50.1…,109.5};X2可