【作者】 潘锋；

【导师】 王建东；

【作者基本信息】 南京航空航天大学 ， 计算机应用技术， 2011， 博士

【摘要】 数据挖掘、机器学习领域普遍存在数据维度很高但同时样本数量偏少的情形，经典的分类、回归算法在对这种数据进行分析处理时往往计算代价过高甚至完全失效。一般的做法是在数据分析与处理之前对数据集进行特征提取或特征选择，抽取样本最相关特征，消除不相关特征与噪声特征，以利于后续工作。本文在深入分析与研究常用特征提取与特征选择方法基础上，提出了一些克服小样本与高计算复杂度问题的有效算法，主要内容如下：1、提出了一种基于K-近邻局部间隔的判别映射方法。首先，将假设间隔概念应用于样本数据的局部分析并加以扩展，在样本分布空间要求局部邻域内同类样本与非同类样本能够尽可能判别；其次，鉴于对未知样本特征提取的需要，将局部邻域结构投影于一个较低维度的子空间内，要求在子空间内局部邻域仍然保持与同类样本距离和与非同类样本距离差异极大，即局部间隔极大化。考虑到求解局部最近邻步骤包含了矩阵求逆运算，基于投影定理使用Gram-Schmidt正交化降低时间复杂度。最后，探讨了基于局部间隔的判别映射方法与局部线性嵌入算法（Local Linear Embedding，LLE）之间的关系，发现基于局部间隔的判别映射方法可以视为LLE算法在有指导学习情形下的线性扩展。2、为进一步提高基于局部间隔的特征提取能力，引入无标记样本，由非同类样本估计局部样本的判别性质，由较多的未标记近邻样本估计局部几何结构。将样本局部分布投影于较低维度的子空间，则算法具有了判别不同子流形的能力。在可视化实验中发现，这种基于局部间隔的半监督判别嵌入算法能够发现不同子流形，同时能够得到较高的分类精度。3、谱聚类是被证明效果较好的无指导学习方法。研究发现，Laplacian矩阵的特征向量指示了样本的类别信息，本文证明了Laplacian矩阵的若干小特征值表现了簇结构的显著性，即特征值趋于零说明聚类效果会比较好。将这一定理作为衡量原始特征重要度的准则，提出了基于无监督技术的特征选择算法，即重要特征能够保证簇结构的显著性，而不相关特征不能保证簇结构的显著性甚至破坏簇结构。由于每选择一个特征都需要对Laplacian矩阵的特征分解步骤，为此使用Nystr m方法逼近半正定矩阵特征值以降低计算复杂度。4、将流形学习的思想应用到特征排序，通过对特征赋予权重的方法计算特征的相关度。主要思想是相关特征在加权特征空间邻域保持同类样本仍然为近邻，而对于非同类近邻则应尽量远离。提出了两种评价特征相关度的标准：商准则与差准则，由于避免了特征分解步骤，计算表明两种准则下算法的时间复杂度为样本维度的线性函数，或样本数量的二次函数，与RELIEF-F算法相当。另外，通过对商准则的进一步研究，提出了基于局部学习的半监督特征加权与排序框架，将无标记样本引入，要求在加权空间相关特征不仅能够更好的判别样本，还能够保持样本的局部光滑性质。半监督特征排序框架同样不需要特征分解步骤，因此具有较低的计算复杂度。从此框架导出两种半监督特征排序算法：基于线性判别分析的特征排序与基于局部判别嵌入分析的特征排序，前者适于线性可分问题的特征排序，后者适于非线性可分问题的特征排序。更多还原

【Abstract】 In data mining and machine learning the prepared data usually contain multitudes of features withsmall sample size, which presents a big challenge for the orthodox approaches to retrieve usefulinformation. Feature extraction and feature selection are usually exploited to circumvent this poblem.Both methods aim to extract the most relevant features, eliminate the irrelevant and noisy features,and make the data analysis feasible. In this paper we will investigate these methods thoroughly topropose some improved algorithms, alleviating the small sample size and computational inefficiencydifficulties. The main contributions are listed as follows:1. A discriminant projection algorithm based on the k-nearest neighbor local margin is proposed.The hypothesis margin is introduced to measure the local discriminative power, i.e. the data points ofthe same class should be close to each other while the data points of different classes should be farfrom each other in the neighborhood. The local margin is projected into a linear low-dimensionalsubspace within which the neighborhood relationship is preserved. Maximizing the sum of theprojected local margins we obtain the global transforming matrix. To reduce the computation forfinding the inverse of the square matrix, the Gram-Schmidt orthogonalization is applied. Finally, theconnection between the algorithm and Local Linear Embedding (LLE) is explored and we note thatthe proposed algorithm can be considered as the variant of the LLE for discriminant analysis.2. The aforementioned feature extraction algorithm is extended to the semi-supervised case usingthe abundant unlabeled data points. The labeled data points are employed to separate the classes,while the unlabeled data points contribute to maintain the local structure. Similar to the supervisedcase the local margin including both the labeled and unlabeled data is projected into alow-dimensional subspace, from which a linear operator can be derived. The experimental resultsdemonstrate that the semi-supervised feature extraction algorithm can not only present superiorclassification accuracy, but also find different sub-manifold in the low-dimensional space.3. Spectral clustering algorithm has been demonstrated to be an effective unsupervised learningmethod. The spectral graph theory indicates that the eigenvalues and eigenvectors of the graphLaplacian are closely related with the clustering results. We prove that the distribution of theeigenvalues describes the distinctness of clusters and the eigenvectors implicitly present the targetvalues of the samples when normalized graph Laplacian is adopted. Based on this finding we proposea feature significance weighting algorithm. The feature weighting algorithm might be computationallyexpensive due to the involved eigen-decomposition of the Laplacian matrix, hence the Nystr m method is applied to reduce the computational cost.4. Motivated by the manifold learning, we rank the feature relevance according to thediscriminative capability of each feature in the local space of the data. Specifically, assuming that theimportant features will force the data points of the same class to maintain their intrinsic neighborrelations, whereas neighboring points of different classes no longer to stick to one another, we derivean optimization problem weighting each feature. Two ranking criteria, i.e. the difference criterion andquotient criterion, produce two feature selection algorithms. The algorithms do not contain the densematrix eigen-decomposition which might be time-consuming.We further measure the local structure of the data set in the feature weighted space using the mixedlabeled and unlabeled data points and incorporate it into the supervised formulation. From the featureweighting framework we derive two feature ranking algorithms, i.e. Semi-supervised Feature Rankingby Linear Discriminant Analysis (SFRLDA) and Semi-supervised Feature Ranking by DiscriminantNeighborhood Analysis (SFRDNE). The former is suitable for linearly separable problems, while thelatter is suitable for nonlinear separable problems.更多还原