DecisionTree的原理

摘 要：本文探討了decision treee的設計原理，分析了Decision tree的核心分類思想，并給出了決策樹的分值構建的偽碼。

關鍵詞：決策樹;分類算法;信息熵;信息增益

一、 研究背景

給定A一個問題Q1，我們列出其諸多答案選項B。比如，B={B1，B2，…，Bn}。其中，n標示共有n個子選項，每個選項都是潛在的答案。然后，我們讓A根據我們的提供的答案B，告訴我們B中的哪個答案是正確的，比如Bi是A給我們的反饋。若答案Bi并非問題的最終解，我們更進一步的根據B的特點提問，設問題是Q2，根據Q2，我們設定答案選項C。同樣，不是一般性，我們假定C={C1，C2，…，Cp}。其中，p表示C中共有p個答案選項。如果A告訴我們Ci是正確答案，那么，我們就得到了更進一步地對問題的收斂解。以此類推，我們可以一直以這種操作延續下去，則最終肯定能夠得到一組滿足要求的解。這個過程就是普通樹的生成過程，同時，也是決策樹的研究背景。

二、 信息論基礎

n分之一份信息量（定義1）：若存在n個相同概率的消息，則每個消息的概率p是1/n，一個消息傳遞的信息量為-log2（1/n）。

熵（定義2）：熵是體系混亂程度的度量，即信息的信息量大小和它的不確定性有直接的關系。對于任意一個隨機變量X，若有n個消息，其給定概率分布為P=（p1，p2，…，pn），則由該分布傳遞的信息量稱為P的熵，它的熵定義為：

H（X）=-∑xP（x）log2[P（x）]

由圖可見，離散信源的信息熵具有：

①非負性：即收到一個信源符號所獲得的信息量應為正值，H（X）≥0

②對稱性：即P=0.5

③確定性：H（1，0）=0，即P=0或P=1已是確定狀態，所得信息量為零

④極值性：因H（U）是P上是凸的，且一階導數在P=0.5 時等于0，所以當P=0.5時，H（U）最大。

信息增益（定義）：設關于變量X的劃分P，在做劃分之前的信息為H（Xi），做劃分之后的信息為H（Xi），則系統的增益為△=H（Xi）-H（Xi+δ）。其中δ表示相對Xi的該變量。

注意，這里的Xi是向量。我們稱Xi為特征向量。顯然信息的增益指的是變化前后系統中信息的變化量。若某個Xi，使得△最大，則這樣的Xi是最好的，因為使用這個特征向量引起的操作增益是系統敏感的。

三、 基于ID3分類的Decision tree

決策樹由node、branch和leaf組成。和普通的樹一樣，決策樹的最上面的結點為根結點，遞歸地，每個branch是一個新的決策node，或者是樹的leaf。每個決策結點代表一個問題或決策，通常對應于待分類對象的屬性。每一個葉子結點代表一種可能的分類結果。決策樹的分類的思想是：沿決策樹從上到下遍歷的過程中，在每個結點處都會生成一次詢問測試，對每個checking node上的不同問題對應的不同的詢問測試結果產生不同的后續分支，以此類推，直到最后到達某個葉子結點。前述增益的特性時，已經明確了，ID3算法計算每個屬性的信息增益，對于關于使用某個特征值后系統的增益，越大越好。故使用作為具有最高增益的屬性作為給定checking node的詢問（query）測試屬性。且以此詢問測試屬性構作一個node，并以該節點的屬性標記，對該屬性的每個值創建一個分支據此partition樣本。

下面給出遞歸調用如下的CreateBranch函數創建決策樹分支的方法創建決策樹的偽代碼，以結束本文的討論：

CreateBrach（…）{

檢測數據集中的每個子項是否屬于同一類：

If yes

Return label of class

Else

通過計算信息熵獲得的信息增益尋找劃分數據集的最好特征

Partition data set

創建分支節點

For 每個劃分的subset

Call CreateBranch（…），并增加返回結果到分支節點中

Return 分支結點

}

參考文獻：

[1]周志華，王玨.機器學習及其應用2009[M].北京：清華大學出版社，2009.

[2]周志華.機器學習[J].航空港，2018（2）：94.

[3]崔偉東，周志華，李星，等.支持向量機研究[J].計算機工程與應用，2001（1）.

[4]姜遠，黎銘，周志華.一種基于半監督學習的多模態Web查詢精化方法[J].計算機學報，2009（10）：217-224.

[5]李楠，姜遠，周志華.基于模型似然的超1-依賴貝葉斯分類器集成方法[J].模式識別與人工智能，2016，20（6）.

[6]曲開社，成文麗，王俊紅.ID3算法的一種改進算法[J].計算機工程與應用，2003，39（25）：104-107.

作者簡介：

智巖，廣東省廣州市，廣州工商學院。