決策樹Decision Trees - Introduction(ID3)

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

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

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

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

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

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

通過觀察我們得出以下結(jié)論：

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

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

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

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

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

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

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

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

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

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

此時(shí)的決策樹長這樣：

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

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

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

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

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

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

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

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

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

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

舉個(gè)例子

知道了信息熵和熵之后，我們來構(gòu)建決策樹

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

此時(shí)我們需要決定另一個(gè)屬性劃分Shadow=？的子集

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

實(shí)現(xiàn)ID3決策樹學(xué)習(xí)算法

這里有些。

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

三種diversity的指標(biāo)：

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

2. 2P(c1)P(c2)

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

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

選擇分割的時(shí)候，對(duì)每個(gè)字段都考慮；對(duì)每個(gè)字段中的值先排序，然后再一一計(jì)算。最后選出最佳的分割。

樹的生成：

錯(cuò)誤率的衡量：最初生成的樹中也是有錯(cuò)誤率的！因?yàn)橛行┤~子節(jié)點(diǎn)并不是“Pure”的。

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

修剪的要點(diǎn)是：應(yīng)該回溯多少、如何從眾多的子樹總尋找最佳的。

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

2) 對(duì)子樹的評(píng)估：通過test set找到最佳子樹

3) 對(duì)最佳子樹進(jìn)行評(píng)估：使用evaluation set。

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

5.10 決策樹與ID3算法

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

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

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

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

構(gòu)造決策樹的關(guān)鍵性內(nèi)容是進(jìn)行屬性選擇度量，屬性選擇度量（找一種計(jì)算方式來衡量怎么劃分更劃算）是一種選擇分裂準(zhǔn)則，它決定了拓?fù)浣Y(jié)構(gòu)及分裂點(diǎn)split_point的選擇。

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

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

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

而在信息學(xué)里面，熵是對(duì)不確定性的度量。

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

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

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

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

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

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

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

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

ID3算法就是在每次需要分裂時(shí)，計(jì)算每個(gè)屬性的增益率，然后選擇增益率最大的屬性進(jìn)行分裂

步驟：1. 對(duì)當(dāng)前樣本集合，計(jì)算所有屬性的信息增益；

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

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

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

的另一個(gè)標(biāo)準(zhǔn)。

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

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

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

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

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

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

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

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

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

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

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

sklearn.tree.DecisionTreeClassifier

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

ID3算法就是在每次需要分裂時(shí)，計(jì)算每個(gè)屬性的增益率，然后選擇增益率最大的屬性進(jìn)行分裂

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

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

**所以，按先按好友密度劃分的信息增益比按真實(shí)頭像劃分的大。應(yīng)先按好友密度劃分。

決策樹——ID3算法應(yīng)用實(shí)例

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

一、實(shí)驗(yàn)?zāi)康?/p>

1、理解分類

2、掌握分類挖掘算法ID3

3、為改進(jìn)ID3打下基礎(chǔ)

二、實(shí)驗(yàn)內(nèi)容

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

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

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

三、實(shí)驗(yàn)原理

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

網(wǎng)站欄目：包含id3決策樹代碼java的詞條
瀏覽路徑：http://chinadenli.net/article0/dodogoo.html

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

廣告

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