基于決策樹算法的數據挖掘應用研究

段繼磊

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

關鍵詞 數據挖掘；決策樹

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

一、引言

數據挖掘是近年來計算機科學中的熱點領域。決策樹[1，2]是一種應用廣泛的算法，在數據挖掘中占有重要的地位。本文介紹了決策樹的理論和算法，研究了決策樹算法在數據挖掘中的應用實例，實驗結果表明決策樹是一種很有效的數據挖掘技術。

二、決策樹的理論和算法

決策樹是一種逼近離散函數值的方法，是用于分類和預測的主要數據挖掘方法之一。作為以實例為基礎的歸納學習算法，決策樹能夠對一組無次序、無規則的實例進行學習，從而推理出決策樹表現形式的分類規則。

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

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

具體的ID3算法如下：

用訓練集R創建節點N；

If A為空

返回N為葉節點，標記為R中多數樣本對應的類；

If N為屬于同一個類

返回N為葉節點，標記為所有樣本對應的類；

Else{

For每一個屬性

估計選擇a作節點的信息增益；

選出信息增益最大的屬性a*作為當前節點；

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

For 每一個Ri

If Ri為空則返回葉結點；Else 執行ID3（Ri）；}

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

作為數據挖掘領域中的經典算法，決策樹算法與其它數據挖掘方法相比具有如下的顯著優點：

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

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

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

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

三、應用實例

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

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

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

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

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

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

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

四、結論

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

參考文獻：

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

[2] 董躍華，劉力.基于相關系數的決策樹優化算法.計算機工程與科學， 2015， 37（9）：1783-1793.