比例逆權(quán)重kNN 算法及其流處理應(yīng)用

李衛(wèi)平，楊 杰，王 鋼

（1.武漢理工大學(xué) 信息工程學(xué)院，湖北 武漢430070；2.鐵道警察學(xué)院 公安技術(shù)系，河南 鄭州450053）

0 引 言

kNN 算法［1］存在顯著不足：類別均衡問題。類別均衡問題也稱為類別敏感問題，指的是當屬于不同類別的訓(xùn)練樣本的數(shù)目差異巨大時，會大大影響算法的分類性能［2］。

針對傳統(tǒng)kNN 算法的不足，Kashyap等通過對距離判據(jù)引入上界和下界來排除不必要的干擾樣本［3］，該算法一定程度上解決了類別敏感問題，但性能提升并不明顯；Tsoukalas等提出用樣本距離權(quán)重參數(shù)提高kNN 性能，取得較高精度［4］，但分類結(jié)果不夠穩(wěn)定；呂峰等提出一種模糊－證據(jù)kNN 分類算法，通過模糊化融合鄰樣本的信息熵提高kNN 算法的性能，取得了良好的實驗效果［5］，該算法的不足是時間開銷偏大。

本文通過對kNN 訓(xùn)練樣本的類別比例逆加權(quán)，充分利用了原始訓(xùn)練數(shù)據(jù)集，并克服了類別不平衡的問題，可以以很小的時間代價提高訓(xùn)練的可靠性和分類準確率。此外，通過記憶每個樣本的權(quán)重類別構(gòu)成，對實時到來樣本的分類無需重新計算全體樣本集，實現(xiàn)了kNN 算法的增量運算。實驗結(jié)果表明，本文提出算法的性能優(yōu)于其它kNN 類算法和若干經(jīng)典分類算法，且可應(yīng)用于流數(shù)據(jù)的實時處理。

1 kNN 分類算法

與支持向量機通過建立軟間隔超平面劃分樣本空間或者決策樹算法通過訓(xùn)練樣本歸納分類樹不同，kNN 算法是一種典型的消極學(xué)習(xí)算法［6］，在訓(xùn)練階段它基本不建立任何分類模型，只記錄樣本之間的距離，在分類過程中，計算待分類樣本與已知數(shù)據(jù)之間的距離，選擇一定數(shù)目的已知鄰居樣本，以其中樣本數(shù)目最多的類別作為待分類數(shù)據(jù)的類別。kNN 算法的分類原理如圖1所示。

基于 “近朱者赤，近墨者黑”哲學(xué)思想的kNN 算法不需要復(fù)雜的統(tǒng)計建模技術(shù)，只需要計算某一固定鄰域內(nèi)不同類別已知樣本的數(shù)目，且能夠直接應(yīng)用于多類分類問題。

當訓(xùn)練樣本中屬于某一類別的數(shù)據(jù)明顯多于其它類別時，由于偶然因素落入待分類樣本鄰域內(nèi)的概率就會大增，從而可能會影響到待分類數(shù)據(jù)點的最終類屬。

圖1 kNN 算法分類原理

一種直觀的方法是從訓(xùn)練數(shù)據(jù)明顯居多的類別中，選擇與其它類別數(shù)目相當?shù)臉颖咀鳛橛?xùn)練樣本，但這種做法帶來了新問題。這種策略浪費了一部分訓(xùn)練數(shù)據(jù)；對數(shù)據(jù)樣本的挑選將帶來較大的額外開銷。

2 比例逆權(quán)重kNN 算法

為了解決kNN 算法的類別敏感問題并且不引入任何新問題，本文提出了一種全新的訓(xùn)練數(shù)據(jù)使用方法，它主要是通過根據(jù)不同類別的樣本數(shù)量給樣本加權(quán)，從而在充分利用全體樣本的空間分布的前提下，消除樣本類別數(shù)目不平衡對分類帶來的干擾。

2.1 比例逆加權(quán)

對于訓(xùn)練數(shù)據(jù)集，其中的樣本類別和每一類樣本的數(shù)目都是已知的，可以按照每類中樣本的數(shù)目給該類的全體樣本賦予一個初始權(quán)重。

若有訓(xùn)練數(shù)據(jù)集S＝ ｛S1，S2，…，Sm｝，其中Si是S中屬于第i個類別的數(shù)據(jù)子集，且滿足

其中，ni是第i類訓(xùn)練數(shù)據(jù)中的樣本數(shù)目。若定義wi為第i類樣本的初始權(quán)重，為了抵消類別數(shù)目不均衡對分類性能的影響，應(yīng)使式 （2）成立

由式 （2）可得

通過對各類別樣本權(quán)重的歸一化處理，可以得到每類樣本的比例逆權(quán)重

通過對訓(xùn)練樣本的類別比例逆加權(quán)，可以解決kNN 算法的類別敏感問題。樣本類別比例逆加權(quán)原理如圖2所示。

圖2 類別比例逆加權(quán)

通過以上步驟，解決了訓(xùn)練樣本中某一類別由于其中樣本數(shù)目巨大而隨機落入待分類數(shù)據(jù)鄰域內(nèi)的問題。

2.2 距離權(quán)重貢獻

根據(jù)不同類別樣本數(shù)目的逆加權(quán)得到的只是樣本的初始權(quán)重，還需要考慮已知樣本與待分類樣本之間的距離，因為雖然都是落入待分類數(shù)據(jù)的某一鄰域，但待分類數(shù)據(jù)的類別與更近的已知樣本相同的概率更大。

樣本之間距離衡量標準可以是歐式距離、曼哈頓距離、馬氏距離等等。前人的應(yīng)用證明，如式 （5）所示余弦定理應(yīng)用于kNN 算法距離衡量中的效果更佳［7］

其中，x1和x2是兩個n 維數(shù)據(jù)點。由余弦定理可知，當sim（x1，x2）＝0時，兩個樣本完全不相關(guān)，當sim（x1，x2）＝1時，兩個樣本完全相同。由此，對于待分類樣本xj，可以改進待分類樣本的權(quán)重為

使用式 （6）所計算的新權(quán)重，可以在類別判斷時綜合考慮已知樣本的類別密度以及它和待分數(shù)據(jù)點之間的距離。

2.3 算法完整流程

在經(jīng)典的kNN 分類算法中，待分類樣本x 的類別Cx由式 （7）決定

式中：L——訓(xùn)練數(shù)據(jù)類別標簽集合，y——已 知樣 本，N——訓(xùn)練數(shù)據(jù)集，I（.）——一個指標函數(shù)，當I（.）的取值為true時，返回值為1，當取值為false時返回值為0。

考慮到結(jié)合樣本間距離的類別比例逆權(quán)重，經(jīng)典kNN算法的類別判定公式可修改如下

通過以上步驟，可實現(xiàn)消除類別敏感缺陷的kNN 分類算法，在充分利用鄰域樣本類別信息的基礎(chǔ)上，通過距離加權(quán)進一步提高分類的可信度。算法的整體流程如圖3所示。

圖3 比例逆權(quán)重kNN 算法的完整流程

在本節(jié)提出了本文的主要研究成果，比例逆權(quán)重kNN算法。相較其它kNN 算法的改進版本，本節(jié)提出算法在理論上具有更高的準確率和更低的時間開銷，在運算邏輯上，該算法仍有提升空間。

3 面向流數(shù)據(jù)的增量式算法

與大多數(shù)挖掘算法一樣，傳統(tǒng)的kNN 算法不具備流處理能力，因為每加入一個新樣本，算法需要重新計算全體樣本與該樣本之間的距離。然而在互聯(lián)網(wǎng)時代，對流式數(shù)據(jù)的實時分析需求漸增。

Jussi等通過對數(shù)據(jù)集的篩選降低數(shù)據(jù)流的規(guī)模，實現(xiàn)了基于kNN 的流數(shù)據(jù)分類［8］，然而對數(shù)據(jù)集的篩選本身較為復(fù)雜，且?guī)砹诵碌拈_銷；黃杰等提出了基于模型簇修剪的流數(shù)據(jù)kNN 分類算法［9］，算法對模型簇的修剪提高了流數(shù)據(jù)分類的實時性，但修剪后的分類精度有限；Xu等提出了基于云的kNN 算法［10］，實現(xiàn)了對流數(shù)據(jù)的實時處理，該算法基于大規(guī)模集群，對硬件能力要求很高。

實際上，在實時應(yīng)用中，帶有類別標簽的訓(xùn)練數(shù)據(jù)往往是批量到來的，只有類別待定的測試數(shù)據(jù)才呈現(xiàn)流式的特性。因此可以提出一種低時間開銷的增量式kNN 分類方法。由于kNN 算法需要在內(nèi)存保存正在處理的待分類樣本與各已知數(shù)據(jù)點之間的距離，對實時到來的待分類樣本，可以通過參考已經(jīng)計算出并保存在內(nèi)存中的訓(xùn)練樣本的位置，計算出最新待分類數(shù)據(jù)點與各已知樣本之間的距離。

當某個待分類樣本被kNN 算法打上類別標簽之后，可以根據(jù)類別標簽的可信度決定是否將該樣本作為補償訓(xùn)練數(shù)據(jù)。第i 個待分類數(shù)據(jù)的類別標簽Ci的可信度Confi（Ci）可以由式 （9）來評價

式中：k——參考樣本數(shù)目，Numi（Ck）——第i個待分類樣本的k 個鄰居樣本所屬的類別總數(shù)。通過對類別標簽可信度設(shè)置閾值，系統(tǒng)可以自動決定是否將某個新處理過的測試數(shù)據(jù)作為輔助訓(xùn)練數(shù)據(jù)。閾值的設(shè)定應(yīng)當考慮具體應(yīng)用對時間開銷和分類精度等性能的具體要求。增量式處理的原理如圖4所示。

圖4 增量式比例逆權(quán)重kNN 算法原理流程

經(jīng)過如圖4所示的流程，比例逆權(quán)重kNN 算法可實現(xiàn)對流數(shù)據(jù)的增量式分類，并能夠根據(jù)新分類數(shù)據(jù)類別標簽的可信度決定是否將新分類數(shù)據(jù)加入訓(xùn)練樣本集。

將本節(jié)提出的增量式運算機制應(yīng)用于比例逆權(quán)重kNN之中，就構(gòu)成了本文最終提出的增量式比例逆權(quán)重kNN 算法 （IPIW－kNN）算法。

4 實 驗

本文提出的算法是數(shù)據(jù)挖掘領(lǐng)域的通用算法，為了測試算法性能，本文以音頻分類和圖像分類為例，分別測試了算法的分類準確率和時間開銷，并與多種經(jīng)典算法作對比分析。實驗部分的音頻測試數(shù)據(jù)來源于數(shù)據(jù)堂，圖像數(shù)據(jù)來源于微軟圖像分類數(shù)據(jù)集。

4.1 分類準確率測試與分析

分類準確率測試的硬件環(huán)境為普通PC機，軟件環(huán)境為Windows 7Professional操 作 系 統(tǒng)、Matlab7.0 和MyEcliplise 6.0。實驗結(jié)果見表1。

表1 算法分類準確率對比

由實驗結(jié)果可知，本文提出算法在kNN 類算法里有更高的精度，甚至高于IS－KNN 算法［11］，即使和復(fù)雜的SVM算法相比，其分類準確率也相差很小。

4.2 分類效率測試

在分類效率測試部分，只對比了各算法在音頻分類中的時間開銷，實驗結(jié)果如圖5所示。

圖5 各分類算法時間開銷對比

如圖5所示，增量式比例逆權(quán)重kNN 算法的時間開銷僅僅略高于kNN 經(jīng)典算法，明顯低于IS－KNN 算法和SVM。雖然本文算法的效率低于C4.5，但C4.5的分類準確率明顯低于本文提出算法。相對于其它kNN 類算法，增量式比例逆權(quán)重kNN 算法以很小的時間開銷換來了明顯的準確率提升，是不錯的改進。

4.3 數(shù)據(jù)流處理測試

為了測試增量式比例逆權(quán)重kNN 算法實時處理流數(shù)據(jù)的能 力，測 試 了 當 數(shù) 據(jù) 流 為1k／s、10k／s、100k／s 和1000k／s時的數(shù)據(jù)緩沖池內(nèi)數(shù)據(jù)大小。緩沖池默認緩沖2 M 數(shù)據(jù)，最大容量為10 M。實驗結(jié)果見表2。

表2 不同數(shù)據(jù)流量下的緩沖數(shù)據(jù)大小

由表2可知，當數(shù)據(jù)流小于10k／s時，本文提出算法可以實時處理數(shù)據(jù)，當數(shù)據(jù)流量為100k／s時，以PC 機為實驗環(huán)境的系統(tǒng)基本可達到實時性，以PC服務(wù)器為環(huán)境的系統(tǒng)依然保持實時性。當數(shù)據(jù)流量達到1000k／s時，算法將無法實時處理數(shù)據(jù)。實驗結(jié)果表明，本文提出算法具有一定的流處理能力。

5 結(jié)束語

當訓(xùn)練數(shù)據(jù)中屬于各類別的樣本數(shù)量差異明顯時，kNN算法［12］的分類性能會大受影響。本文提出了一種類別比例逆加權(quán)策略，可以在充分利用全體訓(xùn)練數(shù)據(jù)的前提下以很低的額外時間開銷解決類別敏感問題；通過記憶訓(xùn)練樣本的位置實現(xiàn)比例逆加權(quán)kNN 算法的增量運算。實驗結(jié)果表明，該算法在kNN類算法中具有很高的分類準確率和較低時間開銷，相對其它算法，其精度－效率綜合性能也是理想的。算法還具有一定的流處理能力，適合應(yīng)用于實時分類場景。

［1］Fayed H A，Atiya A F.A novel template reduction approach for the k－nearest neighbor method ［J］.IEEE Transactions on Neural Networks，2009，20 （5）：890－896.

［2］Li Zisheng，Ding Guofu，Li Rong，et al.A new extracting algorithm of k nearest neighbors searching for point clouds［J］.Pattern Recognition Letters，2014，49 （11）：162－170.

［3］Shrikant Kashyap，Panagiotis Karras.Scalable kNN search on vertically stored time series ［C］／／Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2011：1334－1342.

［4］Vassilis Tsoukalas，Kaburlasos，Christos Skourlas.A granular，parametric KNN classifier［C］／／Proceedings of the 17th Panhellenic Conference on Informatics，Thessaloniki，2013：319－326.

［5］LV Feng，DU Ni，WEN Chenglin.A fuzzy－evidential k nearest neighbor classification algorithm ［J］.ACTC Electroica Sinica，2012，40 （12）：2390－2395 （in Chinese）. ［呂峰，杜妮，文成林.一種模糊－證據(jù)kNN 分類方法 ［J］.電子學(xué)報，2012，40 （12）：2390－2395.］

［6］Porta Alberto，Bari Vlasta，Bassani Tito.K－nearest－neighbor conditional entropy approach for the assessment of short－term complexity of cardiovascular control ［J］.Institutional Research Information System，2013，25 （1）：231－244.

［7］Akbari M，Van Overloop P J，Afshar A.Clustered K nearest neighbor algorithm for daily inflow forecasting ［J］.Water Resources Management，2011，25 （5）：1341－1357.

［8］Jussi Nieminen，Jorma Ylinen，Timo Seppl，et al.A framework for classifying IPFIX flow data，case KNN classifier［C］／／The Eighth International Conference on Networking and Services，2012：14－19.

［9］HUANG Jie，GUO Gongde，CHEN Lifei.Research on pruning strategy of incremental KNN model［J］.Journal of Chinese Computer Systems，2011，32 （5）：845－849 （in Chinese）. ［黃杰，郭躬德，陳黎飛.增量KNN模型的修剪策略研究 ［J］.小型微型計算機系統(tǒng)，2011，32 （5）：845－849.］

［10］XU Huiqi，Guo Shumin，Chen Keke.Building confidential and efficient query services in the cloud with RASP data perturbation ［J］.IEEE Transactions on Knowledge and Data Engineering，2014，26 （2）：322－335.

［11］Amal Miloud－Aouidate，Ahmed Riadh Baba－Ali.IDS false alarm reduction using an instance selection KNN－memetic algorithm ［J］.International Journal of Metaheuristics，2013，2（4）：333－342.

［12］Wu Xindong，Vipin Kumar.The top ten algorithms in data mining ［M］.Chapman and Hall Press，2013：205－207.