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

盧潤(rùn)彩,龐 超,時(shí)志素

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

0 引言

分類是數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)的一項(xiàng)重要基本任務(wù)。一般地,分類是依據(jù)某種分類模型,在具有類標(biāo)的數(shù)據(jù)集合上學(xué)習(xí)出一個(gè)分類函數(shù),即通常所說的分類器。該函數(shù)能夠給由屬性值序偶集所描述的待分類實(shí)例指派一個(gè)最適合的類標(biāo),從而可以應(yīng)用于數(shù)據(jù)分類和預(yù)測(cè)[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í)策略的分類方法在給測(cè)試實(shí)例分類時(shí)才去訪問訓(xùn)練實(shí)例集合來做出預(yù)測(cè),在分類精確度上有明顯的優(yōu)勢(shì)。本文所提出的Local-LDtree分類模型屬于基于懶惰式學(xué)習(xí)策略的分類方法,在給測(cè)試實(shí)例分類時(shí),首先根據(jù)K-近鄰算法[4]的思想選擇出與該測(cè)試實(shí)例最近的部分訓(xùn)練實(shí)例,然后利用Lazy DT[5]模型在局部訓(xùn)練實(shí)例的集合上來給測(cè)試實(shí)例分類。Local-LDtree分類模型在大多數(shù)數(shù)據(jù)集合上取得了較高的分類精確度。

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

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

1.1 實(shí)例間距離的計(jì)算

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

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

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

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

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

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

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

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

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

2 Local-LDtree分類模型

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

①對(duì)于 T中每個(gè)訓(xùn)練實(shí)例t,計(jì)算x到t的距離d(x,t);

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

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

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

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

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

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

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

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

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

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

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

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

表1 實(shí)驗(yàn)數(shù)據(jù)描述

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

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

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

表2 3種分類器的實(shí)驗(yàn)結(jié)果比較

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

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

4 結(jié)束語

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