单细胞降维

基于单细胞表达矩阵的降维方式有很多，例如UMAP，t-SNE，PCA等，而Diffusion Map是基于非线性的降维模式。对于单细胞表达谱而言，该降维方法有利于降维出“枝干形状”的效果：

Diffusion Map

文中提到的URD软件既是基于Diffusion Map算法而制作的，Diffusion Map又称为扩散映射，其原理是将空间距离转换为一种状态转移的概率，从而确定随机游走的方向，从而确定细胞发育轨迹
该算法分为确定细胞转移方向（Markov矩阵）和降维（Markov矩阵特征值分解降维）两块

如图所示，红色为我们的目标细胞，在目标细胞周围有一些细胞，那么Diffusion Map首先计算这些细胞两两之间的距离，进而Affinity化，即如果两个细胞距离较大，那么其概率就小，如果两个细胞距离较小，那么其概率就大。再将其转换为Markov矩阵，Markov矩阵表示某细胞向其他细胞转移的概率，因此在网络图中，边的权重可以用Markov矩阵中的元素表示：

如上图所示，对于邻近的几个细胞来说，当距离矩阵换算为Markov矩阵后，里面的元素代表细胞间转移游走的概率，比方说M12代表cell_1向cell_2转移的概率；M13代表cell_1向cell_3转移的概率。距离远的细胞转移概率比较小，距离近的细胞转移概率比较大（参照下文的Markov矩阵）。
因此Markov矩阵表示细胞随机转移到方向，进而特征值分解降维到二维即可看出细胞的轨迹

1.计算距离矩阵

那么我们的单细胞矩阵形如：

单细胞表达矩阵

每一行代表一个基因（一共m个基因）。每一列代表一个细胞（一共n个细胞）。首先，该算法先计算两两细胞之间的距离，转换为距离矩阵D：

距离矩阵

2.Affinity

之后根据一些核函数，例如高斯核函数进行转化，这一步称为Affinity，转移后的矩阵简称为A矩阵，i 为行，j 为列，其中Dij代表上述的距离矩阵：

高斯核转换
A矩阵如下：
A矩阵

3.标准化（Markov矩阵）

再之后将A矩阵按行标准化以后，转化为Markov矩阵：

将Markov矩阵简称为M矩阵：

M矩阵

比方说，cell_1和cell_2对应的值表示cell_1向cell_2转移的概率；而Markov矩阵为实对称矩阵，一定能分解为n个秩为1的方阵乘它们各自的特征值λ然后相加的结果

接着我们需要把M矩阵给对角化分解：

其中ψ1，ψ2.....ψn是ψ矩阵的行向量，ψ矩阵为特征向量矩阵

ψ矩阵为n×n的特征向量方阵
那么 t 表示多重转移的次数，转移多次后可以达到平稳状态；这个对角矩阵的主对角线表示的是M矩阵的特征值（这里只展示3个）：

对角矩阵

此时重构数据点new：

其中ψ1，ψ2.....ψn是ψ矩阵的行向量

容易得到：

ψ×M代表将特征向量重新做旋转拉伸，变换后的特征向量带有M矩阵的特征，即细胞间距离的特征。
特征向量指向的点代表每个细胞在高维空间所在的点，变换后的列向量为带有细胞距离特征的新坐标点

ψ矩阵为n×n的特征向量方阵

其中q1，q2.....qn为ψ矩阵的列向量，即特征向量；ψ1，ψ2.....ψn是ψ矩阵的行向量；由于M矩阵为实对称矩阵，因此q1...qn相互正交(实对称矩阵可以被正交对角化)

也就是重构的新坐标点矩阵等于特征向量矩阵乘Markov矩阵，对应的元素是相等的，并以此作为新坐标点，M矩阵表示的是两两cell的距离，其中ψ×M相当于做拉伸旋转变化，变换后表示每个细胞在高维空间的相对位置（相对坐标）
个人认为作者采用M矩阵的特征向量组来重构坐标是因为方便后续的计算，个人感觉任意一组正交向量组都可以，因为降维是依据特征值λ的大小来完成的，所以M矩阵的特征向量组是最好选择

新构造的矩阵为new表示的是每个细胞在对应维度的坐标：

new
其中λ的顺序为从大到小，ψ矩阵为n×n的特征向量方阵，ψi 表示第 i 行向量；即第 i 行的特征向量。从某种意义上，此时的n仍然表示细胞个数，而假设我想降维到二维，那么我只需保留前两个即可，即 i=1，2，那么每个细胞的坐标既是二维的

这样就完成了降维，那么Diffusion Map通过Markov随机游走来判断细胞转移的方向，从而确定细胞轨迹的

小tip

这个tip是关于如何理解

这一个坐标转换公式的意义，我们不妨举一个简单的例子：

前面的是特征向量矩阵，后面的是M矩阵，正如我们所说的，M矩阵是一个实对称矩阵，所以特征向量：q1，q2，q3是相互正交的，并且M×q与q转置×M是等效的
我们不妨利用矩阵的乘法性质画出图来观察：

在高维空间里，三个细胞的相对位置如图所示，假设cell_1坐标为(a1,b1,c1)；cell_2坐标为(a2,b2,c2)；cell_3坐标为(a3,b3,c3)
那么我们知道，在三个细胞中，经过计算q3向量的特征值λ3比较小（这是因为q3向量的变化相当于q1向量和q2向量较小），所以对应只保留q1向量特征值λ1和q2向量特征值λ2，从而构建二维坐标，这样就完成了由三维降至二维

盗图传送门：传送门