數據挖掘技術決策樹分類算法（ID3算法）研究

李莉

摘要 近些年來，互聯網迅速發(fā)展，數據量每年都以驚人的幅度提升，人們的生活、政府的管理都和電子信息設備息息相關，特別是電子商務和科學實驗數據庫的迅速壯大，為我們帶來了海量的數據。這些海量的數據中，往往蘊藏非常多有價值的記錄和信息，等待著人們去挖掘，人們希望將這些信息分離提取出來進行更高程度的分析和統(tǒng)計，以便為我們所取用。而目前大部分數據庫系統(tǒng)僅僅可以實現數據的增、刪、改、查，很難找到大數據之間所蘊含的規(guī)則和關系，比較缺乏挖掘數據內部價值的有效方法，較難通過數據的維度去探索和發(fā)現、預測未來的趨勢。本文通過對數據挖掘技術中決策樹的分類算法做出實驗分析，進行比較，給出合理的分析建議。

【關鍵詞】數據挖掘 決策樹 ID3 算法

1 緒論

1.1 數據挖掘

在海量數據中提取有價值的信息和知識我們稱之為數據挖掘技術。在海量數據庫、云端服務器、數據倉儲等存儲媒介里面都存放著大量的數據信息，我們可以在這些存儲媒介當中去探尋有價值的數據，深入分析和挖掘數據中的內在價值。幫助決策者找尋數據與數據之間可能存在的潛在關聯結構，及時有效的發(fā)現可能被忽略和遺忘的要點。通常來說，這些數據信息對未來趨勢的行為判斷有著重要的作用，從而引導決策者做出正確的判斷和最優(yōu)的決策。因此，人們發(fā)明的決策樹分類算法，來幫助人們更好的挖掘數據中有價值的信息。決策樹分類算法的挖掘過程可能要多次循環(huán)往復螺旋遞進，直至達到我們想要的結果。

1.2 數據挖掘分類算法的意義

目前來看，數據挖掘在實際應用中有著重要的作用和意義，數據挖掘技術可以運用于很多場合。比如：在股票金融市場中，可以對股票的歷史交易信息數據進行分析和預測，并多其漲跌走勢做出比較準確的判斷;再比如在天氣預報的過程中，對空氣各類成分以及近半個月的數據進行收集、處理和分析，可以對天氣預報做出比較準確的合理預測;在產品的銷售系統(tǒng)中，己存原始數據庫信息，現在假定有新的客戶添加進數據庫中，我們想講廣告促銷信息分發(fā)給顧客。如果每一位顧客都通知，這勢必成本較大，耗費較多，此時通過數據挖掘技術，找到那些比較有意向購買的顧客，向他們推送廣告，可以大大節(jié)約了時間和金錢費用，促進的成交量，為商家?guī)砀蟮慕洕б?。數據挖掘技術其實就是一種決策支持的過程，是對數據進行深層次的數據分析方法。在平常生活中，可以將數據挖掘技術應用于方方面面，對促進社會的進步和發(fā)展有著很大的幫助。因此，對決策樹分類算法的相關研究有著較高的實用價值和研究價值。

2 決策樹分類算法相關知識

2.1 決策樹的介紹

決策樹（Decision Tree，DT）是一種常用的分類方法，適用于解決各種的分類問題。它通過將數據集進行分類、聚類和預測建模，將一個整體的大問題逐個逐個分解成每個子集小問題，再逐個一已解決子集問題，提高解決問題的效率。通常我們需要構建一個決策樹來對分類過程進行建模比較。

2.2 決策樹基本原理

1948年，美國數學家克勞德.艾而德伍.香農（ Claude Elwood Shannon）創(chuàng)建了信息論，用來解決在信息傳遞過程中的不確定性等問題。在信息論的基礎上，決策樹運用技術發(fā)展壯大。它通過數學的方法度量分析信息數據，通過自定義不同的符號情況，來描繪信息量的大小。其中包括一系列相關概念描述，以下為具體展示：

（1）自信息量。設連續(xù)發(fā)出的信號為Xl、X2…Xn為發(fā)出的信號，直到接收Xi信號，把不確定性的信號標識為I（Xi），即式（1）：

I（Xi）=-log1P（Xi）

（1）

其中P（Xi）表示信源發(fā)出Xi的概率。

（2）信息熵。再通過信息熵來度量信號源X的不確定性，即式（2）：

H（X）=∑P（Xi）Iog2p（xi）

（2）

其中X為信號源，i為任意可能的符號數。

（3）條件熵。設信號源X和Y不是相互獨立的，則用條件熵H（X/Y）來度量整體的不確定性。設X對應的信號源為Xi，Y對應的信號源為Yj，則有： H（X/Y）=-∑∑P（XiYi）10g2P（Xi/Yj）（3）

（4）平均互信息量。信號源X和Y之間的相互關系：

I（X，Y）=H（X）-H（X/Y）

（4）

依據信息論，設S為整個樣本數據整體集合，其中包含n類訓練數據集，每類有Si個實例，則把它們分類所需要的信息量I用如下公式（5）表示為：

I（S1，S2，……，Sn）=一∑Pil0g2（Pi）（5）

由此，我們可以得到數據樣本為S的包含N類的數據集，為了使下一步的工作盡可能盡量的減小，要求每一次都選擇信息增益最大的屬性作為決策樹的節(jié)點，并對屬性進行劃分建立分枝，依據此思想劃分數據樣本集。

3 決策樹ID3算法分析

3.1 決策樹模型的建立

以下我們通過一個具體示例來演示經典ID3算法的整個構建過程。我們采用來自AllElectronics顧客數據庫數據元組訓練集。

利用ID3算法對對數據集合進行決策樹模型的建立，對顧客進行分類，整個計算過程如下：

1計算給定樣本集的信息熵，我們使用以下公式進行計算：

2.計算每個屬性的信息增益

（1）需要確定屬性age的每個樣本值yes和no的分布。

*如果age=“<=30”，則p1=2（有2個yes），n1=3（有3個no），

由公式計算可知：

*如果age=“31……40”，則p2=4（有4個yes），n2=0（O個no），由公式計算知：I（p2，n2）=O：

*如果age=“>40”，則p3=3（有3個yes），n3=2（2個no），由公式計算可知：I（p3，n3） =0.971;

（2）對于屬性1ncome，需要知道m(xù)come的每個樣本值Yes和no的分布。

*如果mcome=“high”，則p1=2（此時類別為yes的個數），n1=2（此時類別為no的個數），由公式計算可知：

*如果mcome-“medium”，則p2=4（有4個yes），n2=2（有2個no），由公式計算可知：I（p2，n2） =0.148;

*如果income=“l(fā)ow”，則p3=3（有3個yes），n3=1（有1個no），由公式計算可知：I（p3，n3） =0.279;

（3）生成決策樹的根和分枝。如圖1所示，我們可以從圖中看出當age為31-40時，節(jié)點所對應的類別均為yes值，所以此時該節(jié)點的I（P2，n2）節(jié)點的信息熵為0，而<=30的屬性和>40的屬性都還有兩個類別，所以要對它們進一步劃分。

（4）依照上文所述的算法原理過程，對整體訓練數據集進行遞歸分解，按照數據信息不同屬性分為不同類別，最終建成決策樹的分類模型，得到決策樹的理想化模型。

4 總結

在這個信息化的時代，處理大量混亂而又復雜的數據的一個很好的方法是分類，在分類技術的發(fā)展過程中，幾個流行的技術分別是神經網絡、遺傳算法、貝葉斯分類、決策樹等。決策樹算法理論清晰，效果直觀，更易被讀者所理解，能夠較好的顯示出數據之間的關聯和內在聯系，具有不錯的分類預測能力。因此，對決策樹算法的研究有著重要的研究價值和實際意義。

參考文獻

[1]毛國君，段立娟，王實，石云.數據挖掘原理與算法[M]，北京：清華大學出版社，2005.

[2] Jiawei Han，Micheline Kamber著，范明，孟小峰等譯.數據挖掘概念與技術[M].北京：機械工業(yè)出版社，2001.

[3]閃四清，陳茵，程雁等譯，美MehmedKantardzic著，數據挖掘——概念、模型、方法和算法[M].北京：清華大學出版社，2003.

[4]張維東等.利用決策樹進行數據挖掘中的信息熵計算[J].計算機工程，2001（03）：66-68.

[5]王大玲等.基于概念層次樹的數據挖掘算法的研究與實現[J].計算機科學，2001，2（02）： 63-66.

[6]唐華松等.數據挖掘中決策樹算法的探討[J].計算機應用研究，2001（08）： 36-40.