沈?qū)W利，秦鑫宇,2+

1.遼寧工程技術(shù)大學(xué) 軟件學(xué)院，遼寧 葫蘆島 125105

2.中國(guó)科學(xué)院海西研究院 泉州裝備制造所，福建 泉州 362216

分類作為數(shù)據(jù)挖掘領(lǐng)域的重要研究?jī)?nèi)容之一，對(duì)其相關(guān)算法的研究已有很長(zhǎng)的歷史，如今隨著Internet 的飛速發(fā)展，每天都有大量來自醫(yī)療、商業(yè)、科學(xué)及日常生活等方方面面的數(shù)據(jù)產(chǎn)生，如何從海量的數(shù)據(jù)提取有效的信息，這就需要用到某種數(shù)據(jù)挖掘算法對(duì)數(shù)據(jù)進(jìn)行分類。目前，比較常見的數(shù)據(jù)分類算法主要有：支持向量機(jī)（support vector machine，SVM）、決策樹（decision tree，DT）、樸素貝葉斯（naive Bayes，NB）、深度神經(jīng)網(wǎng)絡(luò)（deep neural networks，DNN）、K最近鄰（Knearest neighbor，KNN）等。其中K最近鄰算法[1]因其在分類任務(wù)中簡(jiǎn)單且效果良好的特點(diǎn)被廣泛應(yīng)用，基本思想是：在向量空間中，通過計(jì)算每一條待測(cè)樣本與訓(xùn)練樣本之間的距離（或相似性），從訓(xùn)練樣本中找出與待測(cè)樣本最相似的K個(gè)最近鄰樣本，然后對(duì)這K個(gè)樣本的所屬類別進(jìn)行投票，以此判定待測(cè)樣本的最終歸屬類別。然而，當(dāng)面臨高維度大數(shù)據(jù)量的訓(xùn)練樣本時(shí)，由于KNN 分類需要逐個(gè)計(jì)算與訓(xùn)練樣本的相似程度，高昂的計(jì)算開銷使其效率大幅降低。

如何對(duì)此進(jìn)行改進(jìn)以提高KNN 算法在處理規(guī)模較大的高維度樣本時(shí)的效率，成為數(shù)據(jù)挖掘領(lǐng)域一個(gè)極為關(guān)注的問題，對(duì)此有不少學(xué)者提出了自己的改進(jìn)算法，大致分為以下幾類：

（1）從構(gòu)造適應(yīng)數(shù)據(jù)特性的度量角度提升KNN的性能。文獻(xiàn)[2]提出了一種基于Finsler 度量的KNN算法，該算法使用Finsler 作為樣本間距離的度量方式，通過分析樣本的固有屬性，進(jìn)而賦予樣本間距離度量不同的權(quán)重，使算法的分類性能得以提升。文獻(xiàn)[3]將卡方距離作為KNN 算法的度量函數(shù)，采用靈敏度法進(jìn)行特征權(quán)重計(jì)算，克服了歐氏距離對(duì)每個(gè)特征量賦予相同權(quán)重的缺點(diǎn)，提高了KNN 的分類精度。文獻(xiàn)[4]提出一種針對(duì)異構(gòu)非均衡數(shù)據(jù)的分類方法，將數(shù)據(jù)集劃分為若干均衡的數(shù)據(jù)子集，對(duì)每個(gè)子集采用異構(gòu)距離作為KNN 算法中選擇K個(gè)近鄰樣本的度量，并結(jié)合Adaboost進(jìn)行迭代增強(qiáng)，使得KNN 在異構(gòu)非均衡數(shù)據(jù)集上的性能有所提升。

（2）采用特定的優(yōu)化方式降低需要進(jìn)行相關(guān)性度量的樣本數(shù)，從而減小計(jì)算開銷。文獻(xiàn)[5]對(duì)于KNN 算法在樣本相似度計(jì)算方面開銷大的問題提出了基于冗余度的訓(xùn)練樣本裁剪方法，將待訓(xùn)練樣本的同類密度作為冗余度，針對(duì)冗余度高的樣本進(jìn)行適當(dāng)裁剪，進(jìn)而大幅減少了訓(xùn)練樣本數(shù)量，并使得類的分布趨于均勻，KNN 計(jì)算量得以降低。文獻(xiàn)[6]針對(duì)KNN 對(duì)不平衡數(shù)據(jù)敏感的問題，提出了Direct-CSKNN 和Distance-CS-KNN 兩種方法，以最小化成本敏感學(xué)習(xí)中的誤分類成本，并采用平滑、特征選擇和整體選擇等策略來提升方法的性能，使KNN 誤分類成本得以降低。文獻(xiàn)[7]根據(jù)香農(nóng)熵理論，通過計(jì)算信息增益查詢對(duì)分類結(jié)果影響最大的特征，并根據(jù)該特征對(duì)原始訓(xùn)練樣本集進(jìn)行劃分，構(gòu)造子集，從而有效降低了KNN 算法的時(shí)間復(fù)雜度。

（3）采用特征加權(quán)的方式實(shí)現(xiàn)分類精度的提升。文獻(xiàn)[8-9]提出基于特征加權(quán)的KNN 算法，文獻(xiàn)[8]給不同特征賦予不同權(quán)值，突出重要特征的作用，從而提高KNN 的分類精度。文獻(xiàn)[9]提出將特征加權(quán)與SVM 相結(jié)合的方式來確定KNN 的K個(gè)近鄰樣本，使用SVM 確定樣本的每個(gè)特征與分類的相關(guān)度并進(jìn)行打分，作為選擇樣本的K個(gè)近鄰的依據(jù)，以此來增加特征加權(quán)準(zhǔn)確率和分類精度。

（4）改善近鄰搜索方法以提高KNN 的查找效率。文獻(xiàn)[10]針對(duì)高維空間內(nèi)使用Bregman 距離的KNN搜索的效率進(jìn)行了優(yōu)化，提出了一種優(yōu)化的維度劃分策略，即確定出每個(gè)分區(qū)子空間的有效邊界，進(jìn)而對(duì)優(yōu)化的分區(qū)數(shù)量進(jìn)行深度分析，設(shè)計(jì)出有效的分區(qū)策略，并對(duì)所有子空間一起設(shè)計(jì)了一個(gè)集成索引結(jié)構(gòu)，以加快KNN 搜索的過程。

從目前學(xué)者們的研究來看，主要是從改進(jìn)近鄰搜索方法、特征加權(quán)以及對(duì)訓(xùn)練樣本集進(jìn)行優(yōu)化等方面提高KNN 的分類性能，但是在處理大規(guī)模、高維度的數(shù)據(jù)方面，這些算法的分類效率會(huì)出現(xiàn)明顯降低?；诖?，本文創(chuàng)新性地提出一種基于密度Canopy 的增強(qiáng)聚類與深度特征的KNN 算法（KNN algorithm of enhanced clustering based on density canopy and deep feature，NDC_KNN+），主要做了以下四方面的工作：

（1）使用DNN 進(jìn)行特征降維與特征學(xué)習(xí)，以提取到適合分類的深度特征表示形式。

（2）采用密度Canopy 算法對(duì)提取到的特征數(shù)據(jù)樣本進(jìn)行處理，得到最佳集群數(shù)和初始集群中心。

（3）將得到的初始集群中心和集群數(shù)作為Kmeans 算法的輸入?yún)?shù)并進(jìn)行聚類，將聚類好的特征數(shù)據(jù)采用ASS（approximate similarity search）中的Hashing 方法按其近似相似度進(jìn)行集群劃分。

（4）采用聚類增強(qiáng)策略，將集群大小略微擴(kuò)展，以覆蓋到樣本集中可能屬于不同集群的近鄰樣本，最終在這些檢索到的數(shù)據(jù)中執(zhí)行常規(guī)的KNN 搜索。

經(jīng)實(shí)驗(yàn)表明，在大規(guī)模高維度數(shù)據(jù)的處理方面，改進(jìn)后的算法不僅在分類精度上有了極大的提高，還大大縮短了KNN 的分類時(shí)間，減少了搜索距離數(shù)，且對(duì)噪聲數(shù)據(jù)更魯棒。

1 Neural Codes表示

深度神經(jīng)網(wǎng)絡(luò)（DNN）是擁有多個(gè)處理層的計(jì)算模型，并利用這些計(jì)算模型來學(xué)習(xí)具有多層次抽象的數(shù)據(jù)表示[11]。在分類任務(wù)中，DNN 通過反向傳播算法，能自適應(yīng)地調(diào)整輸入在各層網(wǎng)絡(luò)中的權(quán)重參數(shù)，不斷地優(yōu)化分類結(jié)果，最終得到最佳的分類效果[12]。除此之外，DNN 也可以作為特征提取器，樣本數(shù)據(jù)通過網(wǎng)絡(luò)進(jìn)行前向傳播，獲得最后某一隱藏層的激活值作為提取到的特征表示，通過這種方式建立的深層抽象的特征表示稱之為NC（neural codes）表示[13]。

與DNN 的最后一層帶有損失函數(shù)的全連接層相比，KNN 可以獲取到更復(fù)雜的決策邊界，考慮到DNN在特征提取方面和KNN 在決策邊界方面的優(yōu)勢(shì)是互補(bǔ)的，因此將兩者作為一個(gè)混合系統(tǒng)，可以發(fā)揮兩種算法各自的優(yōu)勢(shì)。之前已有實(shí)驗(yàn)通過神經(jīng)網(wǎng)絡(luò)與其他分類器的結(jié)合證明了這樣的混合系統(tǒng)的效果良好。該方法是通過將最后一層全連接層連帶crossentropy 損失函數(shù)換成一個(gè)SVM 分類器來實(shí)現(xiàn)的[14]。使用DNN 獲得的NC 表示還能夠在基于聚類的分類過程中通過生成更合適的分類集群來提高分類效率。

2 密度Canopy+K-means算法

2.1 Canopy 算法

Canopy 算法是Mccallum 提出的一種無(wú)監(jiān)督的快速近似的“粗”聚類算法。經(jīng)典的聚類算法（如Kmeans、K-medoids等）雖然聚類精度高，但得到簇的速度緩慢，且受K值影響較大，Canopy算法的出現(xiàn)有效彌補(bǔ)了這些算法的不足。算法的基本原理如圖1 所示。

Fig.1 Principle of Canopy algorithm圖1 Canopy 算法原理

Canopy 算法的基本流程如下[15]:

步驟1對(duì)于給定樣本數(shù)據(jù)集D={x1,x2,…,xn}，設(shè)定兩個(gè)距離閾值T1和T2,其中T1>T2；

步驟2從數(shù)據(jù)集D中任取一個(gè)樣本點(diǎn)P，作為第一個(gè)Canopy 集合中的點(diǎn)，分別計(jì)算D中剩余樣本點(diǎn)與點(diǎn)P之間的歐式距離d；

步驟3判斷d是否小于T1，如果d

步驟4判斷d是否小于T2，如果d

步驟5重復(fù)步驟2～4，直到數(shù)據(jù)集為空。

由于Canopy 算法的距離閾值T1和T2的值會(huì)對(duì)最終聚類結(jié)果產(chǎn)生很大影響且難以確定，若距離閾值設(shè)定偏大，則會(huì)將原本屬于不同類的樣本點(diǎn)錯(cuò)誤劃分為同一類；若距離閾值設(shè)定太小，則會(huì)將原本為同一類的樣本點(diǎn)劃分為多個(gè)類。為了解決該算法中距離閾值T1、T2的確定問題，本文提出了一種密度Canopy 算法對(duì)此進(jìn)行改進(jìn)。

2.2 密度Canopy 算法

2.2.1 相關(guān)概念

對(duì)于給定數(shù)據(jù)集D={x1,x2,…,xn}，其中xi(1 ≤i≤n)為D中的第i個(gè)樣本向量，設(shè)xi={xi1,xi2,…,xim}，其中xir(1 ≤i≤n,1 ≤r≤m) 為第i個(gè)樣本向量的第r維特征。

定義1數(shù)據(jù)集D中兩樣本向量xi與xj間的歐式距離：

定義2數(shù)據(jù)集D中全部樣本的距離均值：

定義3數(shù)據(jù)集D中樣本向量xi的密度值（即以xi為中心，MeanDis(D)為半徑的范圍內(nèi)樣本向量的數(shù)目）：

其中：

定義4由等式（3）可知，ρ(xi)是滿足其他樣本向量到樣本向量xi間的距離小于MeanDis(D)的條件的樣本數(shù)，滿足條件的樣本向量組成一個(gè)集群，則集群內(nèi)樣本向量間的平均距離為：

a(xi)的值越小，1/a(xi)的值越大，表明集群內(nèi)的元素越緊密，且元素之間的相似度越大。

定義5簇間距離s(xi)表示樣本向量xi與有更高局部密度值的樣本向量xj之間的距離，若xi的局部密度值為最大值，則s(xi)定義為max{d(xi,xj)}，反之，則定義為，具體定義如下：

s(xi)越大，表明兩個(gè)集群之間的不相似度越大。

定義6數(shù)據(jù)集D被劃分為k個(gè)集群，集群Cj(j≤k)的中心是cj，則聚類代價(jià)E為每個(gè)集群內(nèi)的樣本xi(xi∈Cj)與該集群的中心點(diǎn)cj間的平方距離之和，具體定義如下：

式中，E越小，表明集群內(nèi)的距離越小，集群與集群之間越獨(dú)立，聚類效果越好。

為了減少由于傳統(tǒng)的Canopy 算法的閾值選擇的隨機(jī)性引起的最終聚類結(jié)果的不穩(wěn)定，提升聚類效果，本文引入了最大權(quán)重乘積法。該方法是由ρ(xi)、a(xi)和s(xi)以某種形式的乘積構(gòu)成，可以較好地反映集群中心的特征，即w(xi)值最大的樣本點(diǎn)可以作為下一聚類中心。

最大權(quán)重乘積法如圖2所示。首先，根據(jù)等式（3）計(jì)算樣本向量的密度，將密度的最大值作為第一個(gè)集群中心，添加所有滿足等式（3）中樣本向量與初始集群中心間的距離小于MeanDis(D)的條件的樣本向量到當(dāng)前集群中，并在數(shù)據(jù)集中刪除這些樣本點(diǎn)。此外，根據(jù)等式（3）、（4）、（5）、（7）計(jì)算數(shù)據(jù)集中剩余元素的權(quán)重乘積，找到最大值，并選擇相對(duì)應(yīng)的樣本向量作為第二個(gè)集群中心。特別地，對(duì)于樣本向量xi的簇間距離s(xi)，根據(jù)等式（5），若存在更高密度值的樣本向量xj，則對(duì)比xi與所有xj間的歐式距離d(xi,xj)。選擇與xi距離最近的樣本向量作為xi的簇間距離（圖2（a）），若xi的局部密度值為最大值，則選擇與xi距離最遠(yuǎn)的樣本向量作為xi的簇間距離（圖2（b））。最后，重復(fù)上述步驟直到數(shù)據(jù)集為空。

Fig.2 Diagram of maximum weight product method圖2 最大權(quán)重乘積法圖解

2.2.2 算法流程

步驟1對(duì)于給定數(shù)據(jù)集D，由等式（3）計(jì)算數(shù)據(jù)集內(nèi)所有樣本數(shù)據(jù)的密度值，選擇密度值最大的樣本作為第1 個(gè)聚類中心c1，并將c1加入中心點(diǎn)集C中，此時(shí)C={c1}。與此同時(shí)，從數(shù)據(jù)集D中刪除所有滿足剩余樣本點(diǎn)到c1之間的距離小于MeanDis(D)的樣本向量。

步驟2由等式（3）～（5）計(jì)算數(shù)據(jù)集D中剩余樣本向量的ρ(xi)、a(xi)、s(xi)，并將其代入等式（7）中計(jì)算密度權(quán)重w(xi)，選擇密度權(quán)重最大的樣本向量作為第2 個(gè)聚類中心c2，同樣地，將c2也加入中心點(diǎn)集C中，此時(shí)C={c1,c2}，從數(shù)據(jù)集D中刪除所有滿足剩余樣本點(diǎn)到c2之間的距離小于MeanDis(D)的樣本向量。

步驟3由等式（3）、（4）計(jì)算數(shù)據(jù)集D中剩余樣本向量的ρ(xi)、a(xi)，并由等式（5）計(jì)算剩余樣本中的數(shù)據(jù)到中心點(diǎn)集C中每個(gè)中心點(diǎn)的簇間距離，即：s(xi,c1)、s(xi,c2)，然后由等式（7）分別計(jì)算剩余樣本到每個(gè)中心點(diǎn)的密度權(quán)重值w(xi,c1)、w(xi,c2)，選擇w(xi,c1)×w(xi,c2)值最大的樣本作為第3 個(gè)聚類中心c3，將c3加入中心點(diǎn)集C中，此時(shí)C={c1,c2,c3}，從數(shù)據(jù)集D中刪除所有滿足剩余樣本點(diǎn)到c3之間的距離小于MeanDis(D)的樣本向量。獲取最佳集群中心的最大權(quán)重方法如圖3 所示。

Fig.3 Diagram of the best cluster center obtained by maximum weight product method圖3 使用最大權(quán)重乘積法獲得最佳聚類中心圖解

步驟4同理，若存在樣本向量xj滿足max{w(xj,c1)×w(xj,c2)×…×w(xj,ck-1)}，則xj將被設(shè)置為第k個(gè)聚類中心ck，加入中心點(diǎn)集C中，此時(shí)C={c1,c2,…,ck}，并從數(shù)據(jù)集D中刪除所有滿足剩余樣本點(diǎn)到ck之間的距離小于MeanDis(D)的樣本向量。

步驟5重復(fù)步驟4 的流程，從數(shù)據(jù)集中依次找出其余所有滿足步驟4 中條件的聚類中心，將其加入中心點(diǎn)集C中，并依次從數(shù)據(jù)集D中刪除剩余樣本到對(duì)應(yīng)聚類中心之間的距離小于MeanDis(D)的樣本向量，直到數(shù)據(jù)集為空。

可證該式關(guān)于θ1的二階偏導(dǎo)數(shù)小于0，存在最大值，求該式關(guān)于θ1的一階偏導(dǎo)，并令其為0，得到政府關(guān)于新能源汽車的CAFC得分效率的最優(yōu)決策：

最終，數(shù)據(jù)集D被劃分成為若干個(gè)集群，將每個(gè)集群內(nèi)樣本到該集群中其余樣本向量距離之和最小的樣本向量作為聚類中心。因此，最合適的初始聚類中心和群集數(shù)將被確定。

在上述步驟中，ρ(xi)反映了在樣本點(diǎn)xi周圍的元素集中程度，a(xi)反映了集群中元素的相似程度，s(xi)反映了不同集群間的相似度差異程度，由ρ(xi)、a(xi)和s(xi)以某種形式的乘積構(gòu)成的w(xi)則反映了集群中心所在位置的兩個(gè)特征，即具有相對(duì)較高的距離和局部密度，因此w(xi)最大的樣本可以被選擇作為聚類中心。此外，基于密度的方法對(duì)噪聲數(shù)據(jù)不敏感，可能的離群值可以通過ρ(xi)和s(xi)找到并除去。對(duì)于離群值，它具有離散性、低密度和偏離正常樣本的特征，因此，當(dāng)ρ(xi)小而s(xi)大時(shí)，樣本點(diǎn)被視為異常點(diǎn)，去除異常噪聲點(diǎn)可以保證聚類的精度，從而提高聚類的穩(wěn)定性。

2.3 K-means算法

K-means 算法是一種常見的基于劃分的聚類算法，該算法的核心思想是：對(duì)于給定的樣本集，需要事先確定集群數(shù)k，然后通過迭代將樣本集中所有的樣本向量，劃分到k個(gè)不同集群中，使得集群內(nèi)的樣本盡可能緊密分布在一起，集群間的距離盡可能大[16]。

由于K-means 算法簡(jiǎn)單、高效的特點(diǎn)，它適用于大數(shù)據(jù)集的聚類分析，目前K-means 算法主要存在兩個(gè)問題：集群數(shù)（k值）的確定和初始聚類中心的選擇。由于K-means 算法對(duì)k值的敏感性，選取的k個(gè)點(diǎn)不同，將會(huì)影響算法的聚類效果和迭代的次數(shù)，接下來本文提出一種密度Canopy+K-means 算法對(duì)此進(jìn)行改進(jìn)。

2.4 密度Canopy+K-means算法

本文采用密度Canopy+K-means 算法對(duì)特征數(shù)據(jù)聚類。在進(jìn)行聚類時(shí)，針對(duì)K-means 無(wú)法確定集群數(shù)和初始聚類中心隨機(jī)選擇的問題，首先采用密度Canopy 算法（第2.2 節(jié)）對(duì)數(shù)據(jù)進(jìn)行“粗”聚類，將算法得到的最合適的初始聚類中心和群集數(shù)作為Kmeans 算法（第2.3 節(jié)）的輸入?yún)?shù)，然后采用K-means算法進(jìn)行“細(xì)”聚類，以提高K-means 算法的最終聚類效果。密度Canopy+K-means 算法的基本流程如圖4所示。

算法1密度Canopy+K-means算法

Fig.4 Flow chart of density Canopy+K-means algorithm圖4 密度Canopy+K-means算法流程

如算法1 所示，密度Canopy+K-means 算法的執(zhí)行流程如下：

步驟1通過密度Canopy 算法得到最佳k值和初始聚類中心（第1 行到第16 行）。

步驟2計(jì)算其余數(shù)據(jù)集中的樣本與初始聚類中心之間的歐式距離，然后根據(jù)最小距離原理將樣本添加到相應(yīng)聚類中心的集群中（第18 行到第25 行）。

步驟3計(jì)算聚類中元素的平均距離并將其更新為新的聚類中心（第26 行到第27 行）。

步驟4將更新后的聚類中心與原始中心進(jìn)行比較，如果沒有更改，則終止算法，得到聚類的最終結(jié)果。否則，算法進(jìn)入步驟2。

傳統(tǒng)的K-means 算法的時(shí)間復(fù)雜度可以表示為Ο(nmtk)，其中n是數(shù)據(jù)集中的樣本數(shù)，m為樣本向量的特征維度，k是要聚類的集群數(shù)，t是算法的循環(huán)次數(shù)。本文中密度Canopy+K-means 算法的時(shí)間復(fù)雜度可以表示為Ο(n2m+nms+nmt′k)，其中t′是K-means算法的循環(huán)次數(shù)，s是密度Canopy 算法獲得k值和初始聚類中心的循環(huán)次數(shù)，Ο(n2m)是密度Canopy 算法的時(shí)間復(fù)雜度，且s

3 聚類過程下的高效KNN 分類策略

3.1 基于聚類的ASS 策略

ASS 方法是指在訓(xùn)練集中搜索與給定要查詢的數(shù)據(jù)足夠相似的數(shù)據(jù)。當(dāng)面臨大規(guī)模高維度數(shù)據(jù)時(shí)，大多數(shù)的算法都會(huì)花費(fèi)較高的計(jì)算成本[17]。

因此，本文采用了基于聚類的ASS 策略，使用ASS 中最常見的Hashing 方法。首先通過聚類方法得到訓(xùn)練集中每個(gè)樣本向量的聚類標(biāo)簽，根據(jù)聚類標(biāo)簽將對(duì)應(yīng)標(biāo)簽的樣本向量映射至指定的集群中，并最終按其相似度劃分為若干集群，每個(gè)集群用質(zhì)心表示。當(dāng)查詢樣本向量來臨時(shí)，選擇距離最近的質(zhì)心，然后在該質(zhì)心對(duì)應(yīng)的集群內(nèi)使用KNN 算法進(jìn)行精確查詢，以此來提高最近鄰搜索的效率，降低KNN 算法的計(jì)算成本。

3.2 聚類增強(qiáng)策略

上文采用的基于聚類的ASS 策略雖然能夠更有效地執(zhí)行搜索，但考慮到輸入查詢的K個(gè)近鄰樣本向量也可能由不同的集群給出，這通常會(huì)導(dǎo)致分類準(zhǔn)確性的損失。為了減輕這種影響，采用聚類增強(qiáng)策略，允許集群大小略微增加，以使得它們重疊，詳細(xì)流程如算法2 所示。

算法2CKNN+

具體而言，K-means 算法返回計(jì)算出的集群集合ClusterList，其中|len(ClusterList)|=k（第1 行）。對(duì)ClusterList中每個(gè)集群進(jìn)行迭代（第2 行），遍歷查詢每個(gè)集群內(nèi)的所有樣本（第3 行），提取每個(gè)樣本的K個(gè)最近鄰樣本（第4 行），將對(duì)應(yīng)樣本的所有K個(gè)最近鄰樣本合并到該集群中（第5 行），通過聚類增強(qiáng)策略可以降低K個(gè)最近鄰樣本屬于不同集群的概率，有效提升KNN 算法分類的精度，使用聚類增強(qiáng)前后的效果如圖5 所示。

Fig.5 Comparison of effects before and after using clustering enhancement圖5 使用聚類增強(qiáng)前后的效果對(duì)比

需要注意的是，盡管該算法旨在提高分類的準(zhǔn)確性，但這種新方法需要的距離要稍微多一些，因此，要想在效率和準(zhǔn)確性之間找到最佳折中方案，必須通過實(shí)驗(yàn)衡量的方式。

4 NDC_KNN+算法

本文提出了基于密度Canopy 的增強(qiáng)聚類與深度特征的KNN 算法（NDC_KNN+），首先采用DNN 進(jìn)行特征提取與降維，以學(xué)習(xí)到合適的NC 表示形式（第1章），然后采用密度Canopy+K-means 算法（第2 章）、基于聚類的ASS 策略和聚類增強(qiáng)策略（第3 章）進(jìn)行集群劃分，最后執(zhí)行常規(guī)KNN 算法進(jìn)行分類，過程主要包括以下四個(gè)階段。

4.1 NC 表示的提取

相比神經(jīng)網(wǎng)絡(luò)而言，手工提取的特征僅僅適用于某些特定的場(chǎng)景，而且這些特征通常對(duì)人類來說是有意義的，但是對(duì)于機(jī)器學(xué)習(xí)而言卻不是十分必要的。基于此，深度神經(jīng)網(wǎng)絡(luò)提供了一種學(xué)習(xí)輸入數(shù)據(jù)的特征映射的通用方法，且無(wú)需先驗(yàn)知識(shí)。

本文著重使用DNN 來學(xué)習(xí)NC 表示，即從給定的模型中得到輸入數(shù)據(jù)的特征表示。首先輸入帶標(biāo)簽的數(shù)據(jù)集到特定的網(wǎng)絡(luò)當(dāng)中，然后以有監(jiān)督的方式訓(xùn)練網(wǎng)絡(luò)，最后將神經(jīng)網(wǎng)絡(luò)中除最后一層外的其余各層作為主要的特征提取器，將輸入映射到一個(gè)類別可以線性分離的空間。

4.2 使用聚類進(jìn)行數(shù)據(jù)集的劃分

通過聚類可以實(shí)現(xiàn)直接有效的近似KNN 搜索，執(zhí)行此過程可以將數(shù)據(jù)集按其相似度劃分為不同分區(qū)。其作用為：對(duì)于給定的樣本進(jìn)行K最近鄰搜索時(shí)，首先搜索最近的集群（以其質(zhì)心表示），然后在該集群中執(zhí)行常規(guī)的KNN 搜索。具體步驟如下：

步驟1使用密度Canopy 算法（第2.2 節(jié)）獲取NC 表示下特征數(shù)據(jù)最佳聚類數(shù)和初始聚類中心。

步驟2將最佳聚類數(shù)和初始聚類中心作為Kmeans 算法（第2.3 節(jié)）的輸入?yún)?shù)，對(duì)數(shù)據(jù)集中的特征數(shù)據(jù)進(jìn)行聚類操作。

步驟3采用ASS 中的Hashing 方法將聚類之后的數(shù)據(jù)索引按其聚類標(biāo)簽映射至指定的集群中（第3.1 節(jié)），然后使用聚類增強(qiáng)策略將樣本的K個(gè)最近鄰樣本中可能屬于不同集群的最近鄰樣本的索引進(jìn)行合并（第3.2 節(jié)）。

4.3 分類

前兩個(gè)階段（NC 表示的提取、使用聚類進(jìn)行數(shù)據(jù)集的劃分）可以看作是分類前的預(yù)處理過程，因?yàn)橹挥杏?xùn)練集是必須的，并且可以在分類階段之前完全執(zhí)行，所以在實(shí)踐中它們不會(huì)影響算法效率。這些處理過程可以完美互補(bǔ)，在大規(guī)模高維度數(shù)據(jù)的分類方面可以發(fā)揮多種協(xié)同作用。

對(duì)經(jīng)過處理之后的數(shù)據(jù)按對(duì)應(yīng)的數(shù)據(jù)索引取出，找到距離查詢樣本向量最近的集群，然后在對(duì)應(yīng)集群內(nèi)執(zhí)行常規(guī)的KNN 算法進(jìn)行分類。該方法不僅可以獲得良好的特征表示，而且極大提高了KNN 近似搜索的效率，算法的大體流程如圖6 所示。

Fig.6 Overall process diagram圖6 整體過程

4.4 算法分析

傳統(tǒng)的KNN 算法對(duì)于待測(cè)樣本需在整個(gè)數(shù)據(jù)集之中查找最鄰近的K個(gè)樣本，其執(zhí)行效率與數(shù)據(jù)集的樣本規(guī)模有直接的關(guān)系。算法在測(cè)試階段的時(shí)間復(fù)雜度為Ο(n1n2m)，其中，n1表示訓(xùn)練集的樣本數(shù)，n2表示測(cè)試集的樣本數(shù)，m表示樣本向量的特征維度。

對(duì)于NDC_KNN+算法的復(fù)雜度分析，本文主要分析NC 表示下特征數(shù)據(jù)的時(shí)間復(fù)雜度，訓(xùn)練階段包括密度Canopy+K-means 算法、聚類增強(qiáng)策略和基于聚類的KNN 分類三部分。其中密度Canopy+K-means算法的時(shí)間復(fù)雜度為（具體分析詳見2.4 節(jié)），其中m′表示NC 表示下特征數(shù)據(jù)的維度。聚類增強(qiáng)需要對(duì)所有集群中訓(xùn)練樣本的K個(gè)最近鄰樣本進(jìn)行查找并合并，因此該算法的時(shí)間復(fù)雜度為?；诰垲惖腒NN 分類是在每個(gè)集群中進(jìn)行相似樣本的查找，因此該算法的時(shí)間復(fù)雜度為Ο(n1c1m′)，其中c1為集群內(nèi)訓(xùn)練集的樣本數(shù)。綜上所述，算法在訓(xùn)練階段的時(shí)間復(fù)雜度為在測(cè)試階段，由于KNN 算法僅在劃分好的集群內(nèi)進(jìn)行相似樣本的查找，因此算法的時(shí)間復(fù)雜度為Ο(n2c1m′) 。因?yàn)閏1

5 實(shí)驗(yàn)

為了驗(yàn)證本文方法的有效性，選取了5 個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。對(duì)于每個(gè)數(shù)據(jù)集，將分別采用本文方法（NDC_KNN+）與傳統(tǒng)KNN 算法進(jìn)行對(duì)比和評(píng)估，得到不同的實(shí)驗(yàn)結(jié)果。

實(shí)驗(yàn)環(huán)境如下：操作系統(tǒng)為Ubuntu 16.04，CPU為i7-6850K CPU@3.60 GHz，GPU 為帶有cuDNN 庫(kù)的TITAN Xp，開發(fā)工具為Pycharm，編程語(yǔ)言為Python，在pytorch（神經(jīng)網(wǎng)絡(luò)庫(kù)，版本為1.3.1）和scikit-learn（機(jī)器學(xué)習(xí)庫(kù)，版本為0.21.3）上執(zhí)行。

5.1 實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)中采用的數(shù)據(jù)包括MNIST、USPS、FashionMNIST、CIFAR10、CIFAR100。其中，MNIST數(shù)據(jù)集由28×28 像素的手寫數(shù)字圖片構(gòu)成，對(duì)應(yīng)于784 維特征向量；USPS 數(shù)據(jù)集是美國(guó)郵政服務(wù)的手寫數(shù)字識(shí)別庫(kù)，由16×16 像素的灰度手寫數(shù)字圖像構(gòu)成，對(duì)應(yīng)于256 維特征向量；FashionMNIST 數(shù)據(jù)集由28×28 像素的灰度圖像構(gòu)成，對(duì)應(yīng)于784 維特征向量，其中的樣本都來自日常穿著的衣褲鞋包；CIFAR10由維度是3 072 維的32×32×3（RGB）的彩色圖像構(gòu)成；CIFAR100 同樣也由維度是3 072 維的32×32×3 的彩色圖像構(gòu)成，來自100 個(gè)分類，這100 個(gè)分類被分成20 個(gè)超類，每個(gè)圖像都帶有一個(gè)“精細(xì)”標(biāo)簽（它所屬的類）和一個(gè)“粗糙”標(biāo)簽（它所屬的超類）。表1 詳細(xì)描述了所選數(shù)據(jù)集的詳細(xì)信息。

Table 1 Experimental data set表1 實(shí)驗(yàn)數(shù)據(jù)集

5.2 實(shí)驗(yàn)方法及評(píng)價(jià)指標(biāo)

為了驗(yàn)證本文方法的有效性，在每個(gè)數(shù)據(jù)集上分別使用傳統(tǒng)的KNN 算法與本文提出的NDC_KNN+進(jìn)行對(duì)比。除此之外，還對(duì)本文提到的算法效果進(jìn)行對(duì)比驗(yàn)證。使用到的KNN 算法的K值均分別取1、3、5、7、9，聚類的集群數(shù)均由密度Canopy 算法運(yùn)行在不同特征數(shù)據(jù)上所得到的最佳集群數(shù)給定，其中Original、NC 分別代表原始特征數(shù)據(jù)和NC 表示下的特征數(shù)據(jù)。各數(shù)據(jù)集上特征數(shù)據(jù)的最佳集群數(shù)如表2 所示。

Table 2 Optimal number of clusters for each data set using density Canopy表2 使用密度Canopy 獲得的各數(shù)據(jù)集的最佳集群數(shù)

為了得到每個(gè)數(shù)據(jù)集特定的NC 表示形式，為各個(gè)數(shù)據(jù)集定義了特定的DNN 架構(gòu)，以保證能夠提取到最佳精度的特征。表3 描述了各數(shù)據(jù)集的DNN 架構(gòu)。其中Conv(w,h,k)代表有k個(gè)卷積操作的層，每層的大小為w×h個(gè)像素；Linear(n)代表有n個(gè)神經(jīng)元的全連接層；BN(m)代表對(duì)m通道的特征數(shù)據(jù)進(jìn)行批標(biāo)準(zhǔn)化；MaxPool(w,h)代表大小w×h像素的最大池化操作；Drop(p)及Drop2D()表示按一定百分比對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行暫時(shí)性的隨機(jī)丟棄，其中p表示被丟棄的概率值；ResNet18 代表使用ResNet18 的網(wǎng)絡(luò)結(jié)構(gòu)[18]。

在實(shí)驗(yàn)過程中，使用算法的平均精度（即各個(gè)集群中分類后正確的樣本數(shù)占總樣本數(shù)的比例之和的均值）作為對(duì)算法分類效果的評(píng)價(jià)，使用算法的運(yùn)行時(shí)間（即在各個(gè)集群中執(zhí)行KNN 的耗時(shí)之和）、搜索距離數(shù)（即KNN 在各個(gè)集群中搜索的距離之和占原特征數(shù)據(jù)在傳統(tǒng)KNN 算法上的總搜索距離的百分比）作為對(duì)算法效率的評(píng)價(jià)。

Table 3 DNN structures corresponding to different data sets表3 不同數(shù)據(jù)集對(duì)應(yīng)的DNN 結(jié)構(gòu)

此外，還使用輪廓系數(shù)（silhouette coefficient，SCo）、完整性分?jǐn)?shù)（completeness score，CSc）、同質(zhì)性分?jǐn)?shù)（homogeneity score，HSc）作為對(duì)聚類效果的評(píng)價(jià)，具體定義如下：

SCo[19]采用集合內(nèi)聚度和分離度兩種因素，在相同原始數(shù)據(jù)集的基礎(chǔ)上，用來評(píng)估不同算法或者算法的不同運(yùn)行方式對(duì)聚類結(jié)果所產(chǎn)生的影響。其中a代表簇內(nèi)平均距離，b代表簇間平均距離，將公式定義為：

s的值處于-1～1 之間，值越大，表示聚類效果越好。

CSc[20]是一種隨著完整性（即給定類的所有樣本都分配給同一個(gè)簇的比率）的增加而逐步接近于1 的有監(jiān)督度量。

HSc[20]是一種表示聚類的同質(zhì)性（即聚好的簇中屬于相同類別的樣本比率）的度量，也是一種有監(jiān)督度量。

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

5.3.1 不同方法的對(duì)比與評(píng)估

在實(shí)驗(yàn)過程中，分別使用標(biāo)簽Original 和NC 來代表原始特征數(shù)據(jù)和NC 表示下的特征數(shù)據(jù)。除此之外，還使用DCKNN 和DCKNN+來分別代表使用初始聚類過程和聚類增強(qiáng)過程進(jìn)行分類的情況。

表4 顯示了原始特征數(shù)據(jù)和NC 表示下特征數(shù)據(jù)在密度Canopy 算法所給定的最佳集群數(shù)中分別采用DCKNN 和DCKNN+方法得到的平均精度值。

從表4 給出的實(shí)驗(yàn)結(jié)果可以看出，在密度Canopy算法所給出的不同數(shù)據(jù)集對(duì)應(yīng)的原始特征和NC 表示下特征數(shù)據(jù)的最佳集群數(shù)和初始聚類中心的情況下，使用聚類增強(qiáng)策略在不同K值上的平均精度明顯高于不使用聚類增強(qiáng)策略，且在原始數(shù)據(jù)集上使用聚類增強(qiáng)的平均精度提高的幅度更為明顯。除此之外，使用NC 表示的特征數(shù)據(jù)較原始的特征數(shù)據(jù)在分類精度上有較大程度的提高，并且在不同K值下的精度損失值較原始特征數(shù)據(jù)偏低。

綜上所述，使用NC 表示及聚類增強(qiáng)策略可以更好地改善KNN 分類器的性能。此外，使用NC 表示下的特征數(shù)據(jù)也能使得KNN 分類器的性能保持相對(duì)穩(wěn)定和高效。

5.3.2 聚類效果

作為對(duì)NDC_KNN+的進(jìn)一步分析，本小節(jié)將重點(diǎn)討論算法在第一步的聚類效果。在此過程中，使用K-means 和DKmeans 來分別代表傳統(tǒng)K-means 算法和密度Canopy+K-means 算法。表5 給出了原始特征數(shù)據(jù)（以標(biāo)簽Original 表示）和NC 表示下的特征數(shù)據(jù)（以標(biāo)簽NC 表示）在采用密度Canopy 算法前后K-means算法聚類時(shí)間的對(duì)比。

Table 4 Comparison of average accuracy of different methods under different K values表4 不同方法在不同K 值下的平均精度對(duì)比 %

Table 5 Comparison of clustering time between K-means and DKmeans表5 K-means與DKmeans的聚類時(shí)間對(duì)比 s

如表5 所示，可以看出原始特征數(shù)據(jù)相對(duì)NC 表示下的特征數(shù)據(jù)的聚類時(shí)間更長(zhǎng)。除此之外，由于傳統(tǒng)K-means 算法是隨機(jī)選擇的聚類中心，算法在達(dá)到穩(wěn)定狀態(tài)時(shí)迭代次數(shù)較大，因此執(zhí)行時(shí)間更長(zhǎng)，而使用密度Canopy 作為數(shù)據(jù)預(yù)處理的K-means 算法的聚類效果明顯優(yōu)于傳統(tǒng)的K-means 算法，算法完成特征數(shù)據(jù)的聚類達(dá)到穩(wěn)定后的迭代次數(shù)更少，因此比傳統(tǒng)的K-means算法更有效。

圖7（a）～（c）三幅子圖分別代表不同數(shù)據(jù)集在原始特征數(shù)據(jù)和NC 表示下的特征數(shù)據(jù)中使用密度Canopy+K-means 算法所得到的SCo、CSc、HSc 值的對(duì)比效果。

圖7 中聚類結(jié)果的指標(biāo)表明，不同數(shù)據(jù)集在NC表示下的特征數(shù)據(jù)采用密度Canopy+K-means 算法得到的SCo、CSc、HSc 指標(biāo)均優(yōu)于原始特征數(shù)據(jù)對(duì)應(yīng)的指標(biāo)，因此，根據(jù)上述結(jié)果可以發(fā)現(xiàn)使用NC 表示的特征數(shù)據(jù)可以更好地完成聚類過程。

5.3.3 與傳統(tǒng)KNN 算法的比較

Fig.7 Comparison of clustering effect of DKmeans under Original and NC characteristic representation圖7 DKmeans在Original與NC 表示下的聚類效果對(duì)比

Table 6 Comparison of average accuracy,time and distance between two algorithms表6 兩種算法在平均精度、時(shí)間、距離上的對(duì)比

本小節(jié)重點(diǎn)將本文方法（NDC_KNN+）與傳統(tǒng)KNN 方法進(jìn)行對(duì)比，進(jìn)而驗(yàn)證本文方法的優(yōu)勢(shì)所在。將NDC_KNN+方法與傳統(tǒng)KNN 方法在不同K值上分別對(duì)平均精度（accuracy，Acc）、運(yùn)行時(shí)間（Time）、搜索距離數(shù)（distance，Dis）進(jìn)行比較，實(shí)驗(yàn)結(jié)果如表6 所示。

從表6 的實(shí)驗(yàn)結(jié)果可以看出，各數(shù)據(jù)集在不同K值的情況下，NDC_KNN+在平均精度上均比傳統(tǒng)KNN 算法有明顯的提升。除此之外，在算法運(yùn)行時(shí)間和搜索距離數(shù)方面，本文方法大大縮短了KNN 算法K個(gè)近鄰的搜索時(shí)間，并且減少了KNN 算法的搜索距離數(shù)，使分類性能得以明顯提高。

Fig.8 Influence of different noise ratios on accuracy of two algorithms圖8 不同噪聲比對(duì)兩種算法的精度影響

圖8 描述了各數(shù)據(jù)集中采用NDC_KNN+和傳統(tǒng)KNN 算法在不同噪聲比上的不同K值的平均精度?？梢钥闯觯S著噪聲比的增加，NDC_KNN+相較于傳統(tǒng)KNN 方法的平均精度而言下降得更為緩慢，這是由于采用NC 表示的特征數(shù)據(jù)可以減輕噪聲對(duì)于最終分類效果的影響，從而使得本文方法比傳統(tǒng)KNN算法對(duì)噪聲數(shù)據(jù)有更好的魯棒性。

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

針對(duì)KNN 在大規(guī)模多維度數(shù)據(jù)的處理效率方面，本文提出了一種基于密度Canopy 的增強(qiáng)聚類與深度特征的KNN 算法（NDC_KNN+）。該算法首先通過神經(jīng)網(wǎng)絡(luò)來降低數(shù)據(jù)的維度并提取到合適的NC 表示形式，再通過密度Canopy+K-means算法進(jìn)行聚類，并采用基于聚類的ASS 策略將NC 表示下特征數(shù)據(jù)劃分成相似度相差較大的幾個(gè)集群。另外，使用聚類增強(qiáng)策略對(duì)集群中樣本的K個(gè)最近鄰樣本進(jìn)行查找，對(duì)可能屬于不同集群的最近鄰樣本進(jìn)行合并，最終將待測(cè)數(shù)據(jù)分配給與之相似度最接近的集群，在對(duì)應(yīng)集群中進(jìn)行常規(guī)KNN 分類。通過一系列的實(shí)驗(yàn)對(duì)比可以發(fā)現(xiàn)，相比傳統(tǒng)的KNN 算法而言，本文方法實(shí)現(xiàn)了更高的精度，更好的聚類效果，并且能夠大大減少KNN 算法的分類時(shí)間和搜索距離。

在以后的工作中，將考慮如何對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行優(yōu)化以學(xué)習(xí)到更合適的NC 表示。另外，由于聚類的好壞同樣能影響到KNN 的分類精度，如何進(jìn)一步地提升聚類效果也將是下一步研究的重點(diǎn)。