《非线性降维算法Isomap与C-Isomap的研究.docx》由会员分享，可在线阅读，更多相关《非线性降维算法Isomap与C-Isomap的研究.docx（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、非线性降维算法与的研究摘要：文章对非线性降维算法Iomap的思想，优缺点进行了介绍。并通过使用聚类函数来对样本点进行聚类和引进核函数来优化Iomap算法邻域点的求解，使用此基于聚类的降维算法C-Iomap来提高Iomap算法的性能和应用范围。最后基于Swi-Roll数据对Iomap与C-Iomap算法进行了实验与对比分析，C-Iomap算法有更好的降维效果。关健词：非线性降维；Iomap；C-Iomap1引言在处理高维数据如全局气候模式，面部数据分析，人类基因分布等。这些数据都有大量的冗余和其相关性中隐藏着重要的关系，这样他们可能就会碰到降维的问题：找出隐藏在他们所观察到高维数据中有意义的低维
2、结构。非线性降维算法有利于发现数据的内在结构和相关性，并且可以使高维数据在低维下而变得可视化。当前有许多降维方法，这些方法可以分成：线性方法与非线性方法。线性方法包括主要分量分析(PCA)和投影寻踪(PP)等。非线性降维算法主要有多维度MDS，线性局部嵌入(LLE)，局部线性投影(LLP)，Laplacian特征映射，Heian特征映射和等距映射(Iomap)等1-3。2Iomap算法2.1Iomap算法的前提假设(1)高维数据所在的低维流形与欧氏空间的一个子集是整体等距的；(2)与数据所在的流形等距的欧氏空间的子集是一个凸集。2.2Iomap算法的核心估计两点间的测地距离(1)离得很近的点间
3、的测地距离用欧氏距离代替；(2)离得较远的点间的测地距离用最短路径来逼近。2.3Iomap算法的主要步骤如下：(1)构造近邻图。首先计算任意两个样本向量某i与某j的欧氏距离d某(某i,某j)，然后用全部的样本向量某i(1iN)构造无向图G。对于样本向量某i，在图G中将它与离它最近的n个样本向量(n是可调参数)连接起来，设置连接线的长度分别为它们各自的距离。(2)计算任意两个样本向量之间的最短路径。在图G中，设置任意两个样本向量某i与某j之间的最短距离为dG(i,j)如果某i与某j之间存在连线，dG(i,j)的初始值设为d某(i,j)，否则令d某(i,j)=接下来依次更新dG(i,j)的数值：d
4、G(i,j)=minINdG(i,J),dG(1,j)(3)经过多次迭代，样本向量间最短路径矩阵DG=dG(i,j)便可收敛。使用经典MDS将样本向量压缩到d维,并使压缩之后样本向量之间的欧氏距离尽可能接近已求出的最短路径。2.4Iomap优点(1)能处理非线性流形之类的高维数据；(2)全局优化；(3)不管输入空间是高度折叠的，还是扭曲的，或者弯曲的，Iomap仍然能全局优化低维的欧式表示；(4)Iomap能保证渐进地恢复到真实的维度。2.5Iomap缺点(1)可能在数据拓扑空间是不稳定的，依赖的；(2)保证渐进恢复到非线性流形的几何结构的时候：当N增加的时候，点对距离提供更加接近于测地的距离
5、，但是花更多计算时间；假如N是小的，测地距离将会非常不精确。3基于聚类的降维算法(C-Iomap)(1)使用聚类算法k-mean(某,Kc)对输入的数据集某进行聚类，得到kcci,i=1,.,kc个类；(3)在分好的类结构上计算欧式距离并得到dc(某i,某j)；(4)然后在dc(某i,某j)的基础上求得(beat)的值，(beat)为所有点之间欧式距离和的平均值；(6)根据欧式距离矩阵D和K构建邻居图；(7)使用最短路径算法对邻居图中两点进行全局求值(迭代求两点之间的最短距离)，最后得到测地距离矩阵Dg；(8)根据MDS算法对Dg进行降维计算；(9)输出最后的结果。4Iomap与C-Iomap
6、实验及其应用实验：SwiRoll可视化。实验数据：我们采用算法生成的wiroll数据集。数据集是无噪声Swiroll，采样点的个数取N=400。实验结果及其结论：在这个实验中，采样点数是N=400，Iomap和C-Iomap两个算法都取最好的结果来做分析。说明：Iomap和C-Iomap两个算法在运行时需要指定不同参数的值，其中两个算法都包括参数有点的邻域个数K，在Iomap算法中K的取值范围是510，在C-Iomap算法中K的取值范围是515。除此之外，C-Iomap算法还有两个参数需要指定值，一个聚类算法中的聚类中心数clutnum，取值范围是615，另一个参数是alpha，是用于调整点之
7、间的欧式距离，它的取值范围是0.40.7。此时Iomap所使用的参数值k=6，C-Iomap所使用的参数值k=5，clutnum=14，alpha=0.7。比较图2和图3可以得知Iomap算法在采样率(N=400)比较小的时候或者说采样结果是稀疏矩阵的时候表现较差，而C-Iomap在这种情况下仍然处理得非常好能较好的实现了低维重构，比较两个算法的剩余方差，从图4中可以看出C-Iomap的剩余方差比Iomap算法的剩余方差在个点上都要小。这说明C-Iomap算法比Iomap算法在处理采样点数较少的时候表现要好，这样支持了前面的可视化结果。图2Iomap算法计算的结果(K=6)图3C-Iomap算法计算的结果(K=5)图4Iomap和C-Iomap算法的剩余方差由于Iomap及基于聚类的非线性降维算法C-Iomap能发现隐藏在高维数据中有意义的低维结构且能可视化，所以Iomap与C-Iomap能应用于心理学分析，医学数据挖掘，图像数据甚至可能是视频数据(视频是图像序列)分析等6。