邱強(qiáng)

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

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

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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ù)、存儲(chǔ)技術(shù)、計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的迅猛發(fā)展以及人們管理與知識(shí)水平的提高，使得數(shù)據(jù)規(guī)模日益增大。2008年9月，《Nature》雜志推出了大數(shù)據(jù)存儲(chǔ)、管理和分析問題討論的專刊[1]，之后《Science》雜志也相繼出版了關(guān)于大數(shù)據(jù)的研究報(bào)告及專刊[2]。據(jù)中國互聯(lián)網(wǎng)信息中心（CNNIC）于2014年1月16日發(fā)布的《第33次中國互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告》研究報(bào)告指出，截止2013年12月中國網(wǎng)民數(shù)量達(dá)到6.18億。網(wǎng)絡(luò)技術(shù)的飛速發(fā)展、網(wǎng)民規(guī)模的日益增加，導(dǎo)致現(xiàn)實(shí)世界中處理問題的數(shù)據(jù)規(guī)模越來越大。為了能夠從海量數(shù)據(jù)中提煉出有用知識(shí)，數(shù)據(jù)挖掘技術(shù)便應(yīng)用而生。數(shù)據(jù)挖掘[3]是指從大規(guī)模的、不完整的、有噪聲的、模糊的、隨機(jī)的復(fù)雜數(shù)據(jù)集中提取潛在有用的信息或知識(shí)。

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

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

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

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

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

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

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

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

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

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

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

即可得到待測(cè)樣本[txj]的預(yù)測(cè)標(biāo)簽[tyj]，針對(duì)待測(cè)樣本集[TX]中的每個(gè)待測(cè)樣本循環(huán)往復(fù)，得到待測(cè)樣本集[TX]中每個(gè)待測(cè)樣本的預(yù)測(cè)標(biāo)簽，并將其與真實(shí)標(biāo)簽比對(duì)，以衡量分類器性能。

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

2 并行的改進(jìn)K-近鄰分類方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果集分析

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

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

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

4 結(jié)論

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

參考文獻(xiàn)：

[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í)與技術(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)絡(luò)分類器研究 [J]. 電子設(shè)計(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模型的增量學(xué)習(xí)算法[J]. 模式識(shí)別與人工智能， 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] 曹小林，張愛清，莫?jiǎng)t堯. 基于面向?qū)ο蟮牧Ｗ宇惸M并行計(jì)算研究 [J]. 計(jì)算機(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

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

4 結(jié)論

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

參考文獻(xiàn)：

[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í)與技術(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)絡(luò)分類器研究 [J]. 電子設(shè)計(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模型的增量學(xué)習(xí)算法[J]. 模式識(shí)別與人工智能， 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] 曹小林，張愛清，莫?jiǎng)t堯. 基于面向?qū)ο蟮牧Ｗ宇惸M并行計(jì)算研究 [J]. 計(jì)算機(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

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

4 結(jié)論

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

參考文獻(xiàn)：

[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í)與技術(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)絡(luò)分類器研究 [J]. 電子設(shè)計(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模型的增量學(xué)習(xí)算法[J]. 模式識(shí)別與人工智能， 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] 曹小林，張愛清，莫?jiǎng)t堯. 基于面向?qū)ο蟮牧Ｗ宇惸M并行計(jì)算研究 [J]. 計(jì)算機(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