一种并行的改进K—近邻分类方法

邱强

摘要：针对传统K-近邻（K-Nearest Neighbor， K-NN）分类方法不能高校处理大规模训练数据的分类问题，该文提出一种并行的改进K-NN（Improved Parallel K-Nearest Neighbor， IPK-NN）分类方法。该方法首先将大规模训练样本随机划分为多个独立同分布的工作集，对于任意一个新来的待检测样本，在每个工作集上采用标准K-NN方法对该样本进行标记，然后综合各训练集的标记结果，得到该样本的最终标记。实验结果表明，在大规模数据集的分类问题中，IPK-NN方法能够在保持较高分类精度的同时提高模型的学习效率。

关键词： 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

随着传感器技术、存储技术、计算机技术和网络技术的迅猛发展以及人们管理与知识水平的提高，使得数据规模日益增大。2008年9月，《Nature》杂志推出了大数据存储、管理和分析问题讨论的专刊[1]，之后《Science》杂志也相继出版了关于大数据的研究报告及专刊[2]。据中国互联网信息中心（CNNIC）于2014年1月16日发布的《第33次中国互联网络发展状况统计报告》研究报告指出，截止2013年12月中国网民数量达到6.18亿。网络技术的飞速发展、网民规模的日益增加，导致现实世界中处理问题的数据规模越来越大。为了能够从海量数据中提炼出有用知识，数据挖掘技术便应用而生。数据挖掘[3]是指从大规模的、不完整的、有噪声的、模糊的、随机的复杂数据集中提取潜在有用的信息或知识。

分类作为一种重要的机器学习问题，目前已在图像处理、文本分类、股票分析、生物信息学等领域得到了成功应用。目前，常用的分类模型包括：K-近邻分类[4]、贝叶斯分类[5]、决策树[6]、神经网络[7]等。

在这些分类方法中，K-近邻方法是一种典型常用的分类方法[4， 8-9]。K-近邻分类方法是通过衡量待测样本[query]到所有训练样本之间的距离，然后选择距离最近的k个近邻构成该待测样本的近邻集合，并选择近邻集合中类别较多的样本的标签作为待测样本的标签。但是，当训练数据规模较大时，由于K-近邻方法需要计算待测样本到每个训练样本之间的距离，并进行他们之间的比较，因此时间复杂度较高，对大规模训练数据的分类问题无法高效执行。因此，如何提高K-近邻分类方法的学习效率引起了研究者的广泛关注。

随着数据挖掘领域所处理样本规模的日趋增大，要求研究人员能够提出高效的挖掘算法来处理海量数据问题。并行计算作为一种定量、精细、高效的方法在海量数据挖掘中得到了成功的应用[10]。狭义上的并行计算是指在并行/分布式计算机上所做的计算，从广义上讲，将多个问题同时求解的过程都可以看作是并行计算的过程。尽管目前已经有学者提出了一些基于并行计算的分类技术以改进传统的分类方法[11]，但是，采用并行计算技术来提高传统的K-近邻分类方法处理大规模训练数据的分类问题目前还缺乏相关研究。因此，如何结合并行计算技术进一步提高K-近邻方法的训练效率依然是一个值得探讨的问题。

针对传统K-近邻分类方法不能高效处理大规模训练数据分类的问题，该文提出一种基于并行计算的改进K-近邻分类方法。该方法首先将K-近邻分类中的训练样本随机划分为多个独立同分布的工作子集，针对新来的一个待测样本[query]，在每个工作子集上分别计算该工作子集中的训练样本与待测样本间的距离，并根据该工作子集给待测样本打一个标签，最后将待测样本得到的所有标签进行集成，最终决定待测样本所属类别。endprint

1 传统K-近邻分类方法

假设训练集为[Tr={X，Y}=（xi，yili=1]且[xi∈Rd]，其中[X]为训练样本集，[Y]为训练样本集标签，测试集为[TE={TX}=（txjtj=1]，其中[TX]为测试样本集，K-近邻分类参数为[k]。传统K-近邻分类方法的目标即根据与测试样本集[TX]中待测样本[txj]相似度最高的[k]个训练样本来得到测试样本[txj]的类别标签[tyj]。传统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]个分量。假设离散目标函数为[f：Rd→Y]，即建立训练样本空间[Rd]与标签域[Y]之间的对应关系，如[f（xi）=yi]，然后采用式（2）对测试样本[txj]打标签。

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

其中，[δ]函数如下：

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

即可得到待测样本[txj]的预测标签[tyj]，针对待测样本集[TX]中的每个待测样本循环往复，得到待测样本集[TX]中每个待测样本的预测标签，并将其与真实标签比对，以衡量分类器性能。

但是，由于传统[k]-NN分类方法时间复杂度较高，特别地，当训练集规模[l]较大时，无法建立高性能的分类器。针对这个问题，该文提出一种并行的改进K-近邻分类方法，该方法首先将训练样本划分为多个独立同分布的工作子集，然后针对新来的一个待测样本，在每个工作子集上分别计算该工作子集中的训练样本与待测样本之间的距离，并根据该工作子集给待测样本打一个标签，最后将待测样本得到的所有标签进行综合决策，最终决定待测样本所属类别。

2 并行的改进K-近邻分类方法

针对传统K-近邻分类方法对于大规模训练数据的分类问题需要求解每一个待测样本与所有训练样本之间的距离，因此时间复杂度较高，且容易受到噪声样本的影响。该文结合并行计算思想，提出一种基于并行计算的改进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}]。随机划分工作子集参数为[w]，工作子集[Xi]的K-近邻分类参数为[ki]。

Step1：将训练样本集[X]随机划分为[w]个独立同分布的工作子集（这里可以采用不同的划分方法），即得到划分模式[X→{X1，???，Xi，???，Xw}]，其中，[Xi={xi1，xi2，???，xij，???，xili}]。

Step2：对于某个训练样本[qk]，并行地工作子集[X1，X2，???Xw]上分别执行传统的K-近邻分类算法，得到其第[i]个标签[yi（qk）]，具体过程如下：

Step2.1：根据式（4）计算工作子集[Xi]中每个样本[xij]与待测样本[qk]之间的相似度[S（qk，xij）]；

Step2.2：从工作子集[Xi]中选择[ki]个与待测样本[qk]之间相似度最高的样本，构成待测样本[qk]的第[i]个决策子集[Di（qk）]；

Step2.3：观测待测样本[qk]的第[i]个决策子集[Di（qk）]中每个样本的类别标签，选择最多的类别标签作为待测样本[qk]的第[i]个标签[yi（qk）]。

Step3：根综合在[w]个工作子集上所得到的[w]个类别标签[y1（qk），y2（qk）???，yw（qk）]，根据式（5）对待测样本[qk]打标签，即：

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

其中，[count（?）]为计数函数，即统计相同元素个数。

Step4：在待测样本集的每个待测样本上重复执行Step2-Step3的过程，得到所有待测样本的预测标签，算法结束。

3 实验结果集分析

为验证本文提出的并行的改进K-近邻分类方法的性能，该文在一些标准的数据集上进行了实验，并将所提出的并行改进K-近邻方法与传统K-近邻方法进行了比较。实验采用的数据集见表1，其中第一个数据集为人工生成的数据集，其他数据集为UCI中的标准数据集。

从表2可以看出，在数据集Heart、Diabetis、Flare和Image上，该文提出的并行的改进K-近邻方法比传统K-近邻方法在精度上都有提高，特别地，在数据集Flare上的精度提高值接近6%，而只有在Gaussian分布的数据集上精度有所降低，这说明在多数情况下（特别是训练数据规模较大时），该文提出的方法能够有效地避免噪声数据，减小其对测试精度的影响，提高算法的分类性能。同时，从分类时间看，除数据集Gaussian外，在其他数据集上，该文提出的方法都缩短了学习时间，特别当训练数据集比较大时，该文提出的方法在学习效率方面的提高尤为明显，如在数据集Flare和Image上，学习效率都有了2-3倍的提高。endprint

综上可看出，由于本文提出的并行的改进K-近邻分类方法通过采用并行计算的思想，将原始的大规模训练集分解成为多个小规模的工作子集，从而并行地在每个工作子集上对预测样本打标签，减小了噪声样本对分类结果的影响，在提高分类精度的同时大幅度提高了学习效率。

4 结论

K-近邻分类方法是近年来机器学习领域一种常用的分类方法，并在图像处理、模式识别等领域得到了成功应用。但是，由于传统K-近邻分类方法需要求解待测样本与所有训练样本之前的距离，并进行比较，且这个过程是串行执行的，因此学习效率较低，特别地对于大规模训练数据无法进行高效分类。针对这个问题，该文提出一种并行的改进K-近邻分类方法，该方法通过将训练样本划分为多个独立同分布的工作子集，然后针对新来的一个待测样本，在每个工作子集上分别计算该工作子集中的训练样本与待测样本之间的距离，并根据该工作子集给待测样本打一个标签，最后将待测样本得到的所有标签进行综合决策，最终决定待测样本所属类别，减小了噪声样本的影响，在提高分类精度的同时提高了分类效率，有望解决实际的海量数据分类问题。在未来的工作中，将进一步结合当前最新的特征选择算法，来提高本文模型处理复杂高维问题，如图像分类、文本分类等的性能。

参考文献：

[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] 唐新宇. 浅析数据挖掘中的聚类分析 [J]. 电脑知识与技术，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的贝叶斯网络分类器研究 [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] 曹小林，张爱清，莫则尧. 基于面向对象的粒子类模拟并行计算研究 [J]. 计算机研究与发展，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-近邻分类方法通过采用并行计算的思想，将原始的大规模训练集分解成为多个小规模的工作子集，从而并行地在每个工作子集上对预测样本打标签，减小了噪声样本对分类结果的影响，在提高分类精度的同时大幅度提高了学习效率。

4 结论

K-近邻分类方法是近年来机器学习领域一种常用的分类方法，并在图像处理、模式识别等领域得到了成功应用。但是，由于传统K-近邻分类方法需要求解待测样本与所有训练样本之前的距离，并进行比较，且这个过程是串行执行的，因此学习效率较低，特别地对于大规模训练数据无法进行高效分类。针对这个问题，该文提出一种并行的改进K-近邻分类方法，该方法通过将训练样本划分为多个独立同分布的工作子集，然后针对新来的一个待测样本，在每个工作子集上分别计算该工作子集中的训练样本与待测样本之间的距离，并根据该工作子集给待测样本打一个标签，最后将待测样本得到的所有标签进行综合决策，最终决定待测样本所属类别，减小了噪声样本的影响，在提高分类精度的同时提高了分类效率，有望解决实际的海量数据分类问题。在未来的工作中，将进一步结合当前最新的特征选择算法，来提高本文模型处理复杂高维问题，如图像分类、文本分类等的性能。

参考文献：

[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] 唐新宇. 浅析数据挖掘中的聚类分析 [J]. 电脑知识与技术，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的贝叶斯网络分类器研究 [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] 曹小林，张爱清，莫则尧. 基于面向对象的粒子类模拟并行计算研究 [J]. 计算机研究与发展，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-近邻分类方法通过采用并行计算的思想，将原始的大规模训练集分解成为多个小规模的工作子集，从而并行地在每个工作子集上对预测样本打标签，减小了噪声样本对分类结果的影响，在提高分类精度的同时大幅度提高了学习效率。

4 结论

K-近邻分类方法是近年来机器学习领域一种常用的分类方法，并在图像处理、模式识别等领域得到了成功应用。但是，由于传统K-近邻分类方法需要求解待测样本与所有训练样本之前的距离，并进行比较，且这个过程是串行执行的，因此学习效率较低，特别地对于大规模训练数据无法进行高效分类。针对这个问题，该文提出一种并行的改进K-近邻分类方法，该方法通过将训练样本划分为多个独立同分布的工作子集，然后针对新来的一个待测样本，在每个工作子集上分别计算该工作子集中的训练样本与待测样本之间的距离，并根据该工作子集给待测样本打一个标签，最后将待测样本得到的所有标签进行综合决策，最终决定待测样本所属类别，减小了噪声样本的影响，在提高分类精度的同时提高了分类效率，有望解决实际的海量数据分类问题。在未来的工作中，将进一步结合当前最新的特征选择算法，来提高本文模型处理复杂高维问题，如图像分类、文本分类等的性能。

参考文献：

[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] 唐新宇. 浅析数据挖掘中的聚类分析 [J]. 电脑知识与技术，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的贝叶斯网络分类器研究 [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] 曹小林，张爱清，莫则尧. 基于面向对象的粒子类模拟并行计算研究 [J]. 计算机研究与发展，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