扩散映射是一种非线性降维技术，由Ronald R. Coifman和Stéphane Lafon于2006年提出。它通过在数据点上建模随机游走或扩散过程，构建高维数据的低维表示。该方法捕捉数据流形的内在几何结构，强调局部连接而忽略全局距离，因此对噪声和异常值具有鲁棒性。扩散映射广泛应用于机器学习、数据分析以及科学计算等领域，用于可视化、聚类和去噪等任务。
其核心思想是在数据点上定义一个马尔可夫链，其中转移概率反映点之间的相似性。通过分析转移矩阵的特征向量，该方法将数据嵌入到欧几里得空间中，使得欧几里得距离近似于扩散距离，即沿流形的连通性度量。这种嵌入保留了局部结构，同时揭示全局模式，在非线性数据上往往优于主成分分析等线性方法。
数学基础
扩散映射算法从核函数开始，通常采用高斯核，定义为 \( k(x_i, x_j) = \exp(-\|x_i - x_j\|^2 / \epsilon) \)，其中 \( \epsilon \) 是控制邻域大小的尺度参数。基于该核，通过归一化核矩阵构造一个行随机矩阵 \( P \)。矩阵 \( P \) 表示数据图上随机游走的转移概率，其中 \( P_{ij} \) 是从点 \( i \) 一步移动到点 \( j \) 的概率。
扩散过程通过 \( P \) 的幂次来研究，其中 \( P^t \) 给出 \( t \) 步转移概率。在时间 \( t \) 时，两个点之间的扩散距离定义为它们在 \( t \) 步后的概率分布之间的加权 \( L^2 \) 距离。关键结果是，该距离可以通过 \( P \) 的特征向量和特征值来计算。具体而言，扩散映射将每个点 \( x_i \) 嵌入到一个向量中，其分量是缩放后的特征向量：\( \Psi_t(x_i) = (\lambda_1^t \psi_1(i), \lambda_2^t \psi_2(i), \ldots) \)，其中 \( \lambda_k \) 和 \( \psi_k \) 分别是特征值和特征向量。截断到前 \( d \) 个特征向量，得到一个 \( d \) 维嵌入，该嵌入近似于扩散距离。
与谱聚类和流形学习的关系
扩散映射属于谱方法家族，该家族还包括拉普拉斯特征映射和谱聚类。与依赖最短路径距离的方法不同，扩散映射使用整个扩散过程，因此对噪声引起的短路连接更具鲁棒性。参数 \( t \) 控制分析的尺度：较小的 \( t \) 强调局部结构，而较大的 \( t \) 揭示全局连通性。这种灵活性允许实践者以多种分辨率探索数据。
该方法与流形上的热核密切相关，因为扩散过程近似于热方程。这一联系提供了理论保证：随着数据点数量的增加和 \( \epsilon \) 的减小，特征向量收敛到底层流形上拉普拉斯-贝尔特拉米算子的特征函数。这一性质使扩散映射成为流形学习的原理性工具，正如Coifman和Lafon的工作所证明的那样。
在机器学习和科学中的应用
在机器学习中，扩散映射用于非线性特征提取，通常作为聚类或分类的预处理步骤。例如，在图像分析中，它们可以在没有显式标签的情况下，根据形状或纹理分离不同的对象类别。在人工智能研究中，扩散映射已被应用于神经网络的可解释性，通过将高维激活可视化到低维空间。
在科学领域，扩散映射已被用于分析单细胞RNA测序数据，帮助识别细胞类型和轨迹。它们还被应用于分子动力学，以发现描述蛋白质折叠的慢集体变量。该方法已在多种软件库中实现，包括scikit-learn，它为Python用户提供了DiffusionMap类。
扩展与变体
为应对原始算法的局限性，已开发出多种扩展。各向异性扩散映射引入了密度归一化参数 \( \alpha \)，以处理数据点的非均匀采样。多尺度扩散映射结合多个时间尺度 \( t \)，同时捕捉局部和全局结构。此外，样本外扩展技术允许嵌入新数据点而无需重新计算整个映射，使用Nyström方法或几何谐波。
近期研究已将扩散映射与深度学习架构相结合。例如，扩散映射坐标可以作为残差网络中的辅助目标，以改进表示学习。还有工作将扩散映射用于生成式AI模型，其中扩散过程启发了生成扩散模型，尽管这些与降维技术有所不同。
计算考量
扩散映射的主要计算成本在于构造核矩阵并计算其特征向量。对于大型数据集，这可能难以承受，因为矩阵是 \( n \times n \) 的，其中 \( n \) 是点数。稀疏近似，例如使用 \( k \)-最近邻将小的核值置零，可以减少内存和时间。随机化特征分解算法，如AWS和谷歌云等库中实现的，可以加速计算。在实践中，扩散映射通常应用于多达数万个点的数据集，尽管存在适用于更大数据的可扩展变体。
尺度参数 \( \epsilon \) 的选择至关重要。如果太小，图会变得不连通；如果太大，嵌入会丢失局部细节。启发式方法包括将 \( \epsilon \) 设置为成对距离的中位数，或使用基于熵的准则。时间参数 \( t \) 通常设为1以简化，但较大的值可以改善全局结构，代价是丢失精细细节。
参见
参考文献
- Coifman, R. R., & Lafon, S. (2006). Diffusion maps. Applied and Computational Harmonic Analysis, 21(1), 5-30.
- Lafon, S., & Lee, A. B. (2006). Diffusion maps and coarse-graining: A unified framework for dimensionality reduction, graph partitioning, and data set parameterization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28(9), 1393-1403.
- Nadler, B., Lafon, S., Coifman, R. R., & Kevrekidis, I. G. (2006). Diffusion maps, spectral clustering and reaction coordinates of dynamical systems. Applied and Computational Harmonic Analysis, 21(1), 113-127. (注：这些是标准参考文献；文章为原创散文。)