曹文態(tài),楊德剛,2,馮 驥,2

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

1 引言

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

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

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

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

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

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

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

2 相關(guān)知識

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

2.1 ENN方法

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

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

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

(1)

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

(2)

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

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

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

(3)

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

2.2 NaN方法

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

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

(2)自然鄰居方法可以提供一個數(shù)值結(jié)果，即自然鄰居特征值NaNE(Natural Neighbor Eigenvalue)來代替?zhèn)鹘y(tǒng)kNN方法中的參數(shù)k，并且可以根據(jù)不同的數(shù)據(jù)集動態(tài)地選擇NaNE的大小。

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

NaN的方法被定義如下：

定義2(自然鄰居特征值NaNE) 當(dāng)算法達(dá)到穩(wěn)定搜索狀態(tài)時，自然鄰居特征值λ等于搜索輪數(shù)r。

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

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

(xj∈KNNr(xi))}

(4)

定義3(自然鄰居NaN) 當(dāng)算法達(dá)到穩(wěn)定搜索狀態(tài)時，互為鄰居的數(shù)據(jù)點(diǎn)互為自然鄰居。

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

(xj∈KNNλ(xi))

(5)

定義4(自然鄰居鄰域圖NaNG(Natural Neighborhood Graph)) 當(dāng)算法處于搜索穩(wěn)定狀態(tài)時,由自然鄰居關(guān)系構(gòu)成的鄰域圖為自然鄰居鄰域圖。

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

(6)

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

3 ENaN分類方法

本節(jié)將詳細(xì)介紹NaN和ENN方法相結(jié)合的分類方法，并給出分類方法對應(yīng)的步驟，分析方法的時間復(fù)雜度。

3.1 NaN方法和ENN方法的結(jié)合

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

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

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

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

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

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

Figure 2 Four different artificial data sets 圖2 4個不同的人工數(shù)據(jù)集

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

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

3.2 用ENaN方法構(gòu)造一個高效的分類算法

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

在訓(xùn)練階段， ENaN方法提出了自然類統(tǒng)計(jì)值的概念，能夠在無需人為設(shè)置鄰域參數(shù)的情況下根據(jù)數(shù)據(jù)集的特點(diǎn)自適應(yīng)地進(jìn)行計(jì)算。自然類統(tǒng)計(jì)值定義如定義5所示：

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

(7)

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

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

算法1ENaN 分類方法:訓(xùn)練階段

輸入: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的時間復(fù)雜度為O(m*lbm)，其中m為訓(xùn)練數(shù)據(jù)集的大小。算法1首先建立數(shù)據(jù)集的k-d樹，該步驟的時間復(fù)雜度為O(m*lbm)，計(jì)算NaNE的時間復(fù)雜度為O(NaNE*m*lbm)。NaNE的取值在2～m，通常為6或7，對于某些高維或不規(guī)則的數(shù)據(jù)集，NaNE的取值一般大于20且小于30。對于每一類，建立加權(quán)kNN圖，計(jì)算出時間復(fù)雜度為O(m*lbm)。最后，計(jì)算自然類統(tǒng)計(jì)值的復(fù)雜度僅為O(m)。

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

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 實(shí)驗(yàn)及結(jié)果分析

所有的方法和實(shí)驗(yàn)都運(yùn)行在Matlab R2019b上。實(shí)驗(yàn)中所用到的數(shù)據(jù)集將在4.1節(jié)和4.2節(jié)中分別進(jìn)行介紹。

4.1 實(shí)驗(yàn)1

實(shí)驗(yàn)1所用到的15個真實(shí)數(shù)據(jù)集都來自加州大學(xué)歐文分校(UCI)的機(jī)器學(xué)習(xí)庫。表1所示為UCI數(shù)據(jù)集的屬性。

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

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

4.2 實(shí)驗(yàn)2

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

圖4選取了該數(shù)據(jù)集中的5組人臉數(shù)據(jù)進(jìn)行展示。在實(shí)驗(yàn)中，為了避免過大的計(jì)算量，首先對圖像進(jìn)行切割，每幅圖像被處理成32×32=1024維的向量。將數(shù)據(jù)集中的圖像按10折交叉驗(yàn)證法劃分訓(xùn)練集和測試集，以進(jìn)行訓(xùn)練和算法分類精度的測試。在人臉圖像數(shù)據(jù)集上，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 人臉圖像數(shù)據(jù)集部分示例

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

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

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

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

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

5 結(jié)束語

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

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