812
个编辑
更改
跳到导航
跳到搜索
第633行：
第633行： − ==贪婪算法==+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
→聚合方法
=聚合方法=
=聚合方法=
当我们决定了最优的划分之后，就能根据该划分得到聚合后的矩阵了。
假设划分是把若干个状态合成一组，而其他状态各为一组，我们就是对原本的矩阵内，待聚合状态对应的若干行和若干列聚合成一行和一列，而其他元素则保持不动。
==入流的聚合方法：直接加和==
我们可以把马尔科夫链看做一个状态为节点，转移概率为边。
我们把待聚合节点都放进一个大节点的框<math>M</math>里，会发现每个外面的节点转移进这个大节点的概率就等于转移进这个框中所有节点的概率的和，即<math>p_{iM} = \sum_{j \in M} p_{ij}</math>。
所以，对入流（若干列）的聚类方法就是把这若干列直接加和，得到的列等于各节点转移到大节点的概率。
==出流的聚合方法：加权平均==
计算大节点的入流比较简单，而计算大节点的出流会相对较复杂，需要考虑待聚合节点之间的随机游走和状态分布，来计算流出到每个节点的概率。我们可以把出流的聚合看作是对若干行的加权平均。
===权重一致的平均===
在现有的方法中，大多采用最简单的思路：对状态进行权重一致的平均。当我们只看矩阵本身，认为所有的状态都是平等的，应该分配同等的权重，即<math>p_{Mj} = \frac{1}{n} \sum_{j \in M} p_{ji}</math>。
但是，这种情况只适用于成块的状态划分：由于成块性的同属于一组的微观状态转移到另一组的概率相同的性质，这样的平权平均是没有问题的。但是，当我们对不成块的状态划分进行平权平均时，就会导致宏观和微观的马尔科夫动力学不一致的情况。
===权重为平稳分布的平均===
当一个随机游走粒子进入到大节点时，它下一步游走到大节点里或大节点外的其他节点的概率时，应考虑其当前处于大节点内的哪个小节点的概率。
设游走粒子在 <math>t</math> 时刻处于小节点 <math>j</math> 的概率为<math>s_j(t)</math>，其下一步游走到其他粒子的概率应为<math>p_{Mj}(t) = \frac{1}{\sum_{j \in M} s_j(t)} \sum_{j \in M} s_j(t)\ p_{ji}</math> 。
假设游走已达到了平稳分布<math>\pi</math>，游走粒子处于不同小节点 <math>j</math> 的概率为<math>\pi_j</math>，所以其下一步游走到其他粒子的概率应为<math>p_{Mj} = \frac{1}{\sum_{j \in M} \pi_j} \sum_{j \in M} \pi_j\ p_{ji}</math>，而留在大节点的概率为<math>p_{MM} = \frac{1}{\sum_{j \in M} \pi_j} \sum_{j \in M} \pi_j \ p_{jj}</math> 。按照权重为平稳分布对若干行进行加权平均，得到的行仍会满足加和为一的条件。
按照该方法进行加和平均，得到的宏观和微观的马尔科夫动力学就会满足一致的条件。虽然该方法直观明了，该方法的问题在于其需要在系统演变到平稳分布前，计算每个 <math>t</math> 时刻的状态分布概率 <math>s_j(t)</math>。在达到平稳分布前直接使用<math>\pi</math>来聚合还是不会满足一致性，所以比较麻烦，而HOM的计算方式则可以解决这个问题。
===HOM===
==软分类方法：对冗余节点进行拆解==
=不同粗粒化方法之间的异同=
=不同粗粒化方法之间的异同=