基于随机游走的流形学习与可视化

基于随机游走的流形学习与可视化邵超万春红张啸剑

计算机与信息工程学院河南财经政法大学河南郑州2021/6/8

提纲引言动机随机游走模型和通勤时间距离RW-ISOMAP算法实验结果结束语

引言数据降维及其可视化的重要性提高人们对高维海量数据的洞察力提高后续数据分析算法的有效性和执行效率流形学习——一类非常有效的非线性降维算法等距映射

(isometricmapping,ISOMAP)局部线性嵌入

(locallylinearembedding,LLE)拉普拉斯特征映射(Laplacianeigenmap,LE)海森特征映射(Hessianeigenmap,HE)局部切空间排列(localtangentspacealignment,

LTSA)……

引言现有这些流形学习算法能否成功应用严重依赖于其邻域图能否正确表达数据的内在几何结构，这取决于所采用的邻域大小参数是否合适。然而，目前该参数在实际中还难以高效选取，另外，数据中的噪音对邻域大小参数的合适性也会产生一定的影响。究其原因，主要是基于欧氏距离的邻域图创建方法。作为一种线性度量，欧氏距离并没有考虑到数据可能存在的非线性几何结构，容易在邻域图中引入“短路”边，从而使这些流形学习算法对邻域大小参数和噪音都比较敏感，鲁棒性较低。

引言为使邻域图能正确反映数据的内在几何结构，多数算法基于残差(residualvariance)来选取合适的邻域大小参数，但这需要多次运行整个流形学习算法以计算相应的残差，时间复杂度过大，这也使该参数在实际中难以高效选取。针对现有这些流形学习算法对难以高效选取的邻域大小参数依然比较敏感的问题通过减轻流形学习算法对邻域大小参数的敏感程度集成不同邻域大小参数得到的多个运行结果识别并删除邻域图中可能存在的“短路”边通过组合最小生成树来创建邻域图为每个数据点自适应地选取不同的邻域大小参数

提纲引言动机随机游走模型和通勤时间距离RW-ISOMAP算法实验结果结束语

动机通勤时间距离

(commutetimedistance)基于邻域图上的随机游走(randomwalk)理论以概率的形式综合考虑了邻域图上2点间的所有连接路径,不但比单一的最短路径距离更加鲁棒(对邻域图中可能存在的“短路”边不太敏感)，而且还能在一定程度上表达数据的非线性几何结构，这一特点使其比线性的欧氏距离更适合于创建邻域图。

因此,和传统的基于欧氏距离的邻域图创建方法相比,采用通勤时间距离来创建邻域图能更好地避免“短路”边,从而获得比传统流形学习算法更高的鲁棒性。

提纲引言动机随机游走模型和通勤时间距离RW-ISOMAP算法实验结果结束语

随机游走模型和通勤时间距离数据点之间的相似度——数据分析的基础由此得到描述该数据内在几何结构的邻域图

当且仅当或为该邻域图的邻接矩阵或相似矩阵

随机游走模型和通勤时间距离可视为邻域图G上的1个Markov转移概率矩阵

，其中，为数据点

的度(degree)。从数据点

出发,跳转到

的概率为由此便定义了邻域图G上的1个随机游走模型

随机游走模型和通勤时间距离平均首次命中时间(averagefirsthittingtime)

为从

出发，以概率

跳转到

，以此类推，最终首次到达

的期望步数：该度量以概率的形式综合考虑了从

到

的所有连接路径，在刻画

和

之间相异度方面比最短路径距离更加鲁棒，即受邻域图G中“短路”边的影响比较小，从而能在一定程度上表达数据的非线性几何结构，据此创建的邻域图不容易产生“短路”边。该度量并不对称，对称化之后即为通勤时间距离。

随机游走模型和通勤时间距离通勤时间距离(commutetimedistance)

经证明，通勤时间距离可通过Laplacian矩阵的广义逆(Moore-Penrosepseudoinverse)矩阵计算得到:

为该邻域图G的总度

为Laplacian矩阵

的广义逆矩阵

随机游走模型和通勤时间距离通勤时间距离(commutetimedistance)

随机游走模型和通勤时间距离通勤时间距离(commutetimedistance)随着2点间的连接路径增多,或其中某些连接路径的长度变短,其通勤时间距离就会相应减小。因此,单纯依靠通勤时间距离的低维嵌入(如CTE(CommuteTimeEmbedding)算法，亦称为图上的主成分分析算法)虽然有利于聚类,但在流形学习与可视化时会在一定程度上扭曲数据的内在几何结构。

提纲引言动机随机游走模型和通勤时间距离RW-ISOMAP算法实验结果结束语

RW-ISOMAP算法为了更好地保持数据的全局几何结构，提高数据可视化效果，应该像ISOMAP算法那样保持流形上有意义的全局度量——测地距离。然而，ISOMAP算法用来逼近测地距离所采用的单一的最短路径距离具有比较差的鲁棒性，邻域图中可能存在的“短路”边就会使之彻底失去逼近相应测地距离的能力。究其原因，主要是用来计算最短路径距离的邻域图是基于线性的欧氏距离来进行创建的。

RW-ISOMAP算法通勤时间距离会随着连接路径增多或某些连接路径变短而逐步减小，因此，单纯依靠通勤时间距离可能会漏掉其中的某些最近邻点，从而难以确保测地距离的良好逼近。图1由k-最近邻法(k=2)得到的数据集{A,B,C,D}的邻域图，如细实线表示，其中，数据点A的两个最近邻点为B和C。然而，如果单纯使用通勤时间距离来确定最近邻点，则数据点A的两个最近邻点为C和D，如粗虚线表示，这是因为D和A之间存在多条相对较短的连接路径，如(A,D)和(A,C,D)

RW-ISOMAP算法为了确保测地距离的良好逼近，从而更真实地展现数据的内在几何结构，本文首先采用能使邻域图连通的最小k值(记为km)来创建邻域图(称为最小连通邻域图，记为

，该邻域图能为每个数据点都保留若干个最近邻点，并能在最大程度上避免“短路”边)；然后，在此基础上使用通勤时间距离为每个数据点增加更多的最近邻点。由于通勤时间距离考虑了数据的内在几何结构，能在避免“短路”边的情况下使邻域图足够稠密，从而使测地距离得以更加精确的逼近。

RW-ISOMAP算法输入：数据

，用于计算通勤时间距离的邻域大小参数k1和参数t，用于创建邻域图的邻域大小参数k2输出：数据

的低维嵌入

RW-ISOMAP算法

RW-ISOMAP算法

RW-ISOMAP算法

RW-ISOMAP算法

RW-ISOMAP算法

CTD-ISOMAP算法

提纲引言动机随机游走模型和通勤时间距离RW-ISOMAP算法实验结果结束语

实验结果——完整流形的实验结果Swissroll和S-curve数据集

Swissroll数据集上的实验结果

实验结果——完整流形的实验结果Swissroll数据集上的实验结果

实验结果——完整流形的实验结果S-curve数据集上的实验结果

实验结果——完整流形的实验结果S-curve数据集上的实验结果

实验结果——完整流形的实验结果加入噪音的Swissroll数据集上的实验结果

实验结果——完整流形的实验结果加入噪音的Swissroll数据集上的实验结果

实验结果——完整流形的实验结果加入噪音的S-curve数据集上的实验结果

实验结果——完整流形的实验结果加入噪音的S-curve数据集上的实验结果

实验结果——完整流形的实验结果残差(residualvariance)对比

实验结果——完整流形的实验结果带有空洞的Swissroll数据集

实验结果——不完整流形的实验结果带有空洞的Swissroll数据集

实验结果——不完整流形的实验结果带有空洞的Swissroll数据集

实验结果——不完整流形的实验结果

实验结果——人脸数据集的实验结果

实验结果——人脸数据集的实验结果

提纲引言动机随机游走模型和通勤时间距离RW-ISOMAP算法实验结果结束语

结束语由随机游走模型得到的通勤时间距离具有良好的鲁棒性，且考虑了数据的非线性几何结构，因此，本文提出了基于随机游走的流形学习算法—