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

趙書寶，姜春茂

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

1 引 言

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

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

在對訓練樣本進行裁切時，最常用的方式是聚類.基于聚類的快速KNN算法[2，3，5，7]通過在訓練樣本上進行聚類，將樣本劃分為多個類簇，然后選取某一類簇中的對象作為訓練集，但傳統的聚類算法大多是一種二支聚類的結果.類簇之間具有清晰的邊界，在處理對象與類簇之間缺乏明確的歸屬關系的數據時無法清晰的描述類簇邊界模糊的特征.當待測樣本位于類簇的邊界時，容易帶來近鄰點的缺失，從而引起分類準確率的降低，因此基于聚類的快速KNN算法，大多以降低分類準確率為代價，提高分類的效率[2].

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

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

2 問題描述

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

二支聚類算法對樣本進聚類的結果如圖1所示.通過二支聚類將訓練樣本劃分到C1和C2兩個類簇，二支聚類的結果中對象只能屬于一個類簇.當待測樣本位于x1和x2時，二支聚類算法將其劃分到不同的類簇，此時對x1和x2進行KNN分類時容易帶來近鄰點的缺失.而在傳統的KNN分類中兩者可能屬于同一類別.產生這一問題的主要原因是傳統的二支聚類算法無法很好的描述類簇邊界模糊的特征.因此容易產生較高的誤分類代價，降低KNN算法的分類準確率.

圖1 二支聚類的結果

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

圖2 三支聚類的結果

3 基本概念

3.1 陰影集

陰影集[14，15]由Witold Pedrycz于1998年首次提出.陰影集由模糊集演化而來，增強了結果的可解釋性并將傳統的模糊集轉化為三支邏輯.下面給出陰影集的定義.

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

(1)

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

圖3 陰影集

3.2 三支聚類

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

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

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

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

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

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

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

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

4.1 構造三支聚類

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

給定一組數據U={x1，x2，…，xn}，通過FCM將論域U中的對象劃分為k個類簇C={C1，C2，…，Ck}對象x與類簇Ci之間的關系通過隸屬度μCi(x)表示.給定一對閾值(α，β)并且有0<β<α<1，根據隸屬度μCi(x)與閾值α和β的關系，有如下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)

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

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

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

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

(3)

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

(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)，Fr(C1))，(Co(C2)，Fr(C2))，…，(Co(Ck)，Fr(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)，Fr(C1))， (Co(C2)，Fr(C2))，…，(Co(Ck)，Fr(Ci))}.

4.2 快速KNN分類

通過三支聚類對訓練樣本進行裁切，從而構建新的訓練集.根據待測樣本y與類簇Ci的隸屬度可知待測樣本與類簇Ci有3種位置關系，當待測樣本y與類簇Ci的隸屬度高于給定的閾值α時，則使用類簇Ci核心域的對象構建訓練集，然后進行KNN分類.當待測樣本y位于多個類簇的邊界域時，則使用這些邊界域中的對象作為訓練樣本進行KNN分類.如果待測樣本不屬于所有類簇的核心域和邊界域時，則使用全體訓練樣本進行KNN分類.

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

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

1. input：C={(Co(C1)，Fr(C1))，(Co(C2)，Fr(C2))，…，

(Co(Cn)，Fr(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 實驗數據分析

5.1 對比算法與實驗數據集

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

5.2 算法性能分析

為驗證所提出算法的性能，本文比較了所提出的算法與4個對比算法的準確率、平均計算每一個對象參與運算的樣本的個數和算法的運行時間，實驗共重復了50次，最終結果取平均值，分類個數為樣本的真實個數，具體結果如表2-表4所示.

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

表2 5種KNN分類算法的平均準確率對比

表3 不同算法參與運算的對象的平均個數

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

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

5.3 分類簇數與算法效率的關系分析

根據5.2節可以發現，分類簇數越少，則算法的效率越低，分類簇數越多，則算法的效率越高，為驗證這一結論是否具有普遍性，本文設置了以下實驗，在8種不同的UCI數據集上，對比了所提出的TWC-KNN算法與傳統的KNN算法和3種改進的KNN算法在不同規模的分類簇數下算法所需的時間與準確率.分類簇數設置為5，10，15，20，25，在不同的分類簇數下均進行了50次重復，最終結果取其平均值具體結果如圖4和圖5所示.

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

圖4 不同分類簇規模下算法平均消耗時間

圖5 不同分類簇規模下算法的平均準確率

5.4 訓練樣本規模與分類準確率的關系分析

通常隨著訓練樣本規模的減少，分類的準確率會逐漸降低.為分析本文所提出的算法隨著訓練樣本規模的減少，分類準確率是否相對于原有的KNN算法和3種改進的KNN算法呈現顯著的降低，為此本文設計了如下實驗，在8種不同的UCI數據集上，分別運行本文所提出的算法以及其他4種對比算法，聚類的類簇數為真實類簇數，訓練樣本的規模占總樣本的規模的比例依次減少，分別為90%，80%，70%，60%，50%.實驗結果如圖6所示.

從圖6可以發現，隨著訓練樣本規模的減少，分類的準確率在8種數據集上均有一定程度上的降低，但所提出的TWC-KNN算法與傳統的KNN算法和3種改進的KNN算法相比降低程度趨于相同，因此隨著訓練樣本規模的降低，本文所提出的算法相比于對比算法并不會帶來分類準確率的顯著降低.

圖6 不同訓練樣本規模下算法的平均準確率

6 總 結

本文針對現有聚類改進的KNN算法分類準確率較低的問題，提出了一種基于三支聚類的改進KNN算法.該算法首先通過陰影集對FCM聚類結果的隸屬度矩陣進行處理，得到三支聚類，從而將訓練樣本劃分為多個類簇，通過分析待測樣本與類簇中心的位置關系重新構造訓練集，然后進行KNN分類，有效的去除了大量確定不屬于待測樣本K近鄰的對象，且克服了現有的改進KNN算法分類準確率下降的缺點.實驗結果表明了本算法相比于傳統的KNN算法和3種改進的KNN算法，在分類準確率和分類效率方面均有所提高.