比例逆權重kNN 算法及其流處理應用

李衛平，楊 杰，王 鋼

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

0 引 言

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

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

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

1 kNN 分類算法

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

基于 “近朱者赤，近墨者黑”哲學思想的kNN 算法不需要復雜的統計建模技術，只需要計算某一固定鄰域內不同類別已知樣本的數目，且能夠直接應用于多類分類問題。

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

圖1 kNN 算法分類原理

一種直觀的方法是從訓練數據明顯居多的類別中，選擇與其它類別數目相當的樣本作為訓練樣本，但這種做法帶來了新問題。這種策略浪費了一部分訓練數據；對數據樣本的挑選將帶來較大的額外開銷。

2 比例逆權重kNN 算法

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

2.1 比例逆加權

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

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

其中，ni是第i類訓練數據中的樣本數目。若定義wi為第i類樣本的初始權重，為了抵消類別數目不均衡對分類性能的影響，應使式 （2）成立

由式 （2）可得

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

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

圖2 類別比例逆加權

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

2.2 距離權重貢獻

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

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

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

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

2.3 算法完整流程

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

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

考慮到結合樣本間距離的類別比例逆權重，經典kNN算法的類別判定公式可修改如下

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

圖3 比例逆權重kNN 算法的完整流程

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

3 面向流數據的增量式算法

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

Jussi等通過對數據集的篩選降低數據流的規模，實現了基于kNN 的流數據分類［8］，然而對數據集的篩選本身較為復雜，且帶來了新的開銷；黃杰等提出了基于模型簇修剪的流數據kNN 分類算法［9］，算法對模型簇的修剪提高了流數據分類的實時性，但修剪后的分類精度有限；Xu等提出了基于云的kNN 算法［10］，實現了對流數據的實時處理，該算法基于大規模集群，對硬件能力要求很高。

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

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

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

圖4 增量式比例逆權重kNN 算法原理流程

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

將本節提出的增量式運算機制應用于比例逆權重kNN之中，就構成了本文最終提出的增量式比例逆權重kNN 算法 （IPIW－kNN）算法。

4 實 驗

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

4.1 分類準確率測試與分析

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

表1 算法分類準確率對比

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

4.2 分類效率測試

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

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

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

4.3 數據流處理測試

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

表2 不同數據流量下的緩沖數據大小

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

5 結束語

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

［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）. ［呂峰，杜妮，文成林.一種模糊－證據kNN 分類方法 ［J］.電子學報，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］.小型微型計算機系統，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.