流形上k最近邻分类方法.docVIP

流形上k最近邻分类方法 　　摘 要：针对分类数据中存在噪声样本和维数问题，提出了流形上的k最近邻方法。首先，利用贝叶斯公式对经典k最近邻方法进行扩展，并采用核概率密度方法估计样本的局部联合概率密度；其次，建立噪声样本点对模型，并构建改进的边际本征图和相应的权值矩阵，通过定义目标函数寻找最优降维映射矩阵；最后，提出一个完整的流形上k最近邻算法。与6种经典方法在12个常用数据集上的实验比较表明，在大多数情况下所提方法的分类性能要优于其他方法。 　　关键词：k最近邻；噪声样本；降维；分类器；流形 　　中图分类号： TP391 　　文献标志码：A 　　k-nearest neighbors classifier over manifolds 　　WEN Zhi-qiang*， HU Yong-xiang， ZHU Wen-qiu 　　School of Computer and Communication， Hunan University of Technology， Zhuzhou Hunan 412007， China 　　Abstract： 　　For resolving the problem of the existing noise sample and large number of dimensions， the k-nearest neighbors classifier over manifolds was presented in this paper. Firstly the classic k-nearest neighbors was extended by Bayes theorem and local joint probability density was estimated by kernel density estimation in classifier. In addition， after building the noise sample model， an objective function was defined via improved marginal intrinsic graph and its weight matrix for searching the optimal dimension reduction mapping matrix. At last， details about k-nearest neighbors algorithm over manifolds were provided. The experimental results demonstrate that the presented method has lower classification error rate than six kinds of classic methods in most cases on twelve data sets. 　　英文关键词　Key words： 　　k-Nearest Neighbors （kNN）； noise sample； dimensionality reduction； classifier； manifold 　　0 引言 　　k最近邻（k-Nearest Neighbors， kNN）方法是一种简单而高效的监督分类方法，其思想是找到测试样本在训练样本集中的k个最近邻对象，然后根据这些对象的类别属性进行投票，决定测试样本的类别属性。kNN方法的优势在于无须事先知道训练样本的属性值分布，而且不要求获取显式规则。一般来说，kNN的分类准确率要高于其他分类方法，且有坚实理论基础，包括误差??计[1]和误差边界[2]等理论，目前在文本分类、模式识别、图像分类等领域得到广泛应用。然而，kNN算法也有一些不足：首先，由于存在维数灾难问题，kNN算法不适合用于高维数据的分类；其次，当类条件概率分布为不可分或重叠时，邻域中的训练样本将会具有不同类标记。当这些具有不同标记的样本数相当时，kNN的分类错误率将会变大。本文从上述两点不足出发，研究改善kNN算法性能的方法。为了简单起见，称落入贝叶斯决策边界错误区内的样本为噪声样本，这种噪声样本的存在会导致分类误差率增大。显然，如果训练样本中不存在噪声样本，这就意味着分类中具有不同标记的样本重叠问题就不存在，就不会出现错判。目前有很多针对kNN算法的研究：1）有一些研究样本距离的选择问题，如选用加权距离[3]、语义距离[4]、Mahalanobis距离[5]、Chi-squared距离[6]、最大最近距离[7]等来构造k