趙書寶，姜春茂

(哈爾濱師范大學(xué) 計(jì)算機(jī)科學(xué)與信息工程學(xué)院，哈爾濱 150025)

1 引 言

分類是數(shù)據(jù)挖掘領(lǐng)域中非常實(shí)用的技術(shù)，常見的分類算法有決策樹、神經(jīng)網(wǎng)絡(luò)、KNN和支撐向量機(jī)等.其中KNN算法以其理論成熟、思想簡(jiǎn)單和準(zhǔn)確率高的特點(diǎn)得到了廣泛的應(yīng)用.KNN算法的基本思想是先從給定的訓(xùn)練樣本中找到與待測(cè)樣本距離最近的K個(gè)點(diǎn)，然后計(jì)算K個(gè)點(diǎn)中屬于每一類的條件概率，最后通過(guò)投票得出分類結(jié)果.傳統(tǒng)的KNN算法進(jìn)行分類時(shí)對(duì)每一個(gè)待測(cè)樣本都需要搜尋整個(gè)訓(xùn)練集，計(jì)算與所有訓(xùn)練樣本的距離，然后選出距離最近的K個(gè)點(diǎn).KNN算法的分類效率與訓(xùn)練樣本的規(guī)模呈正比，訓(xùn)練樣本的規(guī)模越大，則分類效率越低.因此，一系列快速KNN算法被提出，以解決KNN算法在面對(duì)大規(guī)模數(shù)據(jù)分類效率較低的缺陷.

針對(duì)傳統(tǒng)KNN算法分類效率較低的情況，許多學(xué)者提出了改進(jìn)的KNN算法.分析發(fā)現(xiàn)所提出的算法大致分為兩種類型，第1種是對(duì)訓(xùn)練樣本裁切，減少訓(xùn)練樣本的規(guī)模[1-5].第2種是通過(guò)快速搜索算法，快速尋找距離最近的K個(gè)近鄰樣本[6].如文獻(xiàn)[1]針對(duì)文本分類時(shí)，樣本規(guī)模較大導(dǎo)致分類效率降低的現(xiàn)象，引入了粗糙集的近似集模型，將所有的樣本劃分到類別的上近似集合和下近似集合，從而根據(jù)待測(cè)樣本與類別的位置關(guān)系，選擇合適的類別，從而提高算法的分類效率.文獻(xiàn)[2]通過(guò)基于界標(biāo)的譜聚類算法將訓(xùn)練樣本劃分為多個(gè)類簇，分別計(jì)算待測(cè)樣本與所有類簇中心的距離，使用距離最近的類簇中的對(duì)象重新構(gòu)造訓(xùn)練集進(jìn)行KNN分類，有效降低訓(xùn)練集的規(guī)模.文獻(xiàn)[3]針對(duì)傳統(tǒng)的KNN算法近鄰點(diǎn)個(gè)數(shù)固定的問(wèn)題，提出了一種使用環(huán)形過(guò)濾器的自適應(yīng)K值的KNN算法，算法通過(guò)計(jì)算樣本之間的相似度動(dòng)態(tài)選取K值，相比于傳統(tǒng)的KNN算法，不僅提高了分類的效率，而且提高了分類的準(zhǔn)確率.文獻(xiàn)[4]針對(duì)KNN算法在面對(duì)大規(guī)模數(shù)據(jù)時(shí)分類效率降低的問(wèn)題，提出了一種基于CUDA的并行化KNN算法，實(shí)驗(yàn)表明算法在保證分類準(zhǔn)確率的基礎(chǔ)上，提高了分類的效率.文獻(xiàn)[5]首先將訓(xùn)練樣本中相似度較高的數(shù)據(jù)聚為一個(gè)類簇，然后以測(cè)試點(diǎn)為中心構(gòu)建環(huán)形過(guò)濾器，對(duì)待測(cè)樣本進(jìn)行分類，有效減少了訓(xùn)練樣本的規(guī)模.

在對(duì)訓(xùn)練樣本進(jìn)行裁切時(shí)，最常用的方式是聚類.基于聚類的快速KNN算法[2，3，5，7]通過(guò)在訓(xùn)練樣本上進(jìn)行聚類，將樣本劃分為多個(gè)類簇，然后選取某一類簇中的對(duì)象作為訓(xùn)練集，但傳統(tǒng)的聚類算法大多是一種二支聚類的結(jié)果.類簇之間具有清晰的邊界，在處理對(duì)象與類簇之間缺乏明確的歸屬關(guān)系的數(shù)據(jù)時(shí)無(wú)法清晰的描述類簇邊界模糊的特征.當(dāng)待測(cè)樣本位于類簇的邊界時(shí)，容易帶來(lái)近鄰點(diǎn)的缺失，從而引起分類準(zhǔn)確率的降低，因此基于聚類的快速KNN算法，大多以降低分類準(zhǔn)確率為代價(jià)，提高分類的效率[2].

三支聚類[8-13]在二支聚類的基礎(chǔ)上引入了中間域的概念，將對(duì)象與類簇之間的關(guān)系分為3種，即對(duì)象確定屬于該類簇，對(duì)象確定不屬于該類簇和不確定對(duì)象是否屬于該類簇.三支聚類能夠更好的描述類簇邊界模糊的結(jié)構(gòu)特征，避免了二支聚類的缺陷.因此，本文針對(duì)傳統(tǒng)聚類改進(jìn)的KNN算法中存在的問(wèn)題，提出了一種基于三支聚類的快速KNN算法(TWC-KNN).其基本思想是首先通過(guò)三支聚類將訓(xùn)練樣本劃分為多個(gè)類簇，每個(gè)類簇均由核心域和邊界域兩個(gè)部分組成.然后通過(guò)分析待測(cè)樣本與類簇之間的位置關(guān)系，如果待測(cè)樣本位于類簇的核心域，則使用核心域中的對(duì)象作為訓(xùn)練樣本進(jìn)行KNN分類，如果待測(cè)樣本位于多個(gè)類簇的邊界域，則使用這些邊界域的對(duì)象作為訓(xùn)練樣本進(jìn)行KNN分類，如果待測(cè)樣本不屬于任何類簇的核心域和邊界域，則使用所有的訓(xùn)練樣本進(jìn)行KNN分類.

本文組織如下：第2節(jié)分析了原有的改進(jìn)型KNN算法的缺陷以及TWC-KNN算法的優(yōu)勢(shì).第3節(jié)回顧了陰影集和三支聚類的基本概念.第4節(jié)提出了一種基于陰影集的三支聚類算法，并通過(guò)該算法對(duì)訓(xùn)練樣本進(jìn)行聚類，去除明顯不屬于待測(cè)樣本K近鄰的對(duì)象，從而提高KNN算法的分類效率.第5節(jié)在UCI數(shù)據(jù)集上進(jìn)行試驗(yàn)，通過(guò)與傳統(tǒng)KNN算法和3種改進(jìn)的KNN算法的對(duì)比驗(yàn)證了本文中所提出算法的優(yōu)勢(shì).第6節(jié)總結(jié)全文，并分析了未來(lái)的研究工作.

2 問(wèn)題描述

基于聚類改進(jìn)的KNN算法大多采用首先在訓(xùn)練樣本上聚類，然后找到與待測(cè)樣本距離最近的類簇中心，使用該類簇所包含的對(duì)象構(gòu)建訓(xùn)練集進(jìn)行KNN分類.這樣可以有效減少訓(xùn)練樣本的規(guī)模，提高KNN算法的分類效率.然而目前采用的聚類算法大多是一種二支聚類的結(jié)果，即對(duì)象確定屬于該類簇或確定不屬于該類簇，類簇之間具有清晰的邊界.這種聚類結(jié)果在某些數(shù)據(jù)集上無(wú)法很好的表述類簇邊界模糊的特征，當(dāng)待測(cè)樣本位于類簇邊界時(shí)，僅根據(jù)距離選取最近的類簇，并使用該類簇中的對(duì)象構(gòu)建訓(xùn)練集進(jìn)行KNN分類，容易引起誤分類，降低KNN分類的準(zhǔn)確率.為了更好的描述文本所闡述的思想，通過(guò)如下兩個(gè)示例來(lái)描述二支聚類改進(jìn)的KNN算法分類時(shí)產(chǎn)生的問(wèn)題，以及三支聚類改進(jìn)的KNN算法的優(yōu)勢(shì).

二支聚類算法對(duì)樣本進(jìn)聚類的結(jié)果如圖1所示.通過(guò)二支聚類將訓(xùn)練樣本劃分到C1和C2兩個(gè)類簇，二支聚類的結(jié)果中對(duì)象只能屬于一個(gè)類簇.當(dāng)待測(cè)樣本位于x1和x2時(shí)，二支聚類算法將其劃分到不同的類簇，此時(shí)對(duì)x1和x2進(jìn)行KNN分類時(shí)容易帶來(lái)近鄰點(diǎn)的缺失.而在傳統(tǒng)的KNN分類中兩者可能屬于同一類別.產(chǎn)生這一問(wèn)題的主要原因是傳統(tǒng)的二支聚類算法無(wú)法很好的描述類簇邊界模糊的特征.因此容易產(chǎn)生較高的誤分類代價(jià)，降低KNN算法的分類準(zhǔn)確率.

圖1 二支聚類的結(jié)果

三支聚類算法對(duì)樣本進(jìn)行聚類的結(jié)果如圖2所示.通過(guò)三支聚類將訓(xùn)練樣本劃分到C1和C2兩個(gè)類簇，三支聚類中的每一個(gè)類簇由兩個(gè)子集表示，即Ci=(Co(Ci)，F(xiàn)r(Ci)).位于核心域Co(Ci)的對(duì)象表示確定屬于類簇Ci，位于邊界域Fr(Ci)的對(duì)象表示可能屬于類簇Ci.當(dāng)待測(cè)樣本位于x1和x2時(shí)，三支聚類算法將其劃分到類簇C1和C2的邊界域.因此在進(jìn)行KNN分類時(shí)使用類簇C1和C2邊界域中的對(duì)象構(gòu)造訓(xùn)練集進(jìn)行KNN分類.這樣可以有效克服二支聚類改進(jìn)的KNN算法在面對(duì)類簇邊界模糊的數(shù)據(jù)時(shí)準(zhǔn)確率較低的缺陷.基于三支聚類的改進(jìn)KNN算法在保持較高分類準(zhǔn)確率的同時(shí)，能夠有效降低訓(xùn)練集的規(guī)模，提高分類效率.

圖2 三支聚類的結(jié)果

3 基本概念

3.1 陰影集

陰影集[14，15]由Witold Pedrycz于1998年首次提出.陰影集由模糊集演化而來(lái)，增強(qiáng)了結(jié)果的可解釋性并將傳統(tǒng)的模糊集轉(zhuǎn)化為三支邏輯.下面給出陰影集的定義.

定義1.[14]在論域U中，給定陰影集S，一對(duì)閾值(α，β)，并且有0<β<α<1.將論域U中所有的對(duì)象根據(jù)隸屬度μA(x)映射到集合{0，[0，1]，1}中.即：

(1)

其中隸屬度μA(x)表示對(duì)象x隸屬于概念A(yù)的程度.如果隸屬度函數(shù)μA(x)大于或等于閾值α，則通過(guò)提升操作將對(duì)象x的隸屬度μA(x)提升到1.如果對(duì)象x的隸屬度μA(x)小于或者等于閾值β，則通過(guò)降低操作將隸屬度μA(x)降低到0.如果對(duì)象x的隸屬度μA(x)在α和β之間，則將對(duì)象劃分到陰影區(qū)域.圖3表示一個(gè)陰影集，陰影集通過(guò)隸屬度函數(shù)μA(x)將所有隸屬度高于閾值α的對(duì)象的隸屬度提升到1，將所有隸屬度低于閾值β的對(duì)象的隸屬度降低到0，陰影區(qū)域則包括所有隸屬度在α和β的對(duì)象.

圖3 陰影集

3.2 三支聚類

于洪教授[11]首次將三支決策[16-22]引入到聚類分析中，提出了三支聚類理論.王平心教授[12]借鑒數(shù)學(xué)形態(tài)學(xué)中收縮和擴(kuò)張的思想，提出了一種基于數(shù)學(xué)形態(tài)學(xué)的三支聚類算法，該算法可將傳統(tǒng)的二支聚類的結(jié)果擴(kuò)展為三支聚類的結(jié)果.姜春茂教授[23]分析了云任務(wù)的多樣化需求和資源動(dòng)態(tài)的特性，提出了一種基于負(fù)載敏感的云任務(wù)三支聚類評(píng)分調(diào)度算法.

傳統(tǒng)的聚類算法是一種二支聚類的結(jié)果，即對(duì)象和類簇之間的關(guān)系只有兩種，對(duì)象確定屬于該類簇或者對(duì)象確定不屬于該類簇.給定一組數(shù)據(jù)U={x1，x2，…，xn}，三支聚類的每個(gè)類簇表示為Ci={Co(Ci)，F(xiàn)r(Ci)}，即類簇Ci由兩個(gè)子集構(gòu)成，分別是類簇Ci的核心域Co(Ci)和邊界域Fr(Ci).類簇的瑣碎域表示為Tr(Ci)=U-(Co(Ci)∪Fr(Ci))，瑣碎域包含的對(duì)象表示確定不屬于該類簇.類簇Ci的3個(gè)域滿足如下條件：

1)Co(Ci)∪Fr(Ci)∪Tr(Ci)=U

2)Co(Ci)∩Fr(Ci)=?

3)Co(Ci)∩Tr(Ci)=?

4)Tr(Ci)∩Fr(Ci)=?

上述4個(gè)條件說(shuō)明任何一個(gè)類簇的核心域、邊界域和瑣碎域之間的并集為論域U.核心域、邊界域和瑣碎域兩兩互不相交.

4 基于三支聚類的快速KNN算法

4.1 構(gòu)造三支聚類

三支聚類的類簇由核心域和邊界域兩個(gè)集合組成，而二支聚類的類簇則是單個(gè)集合.本文嘗試通過(guò)陰影集的提升與降低操作對(duì)FCM聚類的結(jié)果進(jìn)行處理得到三支聚類的結(jié)果.FCM聚類算法通過(guò)最小化類內(nèi)間距不斷更新隸屬度，在所有的對(duì)象對(duì)所有的類簇的隸屬度都確定后，生成對(duì)象與類簇的隸屬度關(guān)系矩陣.通過(guò)隸屬度表示對(duì)象與類簇之間的關(guān)系，對(duì)于隸屬度高于閾值α的對(duì)象，通過(guò)提升操作將隸屬度提升到1，表示對(duì)象確定屬于該類簇.對(duì)于隸屬度低于閾值β的對(duì)象，通過(guò)降低操作將隸屬度降低到0，表示對(duì)象確定不屬于該類簇.隸屬度在α和β之間的對(duì)象劃分到陰影區(qū)域，表示對(duì)象可能屬于該類簇.最終得到三支聚類的結(jié)果.

給定一組數(shù)據(jù)U={x1，x2，…，xn}，通過(guò)FCM將論域U中的對(duì)象劃分為k個(gè)類簇C={C1，C2，…，Ck}對(duì)象x與類簇Ci之間的關(guān)系通過(guò)隸屬度μCi(x)表示.給定一對(duì)閾值(α，β)并且有0<β<α<1，根據(jù)隸屬度μCi(x)與閾值α和β的關(guān)系，有如下3種類型的操作：

EO={μCi(x)=1|μCi(x)≥αi}

RO={μCi(x)=[0，1]|βi<μCi(x)<αi}

SO={μCi(x)=0|μCi(x)≤βi}

(2)

通過(guò)對(duì)象的3種操作，可以得到三支聚類的核心域、邊界域和瑣碎域：

Co(Ci)={x∈U|μCi(x)=1}

Fr(Ci)={x∈U|μCi(x)=[0，1]}

Tr(Ci)={x∈U|μCi(x)=0}

(3)

為了計(jì)算最優(yōu)閾值(α，β)，Zhang[24]將博弈論引入到陰影集，通過(guò)求解納什均衡獲得最優(yōu)閾值.Pedrycz[14]將陰影集中提升和降低操作變化的隸屬度之和與陰影集中對(duì)象數(shù)量之差的絕對(duì)值作為優(yōu)化函數(shù)，通過(guò)求解優(yōu)化函數(shù)的最小值獲得最優(yōu)閾值.Deng[25]將貝葉斯風(fēng)險(xiǎn)決策引入到陰影集中，尋找風(fēng)險(xiǎn)最小時(shí)的閾值.本文采用Pedrycz所提出的方法，通過(guò)求解如下優(yōu)化函數(shù)獲得最優(yōu)閾值α和β.對(duì)于任意類簇Ci，μCi(x)表示對(duì)象x對(duì)Ci的隸屬度，通過(guò)分析對(duì)象與類簇的隸屬度關(guān)系，構(gòu)建優(yōu)化函數(shù)：

(4)

其中：

-card{x∈U|β<μCi(x)<α}|

算法的主要步驟如算法1所示：

算法1.three-way clustering based on shadowed set

1. input：a set of dataU={x1，x2，…，xn}，the number of clusters k

2.output：C={(Co(C1)，F(xiàn)r(C1))，(Co(C2)，F(xiàn)r(C2))，…，(Co(Ck)，F(xiàn)r(Ci))}

3. obtaining membership matrix and cluster center through FCM algorithm

4. calculate the optimal thresholdαandβfor each clusterCithrough the shadowed sets

5. for each clusterCi：

6. foriin range(n)：

7. ifμCi(x)>α：

8. dividexintoCo(Ci)

9. else ifμCi(x)<β：

10. dividexintoTr(Ci)

11. else：

12. dividexintoFr(Ci)

13. returnC={(Co(C1)，F(xiàn)r(C1))， (Co(C2)，F(xiàn)r(C2))，…，(Co(Ck)，F(xiàn)r(Ci))}.

4.2 快速KNN分類

通過(guò)三支聚類對(duì)訓(xùn)練樣本進(jìn)行裁切，從而構(gòu)建新的訓(xùn)練集.根據(jù)待測(cè)樣本y與類簇Ci的隸屬度可知待測(cè)樣本與類簇Ci有3種位置關(guān)系，當(dāng)待測(cè)樣本y與類簇Ci的隸屬度高于給定的閾值α?xí)r，則使用類簇Ci核心域的對(duì)象構(gòu)建訓(xùn)練集，然后進(jìn)行KNN分類.當(dāng)待測(cè)樣本y位于多個(gè)類簇的邊界域時(shí)，則使用這些邊界域中的對(duì)象作為訓(xùn)練樣本進(jìn)行KNN分類.如果待測(cè)樣本不屬于所有類簇的核心域和邊界域時(shí)，則使用全體訓(xùn)練樣本進(jìn)行KNN分類.

基于陰影集三支聚類的改進(jìn)KNN分類算法主要步驟如算法2所示：

算法2.improved KNN classification based on three-way clustering of shadowed set

1. input：C={(Co(C1)，F(xiàn)r(C1))，(Co(C2)，F(xiàn)r(C2))，…，

(Co(Cn)，F(xiàn)r(Cn))}，

test sampleY={y1，y2，…，yn}.

2. output：the predicted value of the label of the test sample.

3. foryiinY：

4. foriin range(n)：

5. ifμCi(y)>α：

6. construct training set using objects inCo(Ci)region.

7.elseifβ<μmi(x)<α：

8. construct training set using objects inFr(Ci)region.

9. ifyinot belong to any cluster：

10. construct training set using all training objects

11. run KNN algorithm.

5 實(shí)驗(yàn)數(shù)據(jù)分析

5.1 對(duì)比算法與實(shí)驗(yàn)數(shù)據(jù)集

為了比較本文所提出的基于三支聚類的快速KNN算法(TWC-KNN)是否具有更好的性能，本文選取了一些對(duì)比算法，包括傳統(tǒng)的KNN算法和3種改進(jìn)的快速KNN算法，RC-KNN[2]、LC-KNN[2]和FCM-KNN[26].實(shí)驗(yàn)選取了8組UCI真實(shí)數(shù)據(jù)集，表1給出了8個(gè)UCI數(shù)據(jù)集的詳細(xì)信息包括樣本數(shù)、屬性數(shù)和類別數(shù).訓(xùn)練數(shù)和測(cè)試數(shù)是以7∶3對(duì)實(shí)驗(yàn)數(shù)據(jù)集進(jìn)行分割，所獲得的樣本個(gè)數(shù).

5.2 算法性能分析

為驗(yàn)證所提出算法的性能，本文比較了所提出的算法與4個(gè)對(duì)比算法的準(zhǔn)確率、平均計(jì)算每一個(gè)對(duì)象參與運(yùn)算的樣本的個(gè)數(shù)和算法的運(yùn)行時(shí)間，實(shí)驗(yàn)共重復(fù)了50次，最終結(jié)果取平均值，分類個(gè)數(shù)為樣本的真實(shí)個(gè)數(shù)，具體結(jié)果如表2-表4所示.

從表2可知，所提出的算法在Waveform、Spambase、Satimage、Avila和Parkinsons均獲得了最高的分類準(zhǔn)確率，在Letter、Pendigits和Segmentation3個(gè)數(shù)據(jù)集上分類準(zhǔn)確率略低于傳統(tǒng)的KNN算法，在整體上看TWC-KNN仍高于其余3種改進(jìn)的KNN算法.從8種不同數(shù)據(jù)集的平均準(zhǔn)確率來(lái)看，所提出的算法略微高于傳統(tǒng)的KNN算法，而其他3種改進(jìn)的KNN算法的準(zhǔn)確率則低于傳統(tǒng)的KNN算法.從表3可知，所提出的TWC-KNN有效減少了參與運(yùn)算的對(duì)象的平均個(gè)數(shù).傳統(tǒng)的KNN算法對(duì)訓(xùn)練樣本不做任何處理，因此參與訓(xùn)練的樣本最多.在Spambase數(shù)據(jù)集上， 所提出的算法對(duì)訓(xùn)練樣本裁切的比例最少，參與運(yùn)算的樣本為訓(xùn)練樣本的89.16%.而在Parkinsons數(shù)據(jù)集上，所提出的算法參與運(yùn)算的對(duì)象的平均個(gè)數(shù)為訓(xùn)練樣本的1.87%， 裁剪的樣本比例最多.

表2 5種KNN分類算法的平均準(zhǔn)確率對(duì)比

表3 不同算法參與運(yùn)算的對(duì)象的平均個(gè)數(shù)

從表1可以發(fā)現(xiàn)Spambase數(shù)據(jù)集類別數(shù)最少為2個(gè)，Parkinsons數(shù)據(jù)集的類別數(shù)最多為42個(gè).因此類別個(gè)數(shù)與分類的效率可能存在一定的關(guān)系，類別數(shù)越多，則分類的效率越高.表4展示了不同算法的平均運(yùn)行時(shí)間，從中可知Spambase數(shù)據(jù)集上，TWC-KNN算法的運(yùn)行時(shí)間高于傳統(tǒng)的KNN算法，這主要是由于該數(shù)據(jù)集上類別數(shù)較少，因此訓(xùn)練樣本裁切的比例較少，而在分類時(shí)需要判斷并選擇合適的類簇作為訓(xùn)練集，因此算法的消耗時(shí)間高于KNN算法，其他3種改進(jìn)的KNN算法，RC-KNN、LC-KNN和FCM-KNN均出現(xiàn)了這種現(xiàn)象.在Letter數(shù)據(jù)集上，TWC-KNN算法運(yùn)行時(shí)間提升的最高，這主要是Letter的訓(xùn)練樣本個(gè)數(shù)和維數(shù)較高，因此傳統(tǒng)的KNN算法分類時(shí)間較高，TWC-KNN算法裁切后，訓(xùn)練樣本的規(guī)模大幅度降低，因此在分類時(shí)間上提升最高.

表4 不同算法的平均消耗時(shí)間(time/s)

5.3 分類簇?cái)?shù)與算法效率的關(guān)系分析

根據(jù)5.2節(jié)可以發(fā)現(xiàn)，分類簇?cái)?shù)越少，則算法的效率越低，分類簇?cái)?shù)越多，則算法的效率越高，為驗(yàn)證這一結(jié)論是否具有普遍性，本文設(shè)置了以下實(shí)驗(yàn)，在8種不同的UCI數(shù)據(jù)集上，對(duì)比了所提出的TWC-KNN算法與傳統(tǒng)的KNN算法和3種改進(jìn)的KNN算法在不同規(guī)模的分類簇?cái)?shù)下算法所需的時(shí)間與準(zhǔn)確率.分類簇?cái)?shù)設(shè)置為5，10，15，20，25，在不同的分類簇?cái)?shù)下均進(jìn)行了50次重復(fù)，最終結(jié)果取其平均值具體結(jié)果如圖4和圖5所示.

從圖4可以看出，在不同的分類簇?cái)?shù)下KNN算法消耗的時(shí)間基本穩(wěn)定，這是由于KNN算法對(duì)訓(xùn)練集并未裁切，而所提出的TWC-KNN算法與3種對(duì)比的改進(jìn)KNN算法隨著分類簇?cái)?shù)規(guī)模的增加，分類所消耗的之間大幅度的降低，但隨著分類簇?cái)?shù)的增加到一定程度，分類效率的增加趨向于平穩(wěn)，在Segmentation數(shù)據(jù)集上由于樣本的規(guī)模較小，所以所提出的算法并未展現(xiàn)較好的分類效率，這也反應(yīng)了所提出的TWC-KNN算法更加適合于樣本規(guī)模較大的數(shù)據(jù)集.從圖5中可以看出，隨著分類簇?cái)?shù)的不斷增加，所提出的TWC-KNN算法有輕微的下降趨勢(shì)，這主要是由于所提出的算法為近似算法，隨著分類簇?cái)?shù)的不斷增加，所產(chǎn)生的邊界越多，越容易引起近鄰樣本的缺失，因此分類準(zhǔn)確率有所降低.從圖4和圖5可知，TWC-KNN算法在各個(gè)分類簇?cái)?shù)規(guī)模下，分類準(zhǔn)確率都高于其它3種改進(jìn)的KNN算法，且時(shí)間消耗也小于其它3種改進(jìn)的KNN算法.總體來(lái)看，當(dāng)數(shù)據(jù)集的分類數(shù)較多時(shí)，考慮到分類準(zhǔn)確率的要求，一般建議以真實(shí)分類數(shù)進(jìn)行聚類，劃分類簇，當(dāng)數(shù)據(jù)集的分類數(shù)較少時(shí)，一般建議類簇?cái)?shù)在10-15.總體來(lái)看TWC-KNN相比于其他3種改進(jìn)的KNN算法，在分類準(zhǔn)確率和分類效率方面均有提高，因此所提出的算法是可行的.

圖4 不同分類簇規(guī)模下算法平均消耗時(shí)間

圖5 不同分類簇規(guī)模下算法的平均準(zhǔn)確率

5.4 訓(xùn)練樣本規(guī)模與分類準(zhǔn)確率的關(guān)系分析

通常隨著訓(xùn)練樣本規(guī)模的減少，分類的準(zhǔn)確率會(huì)逐漸降低.為分析本文所提出的算法隨著訓(xùn)練樣本規(guī)模的減少，分類準(zhǔn)確率是否相對(duì)于原有的KNN算法和3種改進(jìn)的KNN算法呈現(xiàn)顯著的降低，為此本文設(shè)計(jì)了如下實(shí)驗(yàn)，在8種不同的UCI數(shù)據(jù)集上，分別運(yùn)行本文所提出的算法以及其他4種對(duì)比算法，聚類的類簇?cái)?shù)為真實(shí)類簇?cái)?shù)，訓(xùn)練樣本的規(guī)模占總樣本的規(guī)模的比例依次減少，分別為90%，80%，70%，60%，50%.實(shí)驗(yàn)結(jié)果如圖6所示.

從圖6可以發(fā)現(xiàn)，隨著訓(xùn)練樣本規(guī)模的減少，分類的準(zhǔn)確率在8種數(shù)據(jù)集上均有一定程度上的降低，但所提出的TWC-KNN算法與傳統(tǒng)的KNN算法和3種改進(jìn)的KNN算法相比降低程度趨于相同，因此隨著訓(xùn)練樣本規(guī)模的降低，本文所提出的算法相比于對(duì)比算法并不會(huì)帶來(lái)分類準(zhǔn)確率的顯著降低.

圖6 不同訓(xùn)練樣本規(guī)模下算法的平均準(zhǔn)確率

6 總 結(jié)

本文針對(duì)現(xiàn)有聚類改進(jìn)的KNN算法分類準(zhǔn)確率較低的問(wèn)題，提出了一種基于三支聚類的改進(jìn)KNN算法.該算法首先通過(guò)陰影集對(duì)FCM聚類結(jié)果的隸屬度矩陣進(jìn)行處理，得到三支聚類，從而將訓(xùn)練樣本劃分為多個(gè)類簇，通過(guò)分析待測(cè)樣本與類簇中心的位置關(guān)系重新構(gòu)造訓(xùn)練集，然后進(jìn)行KNN分類，有效的去除了大量確定不屬于待測(cè)樣本K近鄰的對(duì)象，且克服了現(xiàn)有的改進(jìn)KNN算法分類準(zhǔn)確率下降的缺點(diǎn).實(shí)驗(yàn)結(jié)果表明了本算法相比于傳統(tǒng)的KNN算法和3種改進(jìn)的KNN算法，在分類準(zhǔn)確率和分類效率方面均有所提高.