蔡瑞光，張德生，張 曉

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

分類任務(wù)就是通過訓(xùn)練與學(xué)習(xí)得到一個(gè)分類模型，把每個(gè)屬性特征集映射到一個(gè)預(yù)先定義的類標(biāo)號(hào)[1]。分類算法[2]是一種應(yīng)用極其廣泛的數(shù)據(jù)分析方法，在模式識(shí)別領(lǐng)域?qū)儆诒O(jiān)督學(xué)習(xí)[3]。監(jiān)督學(xué)習(xí)是通過一組已知類別的樣本，訓(xùn)練出一個(gè)目標(biāo)函數(shù)，利用目標(biāo)函數(shù)去判斷新數(shù)據(jù)的類別。近年來，各種分類算法不斷被提出，例如，CART[4]、C4.5[5]、RIPPER[6]、KNN[7]、BBN[8]、ANN[9]、SVM[10]等。目前這些分類算法及其改進(jìn)算法已被廣泛應(yīng)用于商務(wù)、醫(yī)學(xué)、科學(xué)與工程等領(lǐng)域。然而，隨著科學(xué)技術(shù)的發(fā)展和數(shù)據(jù)收集、數(shù)據(jù)存儲(chǔ)技術(shù)的快速進(jìn)步，隨之而來的是數(shù)據(jù)數(shù)量和數(shù)據(jù)自身維度的大幅度增加，但是數(shù)據(jù)質(zhì)量并未得到提升。因此，分類算法在數(shù)據(jù)分析上面臨著更多的困難和更大的挑戰(zhàn)，在分類準(zhǔn)確率和算法復(fù)雜度上往往難以得到滿意的結(jié)果。

KNN[11]算法是機(jī)器學(xué)習(xí)領(lǐng)域的一個(gè)經(jīng)典算法，其有理論簡單、易于實(shí)現(xiàn)等優(yōu)點(diǎn)。該算法首先設(shè)置一個(gè)參數(shù)k，表示近鄰樣本的個(gè)數(shù)，然后根據(jù)待分類樣本到每個(gè)訓(xùn)練樣本的歐幾里德距離，選取距離最近的k個(gè)樣本作為近鄰，最后根據(jù)多數(shù)投票原則來判斷待分類樣本的類標(biāo)號(hào)。然而KNN 算法也有明顯的不足之處：參數(shù)k的設(shè)定具有主觀敏感性，分類結(jié)果受k值影響較大；k鄰域中的每個(gè)近鄰對(duì)分類結(jié)果的貢獻(xiàn)都一樣；決策函數(shù)只考慮單一的因素，例如多數(shù)投票原則或最短距離原則，其分類性能有待進(jìn)一步提高。

針對(duì)KNN 算法存在的不足，Dudani[12]提出了一種典型的距離加權(quán)k近鄰分類算法（WKNN），該算法的主要思想是不同的近鄰對(duì)于分類有不同的分類貢獻(xiàn)并且真正的近鄰點(diǎn)應(yīng)該具有更多的貢獻(xiàn)。Mitani和Hamamoto[13]提出了一種基于局部均值的非參數(shù)分類算法（LMKNN），該算法的主要思想是在每一個(gè)類中為待分類樣本選取近鄰，根據(jù)每類近鄰的局部均值進(jìn)行分類。Zeng等[14]提出了偽近鄰算法（PNN），該算法的主要思想是利用每類中的k個(gè)近鄰的組合來構(gòu)造偽近鄰，尋找最近的偽近鄰進(jìn)行分類。Gou 等[15]提出了一種基于局部均值的偽近鄰算法（LMPNN），該算法作為PNN算法的改進(jìn)，其思想是將每類中的k個(gè)最近鄰用k個(gè)局部均值來代替，以便找到更加準(zhǔn)確的偽最近鄰。Biswas 等[16]提出參數(shù)無關(guān)的模糊加權(quán)k最近鄰分類算法（PIFWKNN），該算法提出了一種參數(shù)獨(dú)立的模糊k最近鄰，并且進(jìn)一步優(yōu)化了全局k值。Ertugral 和Tagluk[17]提出了k近鄰的改進(jìn)算法（DNN），該算法是一種基于D近鄰點(diǎn)的DNN加權(quán)樣本方法。

上述幾種基于KNN的改進(jìn)算法雖然都具有較好的分類效果，但是噪聲點(diǎn)和異常點(diǎn)對(duì)分類準(zhǔn)確率的影響并未降到最低，其中LMPNN算法對(duì)異常點(diǎn)和噪聲點(diǎn)仍然敏感。本文在LMPNN算法的基礎(chǔ)上進(jìn)行改進(jìn)，提出了一種基于雙向選擇的偽近鄰算法。

1 預(yù)備知識(shí)

為了方便說明和理解后面的內(nèi)容，本章主要介紹了LMPNN算法以及互近鄰概念。

1.1 符號(hào)說明

本文常用的符號(hào)整理如表1所示。

表1 符號(hào)說明表

1.2 LMPNN算法

在特征空間Rd中，假定訓(xùn)練集有L個(gè)類標(biāo)號(hào)ω1,ω2,…,ωL，并且是訓(xùn)練集中類別為ωj的訓(xùn)練樣本集合。N和Nj分別代表訓(xùn)練集T中樣本的個(gè)數(shù)和類別為ωj的訓(xùn)練集Tωj中樣本的個(gè)數(shù)。在LMPNN算法中，待測(cè)試樣本x的類標(biāo)簽通過以下步驟產(chǎn)生：

算法1 LMPNN算法

輸入：近鄰個(gè)數(shù)k，待測(cè)試樣本x，訓(xùn)練集T=類標(biāo)號(hào)ωj(j=1,2,…,L)，屬于類別ωj的訓(xùn)練集，屬于類別ωj的訓(xùn)練樣本個(gè)數(shù)Nj。

輸出：待測(cè)試樣本x的類別c。

步驟1 計(jì)算待測(cè)試樣本x到Tωj(j=1,2,…),L中樣本的歐氏距離[18]：

步驟2 將類別ωj中的歐氏距離按升序排列，并取前k個(gè)近鄰：

步驟3 計(jì)算待測(cè)試樣本x在類別ωj中第i個(gè)近鄰的局部均值向量：

步驟4 給每一類中的局部均值向量分配不同的權(quán)重。在ωj類中，第i個(gè)局部均值向量的權(quán)值為：

步驟5 計(jì)算每類ωj中的偽近鄰。

步驟6 預(yù)測(cè)待測(cè)樣本x的類標(biāo)號(hào)c：

1.3 互近鄰

定義1（互近鄰選取準(zhǔn)則[19-20]）在T*={y1,y2,…,yNj,x}中，給定任意樣本yi∈T*(1≤i≤Nj+1)，yi在特征空間Rd中的k鄰域的定義為：

x的k鄰域Nk(x)，即為x的k近鄰集合，yi的k鄰域Nk(yi)，即為yi的k近鄰集合。若x∈Nk(yi)且yi∈Nk(x)，則稱yi和x是互近鄰。即：

圖1 簡單清楚地說明了在定義1 下的互近鄰的作用。x1的近鄰為x2、x3和x6，x2的近鄰為x3、x4和x5，x3的近鄰為x1、x2和x10，x6的近鄰為x7、x8和x9。根據(jù)互近鄰定義可知，x1和x3為互近鄰，將x3加入x1的互近鄰集合M。x2和x6為x1的近鄰，不是互近鄰。

圖1 x1 與它的近鄰

2 本文算法

通過對(duì)LMPNN算法的描述可知，該算法對(duì)異常點(diǎn)和噪聲點(diǎn)仍然敏感的問題，將影響最終的分類正確率。為此，提出一種基于雙向選擇的偽近鄰算法（BS-PNN），克服異常點(diǎn)和噪聲點(diǎn)的敏感性問題，提高近鄰集合質(zhì)量，運(yùn)用更加符合實(shí)際的決策函數(shù)。

2.1 改進(jìn)的類可信度

在圖2 中，當(dāng)決策函數(shù)采用多數(shù)投票原則時(shí)，測(cè)試樣本1 的近鄰個(gè)數(shù)k取3 時(shí)，屬于第1 類，測(cè)試樣本2 的近鄰個(gè)數(shù)k取7時(shí)，屬于第2類；當(dāng)決策函數(shù)采用最短距離原則時(shí)，測(cè)試樣本1 的近鄰個(gè)數(shù)k取3 時(shí)，屬于第2類，測(cè)試樣本2的近鄰個(gè)數(shù)k取7時(shí)，屬于第1類。對(duì)于基于KNN的改進(jìn)算法，當(dāng)采用不同的決策函數(shù)時(shí)，測(cè)樣樣本具有不同的類別，對(duì)分類器的精度有一定的影響。在分類算法中，應(yīng)運(yùn)用考慮更加全面的決策函數(shù)，本文提出了改進(jìn)了改進(jìn)的類可信度。概念如下：

圖2 測(cè)試樣本與k 近鄰

定義2 設(shè)ωj(j=1,2,…),L代表類別，x為待分類樣本，為類別ωj中屬于x的互近鄰，nj為x在類別ωj中的互近鄰樣本數(shù)，且n=n1+n2+…+nL，wi=定義

稱其為x對(duì)類別ωj的類可信度。

在式（8）中，如果T*(ωj,x)越小，x屬于類ωj的可能就越大。為x與類ωj中nj個(gè)局部均值加權(quán)的平均距離。類可信度T*(ωj,x)由互近鄰數(shù)和平均加權(quán)距離兩部分組成。一方面，每類中的近鄰個(gè)數(shù)nj越大，T*(ωj,x)值越小，x屬于類ωj的可能性越大；另一方面，每類中局部均值加權(quán)距離的平均距離越小，T*(ωj,x)值越小，x屬于類別ωj的可能性越大。

本文是將文獻(xiàn)[21]類可信度T(ωj,x)中調(diào)整為將每類中nj個(gè)最近鄰用nj個(gè)局部均值來代替，并且考慮最近鄰的分類貢獻(xiàn)。具體分析如下：

d受單個(gè)近鄰影響較大，如果近鄰集合中含有噪聲點(diǎn)或異常點(diǎn)，決策函數(shù)受一個(gè)近鄰點(diǎn)的影響很大，甚至?xí)淖儨y(cè)試樣本的分類結(jié)果。則運(yùn)用類均值考慮了所有近鄰的分布情況，決策函數(shù)受一個(gè)近鄰樣本點(diǎn)的影響較小。在實(shí)際應(yīng)用中，每一個(gè)近鄰對(duì)分類結(jié)果的貢獻(xiàn)都不一樣，應(yīng)該考慮每一個(gè)近鄰的權(quán)重。在中，wi為每一個(gè)賦予不同的權(quán)重，距離x越近的局部均值所占權(quán)重越大。

本文提出的改進(jìn)的類可信度綜合考慮了每類中近鄰樣本間的局部均值、加權(quán)距離和近鄰個(gè)數(shù)的分類貢獻(xiàn)這三個(gè)方面，更加符合實(shí)際應(yīng)用。

2.2 基于雙向選擇的偽近鄰算法

在LMPNN 算法中，決策函數(shù)采用最短距離原則，選取測(cè)試樣本的近鄰集合時(shí)并未識(shí)別離群點(diǎn)和噪聲點(diǎn)，只是通過加權(quán)局部均值在一定程度上減少了異常點(diǎn)對(duì)分類結(jié)果的影響，異常點(diǎn)對(duì)分類器的影響并未完全消除。本文在LMPNN算法的基礎(chǔ)上進(jìn)行改進(jìn)，提出了基于雙向選擇的偽近鄰算法（BS-PNN）。

BS-PNN算法的基本思想如下：在類別為ωj的訓(xùn)練集Tωj中選取近鄰，讓測(cè)試樣本x和訓(xùn)練樣本根據(jù)互近鄰定義進(jìn)行雙向選擇，只有當(dāng)雙方為互近鄰時(shí)，才將訓(xùn)練樣本添加進(jìn)測(cè)試樣本x的近鄰集合Mj(x)，互近鄰定義可以識(shí)別近鄰集中的噪聲點(diǎn)和異常點(diǎn)，進(jìn)行雙向選擇的近鄰更加可靠。經(jīng)過雙向選擇后，ωj類中測(cè)試樣本x的近鄰個(gè)數(shù)可能會(huì)發(fā)生變化，需要重新計(jì)算近鄰樣本數(shù)。本文的決策函數(shù)從近鄰個(gè)數(shù)和局部均值加權(quán)的平均距離兩方面考慮，使BS-PNN算法更加符合實(shí)際。本文算法的具體步驟如下：

算法2 BS-PNN算法

輸入：近鄰個(gè)數(shù)k，待測(cè)試樣本x，訓(xùn)練集T=類標(biāo)號(hào)ωj(j=1,2,…,L)，屬于類別ωj的訓(xùn)練集屬于類別ωj的訓(xùn)練樣本個(gè)數(shù)Nj。

輸出：待測(cè)試樣本x的類標(biāo)號(hào)c。

步驟1 計(jì)算待測(cè)試樣本x在類ωj中的k個(gè)近鄰，表示為

步驟4 在Mj(x)中，計(jì)算近鄰的局部均值距離及近鄰個(gè)數(shù)nj。

步驟5 給每一類中的局部均值向量分配不同的權(quán)重。在類ωj中，第i個(gè)局部均值向量的權(quán)值為：

步驟6 計(jì)算每一個(gè)類別中的偽近鄰。

步驟7 計(jì)算改進(jìn)的類可信度。

步驟8 預(yù)測(cè)待測(cè)樣本x的類標(biāo)號(hào)c：

該算法的流程圖如圖3所示。

圖3 BS-PNN算法流程圖

2.3 算法復(fù)雜度分析

假設(shè)數(shù)據(jù)集的規(guī)模為N，數(shù)據(jù)維度為d，近鄰個(gè)數(shù)為k，類別個(gè)數(shù)為L?；陔p向選擇的偽近鄰算法的時(shí)間復(fù)雜度主要來源于5 個(gè)方面：（1）計(jì)算測(cè)試樣例到各個(gè)類的距離，時(shí)間復(fù)雜度為O()Nd+Nk；（2）利用互近鄰原理去除噪聲樣本，并選擇有價(jià)值的近鄰，時(shí)間復(fù)雜度為O(kdM+2kM)；（3）計(jì)算每一個(gè)類中的局部均值向量，時(shí)間復(fù)雜度為O(2d)；（4）權(quán)重ωj被分配給每個(gè)類別的第j個(gè)局部均值向量，并且找到每個(gè)類別的基于局部均值的偽鄰居，該步驟要求O()3kM；（5）使用決策函數(shù)判別測(cè)試樣例的類標(biāo)號(hào)，時(shí)間復(fù)雜度為O()3M。所以總的時(shí)間復(fù)雜度為O()Nd+Nk+kdM。雖然基于雙向選擇的偽近鄰算法的時(shí)間復(fù)雜度大于基于改進(jìn)的KNN分類算法，但是算法在運(yùn)行時(shí)，執(zhí)行效率較高。

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

為了進(jìn)一步驗(yàn)證本文所提出的基于雙向選擇的偽近鄰算法的分類性能，在公開數(shù)據(jù)集KEEL和UCI中選擇了15個(gè)數(shù)據(jù)集，在MATLAB R2014a環(huán)境下進(jìn)行仿真實(shí)驗(yàn)，并與KNN、DWKNN、LMKNN、PNN、LMPNN、DNN以及P-KNN這7個(gè)分類算法進(jìn)行了比較。

3.1 數(shù)據(jù)集介紹

本文的15 個(gè)數(shù)據(jù)集中包括3 個(gè)規(guī)模較大的數(shù)據(jù)集letter、thyroid 和sparn 和12 個(gè)規(guī)模較小的數(shù)據(jù)集bupa、ionosphere、balance、diagnostic、musk、wdbc、wine、iris、dermatology、zoo、vehicle和sonar。

數(shù)據(jù)集的主要信息見表2，它們分別是數(shù)據(jù)集名稱、名稱縮寫、樣本數(shù)、屬性數(shù)以及類別數(shù)。其中數(shù)據(jù)集的特征維數(shù)從4維到167維，類別數(shù)從2類到10類，這樣可以更有效的驗(yàn)證本文所提出的算法的分類性能。

表2 數(shù)據(jù)集描述

3.2 實(shí)驗(yàn)設(shè)計(jì)和結(jié)果

為了驗(yàn)證本文所提出的分類算法的可行性和有效性，以表2 中的數(shù)據(jù)為實(shí)驗(yàn)數(shù)據(jù)，以分類準(zhǔn)確率作為評(píng)價(jià)標(biāo)準(zhǔn)比較基于雙向選擇的偽近鄰算法和其他基于KNN的改進(jìn)算法的分類性能。

準(zhǔn)確率又稱為查準(zhǔn)率，是指分類器在測(cè)試集中對(duì)測(cè)試樣例進(jìn)行分類時(shí)，正確判斷的樣本數(shù)占總樣本數(shù)的比例，它反映了分類結(jié)果的好壞。其計(jì)算方法如下：

其中，A為被分類器準(zhǔn)確判斷類標(biāo)號(hào)的樣本數(shù)，B為被分類器錯(cuò)誤判斷類標(biāo)號(hào)的樣本數(shù)。

在本文的實(shí)驗(yàn)中，均采用m折交叉驗(yàn)證法crossvalidation將數(shù)據(jù)集隨機(jī)均等的分為m份，依次拿1份作為測(cè)試集，其余m-1 份作為訓(xùn)練集，進(jìn)行m次交叉驗(yàn)證，并迭代100 次，取平均準(zhǔn)確率。根據(jù)數(shù)據(jù)集中樣本數(shù)量的多少，選擇合適的m折交叉驗(yàn)證。當(dāng)樣本數(shù)量較小時(shí)，選擇3 折或5 折交叉驗(yàn)證；當(dāng)樣本數(shù)量較大時(shí)，選擇10折交叉驗(yàn)證。

本文所提出的BS-PNN 算法以及所有對(duì)比算法均受近鄰個(gè)數(shù)k的影響。在本文的仿真實(shí)驗(yàn)中，對(duì)k值采用逐一驗(yàn)證的方法。具體設(shè)置如下：首先k的取值范圍為1 到15；其次，重復(fù)100 次m折交叉驗(yàn)證得到每個(gè)k值所對(duì)應(yīng)的平均準(zhǔn)確率，將平均準(zhǔn)確率最高時(shí)所對(duì)應(yīng)的k值選擇為最優(yōu)k值。實(shí)驗(yàn)結(jié)果都是在最優(yōu)k值下取得的，如表3所示。

3.3 結(jié)果分析

表3中記錄了BS-PNN算法與其他7種分類算法在15 個(gè)實(shí)際數(shù)據(jù)集上的分類準(zhǔn)確率。由表3 可知，除letter、iris 和thyr 這3 個(gè)數(shù)據(jù)集以外，BS-PNN 算法對(duì)其他數(shù)據(jù)集的分類準(zhǔn)確率均要高于其余7種算法，尤其在iono、wdbc、wine、vehi和sonar這5個(gè)數(shù)據(jù)集上的分類準(zhǔn)確率得到了明顯的提升。letter 數(shù)據(jù)集的最高準(zhǔn)確率在LMPNN 分類器上為96.93%，在BS-PNN 的準(zhǔn)確率為96.61%，雖略低于LMPNN 和P-KNN 的分類準(zhǔn)確率，但仍高于其他6 種對(duì)比算法。iris 和thyr 這2 個(gè)數(shù)據(jù)集的最高準(zhǔn)確率分別在DWKNN 和P-KNN 分類器上取得，BS-PNN的分類準(zhǔn)確率雖略低，但仍高于大多數(shù)對(duì)比算法的準(zhǔn)確率。PIW-LMPNN 在15 個(gè)數(shù)據(jù)集中獲得了最高的平均準(zhǔn)確率（如圖4所示）。

圖4 分類算法的準(zhǔn)確率均值比較

表3 BS-PNN與其他比較算法的平均準(zhǔn)確率 %

本文所提出的BS-PNN算法具有良好的實(shí)驗(yàn)表現(xiàn)，可以從以下兩方面來解釋：一方面，在進(jìn)行仿真實(shí)驗(yàn)時(shí)，該算法相對(duì)于基于KNN 的改進(jìn)算法來說，它利用互近鄰定義來選擇每一個(gè)近鄰點(diǎn)，讓測(cè)試樣本和近鄰樣本進(jìn)行雙向選擇，在一定程度上可以剔除近鄰集合中的噪聲點(diǎn)和異常點(diǎn)。因?yàn)榻忺c(diǎn)對(duì)判斷測(cè)試樣本的類別起決定性作用，當(dāng)近鄰點(diǎn)的質(zhì)量被提高時(shí)，分類結(jié)果也隨之被提高；另一方面，在基于雙向選擇的偽近鄰算法中，經(jīng)過互近鄰定義選擇的每類中的近鄰個(gè)數(shù)是不一致的，所以本文在分類準(zhǔn)則中，將近鄰樣本自身信息、近鄰樣本間的局部均值信息、權(quán)重以及近鄰樣本個(gè)數(shù)相結(jié)合，從近鄰樣本數(shù)量和距離兩個(gè)方面更加充分地考慮了實(shí)際情況，從而提高了分類器的精度。

4 結(jié)束語

本文提出了一種基于雙向選擇的偽近鄰算法（BS-PNN）。首先，該算法通過引入互近鄰概念來選擇測(cè)試樣例的真正近鄰點(diǎn)，然后通過改進(jìn)的類可信度計(jì)算出每一個(gè)類與測(cè)試樣本的相似度，最后通過決策函數(shù)得出測(cè)試樣本的類別。通過在真實(shí)數(shù)據(jù)集和人工合成數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，可知BS-PNN算法的分類性能優(yōu)于其他基于KNN 的改進(jìn)算法，同時(shí)該算法的復(fù)雜度類似于LMPNN 分類器的算法復(fù)雜度。本文下一步的研究工作，將結(jié)合實(shí)際問題來進(jìn)一步探索KNN 改進(jìn)算法的有效性。