陳群賢 上海電機(jī)學(xué)院高職學(xué)院

1 決策樹（decision tree)

1.1 決策樹算法的描述

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

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

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

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

1.3 信息熵

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

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

1.4 決策樹歸納算法（ID3）

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

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

2 決策樹算法

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

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

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

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

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

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

5)根據(jù)所選的屬性的值作為節(jié)點(diǎn)的條件，而且將節(jié)點(diǎn)當(dāng)中的父節(jié)點(diǎn)所對(duì)應(yīng)的樣本集合劃分為每個(gè)子節(jié)點(diǎn)當(dāng)中；

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

2.2 決策樹算法的流程圖

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

圖1 決策樹算法的流程圖

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

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

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

患者年齡 age：young、pre、presbyopic

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

患者閃光程度astigmatic：yes、no

患者流淚癥狀tearRate：normal、reduced

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

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

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

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

Info(type_lenses)是這24個(gè)記錄中，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

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

重復(fù)計(jì)算即可。

3.3 算法結(jié)果圖

根據(jù)ID3算法，選擇信息增益最高的屬性tearRate，即選擇類流量作為決策樹的根節(jié)點(diǎn)，其他過程依次類推。通過Python實(shí)現(xiàn)ID3算法，利用訓(xùn)練樣本構(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)了決策樹在隱形眼鏡配型預(yù)測(cè)系統(tǒng)中的應(yīng)用，挖掘出對(duì)配鏡具有指導(dǎo)性的潛在規(guī)律，具有一定的現(xiàn)實(shí)意義。利用已經(jīng)積累的信息，通過決策樹算法可以挖掘出眼科醫(yī)生對(duì)隱形眼鏡配型的決策過程，幫助非專業(yè)用戶判斷隱形眼鏡類型的選配。