從前，夕小瑤種了一棵樹

從前

從前，小夕種了一棵樹，種在了小夕的小屋後面~

nn

為什麼要種這棵樹呢？因為呀，它可以幫小夕總結歷史經驗，然後幫小夕對當前的局勢做出決策~這樣小夕就可以安心給大家寫文章啦~

nn

這棵樹是這樣的。

nn

一開始，小夕買了一顆小樹苗，把它栽到地上。

nn

然後呢，小夕不給它澆水，也不給他澆肥料，而是讓他吃歷史經驗。比如呢，今天，小夕讓它幫小夕識別出圖片中的生物是喵還是驢。所以呢，這裡的歷史經驗就是一大堆喵和驢的圖片，並且小夕給它標註好了每張圖片是喵還是驢。

可是由於樹沒有眼睛呀，不能直接觀察圖片。所以呢，小夕幫它把圖片轉化成了特徵，也就是用幾個特徵來描述每張圖片。

nn

小夕選了如下幾個特徵來描述每張圖片：

nn

1、頭是否是長條形

2、身上有沒有毛

3、有沒有發現鬍鬚

4、丑不醜

5、萌不萌

nn

所以，比如小夕就會對下面這張圖片：

nn

轉化為[False True False False True]的特徵向量（即，不是長條頭、有毛、沒發現鬍鬚、不醜、萌）

然後小夕一口氣給上千張圖片提取完了特徵，當然，這些圖片都是標註好類別的。

nn

小夕就把它們丟給小夕心愛的小樹苗啦~

快快長大

nn

誒？那小樹苗要怎麼生長呢？

nn

小夕問小樹苗：「小樹小樹，你接下來要怎麼長呢？」

nn

小樹苗喝了口水，說：「我每一步的生長都是非常慎重的，我從不會多長個枝丫或者少長個枝丫。每個樣本這不是有五個特徵嘛，我呢，就會從中挑選出最有價值的一個特徵，來作為我第一次生長的分支。」

nn

小夕接著問：「那你要怎麼挑選特徵呢？」

nn

小樹苗說：「你看啊，比如你挑出來的第二個特徵，「身上有沒有毛」，這就是很糟糕的特徵。為什麼呢？我們就來看「有沒有毛」這個特徵。我數了一下，在所有有毛的動物中，50%的動物是喵，50%的動物是驢。而在所有沒有毛的動物中，也是50%的動物是喵，50%的動物是驢。所以「有沒有毛」這個特徵的任何一個取值下，所有類別的樣本數一樣，是完全等概率的，這樣的特徵完全無法用來做分類啊。因為不管這個特徵的值是什麼，它所映射的各個類別都是等概率的。所以這個類別是最糟糕的。」

nn

小樹苗喝了口水，接著說：「但是你用的第三個特徵，「有沒有鬍鬚」，就非常棒。我統計了一下，有鬍鬚的動物中，喵佔了92%，驢佔了8%。而沒有鬍鬚的動物中，喵佔了20%，驢佔了80%。這樣，如果給我一張未知類別的樣本，只需要看「有沒有鬍鬚」這個特徵的話，基本就可以判斷出這個樣本的類別是什麼了！比如說這個樣本的這個特徵的值恰好是「沒有鬍鬚」，那麼我就有80%的把握說這是一頭驢！當然，如果恰好這個樣本的特徵的值是「有鬍鬚」，我就有92%的把握說這個樣本時一隻喵！這麼棒的特徵，當然是首選的啦！所以，我下面要長的枝丫就是叫做「有沒有鬍鬚枝丫」！」

nn

小夕：

nn

「我可能買了一棵假樹。

nn

我。。。懂你的意思了。你說的選擇最優特徵的方法實際就是計算條件熵的過程。對於你說的「有沒有毛」這個很糟糕的特徵，由於這個特徵的每個取值下，各個類別都是完全等概率分布的，所以是最無序的，最隨機的特徵，我們稱為「條件熵最大的特徵」。熵最大就是1，所以計算出的「有沒有毛」這個特徵的條件熵肯定是1。

nn

而你說的「有沒有鬍鬚」這個特徵，它的每個取值下，類別分布很隨機，也就是說很有序（想像一下，最有序的狀態就是每個取值下，所有樣本都是同一個類別，多麼有序啊。而類別等概率分布的時候，就是每個特徵下魚龍混雜的時候，啥類別都有，亂糟糟的），這種很有序的特徵，計算出的條件熵肯定很小。最有序的情況下，條件熵就是0啦。」

nn

小樹：「好了。但是，我的分類目標是達到100%的準確率。所以，我要進一步挑選特徵了！

nn

基於有鬍鬚的那個分支，我會將這個分支里的樣本重新計算各個特徵的條件熵（當然鬍鬚這個特徵除外），像之前一樣選擇條件熵最大的特徵作為下一個枝丫！

nn

一直重複這個過程，直到哪一個枝丫下的全部樣本都是同一個類別了，這個枝丫就不再繼續分裂了。」

nn

最終，小樹長成了大樹。

nn

這時，小夕忙著給大家寫文章呢，但是小夕的一個好閨蜜小婭拿著一張圖片過來了，她想讓小夕幫她看看這是驢還是喵。

但是小夕很忙呀，沒空理她，就讓她拿著圖片問後院的決策樹啦~

nn

然後小婭去問決策樹這是啥，決策樹說：「它有鬍鬚嗎？」

nn

小婭說：「有！」

nn

樹：「它萌嗎？」

nn

小婭：「一點也不萌！」

nn

樹：「它是長臉嗎？」

nn

小婭：「是長臉！」

nn

樹：「那這就是只驢！」

nn

留下一臉懵逼的小婭在樹下凌亂(￣?￣)

nn

這棵神奇的樹叫什麼呢？

nn

這棵樹的專業說法叫「ID3決策樹」，為什麼是ID3呢？因為它是通過計算條件熵來選擇最優特徵的。其他經典決策樹如C4.5決策樹、CART決策樹等與ID3的區別僅在於最優特徵選擇的演算法。

nn

總結

然後對本文總結一下，本文經過了如下步驟，這也是一個簡單的機器學習/數據挖掘任務的經典流程。

nn

1、對已標註類別的數據集進行數據預處理與特徵提取

2、訓練決策樹（分類器/機器學習模型）

3、對未知類別的數據集進行數據預處理與特徵提取

4、利用決策樹對未知類別樣本的類別做出決策

nn

想要詳細了解ID3決策樹選擇最優特徵的過程（即計算條件熵）的同學，可以Google或者百度一下「條件熵」或者查閱《數據挖掘導論》等機器學習相關的書籍；想要詳細了解如何代碼實現ID3決策樹的同學，可以搜索各種CSDN博客或者查閱《機器學習實戰》等側重代碼實現的書籍。對於如何提高決策樹的泛化能力（防止過擬合）等優化技巧，或者其他類型的決策樹，可以看《數據挖掘導論》等經典書籍~

喜歡本文？那小夕推薦一下自己的微信訂閱號【夕小瑤的賣萌屋】，據說每個想學機器學習的人進來後都停不下來了(￣?￣)

推薦閱讀：