# -*- 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降维算法的Python代码实现 Isomap（等距映射）是一种非线性降维方法，通过计算数据点之间的测地距离来保留流形结构。以下是基于给定框架完成Isomap降维算法的具体步骤，包括计算 `dist2`、矩阵 `B`、特征值分解以及最终降维结果 `Z` 的 Python 代码实现。 #### 1. 计算邻接图和最短路径矩阵 首先，使用 Floyd-Warshall 算法或 Dijkstra 算法计算数据点之间的最短路径矩阵。这是 Isomap 的核心步骤之一，用于近似测地距离。 ```python import numpy as np from scipy.sparse.csgraph import floyd_warshall from sklearn.metrics.pairwise import euclidean_distances def compute_geodesic_distance(X, n_neighbors): # 计算欧氏距离矩阵 dist = euclidean_distances(X, X) # 构建邻接图：仅保留最近的 n_neighbors 个邻居 adj_matrix = np.inf * np.ones(dist.shape) sorted_indices = np.argsort(dist, axis=1)[:, :n_neighbors] for i in range(adj_matrix.shape[0]): adj_matrix[i, sorted_indices[i]] = dist[i, sorted_indices[i]] # 使用 Floyd-Warshall 算法计算最短路径矩阵 geodesic_dist = floyd_warshall(csgraph=adj_matrix, directed=False) return geodesic_dist ``` #### 2. 计算平方距离矩阵 `dist2` 将最短路径矩阵平方以得到 `dist2`。 ```python def compute_squared_distance(geodesic_dist): # 平方距离矩阵 dist2 = geodesic_dist ** 2 return dist2 ``` #### 3. 构造中心化矩阵 `B` 根据公式 \( B = -\frac{1}{2} H \cdot D^2 \cdot H \)，其中 \( H = I - \frac{1}{n} \mathbf{1} \mathbf{1}^T \) 是中心化矩阵。 ```python def construct_B_matrix(dist2): n = dist2.shape[0] H = np.eye(n) - np.ones((n, n)) / n # 中心化矩阵 B = -0.5 * H @ dist2 @ H return B ``` #### 4. 进行特征值分解 对矩阵 `B` 进行特征值分解，并提取前 `n_components` 个最大的特征值及其对应的特征向量。 ```python from scipy.linalg import eigh def eigen_decomposition(B, n_components): # 特征值分解 eigenvalues, eigenvectors = eigh(B) # 取前 n_components 个最大的特征值及其对应的特征向量 sorted_indices = np.argsort(eigenvalues)[::-1] largest_eigenvalues = eigenvalues[sorted_indices[:n_components]] largest_eigenvectors = eigenvectors[:, sorted_indices[:n_components]] return largest_eigenvalues, largest_eigenvectors ``` #### 5. 计算降维结果 `Z` 根据特征值和特征向量构造降维后的数据矩阵 \( Z \)。 ```python def compute_embedding(largest_eigenvalues, largest_eigenvectors): # 归一化特征向量 Z = largest_eigenvectors @ np.diag(np.sqrt(largest_eigenvalues)) return Z ``` #### 完整的 Isomap 实现 将上述步骤整合为一个完整的函数： ```python def isomap(X, n_neighbors, n_components): # Step 1: 计算最短路径矩阵 geodesic_dist = compute_geodesic_distance(X, n_neighbors) # Step 2: 计算平方距离矩阵 dist2 = compute_squared_distance(geodesic_dist) # Step 3: 构造中心化矩阵 B B = construct_B_matrix(dist2) # Step 4: 特征值分解 eigenvalues, eigenvectors = eigen_decomposition(B, n_components) # Step 5: 计算降维结果 Z = compute_embedding(eigenvalues, eigenvectors) return Z ``` #### 示例用法 以下是一个简单的示例，展示如何使用上述函数进行 Isomap 降维。 ```python from sklearn.datasets import make_swiss_roll # 生成瑞士卷数据集 X, _ = make_swiss_roll(n_samples=1000, noise=0.1) # 应用 Isomap 降维 Z = isomap(X, n_neighbors=12, n_components=2) # 可视化降维结果 import matplotlib.pyplot as plt plt.figure(figsize=(8, 6)) plt.scatter(Z[:, 0], Z[:, 1], c=np.arange(len(Z)), cmap='viridis') plt.title('Isomap Dimensionality Reduction') plt.xlabel('Component 1') plt.ylabel('Component 2') plt.colorbar(label='Data Index') plt.show() ``` --- ###