數(shù)據(jù)挖掘技術(shù)決策樹分類算法（ID3算法）研究

李莉

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

【關(guān)鍵詞】數(shù)據(jù)挖掘 決策樹 ID3 算法

1 緒論

1.1 數(shù)據(jù)挖掘

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

1.2 數(shù)據(jù)挖掘分類算法的意義

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

2 決策樹分類算法相關(guān)知識

2.1 決策樹的介紹

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

2.2 決策樹基本原理

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

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

I（Xi）=-log1P（Xi）

（1）

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

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

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

（2）

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

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

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

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

（4）

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

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

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

3 決策樹ID3算法分析

3.1 決策樹模型的建立

以下我們通過一個具體示例來演示經(jīng)典ID3算法的整個構(gòu)建過程。我們采用來自AllElectronics顧客數(shù)據(jù)庫數(shù)據(jù)元組訓(xùn)練集。

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

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

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的個數(shù)），n1=2（此時類別為no的個數(shù)），由公式計算可知：

*如果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所示，我們可以從圖中看出當(dāng)age為31-40時，節(jié)點(diǎn)所對應(yīng)的類別均為yes值，所以此時該節(jié)點(diǎn)的I（P2，n2）節(jié)點(diǎn)的信息熵為0，而<=30的屬性和>40的屬性都還有兩個類別，所以要對它們進(jìn)一步劃分。

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

4 總結(jié)

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

參考文獻(xiàn)

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

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

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

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

[5]王大玲等.基于概念層次樹的數(shù)據(jù)挖掘算法的研究與實(shí)現(xiàn)[J].計算機(jī)科學(xué)，2001，2（02）： 63-66.

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