基于擴展自然鄰居的無參分類方法*

曹文態,楊德剛,2,馮 驥,2

(1.重慶師范大學計算機與信息科學學院,重慶 401331; 2.教育大數據智能感知與應用重慶市工程研究中心(重慶師范大學),重慶 401331)

1 引言

近些年來，伴隨著工程和科學領域的持續發展，現實生活中產生了大量的可用數據。但是，隨著數據量的增加，利用傳統數據分析方法從海量數據中進行模式識別變得相對困難。作為數據挖掘領域的重要方法，分類分析方法已經被廣泛地運用于實際應用中的數據分析。在進行分類分析時，幾乎所有現有的分類器都是基于大量參數的，這些參數的設置也往往需要領域專家的先驗知識。隨著大數據時代的到來[1 - 4]，由于許多分類問題數據集中的數據分布通常都是未知的或者很難獲得的，因此更需要進行分類分析過程中的去參數研究。作為非參數分類器的典型代表之一，k-最近鄰kNN(k-Nearest Neighbor)分類器是從訓練集中找到和測試樣本最接近的k個訓練樣本，然后根據k個鄰居的主要分類信息來預測測試樣本的類別[5,6]。由于其模型的簡單性和高效性，kNN分類器成為了分類分析領域應用范圍最廣的方法之一。

由于kNN分類器工作機制簡單且效果相對較好，吸引了眾多研究者投入研究[7]，并將其應用于各個領域[8 - 10]。因此，kNN在許多不同學科中都有大量的應用[11 - 14]。然而，在使用kNN分類器的過程中還存在以下2個問題：

(1)kNN分類器的效率很大程度上取決于選擇的距離測度的類型，尤其是在大型高維數據庫中更為明顯。在某些應用中，數據結構非常復雜，因此相應的距離測量在計算上需要非常大的花銷[15,16]。對于每個待預測的對象，kNN分類器必須將其與數據庫中的所有其他樣本進行比較,對于龐大的數據庫,頻繁的比較操作會使kNN的實用性變差[17]。

(2)傳統的kNN方法對所有的測試樣本都采用固定的k值，而不考慮樣本的幾何位置和相關特性。因此，如果訓練集中的鄰域不是空間均勻的，則這些k最近鄰居可能不會在測試對象周圍對稱分布。在描述測試對象鄰域時，幾何位置可能比實際距離更重要。

針對以上問題，為了改進基于鄰域的分類器[18]，研究者們也提出了許多方法。此前，基于互k最近鄰MkNN(Mutual k-Nearest Neighbor)方法，Tang等[19]提出了一種利用雙向通信方式的擴展最近鄰居ENN(Extended Nearest Neighbor)分類的方法。與經典的kNN方法只考慮測試樣本的最近鄰居來進行分類決策不同，ENN方法不僅考慮了測試樣本的最近鄰居是誰，而且同時還考慮了誰以測試樣本作為其最近鄰居。

ENN方法的優點是分類決策依賴于所有可變的訓練數據，但是，ENN方法中有一個參數k，改變該參數，鄰域圖的大小和形狀也會改變，ENN中k的選取等參數選擇問題仍然存在。

為了克服ENN分類方法的上述局限性，本文提出了一種新的方法，即ENaN(Extended Natural Neighbor)方法。它既能保留ENN方法的優點，又解決了ENN方法對參數k選擇的問題，ENaN方法在訓練階段和測試階段，借助于自然鄰居NaN(Natural Neighbor)方法來選擇k的最佳值。

2 相關知識

本節中主要介紹擴展自然鄰居方法所使用到的ENN方法與NaN方法的一些基本概念。

2.1 ENN方法

ENN 方法以雙向通信的方式進行預測:它不僅考慮測試樣本的最近鄰居是誰，還考慮誰將測試樣本視為其最近鄰居。通過迭代地假設一個測試樣本的所有可能被預測的類別，ENN從所有訓練數據中提取出廣義分類統計值，并且能夠從數據的全局分布中學習，從而提高模式識別性能，為廣泛的數據分析應用提供強大的技術支持。

二分類問題 ENN 方法的廣義分類統計值(Generalized Class-wise Statistics)的定義如定義1所示:

定義1(廣義分類統計值) 對于基本的二分類問題，分類i的廣義分類統計值Ti定義如式(1)所示：

(1)

其中,S1和S2分別代表二分類問題中的2類樣本集，x是樣本集S中的一個樣本，ni是第i類樣本集的樣本數，k為用戶自定義鄰域參數。Ir(x,S)表示樣本x和它的第r個鄰居是否屬于同一個類，其定義如式(2)所示：

(2)

其中，KNNr(x,S)∈Si表示樣本集S中的樣本x的第r個鄰居也屬于類Si。

對于每個測試樣本，ENN決策規則可近似如式(3)所示：

fENN=arg max{Δnj+kj-kTj},j=1,2

(3)

其中,k是用戶自定義的鄰域參數，nj表示在類j中將測試樣本視為其k最近鄰居的樣本數，kj是類j中測試樣本的最近鄰居數，Tj代表原始類j的廣義分類統計值。

2.2 NaN方法

此前，重慶大學的Zhu等[20]提出了一種新的無參數最近鄰居方法，稱為自然鄰居(NaN)。NaN方法是受人類社會群體思想的啟發，屬于無標度最近鄰居方法的范疇，是一種有效的離群點檢測方法[21,22]。自然鄰居的思想對當前分類問題的解決有3個主要貢獻：

(1)自然鄰居方法可以根據不同數據集的局部特征，生成一個適用的鄰域圖[23]。這種鄰域圖可以識別數據集中的基本簇，特別是流形簇和噪聲。

(2)自然鄰居方法可以提供一個數值結果，即自然鄰居特征值NaNE(Natural Neighbor Eigenvalue)來代替傳統kNN方法中的參數k，并且可以根據不同的數據集動態地選擇NaNE的大小。

(3)每個點的自然鄰居數量是靈活的，這個值是一個0～NaNE的動態可變數。聚類中心點的鄰居數較多，噪聲的鄰居數為0。

NaN的方法被定義如下：

定義2(自然鄰居特征值NaNE) 當算法達到穩定搜索狀態時，自然鄰居特征值λ等于搜索輪數r。

λrr∈N{r|(?xi)(?xj)(r∈N)∧

(xi≠xj)→(xi∈KNNλ(xj))∧

(xj∈KNNr(xi))}

(4)

定義3(自然鄰居NaN) 當算法達到穩定搜索狀態時，互為鄰居的數據點互為自然鄰居。

xj∈NaN(xi)?(xi∈KNNλ(xj))∧

(xj∈KNNλ(xi))

(5)

定義4(自然鄰居鄰域圖NaNG(Natural Neighborhood Graph)) 當算法處于搜索穩定狀態時,由自然鄰居關系構成的鄰域圖為自然鄰居鄰域圖。

e(vi,vj)∈E?xj∈NaN(xi)

(6)

其中，e(vi,vj)表示以樣本vi和vj為頂點組成的邊，E為邊集。

3 ENaN分類方法

本節將詳細介紹NaN和ENN方法相結合的分類方法，并給出分類方法對應的步驟，分析方法的時間復雜度。

3.1 NaN方法和ENN方法的結合

ENN分類方法分為2個階段：訓練階段和測試階段。訓練階段用來計算每個類的廣義分類統計值Ti，并根據Ti構造加權kNN鄰域圖，以訓練樣本為頂點，樣本到其最近鄰居的距離為邊。在測試階段，首先假設測試樣本屬于某一個類，然后計算每個類的廣義分類統計值Ti。接著再假設它屬于另一個類，計算此時每個類的廣義分類統計值Ti。完成所有類別假設后，根據式(1)做出分類決策。

因此可以發現，ENN分類方法的核心在于式(1)中的廣義分類統計值Ti的計算，而Ti的取值極其依賴鄰域參數k的選擇。所以，與傳統的kNN方法類似，ENN方法的分類結果很大程度上依賴于鄰域參數k的選擇。圖1所示為kNN方法和ENN方法在一定k取值范圍內的分類精度的變化情況。

Figure 1 Classification accuracies of kNN and ENN methods with different k圖1 kNN和ENN方法在不同k下的分類精度

從圖1可以看出，在大多數情況下，ENN方法的分類精度明顯優于kNN方法的。此外，ENN仍然存在參數選擇問題，k值選取不當也會明顯降低分類精度。

本文提出的ENaN方法針對ENN方法的參數選取問題進行了改進，希望在沒有任何先驗知識的情況下選擇參數k，并且使分類精度更高。考慮到ENN方法2個階段的具體情況，ENaN方法將以不同的方式選擇鄰域參數。在訓練階段，ENN方法需要一個鄰域參數來度量訓練數據集的分布，在這種情況下，反映數據總體分布的NaNE可能是一個更好的選擇。為了說明數據集與其NaNE之間的關系，圖2中顯示了4個人工數據集的簡單示例。其中圖2a為Flame數據集， 由240條數據組成，分布形狀類似箭頭；圖2b為Train數據集，是任意形狀數據集，有582條數據，分為4類，且有多個噪聲數據；圖2c為Compound數據集，由399條數據組成；圖2d為3D_sprial數據集,形狀為三維空間的2根螺旋線，共300條數據。

圖2說明了NaNE的特性。首先，對于每個數據集，NaNE是動態可變的；其次，NaNE的取值也同時反映了當前數據集中任意數據點的自然鄰居上限。所以當用它作為鄰域參數計算類統計值比用ENN方法的廣義分類統計值更好。

Figure 2 Four different artificial data sets 圖2 4個不同的人工數據集

在測試階段，當未知樣本出現時，每個樣本的自適應鄰域會更準確。而在自然鄰居的概念中，每個點的鄰居數量不是固定的。自然鄰居搜索過程不受鄰域參數的限制，而這種動態鄰域值可以更準確地反映數據點之間的關系，使每個數據點根據自身的特征找到合適的鄰居。特別地，數據點的密度較大時，鄰居也更多，而邊緣點的自然鄰居較少。圖2中不同數據集的NaNG可以直觀地說明每個數據點的自然鄰域。圖3所示為2個UCI數據集中自然鄰居方法的動態鄰域值(為清楚顯示，只展示前100個點)。

Figure 3 Dynamic neighborhood value of natural neighbor method圖3 自然鄰居方法的動態鄰域值

3.2 用ENaN方法構造一個高效的分類算法

基于ENN方法和NaN方法的思想，本文提出了一個無需人為設定參數的高效分類方法ENaN。該方法主要分為2個階段：訓練階段和測試階段。

在訓練階段， ENaN方法提出了自然類統計值的概念，能夠在無需人為設置鄰域參數的情況下根據數據集的特點自適應地進行計算。自然類統計值定義如定義5所示：

定義5自然類統計值(Natural Class-wise statistics)對于類i的自然類統計值NTi定義如式(7)所示：

(7)

其中，Si表示分類i的樣本集，x表示訓練樣本集X中的一個訓練對象，ni是Si中的樣本數量，λ的值等于訓練數據的自然鄰居特征值。Ir(x,S)反映了樣本x和它的第r個鄰居是否屬于同一個類。

在該階段，加權kNN圖可以用來有效地計算給定測試樣本間的距離和自然鄰居，因此在自然類統計值計算步驟中，ENaN方法將加權kNN圖存儲并轉移到下一階段。ENaN分類的訓練階段如算法1所示：

算法1ENaN 分類方法:訓練階段

輸入:training data setXtraining。

輸出:weighted kNN graph,G=〈V,E〉; natural class-wise statistics for each class,NT={NT1,NT2,…,NTm}。

1: Create ak-d treeTfrom training data setXtraining;

2: ?xi∈X,NaN_Num(xi)=0;

3: CalculateNaNEof training data setXtrainingby usingk-d treeT;

4: LetNaNEbe the parameterkto build weighted kNN graphGby usingk-d treeT;

5:forall class of training data setXtrainingdo

6: Calculate the natural class-wise statisticsNTiby using weighted kNN graphG;

7:endfor

8:returnG=〈V,E〉,NT={NT1,NT2,…,NTm};

算法1的時間復雜度為O(m*lbm)，其中m為訓練數據集的大小。算法1首先建立數據集的k-d樹，該步驟的時間復雜度為O(m*lbm)，計算NaNE的時間復雜度為O(NaNE*m*lbm)。NaNE的取值在2～m，通常為6或7，對于某些高維或不規則的數據集，NaNE的取值一般大于20且小于30。對于每一類，建立加權kNN圖，計算出時間復雜度為O(m*lbm)。最后，計算自然類統計值的復雜度僅為O(m)。

在測試階段，算法的目標是確定測試樣本屬于訓練數據集中的哪個類。考慮到樣本的多樣性，本文以每個樣本的自然鄰居數作為其鄰域參數。因此，如果樣本在密度大的區域，進行分類時將考慮到更多的鄰居，而在稀疏區域，只能通過少量的幾個鄰居進行樣本分類。在測試階段，ENaN方法的輸入信息為算法1中得到的加權kNN圖和自然類統計值等，通過算法2可以對待測樣本進行分類，并輸出標簽信息。

ENaN分類方法的測試階段如算法2所示：

算法2ENaN分類方法:測試階段

輸入:training data setXtraining;testing data setXtesting;weighted kNN graph,G=〈V,E〉; natural class-wise statistics for each class,NT= {NT1,NT2,…,NTm}。

輸出:label set of testing data。

1:forall samplexiin testing data setXtestingdo

2: Calculate the number of its natural neighborNaN_Num(xi) in data setXtraining∪{xi} by using weighted kNN graphG;

3:forall class of training data setXtrainingdo

4: Assume samplexibelongs to current class;

5: Calculate the natural class-wise statisticsNTiby using weighted kNN graphG;

6:endfor

7: Calculate ENN classification predictionfENN;

8: Make classification decision of samplexi;

9:endfor

10:Combine all samples’ classification decisions as label set of testing data;

11:returnlabel set of testing data;

4 實驗及結果分析

所有的方法和實驗都運行在Matlab R2019b上。實驗中所用到的數據集將在4.1節和4.2節中分別進行介紹。

4.1 實驗1

實驗1所用到的15個真實數據集都來自加州大學歐文分校(UCI)的機器學習庫。表1所示為UCI數據集的屬性。

Table 1 Size and dimensions of all data sets表1 UCI數據集的大小和維度情況

從表2可以看出，ENaN方法在7個數據集上是精度最高的，而且在其他數據集上的精度也非常接近最好的結果。此外，ENaN方法在15個UCI數據集上的平均精度最高，而且在不同數據集上的結果相對穩定。同時，該方法是一種完全無鄰域參數的方法，這意味著不再需要為每個數據集選擇自適應參數k，這一優勢甚至在某種程度上比分類精度更為重要。

4.2 實驗2

為了更好地驗證本文方法的有效性，實驗2采用一組經過處理的人臉圖像數據集，人臉圖像數據集包含了40個人的400幅人臉圖像，每個人有10幅人臉圖像。每幅圖像的原始大小是92×112。數據集的人臉圖像樣示例如圖4所示。

圖4選取了該數據集中的5組人臉數據進行展示。在實驗中，為了避免過大的計算量，首先對圖像進行切割，每幅圖像被處理成32×32=1024維的向量。將數據集中的圖像按10折交叉驗證法劃分訓練集和測試集，以進行訓練和算法分類精度的測試。在人臉圖像數據集上，ENN方法和ENaN方法的分類精度如圖5所示。

Table 2 Classification accuracy of each method with different k 表2 不同k值下各方法的分類精度 %

Figure 4 Some examples of face image data set圖4 人臉圖像數據集部分示例

特別需要說明的是，ENaN方法無需設置鄰域參數，因此在ENaN方法的鄰域參數的位置標注為ENaN。從圖5可以看出，本文提出的ENaN方法在該人臉圖像數據集上也獲得了最高的檢測精度。ENaN方法無需設置鄰域參數，并且能夠獲取穩定的檢測結果。在ENN方法中，當鄰域參數k設置為3時，方法的平均檢測效果與ENaN方法的接近，但因其k值需要人為依據經驗設置，其在某些復雜數據集上的檢測結果可能因k值的選取不當而會導致急劇下滑。

Figure 5 Classification accuracy of each method with different neighborhood parameters on face image data set 圖5 人臉圖像數據集上各方法 在不同鄰域參數下的分類精度

在人臉圖像數據集上的實驗中，除了將ENaN方法與ENN方法進行對比之外，還與一些常見的分類方法也進行了實驗結果對比，如決策樹、LDA、AdaBoost、CNN等分類方法。其中決策樹方法的分類準則采用基尼指數，最大分裂數為100。LDA方法的模型類型為線性判別，協方差的結構為對角，實驗中的最佳投影維數為19。AdaBoost方法的學習器類型為決策樹，最大分裂數為20，學習器數量為30，學習率為0.1。CNN方法的卷積層為20個5×5的濾波器，池化層大小為2×2,步幅為2，全連接層共有40個輸出。具體實驗結果如圖6所示。

Figure 6 Classification accuracies of common classification methods on face image data set 圖6 常用分類方法在人臉圖像數據集上的分類精度

從圖6中可以發現，在這5個方法中，本文提出的ENaN方法的分類精度高于決策樹、LDA和AdaBoost分類方法的，僅次于CNN分類方法，且與其精度相差不大。但是，由于CNN方法需要人為設置大量的參數，可能會因為參數的設置不合適得不到較好的分類結果。而ENaN方法無需設置鄰域參數，在實際數據集的分類問題上還是有優勢的。

5 結束語

本文提出了一種新的基于擴展最近鄰居的無參數分類方法，用自然鄰居方法較好地解決了分類方法在訓練階段和測試階段對于鄰域參數k的選取問題。實驗結果表明，與傳統方法人為設置鄰域參數相比，ENaN分類方法能夠在無需設置鄰域參數的情況下獲取更為準確的檢測結果。ENaN分類方法提高了分類結果的準確性，并且對不同類型的數據集都具有更好的適應性，很好地解決了鄰域參數k需要靠人為經驗去選擇的難題。

分類分析具有極為廣闊的應用空間，本文所提出的ENaN方法也仍然有許多改進的空間。未來還將在更多的數據集上驗證ENaN方法的實用性，并進一步推動分類方法中去參數化的研究與應用。同時，將探索針對流形數據交疊與自動數據標記等問題進行優化的方法，并嘗試將去參數化的思想應用于分類決策規則的改進，從而進一步提高分類方法的效率。