812
个编辑
更改
→划分方法
# 当剩余分组数 <math>|A_k| = M</math> 时停止
# 当剩余分组数 <math>|A_k| = M</math> 时停止
该算法的复杂度为 <math>O \left (\sum_{k=M}^N k^2 \right )</math>，介乎在<math>O \left ( N^2 \right )</math>和<math>O \left ( N^3 \right )</math>之间。
该算法的复杂度为 <math>O \left (\sum_{k=M}^N k^2 \right )</math>，介乎<math>O \left ( N^2 \right )</math>和<math>O \left ( N^3 \right )</math>之间。
==谱分解==
==谱分解==
谱分解（Spectral Clustering）的思想是利用矩阵的谱，即特征向量，所展示的物理含义进行聚类和划分。
===基于成块性的粗粒化方法（未给定成块的划分的情况）===
===基于成块性的粗粒化方法（未给定成块的划分的情况）===
当马尔科夫矩阵存在块状结构，或者状态明显可以被划分为几类时，根据这样的划分，该矩阵就是成块的。对于简单的<math>P</math>，如图6中的<math>\bar{P}</math>所示，我们能够很快的找出它的成块划分<math>\Phi</math>。然而，在实际应用中，我们经常遇到的矩阵可能并不完美。例如，成块的矩阵的状态排序可能被打乱（如图（6）中的<math>P_1</math>），或者矩阵包含了如<math>P_2</math>的噪声（如图6中的<math>P</math>，<math>P = P_1 + P_2</math>，<math>P_1^TP_2 = 0</math>）。在这种情况下，我们通常面临的是像<math>P</math>这样的矩阵。我们既无法确定它是否成块，也无法决定它的划分，甚至不知道它的马尔科夫秩。
[[文件:Lump fig1.png|缩略图|398x398像素|图6：Zhang<ref name=":4" /> 文章中的示意图。图中左面四个矩阵都是成块的马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0|替代=]]
[[文件:Lump fig1.png|缩略图|398x398像素|图6：Zhang<ref name=":4" /> 文章中的示意图。图中左面四个矩阵都是成块的马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0|替代=]]
针对这一问题，Anru Zhang<ref name=":4">Zhang, Anru, and Mengdi Wang. "Spectral state compression of markov processes." ''IEEE transactions on information theory'' 66.5 (2019): 3202-3231.</ref><ref name=":4" />提出了一种寻找最优划分的方法。通过这种方法，我们可以找到最优的划分，并基于这个划分判断一个马尔科夫矩阵是否成块。具体步骤如下：
针对这一问题，Anru Zhang<ref name=":4">Zhang, Anru, and Mengdi Wang. "Spectral state compression of markov processes." ''IEEE transactions on information theory'' 66.5 (2019): 3202-3231.</ref><ref name=":4" />提出了一种寻找最优划分的方法。通过这种方法，我们可以找到最优的划分，并基于这个划分判断一个马尔科夫矩阵是否成块。具体步骤如下：
我们看到这两个目标函数非常相似。因此，我们可以通过上述算法或 k-Means 聚类来获取最优的状态划分，进而判断马尔科夫矩阵的成块性。
我们看到这两个目标函数非常相似。因此，我们可以通过上述算法或 k-Means 聚类来获取最优的状态划分，进而判断马尔科夫矩阵的成块性。
论文<ref name=":4" />中并未提供使用右奇异向量向量进行聚类的物理原因，但提供了该算法的解与最优解的差距的上界。
<br/>
==基于可逆性的TPM矩阵的粗粒化方法==
动力学可逆性的文章<ref name="reversibility"/>提供了另一种基于奇异值分解的粗粒化方法，以获得宏观层面的简化TPM。其基本思想是将 <math>P</math> 中的行向量 <math>P_{i},\forall i \in [1,N]</math> 投影到 <math>P</math> 的几个较大奇异值对应的奇异向量所张成的子空间上，从而保留 <math>P</math> 的主要信息，并保持 <math>\Gamma</math> 不变。
跟上面的方法类似，该方法的基本思路是将P中的所有行向量 <math>P_{i}</math> 视为维数为 <math>N</math> 的数据向量。首先对这些行向量进行PCA降维，其次将其聚类为 <math>r</math> 个簇，其中 <math>r</math> 是根据奇异值谱的阈值<math>\epsilon</math>截取的。
'''1)''' 对P进行SVD分解（假设P是不可归约的，且具有周期性，从而存在平稳分布）：
<blockquote>
<math>P=U\cdot \Sigma \cdot V^{T},</math>
</blockquote>
其中，<math>U</math>和<math>V</math>是两个尺寸为N×N的正交归一化矩阵，<math>\Sigma = diag(\sigma_{1},\sigma_{2},...,\sigma_{N})</math> 是一个对角矩阵，包含所有有序奇异值。
'''2)'''选择一个<math>\epsilon</math>作为阈值来截断奇异值谱，并得到<math>r_{\epsilon}</math>作为保留状态的个数；
'''3)'''通过计算<math>\tilde{P}\equiv P\cdot V_{N\times r_{\epsilon}}</math>对P中的所有<math>P_{i}</math>进行降维，其中<math>V_{N\times r_{\epsilon}}</math>由<math>P\cdot P^{T}</math>的前<math>r_{\epsilon}</math>个特征向量构成；
'''4)''' 通过 K-means 算法将<math>\tilde{P}</math>中的所有行向量聚类为r组，得到投影矩阵<math>\Phi</math>，其定义为:
<blockquote>
<math>
\Phi_{ij} =\begin{cases}
1, & \text{如果}\tilde{P_{i}}\text{属于第r组}\\
0, & \text{其他情况}
\end{cases}</math>
</blockquote>
对<math>\forall i,j \in [1,N]</math>都成立。
=聚合方法=
=聚合方法=