楊海娟

（蘭州職業(yè)技術(shù)學(xué)院電子信息工程系，甘肅蘭州 730070)

1 研究背景

分類是機器學(xué)習(xí)、數(shù)據(jù)挖掘等領(lǐng)域的一個重要研究方向。分類通過對現(xiàn)有的數(shù)據(jù)進行學(xué)習(xí)，掌握數(shù)據(jù)中潛在的規(guī)律，給決策、商務(wù)應(yīng)用、醫(yī)療保健和生命科學(xué)、目標(biāo)識別及安全認(rèn)證等領(lǐng)域提供了更有效的支持，各種分類算法的研究具有重要的理論研究意義及實際應(yīng)用價值。一般情況下，分類是一個有監(jiān)督的學(xué)習(xí)過程，一個分類算法一般分為兩階段，第一階段訓(xùn)練分類器，利用帶標(biāo)簽的數(shù)據(jù)，訓(xùn)練產(chǎn)生一個分類器，第二階段就是將得到的分類器應(yīng)用于實際的生產(chǎn)環(huán)境。機器學(xué)習(xí)、數(shù)據(jù)挖掘領(lǐng)域考慮的多是第一個階段的問題，即選用何種模型，如何進行訓(xùn)練以得到最好的分類器。

K-近鄰算法(KNN)是一種經(jīng)典分類算法，被國際數(shù)據(jù)挖掘會議評選為機器學(xué)習(xí)的十大經(jīng)典算法之一，它是一種惰性分類算法,沒有訓(xùn)練過程，該分類方法首先簡單地把訓(xùn)練樣本儲存起來,分類時通過計算測試樣本和每個訓(xùn)練樣本的相似性，然后找出k個最近鄰樣本，對k個最近鄰樣本的標(biāo)簽進行投票，以投票的方式?jīng)Q定自身的標(biāo)簽。KNN算法思想簡單，準(zhǔn)確率相對較高，廣泛地應(yīng)用于各種分類問題，對維度很高的數(shù)據(jù)也可以正確分類，尤其適合于多分類問題，但是KNN在樣本容量分布不均勻時，表現(xiàn)出更傾向于大容量樣本，而且如果樣本容量大，所需的計算量大，效率低。針對這一問題，本文提出了一種基于聚類分析的最近鄰方法，其分類器準(zhǔn)確率接近甚至優(yōu)于KNN 方法，可以極大地提高分類效率。

本文剩余部分的章節(jié)按如下結(jié)構(gòu)進行組織。第2節(jié)回顧KNN方法相關(guān)的文獻，第3節(jié)詳細闡述本文提出的算法的思想，第4節(jié)給出實驗過程，并對實驗結(jié)果進行詳細分析，本文最后以第5節(jié)的結(jié)論作為結(jié)尾。

2 相關(guān)工作

由于分類具有重要的意義及實用價值，研究人員已經(jīng)提出了大量的分類方法，例如決策樹[1]、貝葉斯分類器[2]、神經(jīng)網(wǎng)絡(luò)[3]、SVM[4]、Adaboost 分類器[5]以及深度學(xué)習(xí)方法[6]等。其中KNN 是一個典型的惰性分類方法，如前所述，在KNN算法中，要計算待測樣本和每個樣本的相似性，一旦數(shù)據(jù)分布不均，大類別樣本就會占有密度優(yōu)勢，某個類別的樣本數(shù)量大，會增加預(yù)測結(jié)果成為該類的可能，某個類別樣本容量太小，則有可能大大減少成為該類的可能。隨著分類數(shù)據(jù)的不斷快速增長，大數(shù)據(jù)分析與挖掘技術(shù)被廣泛應(yīng)用于各個行業(yè)，因為KNN需要大小和樣本個數(shù)n一樣的線性復(fù)雜度來計算距離完成分類，需要較大的內(nèi)存開銷，分類時間開銷大。即使如此，由于KNN 算法簡單，易于實現(xiàn)，具有較高的分類準(zhǔn)確率，因此為了提高KNN的分類準(zhǔn)確度和效率，多種嘗試提高該算法效率的方法被提出。文獻[7]提出了一種基于將原始樣本替換為新的樣本集合從而建立分類模型的方法，減少了KNN算法需要進行相似計算的樣本數(shù)，從而達到提高分類速度的目的。文獻[8]通過基于熵的改進距離計算，基于加權(quán)距離的分類確定和定量轉(zhuǎn)換來改進KNN算法，克服了傳統(tǒng)KNN 算法的缺點。文獻[9]構(gòu)建了一種基于KNN 的快速分類算法，減少了大量計算，保持了相同的準(zhǔn)確率，提高了分類的速度。很多的算法都一直致力于提高KNN的運算效率。

針對KNN算法無訓(xùn)練的特點[10-11]，本文對KNN引入一個訓(xùn)練過程，提出了一種新的分類方法。首先，在訓(xùn)練階段，對每個類通過聚類進行分類，在每個分得的更小的類中求出一個具有代表性的虛擬樣本，此虛擬樣本就是由本類中所有樣本的均值構(gòu)成的一個“中心樣本”，作為本類別的代理，也稱之為代理樣本。數(shù)據(jù)集有多個類別，每個類被分為多個更小的類，每個小的類別都有一個代理樣本，因而形成一個代理樣本集合，在測試階段，每個測試樣本按照KNN算法進行分類，由于每個代理樣本已經(jīng)有很強的代表性，不需要對多個最近代理樣本投票進行選擇，所以取K值為1進行分類。

本文提出了一種名為BCNNC(Nearest Neighbour Classifier based on Cluster Analysis)的算法，實驗表明，該算法適應(yīng)性強，能對分布不規(guī)則但是類別之間差異較大的數(shù)據(jù)集進行很好的分類，而對于有些數(shù)據(jù)集，能在提高效率的情況下和KNN有近似的表現(xiàn)，在有些數(shù)據(jù)集上甚至超過了KNN的分類效果。

3 BCNNC算法

3.1 算法的提出

機器學(xué)習(xí)中樣本分類的基礎(chǔ)是“類內(nèi)樣本間相似度高，類間樣本的相似度低”，如圖1所示的數(shù)據(jù)集有3個類，均為二維特征的數(shù)據(jù)集，可用距離代表其相似性，距離越近的樣本越相似。通過觀察發(fā)現(xiàn)，3個類內(nèi)部樣本分布密集，距離較近，類之間樣本距離較遠，此三種類別的數(shù)據(jù)之間差別較大，考慮從每個類找出一個“中心樣本”作為每個類的代表，測試樣本分類時，用每個類的代表與測試樣本之間求相似性，那個類代表和測試樣本最相似，就認(rèn)為測試樣本是屬于這種類代表所在的類別，執(zhí)行KNN算法。通過在UCI數(shù)據(jù)集Iris和Wine上測試，發(fā)現(xiàn)其效果與KNN近似。當(dāng)數(shù)據(jù)集中兩類數(shù)據(jù)如圖2所示的環(huán)形分布模擬數(shù)據(jù)集或者其他數(shù)據(jù)集上測試，發(fā)現(xiàn)此方法完全失效，因為兩個類的代理樣本很相似，測試樣本根本無法以此代理為參考來分類，此時類代理顯然失效，如何找出每個類中真正的代理是這種方法是否有效的關(guān)鍵。

圖1 類的代理樣本示意圖

圖2 環(huán)形的代理樣本示意圖

通過觀察發(fā)現(xiàn)，在環(huán)狀分布的類樣本中，如果再次分類，將每個大類分成若干個小類，再找到合適的代理樣本，測試樣本通過這些代理樣本找到自己所在的類。這就好比在眾多圖片中分出人的圖片，經(jīng)常使用的辦法不是直接確定此圖片是不是人的圖片，而是從眾多圖片中找出男人、女人、小孩、老人等具體的人中的一個小類別，最終就找出了所有人的分類，所以對于每一類數(shù)據(jù)樣本來說，都可以考慮對其進一步分類，以幫助人們更好的確認(rèn)測試樣本的分類。

根據(jù)上述事實，將每一類訓(xùn)練樣本進行聚類，分成更小塊的類，如圖3所示。從每塊小分類中找出各自的代理樣本，接著再以代理樣本集合作為KNN的訓(xùn)練樣本，設(shè)置k 值為1，執(zhí)行KNN 算法，此時每個小分類的虛擬代理都可以更好地代表自己所在分類的特性，接著再執(zhí)行KNN算法會得到較好的分類效果。

圖3 類內(nèi)部分類后的代理樣本示意圖

3.2 算法的設(shè)計

本算法分為兩步實現(xiàn)，第一步是訓(xùn)練階段，先對數(shù)據(jù)進行標(biāo)準(zhǔn)化處理，然后將訓(xùn)練集中的每個類分塊，本方法以聚類的方法在類內(nèi)分塊，聚類的方法很多，如基于劃分的K-means 算法，基于層次的BIRCH算法[12]和基于密度的DBSCAN 聚類算法[13]，本文采用了K-means++算法[7]進行類內(nèi)聚類，將類分成小的分類，選出每個小分類中的代理樣本。當(dāng)樣本數(shù)量很大時，如果待分類樣本能處理成以類別為單位，則可以考慮對每個類別并行分類，找出代理樣本集合。第二步為測試階段，將測試樣本進行分類，此階段求出距離測試樣本最近的代理樣本，將測試樣本的類別確定為和此代理樣本的標(biāo)簽一致。

1)數(shù)據(jù)的標(biāo)準(zhǔn)化(normalization)

數(shù)據(jù)標(biāo)準(zhǔn)化有很多種方法，最具代表的是數(shù)據(jù)的歸一化處理，文獻[14-15]指出，樣本數(shù)據(jù)歸一化可以加速學(xué)習(xí)訓(xùn)練速度并提高分類精度。將數(shù)據(jù)按比例縮放，使之落入一個小的特定區(qū)間。確保各種數(shù)量級的特征都會對目標(biāo)的分類起到各自的作用，即將數(shù)據(jù)統(tǒng)一映射到[0,1]區(qū)間上，歸一化計算方法如公式(1)所示：

2) K-means++算法

K-means 算法是一種選擇多個中心點作為質(zhì)心，根據(jù)待聚類點離質(zhì)心點的距離來聚類，離質(zhì)心近的點將被聚為一類，該算法的聚類結(jié)果是球狀的，這種分類結(jié)果適用于本文所提出的分類算法。然而由于原始K-means算法中心點隨機選擇的改進，如果初始點的位置選擇不當(dāng)（例如都在一個簇里面），那么其最終的聚類結(jié)果將可能很不理想。

K-means++則按照如下思路選擇K 個初始中心點：假設(shè)已經(jīng)選取了n 個初始聚類中心(0＜n ＜K)，則在選取第n+1 個聚類中心時：距離當(dāng)前已有的n 個聚類中心越遠的點會有更高的概率被選為第n+1 個聚類中心。在選取第一個聚類中心(n=1)時同樣通過隨機的方法。當(dāng)然這也非常容易理解：聚類中心當(dāng)然是相互離得越遠越好。

算法1 K-means++算法：

輸入：數(shù)據(jù)集，聚類個數(shù)K

輸出：K個簇數(shù)據(jù)的集合

過程：

Step 1:從數(shù)據(jù)集中隨機選取一個樣本點作為初始聚類中心C1；

Step 2:首先計算每個樣本與當(dāng)前已有聚類中心之間的最短距離（即最近的聚類中心的距離），用D(x)表示；接著計算每個樣本點被選為下一個聚類中心的概率p。最后，按照輪盤法選擇出下一個聚類中心；

Step 3:重復(fù)第2步直到選擇出K個聚類中心；

之后的步驟同原始K-means聚類算法相同。

算法中任一樣本點x被選為下一個聚類中心的概率由公式(2) 決定，通過實驗表明使用聚類算法Kmeans++相比K-means聚類結(jié)果穩(wěn)定性較高。

3)算法2 BCNNC算法：

輸入：數(shù)據(jù)集Dataset，分類標(biāo)簽Label，類內(nèi)分類個數(shù)X

輸出：分類正確率

Step 1 輸入數(shù)據(jù)集，輸入X，根據(jù)X計算類內(nèi)分成的類別個數(shù)C；

Step 2 在每個類內(nèi)部用K-means++聚類，得到每個訓(xùn)練數(shù)據(jù)所在的小類編號，并記錄小類的編號和所在大類的對應(yīng)關(guān)系kind數(shù)組；

Step 3 根據(jù)每列屬性的平均值，求出每個小類的代理樣本，得到一個means數(shù)組；

Step 4 以means 數(shù)組作為訓(xùn)練樣本，輸入測試數(shù)據(jù)，執(zhí)行KNN(k=1)算法，得出小類的編號；

Step 5 根據(jù)kind 數(shù)組對應(yīng)的大類編號，確定測試樣本所在的最終類別。

4 實驗結(jié)果與分析

4.1 實驗數(shù)據(jù)集

4 個人工合成數(shù)據(jù)集、5 個UCI 數(shù)據(jù)集及UCI 中3個手寫數(shù)字及2個圖像數(shù)據(jù)集，如表1～表3所示：

表1 4個人工合成數(shù)據(jù)集

表2 5個UCI數(shù)據(jù)集

表3 UCI中3個手寫數(shù)字及2個圖像數(shù)據(jù)集

4.2 算法參數(shù)

本文選擇的KNN 算法都是在K=3 的情況下的執(zhí)行結(jié)果，而本文提出的算法中每個分類的分塊個數(shù)C則是由數(shù)據(jù)集的大小來決定，每個類的分類個數(shù)和其樣本數(shù)成正比，樣本數(shù)多的分得類別也多。分類個數(shù)從每個類只有一個小類，逐漸增加每個類的分類個數(shù)，當(dāng)每個類分成的小類數(shù)目跟樣本數(shù)一樣多時，算法則退化成KNN算法中K=1的情況。

4.3 實驗及分析

實驗分為3個階段，分別是人工合成數(shù)據(jù)集，5個UCI數(shù)據(jù)集、手寫數(shù)字和圖像數(shù)據(jù)集，每個數(shù)據(jù)集在實驗時都會在每個類內(nèi)部分類，在分類個數(shù)C不同的情況下進行多次實驗，并對實驗結(jié)果進行分析，對同樣的數(shù)據(jù)集同時執(zhí)行該算法和KNN(k=3)，進行了20 次實驗，正確率求平均值。

首先在4 個合成數(shù)據(jù)集上展開了實驗，通過模擬產(chǎn)生數(shù)據(jù)集，每個數(shù)據(jù)集經(jīng)過20次執(zhí)行求其平均值，執(zhí)行K-means++把每個類聚成10個小類，求平均正確率，結(jié)果如圖4 所示，本文的算法和常見的分類算法KNN、Linear SVM、RBF SVM,Decsion tree、AdaBoost 進行了正確率比較，表現(xiàn)均和KNN 接近或超過KNN，circle 數(shù)據(jù)集的分類效果較差。表明此算法在線性不可分的數(shù)據(jù)集上表現(xiàn)良好。

接著在UCI 的5 個數(shù)據(jù)集上展開對比實驗，在Iris、Wine、Breast Cancer、horse、banana 這些數(shù)據(jù)集上進行了驗證，Iris 數(shù)據(jù)集和Wine 數(shù)據(jù)集本來為3 類，在對每個類不分類或分成2 個小類時，Breast Cancer數(shù)據(jù)集為兩類，在分成11 類時，Iris 和Wine 數(shù)據(jù)集不用劃分成更小的類就可以超過KNN的精度，Banana共有兩類，在被分為130類時，因為樣本數(shù)目為5 300，如果直接運行KNN 需要5 300 次距離運算，而在本算法中只需要130 次距離運算，Breast Cancer 數(shù)據(jù)集只需要計算11 次，減少了400 多次距離運算，Banana 數(shù)據(jù)集只需要130 次距離計算，減少了4 000 多次距離計算，由于這些數(shù)據(jù)集只經(jīng)過較少的運算就超過了KNN的精度，速度遠遠超過了KNN，證實了在類內(nèi)再能細分的數(shù)據(jù)集上，或者類和類之間差別比較大的數(shù)據(jù)集上，用此算法可進行高效的分類。

最后，在手寫數(shù)字?jǐn)?shù)據(jù)集Pendigits、Digits、Letter、Image和Magic04數(shù)據(jù)集上，本文提出的算法在大多數(shù)數(shù)據(jù)集上識別的正確率優(yōu)于KNN 算法，或者與KNN算法結(jié)果相似，實驗結(jié)果如表4所示，C表示被劃分成的小類的總個數(shù)，每2～5個數(shù)據(jù)分成1個小類，也保持了和KNN近似的正確率，表明這種對細節(jié)要求更高的數(shù)據(jù)集中，2～5 以上的樣本形成一個小類，才能和KNN的效果保持一致，當(dāng)每1個樣本分成1個小類時，該算法退化為KNN算法。

表4 BCNNC算法和KNN算法在手寫數(shù)字和圖像數(shù)據(jù)集上的實驗結(jié)果

5 總結(jié)

本文提出了一種在訓(xùn)練集類內(nèi)聚類的BCNNC分類算法，通過在數(shù)據(jù)集類內(nèi)繼續(xù)分類發(fā)現(xiàn)，分成小類后再執(zhí)行KNN算法與直接執(zhí)行KNN算法得到相似的結(jié)果，有時甚至超過KNN算法的分類精度。通過前兩個階段的實驗表明，對那些類間區(qū)別較明顯但是對類樣本分布線性不可分的數(shù)據(jù)集，采用BCNNC 分類算法后，可以有效地提升分類精度和分類速度。一種數(shù)據(jù)集分成多少小類，要通過嘗試和選擇，對于第三個階段的數(shù)字識別和圖像識別的數(shù)據(jù)集，樣本分類時要根據(jù)樣本的形狀和細節(jié)進行分類，多個樣本分成小類，由一個虛擬樣本來代替多個樣本的特征并不適合，采用此方法并沒有顯著的提高速度，當(dāng)數(shù)據(jù)集由2～5個以上樣本聚成一小類，會得到和KNN基本相似或者優(yōu)于KNN 的分類精度，并且執(zhí)行效率高于KNN分類算法。綜上所述，本文提出的方法適用于類間區(qū)別較明顯，類內(nèi)能再細分的數(shù)據(jù)集分類。