比較樹演算法

Ⅰ 請比較k近鄰，決策樹和樸素貝葉斯這三種分類演算法之間的異同點

決策樹演算法主要包括id3，c45，cart等演算法，生成樹形決策樹，而樸素貝葉斯是利用貝葉斯定律，根據先驗概率求算後驗概率。

如果訓練集很小，那麼高偏差/低方差分類器（如樸素貝葉斯分類器）要優於低偏差/高方差分類器（如k近鄰分類器），因為後者容易過擬合。然而，隨著訓練集的增大，低偏差/高方差分類器將開始勝出（它們具有較低的漸近誤差），因為高偏差分類器不足以提供准確的模型。

一些特定演算法的優點：

樸素貝葉斯的優點：

超級簡單，你只是在做一串計算。如果樸素貝葉斯（NB）條件獨立性假設成立，相比於邏輯回歸這類的判別模型，樸素貝葉斯分類器將收斂得更快，所以只需要較小的訓練集。而且，即使NB假設不成立，樸素貝葉斯分類器在實踐方面仍然表現很好。

如果想得到簡單快捷的執行效果，這將是個好的選擇。它的主要缺點是，不能學習特徵之間的相互作用（比如，它不能學習出：雖然你喜歡布拉德·皮特和湯姆·克魯斯的電影，但卻不喜歡他們一起合作的電影）。

邏輯回歸的優點：

有許多正則化模型的方法，不需要像在樸素貝葉斯分類器中那樣擔心特徵間的相互關聯性。與決策樹和支撐向量機不同，還可以有一個很好的概率解釋，並能容易地更新模型來吸收新數據（使用一個在線梯度下降方法）。

如果想要一個概率框架（比如，簡單地調整分類閾值，說出什麼時候是不太確定的，或者獲得置信區間），或你期望未來接收更多想要快速並入模型中的訓練數據，就選擇邏輯回歸。

決策樹的優點：

易於說明和解釋（對某些人來說—我不確定自己是否屬於這個陣營）。它們可以很容易地處理特徵間的相互作用，並且是非參數化的，所以你不用擔心異常值或者數據是否線性可分（比如，決策樹可以很容易地某特徵x的低端是類A，中間是類B，然後高端又是類A的情況）。

一個缺點是，不支持在線學習，所以當有新樣本時，你將不得不重建決策樹。另一個缺點是，容易過擬合，但這也正是諸如隨機森林（或提高樹）之類的集成方法的切入點。另外，隨機森林往往是很多分類問題的贏家（我相信通常略優於支持向量機），它們快速並且可擴展，同時你不須擔心要像支持向量機那樣調一堆參數，所以它們最近似乎相當受歡迎。

(1)比較樹演算法擴展閱讀：

樸素貝葉斯演算法：

設每個數據樣本用一個n維特徵向量來描述n個屬性的值，即：X={x1，x2，…，xn}，假定有m個類，分別用C1, C2,…，Cm表示。給定一個未知的數據樣本X（即沒有類標號），若樸素貝葉斯分類法將未知的樣本X分配給類Ci，則一定是

P(Ci|X)>P(Cj|X) 1≤j≤m，j≠i

根據貝葉斯定理：

由於P(X)對於所有類為常數，最大化後驗概率P(Ci|X)可轉化為最大化先驗概率P(X|Ci)P(Ci)。如果訓練數據集有許多屬性和元組，計算P(X|Ci)的開銷可能非常大，為此，通常假設各屬性的取值互相獨立，這樣

先驗概率P(x1|Ci)，P(x2|Ci)，…，P(xn|Ci)可以從訓練數據集求得。

根據此方法，對一個未知類別的樣本X，可以先分別計算出X屬於每一個類別Ci的概率P(X|Ci)P(Ci)，然後選擇其中概率最大的類別作為其類別。

樸素貝葉斯演算法成立的前提是各屬性之間互相獨立。當數據集滿足這種獨立性假設時,分類的准確度較高，否則可能較低。另外，該演算法沒有分類規則輸出。

TAN演算法（樹增強型樸素貝葉斯演算法）

TAN演算法通過發現屬性對之間的依賴關系來降低NB中任意屬性之間獨立的假設。它是在NB網路結構的基礎上增加屬性對之間的關聯(邊)來實現的。

實現方法是：用結點表示屬性，用有向邊表示屬性之間的依賴關系，把類別屬性作為根結點，其餘所有屬性都作為它的子節點。通常，用虛線代表NB所需的邊，用實線代表新增的邊。屬性Ai與Aj之間的邊意味著屬性Ai對類別變數C的影響還取決於屬性Aj的取值。

這些增加的邊需滿足下列條件：類別變數沒有雙親結點，每個屬性有一個類別變數雙親結點和最多另外一個屬性作為其雙親結點。

Ⅱ 數據挖掘-決策樹演算法

決策樹演算法是一種比較簡易的監督學習分類演算法，既然叫做決策樹，那麼首先他是一個樹形結構，簡單寫一下樹形結構（數據結構的時候學過不少了）。

樹狀結構是一個或多個節點的有限集合，在決策樹里，構成比較簡單，有如下幾種元素：

在決策樹中，每個葉子節點都有一個類標簽，非葉子節點包含對屬性的測試條件，用此進行分類。
所以個人理解，決策樹就是 對一些樣本，用樹形結構對樣本的特徵進行分支，分到葉子節點就能得到樣本最終的分類，而其中的非葉子節點和分支就是分類的條件，測試和預測分類就可以照著這些條件來走相應的路徑進行分類。

根據這個邏輯，很明顯決策樹的關鍵就是如何找出決策條件和什麼時候算作葉子節點即決策樹終止。

決策樹的核心是為不同類型的特徵提供表示決策條件和對應輸出的方法，特徵類型和劃分方法包括以下幾個：

注意，這些圖中的第二層都是分支，不是葉子節點。

如何合理的對特徵進行劃分，從而找到最優的決策模型呢？在這里需要引入信息熵的概念。

先來看熵的概念：

在數據集中，參考熵的定義，把信息熵描述為樣本中的不純度，熵越高，不純度越高，數據越混亂（越難區分分類）。

例如：要給（0，1）分類，熵是0，因為能明顯分類，而均衡分布的（0.5，0.5）熵比較高，因為難以劃分。

信息熵的計算公式為：
其中 代表信息熵。 是類的個數， 代表在 類時 發生的概率。
另外有一種Gini系數，也可以用來衡量樣本的不純度：
其中 代表Gini系數，一般用於決策樹的 CART演算法 。

舉個例子：

如果有上述樣本，那麼樣本中可以知道，能被分為0類的有3個，分為1類的也有3個，那麼信息熵為：
Gini系數為：
總共有6個數據，那麼其中0類3個，佔比就是3/6，同理1類。

我們再來計算一個分布比較一下：

信息熵為：
Gini系數為：

很明顯，因為第二個分布中，很明顯這些數偏向了其中一類，所以 純度更高 ，相對的信息熵和Gini系數較低。

有了上述的概念，很明顯如果我們有一組數據要進行分類，最快的建立決策樹的途徑就是讓其在每一層都讓這個樣本純度最大化，那麼就要引入信息增益的概念。

所謂增益，就是做了一次決策之後，樣本的純度提升了多少（不純度降低了多少），也就是比較決策之前的樣本不純度和決策之後的樣本不純度，差越大，效果越好。
讓信息熵降低，每一層降低的越快越好。
度量這個信息熵差的方法如下：
其中 代表的就是信息熵（或者其他可以度量不純度的系數）的差， 是樣本(parent是決策之前， 是決策之後)的信息熵（或者其他可以度量不純度的系數）， 為特徵值的個數， 是原樣本的記錄總數， 是與決策後的樣本相關聯的記錄個數。

當選擇信息熵作為樣本的不純度度量時，Δ就叫做信息增益 。

我們可以遍歷每一個特徵，看就哪個特徵決策時，產生的信息增益最大，就把他作為當前決策節點，之後在下一層繼續這個過程。

舉個例子：

如果我們的目標是判斷什麼情況下，銷量會比較高（受天氣，周末，促銷三個因素影響），根據上述的信息增益求法，我們首先應該找到根據哪個特徵來決策，以信息熵為例：

首先肯定是要求 ，也就是銷量這個特徵的信息熵：

接下來，就分別看三個特徵關於銷量的信息熵，先看天氣，天氣分為好和壞兩種，其中天氣為好的條件下，銷量為高的有11條，低的有6條；天氣壞時，銷量為高的有7條，銷量為低的有10條，並且天氣好的總共17條，天氣壞的總共17條。

分別計算天氣好和天氣壞時的信息熵，天氣好時：

根據公式 ，可以知道，N是34，而天氣特徵有2個值，則k=2，第一個值有17條可以關聯到決策後的節點，第二個值也是17條，則能得出計算：

再計算周末這個特徵，也只有兩個特徵值，一個是，一個否，其中是有14條，否有20條；周末為是的中有11條銷量是高，3條銷量低，以此類推有：


信息增益為：

另外可以得到是否有促銷的信息增益為0.127268。

可以看出，以周末為決策，可以得到最大的信息增益，因此根節點就可以用周末這個特徵進行分支：

注意再接下來一層的原樣本集，不是34個而是周末為「是」和「否」分別計算，為是的是14個，否的是20個。
這樣一層一層往下遞歸，直到判斷節點中的樣本是否都屬於一類，或者都有同一個特徵值，此時就不繼續往下分了，也就生成了葉子節點。

上述模型的決策樹分配如下：

需要注意的是，特徵是否出現需要在分支當中看，並不是整體互斥的，周末生成的兩個分支，一個需要用促銷來決策，一個需要用天氣，並不代表再接下來就沒有特徵可以分了，而是在促銷決策層下面可以再分天氣，另外一遍天氣決策下面可以再分促銷。

決策樹的模型比較容易解釋，看這個樹形圖就能很容易的說出分類的條件。

我們知道屬性有二元屬性、標稱屬性、序數屬性和連續屬性，其中二元、標稱和序數都是類似的，因為是離散的屬性，按照上述方式進行信息增益計算即可，而連續屬性與這三個不同。

對於連續的屬性，為了降低其時間復雜度，我們可以先將屬性內部排序，之後取相鄰節點的均值作為決策值，依次取每兩個相鄰的屬性值的均值，之後比較他們的不純度度量。

需要注意的是，連續屬性可能在決策樹中出現多次，而不是像離散的屬性一樣在一個分支中出現一次就不會再出現了。

用信息熵或者Gini系數等不純度度量有一個缺點，就是會傾向於將多分支的屬性優先分類——而往往這種屬性並不是特徵。

例如上面例子中的第一行序號，有34個不同的值，那麼信息熵一定很高，但是實際上它並沒有任何意義，因此我們需要規避這種情況，如何規避呢，有兩種方式：

公式如下：

其中k為劃分的總數，如果每個屬性值具有相同的記錄數，則 ，劃分信息等於 ，那麼如果某個屬性產生了大量劃分，則劃分信息很大，信息增益率低，就能規避這種情況了。

為了防止過擬合現象，往往會對決策樹做優化，一般是通過剪枝的方式，剪枝又分為預剪枝和後剪枝。

在構建決策樹時，設定各種各樣的條件如葉子節點的樣本數不大於多少就停止分支，樹的最大深度等，讓決策樹的層級變少以防止過擬合。
也就是在生成決策樹之前，設定了決策樹的條件。

後剪枝就是在最大決策樹生成之後，進行剪枝，按照自底向上的方式進行修剪，修剪的規則是，評估葉子節點和其父節點的代價函數，如果父節點的代價函數比較小，則去掉這個葉子節點。
這里引入的代價函數公式是：
其中 代表的是葉子節點中樣本個數， 代表的是該葉子節點上的不純度度量，把每個葉子節點的 加起來，和父節點的 比較，之後進行剪枝即可。

Ⅲ 最優二叉樹演算法的判定問題中的應用

在本章的引入部分，兩個例子都是判定問題，這兩個判定問題都可以通過構造哈夫曼樹來優化判定，以達到總的判定次數最少。
再如，要編制一個將百分制轉換為五級分制的程序。顯然，此程序很簡單，只要利用條件語句便可完成。
程序段
if a<60 then b:=』bad』
else if a<70 then b:=』pass』
else if a<80 then b:=』general』
else if a<90 then b:=』good』
else b:=』excellent』;
如果上述程序需反復使用，而且每次的輸入量很大，則應考慮上述程序的質量問題，即其操作所需要的時間。因為在實際中，學生的成績在五個等級上的分布是不均勻的，假設其分布規律如表4所示： 分數 0-59 60－69 70－79 80－89 90－100 比例數 0.05 0.15 0.40 0.30 0.10 表4 分數段的分布頻率
則80%以上的數據需進行三次或三次以上的比較才能得出結果。假定以5，15，40，30和10為權構造一棵有五個葉子結點的哈夫曼樹，它可使大部分的數據經過較少的比較次數得出結果。但由於每個判定框都有兩次比較，將這兩次比較分開，得到新的判定樹，按此判定樹可寫出相應的程序。請您自己畫出此判定樹。
假設有10000個輸入數據，若上程序段的判定過程進行操作，則總共需進行31500次比較；而若新判定樹的判定過程進行操作，則總共僅需進行22000次比較。

Ⅳ 決策樹原理及演算法比較

決策樹是什麼？

    和線性回歸一樣是一種模型，內部節點和葉節點。實現分類，內部節點和葉節點通過有向線（分類規      則）連接起來

決策樹的目標是什麼？

    決策樹通過對數據復雜度的計算，建立特徵分類標准，確定最佳分類特徵。

    表現為「熵」（entropy）和信息增益（information gain），基於決策樹思想的三種演算法：ID3，C4.5,CART演算法，三種演算法的信息衡量的指標也不同.

    熵來表示信息的復雜度，熵越大，信息也就越復雜，公式如下：

那些演算法能夠實現決策樹？

    在決策樹構建過程中，什麼是比較重要的。特徵選擇（按照熵變計算），演算法產生最重要的部分，

決策樹中葉節點的分類比較純，

節點順序的排列規則：

熵變：

數據的預處理：

改進思路一般有兩個1，換演算法；2，調參數

做好數據的預處理：

1，做好特徵選擇；

2，做好數據離散化、異常值處理、缺失填充

分類器：

在決策樹中，從根到達任意一個葉節點的之間最長路徑的長度，表示對應的演算法排序中最壞情況下的比較次數。這樣一個比較演算法排序中的最壞情況的比較次數就與其決策樹的高度相同，同時如果決策樹中每種排列以可達葉子的形式出現，那麼關於其決策樹高度的下界也就是關於比較排序演算法運行時間的下界，

ID3演算法存在的缺點：

    1，ID3演算法在選擇根節點和內部節點分支屬性時，採用信息增益作為評價標准。信息增益的缺點是傾向於選擇取值較多的屬性

    2，當數據為連續性變數的時候，ID3演算法就不是一個合理的演算法的模型了

C4.5信息增益比率，

     1，在信息增益的基礎上除以split-info，是將信息增益改為信息增益比，以解決取值較多的屬性的問題，另外它還可以處理連續型屬性，其判別標準是θ，

      2，C4.5演算法利用增益/熵值，克服了樹生長的過程中，總是『貪婪』選擇變數分類多的進行分類

      3，處理來內需型變數，C4.5的分類樹的分支就是兩條

衡量指標：

（1）信息增益

基於ID3演算法的信息增益對於判定連續型變數的時候病不是最優選擇，C4.5演算法用了信息增益率這個概念。

分類信息類的定義如下：

這個值表示將訓練數據集D劃分成對應屬性A測試的V個輸出v個劃分產生的信息，信息增益率定義為：

選擇最大信息增益率的屬性作為分裂屬性

Gini指標，CART

表明樣本的「純凈度」。Gini系數避免了信息增益產生的問題，

過擬合問題，非常好的泛化能力，有很好的推廣能力

Gini系數的計算：

在分類問題中，假設有k個類，樣本點屬於第k類的概率為Pk，則概率分布的gini指數的定義為：

如果樣本集合D根據某個特徵A被分割為D1，D2兩個部分，那麼在特徵A的提哦啊見下，集合D的gini指數的定義為：

Gini指數代表特徵A不同分組下的數據集D的不確定性，gini指數越大，樣本集合的不確定性也就越大，這一點和熵的概念相類似

決策樹原理介紹：

第三步：對於每個屬性執行劃分：

（1）該屬性為離散型變數

記樣本中的變數分為m中

窮舉m種取值分為兩類的劃分

對上述所有劃分計算GINI系數

（2）該屬性為連續型變數

將數據集中從小到大劃分

按順序逐一將兩個相臨值的均值作為分割點

對上述所有劃分計算GINI系數

學歷的劃分使得順序的劃分有個保證，化為連續型變數處理。

決策樹的生成演算法分為兩個步驟：

預剪枝和後剪枝  CCP（cost and complexity）演算法：在樹變小和變大的的情況有個判斷標准。誤差率增益值：α值為誤差的變化

決策樹的終止條件：

      1，某一個節點的分支所覆蓋的樣本都是同一類的時候

      2，某一個分支覆蓋的樣本的個數如果小於一個閾值，那麼也可以產生葉子節點，從而終止Tree-Growth

確定葉子結點的類：

      1，第一種方式，葉子結點覆蓋的樣本都屬於同一類

      2， 葉子節點覆蓋的樣本未必是同一類，所佔的大多數，那麼該葉子節點的類別就是那個佔大多數的類

Ⅳ 判定樹的演算法

可以解決.
1.0 任意取2枚於天平量測重量,如: a+b; a+c; a+d; a+e;
a+f; a+g; a+h, 檢查稱得的重量數值就能知道.
2.0 還有一個簡單一點的. 取天平之砝碼一個(砝碼重量
已知,5g; 2g; 10g均可以),分別與a;b;c........
等8枚硬幣一起測試,從測試數據即知道哪個硬幣是假的.

你覺得計算方法對嗎? 個人覺得比較快捷.

Ⅵ 目前比較流行的決策樹演算法有哪些

ID3演算法，最簡單的決策樹
c4.5 是最經典的決策樹演算法，選擇信息差異率最大的作為分割屬性。
CART演算法，適合用於回歸

Ⅶ 常見決策樹分類演算法都有哪些

在機器學習中，有一個體系叫做決策樹，決策樹能夠解決很多問題。在決策樹中，也有很多需要我們去學習的演算法，要知道，在決策樹中，每一個演算法都是實用的演算法，所以了解決策樹中的演算法對我們是有很大的幫助的。在這篇文章中我們就給大家介紹一下關於決策樹分類的演算法，希望能夠幫助大家更好地去理解決策樹。
1.C4.5演算法
C4.5演算法就是基於ID3演算法的改進，這種演算法主要包括的內容就是使用信息增益率替換了信息增益下降度作為屬性選擇的標准；在決策樹構造的同時進行剪枝操作；避免了樹的過度擬合情況；可以對不完整屬性和連續型數據進行處理；使用k交叉驗證降低了計算復雜度；針對數據構成形式，提升了演算法的普適性等內容，這種演算法是一個十分使用的演算法。
2.CLS演算法
CLS演算法就是最原始的決策樹分類演算法，基本流程是，從一棵空數出發，不斷的從決策表選取屬性加入數的生長過程中，直到決策樹可以滿足分類要求為止。CLS演算法存在的主要問題是在新增屬性選取時有很大的隨機性。
3.ID3演算法
ID3演算法就是對CLS演算法的最大改進是摒棄了屬性選擇的隨機性，利用信息熵的下降速度作為屬性選擇的度量。ID3是一種基於信息熵的決策樹分類學習演算法，以信息增益和信息熵，作為對象分類的衡量標准。ID3演算法結構簡單、學習能力強、分類速度快適合大規模數據分類。但同時由於信息增益的不穩定性，容易傾向於眾數屬性導致過度擬合，演算法抗干擾能力差。
3.1.ID3演算法的優缺點
ID3演算法的優點就是方法簡單、計算量小、理論清晰、學習能力較強、比較適用於處理規模較大的學習問題。缺點就是傾向於選擇那些屬性取值比較多的屬性，在實際的應用中往往取值比較多的屬性對分類沒有太大價值、不能對連續屬性進行處理、對雜訊數據比較敏感、需計算每一個屬性的信息增益值、計算代價較高。
3.2.ID3演算法的核心思想
根據樣本子集屬性取值的信息增益值的大小來選擇決策屬性，並根據該屬性的不同取值生成決策樹的分支，再對子集進行遞歸調用該方法，當所有子集的數據都只包含於同一個類別時結束。最後，根據生成的決策樹模型，對新的、未知類別的數據對象進行分類。
在這篇文章中我們給大家介紹了決策樹分類演算法的具體內容，包括有很多種演算法。從中我們不難發現決策樹的演算法都是經過不不斷的改造趨於成熟的。所以說，機器學習的發展在某種程度上就是由於這些演算法的進步而來的。

Ⅷ 數據結構 演算法判斷兩棵二叉樹是否等價

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
typedef char datatype;

typedef struct node
{
datatype data;
struct node *lchild,*rchild;
}*bitree;

bitree createtree(bitree root)
{
char s;
s=getchar();
while(s!='@') /*'@'作為一種結束標識符 */
{
if(s==' ') /*『 』時將作為虛結點*/
{
root=NULL;
return root;
}
root=(bitree)malloc(sizeof(bitree));
root->data=s;
root->lchild=createtree(root->lchild); /* 遞歸 */
root->rchild=createtree(root->rchild); /* 遞歸 */
return root;
}
return root;
}

int comparetree(bitree a,bitree b)
{
if(a==NULL && b==NULL) return 1;
else if(a!=NULL && b!=NULL)
{
if(a->data == b->data) return(comparetree(a->lchild,b->lchild) && comparetree(a->rchild,b->rchild));
else return 0;
}
else return 0; //一種NULL，一種不NULL沒考慮，直接返回0就好。
}

int main()
{
bitree a,b;
int p;
printf("請輸入二叉樹1的各元素，以'@'作為結束標志符:\n");
a=createtree(a);
getchar(); //這里需要把換行給吃掉，不然影響後面的輸入。
printf("請輸入二叉樹1的各元素，以'@'作為結束標志符:\n");
b=createtree(b);
printf("輸入結束\n");
p=comparetree(a,b);
if(p==1)
printf("\n兩個二叉樹等價\n");
else
printf("\n兩個二叉樹不等價\n");

return 0;
}

沒輸出主要是需要在兩個輸入之間加上getchar（）,還有判斷是否等價少了一部分。

Ⅸ 決策樹、隨機森林

在了解樹模型之前，自然想到樹模型和線性模型，他們有什麼區別呢？

決策樹與邏輯回歸的分類區別也在於此。

樹形模型更加接近人的思維方式，可以 產生可視化的分類規則，產生的模型具有可解釋性 。樹模型擬合出來的函數其實是 分區間的階梯函數 。

決策樹（decision tree）是一種基本的分類與回歸方法，此處主要討論分類的決策樹。決策樹是一種十分常用的分類方法，屬於有監督學習（Supervised Learning）。所謂有監督學習，就是給出一堆樣本，每個樣本都有一組屬性和一個分類結果，也就是分類結果已知，那麼通過學習這些樣本得到一個決策樹，這個決策樹能夠對新的數據給出正確的分類。

決策樹是一種樹形結構，它主要有三種不同的節點：

決策樹演算法主要包括三個部分： 特徵選擇、樹的生成、樹的剪枝。

比較常用的決策樹演算法有ID3，C4.5和CART（Classification And Regression Tree），CART的分類效果一般優於其他決策樹。

樣本數量，特徵數量上面，一開始需要注意的：

當熵中的概率由數據估計(特別是最大似然估計)得到時，所對應的熵稱為 經驗熵 (empirical entropy)。

什麼叫由數據估計？比如有10個數據，一共有兩個類別，A類和B類。其中有7個數據屬於A類，則該A類的概率即為十分之七。其中有3個數據屬於B類，則該B類的概率即為十分之三。淺顯的解釋就是，這概率是我們根據數據數出來的。

訓練數據集D，則訓練數據集D的經驗熵為H(D)，|D|表示其樣本容量，及樣本個數。設有K個類Ck，k = 1,2,3,···,K，|Ck|為屬於類Ck的樣本個數，這經驗熵公式可以寫為：

信息增益表示得知特徵X的信息而使得類Y的信息不確定性減少的程度。

條件熵H(Y|X)表示在已知隨機變數X的條件下隨機變數Y的不確定性，隨機變數X給定的條件下隨機變數Y的條件熵(conditional entropy) H(Y|X)，定義X給定條件下Y的條件概率分布的熵對X的數學期望：

當熵和條件熵中的概率由數據估計（特別是極大似然估計）得到時，所對應的分別為經驗熵和經驗條件熵，此時如果有0概率，令0log0=0。

信息增益

一般地， 熵H(D)與條件熵H(D|A)之差成為互信息(mutual information) 。決策樹學習中的信息增益等價於訓練數據集中類與特徵的互信息。

信息增益比

Gini 指數

舉例計算Gini指數（不純度）

這個分類結果明顯並不是很好，因為它沒有將見面與不見面完全的分開，在演算法中，當然不能憑我們的「感覺」去評價分類結果的好壞。我們需要用一個數去表示。（具體數值代入上面的基尼指數計算公式）

信息增益 vs 信息增益比

Gini 指數 vs 熵

ID3演算法的核心是在決策樹各個結點上對應信息增益准則選擇特徵，遞歸地構建決策樹。

具體方法是：

1）從根結點(root node)開始，對結點計算所有可能的特徵的信息增益，選擇信息增益最大的特徵作為結點的特徵。

2）由該特徵的不同取值建立子節點，再對子結點遞歸地調用以上方法，構建決策樹；直到 所有特徵的信息增益均很小或沒有特徵可以選擇 為止；

3）最後得到一個決策樹。

ID3相當於用 極大似然法進行概率模型的選擇 。

與ID3演算法相似，但是做了改進，將信息增益比作為選擇特徵的標准。

CART 的全稱是分類與回歸樹。從這個名字中就應該知道，CART 既可以用於分類問題，也可以用於回歸問題。

回歸樹中，使用平方誤差最小化准則來選擇特徵並進行劃分。每一個葉子節點給出的預測值，是劃分到該葉子節點的所有樣本目標值的均值，這樣只是在給定劃分的情況下最小化了平方誤差。

要確定最優化分，還需要遍歷所有屬性，以及其所有的取值來分別嘗試劃分並計算在此種劃分情況下的最小平方誤差，選取最小的作為此次劃分的依據。由於回歸樹生成使用平方誤差最小化准則，所以又叫做最小二乘回歸樹。

ID3

熵表示的是數據中包含的信息量大小。熵越小，數據的純度越高，也就是說數據越趨於一致，這是我們希望的劃分之後每個子節點的樣子。

信息增益 = 劃分前熵 - 劃分後熵。信息增益越大，則意味著使用屬性 a 來進行劃分所獲得的 「純度提升」 越大 **。也就是說，用屬性 a 來劃分訓練集，得到的結果中純度比較高。

ID3 僅僅適用於二分類問題。ID3 僅僅能夠處理離散屬性。

C4.5 克服了 ID3 僅僅能夠處理離散屬性的問題，以及信息增益偏向選擇取值較多特徵的問題，使用信息增益比來選擇特徵。 信息增益比 = 信息增益 / 劃分前熵 選擇信息增益比最大的作為最優特徵。

C4.5 處理連續特徵是先將特徵取值排序，以連續兩個值中間值作為劃分標准。嘗試每一種劃分，並計算修正後的信息增益，選擇信息增益最大的分裂點作為該屬性的分裂點。

CART 與 ID3，C4.5 不同之處在於 CART 生成的樹必須是二叉樹 。也就是說，無論是回歸還是分類問題，無論特徵是離散的還是連續的，無論屬性取值有多個還是兩個，內部節點只能根據屬性值進行二分。

決策樹生成演算法遞歸的產生決策樹，直到不能繼續下去為止，這樣產生的樹往往對訓練數據的分類很准確，但對未知測試數據的分類缺沒有那麼精確，即會出現過擬合現象。過擬合產生的原因在於在學習時過多的考慮如何提高對訓練數據的正確分類，從而構建出過於復雜的決策樹，解決方法是考慮決策樹的復雜度，對已經生成的樹進行簡化。

剪枝（pruning）：從已經生成的樹上裁掉一些子樹或葉節點，並將其根節點或父節點作為新的葉子節點，從而簡化分類樹模型。

實現方式：極小化決策樹整體的損失函數或代價函數來實現

決策樹學習的損失函數定義為：

https://www.cnblogs.com/ooon/p/5647309.html

鑒於決策樹容易過擬合的缺點，隨機森林採用多個決策樹的投票機制來改善決策樹，我們假設隨機森林使用了m棵決策樹，那麼就需要產生m個一定數量的樣本集來訓練每一棵樹，如果用全樣本去訓練m棵決策樹顯然是不可取的，全樣本訓練忽視了局部樣本的規律，對於模型的泛化能力是有害的。

產生n個樣本的方法採用Bootstraping法，這是一種有放回的抽樣方法，產生n個樣本。

而最終結果採用Bagging的策略來獲得，即多數投票機制。

隨機森林的生成方法：

1.從樣本集中通過重采樣的方式產生n個樣本

2.假設樣本特徵數目為a，對n個樣本選擇a中的k個特徵，用建立決策樹的方式獲得最佳分割點

3.重復m次，產生m棵決策樹

4.多數投票機制來進行預測

（需要注意的一點是，這里m是指循環的次數，n是指樣本的數目，n個樣本構成訓練的樣本集，而m次循環中又會產生m個這樣的樣本集）

隨機森林是一個比較優秀的模型，在我的項目的使用效果上來看，它對於多維特徵的數據集分類有很高的效率，還可以做特徵重要性的選擇。運行效率和准確率較高，實現起來也比較簡單。 但是在數據噪音比較大的情況下會過擬合，過擬合的缺點對於隨機森林來說還是較為致命的。

機器學習實戰（三）——決策樹 https://blog.csdn.net/jiaoyangwm/article/details/79525237