等度量映射ISOMAP
映射 度量
2023-09-14 09:08:53 时间
简介
流形学习是一类借鉴了拓扑流形概念的降维方法。流形是在局部与欧式空间同胚的空间,换言之,它在局部具有欧式空间的性质,能用欧式距离来进行距离计算。若低维流形嵌入到高维空间中,则数据样本在高维空间的分布虽然看上去非常复杂,但在局部上仍具有欧式空间的性质,基于流形学习的降维正是这种“邻域保持”的思想。如此,可以在局部建立降维映射关系,然后再设法将局部映射推广到全局。当维数被降至二维或三维时,能对数据进行可视化展示。因此流形学习也可被用于可视化 。
Isomap算法
Isomap算法是在MDS算法的基础上衍生出的一种算法,MDS算法是保持降维后的样本间距离不变,Isomap 算法引进了邻域图,样本只与其相邻的样本连接,他们之间的距离可直接计算,较远的点可通过最小路径算出距离,在此基础上进行降维保距。在近邻连接图上计算两点间的最短路径,可采用著名的Dikstra算法或Floyd 算法,在得到任意两点的距离之后,就可通过 MDS 方法来获得样本点在低维空间中的坐标.
Isomap算法描述
tips:构建邻接图,有两种方法,第一种指定半径阈值,半径内地点为邻近点,第二种为K近邻,在邻近点之间基于欧式距离构建一个邻接图
Isomap 最主要的优点就是使用“测地距离”,而不是使用原始的欧几里得距离,这样可以更好的控制数据信息的流失,能够在低维空间中更加全面的将高维空间的数据表现出来。
代码
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#最小路径这里采用Floyd算法:输入邻接矩阵,邻接矩阵中,除了邻域点之外,其余距离都是无穷大,输出完整的距离矩阵。
def floyd(D,n_neighbors=15):
Max=numpy.max(D)*1000
n1,n2=D.shape
k=n_neighbors
D1=numpy.ones((n1,n1))*Max
D_arg=numpy.argsort(D,axis=1)
for i in range(n1):
D1[i,D_arg[i,0:k+1]]=D[i,D_arg[i,0:k+1]]
for k in xrange(n1):
for i in xrange(n1):
for j in xrange(n1):
if D1[i,k]+D1[k,j]<D1[i,j]:
D1[i,j]=D1[i,k]+D1[k,j]
return D1
#其余是MDS的算法:
def calculate_distance(x,y):
d=numpy.sqrt(numpy.sum((x-y)**2))
return d
def calculate_distance_matrix(x,y):
d=metrics.pairwise_distances(x,y)
return d
def cal_B(D):
(n1,n2)=D.shape
DD=numpy.square(D)
Di=numpy.sum(DD,axis=1)/n1
Dj=numpy.sum(DD,axis=0)/n1
Dij=numpy.sum(DD)/(n1**2)
B=numpy.zeros((n1,n1))
for i in xrange(n1):
for j in xrange(n2):
B[i,j]=(Dij+DD[i,j]-Di[i]-Dj[j])/(-2)
return B
def MDS(data,n=2):
D=calculate_distance_matrix(data,data)
B=cal_B(D)
Be,Bv=numpy.linalg.eigh(B)
Be_sort=numpy.argsort(-Be)
Be=Be[Be_sort]
Bv=Bv[:,Be_sort]
Bez=numpy.diag(Be[0:n])
Bvz=Bv[:,0:n]
Z=numpy.dot(numpy.sqrt(Bez),Bvz.T).T
return Z
#合成Isomap算法:
def Isomap(data,n=2,n_neighbors=30):
D=calculate_distance_matrix(data,data)
D_floyd=floyd(D)
B=cal_B(D_floyd)
Be,Bv=numpy.linalg.eigh(B)
Be_sort=numpy.argsort(-Be)
Be=Be[Be_sort]
Bv=Bv[:,Be_sort]
Bez=numpy.diag(Be[0:n])
Bvz=Bv[:,0:n]
Z=numpy.dot(numpy.sqrt(Bez),Bvz.T).T
return Z
#生成数据集:
def generate_curve_data():
xx,target=datasets.samples_generator.make_s_curve(400, random_state=9)
return xx,target
#调用函数:
if __name__=='__main__':
data,target=generate_curve_data()
Z_Isomap=Isomap(data,n=2)
Z_MDS=MDS(data)
figure=pyplot.figure()
pyplot.suptitle('ISOMAP COMPARE TO MDS')
pyplot.subplot(1,2,1)
pyplot.title('ISOMAP')
pyplot.scatter(Z_Isomap[:,0],Z_Isomap[:,1],c=target,s=60)
pyplot.subplot(1,2,2)
pyplot.title('MDS')
pyplot.scatter(Z_MDS[:,0],Z_MDS[:,1],c=target,s=60)
pyplot.show()
相关文章
- 数据映射--平衡二叉有序树
- 最全三大框架整合(使用映射)——struts.xml和web.xml配置
- 最全三大框架整合(使用映射)——DeptServiceImpl.java
- 最全三大框架整合(使用映射)——IDeptDao.java
- 【python cookbook】【数据结构与算法】6.在字典中将键映射到多个值上
- OpenGL ES 详解纹理生成和纹理映射步骤以及函数
- NeHe OpenGL教程 第六课:纹理映射
- SAP CRM中间件Material Sales Organization和distribution channel的映射逻辑
- atitit. orm mapping cfg 映射配置(3)-------hbnt one2maney cfg
- 一种类似于windows消息映射的方式编程思想分析(NRF52832平台上运行)
- 【Hibernate步步】--一对一映射双向关联具体解释(两)
- hibernate 继承映射
- Java中出现“错误: 编码GBK的不可映射字符”的解决方法
- RBF网络——核心思想:把向量从低维m映射到高维P,低维线性不可分的情况到高维就线性可分了
- 【大数据实时数据同步】OGG异构多路映射同步原表&审计表&只存删除数据表实现方案(一)