812
个编辑
更改
跳到导航
跳到搜索
第588行：
第588行： − + + + + + + + + + + + + + + + + + + + + + + + + 第620行：
第643行： − − −
→划分方法
=划分方法=
=划分方法=
==贪婪算法==
当我们想把 <math>N</math> 个状态的马尔科夫链划分成 <math>M</math> 组时，待选的划分数量可以由 第二类斯特林数（Stirling numbers of the second kind）表示，<math>S(N, M) = \frac{1}{M!} \sum_{k=0}^{M} (-1)^{M-k} \binom{M}{k} k^N</math>
待选的划分数量极大，比如<math>S(20,10)=1.107e32</math>，几乎不可能通过遍历所有待选划分来寻找最优划分，所以，我们需要使用一些方法。
==逐层贪婪算法==
在这个问题中，我们可以采取 自底向上合并（Bottom-Up）的层次聚类（Hierarchical Clustering）方法，即从最细粒度（每个状态单独成组，一共 <math>N</math> 组）开始，每一步合并两个最相似的组，直到达到目标分组数 <math>M</math> 。
具体步骤如下：
# 初始化：每个状态单独成组，<math>A_0={{1},{2},…,{N}}</math>
# 在每一层 <math>k</math> 内：
## 遍历所有组对 <math>G_p</math> 和 <math>G_q</math>：
### 合并为新组 <math>G_{new} = G_p \cup G_q</math>
### 获得新划分 <math>=A_k \setminus \{ G_p , G_q \} \cup G_{new}</math>
### 根据此划分获得新动力学 <math>P'</math>
### 计算 <math>P'</math> 对应的划分指标
## 更新划分 <math>A_{k}</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>之间。
==谱分解==
==谱分解==
我们看到这两个目标函数非常相似。因此，我们可以通过上述算法或 k-Means 聚类来获取最优的状态划分，进而判断马尔科夫矩阵的成块性。
我们看到这两个目标函数非常相似。因此，我们可以通过上述算法或 k-Means 聚类来获取最优的状态划分，进而判断马尔科夫矩阵的成块性。
=聚合方法=
=聚合方法=