论文部分内容阅读
由于K-近邻(K-NearestNeighbor,KNN)分类直观、简单、有效、易实现等优点,广泛应用于模式识别、机器学习、数据挖掘等领域中,更在2005年的ECDM国际会议上被选为十大最有影响力的数据挖掘算法。目前,在K-近邻方面的研究主要集中在对待测样本的分类正确性、减小分类搜索算法的复杂度、以及近邻k值的选择等方面。本文主要围绕K-近邻分类展开研究。首先,通过查找待测样本的近质心近邻,提出了伪近质心近邻分类算法(Pseudo Nearest Centroid Neighbor,PNCN),来解决在小样本数据集上的分类易受到局外点影响这一问题;其次,通过计算待测样本的多个调和平均距离,提出了基于调和平均距离的k近邻分类算法(Harmonic Mean Distance-based K-Nearest Neighbor,HMDKNN),来解决分类算法对近邻 k值的敏感性;最后,通过训练样本的稀疏表示系数来选择k个代表性最近邻,提出了系数加权 K 最近邻分类算法(Coefficient-Weighted K-Nearest Neighbor,CWKNN)和残差加权K最近邻分类算法(Residual-Weighted K-Nearest Neighbor,RWKNN),来克服使用欧氏距离查找近邻的局限性,提高近邻分类性能。本文的主要研究工作及创新点如下:1.为解决在小样本数据集中,KNN分类性能易受离群点影响这一问题,提出了伪近质心近邻分类算法(PNCN)。由于PNCN采用训练样本中每个类的k个近质心近邻点所对应的k个局部均值点来计算伪近质心近邻点,一定程度考虑到了待测样本近邻点的相似性和空间分布,从理论上来说,其分类正确率比其它类似算法要高。实验结果表明,PNCN分类算法与其它类似分类算法相比,无论是在真实小样本数据集上,还是有噪声的小样本数据集上,都有着较高的分类正确率,且对于近邻k值有着较好的鲁棒性。2.为了克服分类正确率易受k值的影响,提高近邻分类性能,基于局部均值向量和每个类中k个最近邻的多个调和平均距离,提出了调和平均距离k近邻分类算法(HMDKNN)。该算法首先在数据集的每个类中,计算待测样本的k个最近邻的局部均值向量,并计算每个类中k个局部均值向量的嵌套调和平均距离,将待测样本划分到最小嵌套调和平均距离值所对应的类别。由于采用多个局部均值向量、多个调和平均距离和每个类的嵌套调和平均距离,HMDKNN与其它类似算法相比,不管是在UCI及KEEL真实数据集,还是人工数据集、噪声数据集及时间序列数据集上,都进一步降低了分类时对近邻k值的敏感性,提高了分类正确率。3.由于稀疏系数能够较好地表现数据之间的相似性和潜在的可判别信息,通过计算待测样本x的所有训练样本的稀疏系数来选择k个代表性最近邻,提出了两种基于稀疏系数的加权近邻分类算法:系数加权K最近邻分类算法(CWKNN)和残差加权K最近邻分类算法(RWKNN)。在CWKNN中,通过稀疏系数选择待测样本的k个最近邻,并将每个近邻的稀疏系数作为其权重,用于近邻分类。在RWKNN中,通过稀疏系数选择待测样本的众个最近邻,然后计算这k个最近邻与待测样本之间的重构残差,最后用重构残差进行加权投票对待测样本进行分类。实验结果表明,CWKNN和RWKNN与其它类似分类算法相比,在真实数据集、人工数据集和噪声数据集上都具有更好的分类性能,且在近邻k值变化时其分类有着良好的鲁棒性。