基于数据块混合度量的加速K-近邻分类方法

摘要

针对标准K-近邻分类方法( K-Nearest Neighbor, KNN)在新样本类别预测过程中需要计算新样本与所有已标记样本距离而导致分类效率低,不能有效处理大规模数据分类的问题,本文提出一种基于数据块混合度量的加速K-近邻分类( KNN Method Based on Data Block Mixed Measurement, KNN_DBM2)方法。该方法将数据块的混合度量引入K-NN的预测类别过程,首先将已标记的数据划分为不同的数据块,计算每个数据块的中心及数据块的混合度,当待测样本进入时,计算待测样本与所有数据块中心的距离,并选择距离待测样本最近的k个数据块,若k个数据块均为纯数据块,则根据中心标签并采用少数服从多数的原则对待测样本打标签,若存在混合度较高的数据块,则计算待测样本与该混合数据块所有样本的距离及与其他纯的数据块中心的距离,并选择最近的k个样本或中心对待测样本打标签。通过这种数据块划分及混合度量的方式,可以减少需要计算的待测样本与其他已标记样本距离的个数,提高K-近邻分类方法的预测性能。实验结果表明,本文提出的KNN_DBM2方法能够获得较高的样本预测速度和较好的预测准确率。%This paper presents a K-Nearest Neighbor ( KNN) method based on data block mixed measurement, called KNN_DBM2 , in order to solve the problem that the low training efficiency and cannot solve the large scale problems of normal K-NN be-cause it needs compute the distance between the sample to be tested and the labeled samples in the new sample classification pre-diction process. By introducing the data block mixed measurement into the prediction process of K-NN, this method divides the labeled samples into many various data blocks, and the mixing degree and center of these blocks are computed. When the new sample to be tested is produced, all the distances between this sample and all the centers of data blocks are computed and the nearest k data blocks are extracted. If all these k data blocks are purity, then label the sample to be tested according to the cen-ters label and adopting a minority to obey the majority. But if the mixed data blocks are existed in these blocks, the distance be-tween the sample and all the samples in mixed data block is calculated, and the distance from the center of the other pure data blocks is also calculated, then label of the sample to be tested by the k nearest sample or centers. By this data block dividing and mixed measurement method, it reduces the number of distances between the sample to be tested and the other labeled samples and obtains the high prediction efficiency synchronously. The experiment results demonstrate that the proposed KNN_DBM2 model can obtain the high learning efficiency and testing accuracy simultaneously.