徐彧鏵

（浙江省衢州第二中學(xué)，浙江衢州，324000）

0 引言

圖像識(shí)別技術(shù)，要運(yùn)用目前流行的機(jī)器學(xué)習(xí)算法，而目前流行的機(jī)器學(xué)習(xí)算法就有十幾種，比如支持向量機(jī)、神經(jīng)網(wǎng)絡(luò)、決策樹。機(jī)器學(xué)習(xí)是人工智能發(fā)展的重要一部分，它涉及的學(xué)科很多，應(yīng)用也相當(dāng)廣泛，它通過分析、研究、設(shè)計(jì)讓計(jì)算機(jī)學(xué)習(xí)知識(shí)，從而提高完善自身的性能。但是神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)的速度較慢，傳統(tǒng)的支持向量機(jī)則不能解決分類多的問題。

本文針對(duì)鳶尾花的特征類別少以及種類少的特點(diǎn)，采用決策樹算法對(duì)課題進(jìn)行展開，對(duì)比與其他人利用支持向量機(jī)、神經(jīng)元網(wǎng)絡(luò)模型來進(jìn)行研究，該系統(tǒng)具有模型簡(jiǎn)單、便于理解、計(jì)算方便、消耗資源少的優(yōu)點(diǎn)。

1 決策樹模型和學(xué)習(xí)

本文采用決策樹算法對(duì)鳶尾花進(jìn)行分類，先建立決策樹的模型并進(jìn)行學(xué)習(xí)訓(xùn)練，在決策樹的訓(xùn)練過程中采用是信息論的知識(shí)進(jìn)行特征選擇，對(duì)選定的特征采用分支的處理，然后再對(duì)分支過后的數(shù)據(jù)集如此反復(fù)的遞歸生成決策樹，在一顆決策樹生成完后對(duì)決策樹進(jìn)行剪枝，以減小決策樹的擬合度，來達(dá)到一個(gè)對(duì)鳶尾花較高的分類準(zhǔn)確率。

要對(duì)鳶尾花進(jìn)行分類首先需要大量的鳶尾花數(shù)據(jù)集作為本文的實(shí)驗(yàn)數(shù)據(jù)，本文采用的數(shù)據(jù)集是來自加州大學(xué)歐文分校UCI數(shù)據(jù)庫中的鳶尾花數(shù)據(jù)集。該數(shù)據(jù)集中鳶尾花的屬性有四個(gè)，分別是花萼長(zhǎng)度、花萼寬度、花瓣長(zhǎng)度和花瓣寬度，鳶尾花的類別則有三種，分別是Iris Setosa，Iris Versicolour，Iris Virginica，用簡(jiǎn)寫Se、Ve和Vi表示這三種花，具體數(shù)據(jù)如圖1所示。

■1.1 信息論

美貝爾電話研究所的數(shù)學(xué)家香農(nóng)是信息論的創(chuàng)始人，1948年香農(nóng)發(fā)表了《通訊的數(shù)學(xué)理論》,成為信息論誕生的標(biāo)志。信息論的誕生對(duì)信息技術(shù)革命以及科學(xué)技術(shù)的發(fā)展起到重要作用。信息論中有兩個(gè)概念信息增益及信息增益率，都是用于衡量原始數(shù)據(jù)集在按照某一屬性特征分裂之后整體信息量的變化值。這樣，本文就可以通過這種指標(biāo)尋找出最優(yōu)的劃分屬性，數(shù)據(jù)集在經(jīng)過劃分之后，節(jié)點(diǎn)的“純度”越來越高，這里的純度值得是花朵的類別，當(dāng)某一節(jié)點(diǎn)中花朵全為一類時(shí)，該節(jié)點(diǎn)已經(jīng)達(dá)到最純狀態(tài)，無需再進(jìn)行劃分，反之繼續(xù)劃分。

圖1 鳶尾花數(shù)據(jù)集

信息熵用于描述信源的不確定性。即發(fā)生每個(gè)事件都有不確定性，為了使不確定性降低，我們需要引入一些相關(guān)的信息進(jìn)行學(xué)習(xí)，引入信息越多，那么得到的準(zhǔn)確率越高，信息熵越高，信源越不穩(wěn)定。例如一束鳶尾花，它可能是Se,可能是Vi，也有可能是Ve，我們利用數(shù)據(jù)庫中的各種鳶尾花的花瓣長(zhǎng)度、花瓣寬度、花萼長(zhǎng)度和花萼寬度來預(yù)測(cè)鳶尾花的類別，引入的鳶尾花種類越多，信息熵就越高。

樣本集合D的信息熵Ent(D)以下面的公式進(jìn)行計(jì)算，其中集合里第k類樣本所占的比例是pk，k的取值范圍是從1到y(tǒng)，y值得是總共有y類樣本，通過式（1）可以計(jì)算得到原始樣本集的信息熵。

1.1.2 信息增益

信息增益即在一個(gè)條件下，信源不確定性減少的程度。信息增益用于度量節(jié)點(diǎn)的純度。信息增益對(duì)可取值數(shù)目較多的屬性有所偏好。在鳶尾花數(shù)據(jù)集的D集合中，屬性a取到某一取值情況的概率乘該取值情況的信息熵得到的值記為 Dv，其中V指的是該屬性a可以取值的個(gè)數(shù)，則屬性a的信息增益為：

通過式（2）可以計(jì)算得到對(duì)于原始總的數(shù)據(jù)集來講，分別采用四種不同的屬性值計(jì)算過后得到的信息增益，比較信息增益大小可以得到最優(yōu)的分裂屬性。在進(jìn)行分裂之后，對(duì)于分裂過后的子集，首先判斷其同一子集里的所有樣本點(diǎn)是不是都屬于同一類花，如果是的則不需要進(jìn)行再次的分裂，如果不是的則表明改點(diǎn)依舊信息不純，需要進(jìn)一步分裂。

1.1.3 信息增益率

信息增益率用于度量節(jié)點(diǎn)的純度。由于信息增益對(duì)可取值數(shù)目較多的屬性有所偏好，因?yàn)閷?duì)于一個(gè)有多值的屬性，它的信息增益是很高的，利用信息增益率可以減少這種現(xiàn)象的產(chǎn)生。它的計(jì)算過程如式（3）所示，字母的意義和信息增益中一樣。

通過信息增益率的計(jì)算同樣可以得到原始的鳶尾花數(shù)據(jù)集中按照某一屬性進(jìn)行劃分之后的信息增益率，選擇產(chǎn)生最大值的屬性作為分裂的標(biāo)準(zhǔn)。同樣地，分裂后的子集中也是采用相同的遞歸方式形成新的子集，直到所有末端分支的子集里所有的樣本都為同一類型的花朵為止。

■1.2 決策樹生成算法

1.2.1 ID3算法與C4.5算法

決策樹生成常用的基本算法是ID3算法和C4.5算法。

ID3算法是一種采用信息增益的方法構(gòu)造決策樹，這種算法該算法開始時(shí)，所有的數(shù)據(jù)都在根節(jié)點(diǎn)上，屬性都是離散的，停止分割的條件是一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)都是屬于同一個(gè)類別或者沒有屬性可以再對(duì)屬性進(jìn)行分割了。

C4.5算法是應(yīng)用信息增益率進(jìn)行的，克服了用信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足。C4.5算法能夠完成對(duì)連續(xù)屬性的離散化處理，由于在本文所研究的對(duì)象中，對(duì)于萼片長(zhǎng)度、萼片寬度、花瓣長(zhǎng)度、花瓣寬度這些數(shù)據(jù)實(shí)際是上都是一些連續(xù)的小數(shù)值，因此如果不采用離散化的操作，這樣直接進(jìn)行處理就會(huì)導(dǎo)致屬性的取值數(shù)量太多的情況，極易造成過擬合的現(xiàn)象。若不是離散的就將它離散化，離散化采用的是一種設(shè)置區(qū)間的形式對(duì)數(shù)據(jù)離散化。利用分裂信息計(jì)算，得到值越大，表示按照該屬性值進(jìn)行劃分越優(yōu)，根據(jù)計(jì)算出的值再對(duì)數(shù)據(jù)分區(qū)間。

數(shù)據(jù)的離散化是一個(gè)比較復(fù)雜的過程，一般都是設(shè)置一個(gè)閾值將其分成兩部分。首先對(duì)屬性的取值進(jìn)行升序排序，得到排序結(jié)果之后，任意兩個(gè)屬性取值之間都有可能的作為分裂點(diǎn)，計(jì)算每個(gè)可能的分裂點(diǎn)的分裂信息，即式（3）中的IV(a)。選擇IV(a)最大的點(diǎn)作為該特征的最佳分裂點(diǎn)，這樣就獲得了該屬性的分裂點(diǎn)的取值情況，就可將連續(xù)的數(shù)值離散化成為兩類不同的數(shù)值。

1.2.2 CART算法

CART是分類樹也是回歸樹。它的根節(jié)點(diǎn)和每一個(gè)非葉子節(jié)點(diǎn)都有兩個(gè)分支，是一棵二叉樹。由于本文所討論的是對(duì)鳶尾花的分類問題，因此這里只考慮當(dāng)CART是分類樹的情況，這時(shí)CART采用基尼值作為節(jié)點(diǎn)分裂的依據(jù)，基尼值越小，節(jié)點(diǎn)越純，決策樹的正確率越高。分類樹的作用是通過一個(gè)對(duì)象的特征來預(yù)測(cè)該對(duì)象所屬的類別且預(yù)測(cè)結(jié)果是離散的。GINI值的計(jì)算公式：其中I表示總共的類別樹，i表示每一種類別的個(gè)數(shù)。

在鳶尾花數(shù)據(jù)集D中，根據(jù)一類屬性分為兩類，分別是D1，D2。在D數(shù)據(jù)集中，A屬性的基尼值則為D1發(fā)生的概率乘D1的基尼值加D2發(fā)生的概率乘D2的基尼值，式5就表示了數(shù)據(jù)集D按照某一屬性值A(chǔ)進(jìn)行二分類之后的結(jié)果。

但是實(shí)際中，鳶尾花的所有屬性值都不是只有兩種值得取值情況，因此，需要對(duì)屬性設(shè)置一個(gè)閾值，使其變成兩類值，具體的閾值選取方法完全等同于C4.5中對(duì)連續(xù)屬性值的處理方法。

■1.3 決策樹的剪枝

決策樹的剪枝分為預(yù)剪枝和后剪枝。剪枝的目的在于解決數(shù)據(jù)噪音、訓(xùn)練數(shù)據(jù)量少、過擬合等問題，使決策樹更高效。

預(yù)剪枝就是在構(gòu)造決策樹的過程中，先對(duì)每個(gè)葉子節(jié)點(diǎn)統(tǒng)計(jì)里面每個(gè)樣本類別的個(gè)數(shù)，選取該葉子節(jié)點(diǎn)中樣本類別個(gè)數(shù)最多的類別作為該葉子節(jié)點(diǎn)的類別。然后在節(jié)點(diǎn)劃分前進(jìn)行估計(jì)，先計(jì)算目前模型A對(duì)新樣本預(yù)測(cè)的準(zhǔn)確率，若當(dāng)前結(jié)點(diǎn)劃分得到一個(gè)較為復(fù)雜的模型B之后，模型B對(duì)相同的新樣本預(yù)測(cè)的準(zhǔn)確率并沒有提升，則不對(duì)當(dāng)前結(jié)點(diǎn)進(jìn)行劃分并且將當(dāng)前結(jié)點(diǎn)標(biāo)記為葉結(jié)點(diǎn)，表示該節(jié)點(diǎn)純度較高，不需要再進(jìn)行劃分，達(dá)到了預(yù)剪枝的效果，簡(jiǎn)化模型。

后剪枝是在決策樹生成后進(jìn)行的，自底向上對(duì)非葉子節(jié)點(diǎn)進(jìn)行考察，如果原始模型是A，并計(jì)算目前模型對(duì)新樣本預(yù)測(cè)的準(zhǔn)確率。在將這個(gè)非葉子結(jié)點(diǎn)的子節(jié)點(diǎn)去掉之后，即將該非葉子去掉之后得到的一個(gè)簡(jiǎn)單的模型B，再計(jì)算模型B對(duì)相同的新樣本預(yù)測(cè)的準(zhǔn)確率，發(fā)現(xiàn)準(zhǔn)確率提升了，就直接把該非葉子結(jié)點(diǎn)的子樹都刪掉，這樣就達(dá)到了后剪枝的效果，簡(jiǎn)化模型提高正確率。

2 總結(jié)與展望

本文通過決策樹的算法，將鳶尾花數(shù)據(jù)庫中的數(shù)據(jù)進(jìn)行學(xué)習(xí)來建立該模型，再通過信息論中的信息熵來描述信源的不確定性，信息增益與信息增益率來度量節(jié)點(diǎn)的純度，從而進(jìn)行特征選擇，再生成決策樹，在決策樹生成過程中和生成后剪枝，對(duì)比分析了ID3算法、C4.5算法、以及CART算法在鳶尾花分類任務(wù)上的可行性。解決了傳統(tǒng)手工分類效率低、準(zhǔn)確率低等缺點(diǎn)。

針對(duì)鳶尾花數(shù)據(jù)集中屬性值一般都是連續(xù)值得情況，本文討論了如何采用分裂信息對(duì)某一種屬性值得取值情況進(jìn)行分析以計(jì)算獲得一個(gè)最優(yōu)的分裂點(diǎn)，并還分析了算法可能出現(xiàn)過擬合的問題，針對(duì)過擬合本文討論了如果從源頭以及結(jié)果解決過擬合的方法，分別是預(yù)剪枝和后剪枝，以達(dá)到?jīng)Q策樹更高的準(zhǔn)確率。

但由于客觀條件以及時(shí)間的限制，本文還有以下幾個(gè)方面需要改進(jìn)：本文僅僅運(yùn)用決策樹算法通過鳶尾花的不同屬性判斷出了鳶尾花的類別，為未來更復(fù)雜的模型提供了幫助、奠定了基礎(chǔ)。但隨著科技的進(jìn)步與發(fā)展，本作者希望日后可以通過圖片判斷出鳶尾花的年齡等一系列更詳細(xì)的信息。