婷婷五月超碰在线,伊人男人天堂,岛国福利AV在线

序

其實不同的決策樹學習算法只是它們選擇特征的依據(jù)不同，決策樹的生成過程都是一樣的（根據(jù)當前環(huán)境對特征進行貪婪的選擇）。

ID3算法的核心是在決策樹各個節(jié)點上應(yīng)用信息增益準則選擇特征，每一次都選擇使得信息增益最大的特征進行分裂，遞歸地構(gòu)建決策樹。
ID3算法以信息增益作為劃分訓(xùn)練數(shù)據(jù)集的特征，有一個致命的缺點。選擇取值比較多的特征往往會具有較大的信息增益，所以ID3偏向于選擇取值較多的特征。

針對ID3算法的不足，C4.5算法根據(jù)信息增益比來選擇特征，對這一問題進行了校正。

CART指的是分類回歸樹，它既可以用來分類，又可以被用來進行回歸。CART用作回歸樹時用平方誤差最小化作為選擇特征的準則，用作分類樹時采用基尼指數(shù)最小化原則，進行特征選擇，遞歸地生成二叉樹。

ID3

算法思想
ID3根據(jù)具有最高信息增益的屬性作為分割點
算法核心是在決策樹各個節(jié)點上應(yīng)用信息增益準則選擇特征，遞歸地構(gòu)建決策樹，具體方法是：從根節(jié)點出發(fā)，對節(jié)點計算所有可能的信息增益，選擇信息增益最大的特征最為節(jié)點的特征，由該特征的不同取值建立子節(jié)點；再對子節(jié)點遞歸地調(diào)用以上方法，構(gòu)建決策樹直到所有特征的信息增益均很小或者沒有特征可以選擇為止。
創(chuàng)建樹
創(chuàng)建根節(jié)點R
如果當前dataset中的數(shù)據(jù)都是同一類，則標記R的類別應(yīng)該為該類
如果當前featurelist集合為空，則標記R的類別應(yīng)為當前dataset中樣本最多的類別。
遞歸--->
---------從featurelist中選擇屬性F（選擇gain（dataset，F(xiàn)）最大的屬性）
---------根據(jù)F的每一個值v，將dataset劃分為不同的子集DS，對于每一個DS：
-----------------創(chuàng)建根節(jié)點C
-----------------如果DS為空，節(jié)點C標記為dataset中樣本數(shù)最多的類別
-----------------如果DS不為空，節(jié)點C = ID3（DS，featurelist-F）
-----------------將節(jié)點C添加為R的子節(jié)點
缺點
ID3只進行決策樹的生成，沒有剪枝，因此容易過擬合。

C4.5

其基本思想與ID3類似，此處重點看一下其新特性。

特點
使用信息增益率
可以處理連續(xù)值
處理缺失值
基于后剪枝
優(yōu)點
產(chǎn)生的分類規(guī)則易于理解
準確率較高
缺點
構(gòu)造樹的過程中需要多次對數(shù)據(jù)集進行掃描以及排序，因此算法效率較低。
處理連續(xù)值方法：
對應(yīng)子樹中的連續(xù)值特征先進行排序，從大到小，計算兩兩之間的均值作為呆分割點，然后再使用信息增益率判斷哪個點分割后的增益率最大。

上述計算連續(xù)變量的信息增益率的方法較為耗時，下面的例子是另一種提高效率的方法：

CART樹

算法思想
cart樹既可以分類又可以回歸，是在給定輸入X的條件下輸出隨機變量Y的條件概率分布的學習方法。

回歸時使用誤差平方和進行特征選擇；
---創(chuàng)建回歸樹時，使用最小誤差平方和來決定回歸樹的最優(yōu)劃分，該劃分準則是期望劃分之后的子樹誤差方差最小

分類時根據(jù)基尼指數(shù)進行特征選擇。
---分類樹遞歸創(chuàng)建時，是選擇當前數(shù)據(jù)集中具有最小基尼指數(shù)的特征作為節(jié)點劃分來構(gòu)建決策樹

cart樹使用后剪枝來降低過擬合風險。

CART算法采用一種二分遞歸分割的技術(shù)，算法總是將當前樣本集分割為兩個子樣本集，使得生成的決策樹的每個非葉結(jié)點都只有兩個分枝。因此CART算法生成的決策樹是結(jié)構(gòu)簡潔的二叉樹。因此CART算法適用于樣本特征的取值為是或非的場景，對于連續(xù)特征的處理則與C4.5算法相似。

特點
二元劃分，使得二叉樹不易產(chǎn)生數(shù)據(jù)碎片，精度往往較高
連續(xù)值特征使用最小平方殘差，最小絕對殘差
分類屬性特征使用gini指數(shù)
基尼指數(shù)

gini越小，代表樣本純度越高
基尼增益
衡量出某個屬性（特征）的全部取值的gini指數(shù)就可以得到分割點：i 表示特征的第 i 個取值。

在二分切割下（i=1,2），根據(jù)訓(xùn)練集N中的屬性F將N劃分為N1 N2，因此gini增益可表示為：
分類樹的學習過程
針對屬性A，分類后的基尼指數(shù)是：

每次講樣本集合劃分為兩類，即每個中間節(jié)點產(chǎn)生兩個分支，如果特征屬性個數(shù)>2，即n>2時，這時我們就需要一個閾值 $\beta$ （劃分次數(shù)）， $\beta$ 將D分割為D1 D2，不同的 $\beta$ 得到不同的D1 D2，重新設(shè)定D1樣本數(shù)為L，D2樣本數(shù)為R，因此L+R=D，上式求和符號鋪展后可改寫為：

根代入Gini計算公式：

因為我們要求解基尼指數(shù)最小值作為最佳分類點，對上式求極小也就是對下式求最大：

上面就是整個分類樹的學習過程。
回歸樹
使用均方誤差來代替熵的計算：N代表D集合的樣本數(shù)量， $y_i$ 和 $r_i$ 分別為第 $i$ 個樣本的輸出值和預(yù)測值：

如果使用樣本的輸出值的均值來代替樣本的預(yù)測值，則上式可寫為：

如果在某個節(jié)點上，根據(jù)某一特征屬性A，將集合D劃分為s個部分，則劃分后的均方誤差為下式，其中 $D_i$ 代表樣本子集， $N_i$ 是 $D_i$ 樣本子集樣本個數(shù)。

上式與上上式子相減，即為劃分為s個部分后的誤差減少了：

如果僅考慮二叉樹的情況，即每個節(jié)點只有兩個分支，此時S=2，基于特征屬性A，集合D被閾值 $\beta$ 劃分為D1 D2兩個集合，每個集合的樣本個數(shù)為L和R，那么：其實在cart回歸樹中，基本都是二叉樹，因此只考慮s=2的情況：

將LS（D）計算公式代入上式：

上式中， $y_i$ 是樣本集合D的label， $l_i$ 和 $r_i$ 分別是D1和D2的樣本label，求上式的最大值，即求下式的最大：