基于CURE聚類算法改進的原型選擇算法①

孫元元， 張德生， 張 曉

(西安理工大學 理學院，西安 710054)

1 引言

K近鄰分類器(KNN)[1]是用于分類任務的最常用和最著名的技術之一，其簡單易操作性被人們廣泛應用于文本分類、圖像處理、手寫數字識別等方面. 然而K近鄰分類器存在計算量大、內存開銷大的特點，目前已經有許多改進方法. 其中最主要的技術有兩種：原型生成和原型選擇. 原型生成PG (Prototype Generation)[2]是通過生成人造數據來代替原始數據，使其能夠填充原始數據集中沒有代表性樣例的區域. 原型選擇PS (Prototype Selection)[3]是對整個數據集進行約簡，在保證不降低甚至提高分類精度等性能的基礎上，獲取具有較高分類貢獻的同時能夠反映原始數據集的分布狀況具有一定代表性的原型子集.

目前，研究學者已經提出了許多原型選擇算法，最著名的兩個方法是壓縮和剪輯策略. 在1968年，Hart[4]最早提出的原型選擇算法是壓縮最近鄰CNN (Condensed Nearest Neighbor)，該算法主要針對整個數據集，盡可能多的約簡數據集的樣例，只保留貢獻率最高的邊界樣例，但該算法分類精度卻有所降低，而且計算過程非常依賴原樣例掃描的順序. 在1972年，Tomek[5]提出了基于K近鄰規則的剪輯算法ENN(Edited Nearest Neighbor)，該算法旨在有效排除原始訓練集中的噪聲數據和重疊數據，但該算法是基于剪輯策略的算法，并沒有刪除對分類沒有重要貢獻的內部樣例點，因此其數據約簡率比較低. 之后，基于ENN的一系列改進算法被提了出來. 在2009年，Fayed和Atiya[6]提出了一種新的壓縮算法—KNN模板約簡算法TRKNN (Template Reduction for KNN)，該算法的基本思想是定義一個最近鄰居“鏈”，然后根據鏈上的每一段距離，設置一個閾值來將其劃分成保留的壓縮數據集和要移除的數據集.在2010年，Ougiaroglou[7]等提出了一個基于聚類的原型選擇算法PSC (Prototype Selection by Clustering)，該算法首先使用K-means聚類算法將整個數據集劃分成不同的簇，然后在每一個簇中選擇代表樣例. 對于同類簇集，最靠近簇中心的樣例被保留下來; 對于不同類簇集，不同類邊界的樣例被保留下來; 保留下來的樣例作為最終的原型進行分類. 在2014年，Li和Wang[8]提出了一個基于二叉最近鄰樹的原型選擇算法BNNT (the Binary Nearest Neighbor Tree)，該算法首先建立一個二叉最近鄰樹，當二叉樹位于一個類的內部時，生成一個中心點代替樹的所有節點被保留; 當二叉樹位于多個類的邊界時，擁有不同類標簽同時在樹中直接相連的原型被保留下來，保留下來的所有樣例點作為原型集進行分類. 在2016年，Li[9]等人提出了基于自然鄰居和最近敵人的原型選擇算法，該算法利用自然鄰居過濾噪聲模式并平滑類邊界，再使用基于最近敵人新的冷凝方法來減少原型的數量，該編輯算法和冷凝算法的結合去除內部冗余樣例，保留了邊界樣例，有效地減少了數據集的數量. 在2017年，朱慶生[10]等人提出基于自然鄰居和最小生成樹的原型選擇算法2NMST(Prototype Selection Algorithm Based on Natural Neighbor and MST)，該算法使用自然鄰居做數據預處理，然后基于設定的終止條件構建Prim最小生成樹，生成一些具有代表性的內部原型，并保留邊界原型. 在2018年，黃宇揚[11]等人提出了一種面向K最近鄰(KNN)的遺傳實例選擇算法. 該算法采用基于決策樹和遺傳算法的二階段篩選機制，先使用決策樹確定噪聲樣本存在的范圍; 再使用遺傳算法在該范圍內精確刪除噪聲樣本，可有效地降低誤刪率并提高效率，采用基于最近鄰規則的驗證集選擇策略，進一步提高了遺傳算法實例選擇的準確度; 最后引進基于均方誤差(MSE)的分類精度懲罰函數來計算遺傳算法中個體的適應度，提高有效性和穩定性. 同年，王熙照[12]等人提出基于非平穩割點的樣例選擇方法.依據在區間端點得到凸函數的極值這一基本性質，通過標記非平衡割點度量一個樣例為端點的程度，然后選取端點程度較高的樣例，從而避免樣例之間距離的計算. 同時，進化算法已經應用于原型選擇算法的，Acampora G[13]等人首次提出將“后驗”算法，即SPEA2應用于原型選擇問題，以明確處理KNN時間和空間復雜度兩個目標，并在分類和降低性能之間提供更好的權衡.

上述提到的所有算法雖然在存儲空間和時間復雜度上都有了較好的改進，但仍具有較低的分類準確率和較高的原型保留率. 針對目前原型選擇存在的問題，本文在CURE算法的基礎上對其進行改進，從而提出一種新的原型選擇方法PSCURE. 同時針對CURE聚類算法改進有兩方面，一方面是異常點剔除方法的改進. 原CURE算法很難確定異常點，本文使用共享鄰居密度計算每個原樣例周圍的密度，再根據密度特征值進行去噪; 另一方面是代表點選擇的改進. 原CURE算法挑選的代表點容易集中在圖形最長的兩端[14]，而本文使用最大最小距離來選取代表點，使代表點具有分散性，由此提出了一種新的原型選擇算法. 本文的結構如下：第2部分主要介紹共享鄰居密度和最大最小距離，以及CURE的相關知識; 第3部分提出基于CURE聚類改進的原型選擇方法及計算; 第4部分針對所提出算法PSCURE進行數值實驗.

2 相關工作

為了更好的理解本文算法，本章介紹了涉及到的3種重要算法：共享最近鄰密度，最大最小距離和CURE聚類算法.

2.1 共享鄰居密度

共享鄰居是兩個樣例數據共同擁有的近鄰個數，基本思想是如果兩個樣例點擁有的近鄰個數越多證明兩點越相似，根據共享鄰居的相似性得知每個點的局部密度，即共享鄰居密度.

定義1[15](共享鄰居). 對于數據集X中的任意點i和j，點i和點j的K-最近鄰居集合分別是Γ(i)和Γ(j)，點i和點j的共享鄰居是它們的公共鄰居集，表示為

定義2[15](SNN相似性). 對于數據集X中的任何點i和j，它們的SNN相似性定義為

其中，dij是點i和j之間的距離. 僅當點i和點j出現在彼此的K鄰居集中時才計算SNN相似性，否則，點i和點j之間的SNN相似性為0. 式(2)的非零部分通過以下形式表示，從中可以清楚地觀察到SNN相似性的含義，即：

等式右端的左邊部分表示點i和點j的共享鄰居的數量，右邊部分是從點i和點j到所有共享鄰居的距離的平均值的倒數，它表示在一定程度上圍繞兩點的密度.通過同時檢查共享鄰居和此兩點的密度，SNN相似性可以更好地適應各種環境.

在定義任意兩點的SNN相似性之后，我們使用該相似性來計算點i 的局部密度ρi.

定義3[15](SNN局部密度). 設點i是數據集X中的任意點，L(i)={x1,x2,···xk}是與點i具有最高相似度的K個點的集合. 點i的局部密度定義為與點i具有最高相似度的K個點的相似度之和，即

基于共享鄰居密度包含了數據點的局部鄰域信息的特點，當一個點鄰域中的數據點分布較密時，該點的密度就相對較大，反之較小.

根據上述定義計算數據集中的每個數據對象的共享最近鄰密度值，然后按照共享鄰居密度值對數據對象進行升序排列，畫出密度遞增曲線. 根據假設，數據集中的噪聲點與正常點相比分布相對稀疏，因而其密度較小，那么在密度遞增曲線上，噪聲點和正常點之間存在一個拐點，在該拐點之前的數據點為噪聲點，而在此之后的點為正常點. 利用共享鄰居密度去噪算法的偽代碼如下：

算法1：利用共享鄰居密度去噪的算法輸入：數據集X，近鄰數K輸出：去噪后的數據集找出所有點的K-最近鄰?i,j∈X For If 兩個點i和j不是互相在對方的K最近鄰中 Then number(SNN(i，j))←0 Else number(SNN(i，j))←共享的近鄰個數End If similarity(i，j)=number(SNN(i，j)) *( 1/(1/number(SNN(i，j)) *sum(dist(i，p))+dist(j，p)))ρi density=sum(similarity(i，j)) //局部密度End for den_threshold=computer_denthr(density)//remove noise points?i∈X For If density(i)＜=den_threshold X.delete(i) End If End for

在算法1中，getKnn(i，X)表示在數據集X中尋找i的K個近鄰，number()表示兩個樣例中的共同的鄰居，也就是共享鄰居個數，如果兩個樣例不是互相在對方的K最近鄰中，定義這兩個樣例的相似度為0，否則根據式(1)計算共享近鄰個數. 通過式(3)計算共享近鄰的相似性similarity()，再根據相似性通過式(4)求出數據集中每個樣例的密度，這里的密度主要是根據一個樣例與周圍K近鄰的共享近鄰的相似性之和定義，computer_denthr()確定密度閾值，從而去除數據集中的噪聲點.

2.2 最大最小距離

最大最小距離算法也稱小中取大距離算法[16]. 本文使用歐式距離，已知N個樣本X1,X2,···,XN，算法描述：

(1) 給定θ，0＜θ＜1(一般θ=1/2)，計算每個特征的平均值生成一個中心點，計算離該中心點最近的數據集中的點作為第一代表點Z1;

(2) 計算所有樣例到Z1的距離Di1，選擇距離第一個代表點Z1最遠的樣例點作為第二個代表點Z2，距離表示為D12;

(3) 計算其余樣例點到Z1，Z2之間的距離，并求出他們中的最小值，即Di=min(Di1,Di2),i=1,2,···,N;

(5) 以此類推計算每個樣例點i到已確定的所有代表點j之間的距離Dij，并求出Di0=maix(min(Di1,Di2,···,Dij))，若Di0＞θ·D12，則繼續建立代表點，否則結束尋找. 利用最大最小距離選取代表點算法的偽代碼如下：

算法2. 最大最小距離選取代表點θ輸入：數據集X，閾值輸出：代表點集合center point=[每個特征的平均值]center[0]=距離point最近的點 //第一代表點center[1]=距離center[0]最遠的點 //第二個代表點D12=get_distance(center[0]，center[1])//計算所有代表點max_min_distance=0 θ?D12 While max_min_distance＞index=0 For i in range(len(X)) min_distance=[] For j in range(len(center)) distance=get_distance(X[i]，center[j]) min_distance.append(distance) End For min_dis=min(dis for dis in min_distance) If min_dis＞max_min_distance max_min_distance=min_dis index=i End if center.append(X[index])End While Return center

2.3 CURE層次聚類算法

CURE (Clustering Using REpresentative)算法[17]采用了一種自底向上的層次聚類算法，最突出的特點是利用代表點而不是中心點代表一個類，利用代表點計算一個類與另一個類之間的距離. 代表點是指能夠代表這個類的形狀、密度和分布的一些數據點，基本的思想是：所有數據點在最初都是一個簇，然后不斷合并，直到最后的簇個數為指定的數目. 詳細步驟如下：

(1) 抽樣過程：從原始數據對象中選取一個隨機樣例D;

(2) 劃分過程：對樣例D進行劃分，一般按數量均勻劃分;

(3) 初始化過程：設置參數，參數一是要形成的簇數K，參數二是代表點(代表該簇的點)的數目m，參數三是收縮因子alpha;

(4) 聚類過程：對每個劃分挑選代表點進行聚類;第一個代表點選擇離簇中心最遠的點，而其余點選擇離所有已經選取的點最遠的點;

(5) 剔除離群點：第一階段刪除在聚類過程中增長非常緩慢的簇; 第二階段在聚類結束時含數據對象明顯少的簇.

3 基于CURE聚類算法改進的原型選擇

基于聚類的原型選擇的動機是快速執行通過聚類挑選出有代表性的內部點和邊界點，為了實現這一點，本文針對CURE層次聚類算法中對噪聲點不易判斷性，使用了共享鄰居密度計算每個樣例的密度，根據密度增值曲線對整個樣例集確定密度閾值，進而確定噪聲點.

在此使用人造數據集Flame people[18]對此算法進行說明. 圖1(a)中表示該人造數據集的密度增值曲線，其中紅色斷點處是我們確定的噪聲點和正常點之間的拐點. 圖1(b)中展示了利用算法1識別噪聲點之后的結果，其中“+”為識別出的噪聲點.

另一方面，針對CURE選擇代表點的局限性，利用最大最小距離選擇代表點的方法代替CURE算法挑選代表點的算法，使得代表點能夠盡量分散，從而更好地代表該簇. 在此利用隨機產生的數據說明該情況. 圖2(a)是利用CURE算法挑選出代表點的圖示，其中圓圈點為代表點，可見代表點集中在兩端，不能很好地反應數據的形狀和分布信息. 圖2(b)中是利用算法2挑選的代表點，可以觀察到，代表點分散在每個邊緣地方，并選擇了適當的中心點來做代表點，滿足分散點的特性，較好的描述了數據集的分布情況.

圖1 利用共享鄰居密度確定噪聲點

圖2 CURE與最大最小距離代表點選取結果

PSCURE算法的主要步驟如下：

(1) 針對原始樣例集S={X1,X2,···,XN}使用算法1對原始樣例集S 進行去噪處理，得到去噪后的樣例集S′;

(2) 針對樣例集S′使用算法2替代CURE聚類算法步驟(4)挑選代表點的方法，所得到的代表點生成最終原型集PS;

(3) 使用最終的原型集PS進行KNN分類.

為了測試本文基于CURE算法改進的原型選擇算法效果，使用了合成數據集pathbased[19]和Flame people[18]進行評估. 圖3(a)展示了pathbased原始數據集的分布情況，圖3(b)通過共享近鄰的密度對整個樣例集進行去噪處理，其中圖中的“+”表示應用該算法識別的噪聲點，直觀地可以看出噪聲點周圍的密度相對其它數據集點的密度較低，圖3(c)通過最大最小距離改進的CURE層次聚類算法針對數據集進行聚類，可以看出該算法將該數據集準確的劃分為三個類，保留其聚類完成后的所有代表點，圖3(d)所示，該算法保留了一些靠近中心的樣例點和簇邊界點，得到的原型最大程度的代表了整個數據集.

圖3 PSCURE原型選擇算法在Pathbased數據集上的展示

同樣，圖4展示了所提算法在合成數據集Flame people上的結果，圖4(a)展示了Flame people原始數據集的分布情況，圖4(b)圖檢測出局部密度最低的兩個點作為噪聲點，即圖中的“+”; 圖4(c)通過改進的CURE聚類算法精確的識別該數據屬于兩個簇，針對兩個簇保留聚類過程所用的代表點作為最后的原型集，即圖4(d)展示，該代表點除了包含內部點之外，還包含兩簇之間的邊界點.

圖4 PSCURE原型選擇算法在Flame people數據集上的展示

4 實驗結果及分析

為了評估PSCURE原型選擇算法的有效性，該章節利用該算法與傳統的KNN[1]，經典的CNN[4]、ENN[5]和最新的TRKNN[6]、PSC[7]、BNNT[8]和2NMST[10]算法在原型選擇的個數及分類準確率方面進行了實驗比較. 為了達到這個目的，從UCI上下載10個數據集，數據集的描述如表1所示.

表1 UCI數據集

4.1 實驗設計

本文使用10折交叉驗證將數據集劃分為訓練集和測試集，取平均值作為最終的測試結果. 在KNN實驗中，選擇K=3、5、7中分類準確率最高的值作為最終分類準確率，距離度量采用的是歐氏距離. 為了精確度量算法的性能，本文使用分類準確率和樣例的保留率兩個主要的考察指標. 分類準確率表示針對測試樣例集利用分類器正確分類的樣例數與測試集總樣例數的比值. 保留率表示訓練數據集經過該算法處理之后保留下來的數據子集與訓練集中樣本個數的比值. 為了方便我們把這兩個指標分別記為Acc和Str. 公式分別如下：

其中，n1表示測試集個數，n2表示訓練集個數，|Pr|表示被正確分類的樣例個數，|PS|表示算法最后保留下來的樣例集個數.

4.2 實驗結果

針對表1給出的UCI數據集中的數據，本文首先利用PSCURE算法與傳統的KNN算法和基于聚類的原型選擇PSC做比較，表2列出了這3個算法的準確率和保留率，同樣，圖5展示準確率和保留率之間的比較，從實驗結果可以看出KNN算法對于整個樣例集沒有進行約簡，因此保留率是100%，在沒有縮減的情況下準確率為77.65%. PSC算法跟傳統的KNN算法進行比較，降低了樣例數量，平均保留率為38.67%，但在準確率上較傳統的KNN算法低于10.91%. PSCURE算法的準確率為81.66%，高于PSC算法的同時，更高于傳統的KNN，但PSCURE算法的平均保留率僅有16.97%，大大約簡了數據，提高了效率. 因此PSCURE算法有效的提高了分類算法的準確率和原型縮減率.

為了更進一步驗證PSCURE算法的有效性，PSCURE算法與CNN，ENN，TRKNN，BNNT相比(見表3)，PSCURE算法對幾乎所有數據集有更高的或差不多的分類準確率，但卻有較低的保留率. 與2NMST相比，PSCURE算法在數據集Sonar、Wine、Glass、Yeast、Segmentation、Letter上有較高的分類準確率且有較低的保留率. 從圖6可以看出，本文所提算法的平均分類準確率最高，但平均保留率最低. 從平均結果來看，PSCURE算法在樣本保留率和分類準確率方面都有明顯的優勢.

5 結束語

KNN在大規模數據集下具有過高的時間和空間復雜度而限制了其應用，為了解決該問題，本文提出了基于CURE聚類算法改進的原型選擇，該算法可以保證在分類準確率不降低情況下，縮減原始數據集樣例數，從而提高分類效率. 本文在CURE算法基礎上進行改進，挑選代表點來對KNN進行原型選擇. 具體地，使用共享鄰居密度對整個樣例集進行噪聲點處理，使用最大最小距離代替CURE聚類算法代表點的選擇，最后利用挑選的代表點集進行KNN分類. 實驗結果表明PSCURE算法比其他原型選擇算法能篩選出較少的原型，但能獲取較高的分類準確率.

表2 PSCURE算法與KNN、PSC的準確率和保留率

表3 算法PSCURE和CNN、ENN、TRKNN、BNNT、2NMST的準確率和保留率的比較結果

圖5 表2中平均準確率和保留率的散點圖

圖6 表3中平均準確率和保留率的散點圖