1、數據分類-決策樹目錄根本概念決策樹ID3算法決策樹C4.5算法2學習目的1.掌握數據分類的根本原理和評價目的2.了解兩種決策樹算法3Part I數據分類的根本概念4定義數據分類是指把數據樣本映射到一個事先定義的類中的學習過程即給定一組輸入的屬性向量及其對應的類，用基于歸納的學習算法得出分類分類問題是數據發掘領域中研討和運用最為廣泛的技術之一，如何更準確、更有效地分類不斷是人們追求的目的數據分類的義務經過學習得到一個目的函數f，把每個屬性集x映射到一個預先定義的類標號y5分類的例如兩類分類例如銀行業：區分高端信譽卡和低端信譽卡醫療診斷：區分正常細胞和癌細胞互聯網：區分正常郵件和渣滓郵件多類分類例

2、如油氣傳輸：區分行人走過、汽車碾過、鎬刨、電鉆等行為文字識別：區分不同的字符其中漢字識別是一個大類別問題社會網絡：區分中心用戶、活潑用戶、不活潑用戶、馬甲用戶等6例如數據集數據集包含多個描畫屬性和一個類別屬性普通來說描畫屬性：延續值或離散值類別屬性：只能是離散值目的屬性延續對應回歸問題AgeSalaryClass30highc125highc221lowc243highc118lowc233lowc1.7分類問題的方式化描畫8分類的過程獲取數據預處置分類決策分類器設計9獲取數據數值型數據病例中的各種化驗數據空氣質量監測數據描畫性數據人事部門檔案資料圖片型數據指紋、掌紋自然場景圖片很多情況下，需

3、求將上述數據一致轉換為數值型數據序列，即構成特征向量特征提取10預處置為了提高分類的準確性和有效性，需求對分類所用的數據進展預處置去除噪聲數據對空缺值進展處置數據降維特征選擇-PCA、LDA 主成分分析 Principal Component Analysis ， PCA 線性鑒別分析(LinearDiscriminantAnalysis,LDA)，有時也稱Fisher線性判別(FisherLinearDiscriminant,FLD)，這種算法是RonaldFisher于1936年發明的，是方式識別的經典算法。11分類器設計1-劃分數據集給定帶有類標號的數據集，并且將數據集劃分為兩個部分訓練

4、集training set測試集testing set劃分戰略1.當數據集D的規模較大時 訓練集2|D|/3，測試集是1|D|/32.當數據集D的規模不大時 n交叉驗證法n-fold validation將數據集隨機地劃分為n組之后執行n次循環，在第i次循環中，將第i組數據樣本作為測試集，其他的n-1組數據樣本作為訓練集,最終的精度為n個精度的平均值。123.當數據集D的規模非常小時每次交叉驗證時，只選擇一條測試數據，剩余的數據均作為訓練集。原始數據集有m條數據時，相當于m-次交叉驗證。是N-次交叉驗證的一個特例。 分類器設計2-分類器構造利用訓練集構造分類器分類模型經過分析由屬性描畫的每類樣

5、本的數據信息，從中總結出分類的規律性，建立判別公式或判別規那么在分類器構造過程中，由于提供了每個訓練樣本的類標號，這一步也稱作監視學習supervised learning14分類器設計3-分類器測試利用測試集對分類器的分類性能進展評價，詳細方式是首先，利用分類器對測試集中的每一個樣本進展分類其次，將分類得到的類標號和測試集中數據樣本的原始類標號進展對比由上述過程得到分類器的分類性能如何評價？15分類決策在構呵斥功分類器之后經過測試，那么可以利用該分類器實踐執行分類16分類的評價準那么-商定和假設17分類的評價準那么-目的1準確度accuracy是最常用的評價準那么代表測試集中被正確分類的數據

6、樣本所占的比例反映了分類器對于數據集的整體分類性能18分類的評價準那么-目的2查全率recall第j個類別的查全率召回率表示在本類樣本中，被正確分類的樣本占的比例代表該類別的分類精度19分類的評價準那么-目的3查準率precision第j個類別的查準率表示被分類為該類的樣本中，真正屬于該類的樣本所占的比例代表該類別的分類純度20分類的評價準那么-目的4F-measure可以比較合理地評價分類器對每一類樣本的分類性能它是查全率和查準率的組合表達式其中參數是可以調理的，通常取值為121分類的評價準那么-目的5幾何均值G-mean它能合理地評價數據集的整體分類性能是各個類別查全率的平方根，當各個類別

7、的查全率都大時才增大同時兼顧了各個類別的分類精度22延伸閱讀Jin-Mao Wei, Xiao-Jie Yuan, et al. A novel measure for evaluating classifiers, Expert Systems with Applications, 37(2021):3799-380923關于數據分類的小結所謂分類即是運用某種分類模型，以對象的假設干維描畫屬性為輸入，經過計算輸出該對象所屬類別的過程數據分類的兩個關鍵步驟是分類器訓練：選定適宜的分類模型及參數分類器測試：利用適宜的目的檢驗分類器有效性目前已有一些成熟的分類器可供運用決策樹支持向量機最近鄰/k-

8、近鄰24Part II決策樹算法25決策樹是一種以給定的數據樣本為根底的歸納學習方法在給定知類標號的數據集的情況下，采用自頂向下的遞歸方式來產生一個類似于流程圖的樹構造樹的最頂層節點是根節點最底層節點是葉節點：代表樣本的類別根節點和葉節點之間的節點是內部節點決策樹方法在根節點和內部節點上根據給定的度量規范來選擇最適宜的描畫屬性作為分支屬性并根據該屬性的不同取值向下建立分支26決策樹例如-購買保險A1-公司職員A2-年齡A3-收入A4-信譽度C-買保險否=40高良c2否50中良c1是50低良c1是50低優c2是4150低優c1否=40中良c2是50中良c1是50中優c227保險決策樹處理了哪類人

9、更傾向于購買保險的問題年齡信譽度公司職員c1c1c2c1c250是否良優28決策樹向程序文語的轉化if (年齡=40 & 是公司職員)買保險if (年齡50 & 信譽度為良)買保險if (年齡50 & 信譽度為優)不買保險29根本決策樹方法根本算法 (貪婪算法)自頂向下的分治算法構造樹開場, 一切的訓練樣本和樹根相連屬性為分類屬性 (假設是延續值，那么離散化)根據選定的屬性遞歸地劃分樣本?如何選擇基于啟發式或統計度量選取測試屬性 (e.g., 信息增益)停頓劃分的準那么一切樣本均和屬于同一類的節點銜接無剩下的屬性用于繼續劃分樣本 葉節點分類運用多數表決法無剩余的樣本其它的提早中止法30屬性選擇

10、度量屬性選擇度量劃分規那么劃分屬性：度量得分高的屬性流行的屬性選擇度量信息增益(ID3， C4.5)選取時，偏向于多值屬性增益率(C4.5)偏向不平衡劃分Gini目的( CART, SLIQ, SPRINT)偏向于多值屬性類的數量很大時，計算較困難信息增益(Information Gain)基于信息論“熵，選取具有最大信息增益的屬性劃分在屬性節點A處，樣本集D所具有的熵 (p( j | D) 為類 j 在節點 t處的概率).度量節點的均質性當一切的類均勻分布時，最大為 (log nc)，具有 最多信息當只需一切樣本屬于一類時，最小為 (0.0) ，具有最少信息在屬性A處，將樣本分為v類的信息量

11、經過在屬性A，構成v個分支后，信息增益為,增益最大的選為劃分屬性信息增益例子類 P: buys_computer = “yes類 N: buys_computer = “no 指 14個樣本中有5個“age =30, 兩個屬于類p，2個屬于類N ,因此Similarly,決策樹首層age?4030.40增益率(Gain Ratio)C4.5 (ID3的后繼算法) 運用增益率抑制信息增益的偏斜性 (信息增益的規范化)Ex.GainRatio(income) = 0.029/0.926 = 0.031具有最大增益率的屬性選為劃分屬性信息增益缺陷: 傾向于選擇分割數目多的屬性。Gini指數Gini指

12、數:節點屬性 A劃分樣本的不純度，設樣本集為D(NOTE: p( j | D) 類 j 在樣本D中的概率).當一切樣本均勻分布在不同類時，最大為(1 - 1/nc), 表示最小興趣信息當一切的樣本屬于一類時，最小 為(0.0)，表示最大興趣信息Gini例子P(C1) = 0/6 = 0 P(C2) = 6/6 = 1Gini = 1 P(C1)2 P(C2)2 = 1 0 1 = 0 P(C1) = 1/6 P(C2) = 5/6Gini = 1 (1/6)2 (5/6)2 = 0.278P(C1) = 2/6 P(C2) = 4/6Gini = 1 (2/6)2 (4/6)2 = 0.444

13、基于Gini指數的劃分用于CART算法在節點A，將訓練集D劃分為k個子集(子節點Di )，那么以劃分的不純度加權和度量其優劣 ni = 子樹 的訓練樣本個數i, n = 節點p處訓練樣本個數.二值屬性的Gini指數劃分為兩個子集帶權劃分的效果: Gini指數越小越好尋求更大和更純的劃分B?YesNoNode N1Node N2Gini(D1) = 1 (5/7)2 (2/7)2 = 0.174 Gini(D2) = 1 (1/5)2 (4/5)2 = 0.32Gini(Children) = 7/12 * 0.174 + 5/12 * 0.32= 0.204決策樹歸納算法算法種類多Hunts

14、Algorithm (one of the earliest)CARTID3, C4.5SLIQ,SPRINTID3算法原理選擇具有較高信息增益的描畫屬性作為給定數據集X的分支屬性，從而創建決策樹中的一個節點根據該描畫屬性的不同取值再創建分支之后對各個分支中的樣本子集遞歸調用上述方法建立下一級子節點當某個分支上的一切數據樣本都屬于同一個類別時劃分停頓，構成葉節點或者當某個分支上的樣本不屬于同一個類別，但是又沒有剩余的描畫屬性可以進一步劃分數據集時也構成葉節點，并且用多數樣本所屬的類別來標志這個葉節點41ID3算法例如該樣本集中共包含4個描畫屬性和1個類別屬性，空間容量為14目的是利用ID3思想

15、構建一棵可用于新樣本分類的決策樹A1-公司職員A2-年齡A3-收入A4-信譽度C-買保險否=40高良c2否50中良c1是50低良c1是50低優c2是4150低優c1否=40中良c2是50中良c1是50中優c242第1步：計算對訓練集分類所需的期望信息知total=14c1(買保險)的樣本數量是n1=9c2(不買保險)的樣本數量是n2=5所以P(c1)=9/14P(c2)=5/14根據期望信息公式可得43第2步：計算A1公司職員的熵A1包含兩種取值：“是和“否利用A1可將X劃分為兩個子集X1和X2X1中的數據樣本都是公司職員7個標號為c1的有6個，n11=6標號為c2的有1個，n21=1那么可得

16、p11=6/7p21=1/7A1-公司職員C-買保險否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c244第2步：計算A1公司職員的熵利用A1可將X劃分為兩個子集X1和X2X2中的數據樣本都不是公司職員7個標號為c1的有3個，n12=3標號為c2的有4個，n22=4那么可得p12=3/7p22=4/7A1-公司職員C-買保險否c2否c2否c1否c1是c1是c2是c1否c2是c1是c1是c1否c1是c1否c245第2步：計算A1公司職員的熵那么計算出A1劃分訓練集所得的熵為46第3步：計算A1公司職員的信息增益47第4步：求出其他描畫屬性的信息增益Gain(A2

17、)=0.246Gain(A3)=0.029Gain(A4)=0.048經比較可知Gain(A2)最大，所以選擇A2年齡作為決策樹的根節點進一步將樹劃分為3個分支48第5步：根據根節點劃分數據集年齡50的子集在此子集內繼續檢查Gain(A1)、Gain(A3)、Gain(A4)選取信息增益最大的描畫屬性作為內部節點A1-公司職員A3-收入A4-信譽度C-買保險否中良c1是低良c1是低優c2是中良c1否中優c251ID3算法小結運用ID3算法的根本思想是采用自頂向下的遞歸方式，將原始樣本空間劃分成假設干更小的樣本空間再對他們單獨進展處置其中，選擇哪一個描畫屬性作為新建節點，根據是調查該描畫屬性的信

18、息增益能否最大52Part IIIC4.5算法下載地址httprulequest/Personal/53ID3的缺乏1/2運用信息增益作為屬性選擇根據帶有傾向性，傾向于選擇取值較多的屬性 為什么？一種能夠的解釋是：對于較難分類的集合，優先將樣本分割到盡能夠多的分支中將極大簡化分類任務54ID3的缺乏2/2無法處置未知值的樣本對于個別樣本缺失了某項描畫屬性的情況，無法處置無法處置延續值的樣本對于描畫屬性是延續值的情況，無法處置55變化一：運用信息增益比56變化二：處置未知值的訓練樣本1/2思想將未知值用最常用的值來替代較容易或，根據現有取值的概率分布來估計未知值較真實顯然：根據思想一，在知樣本中

19、年齡的三個區間分布是50，5人那么可以直接指定未知值為“50A2-年齡C-買保險=40c250c150c150c24150c1=40c250c1？c14150c14150c150c257變化二：處置未知值的訓練樣本2/2思想將未知值用最常用的值來替代較容易或，根據現有取值的概率分布來估計未知值較真實顯然：根據思想二，在知樣本中年齡的三個區間分布是50，5人思索未知值樣本后，分布更新為50，5+5/13人A2-年齡C-買保險=40c250c150c150c24150c1=40c250c1？c14150c14150c150c258變化三：處置延續值的訓練樣本1/10思想將一切數據樣本按照延續型描畫

20、屬性Ac的詳細取值，由小到大進展升序陳列，得到的屬性值取值序列A1c,A2c,.,Atotalc在A1c,A2c,.,Atotalc中生成total-1個分割點，第i個分割點的取值設置為vi=(Aic+A(i+1)c)/2或者vi=Aic該分割點將數據集劃分為兩個子集，即描畫屬性Ac的取值在區間A1c,vi的數據樣本和在區間(vi,Atotalc的數據樣本，顯然劃分共有total-1種方式從total-1個分割點中選擇最正確分割點。對于每一個分割點劃分數據集的方式，計算其信息增益比，從中選擇信息增益比最大的分割點來劃分數據集59變化三：處置延續值的訓練樣本2/10例如求利用C4.5算法在延續值

21、描畫屬性A上的最正確分割點解：第0步，將A的取值升序陳列65,70,70,70,75,78,80,80,80,85,90,90,95,96第1步，計算vi=65時的信息增益比AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c260變化三：處置延續值的訓練樣本3/10解：第1步，計算vi=65時的信息增益比AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c261變化三：處置延續值的訓練樣本4/10解：第1步，計算vi=65時的信息增益比AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c262變化三：處置延續值的訓練樣本5/10解：第2步，計算vi=70時的信息增益比AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c263變化三：處置延續值的訓練樣本6/10解：第2步，計算vi=70時的信息增益比AC85c290c278c196c180c170c265c195c270c180c170c190c175c180c264變化三：處置延續值的訓練樣本7/10解：第2步，計