论文部分内容阅读
摘要：文章对非线性降维算法Isomap的思想，优缺点进行了介绍。并通过使用聚类函数来对样本点进行聚类和引进核函数来优化Isomap算法邻域点的求解，使用此基于聚类的降维算法C-Isomap来提高Isomap算法的性能和应用范围。最后基于Swiss-Roll数据对Isomap与C-Isomap算法进行了实验与对比分析，C-Isomap算法有更好的降维效果。
关健词：非线性降维；Isomap；C-Isomap
中图分类号：TP391文献标识码：A文章编号：1009-3044(2007)04-11036-02
1 引言
在处理高维数据如全局气候模式，面部数据分析，人类基因分布等。这些数据都有大量的冗余和其相关性中隐藏着重要的关系，这样他们可能就会碰到降维的问题：找出隐藏在他们所观察到高维数据中有意义的低维结构。非线性降维算法有利于发现数据的内在结构和相关性，并且可以使高维数据在低维下而变得可视化。
当前有许多降维方法，这些方法可以分成：线性方法与非线性方法。线性方法包括主要分量分析(PCA)和投影寻踪(PP)等。非线性降维算法主要有多维度MDS，线性局部嵌入(LLE)，局部线性投影(LLP)，Laplacian特征映射，Hessian特征映射和等距映射(Isomap)等[1-3]。
2 Isomap算法
Isomap算法是近年来用于非线性降维的一个重要算法。它来源于传统的降维算法MDS,算法的关键在于利用样本向量之间的欧氏距离dx(i,j)计算出样本之间的测地距离dG(i,j)，从而真实再现高维数据内在的非线性几何结构。然后使用经典MDS算法构造一个新的d维欧氏空间Y(d是降维空间的维数)，最大限度地保持样本之间的欧式距离dY(i,j)与dG(i,j)误差最小，从而达到降维的目的。如下图1(a)-图1(c)所示。图1(a)中样本分布数据Swiss-roll上。两点间的欧式距离(虚线)不能表征两点的实际距离。分布于流形面上的曲线是两点的测地线距离。流形未知时可以通过最短路径算法对邻域内的距离进行近似地重构两点间的测地线距离。图1(b)、图1(c)是Isomap降维后两点和两条路径(测地线和短程拼接)的投影结果[4]。
2.1 Isomap算法的前提假设
(1)高维数据所在的低维流形与欧氏空间的一个子集是整体等距的； (2)与数据所在的流形等距的欧氏空间的子集是一个凸集。
2.2 Isomap算法的核心估计两点间的测地距离
(1)离得很近的点间的测地距离用欧氏距离代替；(2)离得较远的点间的测地距离用最短路径来逼近。
2.3 Isomap算法的主要步骤如下：(1)构造近邻图。首先计算任意两个样本向量xi与xj的欧氏距离dX(xi,xj)，然后用全部的样本向量 xi(1≤i≤N)构造无向图G。对于样本向量xi，在图G中将它与离它最近的n个样本向量(n是可调参数)连接起来，设置连接线的长度分别为它们各自的距离。
(2)计算任意两个样本向量之间的最短路径。在图G中，设置任意两个样本向量xi与xj之间的最短距离为dG(i,j) 。如果xi与xj之间存在连线，dG(i,j)的初始值设为 dX(i,j)，否则令dX(i,j)=∞ 。接下来依次更新dG(i,j)的数值：dG(i,j)=min≤I≤N{dG(i,J),dG(1,j)} 。
(3)经过多次迭代，样本向量间最短路径矩阵DG={dG(i,j)}便可收敛。使用经典MDS将样本向量压缩到d维,并使压缩之后样本向量之间的欧氏距离尽可能接近已求出的最短路径。
2.4 Isomap优点
(1)能处理非线性流形之类的高维数据；(2)全局优化；(3)不管输入空间是高度折叠的，还是扭曲的，或者弯曲的，Isomap仍然能全局优化低维的欧式表示；(4)Isomap能保证渐进地恢复到真实的维度。
2.5 Isomap缺点
(1)可能在数据拓扑空间是不稳定的，依赖的；(2)保证渐进恢复到非线性流形的几何结构的时候：当N增加的时候，点对距离提供更加接近于测地的距离，但是花更多计算时间；假如N是小的，测地距离将会非常不精确。
3 基于聚类的降维算法(C-Isomap)
通过以上分析，Isomap算法还有很多地方可以改进的在方，比如，可以使用聚类函数来对所有点进行聚类，这样使得属于邻域中的点更加容易识别，就可以尽可能减少短路。还可以引进核函数来优化Isomap算法邻域点的求解。可以使用这两个方法来提高Isomap算法的性能和应用范围。首先应用聚类算法对样例测试集中的点进行聚类，这样数据点相当于被标上了分类标签，然后我们就可以应用核函数来对不同类或者同类的点之间距离进行优化，使得类内点之间的距离相对更近，而类之间的点的距离就更远一点。最终我们就可以在某种程度上消除了一些噪声干扰或者说能消除短路现象。我们把这个算法称作Clustering-Isomap(简称为C-Isomap)[5]。
C-Isomap算法首先要对输入数据采取预处理，也就是对输入数据进行聚类分析和设置类标签信息，接着就根据聚类结果来计算点之间的欧式距离，然后就使用核函数和参数来调整点之间的欧式距离(参数的设置是根据类标签信息聚定的)，最后就使用标准降维算法IsomapII来进行降维计算(MDS算法就包含在其中)。下面就是C-Isomap算法的详细过程：Cluster-Isomap(X, clustnum,alpha,k)
(1)使用聚类算法k-means(X,Kc) 对输入的数据集X进行聚类，得到kc{ci,i=1,...,kc}个类；
(2)对返回结果cidx(是一个包含向量所属类信息的矩阵，它里面的标值是1-clustnum)进行计算，并且对第i个向量标上类标签clabel[i]；
(3)在分好的类结构上计算欧式距离并得到{dc(xi,xj)} ；
(4)然后在{dc(xi,xj)} 的基础上求得β(beat)的值， β(beat)为所有点之间欧式距离和的平均值；
(5)根据类标签分别调整类内点之间的欧式距离和类类点之间的欧式距离，所使用到的关键变量有β(beat)，alpha(用于调整两点之间欧式距离)。关键函数有RBF核函数。此步最后图得到距离矩阵；
(6)根据欧式距离矩阵D和K构建邻居图；
(7)使用最短路径算法对邻居图中两点进行全局求值(迭代求两点之间的最短距离)，最后得到测地距离矩阵Dg；
(8)根据MDS算法对Dg进行降维计算；
(9)输出最后的结果。
4 Isomap与C-Isomap实验及其应用
实验：Swiss Roll可视化。
实验数据：我们采用算法生成的swiss roll数据集。数据集是无噪声Swiss roll，采样点的个数取N=400。
实验过程：(1)利用设置标签函数中的kmens函数首先对在某一采样率下的Swiss Roll数据进行聚类，然后为数据中每个向量标上标签；(2)利用distance函数来计算距离矩阵，并且使用kernel函数和参数来调整点之间的距离，此时的距离是欧式距离；(3)利用IsomapII算法来对距离矩阵进行降维计算，其中包括构建邻居图，计算两点之间的最短路径，使用MDS算法降维；(4)把降维后的结果用图展示出来；(5)保存实验结果。
实验结果及其结论：在这个实验中，采样点数是N=400，Isomap和C-Isomap两个算法都取最好的结果来做分析。
说明：Isomap和C-Isomap两个算法在运行时需要指定不同参数的值，其中两个算法都包括参数有点的邻域个数K，在Isomap算法中K的取值范围是5~10，在C-Isomap算法中K的取值范围是5~15。除此之外，C-Isomap算法还有两个参数需要指定值，一个聚类算法中的聚类中心数clustnum，取值范围是6~15，另一个参数是alpha，是用于调整点之间的欧式距离，它的取值范围是0.4~0.7。此时Isomap所使用的参数值k=6，C-Isomap所使用的参数值k=5，clustnum=14，alpha=0.7。
比较图2和图3可以得知Isomap算法在采样率(N=400)比较小的时候或者说采样结果是稀疏矩阵的时候表现较差，而C-Isomap在这种情况下仍然处理得非常好——能较好的实现了低维重构，比较两个算法的剩余方差，从图4中可以看出C-Isomap的剩余方差比Isomap算法的剩余方差在个点上都要小。这说明C-Isomap算法比Isomap算法在处理采样点数较少的时候表现要好，这样支持了前面的可视化结果。
图2 Isomap算法计算的结果(K=6)
图3 C-Isomap算法计算的结果(K=5)
图4 Isomap和C-Isomap算法的剩余方差
由于Isomap及基于聚类的非线性降维算法C-Isomap能发现隐藏在高维数据中有意义的低维结构且能可视化，所以Isomap与C-Isomap能应用于心理学分析，医学数据挖掘，图像数据甚至可能是视频数据(视频是图像序列)分析等[6]。
参考文献：
[1]S.T.Roweis and L.K.Saul.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,vol. 290, pp. 2323-2326.
[2]J.B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction[J]. Science, 2000,vol. 290, pp. 2319-2323.
[3]M. Belkin, P. Niyogi, Laplacian Eigenmaps for Dimensionality Reduction and Data Representation[J]. Neural Computation, 2003, Vol. 15, Issue 6, pp. 1373-1396.
[4]徐蓉,姜峰,姚鸿勋.流形学习概述[J].智能系统学报,2006,第1卷第1期,44-50.
[5]唐武雷.全局非线性降维算法C-Isomap的研究[M],华南理工大学硕士学位论文,2006.
[6]袁 远,季星来,孙之荣,李衍达.Isomap在基因表达谱数据聚类分析中的应用[J].清华大学学报(自然科学版), 2004.44(9):1286-1289.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
关健词：非线性降维；Isomap；C-Isomap
中图分类号：TP391文献标识码：A文章编号：1009-3044(2007)04-11036-02
1 引言
在处理高维数据如全局气候模式，面部数据分析，人类基因分布等。这些数据都有大量的冗余和其相关性中隐藏着重要的关系，这样他们可能就会碰到降维的问题：找出隐藏在他们所观察到高维数据中有意义的低维结构。非线性降维算法有利于发现数据的内在结构和相关性，并且可以使高维数据在低维下而变得可视化。
当前有许多降维方法，这些方法可以分成：线性方法与非线性方法。线性方法包括主要分量分析(PCA)和投影寻踪(PP)等。非线性降维算法主要有多维度MDS，线性局部嵌入(LLE)，局部线性投影(LLP)，Laplacian特征映射，Hessian特征映射和等距映射(Isomap)等[1-3]。
2 Isomap算法
Isomap算法是近年来用于非线性降维的一个重要算法。它来源于传统的降维算法MDS,算法的关键在于利用样本向量之间的欧氏距离dx(i,j)计算出样本之间的测地距离dG(i,j)，从而真实再现高维数据内在的非线性几何结构。然后使用经典MDS算法构造一个新的d维欧氏空间Y(d是降维空间的维数)，最大限度地保持样本之间的欧式距离dY(i,j)与dG(i,j)误差最小，从而达到降维的目的。如下图1(a)-图1(c)所示。图1(a)中样本分布数据Swiss-roll上。两点间的欧式距离(虚线)不能表征两点的实际距离。分布于流形面上的曲线是两点的测地线距离。流形未知时可以通过最短路径算法对邻域内的距离进行近似地重构两点间的测地线距离。图1(b)、图1(c)是Isomap降维后两点和两条路径(测地线和短程拼接)的投影结果[4]。
2.1 Isomap算法的前提假设
(1)高维数据所在的低维流形与欧氏空间的一个子集是整体等距的； (2)与数据所在的流形等距的欧氏空间的子集是一个凸集。
2.2 Isomap算法的核心估计两点间的测地距离
(1)离得很近的点间的测地距离用欧氏距离代替；(2)离得较远的点间的测地距离用最短路径来逼近。
2.3 Isomap算法的主要步骤如下：(1)构造近邻图。首先计算任意两个样本向量xi与xj的欧氏距离dX(xi,xj)，然后用全部的样本向量 xi(1≤i≤N)构造无向图G。对于样本向量xi，在图G中将它与离它最近的n个样本向量(n是可调参数)连接起来，设置连接线的长度分别为它们各自的距离。
(2)计算任意两个样本向量之间的最短路径。在图G中，设置任意两个样本向量xi与xj之间的最短距离为dG(i,j) 。如果xi与xj之间存在连线，dG(i,j)的初始值设为 dX(i,j)，否则令dX(i,j)=∞ 。接下来依次更新dG(i,j)的数值：dG(i,j)=min≤I≤N{dG(i,J),dG(1,j)} 。
(3)经过多次迭代，样本向量间最短路径矩阵DG={dG(i,j)}便可收敛。使用经典MDS将样本向量压缩到d维,并使压缩之后样本向量之间的欧氏距离尽可能接近已求出的最短路径。
2.4 Isomap优点
(1)能处理非线性流形之类的高维数据；(2)全局优化；(3)不管输入空间是高度折叠的，还是扭曲的，或者弯曲的，Isomap仍然能全局优化低维的欧式表示；(4)Isomap能保证渐进地恢复到真实的维度。
2.5 Isomap缺点
(1)可能在数据拓扑空间是不稳定的，依赖的；(2)保证渐进恢复到非线性流形的几何结构的时候：当N增加的时候，点对距离提供更加接近于测地的距离，但是花更多计算时间；假如N是小的，测地距离将会非常不精确。
3 基于聚类的降维算法(C-Isomap)
通过以上分析，Isomap算法还有很多地方可以改进的在方，比如，可以使用聚类函数来对所有点进行聚类，这样使得属于邻域中的点更加容易识别，就可以尽可能减少短路。还可以引进核函数来优化Isomap算法邻域点的求解。可以使用这两个方法来提高Isomap算法的性能和应用范围。首先应用聚类算法对样例测试集中的点进行聚类，这样数据点相当于被标上了分类标签，然后我们就可以应用核函数来对不同类或者同类的点之间距离进行优化，使得类内点之间的距离相对更近，而类之间的点的距离就更远一点。最终我们就可以在某种程度上消除了一些噪声干扰或者说能消除短路现象。我们把这个算法称作Clustering-Isomap(简称为C-Isomap)[5]。
C-Isomap算法首先要对输入数据采取预处理，也就是对输入数据进行聚类分析和设置类标签信息，接着就根据聚类结果来计算点之间的欧式距离，然后就使用核函数和参数来调整点之间的欧式距离(参数的设置是根据类标签信息聚定的)，最后就使用标准降维算法IsomapII来进行降维计算(MDS算法就包含在其中)。下面就是C-Isomap算法的详细过程：Cluster-Isomap(X, clustnum,alpha,k)
(1)使用聚类算法k-means(X,Kc) 对输入的数据集X进行聚类，得到kc{ci,i=1,...,kc}个类；
(2)对返回结果cidx(是一个包含向量所属类信息的矩阵，它里面的标值是1-clustnum)进行计算，并且对第i个向量标上类标签clabel[i]；
(3)在分好的类结构上计算欧式距离并得到{dc(xi,xj)} ；
(4)然后在{dc(xi,xj)} 的基础上求得β(beat)的值， β(beat)为所有点之间欧式距离和的平均值；
(5)根据类标签分别调整类内点之间的欧式距离和类类点之间的欧式距离，所使用到的关键变量有β(beat)，alpha(用于调整两点之间欧式距离)。关键函数有RBF核函数。此步最后图得到距离矩阵；
(6)根据欧式距离矩阵D和K构建邻居图；
(7)使用最短路径算法对邻居图中两点进行全局求值(迭代求两点之间的最短距离)，最后得到测地距离矩阵Dg；
(8)根据MDS算法对Dg进行降维计算；
(9)输出最后的结果。
4 Isomap与C-Isomap实验及其应用
实验：Swiss Roll可视化。
实验数据：我们采用算法生成的swiss roll数据集。数据集是无噪声Swiss roll，采样点的个数取N=400。
实验过程：(1)利用设置标签函数中的kmens函数首先对在某一采样率下的Swiss Roll数据进行聚类，然后为数据中每个向量标上标签；(2)利用distance函数来计算距离矩阵，并且使用kernel函数和参数来调整点之间的距离，此时的距离是欧式距离；(3)利用IsomapII算法来对距离矩阵进行降维计算，其中包括构建邻居图，计算两点之间的最短路径，使用MDS算法降维；(4)把降维后的结果用图展示出来；(5)保存实验结果。
实验结果及其结论：在这个实验中，采样点数是N=400，Isomap和C-Isomap两个算法都取最好的结果来做分析。
说明：Isomap和C-Isomap两个算法在运行时需要指定不同参数的值，其中两个算法都包括参数有点的邻域个数K，在Isomap算法中K的取值范围是5~10，在C-Isomap算法中K的取值范围是5~15。除此之外，C-Isomap算法还有两个参数需要指定值，一个聚类算法中的聚类中心数clustnum，取值范围是6~15，另一个参数是alpha，是用于调整点之间的欧式距离，它的取值范围是0.4~0.7。此时Isomap所使用的参数值k=6，C-Isomap所使用的参数值k=5，clustnum=14，alpha=0.7。
比较图2和图3可以得知Isomap算法在采样率(N=400)比较小的时候或者说采样结果是稀疏矩阵的时候表现较差，而C-Isomap在这种情况下仍然处理得非常好——能较好的实现了低维重构，比较两个算法的剩余方差，从图4中可以看出C-Isomap的剩余方差比Isomap算法的剩余方差在个点上都要小。这说明C-Isomap算法比Isomap算法在处理采样点数较少的时候表现要好，这样支持了前面的可视化结果。
图2 Isomap算法计算的结果(K=6)
图3 C-Isomap算法计算的结果(K=5)
图4 Isomap和C-Isomap算法的剩余方差
由于Isomap及基于聚类的非线性降维算法C-Isomap能发现隐藏在高维数据中有意义的低维结构且能可视化，所以Isomap与C-Isomap能应用于心理学分析，医学数据挖掘，图像数据甚至可能是视频数据(视频是图像序列)分析等[6]。
参考文献：
[1]S.T.Roweis and L.K.Saul.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,vol. 290, pp. 2323-2326.
[2]J.B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction[J]. Science, 2000,vol. 290, pp. 2319-2323.
[3]M. Belkin, P. Niyogi, Laplacian Eigenmaps for Dimensionality Reduction and Data Representation[J]. Neural Computation, 2003, Vol. 15, Issue 6, pp. 1373-1396.
[4]徐蓉,姜峰,姚鸿勋.流形学习概述[J].智能系统学报,2006,第1卷第1期,44-50.
[5]唐武雷.全局非线性降维算法C-Isomap的研究[M],华南理工大学硕士学位论文,2006.
[6]袁 远,季星来,孙之荣,李衍达.Isomap在基因表达谱数据聚类分析中的应用[J].清华大学学报(自然科学版), 2004.44(9):1286-1289.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。