孫元元， 張德生， 張 曉

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

1 引言

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

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

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

2 相關(guān)工作

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

2.1 共享鄰居密度

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

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

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

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

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

在定義任意兩點(diǎn)的SNN相似性之后，我們使用該相似性來(lái)計(jì)算點(diǎn)i 的局部密度ρi.

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

基于共享鄰居密度包含了數(shù)據(jù)點(diǎn)的局部鄰域信息的特點(diǎn)，當(dāng)一個(gè)點(diǎn)鄰域中的數(shù)據(jù)點(diǎn)分布較密時(shí)，該點(diǎn)的密度就相對(duì)較大，反之較小.

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

算法1：利用共享鄰居密度去噪的算法輸入：數(shù)據(jù)集X，近鄰數(shù)K輸出：去噪后的數(shù)據(jù)集找出所有點(diǎn)的K-最近鄰?i,j∈X For If 兩個(gè)點(diǎn)i和j不是互相在對(duì)方的K最近鄰中 Then number(SNN(i，j))←0 Else number(SNN(i，j))←共享的近鄰個(gè)數(shù)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)表示在數(shù)據(jù)集X中尋找i的K個(gè)近鄰，number()表示兩個(gè)樣例中的共同的鄰居，也就是共享鄰居個(gè)數(shù)，如果兩個(gè)樣例不是互相在對(duì)方的K最近鄰中，定義這兩個(gè)樣例的相似度為0，否則根據(jù)式(1)計(jì)算共享近鄰個(gè)數(shù). 通過(guò)式(3)計(jì)算共享近鄰的相似性similarity()，再根據(jù)相似性通過(guò)式(4)求出數(shù)據(jù)集中每個(gè)樣例的密度，這里的密度主要是根據(jù)一個(gè)樣例與周?chē)鶮近鄰的共享近鄰的相似性之和定義，computer_denthr()確定密度閾值，從而去除數(shù)據(jù)集中的噪聲點(diǎn).

2.2 最大最小距離

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

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

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

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

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

算法2. 最大最小距離選取代表點(diǎn)θ輸入：數(shù)據(jù)集X，閾值輸出：代表點(diǎn)集合center point=[每個(gè)特征的平均值]center[0]=距離point最近的點(diǎn) //第一代表點(diǎn)center[1]=距離center[0]最遠(yuǎn)的點(diǎn) //第二個(gè)代表點(diǎn)D12=get_distance(center[0]，center[1])//計(jì)算所有代表點(diǎn)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]采用了一種自底向上的層次聚類算法，最突出的特點(diǎn)是利用代表點(diǎn)而不是中心點(diǎn)代表一個(gè)類，利用代表點(diǎn)計(jì)算一個(gè)類與另一個(gè)類之間的距離. 代表點(diǎn)是指能夠代表這個(gè)類的形狀、密度和分布的一些數(shù)據(jù)點(diǎn)，基本的思想是：所有數(shù)據(jù)點(diǎn)在最初都是一個(gè)簇，然后不斷合并，直到最后的簇個(gè)數(shù)為指定的數(shù)目. 詳細(xì)步驟如下：

(1) 抽樣過(guò)程：從原始數(shù)據(jù)對(duì)象中選取一個(gè)隨機(jī)樣例D;

(2) 劃分過(guò)程：對(duì)樣例D進(jìn)行劃分，一般按數(shù)量均勻劃分;

(3) 初始化過(guò)程：設(shè)置參數(shù)，參數(shù)一是要形成的簇?cái)?shù)K，參數(shù)二是代表點(diǎn)(代表該簇的點(diǎn))的數(shù)目m，參數(shù)三是收縮因子alpha;

(4) 聚類過(guò)程：對(duì)每個(gè)劃分挑選代表點(diǎn)進(jìn)行聚類;第一個(gè)代表點(diǎn)選擇離簇中心最遠(yuǎn)的點(diǎn)，而其余點(diǎn)選擇離所有已經(jīng)選取的點(diǎn)最遠(yuǎn)的點(diǎn);

(5) 剔除離群點(diǎn)：第一階段刪除在聚類過(guò)程中增長(zhǎng)非常緩慢的簇; 第二階段在聚類結(jié)束時(shí)含數(shù)據(jù)對(duì)象明顯少的簇.

3 基于CURE聚類算法改進(jìn)的原型選擇

基于聚類的原型選擇的動(dòng)機(jī)是快速執(zhí)行通過(guò)聚類挑選出有代表性的內(nèi)部點(diǎn)和邊界點(diǎn)，為了實(shí)現(xiàn)這一點(diǎn)，本文針對(duì)CURE層次聚類算法中對(duì)噪聲點(diǎn)不易判斷性，使用了共享鄰居密度計(jì)算每個(gè)樣例的密度，根據(jù)密度增值曲線對(duì)整個(gè)樣例集確定密度閾值，進(jìn)而確定噪聲點(diǎn).

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

另一方面，針對(duì)CURE選擇代表點(diǎn)的局限性，利用最大最小距離選擇代表點(diǎn)的方法代替CURE算法挑選代表點(diǎn)的算法，使得代表點(diǎn)能夠盡量分散，從而更好地代表該簇. 在此利用隨機(jī)產(chǎn)生的數(shù)據(jù)說(shuō)明該情況. 圖2(a)是利用CURE算法挑選出代表點(diǎn)的圖示，其中圓圈點(diǎn)為代表點(diǎn)，可見(jiàn)代表點(diǎn)集中在兩端，不能很好地反應(yīng)數(shù)據(jù)的形狀和分布信息. 圖2(b)中是利用算法2挑選的代表點(diǎn)，可以觀察到，代表點(diǎn)分散在每個(gè)邊緣地方，并選擇了適當(dāng)?shù)闹行狞c(diǎn)來(lái)做代表點(diǎn)，滿足分散點(diǎn)的特性，較好的描述了數(shù)據(jù)集的分布情況.

圖1 利用共享鄰居密度確定噪聲點(diǎn)

圖2 CURE與最大最小距離代表點(diǎn)選取結(jié)果

PSCURE算法的主要步驟如下：

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

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

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

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

圖3 PSCURE原型選擇算法在Pathbased數(shù)據(jù)集上的展示

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

圖4 PSCURE原型選擇算法在Flame people數(shù)據(jù)集上的展示

4 實(shí)驗(yàn)結(jié)果及分析

為了評(píng)估PSCURE原型選擇算法的有效性，該章節(jié)利用該算法與傳統(tǒng)的KNN[1]，經(jīng)典的CNN[4]、ENN[5]和最新的TRKNN[6]、PSC[7]、BNNT[8]和2NMST[10]算法在原型選擇的個(gè)數(shù)及分類準(zhǔn)確率方面進(jìn)行了實(shí)驗(yàn)比較. 為了達(dá)到這個(gè)目的，從UCI上下載10個(gè)數(shù)據(jù)集，數(shù)據(jù)集的描述如表1所示.

表1 UCI數(shù)據(jù)集

4.1 實(shí)驗(yàn)設(shè)計(jì)

本文使用10折交叉驗(yàn)證將數(shù)據(jù)集劃分為訓(xùn)練集和測(cè)試集，取平均值作為最終的測(cè)試結(jié)果. 在KNN實(shí)驗(yàn)中，選擇K=3、5、7中分類準(zhǔn)確率最高的值作為最終分類準(zhǔn)確率，距離度量采用的是歐氏距離. 為了精確度量算法的性能，本文使用分類準(zhǔn)確率和樣例的保留率兩個(gè)主要的考察指標(biāo). 分類準(zhǔn)確率表示針對(duì)測(cè)試樣例集利用分類器正確分類的樣例數(shù)與測(cè)試集總樣例數(shù)的比值. 保留率表示訓(xùn)練數(shù)據(jù)集經(jīng)過(guò)該算法處理之后保留下來(lái)的數(shù)據(jù)子集與訓(xùn)練集中樣本個(gè)數(shù)的比值. 為了方便我們把這兩個(gè)指標(biāo)分別記為Acc和Str. 公式分別如下：

其中，n1表示測(cè)試集個(gè)數(shù)，n2表示訓(xùn)練集個(gè)數(shù)，|Pr|表示被正確分類的樣例個(gè)數(shù)，|PS|表示算法最后保留下來(lái)的樣例集個(gè)數(shù).

4.2 實(shí)驗(yàn)結(jié)果

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

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

5 結(jié)束語(yǔ)

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

表2 PSCURE算法與KNN、PSC的準(zhǔn)確率和保留率

表3 算法PSCURE和CNN、ENN、TRKNN、BNNT、2NMST的準(zhǔn)確率和保留率的比較結(jié)果

圖5 表2中平均準(zhǔn)確率和保留率的散點(diǎn)圖

圖6 表3中平均準(zhǔn)確率和保留率的散點(diǎn)圖