看到標題的同學可能會有點疑問，在數(shù)據(jù)挖掘十大經(jīng)典算法里檬寂，ID3的名字并不在列终抽。
其實，ID3與位列十大經(jīng)典算法的C4.5焰薄、CART本是同源拿诸，他們都屬于決策樹算法家族，都算是決策樹構(gòu)建算法塞茅。后兩者也都是在ID3的基礎上發(fā)展優(yōu)化得來亩码。因此，本文以ID3為入口野瘦，為大家講解決策樹類算法的基本思想和ID3的具體邏輯描沟，有了這部分鋪墊，之后再來看C4.5和CART便是會是水到渠成鞭光。
什么是決策樹
既然ID3是一種決策樹分類算法吏廉，那么首先當然先來講講什么是決策樹。應該說惰许，決策樹并不是一種具體的算法席覆，而是一種分類思想。這種思想也非常直觀汹买，就是通過不斷回答問題的方式來劃分類別佩伤，而最終劃分的結(jié)果顯然是可以表達為一個樹狀結(jié)構(gòu)圖，這棵樹便稱之為決策樹晦毙。
其實這種通過提問層層劃分的思想可以說是我們?nèi)粘Ｉ钪凶钪庇^也最常用的分類思路之一生巡，這里援引一個網(wǎng)上看到的極為生動的例子來表現(xiàn)決策樹的分類過程：
以下這個例子來自博客http://www.cnblogs.com/leoo2sk/archive/2010/09/19/decision-tree.html
現(xiàn)想象一個女孩的母親要給這個女孩介紹男朋友，于是有了下面的對話：
女兒：多大年紀了见妒？
母親：26孤荣。
女兒：長的帥不帥？
母親：挺帥的。
女兒：收入高不盐股？
母親：不算很高钱豁，中等情況。
女兒：是公務員不遂庄？
母親：是寥院，在稅務局上班呢。
女兒：那好涛目，我去見見秸谢。這個女孩的決策過程就是典型的分類樹決策。
相當于通過年齡霹肝、長相估蹄、收入和是否公務員對將男人分為兩個類別：見和不見。
假設這個女孩對男人的要求是：
30歲以下沫换、長相中等以上并且是高收入者或中等以上收入的公務員臭蚁，那么這個可以用下圖表示女孩的決策邏輯
這思路是不是直白到不行，當然原作者也說了：
此決策樹純屬為了寫文章而YY的產(chǎn)物讯赏，沒有任何根據(jù)垮兑，也不代表任何女孩的擇偶傾向，請各位女同胞莫質(zhì)問我
什么樣的決策樹才算好漱挎？
相信看到這里系枪，沒有人還會不理解決策樹這種分類思想。但是要作為一種能夠解決實際問題的算法磕谅，光有思想顯然還遠遠不夠私爷，還應該有明確的方法來構(gòu)建這棵樹。通過前面的例子膊夹，大家應該也有直觀的感受衬浑，在一個決策樹的決策過程中，最關鍵的就是這些用來分支所提出的問題放刨，該問什么樣的問題工秩、怎樣根據(jù)答案劃分分支、先問什么后問什么进统，這些顯然直接決定了一顆決策樹的效率優(yōu)劣助币，而這些也就是本文所講的ID3以及后面會講到CART、C4.5要解決的問題麻昼。
事實上，在構(gòu)建決策樹的過程中馋辈，所追求的標準應該是每一步分裂的純度抚芦。所謂純，也就是要盡可能讓每一步分裂出來的子集中的元素屬于同一類別。也就是問題要問的夠“準”叉抡，比如對于分兩類的情況尔崔，最好找到一個問題，可以直接根據(jù)答案區(qū)分出預期的兩類褥民；而如果一個問題問完季春，分出的幾支中還都同時包含預期的兩類中的元素，還要進一步更多的問題才能加以區(qū)分消返，那么就表示這一步的分裂不夠純载弄。
一點點信息論
那么，既然要追求“純”撵颊，那么如何找到每一步分裂時能使結(jié)果最純的分裂方式呢宇攻？這顯然先要對純給一個能夠定量計算的定義。
在這里倡勇，不同的決策樹算法逞刷，所采取的標準有所不同，而在ID3算法里妻熊，采用的是信息論當中的信息熵的增益這一概念來衡量分裂的效果夸浅。
“熵”這一概念本來是來自熱力學，所描述的是能量在空間中分布的混亂程度扔役，能量分布得越混亂帆喇，熵就越大。一個體系的能量完全均勻分布時厅目，這個系統(tǒng)的熵就達到最大值番枚。
而我們信息學的祖師爺克勞德·香農(nóng)把這個概念引入了信息論當中，用來描述信息的混亂程度损敷。并且給出了信息熵的計算公式
其中葫笼，pi表示的是一個信息要素（可以對應我們數(shù)據(jù)挖掘中一種特征值的一種取值）的概率。
而關于這個公式是如何得出的拗馒，牽涉信息論的知識點路星，并不是本文所關注的重點，這里不做展開诱桂。
想要簡要了解的同學們可以參閱以下鏈接https://www.zhihu.com/question/22178202洋丐，閱讀排名第一的回答
簡言之，我們可以這樣去理解信息熵增益這個概念：
既然信息熵描述的是信息的混亂程度挥等，而我們分類的過程其實是讓信息越來越清晰痰娱，也就是信息熵越來越小的過程。因此啰劲，信息熵增益最大也就是要找到一個劃分能比其他劃分帶來的信息熵的減小更多担敌。
ID3算法過程
接下來郭宝，我們通過一個例子來直觀認識一下ID3的算法過程：
假設我們已經(jīng)收集了隔壁老王在各種外部條件下是否會去打高爾夫球這件事的數(shù)據(jù)，如下表：
| 氣溫高低 | 天氣概況 | 是否工作日 | 是否去打球 |
|---|---|---|---|
| 低溫 | 晴 | 否 | 打球 |
| 低溫 | 下雨 | 是 | 沒打 |
| 舒適 | 有風 | 是 | 沒打 |
| 舒適 | 有風 | 是 | 沒打 |
| 高溫 | 有風 | 是 | 沒打 |
| 舒適 | 下雨 | 否 | 沒打 |
| 舒適 | 晴 | 否 | 打球 |
| 高溫 | 有風 | 否 | 沒打 |
| 舒適 | 晴 | 否 | 沒打 |
| 低溫 | 晴 | 是 | 打球 |
現(xiàn)在我們需要根據(jù)這些訓練集來構(gòu)建一棵決策樹掷漱，以便在將來某一天針對當時的氣溫粘室、天氣和是否工作日這三個條件來預測老王是否會去打球。
顯然卜范，為了構(gòu)建決策樹衔统，我們可以用這三類特征值分別作為每一次劃分的問題，但要決定的就是我們應該先選用哪一個特征值做第一次劃分海雪？
這時锦爵，根據(jù)前面學習到的信息熵增益的理論，假設原本的信息熵為
而我們要以特征值R作為第一次劃分喳魏，則劃分之后的信息熵為
我們的目標是讓信息熵增益棉浸，即兩個值的差值達到最大
然而，不論我們選擇了哪個特征值R刺彩，減號前面的Info(D)都是一樣的迷郑，因此我們根本不用去計算這個值，只需要讓減號后面的值最小即可创倔。
接下來我們就依次來計算各個特征值劃分后的信息熵嗡害，以氣溫高低為例，劃分之后的信息熵為：
低溫的概率 * 低溫情況下的信息熵 + 舒適的概率 * 舒適情況下的信息熵 + 高溫概率 * 高溫情況下的信息熵
即
同理畦攘，我們也可以算出按照天氣概況和是否工作日劃分出來的信息熵分別為0.326和0.846霸妹，因此我們應該選擇新信息熵最小的，也就是天氣概況來作為第一次劃分知押，使得劃分最“純”叹螟。
這樣，在第一步之后台盯，我們的決策樹已經(jīng)變成了如下所示：
那么接下來我們需要決策的是第二步劃分選用氣溫高低還是是否工作日罢绽。顯然，重復第一步的動作静盅，就可以計算出這一步改選誰了良价。以此類推，直到得到整顆完整的決策樹蒿叠。
簡單總結(jié)一下ID3的算法過程就是：
- 依次將數(shù)據(jù)中的每一個特征作為分支標準明垢，并計算其相對于原始數(shù)據(jù)的信息增益，選擇最大信息增益的分支標準來劃分數(shù)據(jù)
- 按照選出的特征屬性進行劃分市咽，得到每一個子劃分
- 對每一個子劃分重復上述過程痊银，直到得到完整決策樹
如何處理連續(xù)數(shù)據(jù)
其實上面給出的例子是一種簡化版的決策過程，因為所有特征屬性都是離散化的施绎，其實在實際當中溯革，許多屬性都是連續(xù)值泌射，比如例子當中的氣溫。那么對于特征屬性為連續(xù)值鬓照，應該如何使用ID3算法呢？
先將D中元素按照特征屬性排序孤紧，則每兩個相鄰元素的中間點可以看做潛在分裂點豺裆，從第一個潛在分裂點開始，分裂D并計算兩個集合的期望信息号显，具有最小期望信息的點稱為這個屬性的最佳分裂點臭猜，其信息期望作為此屬性的信息期望。
ID3的特點與優(yōu)劣
優(yōu)點：
- 可以處理同時具有離散和連續(xù)數(shù)據(jù)的輸入
- 分類過程與領域知識無關押蚤，幾乎所有模式和場景都可以跑出結(jié)果
缺點：
- 一次只用一類特征值進行劃分
- 在樣本量較小時蔑歌，可能會導致過度分類
- 對連續(xù)數(shù)據(jù)的處理不夠好
- 對樣本數(shù)據(jù)缺失的情況無法處理
- 不適合處理包含多重分支的特征值
好了，這一part對決策樹和ID3算法的介紹就到這里揽碘。在下一篇文章當中次屠，會繼續(xù)對C4.5，CART以及決策樹的剪枝等概念做進一步的講解雳刺。
