在筆者的上一篇文章中[1]，使用了 k-NN 算法來識別手寫字?jǐn)?shù)據(jù)集，它的缺點(diǎn)是浪費(fèi)存儲空間且執(zhí)行效率低。本文將使用決策樹算法來解決同樣的問題。相對 k-NN 算法，它更節(jié)約存儲空間且執(zhí)行效率更高。更重要的是，實(shí)施決策樹算法的過程將訓(xùn)練算法并得到知識 —— 這是開發(fā)機(jī)器學(xué)習(xí)程序的一般步驟。一旦理解了這個(gè)工作流程，才有可能利用好機(jī)器學(xué)習(xí)這把利劍。

在本文中，筆者將訓(xùn)練一個(gè)決策樹模型并使用該模型來識別手寫字?jǐn)?shù)據(jù)集。從中讀者將可以了解到：如何構(gòu)建學(xué)習(xí)模型？模型經(jīng)過訓(xùn)練后學(xué)習(xí)到了怎樣的知識？學(xué)習(xí)到的知識怎么表示和存儲？又該如何利用這些學(xué)到的知識來解決同類的問題？

本文適合以下背景的讀者閱讀：

• 了解 MNIST 數(shù)據(jù)集[2]；

  
  

• 使用 Javascript 作為編程語言的開發(fā)者；

  
  

• 不需要具備算法能力和高數(shù)的背景：全文只有一道數(shù)學(xué)公式；

  
  

• 加上示例代碼，全文總共 460 行，大約需要 20 分鐘的閱讀時(shí)間。

  
  

作者學(xué)識有限，如有疏漏，敬請指正。

在開始構(gòu)建決策樹之前，必須了解決策樹的工作原理。更詳細(xì)的內(nèi)容可以從參考資料的鏈接[2]中獲得。

一個(gè)例子是，如何教育一個(gè)學(xué)齡前的兒童辨認(rèn)貓和老虎？

• 我們會拿來一些示例照片，對照這些照片根據(jù)某些特征來訓(xùn)練小孩，告他 A 是貓，B 是老虎；

  
  

• 這些特征可能是，表面的顏色、耳朵的形狀、體積的大小等等；

  
  

• 我們總是希望兒童能快速辨認(rèn)出貓和老虎，畢竟假如他們真的遇到了老虎，則需要和老虎保持一定的距離；

  
  

• 其中一種篩選方法就是決策模型：把認(rèn)為最重要的特征先進(jìn)行甄別，然后到次要的，再到次次要的，以此來加速?zèng)Q策過程并得出判定。

作為一個(gè)示例，這里假設(shè)將識別老虎分為 2 個(gè)特征，分別是耳朵的形狀和體積大小，那么已知的數(shù)據(jù)可能是這樣的：

在程序中將使用數(shù)組的形式來表示上列數(shù)據(jù)，我把它稱為「抓虎的數(shù)據(jù)集」：

根據(jù)已有的數(shù)據(jù)集（經(jīng)驗(yàn)），貓和老虎的決策樹則是這樣：

這就是決策樹的工作原理了。因?yàn)閷儆诜诸愃惴?，所以決策樹也可以推演到 MNIST 數(shù)據(jù)集的識別中。把 728 個(gè)點(diǎn)作為特征，對應(yīng)的數(shù)字作為分類目標(biāo)即可應(yīng)用決策樹算法。當(dāng)然決策樹算法不適合解決 MNIST 數(shù)據(jù)集這類特征為數(shù)值型的問題，但是因?yàn)樗子诶斫夂蛯?shí)現(xiàn)，人們在通過解釋后都有能力去理解決策樹所表達(dá)的意義，因此作為機(jī)器學(xué)習(xí)中訓(xùn)練模型的算法來進(jìn)行入門則非常合適。

那么決策樹模型在程序中應(yīng)該如何構(gòu)建和表示呢？

決策樹的構(gòu)建過程就是在訓(xùn)練數(shù)據(jù)集中不斷劃分?jǐn)?shù)據(jù)集，直到找到目標(biāo)分類的過程。在此過程中需要找到最好的數(shù)據(jù)集劃分方式，遞歸地不斷劃分?jǐn)?shù)據(jù)集，直到所有的分類都屬于同一類目或沒有多余特征時(shí)停止生長。可以結(jié)合上一章節(jié)的「抓虎」的決策樹進(jìn)行理解。

找出最佳特征來劃分?jǐn)?shù)據(jù)

不難看出，構(gòu)建決策樹的關(guān)鍵問題是如何找出最佳的特征來劃分?jǐn)?shù)據(jù)集。先要回答問題是，假設(shè)我按照某個(gè)特征將數(shù)據(jù)集一分為二，那么有 N 種劃分方式，哪一種才算做「最好的劃分方式」？這就得引入香農(nóng)熵的概念。

香農(nóng)熵

劃分?jǐn)?shù)據(jù)集的大原則是：將無序的數(shù)據(jù)變得更加有序。

在「抓虎」的決策樹中，耳朵的形狀是最佳的劃分特征，因?yàn)楦鶕?jù)它來劃分后的數(shù)據(jù)集更加有序了（混雜項(xiàng)更少）。度量集合有序程度的其中一種方法就是香農(nóng)熵。香農(nóng)熵是信息論中的內(nèi)容，有興趣的讀者可以從參考資料的鏈接[4]中獲得更詳細(xì)的內(nèi)容。在此只需要知道的是，香農(nóng)熵越低則集合越有序。

香農(nóng)熵的計(jì)算公式是：

根據(jù)公式，在程序中實(shí)現(xiàn)計(jì)算香農(nóng)熵的代碼：

進(jìn)行一些測試將會有助于理解香農(nóng)熵的含義：

根據(jù)特征劃分?jǐn)?shù)據(jù)集

實(shí)現(xiàn)一個(gè)函數(shù)，根據(jù)特征來劃分?jǐn)?shù)據(jù)集：

拿「抓虎」的數(shù)據(jù)集進(jìn)行測試，看看劃分后的數(shù)據(jù)長什么樣？

從結(jié)果上看，成功地按照某個(gè)特征值把數(shù)據(jù)劃分了出來。

組合計(jì)算熵的算法和劃分?jǐn)?shù)據(jù)集的函數(shù)，就可以找出最佳的數(shù)據(jù)劃分特征項(xiàng)。以下是代碼實(shí)現(xiàn)：

將該函數(shù)在「抓虎」的數(shù)據(jù)集進(jìn)行測試，這個(gè)數(shù)據(jù)集的第一劃分依據(jù)是什么特征？

如無意外，程序?qū)⑤敵?0。耳朵的形狀是最佳的劃分特征，證明程序達(dá)到了我們預(yù)想的效果。

遞歸構(gòu)建決策樹

將上面的函數(shù)結(jié)合起來，再不斷地進(jìn)行遞歸就可以構(gòu)建出決策樹模型。什么時(shí)候應(yīng)該停止遞歸？有 2 種情況：

1. 當(dāng)所有的分類都屬于同一類目時(shí)，停止劃分?jǐn)?shù)據(jù) —— 該分類即是目標(biāo)分類；

   
   

2. 劃分的數(shù)據(jù)集中沒有其他特征時(shí)，停止劃分?jǐn)?shù)據(jù) —— 根據(jù)出現(xiàn)次數(shù)最多的類別作為目標(biāo)分類。

   
   

構(gòu)建樹的入?yún)⑹鞘裁矗?/p>

1. 訓(xùn)練數(shù)據(jù)集 —— 從訓(xùn)練數(shù)據(jù)中提取決策知識；

   
   

2. 特征的標(biāo)簽 —— 用于繪制決策樹每個(gè)節(jié)點(diǎn)。

   
   

以下是代碼實(shí)現(xiàn)：

自此就完成了學(xué)習(xí)模型的構(gòu)建。

將已有的數(shù)據(jù)集使用決策樹模型進(jìn)行訓(xùn)練，將會得到怎樣的知識？

以「抓虎」為例，運(yùn)行以下代碼：

可見，能得到的知識是針對數(shù)據(jù)集學(xué)習(xí)到的特征權(quán)重順序排列，是層層篩選決策的依據(jù)。

為了更加直觀和易于理解，可以將數(shù)據(jù)可視化（關(guān)于如何進(jìn)行數(shù)據(jù)可視化不是本文的內(nèi)容），它大概長這樣：

在程序中加入知識的存儲和提取函數(shù)，方便利用已有的知識進(jìn)行推理。所以再聲明 2 個(gè)輔助函數(shù)：

使用已有的知識進(jìn)行推理

只需要寫一個(gè)解析樹的函數(shù)就可以將學(xué)習(xí)到?jīng)Q策知識推理到同類的數(shù)據(jù)集中。以下是代碼實(shí)現(xiàn)：

以「抓虎」為例，下次見到一個(gè)耳朵形狀是三角形，體積較小的動(dòng)物，根據(jù)我們之前學(xué)習(xí)到的知識，它應(yīng)該是貓還是老虎？

如無意外，將會輸出 'Cat'。

最后，組合上面的函數(shù)，將其應(yīng)用到 MNIST 數(shù)據(jù)集的識別中。

值得注意的是，在數(shù)據(jù)準(zhǔn)備環(huán)節(jié)需要一些工作以適應(yīng)上文構(gòu)建的算法：

• 將特征由數(shù)值型轉(zhuǎn)化為標(biāo)稱型，這里我用了 0 / 1；

  
  

• 將分類值由 one-hot 向量轉(zhuǎn)化為具體的數(shù)字。

準(zhǔn)備數(shù)據(jù)

學(xué)習(xí)階段

在筆者的電腦上大概運(yùn)行了 10 分鐘：

看起來運(yùn)行時(shí)間很長，那怎么能說比 k-NN 算法更有效率？！

其實(shí)這是訓(xùn)練階段的耗時(shí)，而訓(xùn)練階段往往是離線處理，有大量的手段可以優(yōu)化這部分的性能。

應(yīng)用階段

如無意外，終端命令行中將輸出以下結(jié)果：

在同樣的數(shù)據(jù)集中，筆者上一篇文章構(gòu)建的 k-NN 算法，運(yùn)行時(shí)長是 325 秒，錯(cuò)誤率是 0.05。這組數(shù)據(jù)該如何解讀？筆者認(rèn)為：

1. 決策樹的在預(yù)測階段計(jì)算量非常小，所以執(zhí)行效率非常高；

   
   

2. 本文做特征處理時(shí)丟失了很多信息，數(shù)值型特征轉(zhuǎn)換到 0/1 的方式太過于粗暴。

   
   

使用決策樹算法來識別 MNIST 數(shù)據(jù)集效果很不理想，不過從中可以看到構(gòu)建一個(gè)機(jī)器學(xué)習(xí)應(yīng)用的完整過程。

參考資料：

1. 機(jī)器學(xué)習(xí)，Hello World from Javascript! 

https://github.com/alvinhui/alvinhui.github.io/issues/12?spm=5176.100239.blogcont304723.12.PKsWjc

  2. MNIST 數(shù)據(jù)集

http://yann./exdb/mnist/?spm=5176.100239.blogcont304723.13.PKsWjc

  3. 決策樹

https://en./wiki/Decision_tree?spm=5176.100239.blogcont304723.14.PKsWjc

  4. 香農(nóng)熵

https://zh./wiki/%E7%86%B5_(%E4%BF%A1%E6%81%AF%E8%AE%BA)?spm=5176.100239.blogcont304723.15.PKsWjc

  5. 本文示例代碼

https://github.com/alvinhui/machine_learning/tree/master/02_tree?spm=5176.100239.blogcont304723.16.PKsWjc