戴艷麗江蘇省宿遷高等師范學(xué)校，江蘇宿遷　223800

分析數(shù)據(jù)挖掘中決策樹(shù)算法及其應(yīng)用

戴艷麗
江蘇省宿遷高等師范學(xué)校，江蘇宿遷223800

數(shù)據(jù)分析中一種比較新的形式就是數(shù)據(jù)挖掘，數(shù)據(jù)挖掘的應(yīng)用非常廣泛，在金融保險(xiǎn)業(yè)、政府部門(mén)、運(yùn)輸領(lǐng)域等都有廣泛的應(yīng)用。本文通過(guò)分析決策樹(shù)的算法研究，闡述了ID3、C4.5、CART等算法的優(yōu)劣勢(shì)以及在數(shù)據(jù)挖掘中的運(yùn)用，在實(shí)際的科研活動(dòng)中，要進(jìn)行綜合考慮和科學(xué)總結(jié)，為未來(lái)相關(guān)方面的發(fā)展提供更加科學(xué)和合理的依據(jù)。

數(shù)據(jù)挖掘；決策樹(shù)算法；應(yīng)用

數(shù)據(jù)分析中一種比較新的形式就是數(shù)據(jù)挖掘，數(shù)據(jù)挖掘就是指挖掘具有價(jià)值的但有相當(dāng)隱蔽性的信息?，F(xiàn)在，數(shù)據(jù)挖掘的應(yīng)用非常廣泛，在金融保險(xiǎn)業(yè)、政府部門(mén)、運(yùn)輸領(lǐng)域等都有廣泛的應(yīng)用。決策樹(shù)算法在數(shù)據(jù)挖掘中可以起到很好的作用，本文將通過(guò)分析決策樹(shù)的算法研究和在數(shù)據(jù)挖掘中的改進(jìn)，希望對(duì)決策樹(shù)在數(shù)據(jù)挖掘中的應(yīng)用提供幫助。

1　決策樹(shù)算法的概述

決策樹(shù)算法是一種數(shù)學(xué)歸納方法，強(qiáng)調(diào)從復(fù)雜無(wú)序的事例中，推導(dǎo)出最終結(jié)果的方法，在分類(lèi)器、預(yù)測(cè)模型和數(shù)據(jù)挖掘中應(yīng)用比較廣泛。決策樹(shù)算法要首先建立一個(gè)決策樹(shù)模型，然后通過(guò)所建立的模型對(duì)復(fù)雜無(wú)序的數(shù)據(jù)進(jìn)行逐項(xiàng)測(cè)試，從根節(jié)點(diǎn)一直到最終的葉節(jié)點(diǎn)。

2　數(shù)據(jù)挖掘中常見(jiàn)的決策樹(shù)算法研究

決策樹(shù)經(jīng)過(guò)長(zhǎng)時(shí)間的發(fā)展，現(xiàn)在常見(jiàn)的算法主要包括ID3算法、C4.5算法以及CART算法。下面我們對(duì)相關(guān)的算法做一個(gè)簡(jiǎn)單的介紹。

2.1ID3算法

ID3算法在決策樹(shù)算法中，是一種比較主流的算法。它的屬性選擇的標(biāo)準(zhǔn)是信息增益方法，通過(guò)在各級(jí)結(jié)點(diǎn)上運(yùn)用信息增益方法，來(lái)確定結(jié)點(diǎn)生成時(shí)的屬性。這樣做可以使取得相關(guān)信息最?。?］。ID3算法的流程圖如圖1所示。

主要公式為：假設(shè)U是整個(gè)集合，｛X1，……，Xn｝是整個(gè)集合的一個(gè)部分，它的概率分布可以表示為Pi=P（Xi），則稱：

為信息源的信息熵。里面的對(duì)數(shù)取2為底，當(dāng)Pi為零的時(shí)候，則

通過(guò)上面的分析，我們對(duì)ID3算法已經(jīng)有了一個(gè)簡(jiǎn)單的了解，下面對(duì)ID3算法的優(yōu)劣勢(shì)進(jìn)行相應(yīng)的研究。ID3算法具有的優(yōu)勢(shì)是：1）由于ID3算法對(duì)所有可能出現(xiàn)的決策樹(shù)都有所涉及，所以具有完整性；2）信息增益減少了訓(xùn)練樣例不夠準(zhǔn)確的敏感性；3）算法在所用時(shí)間上比較少，同時(shí)分類(lèi)效率較高；4）ID3算法的結(jié)點(diǎn)數(shù)量在所有算法中最小。ID3算法的劣勢(shì)是：1）由于ID3算法的假設(shè)前提比較單一，所以不具有對(duì)所有假設(shè)進(jìn)行表示的特點(diǎn)；2）ID3算法在進(jìn)行測(cè)試之后，不會(huì)選擇在對(duì)這個(gè)點(diǎn)進(jìn)行測(cè)試，所以相對(duì)來(lái)說(shuō)得到的結(jié)果只是個(gè)體最優(yōu)的；3）ID3算法對(duì)于屬性值數(shù)目比較依賴，但屬性值本身并不能保證是最優(yōu)的；4）ID3算法的開(kāi)銷(xiāo)較大；5）ID3算法主要基于屬性選擇，而屬性選擇是否對(duì)決策樹(shù)有很大影響，在學(xué)術(shù)界缺乏確定的結(jié)論。通過(guò)對(duì)ID3算法的優(yōu)劣勢(shì)分析，可以認(rèn)為ID3算法的理論明白，方法也并不復(fù)雜，在數(shù)據(jù)挖掘中，可以得到一個(gè)很好的應(yīng)用。

2.2C4.5算法

C4.5算法是昆蘭在1993年創(chuàng)立的，它創(chuàng)立的主要依據(jù)是ID3算法，但更加完整。相比于ID3算法，C4.5算法對(duì)于屬性的不間斷性和屬性值不完整的情況進(jìn)行了改變，在決策樹(shù)剪枝階段也有了比較成熟的算法。C4.5算法采用的是信息增益率為基準(zhǔn)進(jìn)行屬性測(cè)試。信息增益率的英文名稱是：information gain ratio。基本公式為：

假設(shè)整個(gè)集合為S，離散屬性A的不同取值用n表示，子集劃分為S1，……，Sn，用A表示的信息增益率為：

其中：

C4.5算法的優(yōu)點(diǎn)是對(duì)于離散和連續(xù)屬性都可以很好地進(jìn)行處理，信息增益率相比信息增益屬性來(lái)說(shuō)，對(duì)于整個(gè)決策樹(shù)保持穩(wěn)定也更加有利。但同時(shí)C4.5算法也暴露出了一些問(wèn)題：1）C4.5算法的結(jié)果在準(zhǔn)確性上有很大提高，但對(duì)于全局最優(yōu)效果還有待加強(qiáng)；2）決策樹(shù)的整體性能在決策樹(shù)構(gòu)造完成后不易改變；3）C4.5算法在分組時(shí)的效率有待提高；4）C4.5算法的核心信息增益率也有著局限性，如果信息熵的值選擇較小的話，那么信息增率的牢固性則很可能達(dá)不到要求［2］。

2.3CART算法

CART屬于挖掘算法，最早在統(tǒng)計(jì)學(xué)中開(kāi)始廣泛應(yīng)用，相對(duì)來(lái)說(shuō)比較靈活。CART算法的一個(gè)特點(diǎn)就是是一種監(jiān)督學(xué)習(xí)法，即在使用時(shí)，要首先建立一個(gè)可以對(duì)CART進(jìn)行評(píng)價(jià)的樣本集。一般情況下CART的學(xué)習(xí)樣本集為：

其中X為屬性向量，Y為標(biāo)簽向量，其中，回歸樹(shù)的Y的數(shù)量值是有序的，分類(lèi)樹(shù)的Y的數(shù)值是無(wú)序的。

CART算法是基于統(tǒng)計(jì)理論建立的，它的解析能力比較強(qiáng)大，對(duì)非參數(shù)的識(shí)別具有一定作用，對(duì)于相關(guān)的數(shù)據(jù)要求也不是特別的嚴(yán)格，可以是無(wú)序或者離散的，最終獲得的數(shù)據(jù)結(jié)果的規(guī)則也比較簡(jiǎn)單。當(dāng)然，CART算法也存在著一定缺陷。相對(duì)來(lái)說(shuō)CART算法在穩(wěn)定性方面的表現(xiàn)不盡如人意，所建立的模型之間的差異也比較明顯，對(duì)于樣本較小的處理結(jié)果能力有待提高。

3　數(shù)據(jù)挖掘中決策樹(shù)算法的改進(jìn)

3.1決策樹(shù)算法的優(yōu)化

在數(shù)據(jù)挖掘中，決策樹(shù)的算法要有所優(yōu)化。首先應(yīng)該明確加權(quán)簡(jiǎn)化熵的理念，所謂的加權(quán)簡(jiǎn)化熵指的是決策樹(shù)的權(quán)值取決于屬性A的值的具體數(shù)量，然后根據(jù)子集Vi計(jì)算相應(yīng)的簡(jiǎn)化熵值，再和權(quán)值進(jìn)行相乘，所得結(jié)果就是加權(quán)簡(jiǎn)化熵。最后在對(duì)結(jié)果進(jìn)行比較得出最優(yōu)選擇，主要公式為：

其中P為A對(duì)應(yīng)的概率。

3.2新算法的優(yōu)劣勢(shì)分析

通過(guò)與傳統(tǒng)的ID3算法進(jìn)行比較，發(fā)現(xiàn)新算法具有下面的優(yōu)點(diǎn)：1）權(quán)值的引入是一個(gè)比較新的觀念，對(duì)于決策屬性的取值有很大的幫助；2）由于新算法解決了決策樹(shù)“空枝”的問(wèn)題，所以算法的可靠性和易讀性得到了提升；3）新算法相比傳統(tǒng)算法在時(shí)間上的節(jié)省比較多，提升了運(yùn)行效率。

3.3挖掘流程闡述

數(shù)據(jù)挖掘的過(guò)程比較復(fù)雜，首先要通過(guò)對(duì)數(shù)據(jù)進(jìn)行分析，分出不同的數(shù)據(jù)類(lèi)型和格式，在經(jīng)過(guò)清理篩選等工作，存入SQL SERVER。然后選擇ID3、C4.5、CART或者改進(jìn)算法，生成對(duì)應(yīng)的決策樹(shù)，并對(duì)其進(jìn)行檢測(cè)［3］。

4　結(jié)論

隨著社會(huì)經(jīng)濟(jì)的發(fā)展，數(shù)據(jù)挖掘的作用越來(lái)越重要，決策樹(shù)算法在數(shù)據(jù)挖掘中的作用也越來(lái)越廣泛，各種決策樹(shù)算法的各有其自己的優(yōu)劣勢(shì)。在數(shù)據(jù)挖掘中，要根據(jù)實(shí)際情況，進(jìn)行綜合考慮和科學(xué)總結(jié)，為未來(lái)相關(guān)方面的研究提供更加科學(xué)和合理的依據(jù)。

［1］張悅，楊學(xué)全.決策樹(shù)算法在學(xué)生選課系統(tǒng)中的應(yīng)用［J］.科技經(jīng)濟(jì)市場(chǎng)，2014（7）：185.

［2］張莉.數(shù)據(jù)挖掘研究現(xiàn)狀及發(fā)展趨勢(shì)［J］.赤峰學(xué)院學(xué)報(bào)（自然科學(xué)版），2014（18）：14-15.

［3］胡常偉，錢(qián)程.基于決策樹(shù)的模具制造企業(yè)訂單履約數(shù)據(jù)挖掘［J］.模具工業(yè)，2014（11）：4-7.

TP3

A

1674-6708（2015）152-0033-02