一種改進的快速K-近鄰分類方法

李偉，程利濤（大秦鐵路股份有限公司干部培訓中心　030013）

一種改進的快速K-近鄰分類方法

李偉，程利濤
（大秦鐵路股份有限公司干部培訓中心030013）

0　引言

目前，大數據挖掘［1-2］已經成為一個熱點問題被越來越多的研究者所關注。在諸多大數據挖掘問題中，由于分類問題自身的特殊性和復雜性，傳統的分類方法如K-NN［3］、支持向量機［4］、決策樹［5］、神經網絡［6］等已經無法滿足現實世界大數據高效處理的需求。因此，如何構造高效的大數據分類方法已經成為一個亟待解決的問題。

K-近鄰（K-Nearest Neighbor，K-NN）分類方法就是一種最典型的分類方法，目前在圖像檢測、目標跟蹤等諸多領域已經得到了成功應用［7-10］。不妨假設訓練樣本集規模為l，待測樣本規模為t，由于每個待測樣本均需要計算其與所有訓練樣本的距離，因此每個樣本計算距離的時間復雜度為O（l），所有樣本計算距離的時間復雜度為O（lt）。在實際分類問題中，如果訓練樣本規模過小，即擁有已知標記的樣本量過少，無法為待測試任務提供足夠的已知類別信息支持，得到的類別不準確。若訓練樣本規模較大，則算法執行的效率較低，無法進行有效的分類［11-12］。

針對傳統K-近鄰方法需要對每個待測樣本均計算其與所有訓練樣本距離而導致學習效率低下的問題，本文提出了一種改進的快速K-近鄰分類方法。該方法首先通過聚類將訓練集劃分為若干訓練子集。然后判斷待測樣本位于哪個子集當中或者距離哪個子集最近，則在該子集上采用K-近鄰方法對待測樣本進行測試，從而高效得到分類結果。

1　改進的快速K-近鄰分類方法

在傳統K-近鄰方法中，對于每個待測樣本txj，均需要計算其與整個訓練集Tr中所有訓練樣本的距離，因此每個待測樣本的決策復雜度均為O（l），整個模型的決策復雜度為O（tl），因此，當訓練集規模較大時，無法進行高效分類。而本文提出的改進的快速K-近鄰分類方法通過對訓練樣本聚類，不妨假設每個子類的規模為l/s，對于每個待測樣本，其決策復雜度都為O（l/ s），且可以采用并行策略，該復雜度也是整個算法的復雜度，且可以通過增加劃分參數s來提高算法的學習效率。改進的快速K-近鄰分類方法具體如下：

（2）計算每個工作子集Tri=｛（x1，y1），…，（xli，yli））｝的中心μi，其計算方法如下：

（3）計算每個工作子集Tri=｛（x1，y1），…，（xli，yli））｝的半徑ri，其計算方法如下：

（4）抽取待測樣本集Te=｛tx1，tx2，…，txt）｝中的待測樣本txj，并計算其與各子集中心μi的距離，計算方法如下：

（5）比較每個d（txj，μi）與半徑ri的大小，若d（txj，μi）＜ri成立，即待測樣本txj位于子集的超球區域之內，則將作為待測樣本txj的訓練集；

（8）選擇測試集中的其他待測樣本，重復執行（4）-（7）的步驟，直到待測樣本集中的所有樣本均得到其標記；

（9）將待測樣本得到的標簽與其真實標簽對比，得到方法泛化性能，算法結束。

2　實驗結果及分析

本文實驗采用的UCI數據集見表1，并將其與標準的K-近鄰分類方法進行了比較。實驗中，將訓練樣本都五等分，每次隨機選擇其中四份進行五次實驗，并取平均測試精度作為最終結果，實驗環境為1臺PC （2.66GHz CPU，1G內存），實驗平臺是MATLAB 7.0。

表1　實驗數據集

在本文提出的快速K-近鄰分類方法當中，影響其性能的主要參數為聚類劃分參數，即聚類劃分為幾個子集，本文在不同的聚類劃分參數下進行了實驗，對Thyroid和Heart兩個訓練樣本較大的數據集，分別劃分為10、20、30、40、50、60、70、80、90、100進行實驗，對其他兩個訓練樣本較小的數據集，分別劃分為10、20、30、40、50進行實驗，實驗中近鄰參數k取5，實驗結果見表2和表3。

從表2和表3可以看出，隨著聚類劃分參數的增加，SK-NN算法的學習效率逐步提高，但算法的測試精度略有下降；其次，與標準K-NN方法相比，本文提出的改進快速K-NN分類方法在Thyroid上得到的最優精度與標準K-NN相同，在其他三個數據集上得到的最優精度也接近于標準K-NN的測試結果。從學習效率來講，SK-NN算法卻比K-NN算法有了明顯的提高。

綜上可看出，本文提出的改進加速K-近鄰分類方法通過將訓練樣本聚類劃分為多個子集，然后根據待測樣本與每個子集的中心及半徑的關系，從而選擇與待測樣本最為接近的子類進行待測樣本標簽的判斷。該方法通過訓練劃分子集的方式減少了求解距離的數目，提高了分類的效率。

3　結語

傳統K-近鄰分類方法需計算每個待測樣本與所有訓練樣本的距離，學習效率低下，本文提出一種快速的K-近鄰分類方法，通過對訓練樣本進行K-均值聚類，劃分為多個訓練子集，并計算每個子集的中心和半徑，然后判斷待測樣本與中心半徑的關系，來選擇合適的子集對待測樣本進行標簽判別，通過減少距離計算的規模提高了模型學習效率，有望在大規模的社會網絡、文本分類、生物信息學等領域得到應用。

表2　平均測試精度（%）

表3　總訓練時間（s）

［1］Nature.Big Data［EB/OL］.［2012-10-02］.http://www.nature.com/news/specials/bigdata/index.html，2012.

［2］鐘曉，馬少平，張鈸等.數據挖掘綜述［J］.模式識別與人工智能，2001，14（1）:48-55.

［3］Mitchell H B，Schaefer P A.A"soft"K-Nearest Neighbor Voting Scheme［J］.International Journal of Intelligent Systems，2001，16，459-468.

［4］Li Y，Tian X M，Song M L，et al.Multi-Task Proximal Support Vector Machine［J］.Pattern Recognition，2015，48（10）:3249-3257.

［5］Wang X C，Liu X D，Pedrycz W，et al.Fuzzy Rule Based Decision Trees［J］.Pattern Recognition，2015，48（1）:50-59.

［6］高學星，孫華剛，侯保林.使用不同置信級訓練樣本的神經網絡學習方法［J］.電子與信息學報，2014，36（6）:1307-1311.

［7］Liu Z G，Pan Q，Dezert J.A New Belief-Based K-Nearest Neighbor Classification Method［J］.Pattern Recognition，2013，48（3）:834-844.

［8］Su M C，Chou C H.A Modified Version of the k-Means Algorithm with Distance Based on Cluster Symmetry［J］.IEEE Transactions onPattern Analysis and Machine Intelligence，2001，23（6）:674-680.

［9］Tian J，Li M Q，Chen F Z，et al.Coevolutionary Learning of Neural Network Ensemble for Complex Classification Tasks［J］.Pattern Recognition，2012，45（4）:1373-1385.

［10］郭玉堂.基于互K近鄰圖的自動圖像標注與快速求解算法［J］.計算機科學，2011，38（2）:277-280.

［11］彭凱，汪偉，楊煜普.基于余弦距離度量學習的偽K近鄰文本分類算法［J］.計算機工程與設計，2013，34（6）:2200-2203，2211.

［12］楊帆，林琛，周綺鳳等.基于隨機森林的潛在k近鄰算法及其在基因表達數據分類中的應用［J］.系統工程理論與實踐，2012，32 （4）:815-825.

K-Nearest Neighbor Classification；Clustering；Subset

An Improved Speeding K-Nearest Neighbor Classification Method

LI Wei，CHENG Li-tao
（Daqin Railway Corporation Limited Cadre Training Center，Taiyuan 030013）

1007-1423（2015）35-0014-04

10.3969/j.issn.1007-1423.2015.35.003

李偉（1983-），男，山西運城人，碩士，工程師，研究方向為數據挖掘、專業圖可視化、智能軟件設計

2015-11-04

2015-12-10

由于傳統K-近鄰分類方法需要計算每個待測樣本與所有訓練樣本的距離，學習效率較低。針對這個問題，提出一種改進的快速K-近鄰分類方法SK-NN。該方法首先對訓練樣本采用K-均值方法進行聚類，并得到聚類結果中每個子集的中心和半徑，并根據其選擇合適的子類并采用該子類對待測樣本打標簽。由于聚類后得到的子類的規模遠小于原始樣本的規模，因此需要計算的距離數目減少，提高模型的效率。

K-近鄰分類；聚類；子集

程利濤（1982-），男，河北邯鄲人，碩士，工程師，研究方向為數據挖掘、智能信息處理

In the traditional K-nearest neighbor classification method，for each sample to be tested，it needs to calculate the distance between it and all the training samples，so the time complexity is high.To solve this problem，presents an improved speeding K-NN classification method based on clustering dividing，called SK-NN algorithm.Firstly，the training samples are divided by the K-means clustering，and the training samples are divided into multiple subsets.Then the testing sample is belonged to which cluster by the center and radius，and the testing sample is clustered by K-NN on this sub set.The sub set size is smaller than the size of original training sample，so the distances number need to be calculated is decreased and the learning efficiency of model is improved.