一.基本思路：局部距離替換高維空間距離

構(gòu)建原始高維空間的距離直接采用了歐氏距離，但這在流形結(jié)構(gòu)數(shù)據(jù)中往往有問題，如下圖所示，黑線長度便是歐氏距離，而采用紅線來表示距離可能會更加合理

所以核心問題便是如何計算紅色線距離，這可以轉(zhuǎn)換為計算近鄰圖上兩點之間的最短距離問題，操作如下：

（1）對樣本中的每個點，保留與它最近的個點（或者領(lǐng)域半徑內(nèi)的點）的歐氏距離，而其他點的距離設(shè)置為無窮大；

（2）采用Dijkstra算法或者Floyd算法計算所有樣本中任意兩點間的最短距離，并更新原始距離矩陣；

而后面的操作同MDS一樣，所以這一節(jié)的主要操作便是對再運用一次Dijkstra算法/Floyd算法，關(guān)于這倆算法這一節(jié)就介紹了，筆者可能會放在后續(xù)的《數(shù)據(jù)結(jié)構(gòu)與算法》項目中再做介紹，哈哈哈~

二.代碼實現(xiàn)

from matplotlib import pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
import numpy as np
%matplotlib inline

def floyd(dist_matrix):
    vex_num=len(dist_matrix)  
    for k in range(vex_num):
        for i in range(vex_num):
            for j in range(vex_num):
                if dist_matrix[i][k]==np.inf or dist_matrix[k][j]==np.inf:
                    temp=np.inf
                else:
                    temp=dist_matrix[i][k]+dist_matrix[k][j]
                if dist_matrix[i][j]>temp:
                    dist_matrix[i][j]=temp
    return dist_matrix

造偽數(shù)據(jù)

n = 200
r = np.linspace(0,1,n)
l = np.linspace(0,1,n)

t = (3 * np.pi) / 2 * ( 1 + 2 * r )
x =  t * np.cos(t)
y = 10 * l
z =t * np.sin(t)
data=np.c_[x,y,z]

構(gòu)建原始距離矩陣

m=data.shape[0]
D=np.zeros(shape=(m,m))
for i in range(0,m):
    for j in range(i,m):
        D[i,j]=np.sqrt(np.sum(np.power(data[i]-data[j],2)))
        D[j,i]=D[i,j]

使用floyd算法進行更新

epsilon=10#領(lǐng)域半徑
D=np.where(D<epsilon,D,np.inf)
D=floyd(D)

使用MDS算法

import os
os.chdir('../')
from ml_models.decomposition import MDS

mds = MDS(n_components=2)
new_data = mds.fit_transform(D=D)
plt.scatter(new_data[:, 0], new_data[:, 1])
plt.show()

三.問題討論

顯然，Isomap會受到最近鄰或者近鄰半徑的影響，選擇過大或者過小都有弊端：

（1）過小，可能會存在“斷路”的情況，圖中某些區(qū)域可能與其他區(qū)域不存在連接，直觀來看就是距離矩陣通過floyd算法更新后還存在np.inf；

（2）過大，則會存在“短路”的情況，使得距離失真，比如最上圖中的黑線距離會取代紅線距離；

在實際使用時通過后續(xù)任務(wù)的表現(xiàn)（分類/回歸任務(wù)的具體表現(xiàn)）來選取