根据提示，在右侧编辑器的 begin-end 之间补充代码，实现 Isomap 算法。 测试说明 平台会调用你实现的方法对红酒数据进行降维，若降维后数据与正确结果 l1 距离均值小于等于 1 则视为通关，否则输出你处理后的数据。# -*- coding: utf-8 -*- import numpy as np def isomap(data,d,k,Max=10000): ''' input:data(ndarray):待降维数据 d(int):降维后数据维数 k(int):最近的k个样本 Max(int):表示无穷大 output:Z(ndarray):降维后的数据 ''' #********* Begin *********# #计算dist2,dist2i,dist2j,dist2ij #计算B #矩阵分解得到特征值与特征向量 #计算Z #********* End *********# return Z

### ### Isomap 算法的实现步骤 Isomap 是一种非线性降维方法，旨在保留数据的局部和全局几何结构。该算法通过构建低维嵌入来反映高维数据的拓扑结构，保证低维空间中的距离尽可能接近高维空间中的实际距离[^3]。 #### 计算距离矩阵 首先需要计算所有数据点之间的欧氏距离，从而得到邻接矩阵。通常使用 K 近邻算法（KNN）来确定每个点的最近邻居，并在这些点之间建立连接[^3]。 ```python from sklearn.neighbors import kneighbors_graph import numpy as np def compute_adjacency_matrix(X, n_neighbors): adjacency_matrix = kneighbors_graph(X, n_neighbors=n_neighbors, mode='connectivity', include_self=False) distance_matrix = adjacency_matrix.toarray() distance_matrix[distance_matrix == 0] = np.inf for i in range(X.shape[0]): for j in range(X.shape[0]): if distance_matrix[i, j] == np.inf: continue distance_matrix[i, j] = np.linalg.norm(X[i] - X[j]) return distance_matrix ``` #### 最短路径计算 接下来使用 Floyd-Warshall 算法或 Dijkstra 算法来计算任意两点之间的最短路径，以近似流形上的测地距离[^3]。 ```python import itertools def compute_shortest_paths(distance_matrix): N = distance_matrix.shape[0] for k in range(N): for i in range(N): for j in range(N): if distance_matrix[i, j] > distance_matrix[i, k] + distance_matrix[k, j]: distance_matrix[i, j] = distance_matrix[i, k] + distance_matrix[k, j] return distance_matrix ``` #### 中心化矩阵 构造中心化矩阵 $ G $，其元素定义为： $$ G = -\frac{1}{2} (I - \frac{1}{n} \mathbf{1}\mathbf{1}^T) D (I - \frac{1}{n} \mathbf{1}\mathbf{1}^T) $$ 其中 $ D $ 是最短路径矩阵，$ I $ 是单位矩阵，$ \mathbf{1} $ 是全一列向量[^4]。 ```python def center_matrix(D): N = D.shape[0] J = np.eye(N) - np.ones((N, N)) / N G = -0.5 * J @ D @ J return G ``` #### 特征分解 对中心化矩阵 $ G $ 进行特征值分解，并选择前 $ d $ 个最大特征值对应的特征向量构成映射矩阵，最终将数据映射到低维空间中[^1]。 ```python def eigen_decomposition(G, n_components): eigen_values, eigen_vectors = np.linalg.eigh(G) idx = np.argsort(eigen_values)[::-1] eigen_values = eigen_values[idx] eigen_vectors = eigen_vectors[:, idx] eigenvectors_subset = eigen_vectors[:, :n_components] eigenvalues_subset = eigen_values[:n_components] Y = eigenvectors_subset * np.sqrt(eigenvalues_subset) return Y ``` #### 降维结果生成 最后将数据投影到新的低维空间中并进行可视化。 ```python import matplotlib.pyplot as plt def isomap(X, n_components=2, n_neighbors=5): distance_matrix = compute_adjacency_matrix(X, n_neighbors) shortest_paths = compute_shortest_paths(distance_matrix) G = center_matrix(shortest_paths) Y = eigen_decomposition(G, n_components) plt.scatter(Y[:, 0], Y[:, 1]) plt.title("Isomap Result") plt.xlabel("Component 1") plt.ylabel("Component 2") plt.show() return Y ```