段繼磊

摘要 介紹了決策樹(shù)的理論和算法，研究了決策樹(shù)算法在數(shù)據(jù)挖掘中的應(yīng)用實(shí)例，實(shí)驗(yàn)結(jié)果表明決策樹(shù)是一種很有效的數(shù)據(jù)挖掘技術(shù)。

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

Abstract The theory and algorithm of decision tree are introduced in the paper. The decision tree algorithms application case in data mining is researched. The experimental results indicate the decision tree is an effective data mining technique.

Key words Data mining； Decision tree

一、引言

數(shù)據(jù)挖掘是近年來(lái)計(jì)算機(jī)科學(xué)中的熱點(diǎn)領(lǐng)域。決策樹(shù)[1，2]是一種應(yīng)用廣泛的算法，在數(shù)據(jù)挖掘中占有重要的地位。本文介紹了決策樹(shù)的理論和算法，研究了決策樹(shù)算法在數(shù)據(jù)挖掘中的應(yīng)用實(shí)例，實(shí)驗(yàn)結(jié)果表明決策樹(shù)是一種很有效的數(shù)據(jù)挖掘技術(shù)。

二、決策樹(shù)的理論和算法

決策樹(shù)是一種逼近離散函數(shù)值的方法，是用于分類和預(yù)測(cè)的主要數(shù)據(jù)挖掘方法之一。作為以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法，決策樹(shù)能夠?qū)σ唤M無(wú)次序、無(wú)規(guī)則的實(shí)例進(jìn)行學(xué)習(xí)，從而推理出決策樹(shù)表現(xiàn)形式的分類規(guī)則。

決策樹(shù)是一種典型的分類方法，是研究如何利用樹(shù)把一個(gè)復(fù)雜的多類分類問(wèn)題轉(zhuǎn)化為若干個(gè)簡(jiǎn)單的分類問(wèn)題，從而較容易的表示和解決問(wèn)題。決策樹(shù)首先對(duì)數(shù)據(jù)進(jìn)行處理，利用歸納算法生成可讀的規(guī)則和決策樹(shù)，通過(guò)利用樹(shù)來(lái)轉(zhuǎn)換問(wèn)題，決策樹(shù)算法可以很容易地得到if-then形式的分類規(guī)則，然后使用決策對(duì)新數(shù)據(jù)進(jìn)行分析。本質(zhì)上決策樹(shù)是通過(guò)一系列規(guī)則對(duì)數(shù)據(jù)進(jìn)行分類的過(guò)程。

建立決策樹(shù)的過(guò)程可以分為兩個(gè)階段。其中，第一階段為建樹(shù)，即通過(guò)使用訓(xùn)練數(shù)據(jù)集進(jìn)行學(xué)習(xí)，從而導(dǎo)出決策樹(shù)。決策樹(shù)歸納的基本算法是貪心算法，它采用的是自項(xiàng)向下遞歸的各個(gè)擊破方式來(lái)構(gòu)建判定樹(shù)。建立決策樹(shù)的第二個(gè)階段為剪枝。通過(guò)使用測(cè)試數(shù)據(jù)集對(duì)決策樹(shù)進(jìn)行驗(yàn)證。當(dāng)建立的決策樹(shù)無(wú)法正確分類時(shí)，就需要對(duì)決策樹(shù)進(jìn)行剪枝以便解決過(guò)度擬合訓(xùn)練集合的問(wèn)題。剪枝階段降低了由于訓(xùn)練集的噪聲而產(chǎn)生的影響，從而建立一棵正確的決策樹(shù)。在眾多的決策樹(shù)算法中，ID3和C4.5是最早研究的決策樹(shù)算法。

具體的ID3算法如下：

用訓(xùn)練集R創(chuàng)建節(jié)點(diǎn)N；

If A為空

返回N為葉節(jié)點(diǎn)，標(biāo)記為R中多數(shù)樣本對(duì)應(yīng)的類；

If N為屬于同一個(gè)類

返回N為葉節(jié)點(diǎn)，標(biāo)記為所有樣本對(duì)應(yīng)的類；

Else{

For每一個(gè)屬性

估計(jì)選擇a作節(jié)點(diǎn)的信息增益；

選出信息增益最大的屬性a*作為當(dāng)前節(jié)點(diǎn)；

根據(jù)a*的取值將R分裂為{Ri），并對(duì)決策樹(shù)分叉；

For 每一個(gè)Ri

If Ri為空則返回葉結(jié)點(diǎn)；Else 執(zhí)行ID3（Ri）；}

針對(duì)ID3算法不能直接處理連續(xù)型屬性的不足， C4.5決策樹(shù)算法進(jìn)行了改進(jìn)]，從而能夠處理屬性值空缺和連續(xù)型屬性等應(yīng)用。

作為數(shù)據(jù)挖掘領(lǐng)域中的經(jīng)典算法，決策樹(shù)算法與其它數(shù)據(jù)挖掘方法相比具有如下的顯著優(yōu)點(diǎn)：

（1）易于理解：決策樹(shù)能夠生成簡(jiǎn)單和易于理解的規(guī)則，能夠清晰的顯示哪些字段比較關(guān)鍵和重要，因此用戶不需要了解很多決策樹(shù)的背景知識(shí)。

（2）執(zhí)行效率高：由于決策樹(shù)計(jì)算量相對(duì)較小，而且容易轉(zhuǎn)化成分類規(guī)則，只需要從樹(shù)根向下一直到達(dá)葉子節(jié)點(diǎn)，沿途的分裂條件就能唯一確定一條分類的規(guī)則，因此較容易計(jì)算，執(zhí)行速度快，分類效率非常高。

（3）準(zhǔn)確性高：跟其它分類方法相比，決策樹(shù)算法通?？梢缘玫胶芎玫姆诸悳?zhǔn)確性，因此利用決策樹(shù)得到的分類規(guī)則能夠較準(zhǔn)確地對(duì)樣本進(jìn)行分類，可以較好的滿足用戶的的應(yīng)用需要。

（4）具有很好的可伸縮性：決策樹(shù)算法具有很好的可伸縮性，決策樹(shù)算法不但可以應(yīng)用到對(duì)小數(shù)據(jù)集進(jìn)行數(shù)據(jù)挖掘，而且可對(duì)海量數(shù)據(jù)集進(jìn)行數(shù)據(jù)挖掘。

三、應(yīng)用實(shí)例

本文將決策樹(shù)算法應(yīng)用到sonar數(shù)據(jù)集上進(jìn)行應(yīng)用實(shí)例研究。sonar數(shù)據(jù)集是UCI數(shù)據(jù)庫(kù)[3]中的一個(gè)數(shù)據(jù)集，它包括了61個(gè)屬性，208個(gè)樣本，2個(gè)類別。本文采用精度來(lái)衡量分類算法的性能。本文采用精度來(lái)衡量分類算法的性能。分類器對(duì)樣本的分類結(jié)果有4種情況。

TP：被正確地分類為屬于此類別的樣本數(shù)量。

TN：被正確地分類為不屬于此類別的樣本數(shù)量。

FP：被錯(cuò)誤地分類為屬于此類別的樣本數(shù)量。

FN：被錯(cuò)誤地分類為不屬于此類別的樣本數(shù)量。

根據(jù)以上4種情況，分類性能可以按照精度來(lái)評(píng)價(jià)，精度的定義如下：

實(shí)驗(yàn)中也利用na?ve bayes算法對(duì)到sonar數(shù)據(jù)集進(jìn)行了分類，并將其結(jié)果作為比較的基準(zhǔn)。

四、結(jié)論

決策樹(shù)算法是數(shù)據(jù)挖掘中的重要方法。本文介紹了決策樹(shù)的理論和算法，研究了決策樹(shù)算法在的一個(gè)數(shù)據(jù)挖掘應(yīng)用實(shí)例，實(shí)驗(yàn)結(jié)果說(shuō)明決策樹(shù)算法是一種非常有效的算法。

參考文獻(xiàn)：

[1] QUINLAN J. C4.5：Programs for Machine Learning[M].San Matteo，CA：Morgan Kaufm- ann Publishers，1993.

[2] 董躍華，劉力.基于相關(guān)系數(shù)的決策樹(shù)優(yōu)化算法.計(jì)算機(jī)工程與科學(xué)， 2015， 37（9）：1783-1793.