基于Python的決策樹配鏡預測系統

陳群賢 上海電機學院高職學院

1 決策樹（decision tree)

1.1 決策樹算法的描述

決策樹是分類和預測的挖掘方法中應用較為廣泛的模式之一，是一種由內部結點、分叉及葉結點構成的，用來表示決策樹規則的樹結構，其中，內部結點表示某種檢驗屬性，分叉表示檢驗的結果，葉結點表示類或某一類的分類，而頂點稱為根結點。在構建的決策樹中，從根節點到葉結點的一條路徑就對應著一條分類規則，其構建的過程，取決于檢驗屬性的選擇以及分叉點的確定。不同決策樹算法采用的屬性分割法不同，常用的決策樹算法主要有：ID3、C4.5、GINT等。

1.2 決策樹構造過程所遵循的原則

如果把一個節點（非葉子節點）看做是提一個問題，那么原則就是：盡可能先提最重要的問題，通過最少的問題得到最多的信息。所以對于決策樹來說，就是希望從根節點走到葉節點的決策路徑越短越好。如果說把決策樹中每一個非葉子節點看做是對樣本的某個特征進行提問。那么我們可以這樣認為：構造決策樹，就是要正確地選擇特征，使得決策樹盡可能地矮。

如何用貪心法來構造一顆“矮”的決策樹？我們在構造決策上并選擇特征的時候，為了縮短決策路徑，就需要讓測試樣本的不確定性盡可能地少。建立規則的過程如下：首先利用數據集根據特征屬性計算信息增益，然后選擇具有最大信息增益的特征屬性作為根節點，以該特征屬性的每個數值作為一個分支，最后根據特征屬性的每個數值劃分的數據集只包含一個數值或者只包含一個特征屬性為止。

1.3 信息熵

用貪心法來構造一顆“矮”的決策樹時用到的熵，香農熵（Shannon’s Entropy）又簡稱為熵(Entropy)，是對不確定性的測量，數據集包含的類別越多，對應信息熵越大；設隨機變量X的取值范圍是{x1,x2,…,xn)，則X的熵H定義為：

這里b是對數所使用的底數，通常是2；p(xi)是選擇該分類的概率。

1.4 決策樹歸納算法（ID3）

1970-1980 ，J.Ross. Quinlan首先提出ID3算法，第一步是選擇屬性判斷結點，采用信息熵的比較。第二步是信息增益(Information Gain)：Gain(A)=Info(D)-Infor_A(D)通過A來作為節點分類獲取了多少信息。ID3 算法以信息增益作為特征屬性選擇的依據，導致數值類型多的特征屬性比數值類型少的特征屬性具有更高的信息增益。

信息增益 (Information Gain)：Gain(A)=Info(D)-Infor_A(D)。

2 決策樹算法

2.1 決策樹算法的形式化描述

決策樹算法的形式化描述如下：

1)起初只是一顆空樹以及一些經過處理的數據樣本的集合，在進行數據分配時，選取最優的根節點，還要選取測試的屬性，然后再對樣本中的數據進行劃分；

2)如果當前的樣本集合中的屬性屬于同一種類別，那么就只創建本類別的葉子節點；

3)如果不是同一屬性，則就選取最優的計算方法計算當前集合的任何的可能劃分方法；

4)將用最優劃分所對應的屬性當作節點的屬性，而且創建和該屬性含有一樣多的子節點；

5)根據所選的屬性的值作為節點的條件，而且將節點當中的父節點所對應的樣本集合劃分為每個子節點當中；

6)再將分支的節點當作當前的節點，然后從步驟（2）如此循環，指導最后劃分徹底為止。

2.2 決策樹算法的流程圖

決策樹算法的流程圖如圖1所示.

圖1 決策樹算法的流程圖

3 根據ID3算法構造配鏡預測系統決策樹

3.1 數據集合

本次測試的模擬數據如表1所示。數據包含患者的年齡、視力診斷結果、閃光程度、淚流量等四個特征屬性以及選好的眼鏡類型。其中：

患者年齡 age：young、pre、presbyopic

患者視力診斷結果prescript：myope、hyper

患者閃光程度astigmatic：yes、no

患者流淚癥狀tearRate：normal、reduced

隱形眼鏡類型：no lenses(不需要鏡片)、hard(硬型鏡片)、soft(軟型鏡片)

表1 測試模擬數據

3.2 配鏡預測系統決策樹歸納算法

例如tearRate的信息增益，Gain(tearRate) = Info(type_lenses) - Infor_tearRate (type_lenses)。

Info(type_lenses)是這24個記錄中，no lenses的概率15/24，soft的概率5/24，hard的概率4/24，帶入到信息熵公式。

Infor_tearRate (type_lenses)是tearRate屬性中normal的概率是12/24，其中no lenses的概率3/12，soft的概率5/12，hard的概率4/12；reduced的概率是12/24，其中no lenses的概率12/12，soft的概率0/12，hard的概率0/12，分別代入信息熵公式：

Info(type_lenses)與Infor_tearRate (type_lenses)做差，即是tearRate的信息增益，具體如下：

G a i n(t e a r R a t e)=I n f o(t y p e_l e n s e s)-I n f o r_t e a r R a t e (t y p e_l s e s)=1.3 2 6 0 8 7 5 2 5 3 6 4 2 9 8 3-0.7772925846688997=0.5487949406953986

類似，Gain(age) = 0.03939650364612124, Gain(prescript) =0.039510835423565815, Gain(astigmatic)= 0.37700523001147723

在配鏡預測系統中，比較發現tearrate特征可以使熵下降得最快，所以，選擇信息增益最大的tearRate作為根節點。

重復計算即可。

3.3 算法結果圖

根據ID3算法，選擇信息增益最高的屬性tearRate，即選擇類流量作為決策樹的根節點，其他過程依次類推。通過Python實現ID3算法，利用訓練樣本構造的決策樹文本方式是：

{`tearRate`： {`normal`： {`astigmatic`： {`no`： {`age`：{`presbyopic`： {`prescript`： {`hyper`： `soft`, `myope`： `no lenses`}}, `young`： `soft`, `pre`： `soft`}}, `yes`： {`prescript`：{`hyper`： {`age`： {`presbyopic`： `no lenses`, `young`： `hard`,`pre`： `no lenses`}}, `myope`： `hard`}}}}, `reduced`： `no lenses`}}

采用文本方式很難分辨出決策樹的摸樣，調用dtPlot.createPlot(lensesTree)函數，可將決策樹可視化展現如圖2所示。

圖2 隱形眼鏡配型決策樹

4 結束語

本文展現了決策樹在隱形眼鏡配型預測系統中的應用，挖掘出對配鏡具有指導性的潛在規律，具有一定的現實意義。利用已經積累的信息，通過決策樹算法可以挖掘出眼科醫生對隱形眼鏡配型的決策過程，幫助非專業用戶判斷隱形眼鏡類型的選配。