決策樹Decision Trees - Introduction(ID3)

你在一生中遇到各種不同的人，在有了一些經驗后，你知道自己喜歡哪種類型的人。于是在遇見新人類時，很多時候你可以判斷自己是否喜歡它們，通過經驗知道的，然后不通過大腦感覺。我們通過建立相似的機制。

網站建設哪家好，找創(chuàng)新互聯(lián)！專注于網頁設計、網站建設、微信開發(fā)、小程序設計、集團企業(yè)網站建設等服務項目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了武夷山免費建站歡迎大家使用！

我們來假設你遇到了一些人，你不希望vmpires成為你的未來的朋友，所以你做出以下的列表，判斷他們是否是吸血鬼。

觀察這個數(shù)據(jù)集后，我們畫出一個樹來判斷是否是吸血鬼

因為畫出這棵樹可以幫助我們做出選擇，所以我們稱之為“Decision Tree”，這棵樹必須滿足所給數(shù)據(jù)集中的所有數(shù)據(jù)，并且我們也希望它可以滿足以后的所有輸入。

但如何構造出這棵樹呢？以上的樹是通過所及觀察畫出的。

通過觀察我們得出以下結論：

? ? 所有with pale complexion的人都不是吸血鬼

? ? 所有有ruddy complexion和吃garlic的人都不是吸血鬼，如果他們不吃大蒜則是吸血鬼

? ? 所有有average complexion的人，并且他們沒有影子或不知道是否有影子的是吸血鬼，否則如果有影子則不是吸血鬼

這是我們通過簡單數(shù)據(jù)判斷出的決策樹，這種隨機的猜測在巨大的數(shù)據(jù)集上是行不通的，我們需要更加系統(tǒng)的步驟來解決這個問題。

那我們來用貪心算法嘗試解決一下！

首先通過看數(shù)據(jù)集，決定選擇哪一個屬性作為樹的根節(jié)點.... 這是個 二分類問題 ，所以在決策樹的最后我們可以有兩種可能的解決方式，所以每個輸入的例子可以分類為真或假兩類。這里用P表示positive，是吸血鬼，N表示negative，不是吸血鬼。

我們想要那些把數(shù)據(jù)分為同類的屬性，也就是說，P或N各自存在于一個子集，也就可以區(qū)分是否是吸血鬼，這就將是葉子節(jié)點。

檢查每個特征，觀察哪一個在相同集合中有最多的元素，此時找到了shadow？這個屬性

shadow這個屬性，可以決定一個人是否是吸血鬼，但是如果不清楚是否有shadow則不能判斷這個人是否是吸血鬼，我們需要另一個特征在shadow=？時將數(shù)據(jù)集分開。

當shadow=？時，我們分析得知garlic這個屬性將其劃分為同質子集，區(qū)分了最多的元素。

此時的決策樹長這樣：

這棵樹比我們之前隨機選特征得出的樹更加簡單，所以我們發(fā)現(xiàn)貪心算法幫助我們獲得更好的結果。但這是正確的方式去做嗎？

不是，因為數(shù)據(jù)集很龐大，我們不需要最終將屬性區(qū)分到同質集中，我們可能會發(fā)現(xiàn)所有的屬性元素在同質集中是零個。

現(xiàn)在我們用ID3算法生成決策樹，這運用了 Information gain 這個概念，是通過 entropy熵 定義的，熵是在信息理論學中的根本quantity

想象這有通過某個特征區(qū)分的兩個分類

我們觀察到，左邊的P和N有相同的數(shù)量，所以這不能給我們提供任何判斷的提示，但是右邊的P大于N，所以它可能會指引我們到P，所以這兩個中我們會考慮右邊的分類。

所以，我們并不直接給它們打零分，我們說，如果一個分類中P和N有相同的數(shù)量的有更高的熵值，最混亂，另一個分類中只有P或只有N，它的熵最低，值為0，表示最不混亂。以下我們可以看到這個圖，P/（P+N）和熵值的圖

所以，當P=N時，也就是P/(P+N)=0.5時，熵值最大為1，如果P=K(某個int值)N=0，熵值為0

那計算出這個熵值，得出這個圖有沒有數(shù)學方程呢？幸運的是，這個曲線可以通過以下方差獲得：

我們可以把x的取值 代入這個熵的形式

公式中的P 和 N就是根據(jù)該特征劃分的Ps和Ns的數(shù)量，同時我們也想從屬性中獲取信息熵Information gain，也定義為IG。

舉個例子

知道了信息熵和熵之后，我們來構建決策樹

我們計算出最大的IG信息熵是shadow屬性，將其作為根節(jié)點

此時我們需要決定另一個屬性劃分Shadow=？的子集

接著算出garlic的 IG值最大，畫出的樹如下：

實現(xiàn)ID3決策樹學習算法

這里有些。

Diversity(整體)-diversity(左節(jié)點)-diversity(右節(jié)點)，值越大，分割就越好。

三種diversity的指標：

1. min(P(c1),P(c2))

2. 2P(c1)P(c2)

3. [P(c1)logP(c1)]+[P(c2)logP(c2)]

這幾個參數(shù)有相同的性質：當其中的類是均勻分布的時候，值最大；當有一個類的個數(shù)為0的時候，值為0。

選擇分割的時候，對每個字段都考慮；對每個字段中的值先排序，然后再一一計算。最后選出最佳的分割。

樹的生成：

錯誤率的衡量：最初生成的樹中也是有錯誤率的！因為有些葉子節(jié)點并不是“Pure”的。

樹的修剪：是不是當所以的葉子都很純是，這棵樹就能工作的很好呢?

修剪的要點是：應該回溯多少、如何從眾多的子樹總尋找最佳的。

1) 鑒別生成候選子樹 ：使用一個調整的錯誤率。AE(T)=E(T)+aleaf_count(T)。一步步的生成一些候選子樹。

2) 對子樹的評估：通過test set找到最佳子樹

3) 對最佳子樹進行評估：使用evaluation set。

4) 考慮代價(cost)的問題

5.10 決策樹與ID3算法

決策樹（decision tree）是一個樹結構（可以是二叉樹或非二叉樹）。決策過程是從根節(jié)點開始，測試待分類項中相應的特征屬性，并按照其值選擇輸出分支，直到到達葉子節(jié)點，將葉子節(jié)點存放的類別作為決策結果。

決策樹的關鍵步驟是分裂屬性。就是在某節(jié)點處按某一特征屬性的不同劃分構造不同的分支，目標是讓各個分裂子集盡可能地“純”。即讓一個分裂子集中待分類項屬于同一類別。

簡而言之，決策樹的劃分原則就是：將無序的數(shù)據(jù)變得更加有序

分裂屬性分為三種不同的情況 ：

構造決策樹的關鍵性內容是進行屬性選擇度量，屬性選擇度量（找一種計算方式來衡量怎么劃分更劃算）是一種選擇分裂準則，它決定了拓撲結構及分裂點split_point的選擇。

屬性選擇度量算法有很多，一般使用自頂向下遞歸分治法，并采用不回溯的貪心策略。這里介紹常用的ID3算法。

貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，所做出的是在某種意義上的局部最優(yōu)解。

此概念最早起源于物理學，是用來度量一個熱力學系統(tǒng)的無序程度。

而在信息學里面，熵是對不確定性的度量。

在1948年，香農引入了信息熵，將其定義為離散隨機事件出現(xiàn)的概率，一個系統(tǒng)越是有序，信息熵就越低，反之一個系統(tǒng)越是混亂，它的信息熵就越高。所以信息熵可以被認為是系統(tǒng)有序化程度的一個度量。

熵定義為信息的期望值，在明晰這個概念之前，我們必須知道信息的定義。如果待分類的事務可能劃分在多個分類之中，則符號x的信息定義為：

在劃分數(shù)據(jù)集之前之后信息發(fā)生的變化稱為信息增益。

知道如何計算信息增益，就可計算每個特征值劃分數(shù)據(jù)集獲得的信息增益，獲得信息增益最高的特征就是最好的選擇。

條件熵 表示在已知隨機變量的條件下隨機變量的不確定性，隨機變量X給定的條件下隨機變量Y的條

件熵(conditional entropy) ，定義X給定條件下Y的條件概率分布的熵對X的數(shù)學期望：

根據(jù)上面公式，我們假設將訓練集D按屬性A進行劃分，則A對D劃分的期望信息為

則信息增益為如下兩者的差值

ID3算法就是在每次需要分裂時，計算每個屬性的增益率，然后選擇增益率最大的屬性進行分裂

步驟：1. 對當前樣本集合，計算所有屬性的信息增益；

是最原始的決策樹分類算法，基本流程是，從一棵空數(shù)出發(fā)，不斷的從決策表選取屬性加入數(shù)的生長過程中，直到決策樹可以滿足分類要求為止。CLS算法存在的主要問題是在新增屬性選取時有很大的隨機性。ID3算法是對CLS算法的改進，主要是摒棄了屬性選擇的隨機性。

基于ID3算法的改進，主要包括：使用信息增益比替換了信息增益下降度作為屬性選擇的標準；在決策樹構造的同時進行剪枝操作；避免了樹的過度擬合情況；可以對不完整屬性和連續(xù)型數(shù)據(jù)進行處理；使用k交叉驗證降低了計算復雜度；針對數(shù)據(jù)構成形式，提升了算法的普適性。

信息增益值的大小相對于訓練數(shù)據(jù)集而言的，并沒有絕對意義，在分類問題困難時，也就是說在訓練數(shù)據(jù)集經驗熵大的時候，信息增益值會偏大，反之信息增益值會偏小，使用信息增益比可以對這個問題進行校正，這是特征選擇

的另一個標準。

特征對訓練數(shù)據(jù)集的信息增益比定義為其信息增益gR( D,A) 與訓練數(shù)據(jù)集的經驗熵g(D,A)之比 ：

gR(D,A) = g(D,A) / H(D)

sklearn的決策樹模型就是一個CART樹。是一種二分遞歸分割技術，把當前樣本劃分為兩個子樣本，使得生成的每個非葉子節(jié)點都有兩個分支，因此，CART算法生成的決策樹是結構簡潔的二叉樹。

分類回歸樹算法(Classification and Regression Trees,簡稱CART算法)是一種基于二分遞歸分割技術的算法。該算法是將當前的樣本集，分為兩個樣本子集，這樣做就使得每一個非葉子節(jié)點最多只有兩個分支。因此，使用CART

算法所建立的決策樹是一棵二叉樹，樹的結構簡單，與其它決策樹算法相比，由該算法生成的決策樹模型分類規(guī)則較少。

CART分類算法的基本思想是：對訓練樣本集進行遞歸劃分自變量空間，并依次建立決策樹模型，然后采用驗證數(shù)據(jù)的方法進行樹枝修剪，從而得到一顆符合要求的決策樹分類模型。

CART分類算法和C4.5算法一樣既可以處理離散型數(shù)據(jù)，也可以處理連續(xù)型數(shù)據(jù)。CART分類算法是根據(jù)基尼(gini)系

數(shù)來選擇測試屬性，gini系數(shù)的值越小，劃分效果越好。設樣本集合為T，則T的gini系數(shù)值可由下式計算：

CART算法優(yōu)點：除了具有一般決策樹的高準確性、高效性、模式簡單等特點外，還具有一些自身的特點。

如，CART算法對目標變量和預測變量在概率分布上沒有要求，這樣就避免了因目標變量與預測變量概率分布的不同造成的結果；CART算法能夠處理空缺值，這樣就避免了因空缺值造成的偏差；CART算法能夠處理孤立的葉子結點，這樣可以避免因為數(shù)據(jù)集中與其它數(shù)據(jù)集具有不同的屬性的數(shù)據(jù)對進一步分支產生影響；CART算法使用的是二元分支，能夠充分地運用數(shù)據(jù)集中的全部數(shù)據(jù)，進而發(fā)現(xiàn)全部樹的結構；比其它模型更容易理解，從模型中得到的規(guī)則能獲得非常直觀的解釋。

CART算法缺點：CART算法是一種大容量樣本集挖掘算法，當樣本集比較小時不夠穩(wěn)定；要求被選擇的屬性只能產生兩個子結點，當類別過多時，錯誤可能增加得比較快。

sklearn.tree.DecisionTreeClassifier

1.安裝graphviz.msi ， 一路next即可

ID3算法就是在每次需要分裂時，計算每個屬性的增益率，然后選擇增益率最大的屬性進行分裂

按照好友密度劃分的信息增益：

按照是否使用真實頭像H劃分的信息增益

**所以，按先按好友密度劃分的信息增益比按真實頭像劃分的大。應先按好友密度劃分。

決策樹——ID3算法應用實例

在ID3決策樹歸納方法中，通常是使用信息增益方法來幫助確定生成每個節(jié)點時所應采用的合適屬性。這樣就可以選擇具有最高信息增益（熵減少的程度最大）的屬性最為當前節(jié)點的測試屬性，以便對之后劃分的訓練樣本子集進行分類所需要的信息最小，也就是說，利用該屬性進行當前（節(jié)點所含）樣本集合劃分，將會使得所產生的樣本子集中的“不同類別的混合程度”降為最低。因此，采用這樣一種信息論方法將有效減少對象分來所需要的次數(shù)，從而確保所產生的決策樹最為簡單。

一、實驗目的

1、理解分類

2、掌握分類挖掘算法ID3

3、為改進ID3打下基礎

二、實驗內容

1、選定一個數(shù)據(jù)集（可以參考教學中使用的數(shù)據(jù)集）

2、選擇合適的實現(xiàn)環(huán)境和工具實現(xiàn)算法 ID3

3、給出分類規(guī)則

三、實驗原理

決策樹是一種最常見的分類算法，它包含有很多不同的變種，ID3算法是其中最簡單的一種。ID3算法中最主要的部分就是信息熵和信息增益的計算。

網站欄目：包含id3決策樹代碼java的詞條
瀏覽路徑：http://jinyejixie.com/article0/dodogoo.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供微信小程序、外貿網站建設、網站維護、電子商務、App開發(fā)、自適應網站

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)