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

一種改進(jìn)的快速K-近鄰分類方法

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

0　引言

目前，大數(shù)據(jù)挖掘［1-2］已經(jīng)成為一個(gè)熱點(diǎn)問(wèn)題被越來(lái)越多的研究者所關(guān)注。在諸多大數(shù)據(jù)挖掘問(wèn)題中，由于分類問(wèn)題自身的特殊性和復(fù)雜性，傳統(tǒng)的分類方法如K-NN［3］、支持向量機(jī)［4］、決策樹(shù)［5］、神經(jīng)網(wǎng)絡(luò)［6］等已經(jīng)無(wú)法滿足現(xiàn)實(shí)世界大數(shù)據(jù)高效處理的需求。因此，如何構(gòu)造高效的大數(shù)據(jù)分類方法已經(jīng)成為一個(gè)亟待解決的問(wèn)題。

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

針對(duì)傳統(tǒng)K-近鄰方法需要對(duì)每個(gè)待測(cè)樣本均計(jì)算其與所有訓(xùn)練樣本距離而導(dǎo)致學(xué)習(xí)效率低下的問(wèn)題，本文提出了一種改進(jìn)的快速K-近鄰分類方法。該方法首先通過(guò)聚類將訓(xùn)練集劃分為若干訓(xùn)練子集。然后判斷待測(cè)樣本位于哪個(gè)子集當(dāng)中或者距離哪個(gè)子集最近，則在該子集上采用K-近鄰方法對(duì)待測(cè)樣本進(jìn)行測(cè)試，從而高效得到分類結(jié)果。

1　改進(jìn)的快速K-近鄰分類方法

在傳統(tǒng)K-近鄰方法中，對(duì)于每個(gè)待測(cè)樣本txj，均需要計(jì)算其與整個(gè)訓(xùn)練集Tr中所有訓(xùn)練樣本的距離，因此每個(gè)待測(cè)樣本的決策復(fù)雜度均為O（l），整個(gè)模型的決策復(fù)雜度為O（tl），因此，當(dāng)訓(xùn)練集規(guī)模較大時(shí)，無(wú)法進(jìn)行高效分類。而本文提出的改進(jìn)的快速K-近鄰分類方法通過(guò)對(duì)訓(xùn)練樣本聚類，不妨假設(shè)每個(gè)子類的規(guī)模為l/s，對(duì)于每個(gè)待測(cè)樣本，其決策復(fù)雜度都為O（l/ s），且可以采用并行策略，該復(fù)雜度也是整個(gè)算法的復(fù)雜度，且可以通過(guò)增加劃分參數(shù)s來(lái)提高算法的學(xué)習(xí)效率。改進(jìn)的快速K-近鄰分類方法具體如下：

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

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

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

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

（8）選擇測(cè)試集中的其他待測(cè)樣本，重復(fù)執(zhí)行（4）-（7）的步驟，直到待測(cè)樣本集中的所有樣本均得到其標(biāo)記；

（9）將待測(cè)樣本得到的標(biāo)簽與其真實(shí)標(biāo)簽對(duì)比，得到方法泛化性能，算法結(jié)束。

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

本文實(shí)驗(yàn)采用的UCI數(shù)據(jù)集見(jiàn)表1，并將其與標(biāo)準(zhǔn)的K-近鄰分類方法進(jìn)行了比較。實(shí)驗(yàn)中，將訓(xùn)練樣本都五等分，每次隨機(jī)選擇其中四份進(jìn)行五次實(shí)驗(yàn)，并取平均測(cè)試精度作為最終結(jié)果，實(shí)驗(yàn)環(huán)境為1臺(tái)PC （2.66GHz CPU，1G內(nèi)存），實(shí)驗(yàn)平臺(tái)是MATLAB 7.0。

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

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

從表2和表3可以看出，隨著聚類劃分參數(shù)的增加，SK-NN算法的學(xué)習(xí)效率逐步提高，但算法的測(cè)試精度略有下降；其次，與標(biāo)準(zhǔn)K-NN方法相比，本文提出的改進(jìn)快速K-NN分類方法在Thyroid上得到的最優(yōu)精度與標(biāo)準(zhǔn)K-NN相同，在其他三個(gè)數(shù)據(jù)集上得到的最優(yōu)精度也接近于標(biāo)準(zhǔn)K-NN的測(cè)試結(jié)果。從學(xué)習(xí)效率來(lái)講，SK-NN算法卻比K-NN算法有了明顯的提高。

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

3　結(jié)語(yǔ)

傳統(tǒng)K-近鄰分類方法需計(jì)算每個(gè)待測(cè)樣本與所有訓(xùn)練樣本的距離，學(xué)習(xí)效率低下，本文提出一種快速的K-近鄰分類方法，通過(guò)對(duì)訓(xùn)練樣本進(jìn)行K-均值聚類，劃分為多個(gè)訓(xùn)練子集，并計(jì)算每個(gè)子集的中心和半徑，然后判斷待測(cè)樣本與中心半徑的關(guān)系，來(lái)選擇合適的子集對(duì)待測(cè)樣本進(jìn)行標(biāo)簽判別，通過(guò)減少距離計(jì)算的規(guī)模提高了模型學(xué)習(xí)效率，有望在大規(guī)模的社會(huì)網(wǎng)絡(luò)、文本分類、生物信息學(xué)等領(lǐng)域得到應(yīng)用。

表2　平均測(cè)試精度（%）

表3　總訓(xùn)練時(shí)間（s）

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

［2］鐘曉，馬少平，張鈸等.數(shù)據(jù)挖掘綜述［J］.模式識(shí)別與人工智能，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］高學(xué)星，孫華剛，侯保林.使用不同置信級(jí)訓(xùn)練樣本的神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)方法［J］.電子與信息學(xué)報(bào)，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近鄰圖的自動(dòng)圖像標(biāo)注與快速求解算法［J］.計(jì)算機(jī)科學(xué)，2011，38（2）:277-280.

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

［12］楊帆，林琛，周綺鳳等.基于隨機(jī)森林的潛在k近鄰算法及其在基因表達(dá)數(shù)據(jù)分類中的應(yīng)用［J］.系統(tǒng)工程理論與實(shí)踐，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-），男，山西運(yùn)城人，碩士，工程師，研究方向?yàn)閿?shù)據(jù)挖掘、專業(yè)圖可視化、智能軟件設(shè)計(jì)

2015-11-04

2015-12-10

由于傳統(tǒng)K-近鄰分類方法需要計(jì)算每個(gè)待測(cè)樣本與所有訓(xùn)練樣本的距離，學(xué)習(xí)效率較低。針對(duì)這個(gè)問(wèn)題，提出一種改進(jìn)的快速K-近鄰分類方法SK-NN。該方法首先對(duì)訓(xùn)練樣本采用K-均值方法進(jìn)行聚類，并得到聚類結(jié)果中每個(gè)子集的中心和半徑，并根據(jù)其選擇合適的子類并采用該子類對(duì)待測(cè)樣本打標(biāo)簽。由于聚類后得到的子類的規(guī)模遠(yuǎn)小于原始樣本的規(guī)模，因此需要計(jì)算的距離數(shù)目減少，提高模型的效率。

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

程利濤（1982-），男，河北邯鄲人，碩士，工程師，研究方向?yàn)閿?shù)據(jù)挖掘、智能信息處理

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.