基于訓(xùn)練集局部加權(quán)的C4.5算法改進研究

張揚武

摘要：C4.5算法采用信息增益率來構(gòu)造決策樹，克服了選擇較多值的屬性的趨向，具有處理連續(xù)屬性的能力。在處理大數(shù)據(jù)集時，表現(xiàn)出效率較低，忽略樣本集中的不同樣本與測試數(shù)據(jù)的距離差異。該文提出了一種基于訓(xùn)練集局部加權(quán)的C4.5改進算法，根據(jù)歐式距離或漢明距離來定義樣本的權(quán)值，將權(quán)值更新到訓(xùn)練集中，重新計算的信息增益率反映了訓(xùn)練樣本的差異對測試數(shù)據(jù)的影響，并且在處理大數(shù)據(jù)集時，根據(jù)權(quán)值排序和設(shè)置的閾值簡化數(shù)據(jù)集，降低了計算復(fù)雜度，提高效率。

關(guān)鍵詞：C4.5；信息增益比；局部加權(quán)；數(shù)據(jù)集；鄰近距離

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2016）16-0202-03

Abstract： C4.5 algorithm uses information gain-ratio to construct a decision tree， and overcome the tendency to select the attribute onmore values， with the ability to handle continuous attributes.But it showless efficient when dealing with large data sets and ignoring the differences of distance from the sample set and test data set.Based on training set weighted locally， This paper proposes a suite of algorithm of improvement for C4.5algorithm.The sample weights ，which are defined according to the Euclidean distance or Hamming distance， update to the training set.On this basis， information gain-ratio which is recalculated reflects the impact of the differences of distance from the sample set and test data set.Therefore，the proposed algorithm can reduces the computational complexity and improves efficiencywhen dealing with large data sets，using the simplifiedsample set based onweight sorting and the threshold.

Key words：C4.5； information gain-ratio； weighted locally； data set； near distance

1 概述

ID3算法根據(jù)計算信息增益，選擇有較高信息增益的屬性進行節(jié)點分裂，對于離散屬性集Values來說，增加一個ID屬性，每條屬性都有不同的ID，計算信息增益時，屬性ID產(chǎn)生的信息增益是最大的。如果選擇屬性ID分裂節(jié)點，將為每條數(shù)據(jù)產(chǎn)生一個分支，這是沒有意義的。C4.5算法是ID3的改進算法，其核心思想是根據(jù)屬性的信息增益率（Gain-ratio）代替信息增益（Information Gain）來選擇屬性分裂節(jié)點來構(gòu)造決策樹，信息增益率由選取屬性的信息增益和按照選取的屬性劃分樣本集的均勻性共同決定，克服了ID3算法趨于選擇較多值的屬性的缺點，通過斷點來處理連續(xù)數(shù)據(jù)，在決策樹構(gòu)造過程中進行剪枝來解決過擬合問題，產(chǎn)生的規(guī)則易于理解[1]。

在實際應(yīng)用中，樣本集的分布情況會影響分類器的分類效果。有的樣本集類別不均衡，存在大類和小類，有些屬性對大類分類效果較好，有些屬性對小類分類效果較好[2]。有的樣本集屬性不均衡，有的屬性取值較多，而有的屬性值取值較少。因此，分類器的好壞與訓(xùn)練集中的樣本數(shù)據(jù)質(zhì)量密切相關(guān)。數(shù)據(jù)集的選擇應(yīng)該分布較均衡，盡量選擇具有代表性的數(shù)據(jù)。數(shù)據(jù)集中的不同樣本對于測試數(shù)據(jù)的作用是不一樣，例如，對于用來預(yù)測2015年房價的數(shù)據(jù)集，2014年的樣本顯然比2004年的樣本更有用[3]。 C4.5算法基于統(tǒng)計學(xué)規(guī)律，根據(jù)信息熵來選擇屬性分裂節(jié)點，考慮的是靜態(tài)的整體性，不是動態(tài)的整體性，它沒有考慮測試集和訓(xùn)練集之間的距離關(guān)系。在K最近鄰（k-Nearest Neighbor，KNN）算法中，如果一個測試數(shù)據(jù)在特征空間中的k個最相似的樣本中的大多數(shù)屬于某一個類別，則該樣本也屬于這個類別。這說明與測試數(shù)據(jù)鄰近的樣本對分類結(jié)果影響較大，在C4.5算法中，訓(xùn)練集中樣本被同等對待，其差異并沒有反映到?jīng)Q策樹的構(gòu)造過程中。因此，基于C4.5的改進算法在計算信息增益率時增加了樣本的權(quán)值參數(shù)，使樣本空間分布隨測試數(shù)據(jù)的不同而發(fā)生變化，反映了訓(xùn)練集中的不同樣本對待預(yù)測的測試數(shù)據(jù)影響也不相同，與測試數(shù)據(jù)距離較近的訓(xùn)練樣本對預(yù)測結(jié)果影響較大，而遠離測試數(shù)據(jù)的樣本對預(yù)測結(jié)果影響較小[4]。

2 一種改進的C4.5算法

2.1 距離的衡量

3 結(jié)語

C4.5算法在構(gòu)造決策樹過程中，需要多次對數(shù)據(jù)集進行掃描和排序，導(dǎo)致效率較低。如果考慮訓(xùn)練集較大，受到內(nèi)存容量限制無法裝入到內(nèi)存時，程序?qū)o法運行。因此，C4.5算法適用于能夠駐留內(nèi)存的數(shù)據(jù)集使用。本文提出了一種基于訓(xùn)練集局部加權(quán)的信息增益率的計算方法，根據(jù)測試數(shù)據(jù)與訓(xùn)練樣本之間的距離來定義樣本的權(quán)值，更新的訓(xùn)練集導(dǎo)致信息增益率計算發(fā)生改變，反映了較近的訓(xùn)練樣本對分類的重要影響。并且在處理大數(shù)據(jù)集時，根據(jù)權(quán)值排序調(diào)整數(shù)據(jù)集大小，降低了計算復(fù)雜度和樹的復(fù)雜度。

參考文獻：

[1] Witten IH，F(xiàn)rank E .Data Mining：Practical Machine Learning Toolsand Techniques[M].2nd ed.， San Francisco ：Elsevier Inc.，2005.

[2] AlmuallimH .On handling tree-structured attributes[C]// AshburnerM . Proc of the 12th IntConf on Machine Learning. San Fransisco ：Morgan Kaufmann ， 1995. 12-20.

[3] Wu Xindong，Kumar V，Quinlan J .Top 10 algorithms in data mining[J].Knowledge and Information Systems， 2008，14（1）：1-37.

[4] Moore AW， Zuev D， Crogan M. Discriminators for use in flow—based classification[R]. Technical Report， RR-05-13，London ：Queen Mary University of London，2005.

[5] Pawlak Z D，Quinlan J .Rough set theory and itsapplicationto data analysis[J].Cybernetics and Systems，1998，29（9）：611-668.

[6] Ghosh A K， Chaudhuri P，Murthy C A. Multiscale classification using nearest neighbor density estimates[J]. IEEE Transactionson Systems，Man，and Cybernetics，PartB：Cybernetics， 2006，36（5）：1139-1148.