蒲海坤＊ 高 鑫 桑 鑫

（西京學院 信息工程學院，陜西 西安 710123）

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

1 知識挖掘概念與步驟

數(shù)據(jù)挖掘是一個對數(shù)據(jù)處理分析的過程，對海量數(shù)據(jù)進行分析處理以挖掘探索有價值知識的過程，簡單說來就是從大量知識中找到有價值的、自己所需要的知識。

知識挖掘一般是由以下幾個步驟構成：

（1）數(shù)據(jù)清洗：用來清洗和剔除不相關的數(shù)據(jù)知識。

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

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

（4）數(shù)據(jù)挖掘：主要作用是利用先進智能的方法來挖掘數(shù)據(jù)或將數(shù)據(jù)知識進行規(guī)律歸納，是整個過程中的基本步驟。

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

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

決策樹算法綜述：

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

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

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

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

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

2.1 ID3 決策樹構建

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

構建決策樹根結點所用到的信息：分類信息熵如表2 所示。

表2 分類信息熵

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

構建好決策樹,我們就可以利用決策樹進行預測：

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

2.2 C4.5 決策樹構建

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

2.3 實驗結果分析

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

圖1 C4.5 算法結果圖

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

3 總結與展望

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