CMDS算法无法处理距离矩阵中的inf值，请求异常处理方案

当距离矩阵中存在inf（代表图中点不连通）时，原代码计算D**2会生成inf值，后续矩阵乘法得到的B矩阵会包含无效值，直接导致特征分解失败。经典CMDS基于欧氏距离的全局一致性假设，不连通的点无法满足该前提，因此我们可以通过拆分连通分量单独处理的方式解决这个问题：

核心思路 #

1. 识别连通分量：把距离矩阵中的inf视为两点间无连接，构建无向图并找出所有连通子图。
2. 分量内单独CMDS：对每个连通分量单独执行经典CMDS，得到分量内部的局部嵌入。
3. 分量间坐标调整：将不同分量的嵌入结果平移到不同空间区域，避免重叠，保证整体嵌入的可读性。

修改后的代码 #

import numpy as np
from sklearn.metrics import euclidean_distances
from scipy.sparse.csgraph import connected_components

def cmds(X, n_dim, input_type='raw'):
    """
    Classical(linear) multidimensional scaling (MDS) that handles disconnected graphs (inf distances)
    
    Parameters
    ----------
    X: (d, n) array or (n,n) array
        input data. The data are placed in column-major order. 
        That is, samples are placed in the matrix (X) as column vectors
        d: dimension of points
        n: number of points
        
    n_dim: dimension of target space
    
    input_type: it indicates whether data are raw or distance
        - raw: raw data. (n,d) array. 
        - distance: precomputed distances between the data. (n,n) array.
    Returns
    -------
    Y: (n_dim, n) array. projected embeddings.
    evals: list of arrays. eigen values for each connected component
    evecs: list of arrays. corresponding eigen vectors for each connected component
    """

    if input_type == 'distance':
        D = X.copy()
    elif input_type == 'raw':
        Xt = X.T
        D = euclidean_distances(Xt,Xt)
    
    # Step 1: Identify connected components (treat inf as no edge)
    adjacency = np.where(np.isfinite(D), 1, 0)
    n_components, labels = connected_components(csgraph=adjacency, directed=False)
    
    Y = np.zeros((n_dim, D.shape[0]))
    evals_list = []
    evecs_list = []
    
    # Step 2: Process each connected component separately
    for comp in range(n_components):
        comp_indices = np.where(labels == comp)[0]
        n_comp = len(comp_indices)
        
        if n_comp == 1:
            # Single point: place at origin
            Y[:, comp_indices[0]] = np.zeros(n_dim)
            evals_list.append(np.array([]))
            evecs_list.append(np.array([]))
            continue
        
        # Extract sub-distance matrix for the component
        D_comp = D[comp_indices][:, comp_indices]
        
        # Centering matrix for component
        H_comp = np.eye(n_comp) - np.ones((n_comp, n_comp)) / n_comp
        
        # Double-center the distance matrix
        B_comp = -0.5 * H_comp @ (D_comp ** 2) @ H_comp
        
        # Eigen decomposition
        evals_comp, evecs_comp = np.linalg.eigh(B_comp)
        
        # Sort eigenvalues and eigenvectors in decreasing order
        sort_indices = np.argsort(evals_comp)[::-1]
        evals_comp = evals_comp[sort_indices]
        evecs_comp = evecs_comp[:, sort_indices]
        
        # Select top n_dim eigenvectors
        evecs_comp = evecs_comp[:, :n_dim]
        
        # Project data to new space
        Y_comp = np.sqrt(np.diag(evals_comp[:n_dim])) @ evecs_comp.T
        
        # Step 3: Translate component to avoid overlap with others
        shift = (comp + 1) * 5 * np.eye(n_dim)[:, 0]  # Shift along first axis
        Y_comp += shift.reshape(-1, 1)
        
        # Assign to global embedding
        Y[:, comp_indices] = Y_comp
        evals_list.append(evals_comp)
        evecs_list.append(evecs_comp)
    
    return Y, evals_list, evecs_list

关键修改说明 #

• 连通分量识别：使用scipy.sparse.csgraph.connected_components从邻接矩阵（有限距离视为边）中找出所有连通子图。
• 单分量处理：对单个点的分量直接放置在原点，避免无意义的计算。
• 分量平移：通过给每个分量添加固定偏移量，确保不同连通分量的嵌入结果不会重叠，提升可视化效果。你可以根据需求调整偏移量的大小或方向。
• 结果存储：返回每个分量的特征值和特征向量列表，方便后续分析每个子图的嵌入情况。

内容的提问来源于stack exchange，提问作者Sudhanshu Goyal