邱強

摘要：針對傳統(tǒng)K-近鄰（K-Nearest Neighbor， K-NN）分類方法不能高校處理大規(guī)模訓練數(shù)據(jù)的分類問題，該文提出一種并行的改進K-NN（Improved Parallel K-Nearest Neighbor， IPK-NN）分類方法。該方法首先將大規(guī)模訓練樣本隨機劃分為多個獨立同分布的工作集，對于任意一個新來的待檢測樣本，在每個工作集上采用標準K-NN方法對該樣本進行標記，然后綜合各訓練集的標記結(jié)果，得到該樣本的最終標記。實驗結(jié)果表明，在大規(guī)模數(shù)據(jù)集的分類問題中，IPK-NN方法能夠在保持較高分類精度的同時提高模型的學習效率。

關(guān)鍵詞： K-近鄰分類； 并行計算； 并行K-近鄰分類； 工作集

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2014）12-2825-03

A Parallel Improved K-Nearest Neighbor Classification Method

QIU Qiang

（China North Industries Group Corporation， Taiyuan 030600， China）

Abstract：To solve problems that traditional K-nearest neighbor （K-NN） classification algorithm can not solve the large scale training dataset classification problem， this paper presents a parallel improved K-nearest neighbor method， called IPK-NN classification algorithm. At first， the large scale training samples set is divided into some working sets with independent identical distribution. Then for a new query sample， by the traditional K-NN method， the label of it is obtained by every working set. Lastly， combining the label of every working set， the last optimal label of this query sample is obtained. Simulation results demonstrate that by this IPK-NN algorithm， the excellent classification efficiency is obtained with the high classification accuracy.

Key words： K-nearest neighbor； parallel computing； parallel K-NN classification； working set

隨著傳感器技術(shù)、存儲技術(shù)、計算機技術(shù)和網(wǎng)絡技術(shù)的迅猛發(fā)展以及人們管理與知識水平的提高，使得數(shù)據(jù)規(guī)模日益增大。2008年9月，《Nature》雜志推出了大數(shù)據(jù)存儲、管理和分析問題討論的?？痆1]，之后《Science》雜志也相繼出版了關(guān)于大數(shù)據(jù)的研究報告及?？痆2]。據(jù)中國互聯(lián)網(wǎng)信息中心（CNNIC）于2014年1月16日發(fā)布的《第33次中國互聯(lián)網(wǎng)絡發(fā)展狀況統(tǒng)計報告》研究報告指出，截止2013年12月中國網(wǎng)民數(shù)量達到6.18億。網(wǎng)絡技術(shù)的飛速發(fā)展、網(wǎng)民規(guī)模的日益增加，導致現(xiàn)實世界中處理問題的數(shù)據(jù)規(guī)模越來越大。為了能夠從海量數(shù)據(jù)中提煉出有用知識，數(shù)據(jù)挖掘技術(shù)便應用而生。數(shù)據(jù)挖掘[3]是指從大規(guī)模的、不完整的、有噪聲的、模糊的、隨機的復雜數(shù)據(jù)集中提取潛在有用的信息或知識。

分類作為一種重要的機器學習問題，目前已在圖像處理、文本分類、股票分析、生物信息學等領(lǐng)域得到了成功應用。目前，常用的分類模型包括：K-近鄰分類[4]、貝葉斯分類[5]、決策樹[6]、神經(jīng)網(wǎng)絡[7]等。

在這些分類方法中，K-近鄰方法是一種典型常用的分類方法[4， 8-9]。K-近鄰分類方法是通過衡量待測樣本[query]到所有訓練樣本之間的距離，然后選擇距離最近的k個近鄰構(gòu)成該待測樣本的近鄰集合，并選擇近鄰集合中類別較多的樣本的標簽作為待測樣本的標簽。但是，當訓練數(shù)據(jù)規(guī)模較大時，由于K-近鄰方法需要計算待測樣本到每個訓練樣本之間的距離，并進行他們之間的比較，因此時間復雜度較高，對大規(guī)模訓練數(shù)據(jù)的分類問題無法高效執(zhí)行。因此，如何提高K-近鄰分類方法的學習效率引起了研究者的廣泛關(guān)注。

隨著數(shù)據(jù)挖掘領(lǐng)域所處理樣本規(guī)模的日趨增大，要求研究人員能夠提出高效的挖掘算法來處理海量數(shù)據(jù)問題。并行計算作為一種定量、精細、高效的方法在海量數(shù)據(jù)挖掘中得到了成功的應用[10]。狹義上的并行計算是指在并行/分布式計算機上所做的計算，從廣義上講，將多個問題同時求解的過程都可以看作是并行計算的過程。盡管目前已經(jīng)有學者提出了一些基于并行計算的分類技術(shù)以改進傳統(tǒng)的分類方法[11]，但是，采用并行計算技術(shù)來提高傳統(tǒng)的K-近鄰分類方法處理大規(guī)模訓練數(shù)據(jù)的分類問題目前還缺乏相關(guān)研究。因此，如何結(jié)合并行計算技術(shù)進一步提高K-近鄰方法的訓練效率依然是一個值得探討的問題。

針對傳統(tǒng)K-近鄰分類方法不能高效處理大規(guī)模訓練數(shù)據(jù)分類的問題，該文提出一種基于并行計算的改進K-近鄰分類方法。該方法首先將K-近鄰分類中的訓練樣本隨機劃分為多個獨立同分布的工作子集，針對新來的一個待測樣本[query]，在每個工作子集上分別計算該工作子集中的訓練樣本與待測樣本間的距離，并根據(jù)該工作子集給待測樣本打一個標簽，最后將待測樣本得到的所有標簽進行集成，最終決定待測樣本所屬類別。endprint

1 傳統(tǒng)K-近鄰分類方法

假設訓練集為[Tr={X，Y}=（xi，yili=1]且[xi∈Rd]，其中[X]為訓練樣本集，[Y]為訓練樣本集標簽，測試集為[TE={TX}=（txjtj=1]，其中[TX]為測試樣本集，K-近鄰分類參數(shù)為[k]。傳統(tǒng)K-近鄰分類方法的目標即根據(jù)與測試樣本集[TX]中待測樣本[txj]相似度最高的[k]個訓練樣本來得到測試樣本[txj]的類別標簽[tyj]。傳統(tǒng)K-近鄰分類方法針對每個測試樣本[txj]，從訓練樣本集[X]中選擇與測試樣本[txj]距離最近的k個訓練樣本[k_Set=xqkq=1]，其中，任意一個訓練樣本[xi]與待測樣本[txj]的距離定義如下：

[d（xi，txj）=p=1d（xpi-txpj）2] （1）

其中，[xpi]表示訓練樣本[xi]的第[p]個分量，[txpj]表示待測樣本[txj]的第[p]個分量。假設離散目標函數(shù)為[f：Rd→Y]，即建立訓練樣本空間[Rd]與標簽域[Y]之間的對應關(guān)系，如[f（xi）=yi]，然后采用式（2）對測試樣本[txj]打標簽。

[tyi'=arg maxy∈Yi=1kδ（y，f（xi））] （2）

其中，[δ]函數(shù)如下：

[δ（a，b）=1， a=b0， a≠b] （3）

即可得到待測樣本[txj]的預測標簽[tyj]，針對待測樣本集[TX]中的每個待測樣本循環(huán)往復，得到待測樣本集[TX]中每個待測樣本的預測標簽，并將其與真實標簽比對，以衡量分類器性能。

但是，由于傳統(tǒng)[k]-NN分類方法時間復雜度較高，特別地，當訓練集規(guī)模[l]較大時，無法建立高性能的分類器。針對這個問題，該文提出一種并行的改進K-近鄰分類方法，該方法首先將訓練樣本劃分為多個獨立同分布的工作子集，然后針對新來的一個待測樣本，在每個工作子集上分別計算該工作子集中的訓練樣本與待測樣本之間的距離，并根據(jù)該工作子集給待測樣本打一個標簽，最后將待測樣本得到的所有標簽進行綜合決策，最終決定待測樣本所屬類別。

2 并行的改進K-近鄰分類方法

針對傳統(tǒng)K-近鄰分類方法對于大規(guī)模訓練數(shù)據(jù)的分類問題需要求解每一個待測樣本與所有訓練樣本之間的距離，因此時間復雜度較高，且容易受到噪聲樣本的影響。該文結(jié)合并行計算思想，提出一種基于并行計算的改進K-近鄰分類方法（IPK-NN）。假設訓練集為[Tr={X，Y}=（xi，yili=1]且[xi∈Rd]，其中[X]為訓練樣本集，[Y]為訓練樣本集標簽，測試集為[TE={TX}=（txjtj=1]，其中[TX]為測試樣本集。該方法首先將訓練樣本集[X]劃分為多個獨立同分布的工作子集，即：[X→{X1，X2，???，Xi，???，Xw}]，其中，[Xi={xi1，xi2，???，xij，???，xili}]。然后針對每一個新來的待測樣本[q]，衡量待測樣本[q]與訓練樣本子集[Xi]中每個樣本[xij（j=1，2，???，li）]之間的相似度，具體地，相似度求法如下：

[S（q，xij）=1k=1d（qk-xkij）2] （4）

然后選擇相似度最高的[ki]個樣本，將[ki]個樣本中最多的類別標簽[yi]作為待測樣本[q]的第[i]個類別標簽。

具體地，并行的改進K-近鄰分類算法如下：

初始化：設訓練集為[Tr={X，Y}=（xi，yili=1]且[xi∈Rd]，其中[X]為訓練樣本集，[Y]為訓練樣本集標簽，測試集為[TE={TX}=（txjtj=1]，其中[TX]為測試樣本集，待測樣本集為[Q={q1，q2，???qk，???，qz}]。隨機劃分工作子集參數(shù)為[w]，工作子集[Xi]的K-近鄰分類參數(shù)為[ki]。

Step1：將訓練樣本集[X]隨機劃分為[w]個獨立同分布的工作子集（這里可以采用不同的劃分方法），即得到劃分模式[X→{X1，???，Xi，???，Xw}]，其中，[Xi={xi1，xi2，???，xij，???，xili}]。

Step2：對于某個訓練樣本[qk]，并行地工作子集[X1，X2，???Xw]上分別執(zhí)行傳統(tǒng)的K-近鄰分類算法，得到其第[i]個標簽[yi（qk）]，具體過程如下：

Step2.1：根據(jù)式（4）計算工作子集[Xi]中每個樣本[xij]與待測樣本[qk]之間的相似度[S（qk，xij）]；

Step2.2：從工作子集[Xi]中選擇[ki]個與待測樣本[qk]之間相似度最高的樣本，構(gòu)成待測樣本[qk]的第[i]個決策子集[Di（qk）]；

Step2.3：觀測待測樣本[qk]的第[i]個決策子集[Di（qk）]中每個樣本的類別標簽，選擇最多的類別標簽作為待測樣本[qk]的第[i]個標簽[yi（qk）]。

Step3：根綜合在[w]個工作子集上所得到的[w]個類別標簽[y1（qk），y2（qk）???，yw（qk）]，根據(jù)式（5）對待測樣本[qk]打標簽，即：

[y（qk）=arg（max（counti=1，???，w（yi（qk））））] （5）

其中，[count（?）]為計數(shù)函數(shù)，即統(tǒng)計相同元素個數(shù)。

Step4：在待測樣本集的每個待測樣本上重復執(zhí)行Step2-Step3的過程，得到所有待測樣本的預測標簽，算法結(jié)束。

3 實驗結(jié)果集分析

為驗證本文提出的并行的改進K-近鄰分類方法的性能，該文在一些標準的數(shù)據(jù)集上進行了實驗，并將所提出的并行改進K-近鄰方法與傳統(tǒng)K-近鄰方法進行了比較。實驗采用的數(shù)據(jù)集見表1，其中第一個數(shù)據(jù)集為人工生成的數(shù)據(jù)集，其他數(shù)據(jù)集為UCI中的標準數(shù)據(jù)集。

從表2可以看出，在數(shù)據(jù)集Heart、Diabetis、Flare和Image上，該文提出的并行的改進K-近鄰方法比傳統(tǒng)K-近鄰方法在精度上都有提高，特別地，在數(shù)據(jù)集Flare上的精度提高值接近6%，而只有在Gaussian分布的數(shù)據(jù)集上精度有所降低，這說明在多數(shù)情況下（特別是訓練數(shù)據(jù)規(guī)模較大時），該文提出的方法能夠有效地避免噪聲數(shù)據(jù)，減小其對測試精度的影響，提高算法的分類性能。同時，從分類時間看，除數(shù)據(jù)集Gaussian外，在其他數(shù)據(jù)集上，該文提出的方法都縮短了學習時間，特別當訓練數(shù)據(jù)集比較大時，該文提出的方法在學習效率方面的提高尤為明顯，如在數(shù)據(jù)集Flare和Image上，學習效率都有了2-3倍的提高。endprint

綜上可看出，由于本文提出的并行的改進K-近鄰分類方法通過采用并行計算的思想，將原始的大規(guī)模訓練集分解成為多個小規(guī)模的工作子集，從而并行地在每個工作子集上對預測樣本打標簽，減小了噪聲樣本對分類結(jié)果的影響，在提高分類精度的同時大幅度提高了學習效率。

4 結(jié)論

K-近鄰分類方法是近年來機器學習領(lǐng)域一種常用的分類方法，并在圖像處理、模式識別等領(lǐng)域得到了成功應用。但是，由于傳統(tǒng)K-近鄰分類方法需要求解待測樣本與所有訓練樣本之前的距離，并進行比較，且這個過程是串行執(zhí)行的，因此學習效率較低，特別地對于大規(guī)模訓練數(shù)據(jù)無法進行高效分類。針對這個問題，該文提出一種并行的改進K-近鄰分類方法，該方法通過將訓練樣本劃分為多個獨立同分布的工作子集，然后針對新來的一個待測樣本，在每個工作子集上分別計算該工作子集中的訓練樣本與待測樣本之間的距離，并根據(jù)該工作子集給待測樣本打一個標簽，最后將待測樣本得到的所有標簽進行綜合決策，最終決定待測樣本所屬類別，減小了噪聲樣本的影響，在提高分類精度的同時提高了分類效率，有望解決實際的海量數(shù)據(jù)分類問題。在未來的工作中，將進一步結(jié)合當前最新的特征選擇算法，來提高本文模型處理復雜高維問題，如圖像分類、文本分類等的性能。

參考文獻：

[1] Big Data [EB/OL]. Nature ，2008， 455， 7209， 1-136.

[2] Special online collection： Dealing with data [EB/OL]. Science， 2011， 331， 6018.

[3] 唐新宇. 淺析數(shù)據(jù)挖掘中的聚類分析 [J]. 電腦知識與技術(shù)，2013， 9（9）： 2031-2032.

[4] Liu Z G， Pan Q， Dezert J. A new belief-based K-nearest neighbor classification method [J]. Pattern Recognition， 2013， 48（3）： 834-844.

[5] 劉曉潔. 基于PCA的貝葉斯網(wǎng)絡分類器研究 [J]. 電子設計工程，2009， 17（9）： 86-88.

[6] Haim Y B， Tov E T. A streaming parallel decision tree algorithm [J]. Journal of Machine Learning Research， 2010， 11， 849-872.

[7] 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.

[8] 郭躬德，黃杰，陳黎飛. 基于KNN模型的增量學習算法[J]. 模式識別與人工智能， 2010， 23（5）： 701-707.

[9] Nicolas G P， Domingo O B. Boosting k-nearest neighbor classifier by means of input space projection [J]. Expert Systems with Applications， 2009， 36（7）： 10570-10582.

[10] 曹小林，張愛清，莫則堯. 基于面向?qū)ο蟮牧Ｗ宇惸M并行計算研究 [J]. 計算機研究與發(fā)展，2007， 44（10）： 1647-1651.

[11] Lu B， Tan C H， Cardie C， et al. Joint Bilingual Sentiment Classification with Unlabeled Parallel Corpora [C]. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics， Portland， Oregon， 320-330.endprint

綜上可看出，由于本文提出的并行的改進K-近鄰分類方法通過采用并行計算的思想，將原始的大規(guī)模訓練集分解成為多個小規(guī)模的工作子集，從而并行地在每個工作子集上對預測樣本打標簽，減小了噪聲樣本對分類結(jié)果的影響，在提高分類精度的同時大幅度提高了學習效率。

4 結(jié)論

K-近鄰分類方法是近年來機器學習領(lǐng)域一種常用的分類方法，并在圖像處理、模式識別等領(lǐng)域得到了成功應用。但是，由于傳統(tǒng)K-近鄰分類方法需要求解待測樣本與所有訓練樣本之前的距離，并進行比較，且這個過程是串行執(zhí)行的，因此學習效率較低，特別地對于大規(guī)模訓練數(shù)據(jù)無法進行高效分類。針對這個問題，該文提出一種并行的改進K-近鄰分類方法，該方法通過將訓練樣本劃分為多個獨立同分布的工作子集，然后針對新來的一個待測樣本，在每個工作子集上分別計算該工作子集中的訓練樣本與待測樣本之間的距離，并根據(jù)該工作子集給待測樣本打一個標簽，最后將待測樣本得到的所有標簽進行綜合決策，最終決定待測樣本所屬類別，減小了噪聲樣本的影響，在提高分類精度的同時提高了分類效率，有望解決實際的海量數(shù)據(jù)分類問題。在未來的工作中，將進一步結(jié)合當前最新的特征選擇算法，來提高本文模型處理復雜高維問題，如圖像分類、文本分類等的性能。

參考文獻：

[1] Big Data [EB/OL]. Nature ，2008， 455， 7209， 1-136.

[2] Special online collection： Dealing with data [EB/OL]. Science， 2011， 331， 6018.

[3] 唐新宇. 淺析數(shù)據(jù)挖掘中的聚類分析 [J]. 電腦知識與技術(shù)，2013， 9（9）： 2031-2032.

[4] Liu Z G， Pan Q， Dezert J. A new belief-based K-nearest neighbor classification method [J]. Pattern Recognition， 2013， 48（3）： 834-844.

[5] 劉曉潔. 基于PCA的貝葉斯網(wǎng)絡分類器研究 [J]. 電子設計工程，2009， 17（9）： 86-88.

[6] Haim Y B， Tov E T. A streaming parallel decision tree algorithm [J]. Journal of Machine Learning Research， 2010， 11， 849-872.

[7] 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.

[8] 郭躬德，黃杰，陳黎飛. 基于KNN模型的增量學習算法[J]. 模式識別與人工智能， 2010， 23（5）： 701-707.

[9] Nicolas G P， Domingo O B. Boosting k-nearest neighbor classifier by means of input space projection [J]. Expert Systems with Applications， 2009， 36（7）： 10570-10582.

[10] 曹小林，張愛清，莫則堯. 基于面向?qū)ο蟮牧Ｗ宇惸M并行計算研究 [J]. 計算機研究與發(fā)展，2007， 44（10）： 1647-1651.

[11] Lu B， Tan C H， Cardie C， et al. Joint Bilingual Sentiment Classification with Unlabeled Parallel Corpora [C]. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics， Portland， Oregon， 320-330.endprint

綜上可看出，由于本文提出的并行的改進K-近鄰分類方法通過采用并行計算的思想，將原始的大規(guī)模訓練集分解成為多個小規(guī)模的工作子集，從而并行地在每個工作子集上對預測樣本打標簽，減小了噪聲樣本對分類結(jié)果的影響，在提高分類精度的同時大幅度提高了學習效率。

4 結(jié)論

K-近鄰分類方法是近年來機器學習領(lǐng)域一種常用的分類方法，并在圖像處理、模式識別等領(lǐng)域得到了成功應用。但是，由于傳統(tǒng)K-近鄰分類方法需要求解待測樣本與所有訓練樣本之前的距離，并進行比較，且這個過程是串行執(zhí)行的，因此學習效率較低，特別地對于大規(guī)模訓練數(shù)據(jù)無法進行高效分類。針對這個問題，該文提出一種并行的改進K-近鄰分類方法，該方法通過將訓練樣本劃分為多個獨立同分布的工作子集，然后針對新來的一個待測樣本，在每個工作子集上分別計算該工作子集中的訓練樣本與待測樣本之間的距離，并根據(jù)該工作子集給待測樣本打一個標簽，最后將待測樣本得到的所有標簽進行綜合決策，最終決定待測樣本所屬類別，減小了噪聲樣本的影響，在提高分類精度的同時提高了分類效率，有望解決實際的海量數(shù)據(jù)分類問題。在未來的工作中，將進一步結(jié)合當前最新的特征選擇算法，來提高本文模型處理復雜高維問題，如圖像分類、文本分類等的性能。

參考文獻：

[1] Big Data [EB/OL]. Nature ，2008， 455， 7209， 1-136.

[2] Special online collection： Dealing with data [EB/OL]. Science， 2011， 331， 6018.

[3] 唐新宇. 淺析數(shù)據(jù)挖掘中的聚類分析 [J]. 電腦知識與技術(shù)，2013， 9（9）： 2031-2032.

[4] Liu Z G， Pan Q， Dezert J. A new belief-based K-nearest neighbor classification method [J]. Pattern Recognition， 2013， 48（3）： 834-844.

[5] 劉曉潔. 基于PCA的貝葉斯網(wǎng)絡分類器研究 [J]. 電子設計工程，2009， 17（9）： 86-88.

[6] Haim Y B， Tov E T. A streaming parallel decision tree algorithm [J]. Journal of Machine Learning Research， 2010， 11， 849-872.

[7] 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.

[8] 郭躬德，黃杰，陳黎飛. 基于KNN模型的增量學習算法[J]. 模式識別與人工智能， 2010， 23（5）： 701-707.

[9] Nicolas G P， Domingo O B. Boosting k-nearest neighbor classifier by means of input space projection [J]. Expert Systems with Applications， 2009， 36（7）： 10570-10582.

[10] 曹小林，張愛清，莫則堯. 基于面向?qū)ο蟮牧Ｗ宇惸M并行計算研究 [J]. 計算機研究與發(fā)展，2007， 44（10）： 1647-1651.

[11] Lu B， Tan C H， Cardie C， et al. Joint Bilingual Sentiment Classification with Unlabeled Parallel Corpora [C]. Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics， Portland， Oregon， 320-330.endprint