馬 強(qiáng)

（長治學(xué)院計(jì)算機(jī)系，山西長治，046011）

?

數(shù)據(jù)挖掘中決策樹算法的優(yōu)化應(yīng)用研究

馬 強(qiáng)

（長治學(xué)院計(jì)算機(jī)系，山西長治，046011）

摘要：決策樹算法是數(shù)據(jù)挖掘中一種非常重要的分類方法。決策樹具有屬性結(jié)構(gòu)和較好的分類預(yù)測能力，提供了基本的提取決策規(guī)則。本文闡述了決策樹算法的基本思想，并分析了決策樹算法運(yùn)用中會遇到的一些問題，并針對性的提出一些建議。

關(guān)鍵詞：數(shù)據(jù)挖掘；決策樹算法；應(yīng)用研究

0　引言

數(shù)據(jù)挖掘指的就是利用一些分析工具從大量的、不完全的、模糊的、有噪音的、隨機(jī)的數(shù)據(jù)中，提取出隱藏在其中的、實(shí)現(xiàn)未知并具有價值信息的過程。數(shù)據(jù)挖掘需要實(shí)現(xiàn)建立數(shù)據(jù)關(guān)系模型，對數(shù)據(jù)進(jìn)行分析預(yù)測。在數(shù)據(jù)挖掘中，分類是一項(xiàng)非常重要的任務(wù)，分類用于預(yù)測，預(yù)測的目的就是從歷史數(shù)據(jù)中自動推導(dǎo)出數(shù)據(jù)的描述趨勢，從而對未來的數(shù)據(jù)進(jìn)行預(yù)測。決策樹算法是數(shù)據(jù)挖掘中最常用的方法，其作用于分類階段，可以直接體現(xiàn)數(shù)據(jù)特點(diǎn)，分析預(yù)測數(shù)據(jù)，并能方便提取決策規(guī)則。

1　決策樹的概念

決策樹分類算法是數(shù)據(jù)挖掘中用到比較廣并且非常有效的分類方法，包括ID3和C4.5算法，其采用“自上而下、分類治之”的方法，通過一些無序、無規(guī)則的事例推測出決策樹的分類規(guī)則，可以實(shí)現(xiàn)對位置數(shù)據(jù)的分類、預(yù)測和數(shù)據(jù)預(yù)處理。決策樹方法以分析和歸納利用信息理論為原則，采用流程圖式樹結(jié)構(gòu)，分為根節(jié)點(diǎn)和葉點(diǎn)，最頂層根節(jié)點(diǎn)包含信息內(nèi)容最大，每一分支葉點(diǎn)是代表樣品類別或類分布。決策樹一般分為構(gòu)成和剪枝兩個步驟，如圖1所示：

圖1　決策樹工作原理流程圖

2　常見的決策樹算法分析

2.1ID3算法：ID3算法是一種基于信息熵的決策樹學(xué)習(xí)算法，其中引入了Shannon信息論，將信息熵作為選擇測試的標(biāo)準(zhǔn)，對實(shí)例集進(jìn)行分類，同時構(gòu)造決策樹來預(yù)測如何由測試屬性來對整個實(shí)例空間進(jìn)行劃分。在ID3算法中的每一個循環(huán)過程都是對訓(xùn)練集進(jìn)行查詢來確定屬性的信息增益。構(gòu)造決策樹時采用自頂向下的遞歸方式，將大量數(shù)據(jù)通過歸納、概括、提煉出事物的屬性規(guī)律后，以決策樹的方式表示出來，如下：

總的來說，在處理大規(guī)模學(xué)習(xí)問題時，選擇理論清晰、方法簡單的ID3算法，不失為一種知識獲取的有用工具。

2.2C4.5算法：C4.5決策樹算法是D3 算法的擴(kuò)展，通過信息熵方法遞歸形成決策樹，具有更加強(qiáng)的連續(xù)屬性，具有適用廣、高效率的特點(diǎn)。對比兩種算法的不同之處，一方面表現(xiàn)在C4.5的測試屬性技術(shù)是信息增益率（信息增益率=信息增益/分割信息量），而ID3算法采用基于信息增益的方法選擇測試屬性。另一方面表現(xiàn)是C4.5算法不需要獨(dú)立測試樣本集，提高效率，可以直接處理連續(xù)屬性和屬性空缺的樣本，這樣的產(chǎn)生決策樹分枝減少，而ID3算法的連續(xù)屬性處理是離散化的。例：

3　決策樹算法中存在的問題

3.1數(shù)據(jù)過分相似問題。決策樹算法運(yùn)算過程中產(chǎn)生數(shù)據(jù)過分相似的原因主要有兩點(diǎn)：（1）決策樹算法在選擇物體屬性時不能進(jìn)行分辨，容易選到一些與自身種類不相關(guān)的屬性，主要是因?yàn)槭挛锉旧淼膶傩蕴?；?）決策樹在運(yùn)算過程中根據(jù)自己的偏好選擇各自屬性，因此可能就會選擇到和種類無關(guān)的屬性，漏選真正需要的屬性。采用決策樹修剪法把不相關(guān)的屬性刪除，從而避免選到不相關(guān)屬性。決策樹生長完成后進(jìn)行剪枝的方法稱為后剪枝法，而決策樹生長完成前進(jìn)行剪枝方法稱為前剪修法。

3.2取值問題。構(gòu)建一個好的決策樹最主要的難點(diǎn)在于對分支取值進(jìn)行良好取值。決策樹分支建立需要根據(jù)字段對不同取值的記錄，在每個子集分支下層反復(fù)建立分支和節(jié)葉點(diǎn)，對不同取值的分枝階段進(jìn)行選擇。子集記錄的劃分值不同受到不同的字段值選擇的影響，進(jìn)而影響到信息的規(guī)則尋找的優(yōu)劣。假設(shè)依據(jù)一個較差的取值來構(gòu)建決策樹分支，即影響決策樹的生產(chǎn)速度，也容易出現(xiàn)結(jié)構(gòu)性差和分支過細(xì)等不良現(xiàn)象。

4　決策樹分類算法的優(yōu)化

通過分析決策樹的兩種算法ID3算法與C4.5算法的不同，以及決策樹算法中存在的一些問題，主要提出從屬性選擇、連續(xù)屬性離散化、抽樣方法、綜合其他算法的幾方面改進(jìn)決策樹分類算法。

4.1屬性選擇。為了有效避免噪音和干擾屬性對數(shù)據(jù)分類的影響，需要在建立決策樹之前對屬性重要性進(jìn)行排序，并且對其重要屬性要通過神經(jīng)網(wǎng)絡(luò)技術(shù)進(jìn)行訓(xùn)練和檢驗(yàn)來預(yù)測其精度。按照屬性的重要次序依次向兩端加減一個鄰近的屬性并進(jìn)行訓(xùn)練和檢驗(yàn)比較。一直反復(fù)進(jìn)行，直到找的分類效果最佳的n個屬性為止。

4.2連續(xù)屬性離散化。離散化是分類過程中處理連續(xù)性的一種有效方法，并且離散化的效率會直接影響到后面機(jī)器學(xué)習(xí)算法的效率和性能。像ID3算法只能夠處理離散屬性，而C4.5雖然能夠處理連續(xù)屬性，但是其離散化也是系統(tǒng)集成的一個重要步驟。離散化方法可以分為兩類：全局離散和局部離散。全局離散需要考慮到屬性之間的相互作用，局部離散方法限制一次只能對一個屬性進(jìn)行離散。局部離散相對于全部離散要簡單。由于全部離散要同時對所有的屬性進(jìn)行離散，所以計(jì)算代價要高于局部離散。

4.3抽樣方法。提高決策樹的效率可以采用抽樣方法。用抽樣方法分析決策樹構(gòu)建過程中產(chǎn)生的數(shù)據(jù)集，分析產(chǎn)生節(jié)點(diǎn)過程。抽樣分析整個數(shù)據(jù)庫中的子集，再利用抽取的子集樣本構(gòu)建決策樹來分析未知樣本類別或分類規(guī)制。也有其不好的一點(diǎn)就是容易把數(shù)據(jù)中一些非常有價值的數(shù)據(jù)模型漏掉。

4.4綜合其他算法。通過將遺傳算法與決策樹算法結(jié)合能夠得到一個精確度更高的決策樹，采用這種方式構(gòu)建決策樹分為兩種方法：一種是對決策樹編碼。以CALTROT算法為例構(gòu)建一個二叉決策樹，這種基于遺傳算法構(gòu)建決策樹中其染色體就是決策樹，其中又包含眾多的二叉決策樹，都由兩個分支和一個節(jié)點(diǎn)組成，通過改變?nèi)旧w的排列順序，再選擇，加之變異和交叉構(gòu)建一棵最優(yōu)的決策樹。另一種方法是對決策樹不編碼，對決策樹直接進(jìn)行變異、操作、交叉和選擇，將遺傳算法、決策樹算法和抽樣算法相互結(jié)合，彌補(bǔ)子集方法上的缺陷。

5　結(jié)束語

隨著信息技術(shù)的不斷發(fā)展，數(shù)據(jù)挖掘分類問題和算法研究成為熱點(diǎn)，本文對數(shù)據(jù)挖掘中決策樹算法的應(yīng)用進(jìn)行了優(yōu)化研究。通過分析決策樹常見的兩種算法以及決策樹算法中存在的問題，針對實(shí)際問題，主要提出從屬性選擇、連續(xù)屬性離散化、抽樣方法、綜合其他算法的幾方面改進(jìn)決策樹分類算法，提高決策樹算法的效率和性能。

參考文獻(xiàn)

[1]唐華松,姚耀文.數(shù)據(jù)挖掘中決策樹算法的探討[J].計(jì)算機(jī)應(yīng)用研究，2001（8）：18-19+22

[2]王黎明.決策樹學(xué)習(xí)及其剪枝算法研究[D].武漢:武漢理工大學(xué). 2007

[3]林震,王威.基于決策樹的數(shù)據(jù)挖掘算法優(yōu)化研究[J]. 現(xiàn)代計(jì)算機(jī)，2012（28）：11-14

作者簡介

馬強(qiáng)，1980.9，男，長治學(xué)院計(jì)算機(jī)系，講師，碩士，研究方向：數(shù)據(jù)挖掘、數(shù)據(jù)庫、軟件設(shè)計(jì)等。

項(xiàng)目資助：長治學(xué)院教學(xué)研究項(xiàng)目（JY201418）。

Application research on optimization of decision tree in data mining algorithm

Ma Qiang
（Department of Computer Science, Changzhi University，Changzhi,Shanxi，046011）

Abstract：This paper describes the basic idea of the decision tree algorithm,and analyzes some of the problems encountered in the application of the decision tree algorithm,and puts forward some suggestions for the.

Keywords：data mining;The decision tree algorithm;Application research on