基于K-近鄰的局部懶惰式決策樹分類模型

盧潤彩,龐 超,時志素

(1.石家莊信息工程職業學院,河北石家莊050035;2.石家莊學院,河北石家莊050000)

0 引言

分類是數據挖掘和機器學習的一項重要基本任務。一般地,分類是依據某種分類模型,在具有類標的數據集合上學習出一個分類函數,即通常所說的分類器。該函數能夠給由屬性值序偶集所描述的待分類實例指派一個最適合的類標,從而可以應用于數據分類和預測[1]。研究者們已經提出了許多分類方法和技術,例如,樸素貝葉斯方法[1]、貝葉斯網絡[1]、決策樹[2,3]、決策表[3]、神經網絡、K-近鄰[4]以及支持向量機等。這些方法從學習策略上可以分為基于懶惰式學習策略的分類方法和基于急切式學習策略的分類方法。

其中基于懶惰式學習策略的分類方法在給測試實例分類時才去訪問訓練實例集合來做出預測,在分類精確度上有明顯的優勢。本文所提出的Local-LDtree分類模型屬于基于懶惰式學習策略的分類方法,在給測試實例分類時,首先根據K-近鄰算法[4]的思想選擇出與該測試實例最近的部分訓練實例,然后利用Lazy DT[5]模型在局部訓練實例的集合上來給測試實例分類。Local-LDtree分類模型在大多數數據集合上取得了較高的分類精確度。

1 Local-LDtree的關鍵問題

Local-LDtree分類模型需要解決2個關鍵問題：①根據K-近鄰算法的思想,選擇與測試實例最近的部分訓練實例形成局部訓練實例集合時,如何進行實例間距離的計算;②在形成局部訓練實例集合后,Local-LDtree分類模型采用什么算法在其上對測試實例進行分類。

1.1 實例間距離的計算

K-近鄰算法是基于實例的學習方法中的一種。當給特定測試實例分類時,K-近鄰算法計算該測試實例到訓練實例集合中的每一個實例的距離,選擇距離測試實例最近的K個訓練實例,然后將這K個訓練實例的最普遍的類值作為測試實例的類值。K-近鄰算法的分類精確度較高,但是如果能更有效地確定K個訓練實例的最普遍的類值,就會得到更高的分類精確度。

利用K-近鄰算法的思想建立Local-LDtree分類模型時,首先要解決實例間距離的計算問題。本文采用歐氏距離來定義實例間的距離。假定所有的實例對應于n維歐氏空間 ?n中的點。任意的實例 x表示為下面的特征向量：

式中,ar(x)為實例x的第r個屬性值。那么2個實例xi和xj間的距離定義為：

利用歐氏距離來定義實例間的距離比較容易理解,在實驗中也取得了較好的效果。

1.2 局部分類算法的選擇——Lazy DT

Local-LDtree模型在局部訓練實例集合上采用懶惰式決策樹算法算法(Lazy DT)。Lazy DT分類算法像許多懶惰式算法一樣,推理過程的第一部分(建立分類器階段)是不存在的,所有的工作都在給一個特定實例分類的過程中完成。

Lazy DT分類算法從概念上為每一個待分類實例建立一棵最優的樹。建樹過程中選擇分裂屬性時,采用了信息增益的標準,選擇信息增益值最大的屬性作為最佳分裂屬性。

Lazy DT分類算法為一個給定測試實例分類的過程是：首先,判斷訓練集合中的所有實例是否具有相同的類值,如是則測試實例的類屬性值就是這個相同的類值;如不是,判斷訓練集合中的所有實例是否具有相同的屬性值,如果是,則測試實例的類屬性值為訓練實例中占最大比率的類屬性值;如上述2種情況都沒有滿足,則選擇一個信息增益最大的屬性X作為根節點,將所有X屬性值與測試實例的X屬性值相等的訓練實例值劃分為一個子集合,將此子集合作為下一次選擇分裂屬性的訓練集合,來建立為測試實例分類的路徑。重復以上的過程,直到得到測試實例的類屬性值。

Lazy DT實際上只需建立一條針對測試實例的路徑和一個使算法變快的緩沖表,在小的數據集合上,分類精確度較高。可以應用于局部訓練實例集合來給測試實例確定最合適的類標。

2 Local-LDtree分類模型

Local-LDtree分類模型是采用K-近鄰算法和Lazy DT分類算法相結合而建立新的分類模型,是基于懶惰式學習策略的分類方法。它給測試實例分類時,首先根據K-近鄰算法的思想選擇出與該測試實例最近的部分訓練實例,然后利用Lazy DT模型在局部訓練實例的集合上來給測試實例分類。Local-LDtree分類模型像許多懶惰式算法一樣,建立分類器的階段幾乎不做什么工作,大部分的工作都是在給一個特定的測試實例分類時進行的。其具體算法為：輸入：帶有類標的訓練數據集合 T,一個無類標的待分實例x;輸出：實例 x的類標：

①對于 T中每個訓練實例t,計算x到t的距離d(x,t);

②在T中選擇出與x距離最近的K個訓練實例,記為x1,x2,…,xk,將這K個訓練實例放入數據集合SUBT中;

③將SUBT和x作為Lazy DT的輸入,調用Lazy DT算法,得到 x的類標;

④返回利用Lazy DT得到的x的類標;

在Local-LDtree算法中,將K設置為可以取不同值的參數,例如可以取K=30或K=50等。K取不同的值會引起分類精確度的輕微變動。

算法的關鍵是：①選擇適當的距離計算標準,并針對測試用例計算它到每個訓練實例的距離;②在利用懶惰式決策樹在局部訓練實例上給測試實例x分類時,算法要正確在選擇分裂屬性和與x對應的訓練實例集合。

算法運行的過程中,實例間距離的計算一般不會出現異常情況,但調用Lazy DT算法在局部訓練集合上分類時會遇到一些特殊問題,如連續屬性的處理、缺損屬性的處理等。對于這些特殊問題在算法上進行了如下改進：

①連續型屬性的處理：對于連續型屬性不是進行預處理,而是采用2路分裂,將其進行離散化;

②缺損屬性值的處理：缺損屬性值的處理包括2種情況：測試實例具有缺損屬性值的處理和訓練實例具有缺損屬性值的處理。當給定測試實例具有缺損屬性值時,對所有訓練實例和測試都刪除該屬性,然后再進行針對給定測試實例進行分類。當訓練實例具有缺損屬性值時,將訓練實例缺損屬性值賦值為給定測試實例的該屬性值,這樣將不會影響分類時其他屬性對測試實例預測類標的支持;

③屬性最大信息增益為零時的處理：當屬性的最大信息增益為零時,選擇訓練集合中占最大比例的類屬性值作為給定測試實例的預測類屬性值;

④有未分類實例問題的處理：在Local-LDtree分類模型調用Lazy DT算法時,如果Lazy DT運行中當前層的訓練實例數為零,就會出現有未分類實例。此時將上一層的訓練集合中占最大比例的類屬性值近似地認為是測試實例的預測類屬性值即可消除未分類實例,同時還可提高分類器的分類精確度。

3 實驗數據及結果分析

本文采用來自UCI的數據集合,分別是音頻(Audio)、動物園(Zoo)、SF(Solarflare)、退火(Anneal)、平衡 度 (Balance-Scale)、超 聲心電 圖(Echocardiogram)、玻璃(Glass)、葡萄酒(Wine)、國際橡棋(Chess)、TTT(Tic-Tac-Toe)、鳶尾花(Iris)、SF-M(Solarflare-M)。表1描述了所使用的實驗數據的特征,分別列出了每個數據集合的實例個數、類屬性值個數、屬性個數以及屬性的取值特征(R為屬性值取數值型屬性值;N為屬性值取名稱型屬性值)。

表1 實驗數據描述

在所有的數據集合上評估分類器的性能所采用的方法都是10重交叉驗證的方法,運行分類器時采用的都是默認參數。

實驗的主要目的是對Local-LDtree、一般決策樹和樸素貝葉斯分類器在12個數據集合上比較它們的分類精確度。每個分類器采用10重交叉驗證估計分類器的精確度。每一個數據集合被分成10個沒有交叉數據的子集,所有子集的大小大致相同。分類器訓練和測試總共10次;每一次分類器使用去除一個子集的剩余數據作為訓練集,然后在被去除的子集上進行測試。把所有得到的精確度的平均值作為評估精確度,即10重交叉驗證精確度。對一般決策樹分類器,本文采用經典的C4.5算法,J48是在Weka實驗平臺下它的具體實現程序。在運行J48和樸素貝葉斯2種分類器時候,均采用其默認參數。

表2列出了樸素貝葉斯、J48和Local-LDtree這3種分類器在12個實驗數據上分類精確度的對比。其中,w代表在12個實驗數據上Local-LDtree的分類精確度比當前列對應的分類器的分類精確度高的實驗數據的數目;t代表Local-LDtree的分類精確度等于當前列對應的分類器的分類精確度的實驗數據的數目;l代表Local-LDtree的分類精確度比當前列對應的分類器的分類精確度低的實驗數據的數目。

表2 3種分類器的實驗結果比較

實驗結果可以看出,Local-LDtree在大部分實驗數據集上取得了最好的分類性能。在12個實驗數據集合上,Local-LDtree的平均分類精確度為88.007 6;樸素貝葉斯的平均分類精確度為81.723 1;J48的平均分類精確度為84.437 8。對音頻(Audio)、動物園(Zoo)、SF(Solarflare)、退火(Anneal)、葡萄酒(Wine)、玻璃(Glass)和 TTT(Tic-Tac-Toe)8個數據集合,Local-LDtree的分類精確度均比樸素貝葉斯分類器和J48高。

在本文的實驗中判斷是否采用Lazy DT方法進一步給測試實例分類時,所取的K值為30,即Local-LDtree的最近鄰居的數目取為30。實際上,K取值的變動均會引起Local-LDtree分類器分類精確度上下浮動。

4 結束語

Local-LDtree的實現中,采用的是歐式距離。研究中還有其他實例間距離計算方法,如可以將實例之間取不同屬性值的屬性的個數作為實例之間的距離等。是否采取其他計算距離的方法會得更好的分類效果,是需下一步研究的問題;Local-LDtree中調用Lazy DT算法時,采用信息增益標準來選擇最佳的分裂屬性,是否還有其他更好的分裂標準,需進一步進行研究;算法中K取不同的值會引起分類精確度的輕微變動,本文中實驗結果數據是K=30時的結果,K選擇什么值會使算法得到的分類精確度最優,也需要再加以研究。

[1]SIMOVICID A,SZY MON J.A Metric Approach to Buildingdecision Trees Based on Goodman-Kruskal Association Index[C].Australia ：PAKDD,2004：181-190.

[2]ATKESON C G,MOORE A W,SCHAAL S.Locally Weighted Learning for Control[J].Artificial Intelligence Review,1997,11(5)：75-113.

[3]AHA D W,LER D K,ALBERT M K.Instance-based Learning Algorithms[J].Machine Learning,1991,6(1)：37-66.

[4]CLEARY J G,TRIGG L E.An Instance-based Learner Using an Entropic Distance Measure[C].CA：Proc.12th International Conference on Machine Learning,1995：108-114.

[5]FRIEDMAN J H,KOHAVI R,YEOGIRL Y.Lazy Decision Trees[C].Portland：AAAI-96,1996：717-724.