【作者】 刘小明；

【导师】 董金祥； 尹建伟；

【作者基本信息】 浙江大学 ， 计算机科学与技术， 2007， 博士

【摘要】 信息化技术的快速发展及其广泛应用，使具有高维数的非结构化数据信息大量出现。高维不仅使数据难以被人们直观理解，而且难以被现有机器学习和数据挖掘算法有效地处理。降维方法是处理这些数据的一个重要手段，虽然在数据的降维处理方面已经有了大量的研究工作，但是在线性与非线性流形降维领域仍然存在许多具有挑战性的问题。2000年在Science上三篇文章分别从神经科学与计算机科学的角度对降维问题进行了研究，进一步促进了降维问题的研究，并推动流形学习成为当前机器学习研究中的一个热点问题。论文围绕线性流形与非线性流形学习算法及其应用展开，从监督式的全局线性流形降维、非监督式非线性降维、监督式非线性降维与分类、线性逼近降维及分类、和基于矩阵表示的线性降维方面对流形学习算法进行了一些研究，主要工作包括以下几个方面：在监督式的全局线性流形降维方面，提出了一种同时利用不同类数据的均值与协方差分布信息的新降维方法，在最大化成对类别均值距离的同时保持成对类间的协方差距离。分析了算法与线性辨别分析，切片平均方差估计方法，异方差辨别分析方法和协方差保持投影算法间的关系。同时基于算法的成对模式，融入与Bayes分类错误率相关的权重信息，提出了加权PCPM方法WPCPM。在非监督式的非线性降维方面，针对局部切空间排列算法LTSA算法不能有效处理新数据的问题，提出来一种增量式的LTSA算法-ILTSA，对于新数据点，ILTSA首先更新受新样本影响的数据点的局部仿射空间，得到新的局部几何信息。通过最小化数据点的局部重构误差，得到已有数据点局部排列，然后在最小均方差意义下得到新样本的全局坐标。最后，用Rayleigh-Ritz加速方法更新所有数据点的全局坐标。此外，提出了基于LASSO回归选择标志点的标志点LTSA算法(LLTSA)，最后，提出了LLTSA的增量式算法(ILLTSA)。在监督式非线性降维方面，针对非监督式局部切空间排列LTSA算法没有利用样本的类别信息，不能直接用于分类的问题，提出了一种基于LTSA和直推式k近邻分类器上的直推式分类算法。使用改进的两阶段的LDA／QR算法构造局部低维坐标系，使用LDA／QR不仅可以利用样本数据的类别信息，而且可以解决传统LDA方法的奇异性问题。为了更好地利用无类别标签的数据分布信息，采用TCM-KNN算法对低维数据完成分类。在非线性流形降维的线性逼近方面，针对近邻关系保持嵌入NPE算法易于受到降低后的维数影响，性能依赖于正确的维数估计的问题，提出来一种正交化的近邻关系保持嵌入降维算法。算法假设每个数据点都能由其近邻点的线性组合表示，在降维过程中保持数据点的局部几何信息，通过迭代地计算正交基函数得到数据的低维嵌入坐标。通过使变换矩阵正交化，降低算法对维数的依赖性。同时，提出了在降维后的低维空间中使用标签传递(LNP)的分类算法，能更好地利用在降维中保留的局部几何信息。在基于矩阵表示的监督式线性降维方面，针对局部敏感辨别分析算法LTSA只能处理向量型的数据，当处理图像等矩阵数据时，需要首先将矩阵展开为向量，易导致与传统LDA相同的奇异性的问题，提出了一种称为二维局部敏感辨别分析方法(2DLSDA)方法，其直接处理2维的图像矩阵而不需要将矩阵转化为向量，能克服奇异性问题。同时，依据图像的两种展开方式，提出了两个单边2DLSDA算法。算法基于Schur分解来求得正交变换矩阵，比传统基于特征值分解的算法高效并稳定。更多还原

【Abstract】 With the quick advancement and extensive application of information technology, more data with high dimension and complex structure occurs very quickly. High dimension not only makes the data hard to understand, and makes traditional machine learning and data mining techniques less effective. Dimension reduction is one of the important techniques to deal with high-dimensional data; while there have been many research work done in this field, there are still challenging problems to uncover the linear and nonlinear structure information in data. In 2000, three articles published on Science magazine studied the dimension reduction issue from the perspectives of neuroscience and computer science respectively, which further accelerate the research of this field, and promote the manifold learning methods for dimension reduction become one of the hot problems in machine learning.This dissertation deals with manifold learning for dimension reduction and its application, studies the problem from the both the linear and nonlinear, unsupervised and supervised perspectives. The main contributions of this dissertation can be summarized as follows:In the perspective of supervised global linear dimension reduction, a Pairwise Covariance-preserving Projection Method (PCPM) is proposed, which maximizes the class mean distance and also preserves approximately the distance of pairwise class covariances. The optimization involved in PCPM can be solved directly by eigenvalues decomposition. Theoretical analysis reveals the relationship between PCPM and Linear Discriminant Analysis (LDA), Sliced Average Variance Estimator (SAVE), Heteroscedastic Discriminant Analysis (HDA) and Covariance-preserving Projection Method (CPM). Furthermore, pairwise weights related to Bayes classification accuracy are incorporated naturally with the pairwise summarization form, and a weighted PCPM is also proposed.In the perspective of unsupervised nonlinear dimension reduction, an incremental version ILTSA of LTSA (Local Tangent Space Alignment) is proposed, which can greatly reduce the computation time demand of LTSA algorithm to deal with new data. For a new sample data, the low-dimensional affine subspaces of affected points are updated firstly. Through minimizing the reconstruction errors of data point as respect to existing points, the global coordinates and local alignment matrix of existing points are obtained and the global coordinate of new data point is obtained in the least square sense. Finally, the global coordinates of all data points are updated with Rayleigh-Ritzacceleration. Besides, a landmark version of LTSA (LLTSA) is proposed, where landmarks are selected based on LASSO regression, which can reduce the memory demand of the algorithm. Furthermore, an incremental version (ILLTSA) of LLTSA is also proposed.In the perspective of supervised nonlinear dimension reduction, a new transductive classification method based on local tangent space alignment (LTSA) and transductive k-nearest neighbors is proposed. In the method, an improved 2-stage LDA/QR method is used to construct local low-dimensional coordinates, which can not only utilize the label information of sample data, but can also conquer the singularity problem of traditional LDA. Then the global low-dimensional embedding coordinates are obtained with LTSA, and TCM-KNN method is used for classification on the low-dimensional manifold finally.In the perspective of linear approximation of nonlinear dimension reduction, an Orthogonal Neighborhood Preserving Embedding method is proposed to overcome the sensitivity of dimension estimation problem of Neighborhood Preserving Embedding method. The method obtains the low dimensional coordinates by iteratively computes the mutually orthogonal basis functions, can assure the orthogonality of the projection matrix. Moreover, utilizing the local geometry during ONPE dimension reduction, a new classification method based on label propagation method (LNP) is proposed.In the perspective of supervised linear dimension reduction with matrix representation, a method called two-dimensional locality sensitive discriminant analysis (2DLSDA) for image recognition is proposed, which is based directly on 2D image matrices, can overcome the singularity problem and can utilize the spatial information among pixels more effectively. Two orthogonal transform matrixes are computed based on Schur decomposition. Based on Schur decomposition, the projection matrixes are orthogonal and can be obtained more efficient and numerical stable. Meanwhile, based on the unfolding way of image matrices, two unilateral 2DLSDA methods are proposed.更多还原