对大规模高维数据结构的分析和研究一直是数据挖掘、机器学习和模式识别等领域中十分重要的研究课题之一,同时也是现代科学技术所必须面对的困难之一。高维数据的结构特征主要包括聚类结构和流形结构,所用到的研究方法涉及到了多个数学分支,如多元分析、非线性泛函分析及统计等,寻找简单而有效的方法是人们一直追求的目标。因此对高维数据结构的学习具有十分重要的价值。本文提出了一种新的最近邻居概念,自然最近邻居(Natural Nearest Neighbor : 3N),它是一种无尺度(scale-free)的最近邻居,其核心的思想是最离群的数据对象只有一个最近邻居或者说具有最低的能量,而稠密的对象有较多的邻居或较高的能量,而且,自然最近邻居的计算过程可以自动地实现,这是本文的主要贡献和创新。由自然最近邻居可以自动地形成一种自适应的数据最近邻域图或数据网络,借助复杂网络的概念,这也是一种无标度(scale-free)的网络,这种邻域图或网络可以很好地表示数据对象之间的关联关系,能够明显地给出各个数据对象的密度信息。自然最近邻居的形成机制,能够有效地降低跨边界寻找最近邻居的风险,因而可保持具有聚类结构的数据的凝聚状态,自然地展示出聚类数据的基础结构(infrastructure),为后续的聚类和流形结构分析提供一个稀疏和无参数的基础图模型。将这种自适应邻域图用于流形学习算法,如Isomap、LLE、HLLE、LTSA等,可得到相应的无自由参数的自适应流形学习算法,避免了传统流形学习算法中关于邻域参数的选择问题,原因在于由自然最近邻居所形成的邻域图能很好地逼近低维嵌入的数据流形。这为机器学习领域中的两大热点问题之一的维数约简(Dimensionality Reduction)方法提供了一个新的视角。本文还研究了离群数据对象的特征子空间结构与聚类特征子空间结构之间的关系,还提供了一种从邻居的角度来观察离群对象的行为。本文的主要创新和贡献包括如下几个方面。(1)提出了自然最近邻居(3N)的概念,并提供了一个十分简单的计算方法。在标准分布(均匀分布、正态分布)及规则数据集上验证了这种邻居概念的合理性。与k-最近邻居和ε-最近邻居相比含有更丰富的信息:如密度、离群信息以及结构逼近等。从自然最近邻居数目的分布(直方图)可以观察数据集的分布状态,这种分布与数据集的高维特性无关。(2)将自适应邻域图用于代表性的流形学习算法:如全局结构流形学习算法Isomap和局部结构流形学习算法LLE、HLLE及LTSA等算法,提出了无自由参数的自适应流形学习算法3N-Isomap、3N-LLE及3N-LTSA等,同时解决了近十年来流形学习算法中关于如何选择自由参数的问题。使任何人都可使用这批算法来观察自已领域范围内的数据,而不受困扰。在三个实际问题中应用了3N-Isomap算法,并提出了自动多流形学习算法、大规模流形学习算法(由一个通用的简单随机采样算法实现)及同质数据复杂性分析方法。(3)将自适应邻域图用于谱图聚类算法,如MNcut算法,提出了一个改进的算法3N-MNcut,其性能优于原聚类算法。(4)提出了离群点的特征子空间结构与聚类的特征子空间结构具有相同的特征依赖,即都依赖于最大特征值及相应的特征子空间。提出了一个新的离群指数,可以观察离群点的动态行为。