论文摘要
在模式识别、机器学习、数据挖掘等领域中，K-近邻准则有着广泛的研究和应用背景。在实际的应用中，K-近邻分类由于其直观、简单、有效、易实现等特点，是一种常用的分类方法，被认为是数据挖掘领域的十大算法之一。近些年来，在基于图嵌入的降维中，很多图嵌入算法都采用K-近邻准则来构建数据的局部邻接关系图，如保局部投影（Locality Preserving Projections, LPP）及其变体，这种K-近邻构图方式在高维的数据模式分类中取得了良好的性能。本文围绕模式分类的K-近邻方法进行研究和探讨，其研究的内容主要包括基于K-近邻准则的分类问题，K-近邻准则在基于图嵌入的降维技术中的应用。本文的主要创新点如下：1．针对基于K-近邻准则的非参数分类算法的分类性能受训练样本局外点的严重影响，尤其是在小样本的情况下，设计了基于局部均值的K-近质心近邻（LocalMean-Based K-Nearest Centroid Neighbor, LMKNCN）分类算法。LMKNCN考虑了待测样本点在每类训练集中的k个近邻点与其自身所具有的相似性和空间几何分布性，同时利用从每类训练样本中所选取的k个近邻点的局部均值大小，来判断未知样本所属类别。所提算法不仅具有基于局部均值的K-近邻（Local Mean-BasedK-Nearest Neighbor, LMKNN）分类在局外点存在的情况下所表现出的稳健性，而且具有K-近质心近邻（K-Nearest Centroid Neighbor, KNCN）分类在小样本情况下所表现的有效性。大量的真实和人工数据集上的实验表明了LMKNCN算法在训练集样本个数、近邻选择个数和特征维度变化的情况下，都取得了良好的分类效果。2．针对基于图嵌入的降维方法中存在的小样本问题、外样本问题、局部过学习问题，提出了一种新的有监督的图嵌入学习算法，即保局判别近邻嵌入（Locality-Preserved Discriminant Neighborhood Embedding, LDNE）。LDNE将保局部投影和判别近邻嵌入（Discriminant Neighborhood Embedding, DNE）整合在统一的学习模型中，使其获得的图嵌入，较好的反映了高维数据所隐含的本质流形结构，不仅具有LPP的保局部特点和DNE的判别能力，还进一步增强了模式之间的判别信息。高维数据集上的一系列实验充分验证了LDNE是一种有效的降维算法，增强了高维数据在低维嵌入子空间的模式识别能力。3．在保局部投影的降维算法中，近邻图的构造与权重的配置起着至关重要的作用。鉴于此，根据LPP的保局部思想，提出了最大近邻间隔判别投影（MaximumNeighborhood Margin Discriminant Projection, MNMDP）算法。在MNMDP方法中，近邻边权重的定义，充分考虑了样本的类别信息，进而定义类内近邻散度和类间近邻散度，同时在目标函数优化时，利用最大间隔准则（Maximum Margin Criterion,MMC），最大化同类近邻和异类近邻之间的间隔，从而找到高维数据在低维空间的图嵌入。MNMDP不仅能解决图嵌入降维中存在的相关问题，而且提高了模式之间的判别能力。在基于手的生物鉴定数据集上的实验，验证了MNMDP算法的有效性。4．将稀疏构图和近邻构图有机结合起来，在稀疏保持投影（Sparsity PreservingProjections, SPP）和LPP的基础上，提出了稀疏保局投影（Sparsity Locality PreservingProjections, SLPP）算法。SLPP首先通过稀疏学习进行稀疏构图，然后在稀疏表示的基础上，结合K-近邻构图，建立稀疏保局的图嵌入模型。在SLPP投影的低维子空间中，不仅保持了高维数据内在几何属性和稀疏表示的自然判别能力，还保持了数据的局部几何信息，进一步增强了模式之间的判别能力。在人脸数据集上的实验表明了SLPP的有效性。