朱 琳，楊 楊

(1. 北京郵電大學，北京 100876；2. 北京郵電大學，北京 100876)

ID3算法的優(yōu)化

朱 琳1，楊 楊2

(1. 北京郵電大學，北京 100876；2. 北京郵電大學，北京 100876)

隨著硬件設備的普及，促使信息技術和移動互聯(lián)網(wǎng)的快速發(fā)展，人們已經(jīng)告別了信息匱乏的時期，而進入到了信息過載的時期。人們試圖用搜索功能搜索出自己想要的信息，如今已是非常困難，怎樣從海量的數(shù)據(jù)中篩選出有價值的信息是信息提供者和信息需求者都要面對的挑戰(zhàn)。本文對數(shù)據(jù)分類中的ID3算法的基本概念和原理以及其構造過程進行了詳細闡述，針對ID3算法傾向于選擇取值較多的屬性的缺點，引進屬性閾值和信息增益率兩個概念。彌補ID3算法屬性選擇標準的不足，來實現(xiàn)新的屬性選擇標準，對原有ID3算法進行改進。通過實驗對改進前后的算法進行了比較，實驗表明，改進后的算法提高了分類準確度。

數(shù)據(jù)挖掘；ID3算法；信息增益；信息增益率；分類

0 引言

在解決分類問題時，使用次數(shù)最多、范圍最廣的算法是決策樹算法。它主要是用來解決離散化數(shù)據(jù)值的問題，并對錯誤數(shù)據(jù)有很好的健壯性。基于構建決策樹的算法是一種使用“自頂向下，分而治之”策略進行分枝的歸納算法，整個訓練樣本數(shù)據(jù)集被分割成一個個互斥的子集，通過這種方法生成分類器，即決策樹模型，利用生成的分類器對未分類的數(shù)據(jù)進行分類并提取分類規(guī)則。由此可知，使用決策樹的方法來進行分類時，核心是如何構建一棵可使分類結(jié)果最準確的決策樹。構建好決策樹后，就可以把數(shù)據(jù)庫中的未分類數(shù)據(jù)通過決策樹模型進行分類。因此，對決策樹算法的深入研究，就是研究如何建立一棵具有最小深度且有最大分類精確度的決策樹。

研究者們在構建決策樹時提出了很多構建算法，ID3算法是最常見的決策樹構建算法。該算法的核心是通過計算訓練集中每個屬性的信息增益，由信息增益作為每次選擇樹結(jié)點的選擇標準，確保構建好的決策樹中每個結(jié)點上都是最合適的屬性。這種選擇信息增益最大的屬性作為分裂屬性的選擇方式，可以保證每次分裂后，分裂結(jié)點的子結(jié)點的信息增益之和都是最低的，這是一種通過信息量的貢獻度來自頂而下分裂的過程。所以這種算法的核心思想就在于應用信息論中“熵”這個概念，將信息增益最大的那個決策屬性當做決策的結(jié)點屬性，根據(jù)不同的屬性取值來擴大它的分支，對每一個分支的樣本子集遞歸調(diào)用[1]。

1 ID3算法

ID3算法是一個典型的決策樹學習算法，其核心是在決策樹的各級結(jié)點上，使用信息增益方法作為屬性選擇標準，來幫助確定生成每個結(jié)點時所應采用的合適屬性。這樣就可以選擇具有最高信息增益的屬性作為當前結(jié)點的測試屬性，以便使用該屬性所劃分獲得的訓練樣本子集進行分類所需信息最小。

分裂屬性的選擇標準是選取信息增益最大的的屬性，然后建立決策樹。則選擇標準中的信息增益的計算方式如下[2]：

設給定的訓練數(shù)據(jù)集的大小為m，集合S＝A1*是n維有窮向量空間，而且每個向量空間又有子空間分別為維。

設s1,s2,…sr是向量空間S的子集，其大小分別為且有。則一棵決策樹能正確判斷所需的信息熵（信息期望量）為：

則以屬性Ak為根所需要的信息熵為：

以屬性Ak為根的信息增益是：

ID3選擇使信息增益值最大的屬性Ak作為分裂結(jié)點的原則進行決策樹構建，即選擇每次計算的信息增益最大的屬性作為決策樹的結(jié)點，并對屬性的每個屬性值建立分支，根據(jù)這種策略對訓練數(shù)據(jù)樣本集進行分類。

由此可見，信息增益Gain(A)的值隨著E(A)的值變化而變化，信息增益的值與E(A)值呈負相關關系，即信息增益的值隨著信息熵的增大而減小。因此可以看出如果分裂屬性A對信息增益的貢獻最大，則通過信息增益的標準來選取分裂屬性，可以將分類的不確定性降到最小。

ID3算法是利用信息熵的知識來選擇重要的特征的，并且其基礎理論也相對的更加簡單清楚。ID3算法的優(yōu)點主要是以下幾點[3]：

（1）ID3算法所使用的是訓練樣本數(shù)據(jù)集中的所有數(shù)據(jù)，其目的在于能更好的挖掘出整個訓練數(shù)據(jù)集中的分類特征，進而達到減少噪音數(shù)據(jù)所帶來的敏感度的問題。換句話說，它能夠通過改進算法這種方式來以一種更簡單的方法消除噪音數(shù)據(jù)所帶來的負面影響。

（2）ID3算法無需遍歷整個數(shù)據(jù)集，它因為采用自頂而下的搜索策略，所以可以在一小部分的范圍內(nèi)進行搜索。也正因為這樣的搜索策略，算法可以用較少的測試次數(shù)使分類的速度變快，因為算法運行時間是跟訓練樣本集的記錄數(shù)、屬性的數(shù)目以及屬性的可能取值數(shù)目呈正相關的。

（3）ID3是一種在信息論基礎上的決策樹算法，所以它才可以生成出最少階段個數(shù)的決策樹。

同時，ID3算法也存在著如下的幾個缺點[4]：

（1）ID3算法在屬性之間的關聯(lián)性這個層面上相對薄弱，強調(diào)的程度非常不夠。它所形成的這個決策樹中，每一個結(jié)點都僅僅含有唯一的屬性，屬性之間缺乏相互間的聯(lián)系。雖然它可以將多個屬性集中在這個完整的決策樹中，但是卻不能將他們關聯(lián)起來，從而導致看起來每個結(jié)點之間的聯(lián)系都是很雜亂而松散的。

（2）D3算法雖然可以很好的處理離散型屬性，然而它卻難以處理連續(xù)型屬性。只有通過預處理將連續(xù)型屬性離散化，才可以對其進行處理。

（3）ID3算法比較容易產(chǎn)生過度擬合的現(xiàn)象，因為它對由決策屬性值取錯和所給類別錯誤的樣本產(chǎn)生的噪音數(shù)據(jù)比較敏感。

（4）ID3算法屬于貪婪算法。每當樣本的集合產(chǎn)生了變化時，都會導致各個決策屬性的信息增益跟著變化。所以每次實例的增加都不得不拋棄之前構建好的決策樹，創(chuàng)建一個全新的決策樹。所以并不適合增量式的學習，因為這會加大無謂的開銷[5]。

2 算法改進

ID3算法的核心思想是選擇信息增益最大的屬性作為分裂屬性選擇的標準，因此該算法更偏向于選擇值較多的屬性，但忽略了屬性值多并不一定是關鍵屬性的問題。本文主要針對ID3算法屬性多值偏向性的問題進行改進，通過信息增益率和信息增益共同建立決策樹。但是，這樣可能會出現(xiàn)過度補償?shù)那闆r，利用決策樹的分類確定參數(shù)值，并二次建立決策樹。從而更好地改善該算法的多值偏向性問題[6]。

與C4.5算法[7]不同之處就在于，本文中改進后的ID3算法并不是用信息增益率取代信息增益，而是將兩個參數(shù)共同作為選擇分裂屬性時的標準，這樣能夠在一定程度上避免對多值偏向性平衡過度的情況[8]。

在ID3算法的基礎上，提出信息增益率，定義信息增益率的概念后，把信息增益率和信息增益共同作為選擇分裂屬性時的選擇標準。其中，信息增益率的計算公式如下：

由公式可以看出，信息增益率是比值，可能會得到近似為零的結(jié)果，這種情況發(fā)生的原因是過度補償，所以有必要引入閾值r。在集合S中存在n個屬性，閾值r可定義為全部屬性信息熵的均值，即：

該改進算法思路如下：

利用公式（2）計算每個屬性的信息熵；

（1）根據(jù)信息熵計算該次生成決策樹算法中的閾值r，閾值求法參見公式（5）；

（2）計算假設某屬性為分裂屬性時的信息增益，遍歷每一個未被選中的屬性；

（3）若計算得出某屬性的信息增益比閾值r大，則通過信息增益標準選擇，即分裂結(jié)點的選擇標準是選取信息增益最大的結(jié)點；若信息增益比閾值r小，則通過信息增益率標準選擇，即選擇信息增益率最大的結(jié)點作為分裂結(jié)點；

（4）若還有未被選中的結(jié)點，則返回步驟（1）繼續(xù)計算，直到所有結(jié)點均被選中。

3 仿真實驗與結(jié)論

為了證明該算法的正確性和高效性，本文中使用UCI提供的數(shù)據(jù)集進行對比仿真實驗。將數(shù)據(jù)集分為兩部分，分別作為訓練集和測試集，圖3-4為ID3算法和改進算法第一次生成決策樹的精確度對比圖，對比參數(shù)精確度是指使用構建的決策樹分類后的測試集與原數(shù)據(jù)集的一致的數(shù)目與測試集總記錄數(shù)的比值。

在圖1中，橫坐標為7種數(shù)據(jù)集，分別為UCI數(shù)據(jù)集中Haberman's Survival、Iris、Adult、Acute、Balance、Car、Abalone，縱坐標為算法精確度?？梢园l(fā)現(xiàn)，對于不同規(guī)模的數(shù)據(jù)集，改進算法第一次生成的決策樹的精度在84.7%-91.4%間浮動，而傳統(tǒng)ID3算法的精確度大約在76.9%～86.3%左右，與原ID3算法相比改進后的算法在分類準確度上有5%左右的小幅度提升。因為新的ID3算法在第一次生成決策樹時平衡了傳統(tǒng)算法多值偏向性的缺點，由此可得出新的算法在多值偏向性的平衡上有顯著的效果。

圖1 ID3算法和改進算法精度對比Fig.1 Comparison of ID3 Algorithm and Improved Algorithm

圖2 和圖3為在不同樣本數(shù)量的數(shù)據(jù)集下，原ID3算法與改進算法在精確度和時間上的比較。

圖2 不同樣本數(shù)量下算法精確度比較Fig.2 Comparison of algorithm accuracy under different sample sizes

圖3 不同樣本數(shù)量下算法耗時比較Fig.3 Time-consuming Comparison of Different Samples

4 結(jié)論

ID3算法是決策樹算法中最典型的算法，有大量學者對其進行了研究分析，本文在前人的研究下，對1D3算法及其改進算法進行了詳細介紹, 首先對ID3算法的基本原理進行闡述，針對該算法最大的不足即屬性的多值偏向問題，通過信息增益率的引入，在一定程度上克服了這個主要缺陷。實驗結(jié)果表明：新算法克服了ID3算法傾向于取值較多的屬性的缺點，比ID3算法在分類準確度上有更好的分類效果。

[1] 王永梅, 胡學鋼. 決策樹中ID3算法的研究[J]. 安徽大學學報(自然科學版), 2011, 03: 71-75.

[2] 王小巍, 蔣玉明. 決策樹ID3算法的分析與改進[J]. 計算機工程與設計, 2011, 09: 3069-3072+3076.

[3] 劉祺. 決策樹ID3算法的改進研究[D]. 哈爾濱工程大學, 2009.

[4] 黃宇達, 范太華, 王迤冉. 決策樹ID3算法的一種改進算法[J]. 電腦知識與技術, 2012, 01: 96-98.

[5] 馬莉雅. 基于決策樹、邏輯回歸和改進神經(jīng)網(wǎng)絡的幾種慢性病的危險因素分析研究[J]. 軟件, 2014, 35(12): 58-65.

[6] 王勝. 基于決策樹ID3算法研究與實現(xiàn)[J]. 齊齊哈爾大學學報(自然科學版), 2012, 03: 64-68.

[7] 陳英, 馬仲兵, 黃敏. 優(yōu)化的C4.5 決策樹算法[J]. 軟件, 2013, 34(2): 61-64.

[8] 史尤昭. 數(shù)據(jù)挖掘技術研究與應用[J]. 軟件, 2015, 36(11): 38-42.

Improvement of Decision Tree ID3 Algorithm

ZHU Lin1, YANG Yang2
(1. Beijing University of Posts and Telecommunications, Beijing 100876, China; 2. Beijing University of Posts and Telecommunications, Beijing 100876, China)

With the popularization of hardware equipment, prompting the rapid development of information technology and mobile Internet, people have already bid farewell to the period of lack of information, and entered the period of information overload. People try to use the search function to search out the information they want, and now it is very difficult, how to filter out from the mass of valuable information is information providers and information needs of those who have to face the challenge. In this paper, the basic concept and principle of ID3 algorithm in data classification and its construction process are expounded. In view of the shortcomings of ID3 algorithm which tend to choose more attributes, the two concepts of attribute threshold and information gain rate are introduced. Make up for the deficiency of attribute selection standard of ID3 algorithm to realize the new attribute selection standard and improve the original ID3 algorithm. Experiments show that the improved algorithm improves the classification accuracy.

Data mining; ID3 Algorithm; Information gain; Information gain rate; classification

TP311.13

A

10.3969/j.issn.1003-6970.2016.12.020

朱琳(1992-)，女，碩士，數(shù)據(jù)挖掘。

楊楊，副教授，數(shù)據(jù)挖掘、網(wǎng)絡管理。

本文著錄格式：朱琳，楊楊. ID3算法的優(yōu)化[J]. 軟件，2016，37（12）：89-92