第八章 決策樹算法
本文關(guān)鍵詞：決策樹學習及其剪枝算法研究，由筆耕文化傳播整理發(fā)布。
第八章 決策樹算法
1、什么是決策樹？決策樹是一種類似于流程圖的樹結(jié)構(gòu)。其中，每個內(nèi)部結(jié)點（非樹葉結(jié)點）表示在一個屬性上的測試，每個分枝代表該測試的一個輸出，而每個樹葉結(jié)點存放一個類標號。樹的最頂層結(jié)點是根節(jié)點。內(nèi)部結(jié)點用矩形表示，而葉結(jié)點用橢圓表示。決策樹可以是二叉的，也可以是非二叉的（根據(jù)不同的決策樹算法而定）。一棵典型的決策樹如下圖：
2、如何使用決策樹分類？給定一個類標號未知的元組X，，在該決策樹上測試該元組的屬性值。跟蹤一條由根到葉結(jié)點的路徑，該葉結(jié)點就存放著該元組的類預測。
3、為什么決策樹分類器如此流行？（1）決策樹分類器的構(gòu)造不需要任何領(lǐng)域知識或參數(shù)設置，因此適合于探測式知識發(fā)現(xiàn)。
（2）決策樹可以處理高維數(shù)據(jù)。
（3）獲取的知識用樹的形式表示是直觀的，并且容易被人理解。
（4）決策樹歸納的學習和分類步驟是簡單和快速的。
（5）一般而言，決策樹分類器具有很好的準確率。
4、決策樹算法屬性選擇度量：是一種選擇分裂準則，把給定類標記的訓練元組的數(shù)據(jù)分區(qū)D“最好地”劃分成單獨類的啟發(fā)式方法。理想情況下，D劃分后的每個小分區(qū)都是純的（即落在一個給定分區(qū)的所有元組都屬于相同的類）�！白詈玫摹狈诸悳蕜t是最接近這種情況的劃分。
根據(jù)分裂屬性選擇度量的不同，決策樹的常見算法有ID3（度量：信息增益）、C4.5（度量：增益率）、CART（度量：基尼指數(shù)）。當然，決策樹算法之間的差別也包括用于剪枝的機制等。
它們都采用貪心（即非回溯）的方法，其中決策樹以自頂向下遞歸的分治法構(gòu)造。大多數(shù)決策樹算法都沿用這種自頂向下方法，從訓練元組集和它們相關(guān)聯(lián)的類標號開始構(gòu)造決策樹。隨著樹的構(gòu)建，訓練集遞歸地劃分成較小的子集。這些子集分布在第一個決策點的所有分支上。如果某個分支下的數(shù)據(jù)屬于同一類型，則當前已經(jīng)正確地劃分數(shù)據(jù)分類，無需進一步對數(shù)據(jù)集進行分割。如果數(shù)據(jù)子集內(nèi)的數(shù)據(jù)不屬于同一類型，則需要重復劃分數(shù)據(jù)子集的過程。如何劃分數(shù)據(jù)子集的算法和劃分原始數(shù)據(jù)集的方法相同，直到所有具有相同類型的數(shù)據(jù)均在一個數(shù)據(jù)子集內(nèi)。
基本決策樹算法概括在下圖中：
遞歸的終止條件是：程序遍歷完所有劃分數(shù)據(jù)集的屬性，或者每個分支下的所有實例都具有相同的分類。
4.1 ID3算法（信息增益）ID3算法（Iterative Dichotomiser3 迭代的二分器3代）是一位機器學習研究人員J.Ross Quinlan開發(fā)的決策樹算法。
ID3算法的核心思想：以信息增益作為屬性選擇度量（該度量基于香農(nóng)在研究消息的值或“信息內(nèi)容”的信息論方面的先驅(qū)工作），選擇分裂后信息增益最大的屬性進行分裂。該算法采用自頂向下的貪婪搜索遍歷可能的決策樹空間。
思想：（1）自頂向下的貪婪搜索遍歷可能的決策樹空間構(gòu)造決策樹
（2）從“哪一個屬性將在樹的根節(jié)點被測試”開始；
（3）使用統(tǒng)計測試來確定每一個實例屬性單獨分類訓練樣例的能力，分類能力最好的屬性作為樹的根結(jié)點測試。
（4）然后為根結(jié)點屬性的每個可能值產(chǎn)生一個分支，并把訓練樣例排列到適當?shù)姆种Вㄒ簿褪钦f，樣例的該屬性值對應的分支）之下。
（5）重復這個過程，用每個分支結(jié)點關(guān)聯(lián)的訓練樣例來選取在該點被測試的最佳屬性。
信息增益：原來的信息需求（僅基于類比例）與新的信息需求（對屬性A劃分后）之間的差。
Gain（A）告訴我們通過屬性A上的劃分我們得到了多少。選擇具有最高增益Gain（A）的屬性A作為分裂屬性。這等價于在“能做最佳分類”的屬性A上劃分，使得完成 元組分類還需要的信息最小（即最小化InfoA（D））
對D中的元組分類所需的期望信息由下式給出：
離散屬性A（具有v個不同的觀測值）對D進行屬性劃分后所需要的期望信息：
例子：顧客數(shù)據(jù)庫標記類的訓練元組
類似地，可以計算Gain（income）=0.029位 Gain（student）=0.151位 Gain（credit_rating）=0.048位。
由于age在屬性中具有最高的信息增益，所以它被選作分裂屬性。并且每個屬性值生長出一個分枝，然后元組據(jù)此劃分。
其中，落在分區(qū)age=“middle_age”的元組都屬于相同的類。由于它們都屬于類“yes”，所以要在該分枝的端點創(chuàng)建一個樹葉，并用“yes”標記。 算法返回的最終決策樹 如下圖：
上面我們說的分裂屬性都是離散值的，如果是連續(xù)值的我們怎么計算它們的信息增益呢？假設屬性A是連續(xù)值的，而不是離散值的（例如，假定有屬性age的原始值，而不是該屬性的離散化版本。）對于這種情況，必須確定A的“最佳”分裂點，其中分裂點是A上的閾值。
首先，將A的值按遞增序排序。典型地，每對相鄰值的中點被看作可能的分裂點。這樣，給定A的v個值，則需要計算v-1個可能的劃分。對于A的每個可能的分裂點，計算Info（D），其中分區(qū)的個數(shù)為2，A具有最小期望信息需求的點選作A的分裂點。D1是滿足A<=split_poin的元組集合，而D2是滿足A>split_poin的元組集合。這樣的話，就轉(zhuǎn)換成離散屬性的計算了。
在此，順便介紹一下，根據(jù)屬性分裂準則劃分元組的三種可能性：
4.2 C4.5算法（增益率） ID3的缺點：信息增益度量偏向具有許多輸出的測試。換句話說，它傾向于選擇具有大量值的屬性。例如，考慮充當唯一標識符的屬性，如product_ID。在product_ID的劃分將導致大量分區(qū)（與值一樣多），每個只包含一個元組。由于每個分區(qū)都是純的，所以基于該劃分對數(shù)據(jù)集D分類所需要的信息為Infoproduct_ID(D)=0。因此，通過對該屬性的劃分得到的信息增益最大。顯然，這種劃分對分類沒有用。C4.5的出現(xiàn)就是為了克服這種偏倚。
C4.5：也是Quinlan提出來的，它是對ID3算法的改進，這些改進包括處理數(shù)值屬性、缺失值、噪聲數(shù)據(jù)和由決策樹產(chǎn)生規(guī)則的方法。C4.5采用增益率作為屬性選擇度量，增益率定義為：
其中，分裂信息度量被定義為(分裂信息用來衡量屬性分裂數(shù)據(jù)的廣度和均勻)：
事務數(shù)據(jù)庫中屬性income的增益率的計算：
4.3 CART算法（基尼指數(shù)）CART：分類和回歸樹（ClassificationAnd Regression Tree）算法由Breiman等人于1984年提出的。它是以二叉樹的形式給出，易于理解、使用和解釋。如果目標變量是離散的，則該樹為分類樹（classification tree），而對于連續(xù)數(shù)值目標變量，則該樹稱為回歸樹（regression
tree）。
Gini指數(shù)：是一種不等性度量，由意大利統(tǒng)計學家Corrado Gini提出，并于1912年發(fā)表在他的文章“Variabilita e mutabilita”中。它通常用來度量收入不平衡，但是它可以用來度量任何不均勻分布。Gini指數(shù)是一個0—1之間的數(shù)。其中0對應于完全相等（其中每個人都具有相同的收入），而1對應于完全不相等（其中一個人具有所有收入，而其他人收入都為零）�；�尼指數(shù)度量數(shù)據(jù)分區(qū)或訓練元組集D的不純度，定義為：
基尼指數(shù)考慮每個屬性的二元劃分。
（1）首先考慮A是離散值屬性的情況，其中A具有v個不同值出現(xiàn)在D中。如果A具有v個可能的值，則存在2v個可能的子集。例如，如果income具有3個可能的值{low,medium,high}，則可能的子集具有8個。不考慮冪集（{
low,medium,high}）和空集（{ }），因為從概念上講，它不代表任何分裂。因此，基于A的二元劃分，存在2v -2中形成數(shù)據(jù)集D的兩個分區(qū)的可能方法。
當考慮二元劃分裂時，計算每個結(jié)果分區(qū)的不純度的加權(quán)和。例如，如果A的二元劃分將D劃分成D1和D2，則給定該劃分，D的基尼指數(shù)為
選擇該屬性產(chǎn)生最小基尼指數(shù)的子集作為它的分裂子集。
（2）對于連續(xù)值屬性，其策略類似于上面介紹的信息增益所使用的策略。
對于離散或連續(xù)值屬性A的二元劃分導致的不純度降低為
最大化不純度降低（或等價地，具有最小基尼指數(shù)）的屬性選為分裂屬性。該屬性和它的分裂子集（對于離散值的分裂屬性）或分裂點（對于連續(xù)值的分裂屬性）一起 形成分裂準則。
例子：繼續(xù)使用“顧客數(shù)據(jù)庫”進行介紹。
（1）計算D的不純度：
（2）為了找出D中元組的分裂準則，需要計算每個屬性的基尼指數(shù)。從屬性income開始，并考慮每個可能的分裂子集�？紤]子集{low，medium}，基于該劃分計算出的基尼指數(shù)為：
類似地，其余子集劃分的基尼指數(shù)值是：0.458（子集{low，high}和{medium}）和0.450（子集{medium，high}和{low}）。因此，屬性income的最好劃分在{low，medium}（或{high}） 上，因為它最小化基尼指數(shù)。
評估屬性age，得到{youth，senior}（或{middle_aged}）為age的最好劃分，具有基尼指數(shù)0.357；
屬性student和credit_rating都是二元的，分別具有基尼指數(shù)值0.367和0.429。
（3）屬性age和分裂子集{youth，senior}產(chǎn)生最小的基尼指數(shù)。二元劃分“age屬于{youth，senior}？”導致D中元組的不純度降低最大，并返回作為分裂準則。從它生長出兩個分枝，并且相應地劃分元組。5、決策樹算法之間的比較
信息增益偏向于多值屬性。盡管增益率調(diào)整了這種偏倚，但是它傾向于產(chǎn)生不平衡的劃分，其中一個分區(qū)比其他分區(qū)小得多�；�尼指數(shù)偏向于多值屬性，并且當類的數(shù)量很大時會有困難。它還傾向于導致相等大小的分區(qū)和純度。盡管是有偏的，但是這些度量在實踐中產(chǎn)生相當好的結(jié)果。6、樹剪枝
決策樹為什么要剪枝？原因是避免決策樹過擬合(Overfitting)樣本。前面的算法生成的決策樹非常詳細并且龐大，每個屬性都被詳細地加以考慮，決策樹的樹葉節(jié)點所覆蓋的訓練樣本都是“純”的。因此用這個決策樹來對訓練樣本進行分類的話，你會發(fā)現(xiàn)對于訓練樣本而言，這個樹表現(xiàn)完好，誤差率極低且能夠正確得對訓練樣本集中的樣本進行分類。訓練樣本中的錯誤數(shù)據(jù)也會被決策樹學習，成為決策樹的部分，但是對于測試數(shù)據(jù)的表現(xiàn)就沒有想象的那么好，或者極差，這就是所謂的過擬合(Overfitting)問題。
“如何進行剪枝？”有兩種常用的剪枝方法：先剪枝和后剪枝先剪枝：通過提前停止樹的構(gòu)建（例如，通過決定在給定的節(jié)點不再分裂或劃分訓練元組的子集）而對樹“剪枝”。一旦停止，結(jié)點就成為樹葉。該樹葉可以持有子集元組中最頻繁的類，或這些元組的概率分布。
在構(gòu)造樹時，可以使用諸如統(tǒng)計顯著性、信息增益、基尼指數(shù)等度量來評估劃分的優(yōu)劣。如果劃分一個結(jié)點的元組導致低于預定義閾值的劃分，則給定子集的進一步劃分將停止。然而，選取一個適當?shù)拈?#20540;是困難的。高閾值可能導致過分簡化的樹，而低閾值可能使得樹的簡化太少。
例子：限定樹的最大生長高度為3
例子：
CART使用的是：代價復雜度（后剪枝方法的一種實例）剪枝算法。
該方法把樹的復雜度看作樹中樹葉結(jié)點的個數(shù)和樹的錯誤率的函數(shù)（其中，錯誤率是樹誤分類的元組所占的百分比）。它從樹的底部開始。對于每個內(nèi)部結(jié)點N，計算N的子樹的代價復雜度和該子樹剪枝后N的子樹（即用一個樹葉節(jié)點替換）的代價復雜度，比較這兩個值。如果剪去結(jié)點N的子樹導致較小的代價復雜度，則剪掉該子樹；否則，保留該子樹。
C4.5使用的是：悲觀剪枝。它類似于代價復雜度方法，因為它也使用錯誤率評估，對子樹剪枝做出決定。
剪枝后還可能存在什么困擾？另外，對于組合方法，先剪枝和后剪枝可以交叉使用。后剪枝所需要的計算比先剪枝多，但是通常產(chǎn)生更可靠的樹。
盡管剪枝后的樹一般比未剪枝的樹更緊湊，但是他們?nèi)匀豢赡芎艽�、很復雜。決策樹可能受到重復和復制的困擾，使得他們很難解釋。
沿著一條給定的分枝反復測試一個屬性時就會出現(xiàn)重復。復制是樹中存在重復的子樹。這些情況影響了決策樹的準確率和可解釋性。
解決辦法：（1）使用多元劃分（基于組合屬性的劃分）（2）使用不同形式的知識表示（如規(guī)則），而不是決策樹。
決策樹分類及剪枝算法研究_張宇（哈爾濱理工大學）
決策樹學習及其剪枝算法研究_王黎明（武漢理工大學）
7、可伸縮性與決策樹歸納（后期續(xù)寫）
猜你在找
本文關(guān)鍵詞：決策樹學習及其剪枝算法研究，由筆耕文化傳播整理發(fā)布。
本文編號：243486
本文鏈接：http://sikaile.net/guanlilunwen/tongjijuecelunwen/243486.html
