基于C4.5 數(shù)據(jù)挖掘算法研究與實(shí)現(xiàn)

蒲海坤＊ 高 鑫 桑 鑫

（西京學(xué)院 信息工程學(xué)院，陜西 西安 710123）

近年來(lái),我國(guó)經(jīng)濟(jì)飛速發(fā)展,科學(xué)技術(shù)方面也得到了巨大的進(jìn)步,人們也不斷在其他領(lǐng)域進(jìn)行探索,信息技術(shù)的迅猛發(fā)展標(biāo)志著信息時(shí)代已經(jīng)到來(lái),伴隨而來(lái)的是數(shù)據(jù)的爆發(fā),“大數(shù)據(jù)”被越來(lái)越多的提及。目前數(shù)據(jù)挖掘技術(shù)主要運(yùn)用在對(duì)信息的提取、分類、篩選等方面,以獲取有用信息,而決策樹(shù)算法就是其中之一。隨著大數(shù)據(jù)時(shí)代的到來(lái),人們對(duì)于海量信息背后蘊(yùn)藏的知識(shí)的渴求更加強(qiáng)烈,數(shù)據(jù)的處理方法勢(shì)必受到關(guān)注和重視,以幫助人們找到這些海量數(shù)據(jù)背后所存在的規(guī)律和相應(yīng)的關(guān)系,以根據(jù)現(xiàn)有規(guī)則對(duì)未來(lái)事物或發(fā)展做出預(yù)測(cè)。

1 知識(shí)挖掘概念與步驟

數(shù)據(jù)挖掘是一個(gè)對(duì)數(shù)據(jù)處理分析的過(guò)程，對(duì)海量數(shù)據(jù)進(jìn)行分析處理以挖掘探索有價(jià)值知識(shí)的過(guò)程，簡(jiǎn)單說(shuō)來(lái)就是從大量知識(shí)中找到有價(jià)值的、自己所需要的知識(shí)。

知識(shí)挖掘一般是由以下幾個(gè)步驟構(gòu)成：

（1）數(shù)據(jù)清洗：用來(lái)清洗和剔除不相關(guān)的數(shù)據(jù)知識(shí)。

（2）數(shù)據(jù)集成：將來(lái)自于不同地方的數(shù)據(jù)資源集合在一起。

（3）數(shù)據(jù)轉(zhuǎn)換：將集合起來(lái)的數(shù)據(jù)資源轉(zhuǎn)換成易于存貯的形式，便于后續(xù)程序運(yùn)用。

（4）數(shù)據(jù)挖掘：主要作用是利用先進(jìn)智能的方法來(lái)挖掘數(shù)據(jù)或?qū)?shù)據(jù)知識(shí)進(jìn)行規(guī)律歸納，是整個(gè)過(guò)程中的基本步驟。

（5）模式評(píng)估：此環(huán)節(jié)是根據(jù)標(biāo)準(zhǔn)評(píng)價(jià)出具有價(jià)值的數(shù)據(jù)知識(shí)。

（6）知識(shí)表示：利用相關(guān)技術(shù)向用戶展示所需要的數(shù)據(jù)知識(shí)。

決策樹(shù)算法綜述：

決策樹(shù)中應(yīng)用了熵的三種形式,分別是信息熵、條件熵和互信息。熵是一個(gè)衡量指標(biāo), 衡量海量數(shù)據(jù)中信息知識(shí)的不確定性。信息知識(shí)的不確定性可以決定熵的大小, 兩者呈正相關(guān)聯(lián)系，而數(shù)據(jù)信息的不確定性和復(fù)雜程度是由概率來(lái)決定的。若信息只有一類,則純度最高,熵值為0；若信息有兩類且數(shù)量相同,則混亂度最高,純度最低,熵值為1。

下面是一元模型中信息熵的計(jì)算公式,其中c 為特征數(shù)量,p為特征在總數(shù)中的占比,T 為隨機(jī)變量：

以下是條件熵E(T,X)的計(jì)算公式,p(c)為每個(gè)特征值的占比,E(c)為特征值的信息熵。條件熵的值越低說(shuō)明二元模型的不確定性越小。

決策樹(shù)算法從本質(zhì)上來(lái)講就是對(duì)數(shù)據(jù)進(jìn)行測(cè)算, 再根據(jù)屬性相似度進(jìn)行歸屬分類,構(gòu)造出樹(shù)狀圖,從最上面的根節(jié)點(diǎn)出發(fā),由上至下分出各個(gè)子節(jié)點(diǎn),直到數(shù)據(jù)屬性不能在進(jìn)行分裂為止。在進(jìn)行分類遞歸時(shí), 選擇合適的特征作為節(jié)點(diǎn)決策樹(shù)構(gòu)造中最為重要的環(huán)節(jié)。

2 C4.5 數(shù)據(jù)挖掘設(shè)計(jì)及算法實(shí)現(xiàn)

2.1 ID3 決策樹(shù)構(gòu)建

構(gòu)建ID3 算法決策樹(shù)所用到的天氣數(shù)據(jù)集如表1 所示。

構(gòu)建決策樹(shù)根結(jié)點(diǎn)所用到的信息：分類信息熵如表2 所示。

表2 分類信息熵

構(gòu)建決策樹(shù)的分支點(diǎn)：把outlook 作為根節(jié)點(diǎn),它的取值分別是雨天,陰天和晴天。而陰天分支結(jié)果都為是,所以對(duì)另外兩個(gè)分支使用同樣的方法,計(jì)算分類熵,屬性熵,成功構(gòu)建決策樹(shù)。

構(gòu)建好決策樹(shù),我們就可以利用決策樹(shù)進(jìn)行預(yù)測(cè)：

當(dāng)有新的數(shù)據(jù)添加,需要獲得結(jié)果時(shí),可根據(jù)上面的決策樹(shù)進(jìn)行預(yù)測(cè),如outlook:下雨天,Temp:溫和,Humidity:偏高,Wind:無(wú),通過(guò)決策樹(shù)分析可知這組數(shù)據(jù)在第二層進(jìn)入sunny 分支, 在第三層humidity 進(jìn)入左邊分支,play golf：否。

2.2 C4.5 決策樹(shù)構(gòu)建

C4.5 算法是機(jī)器學(xué)習(xí)算法中一種常見(jiàn)的分類決策樹(shù)算法,它是ID3 算法的一種延伸和優(yōu)化。C4.5 算法決策樹(shù)的構(gòu)建過(guò)程與ID3 算法基本相同,是在ID3 算法的基礎(chǔ)上,在計(jì)算完Gain(T,X)之后計(jì)算各個(gè)屬性的分裂信息SplitInfo。因此,我們可以繼續(xù)以O(shè)utlook 作為根節(jié)點(diǎn),在決策樹(shù)分支的每一個(gè)結(jié)點(diǎn)處都計(jì)算出分類熵,屬性熵,進(jìn)而求出信息增益率,以此作為選擇結(jié)點(diǎn)的標(biāo)準(zhǔn)。

2.3 實(shí)驗(yàn)結(jié)果分析

本文在對(duì)決策樹(shù)算法進(jìn)行鉆研,在天氣數(shù)據(jù)集上,編寫(xiě)代碼并利用ID3 算法和C4.5 算法生成決策樹(shù),并對(duì)算法所產(chǎn)生的結(jié)果作分析。C4.5 算法運(yùn)行結(jié)果如圖1 所示。

圖1 C4.5 算法結(jié)果圖

從結(jié)果來(lái)看,采用C4.5 算法構(gòu)建的決策樹(shù)具有較高的數(shù)據(jù)準(zhǔn)確率,更接近實(shí)際情況。在算法實(shí)現(xiàn)過(guò)程中,充分?jǐn)M合決策樹(shù)以信息熵為分類標(biāo)準(zhǔn),通過(guò)遞歸分層逐步降低數(shù)據(jù)的混沌程度,逐步提高數(shù)據(jù)的“純度”。在此基礎(chǔ)上,C4.5 計(jì)算了互信息的比例, 消除了ID3 算法在特征包含多個(gè)特征值時(shí)分塊過(guò)多對(duì)數(shù)據(jù)純度提高的影響。此時(shí),數(shù)據(jù)之間的不確定性逐漸減小,分類結(jié)果的決定因素也變得清晰,從而將多個(gè)數(shù)據(jù)劃分為一個(gè)類別。

3 總結(jié)與展望

本文主要通過(guò)對(duì)決策樹(shù)算法中的ID3 算法和C4.5 算法的研究分析, 掌握數(shù)據(jù)挖掘的基本概念, 來(lái)探索決策樹(shù)算法的原理。決策樹(shù)算法通過(guò)構(gòu)造樹(shù)的模型對(duì)數(shù)據(jù)進(jìn)行分類歸納,分析得到所需信息。這種算法的核心是怎樣去構(gòu)造小規(guī)模、高精度的樹(shù)。在對(duì)決策樹(shù)算法進(jìn)行實(shí)際應(yīng)用后,本人受益匪淺,有了數(shù)據(jù)挖掘研究思維和決策樹(shù)模型概念。