【作者】 黄启宏；

【导师】 刘钊；

【作者基本信息】 电子科技大学 ， 信号与信息处理， 2007， 博士

【摘要】 科学的进步，尤其是信息产业的发展，把我们带入了一个崭新的信息时代。在信息时代的科学研究中，不可避免地会遇到大量的高维数据，特别是图像数据。在实际应用中，用图像数据来表示的观测点可以模拟成可能带有噪声的低维非线性流形上的样本点或近似这些样本点。因此，流形学习已成为数据挖掘的一个重要手段，目的是找出图像高维空间中隐藏的低维结构或一些有益的性质。有一些因素影响着流形学习方法的效率。本征维数估计方法研究是高维图像数据处理领域的重要研究方向，如何准确地寻求本征维数可以帮助人们认识图像数据的本征结构，对于高维图像数据的维数约简以及其它的后续处理都具有重要的指导意义。虽然先前的研究指出了不同流形学习之间的联系，但是在核框架下来看不同流形学习之间的联系却是一个新的研究方向。黎曼正则坐标包含了流形中指定点到邻近点的方向和距离信息，如何将这种源于微分几何的技术应用到流形学习中也是值得研究的课题之一。对于这些问题，本文给出了比较完善的解答。本文的主要贡献如下：1．探讨了一种新的图像数据的本征维数估计算法。在没有流形几何或拓扑的先验知识的条件下，算法的关键在于如何构建一个基于流形切丛的近似单纯复形。这种算法的一个重要性质就是其计算复杂度只跟流形维数相关，而不是嵌入空间的维数相关。实验结果说明了本文算法在平面、空间上重建曲线、表面以及人脸图像本征维数估计中都取得了较好的效果，也分析了一个失败的情况。2．探讨了一种新的鲁棒流形学习方法。近年来提出的概率子空间混合模型对于图像流形学习是一种非常有用的方法，其对全局映射的缺乏可以由最近发展起来的基于局部线性嵌入，也称为局部线性坐标的方法来改善。然而，在很多存在野值点的实际应用中，这种方法缺乏必要的鲁棒性。这里给出了一种结合概率子空间混合模型的t分布的鲁棒混合模型。实验结果表明这种鲁棒子空间混合模型在图像数据集的密度估计和分类中具有非常好的优势。通过在嵌入步骤中引入重新定义的加权，很好的解决了局部嵌入坐标中的鲁棒性问题。3．首先，我们从核技术观点出发，对几种众所周知的流形维数约简算法进行了说明。Isomap，图Laplacian特征映射和局部线性嵌入(LLE)都利用一个局部邻域信息来构建流形的全局嵌入，可以看作基于特别构造的格莱姆矩阵的KPCA，揭示了三种算法之间的相似之处和不同之处。最后，Isomap是一个广泛使用的低维嵌入方法，是加权图的几何距离跟经典尺度分析(测度多尺度分析)相结合。我们将注意力集中在Isomap中没有考虑到的两个关键问题：(1)泛化能力；(2)拓扑稳定性。我们探讨了一种具备以上两种性质的鲁棒核Isomap方法，将Isomap和Mercer核机器联系起起来。通过KPCA，泛化能力也就自然呈现出来。对于拓扑稳定性，观察图中的网络流，我们探讨了一种消除临界野值点的方法。本文方法的泛化能力和稳定性在(图像)数据集的实验结果中也得到了证实。4．探讨了一种基于黎曼正则坐标的快速流形学习方法。这种坐标系统可以看成Euclidean空间的笛卡尔坐标的一种泛化。借助一些来自微分几何的基本概念以及使用Diikstra算法用于计算图最短路径，可以实现高维数据的维数约简。我们希望本文方法开启一种新的图像处理的分析方法，其中，坐标系统是从高维实验数据学习获得，而不是事先采用定义好的模型。更多还原

【Abstract】 With the progress of science, especially the development of information industry, we enter a brand-new information age. When doing research in information age, one is inevitably confronted with large volumes of high-dimensional data, especially image data. In real-world applications, observations represented as image data or vectors can be modeled as samples lying on or close to a low-dimensional nonlinear manifold possibly with noise. Hence, data reduction especially nonlinear dimensionality reduction is an important tool of data mining, and the goal of dimension reduction is to find out the low dimensional structure of the nonlinear manifold from the high dimensional data. So, manifold learning is an important tool of data mining, and the goal of it is to find out the hidden dimensional structure of the high dimensional image data.There are some common issues that determine the effectiveness of the manifold learning. The researching on intrinsic dimension estimating techniques has become an important research direction in the realm of high dimensional image data. How to exactly estimate the intrinsic dimension is helpful for people to discover the intrinsic configuration of the image data, and play a guiding role in dimension reduction and other subsequent processes. All manifold learning share a common characteristic in that they use a local structure on the data to globally map the manifold to a lower dimensional space. Although previous studies have pointed out relationships among various manifold learning, it is a novel direction to relate them within a kernel framework. Riemannian normal coordinates contain information about the direction and distance from a specific point on a manifold to other points nearby. It is worth to translate this technique from its original setting in differential geometry, to the task of manifold learning. To confront these proposed problems, we give relatively consummate answers.The contributions of this paper are as follows:1. A new algorithm for intrinsic dimension of image data is presented. Without a priori knowledge of the manifold’s geometry or topology except for its dimension, the key goal is to construct a simplicial complex based on approximations to the tangent bundle of the manifold. An important property of the algorithm is that its complexity depends on the dimension of the manifold, rather than that of the embedding space. Successful examples are presented in the cases of reconstructing curves in the plane and space, surfaces in space, and intrinsic estimating of human face image; in addition, a case when the algorithm fails is analyzed.2. A new method for robust manifold learning is presented. Probabilistic subspace mixture models, as proposed over the last few years, are interesting methods for learning image manifolds. Their lack of a global mapping can be remedied by a recently developed method based on locally linear embedding, called locally linear coordination. However, for many practical applications, where outliers are common, this method lacks the necessary robustness. Here, the idea of robust mixture modeling by t-distributions is combined with probabilistic subspace mixture models. The resulting robust subspace mixture model is shown experimentally to give advantages in density estimation and classification of image data sets. It also solves the robustness problems of locally linear coordination, by introducing a weighted re-definition of the embedding step.3. First, We interpret several well-known algorithms for dimensionality reduction of manifolds as kernel methods. Isomap, graph Laplacian eigenmap, and locally linear embedding(LLE) all utilize local neighborhood information to construct a global embedding of the manifold, are described as kernel PCA on specially constructed Gram matrices, and illustrate the similarities and differences between the algorithms. Last, Isomap is one of widely-used low-dimensional embedding methods, where geodesic distances on a weighted graph are incorporated with the classical scaling (metric multidimensional scaling). In this paper we pay our attention to two critical issues that were not considered in Isomap, such as: (1) generalization property,(2) topological stability. Then a robust kernel Isomap method, armed with such two properties, is presented. The proposed method which relates Isomap to Mercer kernel machines, so that the generalization property naturally emerges, through kernel principal component analysis. For topological stability, we investigate the network flow in a graph, providing a method for eliminating critical outliers. The generalization property and topological stability of the robust kernel Isomap is confirmed through experiments with several (image) data sets.4. A fast manifold learning based on Riemannian normal coordinates is presented. This coordinate system is in a way a generalization of Cartesian coordinates in Euclidean space. In order to reduce the dimension of high dimensional data, our implementation currently uses Dijkstra’s algorithm for shortest paths in graphs and some basic concepts from differential geometry. We expect this approach to open up new possibilities for analysis of image data, where the coordinate system is learned from experimental high-dimensional data rather than defined models.更多还原