段繼磊

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

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

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

二、決策樹的理論和算法

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

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

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

具體的ID3算法如下：

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

If A為空

返回N為葉節(jié)點，標記為R中多數(shù)樣本對應(yīng)的類；

If N為屬于同一個類

返回N為葉節(jié)點，標記為所有樣本對應(yīng)的類；

Else{

For每一個屬性

估計選擇a作節(jié)點的信息增益；

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

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

For 每一個Ri

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

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

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

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

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

（3）準確性高：跟其它分類方法相比，決策樹算法通常可以得到很好的分類準確性，因此利用決策樹得到的分類規(guī)則能夠較準確地對樣本進行分類，可以較好的滿足用戶的的應(yīng)用需要。

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

三、應(yīng)用實例

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

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

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

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

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

根據(jù)以上4種情況，分類性能可以按照精度來評價，精度的定義如下：

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

四、結(jié)論

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

參考文獻：

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

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