基于K-近鄰的局部懶惰式?jīng)Q策樹分類模型

盧潤彩,龐 超,時志素

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

0 引言

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

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

1 Local-LDtree的關(guān)鍵問題

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

1.1 實例間距離的計算

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

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

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

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

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

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

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

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

Lazy DT實際上只需建立一條針對測試實例的路徑和一個使算法變快的緩沖表,在小的數(shù)據(jù)集合上,分類精確度較高?？梢詰?yīng)用于局部訓(xùn)練實例集合來給測試實例確定最合適的類標(biāo)。

2 Local-LDtree分類模型

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

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

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

③將SUBT和x作為Lazy DT的輸入,調(diào)用Lazy DT算法,得到 x的類標(biāo);

④返回利用Lazy DT得到的x的類標(biāo);

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

算法的關(guān)鍵是：①選擇適當(dāng)?shù)木嚯x計算標(biāo)準(zhǔn),并針對測試用例計算它到每個訓(xùn)練實例的距離;②在利用懶惰式?jīng)Q策樹在局部訓(xùn)練實例上給測試實例x分類時,算法要正確在選擇分裂屬性和與x對應(yīng)的訓(xùn)練實例集合。

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

①連續(xù)型屬性的處理：對于連續(xù)型屬性不是進(jìn)行預(yù)處理,而是采用2路分裂,將其進(jìn)行離散化;

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

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

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

3 實驗數(shù)據(jù)及結(jié)果分析

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

表1 實驗數(shù)據(jù)描述

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

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

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

表2 3種分類器的實驗結(jié)果比較

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

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

4 結(jié)束語

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

[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.