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

1 決策樹（decision tree)

1.1 決策樹算法的描述

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

1.2 決策樹構(gòu)造過程所遵循的原則

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

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

1.3 信息熵

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

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

1.4 決策樹歸納算法（ID3）

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

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

2 決策樹算法

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

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

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

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

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

4)將用最優(yōu)劃分所對應的屬性當作節(jié)點的屬性，而且創(chuàng)建和該屬性含有一樣多的子節(jié)點；

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

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

2.2 決策樹算法的流程圖

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

圖1 決策樹算法的流程圖

3 根據(jù)ID3算法構(gòu)造配鏡預測系統(tǒng)決策樹

3.1 數(shù)據(jù)集合

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

患者年齡 age：young、pre、presbyopic

患者視力診斷結(jié)果prescript：myope、hyper

患者閃光程度astigmatic：yes、no

患者流淚癥狀tearRate：normal、reduced

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

表1 測試模擬數(shù)據(jù)

3.2 配鏡預測系統(tǒng)決策樹歸納算法

例如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

在配鏡預測系統(tǒng)中，比較發(fā)現(xiàn)tearrate特征可以使熵下降得最快，所以，選擇信息增益最大的tearRate作為根節(jié)點。

重復計算即可。

3.3 算法結(jié)果圖

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

{`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`}}

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

圖2 隱形眼鏡配型決策樹

4 結(jié)束語

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