题目一 现有1500个二维空间的数据点，请完成如下工作： (1).编写一个程序不调用sklearn.manifold ，实现ISOMAP降维度。 (2).编写一个程序不调用locally_linear_embedding，实现LLE降维。

ISOMAP算法的实现：

ISOMAP算法是一种基于流形学习的非线性降维方法，主要用于处理高维数据。其基本思想是在保持数据间的距离不变的情况下，将高维数据映射到低维空间中。

ISOMAP算法的主要步骤如下：

1.计算每个数据点之间的欧几里得距离。

2.对于每个数据点，找到与其距离最近的K个数据点，并建立它们之间的边。

3.使用Floyd算法计算任意两个数据点之间的最短路径。

4.基于最短路径计算数据点之间的测地距离。

5.将测地距离作为输入，使用MDS算法将数据点映射到低维空间中。

下面是ISOMAP算法的Python实现：

import numpy as np
from scipy.spatial.distance import cdist
from scipy.sparse import lil_matrix, csgraph
from sklearn.utils.graph_shortest_path import graph_shortest_path

def isomap(X, n_components, n_neighbors):
    # 计算每个数据点之间的欧几里得距离
    D = cdist(X, X)
    
    # 对于每个数据点，找到与其距离最近的K个数据点，并建立它们之间的边
    knn_graph = lil_matrix((X.shape[0], X.shape[0]), dtype=np.float32)
    for i in range(X.shape[0]):
        indices = np.argsort(D[i])[1:n_neighbors+1]
        knn_graph[i, indices] = D[i, indices]
        
    # 使用Floyd算法计算任意两个数据点之间的最短路径
    dist_matrix = graph_shortest_path(knn_graph, directed=False)
    
    # 基于最短路径计算数据点之间的测地距离
    G = csgraph.laplacian(dist_matrix, normed=True)
    eigvals, eigvecs = np.linalg.eig(G)
    indices = np.argsort(eigvals)[:n_components]
    Y = eigvecs[:, indices].real
    return Y

LLE算法的实现：

LLE算法是一种基于局部线性嵌入的非线性降维方法，主要用于处理高维数据。其基本思想是在保持数据间的局部线性关系不变的情况下，将高维数据映射到低维空间中。

LLE算法的主要步骤如下：

1.对于每个数据点，找到与其距离最近的K个数据点，并使用它们构建一个K维线性空间。

2.计算每个数据点在该K维线性空间中的权重系数。

3.对于每个数据点，将其表示为其K个最近邻点的加权线性组合。

4.使用MDS算法将数据点映射到低维空间中。

下面是LLE算法的Python实现：

import numpy as np
from scipy.spatial.distance import cdist
from sklearn.utils.graph_shortest_path import graph_shortest_path

def lle(X, n_components, n_neighbors):
    # 计算每个数据点之间的欧几里得距离
    D = cdist(X, X)
    
    # 对于每个数据点，找到与其距离最近的K个数据点，并使用它们构建一个K维线性空间
    knn_indices = np.argsort(D, axis=1)[:, 1:n_neighbors+1]
    knn_distances = np.array([D[i, knn_indices[i]] for i in range(X.shape[0])])
    W = np.zeros((n_neighbors, n_neighbors))
    for i in range(n_neighbors):
        G = X[knn_indices[:, i]] - X
        C = np.dot(G, G.T)
        w = np.linalg.solve(C, np.ones(n_neighbors))
        W[i] = w / np.sum(w)
    M = np.eye(X.shape[0]) - np.dot(W, np.eye(n_neighbors))
    
    # 计算每个数据点在该K维线性空间中的权重系数
    eigvals, eigvecs = np.linalg.eig(np.dot(M.T, M))
    indices = np.argsort(eigvals)[1:n_components+1]
    Y = eigvecs[:, indices].real
    
    # 对于每个数据点，将其表示为其K个最近邻点的加权线性组合
    knn_indices = np.argsort(D, axis=1)[:, :n_neighbors]
    knn_distances = np.array([D[i, knn_indices[i]] for i in range(X.shape[0])])
    W = np.zeros((X.shape[0], n_neighbors))
    for i in range(X.shape[0]):
        G = X[knn_indices[i]] - X[i]
        C = np.dot(G, G.T)
        w = np.linalg.solve(C, np.ones(n_neighbors))
        W[i] = w / np.sum(w)
    Y = np.dot(W, Y)
    
    # 使用MDS算法将数据点映射到低维空间中
    G = cdist(Y, Y)
    H = np.eye(X.shape[0]) - np.ones((X.shape[0], X.shape[0])) / X.shape[0]
    S = -0.5 * np.dot(np.dot(H, G ** 2), H)
    eigvals, eigvecs = np.linalg.eig(S)
    indices = np.argsort(eigvals)[::-1][:n_components]
    Y = eigvecs[:, indices].real
    return Y