论文部分内容阅读
【摘 要】 流形学习的主要目标是发现高维观测数据空间中的低维光滑流形。论文考虑噪声点会导致数据集拓扑结构不稳定,不能得到较优的低维嵌入结果,给出一种基于共享近邻(Sharing Nearest Neighbors,SNN)的鲁棒性ISOMAP算法,并对提取到的噪声点低维映射给出了一种线性泛化公式。最后将算法应用于含噪声的Swiss-Roll数据集中,通过计算数据集量化标准——残差,验证了算法的可行性和有效性。
【关键词】 流形学习 共享近邻 鲁棒性ISOMAP 残差
论文结合共享近邻(Sharing Nearest Neighbors,SNN)算法思想,提出一种ISOMAP的鲁棒性改进算法,可以有效检测出数据集中的噪声点。首先完成除噪后数据集的低维映射,然后针对噪声点提出泛化公式完成噪声点的低维映射。最后通过对含噪声的Swiss-Roll数据集进行实验,并对映射数据集的残差进行量化,验证了算法的可行性和有效性。
1ISOMAP算法
ISOMAP是由Tenenbaum和Silva于2000年提出的,算法建立在经典的MDS(多维尺度变换)算法基础上,其目标是使降维后的数据尽量保持在降维前的数据间的邻接关系。传统MDS采用欧式距离来度量两点之间的距离关系,但在很多情况下欧式距离度量不能真正体现数据点集之间的真正距离关系。如图1(A)所示,直线为两点之间的欧式距离,曲线为两点沿曲面的距离(测地线距离),可以看出两点间测地线距离更符合数据点的距离关系度量。ISOMAP算法通过计算两点间的最短路经(图1(B)折线)来逼近两点间测地线距离(图1(B)直线),用两点间最短路经距离代替MDS中的欧式距离,完成高维空间到低维空间的映射。
具体的ISOMAP算法步骤可描述为:
Step1:建立加权邻接图G。主要有两种方法确定邻接图的边,ε邻域和k近邻,并以数据点间的欧氏距离作为边上的权重。
Step2:利用图论中的Dijkstra算法或Floyd算法计算图G中每两点间的最短路径,记得到的距离矩阵为DG={dG(i,j)}。
Step3:用MDS求低维嵌入坐标,记H=(Hij)=(δij-),S=(Sij)=(Dij2),则所求的d维嵌入坐标由τ(D)的最大的d个特征值所对应的特征向量给出。
图1 欧氏距离,测地线距离和最短路径
在给定数据集良好抽样且内在扁平的条件下,ISOMAP算法能成功运用,如对不含噪声的Swiss-Roll数据集来讲,在映射到低维平面后能得到一理想的矩形面(图1(b))。但是在绝大部分环境下数据集一般是含噪声的,ISOMAP算法首先需要构造数据点的邻接图,而噪声点的出现就直接影响了数据点的邻接关系图。由图2可以看出噪声点的出现破坏了原有数据点的邻接结构,当数据集中噪声点规模较大时,数据集中噪声点势必会破坏整个数据集的拓扑结构,进而会对整个降维映射过程产生较大影响。因此需要对这些噪声点进行处理来得到较为理想的低维映射结果。
图2 噪声点对数据集邻接图的影响
2基于SNN孤立点检测算法
共享最近邻聚类是一种整合了多种聚类思想的聚类方法,可以处理包含噪声、孤立点以及任意形状、大小、密度的子类的高维数据的聚类问题。同时SNN算法可以适用于高维数据的聚类问题,通常情况下,噪声点的邻接点较少,因此可以通过计算共享的最近邻来定义两个对象之间的相似性,并以此来检测噪声点。
设Ω为n维样本空间,点p,p∈Ω,点p的最近k近邻列表是表示与点p距离最近的k个点组成的集合,用nn[p]表示。(V,E)表示共享最近邻图。u,v当且仅当u∈nn[v]且时v∈nn[u]认定点u,v之间有连接;具体的两点间的连接强度可由下式来确定:
str(u,v)=Σ(k+1-m)*(k+1-n),um=vn(2.1)
str(u)=Σsum(str(u,v))(2.2)
根据(2.1)可以得到两点的连接强度矩阵,设定一定阈值,连接强度低于一定阈值的可视为噪声点的连接边,可以直接删除;通过(2.2)可以计算每个点的连接强度,对连接强度低于域值的可视为噪声点。图3(a)所示为含噪声点的不规则分布的数据点集,图3(b)中加号点为检测出的噪声点,可以看出基于SNN的孤立点检测算法效果良好。
图3 基于SNN的孤立点检测算法对各种数据集形状的数据点的检测结果
3基于SNN的鲁棒性ISOMAP算法
由基于SNN的孤立点检测算法在除噪中的应用,可以设计基于SNN的鲁棒性ISOMAP算法,对除噪后的数据集进行降维。
对噪声点的处理引入一个数据泛化公式进行处理,由于非线性映射算法泛化能力弱,不能找到直接的映射函数完成数据点的映射,可以通过已知数据点的映射结果确定线性公式来近似噪声点映射坐标,具体的推导如下。
设Ω1为除噪后得到的数据集,N为样本数,XN+1∈RD为待处理的噪声点,D为数据点初始维数,设{xN+11,xN+12…xN+1k}为xN+1在Ω1中的k近邻列表,yN+11,yN+12…yN+1k}为k近邻降维后的数据点坐标。则可通过解下式得到噪声点的重构权值:
通过重构权值可得到映射后的坐标为:
至此,设计具体的基于孤立点检测的鲁棒性ISOMAP算法的步骤为:
Setp1:去除数据集噪声。①构造数据集距离矩阵。②计算每个数据点的K近邻列表。③计算每个数据点的共享近邻图。④采用(2.1)通过共享近邻图计算每两个点之间的连接强度。⑤设定阈值,对数据集中连接强度低于该阈值的视为噪声点,并从数据集中去除该噪声点。
Step2:应用ISOMAP算法;对除噪后得到的数据集进行降维处理。
Step3:对噪声点XN+1的映射处理;查找XN+1在除噪后数据集中k的近邻列表,通过(3.3)得到噪声点映射后的坐标。
4映射质量的度量
为了比较算法的映射质量,需要引入一标准来量化算法的映射好坏,常用的标准是残差(residual variance),具体的残差表达式为:1-ρ2Dx(k)Dy其中Dx(k)和Dy分别表示数据点在原数据空间中的测地距离矩阵(由邻域图中的最短路径长度来进行逼近,在给定数据集的情况下为邻域大小k的函数)和在低维可视空间中的欧氏距离矩阵,ρDx(k)Dy则表示它们之间的线性相关系数。残差越小,表示映射的“质量”越高。
5实验及分析
为了验证本文算法的有效性,对含有噪声点swiss-roll数据集进行验证,如图4所示,该swiss-roll数据集由1000个良好采样的数据点及40个噪声点组成,算法的近邻点个数为5,图4(a)为含噪声点(深色点)swiss-roll数据集,图4(b)为采用经典ISOMAP算法处理后的低维映射结果。图4(c)为本文提出算法检测得到的噪声点(深色点),图4(d)为本文算法得到映射结果,其中深色点为噪声点的映射结果。
从图中可以看出,由于噪声点的出现破坏了良好采样数据集的拓扑结构,使得传统的ISOMAP算法对含噪声点的数据集映射时产生了扭曲,而本文提出的算法可有效去除噪声点,保持了良好采样数据集的拓扑结构;能够有效处理噪声点,提高了传统算法的鲁棒性,使得低维映射能够较好反映数据集的拓扑结构(图4(d))。
图4 不同算法对含噪声数据集的处理结果,k=5
为了进一步说明算法的映射质量,论文对两种算法在不同邻域大小下的残差做了进一步比较(图5实线为本文提出的算法的结果,虚线为经典ISOMAP算法的计算结果),从实验可以看出,论文提出的算法对取不同的邻域大小都优于传统的ISOMAP算法的映射质量,进一步说明了本文算法的可行性和有效性。
6结论
本文对当前流形学习算法的不足做了分析,并针对流形学习算法对噪声点敏感这一问题给出一种有效检测噪声点的算法,对噪声点的处理提出线性泛化公式,并通过实验证明算法的可行性和有效性。
由于噪声点的情况复杂,有些情况下算法会出现一定的误检率和漏检率,同时近邻点个数的大小也会导致阈值的改变,因此还需要进一步改进以提高算法的检测效果。此外由于流形学习算法自适应能力差,提出有效的自适应流形学习算法也是将来需要着手解决的一个问题。
参考文献
1J. B. Tenenbaum, V. de Silva, J. C. Langford.A global geometric
framework for nonlinear dimensionality reduction .Science,2000,290
(5500):2319~2323
2Roweis S T,L.K.Saul. Nonlinear dimensionality reduction by locally
linear embedding.Science,2000,290:2323~2326
3Zhang ZY,Zha HY.Principal Manifolds and Nonlinear Dimension
Reduction via Local Tangent Space Alignment.SLAM Journal of
Scientific Computing,2004.26(1):313~338
4Mikhail Belkin,Partha Niyogi.Laplacian Eigen mapsforDimensionality
Reduction and Data Representation.NeuralComputation,2003,15(6):
1373~1396
【关键词】 流形学习 共享近邻 鲁棒性ISOMAP 残差
论文结合共享近邻(Sharing Nearest Neighbors,SNN)算法思想,提出一种ISOMAP的鲁棒性改进算法,可以有效检测出数据集中的噪声点。首先完成除噪后数据集的低维映射,然后针对噪声点提出泛化公式完成噪声点的低维映射。最后通过对含噪声的Swiss-Roll数据集进行实验,并对映射数据集的残差进行量化,验证了算法的可行性和有效性。
1ISOMAP算法
ISOMAP是由Tenenbaum和Silva于2000年提出的,算法建立在经典的MDS(多维尺度变换)算法基础上,其目标是使降维后的数据尽量保持在降维前的数据间的邻接关系。传统MDS采用欧式距离来度量两点之间的距离关系,但在很多情况下欧式距离度量不能真正体现数据点集之间的真正距离关系。如图1(A)所示,直线为两点之间的欧式距离,曲线为两点沿曲面的距离(测地线距离),可以看出两点间测地线距离更符合数据点的距离关系度量。ISOMAP算法通过计算两点间的最短路经(图1(B)折线)来逼近两点间测地线距离(图1(B)直线),用两点间最短路经距离代替MDS中的欧式距离,完成高维空间到低维空间的映射。
具体的ISOMAP算法步骤可描述为:
Step1:建立加权邻接图G。主要有两种方法确定邻接图的边,ε邻域和k近邻,并以数据点间的欧氏距离作为边上的权重。
Step2:利用图论中的Dijkstra算法或Floyd算法计算图G中每两点间的最短路径,记得到的距离矩阵为DG={dG(i,j)}。
Step3:用MDS求低维嵌入坐标,记H=(Hij)=(δij-),S=(Sij)=(Dij2),则所求的d维嵌入坐标由τ(D)的最大的d个特征值所对应的特征向量给出。
图1 欧氏距离,测地线距离和最短路径
在给定数据集良好抽样且内在扁平的条件下,ISOMAP算法能成功运用,如对不含噪声的Swiss-Roll数据集来讲,在映射到低维平面后能得到一理想的矩形面(图1(b))。但是在绝大部分环境下数据集一般是含噪声的,ISOMAP算法首先需要构造数据点的邻接图,而噪声点的出现就直接影响了数据点的邻接关系图。由图2可以看出噪声点的出现破坏了原有数据点的邻接结构,当数据集中噪声点规模较大时,数据集中噪声点势必会破坏整个数据集的拓扑结构,进而会对整个降维映射过程产生较大影响。因此需要对这些噪声点进行处理来得到较为理想的低维映射结果。
图2 噪声点对数据集邻接图的影响
2基于SNN孤立点检测算法
共享最近邻聚类是一种整合了多种聚类思想的聚类方法,可以处理包含噪声、孤立点以及任意形状、大小、密度的子类的高维数据的聚类问题。同时SNN算法可以适用于高维数据的聚类问题,通常情况下,噪声点的邻接点较少,因此可以通过计算共享的最近邻来定义两个对象之间的相似性,并以此来检测噪声点。
设Ω为n维样本空间,点p,p∈Ω,点p的最近k近邻列表是表示与点p距离最近的k个点组成的集合,用nn[p]表示。(V,E)表示共享最近邻图。u,v当且仅当u∈nn[v]且时v∈nn[u]认定点u,v之间有连接;具体的两点间的连接强度可由下式来确定:
str(u,v)=Σ(k+1-m)*(k+1-n),um=vn(2.1)
str(u)=Σsum(str(u,v))(2.2)
根据(2.1)可以得到两点的连接强度矩阵,设定一定阈值,连接强度低于一定阈值的可视为噪声点的连接边,可以直接删除;通过(2.2)可以计算每个点的连接强度,对连接强度低于域值的可视为噪声点。图3(a)所示为含噪声点的不规则分布的数据点集,图3(b)中加号点为检测出的噪声点,可以看出基于SNN的孤立点检测算法效果良好。
图3 基于SNN的孤立点检测算法对各种数据集形状的数据点的检测结果
3基于SNN的鲁棒性ISOMAP算法
由基于SNN的孤立点检测算法在除噪中的应用,可以设计基于SNN的鲁棒性ISOMAP算法,对除噪后的数据集进行降维。
对噪声点的处理引入一个数据泛化公式进行处理,由于非线性映射算法泛化能力弱,不能找到直接的映射函数完成数据点的映射,可以通过已知数据点的映射结果确定线性公式来近似噪声点映射坐标,具体的推导如下。
设Ω1为除噪后得到的数据集,N为样本数,XN+1∈RD为待处理的噪声点,D为数据点初始维数,设{xN+11,xN+12…xN+1k}为xN+1在Ω1中的k近邻列表,yN+11,yN+12…yN+1k}为k近邻降维后的数据点坐标。则可通过解下式得到噪声点的重构权值:
通过重构权值可得到映射后的坐标为:
至此,设计具体的基于孤立点检测的鲁棒性ISOMAP算法的步骤为:
Setp1:去除数据集噪声。①构造数据集距离矩阵。②计算每个数据点的K近邻列表。③计算每个数据点的共享近邻图。④采用(2.1)通过共享近邻图计算每两个点之间的连接强度。⑤设定阈值,对数据集中连接强度低于该阈值的视为噪声点,并从数据集中去除该噪声点。
Step2:应用ISOMAP算法;对除噪后得到的数据集进行降维处理。
Step3:对噪声点XN+1的映射处理;查找XN+1在除噪后数据集中k的近邻列表,通过(3.3)得到噪声点映射后的坐标。
4映射质量的度量
为了比较算法的映射质量,需要引入一标准来量化算法的映射好坏,常用的标准是残差(residual variance),具体的残差表达式为:1-ρ2Dx(k)Dy其中Dx(k)和Dy分别表示数据点在原数据空间中的测地距离矩阵(由邻域图中的最短路径长度来进行逼近,在给定数据集的情况下为邻域大小k的函数)和在低维可视空间中的欧氏距离矩阵,ρDx(k)Dy则表示它们之间的线性相关系数。残差越小,表示映射的“质量”越高。
5实验及分析
为了验证本文算法的有效性,对含有噪声点swiss-roll数据集进行验证,如图4所示,该swiss-roll数据集由1000个良好采样的数据点及40个噪声点组成,算法的近邻点个数为5,图4(a)为含噪声点(深色点)swiss-roll数据集,图4(b)为采用经典ISOMAP算法处理后的低维映射结果。图4(c)为本文提出算法检测得到的噪声点(深色点),图4(d)为本文算法得到映射结果,其中深色点为噪声点的映射结果。
从图中可以看出,由于噪声点的出现破坏了良好采样数据集的拓扑结构,使得传统的ISOMAP算法对含噪声点的数据集映射时产生了扭曲,而本文提出的算法可有效去除噪声点,保持了良好采样数据集的拓扑结构;能够有效处理噪声点,提高了传统算法的鲁棒性,使得低维映射能够较好反映数据集的拓扑结构(图4(d))。
图4 不同算法对含噪声数据集的处理结果,k=5
为了进一步说明算法的映射质量,论文对两种算法在不同邻域大小下的残差做了进一步比较(图5实线为本文提出的算法的结果,虚线为经典ISOMAP算法的计算结果),从实验可以看出,论文提出的算法对取不同的邻域大小都优于传统的ISOMAP算法的映射质量,进一步说明了本文算法的可行性和有效性。
6结论
本文对当前流形学习算法的不足做了分析,并针对流形学习算法对噪声点敏感这一问题给出一种有效检测噪声点的算法,对噪声点的处理提出线性泛化公式,并通过实验证明算法的可行性和有效性。
由于噪声点的情况复杂,有些情况下算法会出现一定的误检率和漏检率,同时近邻点个数的大小也会导致阈值的改变,因此还需要进一步改进以提高算法的检测效果。此外由于流形学习算法自适应能力差,提出有效的自适应流形学习算法也是将来需要着手解决的一个问题。
参考文献
1J. B. Tenenbaum, V. de Silva, J. C. Langford.A global geometric
framework for nonlinear dimensionality reduction .Science,2000,290
(5500):2319~2323
2Roweis S T,L.K.Saul. Nonlinear dimensionality reduction by locally
linear embedding.Science,2000,290:2323~2326
3Zhang ZY,Zha HY.Principal Manifolds and Nonlinear Dimension
Reduction via Local Tangent Space Alignment.SLAM Journal of
Scientific Computing,2004.26(1):313~338
4Mikhail Belkin,Partha Niyogi.Laplacian Eigen mapsforDimensionality
Reduction and Data Representation.NeuralComputation,2003,15(6):
1373~1396