isomap 的代码实现

以下是一个简单的 Python 代码实现 Isomap 算法：

import numpy as np
from scipy.spatial.distance import cdist
from sklearn.neighbors import NearestNeighbors


class Isomap:
    def __init__(self, n_components=2, n_neighbors=5):
        self.n_components = n_components
        self.n_neighbors = n_neighbors
        
    def fit_transform(self, X):
        dist_matrix = cdist(X, X)
        
        # 计算每个样本的最近邻
        knn = NearestNeighbors(n_neighbors=self.n_neighbors+1).fit(X)
        distances, indices = knn.kneighbors(X)
        
        # 构建权重矩阵
        weights = np.zeros_like(dist_matrix)
        for i in range(X.shape[0]):
            for j in indices[i]:
                weights[i][j] = dist_matrix[i][j]
                weights[j][i] = dist_matrix[i][j]
                
        # 计算最短路径距离
        for k in range(X.shape[0]):
            for i in range(X.shape[0]):
                for j in range(X.shape[0]):
                    if weights[i][j] > weights[i][k] + weights[k][j]:
                        weights[i][j] = weights[i][k] + weights[k][j]
        
        # 计算内积矩阵
        B = np.zeros((X.shape[0], X.shape[0]))
        for i in range(X.shape[0]):
            for j in range(X.shape[0]):
                if i != j:
                    B[i][j] = -0.5 * (weights[i][j] ** 2 - 
                                      (dist_matrix[i][j] ** 2) / self.n_neighbors + 
                                      np.sum((dist_matrix[i][indices[i][1:]] ** 2) / self.n_neighbors) + 
                                      np.sum((dist_matrix[j][indices[j][1:]] ** 2) / self.n_neighbors))
                    
        # 对内积矩阵进行特征值分解
        eigvals, eigvecs = np.linalg.eigh(B)
        indices = np.argsort(eigvals)[::-1]
        eigvals = eigvals[indices][:self.n_components]
        eigvecs = eigvecs[:, indices][:, :self.n_components]
        
        # 将特征向量转换为新的低维表示
        Y = eigvecs.dot(np.diag(np.sqrt(eigvals)))
        
        return Y

使用示例：

import matplotlib.pyplot as plt
from sklearn.datasets import make_s_curve

# 生成三维 S 形数据
X, color = make_s_curve(n_samples=1000, random_state=0)

# 使用 Isomap 算法将数据降到二维
isomap = Isomap(n_components=2)
Y = isomap.fit_transform(X)

# 可视化降维结果
plt.scatter(Y[:, 0], Y[:, 1], c=color)
plt.title("Isomap")
plt.show()