2019以ID3算法為例探討數據挖掘中決策樹算法應用課件.ppt

《2019以ID3算法為例探討數據挖掘中決策樹算法應用課件.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、以ID3算法為例探討數據挖掘中決策樹算法的應用主講：郭佳2019.11.28決策樹是一種常用于預測模型的算法，它通過將大量數據有目的分類，從中找到一些有價值的，潛在的信息。它的主要優(yōu)點是描述簡單，分類速度快，特別適合大規(guī)模的數據處理。最有影響和最早的決策樹方法是由Quinlan在1986年提出的著名的基于信息熵的ID3算法。接下來主要介紹ID3算法。決策樹算法的概念由ID3算法得到的決策樹決策樹分類是一種從無次序、無規(guī)則的訓練樣本集中推理出決策樹表示形式的分類規(guī)則的方法。它采用自頂向下的方法，在決策

2、樹的內部結點進行屬性值的比較并根據不同的屬性值判斷從該結點向下的分支，在決策樹的葉結點得到結論。所以從根結點到任一個葉結點所形成的一條路徑就構成了一條分類規(guī)則，葉結點所標記的類別就構成了規(guī)則的結論內容。決策樹算法的概念數據挖掘是由可以獲取的數據驅動的，其成功在很大程度上取決于數據的數量和質量。我們應從大量的企業(yè)客戶數據中找到與分析問題有關的樣本數據子集。這樣可以減少處理的數據量，但必須保證其樣本子集具有典型的代表性。然后，進行數據預處理、分析，盡可能的對問題解決的要求進一步明確化、量化。按問題要求對

3、數據進行增刪或組合生成新的變量，以體現對問題狀態(tài)的有效描述。用于分類的訓練數據源組將具體的客戶年齡概化為<=30、31-50、>50三個年齡段，分別代表青年、中年和老年客戶，將產品價格分為高、中、低三檔等，具體見表1，有4個屬性：客戶年齡段、文化程度、銷售地區(qū)、產品檔次，類別是銷售業(yè)績，分為好和差兩類。以某類產品的銷售記錄數據為例表1訓練樣本集合ID3算法是一種根據熵減（EntropyDeduce）理論選擇最優(yōu)的描述屬性的方法。該算法從樹的根節(jié)點處的所含訓練樣本開始，選取一個屬性來區(qū)分這些樣本。對屬

4、性的每一個值產生一個分支。分支屬性的相應樣本子集被移到新生成的子節(jié)點上。這個算法遞歸地應用于每個子節(jié)點，直到一個節(jié)點上的所有樣本都分區(qū)到某個類中。算法中屬性選擇的基礎是基于使節(jié)點所含的信息熵最小化。ID3算法原理具體方法如下：設S為一個包含s個數據樣本的集合，類別屬性可以取m個不同的值，對應于m個不同的類別，。假設為類別中的樣本個數，若要對一個給定數據對象進行分類，決策樹的構造過程如下：(1)計算初始熵其中是任意一個數據對象屬于類別的概率，可以按計算。ID3算法原理(2)屬性的選擇設一個屬性A取v個

5、不同的值。可以用屬性A將集合S劃分為v個子集，其中包含了集合S中屬性A取值的數據樣本。若屬性A被選為測試屬性，設為子集中屬于類別的樣本數。則利用屬性A劃分當前樣本集合所需要的信息（熵）可以計算如下：ID3算法原理其中被當作第j個子集的權值，它是由子集中屬性A取aj值的樣本數之和除以S集合中的樣本總數，E(A)的值越小，表示子集劃分結果越好。I是對于一個給定子集的信息熵，計算方法為：這樣利用屬性A對當前分支節(jié)點進行相應樣本集合劃分所獲得的信息增益為：Gain(A)=-E(A)換言之，Gain(A)被認

6、為是根據屬性A取值進行樣本集合劃分所獲得的信息熵的減少量，也可以說是由于知道屬性A的值而導致的熵的期望壓縮。ID3算法原理ID3算法計算每個屬性的信息增益，并從中選擇出信息增益最大的屬性作為給定集合的測試屬性并由此產生相應的分支節(jié)點。所產生的節(jié)點被標記為相應的屬性，并根據這一屬性的不同取值分別產生相應決策樹分支，每個分支代表一個被劃分的樣本子集。ID3算法原理由表1可知：類標號屬性有兩個不同的值，因此有兩個不同的類（即m=2）設類C1對應于good，類C2對應于bad。類good有18個樣本，類ba

7、d有8個樣本。為了計算每個屬性的信息增益，先使用計算初始信息熵為：I(s1,s2)=I(18,8)=-ID3算法分類模型的建立下一步，需要計算每個屬性的熵，即客戶年齡age、文化程度education、產品檔次level和銷售區(qū)域area。先看age屬性，觀察age的每個樣本值的good、bad分布，對每個分布分別計算信息熵：當age<=30：s11=9s21=2時，I(s11,s21)=-當age在31-50間：s12=8s22=4時，I(s12,s22)=-當age>=50：s13=1s23=2

8、時，I(s13,s23)=-如果樣本按age劃分，對一個給定的樣本分類所需的信息熵為：E(age)==0.8192類似的，可以得到：E(education)==0.7669E(level)==0.853E(area)=利用上述屬性對當前分支節(jié)點進行相應樣本集合劃分所獲得的信息增益分別為：Gain(age)=I(s1,s2)-E(age)=0.895-0.8192=0.0758Gain(education)=I(s1,s2)-E(education)=0.895-0.7