【作者】 王庆刚；

【导师】 李见为；

【作者基本信息】 重庆大学 ， 仪器科学与技术， 2009， 博士

【摘要】 信息化技术的快速发展及其广泛应用,使具有高维数的非结构化数据信息大量出现。高维使得这些数据的内在规律不仅超出人们的直接感知能力,而且很难被现有机器学习和数据挖掘算法有效地处理。如何对高维数据进行有效维数约简,并由此发现其内在结构和规律已成为高维信息处理研究的关键问题之一。流形学习的主要目标是发现蕴含在高维数据集中的内在几何结构与规律性,是近年来机器学习和模式识别等领域一个新的研究热点。本文对流形学习算法及其应用问题进行了研究,主要工作及研究成果总结如下:①在对PCA和MVU算法分析的基础上,提出了有区别方差嵌入(DVE)算法。通过构造数据集的近邻图和非近邻图,DVE算法对样本方差采取了不同的处理方式,使低维表示全局方差最大的同时保持局部方差不变。DVE可以看作是PCA算法的非线性扩展,同时也可以看作是对MVU算法严格局部等距约束的松弛改进。DVE是一种全局维数约简算法,可以有效揭示蕴含在高维数据集中的全局几何结构和内在规律。与MVU和ISOMAP相比,DVE算法具有小的运算强度和存储需求。另外,DVE算法对具有等角映射特性的数据集有很好的降维效果,而ISOMAP和MVU的距离保持特性使得它们无法处理此类数据集。②DVE算法需要对稠密矩阵进行特征分解,尽管与ISOMAP和MVU相比,算法的计算复杂度有了很大的降低,但仍无法满足对现实世界中海量高维数据的实时处理要求。针对这一问题,提出了基于基准点的DVE快速算法(LDVE)。在保持近邻点间距离和不变的条件下,LDVE算法通过使随机选取的基准点间的距离和最大在低维空间中展开高维数据流形,算法的求解也同时转化为稀疏矩阵的特征分解问题,从而有效降低了计算强度和存储需求。③DVE算法得不到一个显式映射函数,无法对新增数据点进行有效处理,针对这一问题,通过对DVE算法进行线性逼近,提出了有区别方差投影(DVP)算法。和DVE算法一样,DVP算法在揭示数据集全局结构的同时有效保存它的局部结构,可以作为经典PCA和LPP的有效补充。④DVP是一种非监督维数约简算法,它并不能保证不同类别的数据点在低维投影空间中可以被有效分开。针对这一问题,提出了监督有区别方差投影(SDVP)算法。通过构造数据集的类内近邻图和类间图,SDVP算法使得高维数据集在低维空间中投影的类内局部散度最小,同时类间全局散度最大。SDVP可以看作是线性判别分析(LDA)的局部化形式,而边际Fisher分析(MFA)又可以看作是SDVP的局部化形式。SDVP算法对具有多模态或嵌入流形结构的数据集有好的分类效果。在UCI机器学习数据库和一些标准人脸数据库上的分类实验证明了算法的优越性。更多还原

【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. How to reduce the high dimensional data into the low dimensional space and discover the intrinsic structure have become the pivotal problem in high dimensional information processing. The main purpose of manifold learning algorithms is to detect the intrinsic structure embedded in the high dimensional data space, which have been a focused research field in machine learning and pattern recognition.In this dissertation, some key issues on manifold learning have been studied, the main contributions are summarized as follows:Baed on the analysis of PCA and MVU, we propose a new nonlinear dimensionality reduction method called distinguishing variance embedding (DVE). By constructing the neighborhood graph and non-neighborhood graph, DVE deals with the sample variance distinguishingly, that maximizes the global variance and simultaneously preserves the local variance. DVE can be viewed as the nonlinear counterpart of PCA, and also be viewed as a variant of MVU that relaxes the strict distance-preserving constraints. As a global algorithm for nonlinear dimensionality reduction, DVE can detect the global geometric structure of data set in the high demensional space. Compared with MVU and ISOMAP, the computation intensity and storage demands of DVE are drastically reduced. DVE can also effectively deal with the conformal data set while ISOMAP and MVU fail for their isometric property.Despite the computational complexity of DVE greatly reduced when compared with ISOMAP and MVU, the eigen-decompose of dense matrix in DVE makes it can’t meet the real-time data processing requirements in the real world. In order to solve this problem, the landmark version of DVE is proposed. Subject to the constraint that the total sum of distances between neighboring points remain unchanged, landmark DVE unfolds the data manifold in the low dimensional space by pull the randomly selected landmark points as far apart as possible. The main optimization of landmark DVE involves an eigen-decompose of spare matrix. Compared with DVE, the computation intensity and storage demands of landmark DVE are effectively reduced. Like other manifold learning algorithms, DVE has no straightforward extension for out-of-sample examples as it can’t get a mapping function. In order to solve this problem, the linear approximation of DVE is introduced, which is called distinguishing variance projection (DVP). Similar to DVE, DVP can detect the global structure of high dimensional data set and simultaneously preserve its local neighborhood information in a certain sense. DVP can be viewed as an effective complement of classical PCA and LPP.As an unsupervised dimensionality reduction algorithm, DVP can’t ensure that the data in different category be separated well in low dimensional subspace. As DVP deals with the data points in pairwise manner, the algorithm can be performed in supervised manner by taking the label information into account, called supervised distinguishing variance projection (SDVP). By constructing the intra-class neighborhood graph and inter-class graph, SDVP seeks the low dimensional subspace in which the intra-class local scatter of data is minimized and at the same time the inter-class scatter is maximized. SDVP can be viewed as a local variant of LDA, and MFA can be viewed as a local variant of SDVP. SDVP is suitable for the classification tasks of multi-modal and manifold data set. The experiments on the UCI machine learning databases and standard face databases prove the effectiveness of the algorithm.更多还原