分类算法之决策树介绍
實(shí)習(xí)了一段時(shí)間，接觸了一些數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)的算法，先記錄下來(lái)方便以后的復(fù)習(xí)回顧：
?
一：決策樹(shù)概念
決策樹(shù)可以看做一個(gè)樹(shù)狀預(yù)測(cè)模型，它是由節(jié)點(diǎn)和有向邊組成的層次結(jié)構(gòu)。樹(shù)中包含3中節(jié)點(diǎn)：根節(jié)點(diǎn)、內(nèi)部節(jié)點(diǎn)、葉子節(jié)點(diǎn)。決策樹(shù)只有一個(gè)根節(jié)點(diǎn)，是全體訓(xùn)練數(shù)據(jù)的集合。樹(shù)中每個(gè)內(nèi)部節(jié)點(diǎn)都是一個(gè)分裂問(wèn)題：指定了對(duì)實(shí)例的某個(gè)屬性的測(cè)試，它將到達(dá)該節(jié)點(diǎn)的樣本按照某個(gè)特定的屬性進(jìn)行分割，并且該節(jié)點(diǎn)的每一個(gè)后繼分支對(duì)應(yīng)于該屬性的一個(gè)可能值。每個(gè)葉子節(jié)點(diǎn)是帶有分類標(biāo)簽的數(shù)據(jù)集合即為實(shí)例所屬的分類。
決策樹(shù)算法很多，例如：ID3、C4.5、CART等。這些算法均采用自上而下的貪婪算法，每個(gè)內(nèi)部節(jié)點(diǎn)選擇分類效果最好的屬性來(lái)分裂節(jié)點(diǎn)，可以分成兩個(gè)或者更多的子節(jié)點(diǎn)，繼續(xù)此過(guò)程直到這棵決策樹(shù)能夠?qū)⑷康挠?xùn)練數(shù)據(jù)準(zhǔn)確的分類，或所有屬性都被用到為止。該算法的簡(jiǎn)化版本是在使用了全部樣本的假設(shè)來(lái)構(gòu)建決策樹(shù)的。具體步驟如下：
（1）：假設(shè)T為訓(xùn)練樣本集。
（2）：從屬性集合Attributes中選擇一個(gè)最能區(qū)別T中樣本的屬性。
（3）：創(chuàng)建一個(gè)樹(shù)節(jié)點(diǎn)，它的值為所選擇的屬性。創(chuàng)建此節(jié)點(diǎn)的子節(jié)點(diǎn)，每個(gè)子鏈代表所選屬性的一個(gè)唯一值（唯一區(qū)間），使用子鏈的值進(jìn)一步將樣本細(xì)分為子類。
? 對(duì)于每一個(gè)分支繼續(xù)重復(fù)（2）（3）的過(guò)程，直到滿足以下兩個(gè)條件之一：
(a):所有屬性已經(jīng)被這條路徑包括。
(b):與這個(gè)節(jié)點(diǎn)關(guān)聯(lián)的所有訓(xùn)練樣本都具有相同的目標(biāo)屬性（熵為0）。
下面借用《數(shù)據(jù)挖掘概念與技術(shù)》書(shū)中的一個(gè)列子來(lái)方便理解：
圖1-1
圖1-1是一個(gè)典型的決策樹(shù)，它表示概念buys_computer,即它目的是預(yù)測(cè)顧客是否可能購(gòu)買計(jì)算機(jī)。內(nèi)部節(jié)點(diǎn)用矩形表示，葉子節(jié)點(diǎn)用橢圓表示。
為了對(duì)未知的樣本分類，樣本的屬性值在決策樹(shù)上測(cè)試。我們用一些訓(xùn)練樣本構(gòu)造了圖1-1中的決策樹(shù)，每個(gè)內(nèi)部節(jié)點(diǎn)表示一個(gè)屬性上的測(cè)試，每個(gè)葉子節(jié)點(diǎn)代表一個(gè)分類（buys_computer = yes, buys_computer = no ）.
?
二：決策樹(shù)的適用情況
通常決策樹(shù)學(xué)習(xí)最適合具有以下特征的問(wèn)題：
（1）：實(shí)例是由“屬性-值”對(duì)表示的。
（2）：目標(biāo)函數(shù)具有離散的輸出值。例如上面的yes和no
（3）：實(shí)例的所有屬性都是離散值。如果是連續(xù)值或者離散值種類太多，可以把它分為不同的區(qū)間，例如上面的age分為了3個(gè)區(qū)間而不是每個(gè)獨(dú)立的值為一個(gè)判斷分支。
?
三：決策屬性的選擇
建樹(shù)算法中屬性的選擇非常重要。屬性選擇方法很多種，例如信息增益（information gain）、信息增益比（information gain ratio）、Gini 指標(biāo)（Gini Index）等方法。
ID3算法依據(jù)的是信息增益來(lái)選擇屬性,每次計(jì)算所有剩余候選屬性的信息增益，然后根據(jù)信息增益最大的一個(gè)作為此次的分類屬性。信息增益是用熵作為尺度，是衡量屬性對(duì)訓(xùn)練數(shù)據(jù)分類能力的標(biāo)準(zhǔn)。
假設(shè)表3-1為圖1-1中的訓(xùn)練樣本集：共有14條數(shù)據(jù)，屬性有：age、income、student、credit_rating,目標(biāo)屬性是：buys_computer
表3-1
下面根據(jù)表3-1和圖1-1的例子來(lái)講解某具體屬性的信息增益的計(jì)算過(guò)程：
對(duì)于某個(gè)具體的屬性A，它的信息增益計(jì)算表達(dá)式是：
?
（1）是對(duì)給定樣本分類所需的期望信息，計(jì)算過(guò)程如下：
設(shè)S是s個(gè)訓(xùn)練樣本的集合，S也就是對(duì)于表3-1中的數(shù)據(jù)，s = 14。假定類標(biāo)號(hào)屬性有m個(gè)不同值，定義m個(gè)不同類Ci（i=1,2,...m）.設(shè)si是類Ci中的樣本數(shù)，對(duì)應(yīng)表3-1和圖1-1實(shí)例中m=2,其中 C1 = yes C2 = no s1 = 9 s2 = 5 。
則：
其中pi是任意樣本屬于Ci的概率，pi = si/s .公式中的對(duì)數(shù)函數(shù)以2為底，因?yàn)樾畔⒂枚M(jìn)位編碼。
在該實(shí)例中?
?
?
（2）是根據(jù)A劃分子集的熵或期望值，計(jì)算過(guò)程如下：
設(shè)屬性A有v個(gè)不同的值{a1,...av},對(duì)應(yīng)實(shí)例中的數(shù)據(jù)，例如屬性age，分為3個(gè)不同的值:
a1為?<=30
a2為?30..40
a3為?>40 ;
屬性A把訓(xùn)練樣本集合S劃分為v個(gè)子集{S1,...Sv};其中Sj包含訓(xùn)練樣本集S中在屬性A上有值aj的樣本。Sij是子集Sj中屬于類Ci的樣本數(shù)。
其中充當(dāng)?shù)趈個(gè)子集的權(quán)值，等于子集（即A值為aj）的樣本總數(shù)除以S中的樣本總數(shù) 即 Sj/S。
對(duì)于給定的子集Sj有
其中，Pij=Sij/Sj ,是Sj中的樣本屬于Ci的概率。
該實(shí)例中：
? ? ? ? 因此屬性age的信息增益為：Gain（age）= I（s1,s2） - E(age) = 0.246
類似的我們可以計(jì)算出Gain(income)=0.029 Gain(student)=0.151 Gain(credit_rating)=0.048.由于age在屬性中具有最高信息增益，因此它被選作為第一個(gè)測(cè)試屬性。
圖1-1是最終生成的決策樹(shù)。
?
四：決策樹(shù)的剪枝
為了防止決策樹(shù)和訓(xùn)練樣本集的過(guò)度擬合，需要對(duì)決策樹(shù)進(jìn)行剪枝。剪枝通常有事先剪枝法和事后剪枝法。
事先剪枝法： 是建樹(shù)過(guò)程中判斷當(dāng)前節(jié)點(diǎn)是否需要繼續(xù)劃分的剪枝方法。通常是通過(guò)重要性檢測(cè)判斷是否停止分裂節(jié)點(diǎn)。
?事后剪枝法：?是讓樹(shù)充分生長(zhǎng)之后，再判斷是否將某些分支變成節(jié)點(diǎn)。常用方法是根據(jù)錯(cuò)誤分裂率（或者決策樹(shù)編碼長(zhǎng)度）進(jìn)行決策樹(shù)的事后修剪。
?
參考資料：機(jī)器學(xué)習(xí)? Mitchell T.M
數(shù)據(jù)挖掘：概念與技術(shù) 第三版 ?Jiawei Han ?
?
?
?
?
?
?
?
?
?
?
轉(zhuǎn)載于:https://www.cnblogs.com/justcxtoworld/p/3346271.html
總結(jié)
以上是生活随笔為你收集整理的分类算法之决策树介绍的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 统计在从1到n的正整数中1出现的次数
- 下一篇： 第五章（1）Libgdx应用框架之生命周