決策樹典型算法研究綜述

邵晏暉

摘要：決策樹算法是數(shù)據(jù)挖掘領(lǐng)域的一個(gè)研究熱點(diǎn)，通常用于提取描述重要數(shù)據(jù)類的模型或預(yù)測未來的數(shù)據(jù)趨勢。該文介紹了決策樹及其發(fā)展過程，重點(diǎn)闡述了三種典型的決策樹算法，分析了它們的優(yōu)缺點(diǎn)，并對三種算法進(jìn)行了比較，最后探討了決策樹算法的改進(jìn)方向。

關(guān)鍵詞：數(shù)據(jù)挖掘；決策樹；分類

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2018）08-0175-03

1引言

數(shù)據(jù)挖掘（Data Mining）技術(shù)是一個(gè)非常熱門的、重要的、具有廣闊應(yīng)用前景的研究領(lǐng)域。數(shù)據(jù)挖掘的兩個(gè)目標(biāo)是預(yù)測和描述。分類算法是屬于預(yù)測式數(shù)據(jù)挖掘的一種數(shù)據(jù)分析方法。其中，決策樹算法是目前經(jīng)常被使用的數(shù)據(jù)分類方法之一，已經(jīng)成功應(yīng)用在醫(yī)療、交通、金融等領(lǐng)域。

決策樹是機(jī)器學(xué)習(xí)中的一個(gè)樹狀預(yù)測模型，其內(nèi)部結(jié)點(diǎn)表示在一個(gè)屬性上的測試，而葉子結(jié)點(diǎn)代表最終的類別結(jié)果。決策樹模型很自然地還原了做決策的過程，將復(fù)雜的決策過程拆分成了一系列簡單的選擇，因而能直觀地解釋決策的整個(gè)過程。

本文對三種典型的決策樹分類算法進(jìn)行了介紹，分析了不同算法的優(yōu)缺點(diǎn)，并討論了決策樹算法今后的改進(jìn)方向。

2典型決策樹分類算法

決策樹是一種常用的數(shù)據(jù)挖掘方法，是一個(gè)類似流程圖的樹型結(jié)構(gòu)。決策樹包含三個(gè)元素：根結(jié)點(diǎn)、內(nèi)部結(jié)點(diǎn)和葉子結(jié)點(diǎn)。若要對未知的數(shù)據(jù)對象進(jìn)行分類，可以按照決策樹的數(shù)據(jù)結(jié)構(gòu)對數(shù)據(jù)集中的屬性（取值）進(jìn)行測試，從決策樹的根結(jié)點(diǎn)到葉結(jié)點(diǎn)的一條路徑就代表了對相應(yīng)數(shù)據(jù)對象的類別預(yù)測。決策樹是一種分而治之（divide-and-conquer）的決策過程，形成決策樹的決策規(guī)則有許多，如信息增益，信息增益比，基尼指數(shù)等。下面介紹三種典型的決策樹分類算法：ID3算法、C4.5算法和CART算法。

2.1 ID3算法

決策樹分類方法的核心算法是由Ross Quinlan在1986年提出的ID3算法。ID3算法的思想是：首先在決策樹的各級結(jié)點(diǎn)上，選擇信息增益最大的屬性作為分類結(jié)點(diǎn)，根據(jù)該屬性的不同取值分裂出各個(gè)子結(jié)點(diǎn)，隨后采用遞歸的方法建立決策樹的分支，直到樣本集中只含有一種類別時(shí)停止，得到最終的決策樹。

基尼指數(shù)與熵有類似的性質(zhì)。Gini（D）、Cini（D，A）分別表示集合D的不確定性以及通過A=a分割后集合的不確定性?；嶂笖?shù)值越大，樣本集合的不確定性也就越大。

CART算法的優(yōu)點(diǎn)：1）自動(dòng)處理缺失值，無需進(jìn)行缺失值替換，能夠處理孤立點(diǎn)。2）可使用自動(dòng)的成本復(fù)雜性剪枝來得到歸納性更強(qiáng)的樹。3）變量數(shù)多時(shí)，可判斷屬性變量的重要性，自動(dòng)忽略對目標(biāo)變量沒有貢獻(xiàn)的屬性。

CART算法的缺點(diǎn)：1）CART算法本身是一種大樣本的統(tǒng)計(jì)分析方法，樣本量較小時(shí)模型不穩(wěn)定。2）CART算法的要求是被選擇的屬性要是連續(xù)且有序的，并且只能產(chǎn)生兩個(gè)子結(jié)點(diǎn)。

2.4三種算法的比較

本文給出了三種典型的決策樹算法，它們在關(guān)鍵技術(shù)上的使用各自不同，表1列出了對此的一個(gè)比較。

3決策樹算法的改進(jìn)方向

3.1決策樹算法的分類精度

分類預(yù)測算法的精度代表了該算法得到的預(yù)測分類結(jié)果和實(shí)際分類結(jié)果之間的接近程度，精度越高，預(yù)測的結(jié)果越接近現(xiàn)實(shí)情況，說明分類算法性能越好。決策樹的分類精度將會一直是今后的研究重點(diǎn)。判斷各種決策樹的生成算法和剪枝算法的優(yōu)劣，精度是最重要的衡量指標(biāo)。決策樹剪枝是為了減小數(shù)據(jù)噪聲對影響，構(gòu)造多變量決策樹是為了減小決策樹的深度，它們的最終目的都是為了提高決策樹的精度。

3.2決策樹算法與其他技術(shù)的結(jié)合

在數(shù)據(jù)挖掘中，面臨的數(shù)據(jù)往往是海量的，數(shù)據(jù)挖掘方法的主動(dòng)性和快速性顯得日益重要。只使用單一的決策樹分類算法已經(jīng)很難處理目前日益龐大的數(shù)據(jù)集，完成各種數(shù)據(jù)挖掘任務(wù)。因此需要研究決策樹算法同其他方法交叉結(jié)合的問題。如果把決策樹方法同神經(jīng)網(wǎng)絡(luò)技術(shù)、模糊集理論、遺傳算法等相結(jié)合來進(jìn)行研究，可以不同程度地提高處理效率和精度。

4結(jié)束語

決策樹算法雖然已經(jīng)有了廣泛的研究和應(yīng)用，并且廣泛應(yīng)用于各個(gè)領(lǐng)域，如語音識別，模式識別，專家系統(tǒng)等。但是，決策樹算法仍需在適應(yīng)性、容噪性等方面進(jìn)行適當(dāng)?shù)母倪M(jìn)。如何尋找更好的數(shù)據(jù)預(yù)處理方法，如何發(fā)掘更好的優(yōu)化決策樹方法，如何更有效快速地完成決策樹剪枝，如何將決策樹與多種方法交叉結(jié)合等多種問題，都需要今后的學(xué)習(xí)中去研究。