3,094
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − [[马尔科夫链]]是一类特殊的随机过程，在给定当前状态下，对于未来状态的预测便不再依赖于过去状态。它可以看作一个n维的状态的序列<math>\{s^{(1)}, s^{(2)}, ... , s^{(t)}\}</math>，其中每一步的状态转换都有马尔科夫矩阵（满足每一行和为1的条件的方阵）<math>P</math>决定，即<math>p(s^{(t+1)}) = p(s^{(t)}) P</math>。 − Lumpability在[[马尔科夫链的粗粒化]]中是一种描述是否可聚类的性质，这个概念最早出现在Kemeny, Snell在1969年的Finite Markov Chains<ref name=":1">Kemeny, John G., and J. Laurie Snell. ''Finite markov chains''. Vol. 26. Princeton, NJ: van Nostrand, 1969. https://www.math.pku.edu.cn/teachers/yaoy/Fall2011/Kemeny-Snell_Chapter6.3-4.pdf</ref>中。Lump有‘块’的意思。我们会在正文中提到，判断一个马尔科夫链是否lumpable，是看它的马尔科夫状态转移矩阵这个大方块中的元素能不能结成一个个小方块。按照这些小方块进行聚类，虽然抹除了小方块内的状态的异质性，但是能够保留方块之间的状态转移机制。这样的划分有很好的性质，所以它是马尔科夫链聚类讨论中比较常见的一种情况。它保留了宏观层面上的最大预测性，而且保证了粗粒化前后的过程的一致性。 − − 集智百科编辑团队暂提供一个中文翻译为'''成块性'''，下文中的成块性就是指lumpability这个概念。 − − − − ==最初定义== − − 为了严谨的介绍这一定义，我们会详细翻译文章中的部分。'''不感兴趣的读者可以跳到更简洁直观的‘成块性的充分必要条件'部分。''' − − 首先定义马尔科夫链为一个n维的状态分布的序列<math>\{s^{(1)}, s^{(2)}, ... , s^{(t)}\}</math>，微观状态空间为<math>S=\{s_1, s_2, ... ,s_n\}</math>，下标代表了第几个状态，<math>s^{(t)}</math>表示系统在<math>t</math>时刻处于各微观状态的概率，<math>s^{(t)} = [ Pr(s(t) = s_1), Pr(s(t) = s_2), ... , Pr(s(t) = s_n) ]</math>。 − − 对于一个任意状态划分（state partition） <math>A=\{A_1, A_2, ... ,A_r\}</math>，我们也可以把其理解为宏观的状态空间。<math>S</math> 和 <math>A</math> 之间的硬性划分映射关系<math>\Phi:S \rightarrow A</math>为：<math>A_i \in S, A_i \neq \empty, A_i \cap A_j = \empty , \forall i, j, \cup_i A_i = S</math>。这种映射关系是指：<math>A</math>中的每个元素<math>A_i</math>都包括了若干个<math>s_i</math>；<math>A_i</math>和<math>A_j</math>之间没有交集，即每个<math>s_i</math>不会同时属于<math>A_i</math>和<math>A_j</math>；<math>S</math>中的每个元素必须属于某个<math>A</math>的元素，即<math>A</math>覆盖了<math>S</math>。 − − [[文件:Lumpable矩阵粗粒化示例.png|缩略图|500x500像素|图1：矩阵粗粒化示例]]在这里，我们考虑的是线性的马尔科夫过程的投影，所以<math>\Phi</math>是一个<math>n \times n</math>的投影矩阵。对于任意状态划分 <math>\Phi</math>，我们能够定义一个'''简化过程（lumped process）'''，即把微观的动力学轨迹<math>s^{(t)}</math>通过投影矩阵<math>\Phi</math>投影到<math>A</math>的空间上，<math>A^{(t)} = s^{(t)} \Phi</math>。 − − 比如，对于图中的马尔科夫链，我们有某条微观状态序列<math>\{ s^{(1)}, ..., s^{(6)} \} = \{ s_1, s_3, s_4, s_2, s_2, s_3 \}</math>，对于投影矩阵<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>，我们得到的投影后的宏观状态序列为<math>\{ A_1, A_2, A_2, A_1, A_1, A_2 \}</math> − − − − '''''定义1'''''：'''简化过程 lumped process''' − − '''简化过程（lumped process），是微观轨迹在宏观空间上的投影。投影后的轨迹<math>A^{(t)}</math>的状态转移概率可以写作下列公式：''' − − {{NumBlk|:| − <math> − Pr_{\pi}[s^{(0)} \in A_i] − </math> − |{{EquationRef|1.1}}}} − {{NumBlk|:| − <math> − Pr_{\pi}[s^{(1)} \in A_j | s^{(0)} \in A_i] − </math> − |{{EquationRef|1.2}}}} − {{NumBlk|:| − <math> − Pr_{\pi}[s^{(t)} \in A_m | s^{(t-1)} \in A_k, ... , s^{(1)} \in A_j, s^{(0)} \in A_i] − </math> − |{{EquationRef|1.3}}}} − − '''其中，<math> \pi </math>为初始微观状态。''' − − 这些公式描述了： − − # 式子1.1：系统在<math>t=0</math>的微观状态<math>s^{(0)}</math>属于某个宏观状态<math>A_i</math>的概率； − # 式子1.2：已知在<math>t=0</math>的微观状态<math>s^{(0)}</math>属于某个宏观状态<math>A_i</math>，那么在时间<math>t=1</math>的微观状态<math>s^{(1)}</math>属于某个宏观状态<math>A_j</math>的概率； − # 式子1.3：已知历史微观状态<math>\{s^{(0)}, ... , s^{(t-1)} \}</math>对应的宏观状态，那么在时间<math>t</math>的微观状态<math>s^{(t)}</math>属于某个宏观状态<math>A_m</math>的概率； − − 我们看到从<math>s^{(t)}</math>到<math>A^{(t+1)}</math>存在微观状态->微观动力学->粗粒化->宏观状态 的这一条路径（细心的读者可能会发现在图中还有另一条路径，我们会在后面讨论）。我们现在有了微观动力学<math>\{s^{(0)}, ... , s^{(t-1)} \}</math>，也有了微观到宏观的粗粒化过程<math>A</math>。所以式子（1）描述的简化过程正是先走微观动力学再聚合的这条路径的<math>A^{(t)}</math>。它描述了我们从任意一个初始状态<math>s^{(0)}</math>（或状态分布<math>\pi</math>），一直走微观动力学，然后在<math>t</math>时刻做粗粒化得到<math>A^{(t)}</math>的过程。 − − 需要注意的是，虽然任意一个状态划分 <math>A</math>都能走这样的路径，并形成简化过程，'''但不是所有的这些简化过程都符合实际意义的。'''他们不一定能够得出一个宏观动力学来描述式子（1）中微观状态的宏观投影，例如图（2）中的第二个例子，也'''不一定会拥有马尔科夫性。''' − − 我们暂且先不考虑‘失败’的情况，先关注‘成功’的部分。书中接下来就定义了什么叫做成块的划分： − − − − '''''定义2'''''：'''成块的划分 lumpable partition''' − − '''对于一个给定的状态 <math>A</math>，当下列两个条件都满足时，<math>A</math>是一个成块划分（lumpable partition）。''' − − '''1. 定义1中式子(1)描述的简化过程具有马尔科夫性，即式子(1.3)可写成'''{{NumBlk|:|<math>Pr_{\pi} \left [s^{(t)} \in A_m | s^{(t-1)} \in A_k, ... , s^{(1)} \in A_j, s^{(0)} \in A_i \right ] = Pr_{\pi} \left [s^{(t)} \in A_m | s^{(t-1)} \in A_k \right ]</math>|{{EquationRef|2}}}} − − '''2. 转移概率(transition probability)，即式子(1.3)（或式子(2)），对任何微观初始状态(starting vector) <math> \pi </math> 都保持一致，从而我们能够得出宏观的概率转移矩阵<math>P' = \Phi^T P (\Phi^T)^{-1} = \Phi^T P \Phi^{\dagger} = \Phi^T P \Phi (\Phi^T \Phi)^{-1}</math>''' − − 其中，因为<math>\Phi</math>不是方阵，我们定义<math>\Phi^{\dagger}</math>为<math>\Phi</math>的伪逆矩阵，满足<math>\Phi \Phi^{\dagger} \Phi = \Phi</math>。另外，<math>\Phi^T \Phi</math>是一个对角阵，对角线上的元素为每个<math>A_i</math>包括了多少个微观状态的计数，而它的逆矩阵就是把对角线上的元素全部取倒数。 − − − − [[文件:Lumpable和non-lumpable的例子.png|缩略图|图2：对成块的和不成块的矩阵做粗粒化|替代=|600x600像素]]不满足上述两个条件的，都不被定义为成块的划分。也就是说，不是所有的简化过程都是成块的，即使他们的命名方式（lumpable process v.s. lumped process）相似。 − − 从图（2）的成块划分的例子中，我们看到对于分组矩阵<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>，成块的动力学TPM可以找到一个简化过程，而这个简化过程是满足马尔可夫性，且对所有初始状态都保持一致的。也就是说，无论<math>s^{(t)}</math>是什么，<math>\{ s^{(t)}, s^{(t+1)} \}</math>投影到宏观空间上的<math>\{ A^{(t)}, A^{(t+1)} \}</math>的<math> P( A^{(t+1)} | A^{(t)} )</math>都保持一致。 − − − − 对于例子中的不成块的矩阵，我们或许可以给它强制定义一个简化过程的TPM，比如<math> P_1' = \left ( \begin{array}{cc} 0.6 & 0.4 \\ 0.2 & 0.8 \\ \end{array} \right )</math>，但这个简化过程并不能对任何微观初始状态保持一致，只能对<math>s^{(t)} = \pi = \left [ \begin{array}{cc}1 & 0 & 0 & 0 \end{array} \right ]</math>适用。而<math>s^{(t)} = \pi = \left [ \begin{array}{cc}0 & 1 & 0 & 0 \end{array} \right ]</math>不适用这个简化过程。它适用的是<math> P_2' = \left ( \begin{array}{cc} 0.5 & 0.5 \\ 0.2 & 0.8 \\ \end{array} \right )</math>。这里的不适用是指，这个简化过程不能描述这个<math>\pi</math>为初始状态出发的微观状态序列投影的宏观状态序列。我们看到，对于这个分组矩阵<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>，马尔科夫矩阵有两个简化过程 <math> P_1'</math>和<math> P_2'</math>，而它们各自只适用于一些微观初始状态(starting vector) <math> \pi </math>，并不满足定义2中的条件，所以<math>A</math>对于这个TPM来说不是一个成块的划分。事实上，这个TPM只存在一个成块的划分，就是不做任何的分组，所以它无法按照成块性的定义进行粗粒化。在后面“成块性概念的变种”的部分，我们会提到，虽然对这个TPM做的划分不符合（强）成块性的要求，但是它实际上满足弱成块性 Weak Lumpability，即简化过程对部分微观初始状态使用。 − − − − ==成块性的充分必要条件== − − 通过上面的例子，我们可以对成块性有一些直观的理解。我们可以留意到，在成块的划分中，有两个分组，所以有四个框。每一个框里，每一列相加的和都是一样的，比如左上角的框中，<math>0.3 + 0.3 = 0.2 + 0.4</math>。这就是成块性更通俗的解释，就是它'''成块'''了，在某些文献中，并不会使用上面提及的定义，而是直接使用这个通俗版的解释，而且这两者之间是存在充分必要条件关系的<ref name=":1" />。设<math>p_{s_k \rightarrow s_m} = p(s^{(t)} = s_m | s^{(t-1)} = s_k)</math>，<math>p_{s_k \rightarrow A_i} = p(s^{(t)} \in A_i | s^{(t-1)} = s_k) = \sum_{s_m \in A_i} p_{s_k \rightarrow s_m}</math>，<math>p_{A_i \rightarrow A_j} = p(A^{(t)} = A_j | A^{(t-1)} = A_i)</math>，作者<ref name=":1" />提出了判断一个马尔科夫链对'''给定划分 <math>A</math>''' 是否成块的充分必要条件为： − − '''''定理1：''''' − − '''给定划分 <math>A</math>是成块的充分必要条件为：''' − − '''对于任意一对<math>A_i, A_j</math>，每一个属于<math>A_i</math>的状态<math>s_k</math>的<math>p_{s_k \rightarrow A_j}</math>都是一样的。或者说，<math>A_i</math>里的每一个状态<math>s_k</math>转移到<math>A_j</math>中所有状态的转移概率的加总都是一样的。''' − − {{NumBlk|:| − <math> − \forall i, j, \forall s_k, s_m \in A_i, p_{s_k \rightarrow A_j} = p_{s_m \rightarrow A_j} − </math> − |{{EquationRef|3}}}} − − 符合了这个条件后，我们才能把<math>A_j</math>中的所有微观状态<math>s_l</math>状态合成一个宏观状态<math>A_j</math>，因为它从其他宏观状态的转入概率是一致的。同样的，我们也能把<math>A_i</math>中的所有微观状态<math>s_k</math>状态合成一个宏观状态<math>A_i</math>，因为这些微观状态<math>s_k</math>（和<math>A_i</math>）到其他宏观状态的转出概率是一致的。 − − 在下面的例子中，我们看到，同属于<math>A_1</math>的<math>s_1</math>和<math>s_2</math>到<math>A_1</math>和<math>A_1</math>的转移概率是一样的，而同样的，同属于<math>A_2</math>的<math>s_3</math>和<math>s_4</math>到宏观状态的概率也是一样的。所以，<math>[[1,2], [3, 4]]</math>对<math>P</math>来说就是一个成块的划分。 − − [[文件:成块性充分必要条件.png|居中|700像素|成块性充分必要条件实例]] − − − 顺着这个条件，我们也能对成块的划分，定义宏观动力学<math>A^{(t)} = A^{(t-1)} P'</math>了： − − '''''定义3'''''：'''成块性的宏观动力学''' − − '''对于给定的微观状态<math>S</math>，微观动力学<math>p_{s_k \rightarrow s_m}</math>和成块的划分 <math>A</math>，宏观动力学<math>p_{A_i \rightarrow A_j}</math>等于<math>A_i</math>中任意状态<math>s_k</math>到<math>A_j</math>的概率：''' − − {{NumBlk|:| − <math> − \begin{aligned} − p_{A_i \rightarrow A_j} = p_{s_k \rightarrow A_j} = \sum_{s_m \in A_j} p_{s_k \rightarrow s_m}, k \in A_i − \end{aligned} − </math> − |{{EquationRef|4}}}} − − 这个公式表达的是，群组<math>A_i</math>到群组<math>A_j</math>的转移概率 = 群组<math>A_i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>的转移概率 = 群组<math>A_i</math>中任意状态<math>s_k</math>到群组<math>A_j</math>中的所有状态的转移概率的和。 − − 我们也可以直接定义<math>P</math>和<math>P'</math>之间的关系： − − <math>P' = \Phi^T P (\Phi^T)^{-1} = \Phi^T P \Phi (\Phi^T \Phi)^{-1}</math>， − − 其中，<math>\Phi^T \Phi</math>是一个对角阵，对角线上的元素为每个<math>A_i</math>包括了多少个微观状态的计数，而它的逆矩阵就是把对角线上的元素全部取倒数。 − − − − 根据成块划分 <math>\Phi</math>定义好宏观动力学后，我们就能走另外一条路径了：'''微观状态->粗粒化->宏观动力学->宏观状态'''。我们发现这和'''微观状态->微观动力学->粗粒化->宏观状态'''这两条路径，'''从任意一个微观状态出发，都能到达相同的宏观状态。'''所以，这满足了'''动力学'''和'''粗粒化'''这两个'''算子'''的'''可交换性（Exchangeability）'''。具体的证明我们会在后面的‘成块性满足的性质’部分介绍。 − − − − 这里，我们翻译了作者在书<ref name=":1" />中提供的定理1的必要性和成块性证明。 − − '''必要性部分的证明：''' − − 必要性是指，如果一个马尔可夫链的划分 <math>A</math>是成块的，那么就肯定会满足上述的这个特定条件。 − − 从成块的划分的定义可知，<math>A</math>的转移概率满足宏观马尔可夫性，且这个转移概率<math>Pr_{\pi} [ s^{(1)} \in A_j | s^{(0)} \in A_i ]</math>对每个<math>\pi</math>保持一致，即在<math>t=0</math>时无论从哪个具体的初始状态<math>\pi</math>开始，只要它属于<math>A_i</math>这个群组里，在<math>t=1</math>时刻转移到<math>A_j</math>的概率都相同。 − − 我们设这个（<math>A_i</math>中任意微观状态<math>s_k</math>的）共同的转移概率为<math>\hat{p}_{A_i \rightarrow A_j}</math>。当初始状态<math>\pi</math>属于某个<math>A_i</math>时（<math>\pi \in A_i</math>），<math>p_{s_k \rightarrow A_j} = Pr_{\pi \in A_i} [ s^{(1)} \in A_j ] = \hat{p}_{A_i \rightarrow A_j}</math>。 − − 所以，这说明了，如果一个马尔可夫链的简化过程满足成块性，那么从任一集合到另一集合的转移概率必须是集合间的固定值，而与集合内的具体状态（不管是<math>\pi</math>还是<math>s_k</math>）无关。这个固定值就是式子（4）定义的宏观状态转移概率，所以满足了该条件。 − − '''充分性部分的证明：''' − − 充分性是指，如果一个马尔可夫链的某个状态划分 <math>A</math>满足这个条件，那么它就是成块的。我们要证明的是，如果上述条件满足，那么马尔可夫性成立，即对于任何给定的<math>t</math>，转移概率<math>Pr \left [ s^{(t)} \in A_j | s^{(t-1)} \in A_i, \ldots, s^{(1)} \in A_k, s^{(0)} \in A_m \right ]</math>只依赖于<math>A_i</math>和<math>A_j</math>，而不依赖于<math>A_i</math>中的具体状态或是<math>t-1</math>前的宏观状态。 − − 条件要求所有<math>s_k \in A_i</math>，转移概率<math>p_{s_k \rightarrow A_j} = p_{A_i \rightarrow A_j}</math>，这意味着无论我们从<math>A_i</math>中的哪个微观状态转移过来，转移到<math>A_j</math>的概率都是相同的。 − − 因此，当我们知道<math>t-1</math>的宏观状态是<math>A_i</math>时，我们计算<math>t</math>时刻转移到<math>A_j</math>的概率时，只需要用<math>p_{A_i \rightarrow A_j}</math>，而不需要关心<math>A_i</math>中的具体状态。 − − 由于转移概率只依赖于群组<math>A_i</math>和<math>A_j</math>，而不依赖于<math>A_i</math>中的具体状态，因此我们可以将<math>A_i</math>中的所有状态合并为一个状态，并且这个合并后的链仍满足马尔可夫性。所以，上述条件为成块性的充分条件。 − − − − 从这两个证明里，我们也能看到微观动力学的路径和宏观动力学的路径的一致性。无论我们从<math>A_i</math>中的哪个具体状态<math>s^{(t-1)}</math>开始，只要我们知道当前的宏观状态是<math>A_i</math>，我们就可以计算下一步转移到<math>A_j</math>的概率，而不依赖于<math>s^{(t-1)}</math>。这表明，微观<math>s^{(t-1)}</math>->宏观<math>A^{(t-1)}</math>->宏观动力学-><math>A^{(t)}</math>不会影响未来状态的预测，因此从<math>s^{(t-1)}</math>出发的两个路径得出的<math>A^{(t)}</math>的概率是一致的。 − − − − '''请注意'''：成块性有一个非常重要的前提，即我们要给定一个对马尔科夫链的状态的划分，然后根据马尔科夫状态转移矩阵来决定这个划分对这个马尔科夫链是否成块的。 − − 所以，成块性并不是一个马尔科夫链的特质，而是对马尔科夫链的某个状态划分的特质。直接说某个马尔科夫链是成块的或是不成块的是不严谨的，但是我们可以说，对于某个马尔科夫链的某个状态划分是成块或不成块的。但是，通常为了简略表达，当我们说某个马尔科夫链成块时，我们表达的是它存在某种成块的状态划分。 − − ==成块性的正例和反例== − − 对于一个马尔科夫链，有些分组是成块的，有些分组是不成块的。这里用一个简单的例子提供正例和反例。 − − 我们用到的是这样一个转移矩阵： − − <math> − \begin{aligned} − P = P_{s_i \rightarrow s_j} = \left [ − \begin{array}{ccc:c} − 0.3 & 0.3 & 0.3 & 0.1 \\ − 0.3 & 0.3 & 0.3 & 0.1 \\ − 0.3 & 0.3 & 0.3 & 0.1 \\ − \hdashline0.1 & 0.1 & 0.1 & 0.7 − \end{array} − \right ] − \end{aligned} − </math> − − ====正例==== − − 我们可以看到，123行都是一样的，所以把他们<math>\{s_1, s_2, s_3\}</math>分在一组<math>A_1</math>，并把状态<math>s_4</math>分在另外一组<math>A_2</math>，看起来像是一个合理的正例。接下来我们来计算一下。 − − 第1组<math>A_1</math>的状态<math>s_1</math>到第1组<math>A_1</math>，<math>p_{s_1 \rightarrow A_1} = p_{A_1 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_1 \rightarrow s_m} = p_{s_1 \rightarrow s_1} + p_{s_1 \rightarrow s_2} + p_{s_1 \rightarrow s_3} = 0.3 \times 3 = 0.9 </math> − − 第1组<math>A_1</math>的状态<math>s_1</math>到第2组<math>A_2</math>，<math>p_{s_1 \rightarrow A_2} = p_{A_1 \rightarrow A_2} = \sum_{s_m \in A_2} p_{s_1 \rightarrow s_m} = p_{s_1 \rightarrow s_4} = 0.1 </math> − − 第2组<math>A_2</math>的状态<math>s_4</math>到第1组<math>A_1</math>，<math>p_{s_4 \rightarrow A_1} = p_{A_2 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_4 \rightarrow s_m} = p_{s_4 \rightarrow s_1} + p_{s_4 \rightarrow s_2} + p_{s_4 \rightarrow s_3} = 0.1 \times 3 = 0.3 </math> − − 第2组<math>A_2</math>的状态<math>s_4</math>到第2组<math>A_2</math>，<math>p_{s_4 \rightarrow A_2} = p_{A_2 \rightarrow A_2} = \sum_{s_m \in A_2} p_{s_4 \rightarrow s_m} = p_{s_4 \rightarrow s_4} = 0.7 </math> − − <math> − \begin{aligned} − P = P_{A_k \rightarrow A_l} = \left [ − \begin{array}{c:c} − 0.9 & 0.1 \\ − \hdashline0.3 & 0.7 − \end{array} − \right ] − \end{aligned} − </math> − − − − ====反例==== − − 现在我们来看一个反例：把状态12分为一组，状态34分为另一组。同样的，我们来计算一下。这次我们需要对3和4分开计算了。 − − 第1组<math>A_1</math>的状态<math>s_1</math>到第1组<math>A_1</math>，<math>p_{s_1 \rightarrow A_1} = p_{A_1 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_1 \rightarrow s_m} = p_{s_1 \rightarrow s_1} + p_{s_1 \rightarrow s_2} = 0.3 \times 2 = 0.6 </math> − − 第1组<math>A_1</math>的状态<math>s_1</math>到第2组<math>A_2</math>，<math>p_{s_1 \rightarrow A_2} = p_{A_1 \rightarrow A_2} = \sum_{s_m \in A_2} p_{s_1 \rightarrow s_m} = p_{s_1 \rightarrow s_3} + p_{s_1 \rightarrow s_4} = 0.4 </math> − − 第2组<math>A_2</math>的状态<math>s_3</math>到第1组<math>A_1</math>，<math>p_{s_3 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_3 \rightarrow s_m} = p_{s_3 \rightarrow s_1} + p_{s_3 \rightarrow s_2} = 0.3 \times 2 = 0.6 </math> − − 第2组<math>A_2</math>的状态<math>s_4</math>到第1组<math>A_1</math>，<math>p_{s_4 \rightarrow A_1} = \sum_{s_m \in A_1} p_{s_4 \rightarrow s_m} = p_{s_4 \rightarrow s_1} + p_{s_4 \rightarrow s_2} = 0.1 \times 2 = 0.2 </math> − − 这里我们就能看到，<math>p_{s_3 \rightarrow A_1} \neq p_{s_4 \rightarrow A_1}</math>，当同一组的两个状态<math>s_3</math>和<math>s_4</math>对其他组的转移概率不一样的话，如果我们强行按照这样来分组（也没办法强行，因为我们不知道<math>p_{A_2 \rightarrow A_1} = p_{s_3 \rightarrow A_1}</math>还是<math>p_{A_2 \rightarrow A_1} = p_{s_4 \rightarrow A_1}</math>），假设<math>p_{A_2 \rightarrow A_1} = 0.6</math>，我们会发现这样的粗粒化结果违背了成块性一开始的定义<ref name=":1" />（公式(1)），即粗粒化后的'''转移概率对所有的初始微观状态<math>\pi</math>都适用'''。因为当<math>\pi = s_4</math>的时候，<math>p_{A_2 \rightarrow A_1} = 0.6</math>这个转移概率就是错的，即使<math>\pi \neq s_4</math>，任何初始微观状态<math>\pi</math>都会在某时刻<math>n</math>达到<math>s_4</math>并导致转移概率出错。 − − − − ====一个更复杂的正例==== − − 三个相同状态的例子可能稍微有点简单，接下来我们来看一个稍微复杂一点的例子： − − <math> − \begin{aligned} − P = P_{s_i \rightarrow s_j} = \left [ − \begin{array}{cc:cc} − 0.2 & 0.4 & 0.3 & 0.1 \\ − 0.4 & 0.2 & 0.1 & 0.3 \\ − \hdashline0.2 & 0.1 & 0.2 & 0.5 \\ − 0.1 & 0.2 & 0 & 0.7 − \end{array} − \right ] − \end{aligned} − </math> − − 对于这个马尔科夫矩阵，<math>\{\{1,2\}, \{3,4\}\}</math>是一个成块的分组。分组后的转移矩阵为： − <math> − \begin{aligned} − P = P_{A_k \rightarrow A_l} = \left [ − \begin{array}{c:c} − 0.6 & 0.4 \\ − \hdashline0.3 & 0.7 − \end{array} − \right ] − \end{aligned} − </math> − − − − ==成块性满足的性质== − − 在[[马尔科夫链的粗粒化]]过程中，我们有很多目标。 − #首先，我们想尽量降低压缩后的动力学维度； − #其次，我们想在压缩过程中尽量保留动力学中有用的信息； − #最后，我们想要压缩后的过程和原本的过程尽量保持一致。 − − 其中，比较直观的是，压缩的维度越多，能保留的信息就越少，压缩前后的动力学就会越难保持一致。而成块性相对来说是一个比较严格的划分要求，所以我们能看到，按照成块性来做动力学粗粒化能压缩的维度并不多，但是它能保留在宏观层面上所有有用的信息，而且保证了粗粒化前后的过程的一致性。 − − ===宏观最大预测性=== − − 宏观最大预测性是指，当我们把某一个时刻的微观状态粗粒化成宏观状态后，我们就不再需要微观状态来预测后续的宏观状态。 − − 我们只需要知道<math>A^{(t)}</math>就可以最大化<math>A^{(t+1)}</math>的预测效果，而<math>s^{(t+1)}</math>虽然能提供一些额外的信息，但是对于预测<math>A^{(t+1)}</math>不会有任何帮助。也就是说，条件互信息<math>I(A^{(t+1)}; s^{(t+1)} | A^{(t)}) = 0</math>。这意味着，宏观动力学不需要任何来自微观状态的修正，就能独立且正确的反映系统。 − − 虽然成块性划分能够准确预测宏观动力学，但它无法确保像[[计算力学]]中因果态那样的微观最大预测性，因为它在聚类过程中会损失微观状态的信息，使得我们无法辨别某个<math>A^{(t)}</math>具体是哪个微观态<math>s^{(t)}</math>。而且，这个信息的损失是不可逆的，所以从微观粗粒化到宏观之后，就无法再还原到微观了。 − − − − ===成块划分和粗粒化的可交换性=== − − [[文件:马尔科夫链的粗粒化定义.png|替代=|缩略图|图3：粗粒化图例]] − − 图3展示了从某个微观状态<math>s^{(t)}</math>出发，到达下一刻的宏观状态<math>A^{(t+1)}</math>的两条路径<ref name=":7">Coarse graining. ''Encyclopedia of Mathematics.'' URL: <nowiki>http://encyclopediaofmath.org/index.php?title=Coarse_graining&oldid=16170</nowiki></ref>： − #先进过微观动力学达到<math>s^{(t+1)}</math>，再做粗粒化得到<math>A^{(t+1)}</math> − #先做粗粒化得到<math>A^{(t)}</math>，再经过宏观动力学到达<math>A^{(t+1)}</math> − − 如果我们分别把粗粒化和（宏观/微观）动力学看作是两个算子，那这两个算子的可交换性是指，无论从哪个微观状态分布出发，我们走两条路径得到的<math>A^{(t+1)}</math>的分布是一样的，也就是说，'''<math>s^{(t)} \Phi P' = s^{(t)} P \Phi</math>'''。 − − 证明如下： − − 对于一个成块的<math>P</math>，和它的成块划分<math>\Phi</math>，我们针对<math>\Phi = \left ( \begin{array}{cc} 1 & 0 \\ 0 & 1 \\ 0 & 1 \\ 0 & 1 \end{array} \right )</math>的例子，但所有其他的例子都一样的。 − − 对于这个<math>\Phi</math>，我们知道<math>P_{11}=A_{11}</math>，<math>P_{12}+P_{13}+P_{14}=A_{12}</math>，<math>P_{21}=P_{31}=P_{41}=A_{21}</math>，<math>P_{22}+P_{23}+P_{24}=P_{32}+P_{33}+P_{34}=P_{42}+P_{43}+P_{44}=A_{22}</math>。 − − 正因为<math>A_{21}</math>和<math>A_{22}</math>的等于关系，<math>P \Phi = \left ( \begin{array}{cc} P_{11}' & P_{12}' \\ P_{21}' & P_{22}' \\ P_{21}' & P_{22}' \\ P_{21}' & P_{22}' \end{array} \right )</math>。它相当于把<math>P</math>的每一行按照划分来进行加总，而<math>P \Phi</math>内同一组的行是一样的。 − − 而<math>\Phi P'</math>的意思是把<math>P'</math>的每一行按照<math>\Phi</math>抄写到对应的微观状态的行中，所以，我们会发现<math>\Phi P'</math>和<math>P \Phi</math>的结果是一样的。 − − − − ===一致性Consistency=== − − 这一小节里我们讨论一下，对一个马尔科夫链的成块的划分 与 HOM（Higher-order Macronodes，详情请参考[[复杂网络中的因果涌现]]），和Consistency之间的关联。 − − Higher-order Macronodes，是由Jian Xu<ref name=":3">J. Xu, T. L. Wickramarathne, and N. V. Chawla， 'Representing higher-order dependencies in networks,' Science Advances, vol. 2, Article ID el600028, 2016.a</ref>提出，根据给定的微观马尔科夫链和节点的聚类方案，得出一个和微观转移矩阵保持一致的宏观转移矩阵的方法。 − − 我们这里使用一个简单的成块的划分的例子，来显示成块性的粗粒化跟HOM是对应的。 − − [[文件:Lumpability例子示意图.png|缩略图|图4：例子示意图|替代=]] − − <math> − \begin{aligned} − P = P_{s_i \rightarrow s_j} = \left [ − \begin{array}{c:c:cc:c:c} − 0 & 0 & 0.3 & 0.1 & 0.6 & 0\\ − \hdashline − 0 & 0 & 0.2 & 0.3 & 0 & 0.5\\ − \hdashline − 0 & 0 & 0 & 0.7 & 0.2 & 0.1\\ − 0 & 0 & 0.7 & 0 & 0.2 & 0.1\\ − \hdashline − 1.0 & 0 & 0 & 0 & 0 & 0\\ − \hdashline − 0 & 1.0 & 0 & 0 & 0 & 0\\ − \end{array} − \right ] − \end{aligned} − </math> − − 对于这个转移概率矩阵，<math>\{1, 2, \{34\}, 5, 6\}</math>是一个成块的划分。 − − − − 首先，我们先按照成块性的粗粒化定义，计算对应的宏观转移概率： − <math> − \begin{aligned} − \left [ − \begin{array}{c:c:c:c:c} − 0 & 0 & 0.4 & 0.6 & 0\\ − \hdashline − 0 & 0 & 0.5 & 0 & 0.5\\ − \hdashline − 0 & 0 & 0.7 & 0.2 & 0.1\\ − \hdashline − 1.0 & 0 & 0 & 0 & 0\\ − \hdashline − 0 & 1.0 & 0 & 0 & 0\\ − \end{array} − \right ] − \end{aligned} − </math> − − − − [[文件:HOM示例.png|411x411像素|缩略图|图5：HOM节点边权合并示意图|替代=]] − − 然后，我们来简单介绍一下的[[网络归并]]构建宏观HOM转移概率矩阵的计算方法。 − − 在图4中，我们把3和4看作是待合并节点<math>A</math>。 − − 1. 对于其他节点到待合并节点<math>A</math>的连边，即待合并节点的入流（图4中绿色的连边），我们直接加和即可，即<math>p_{s_1 \rightarrow A} = 0.3+0.1=0.4</math>，<math>p_{ s_2 \rightarrow A} = 0.2+0.3=0.5</math> − − 2. 对于待合并节点<math>A</math>到其他节点的连边，即待合并节点的出流（图4中棕色的连边），我们需要考虑三种情况： − #当待合并节点<math>A</math>间存在连边时； − #当待合并节点<math>A</math>指向同一个输出节点时； − #当待合并节点<math>A</math>指向不同输出节点时； − − 待合并节点<math>A</math>的出流的计算方式都不一样，如图5所示。 − − '''但是'''，我们可以注意到，这三种计算方式都是待合并节点<math>A</math>中的各节点的出流的<math>W_i^{out}</math>加权，而我们知道，成块性的特性决定了，群组里的各节点到其他群组的出流<math>W_i^{out}</math>都是一样的，对相同的<math>W_i^{out}</math>做任意加权平均的结果都等于<math>W_i^{out}</math>。也就是说，任意的加权方法对于成块的划分来说都能得出相同的结果。 − − 由此，我们总结，'''成块性的聚合方式和HOM的计算方式，无论入流还是出流都完全一致。''' − − − − 我们得出这个结论的目标是，借助HOM方法的一致性的性质，说明成块性的聚合方式，也有一致性的性质。 − − 以下关于[[动力学的一致性检验]]的描述节选自[[复杂网络中的因果涌现]]： − − 定义微观网络<math>G </math>与宏观网络<math>G_M </math>，在两个网络上[[随机游走]]，在未来某个时间<math>t </math> ， <math>G </math>上的预期分布为 <math>P_m(t) </math>， <math>G_M </math>上的预期分布为 <math>P_M(t) </math>。 − − 将<math>P_m(t) </math>分布叠加到宏观上<math>G_M </math>的相同节点上，得到<math>P_{M|m}(t) </math>分布。用<math>P_M(t) </math>和<math>P_{M|m}(t) </math>之间的KL散度来衡量其不一致性（inconsistency），若结果为零则动力学一致。公式为： − − <math>inconsistency=\sum_{t=0}^T D_{KL}[P_M(t)||P_{M|m}(t)]</math> − − 也就是说，Inconsistency 等于 宏观和微观网络节点在不同时刻的概率分布的[[KL散度]]之和。 − − 实验发现，对不同节点规模以及参数下的微观网络，使用HOM粗粒化后的宏观网络的不一致性随着迭代步数的增加都会收敛到0。这说明，HOM构建的宏观网络和微观网络是保持一致的。 − − 回到上面基于成块划分做的粗粒化过程与HOM等价的推断，我们就能得出，'''根据成块性而做的粗粒化，构建的宏观网络和微观网络也是保持一致的。''' − − <br/> − − ==成块性概念的变种== − − 我们不难发现，成块性虽然满足了非常多很好的特性，但是同时，它是一个非常严格的矩阵。在现实情况中，如果不允许一定的误差的话，我们几乎非常难获取到成块的划分，从而难以对马尔科夫链进行划分。 − − 所以，成块性衍生出了很多变种的概念，一共6个。根据变种的成块性中较宽松的限制，我们能够得到更有效的划分，并研究这些划分在多大程度上保留了宏观最大预测性、可交换性、一致性等性质。 − − ===强成块性 Strong/Ordinary Lumpability=== − − 强成块性（Strong lumpability） 或 ordinary lumpability 是上面所述的成块性的原本概念，是这六个变种中约束最强的一种。它要求矩阵具有严格的分块性。 − − 这里的'Strong'是与下面的'weak'相对的概念，指上文的简化过程满足对任意初始状态分布都保持一致的条件。 − − 简单的例子： − − <math> − \begin{aligned} − P = P_{s_i \rightarrow s_j} = \left [ − \begin{array}{cc:cc} − 0.2 & 0.4 & 0.3 & 0.1 \\ − 0.4 & 0.2 & 0.1 & 0.3 \\ − \hdashline0.2 & 0.1 & 0.2 & 0.5 \\ − 0.1 & 0.2 & 0 & 0.7 − \end{array} − \right ] − \end{aligned} − </math> − − 此例子中，<math>[[1, 2], [3, 4]]</math>是一个强成块的分组。 − − − − ===弱成块性 Weak Lumpability=== − − 弱成块性（weak lumpability）<ref name=":3" />是指简化过程不对所有的初始状态满足，而仅对某些初始状态满足。 − − 一个简单的例子是，某个状态<math>s_i</math>到<math>s_j</math>不联通的，而简化过程适用于<math>s_i</math>但不适用于<math>s_j</math>。所以，当初始状态等于<math>s_i</math>时，因为永远不会到达<math>s_j</math>，所以简化过程会一直适用。 − − 简单的例子： − − <math> − \begin{aligned} − P = P_{s_i \rightarrow s_j} = \left [ − \begin{array}{cc:cc} − 0.6 & 0.4 & 0.0 & 0.0 \\ − 0.3 & 0.7 & 0.0 & 0.0 \\ − \hdashline − 0.2 & 0.1 & 0.2 & 0.5 \\ − 0.6 & 0.1 & 0.1 & 0.1 − \end{array} − \right ] − \end{aligned} − </math> − − 此例子中，<math>[[1, 2], [3], [4]]</math>是一个强成块的分组，而<math>[[1, 2], [3, 4]]</math>是一个弱成块的分组, − − − ===精确成块 Exact Lumpability=== − − 强成块的<math>P</math>的分组内每一行的加总是一样的，也就是说，同一组中的每个状态到另一个分组的转出概率是相同的。 − − 而在精确成块性（exact lumpability）中，<math>P</math>分组内的每一列的加总是一样的，也就是说，同一组中的每个状态从另一个分组的转入概率是相同的。 − − 在<ref name=":2">Buchholz, Peter. "Exact and ordinary lumpability in finite Markov chains." ''Journal of applied probability'' 31.1 (1994): 59-75.</ref>中给出的正式定义是，<math>P</math>的'''转置'''经过'''行归一化'''是强成块的。 − − 另外，<ref name=":2"/>说明了精确成块的<math>P</math>也是弱成块的。 − − − − 在强成块性的例子中，<math>[[1, 2], [3, 4]]</math>是一个强成块的分组，但不是一个精确成块的分组。 − − 我们再举一个例子： − − <math> − \begin{aligned} − P = P_{s_i \rightarrow s_j} = \left [ − \begin{array}{cc:cc} − 0.1 & 0.1 & 0.4 & 0.4 \\ − 0.4 & 0.4 & 0.1 & 0.1 \\ − \hdashline − 0.3 & 0.3 & 0.2 & 0.2 \\ − 0.2 & 0.2 & 0.3 & 0.3 − \end{array} − \right ] − \end{aligned} − </math> − − − 此例子中，<math>[[1, 2], [3, 4]]</math>不是一个强成块的分组，但是一个精确成块的分组, − − − − ===严格成块性 Strict Lumpability=== − − 严格成块性（strict lumpability）<ref name=":2"/>是指一个马尔可夫链同时满足强成块性和精确成块性。也就是说，同一组中的每个状态不仅从另一个分组的转入概率相等，而且到另一个分组的转出概率也相等。 − − 简单的例子： − − <math> − \begin{aligned} − P = P_{s_i \rightarrow s_j} = \left [ − \begin{array}{cc:cc} − 0.4 & 0.2 & 0.1 & 0.3 \\ − 0.2 & 0.4 & 0.3 & 0.1 \\ − \hdashline − 0.1 & 0.3 & 0.4 & 0.2 \\ − 0.3 & 0.1 & 0.2 & 0.4 − \end{array} − \right ] − \end{aligned} − </math> − − 此例子中，<math>[[1, 2], [3, 4]]</math>既是一个强成块的分组，又是一个精确成块的分组。 − − − − ===准成块性 Quasi Lumpability=== − − 我们可以看到，强成块性这种对于马尔科夫矩阵的分块性是一个很严格的要求。而我们在现实情况中，很难会找到强成块的矩阵，稍微加了一点扰动就不行了。如果我们考虑了这种扰动的情况，我们就可以定义不成块但非常接近成块的情况：quasi<ref name=":5">Franceschinis, Giuliana, and Richard R. Muntz. "Bounds for quasi-lumpable Markov chains." Performance Evaluation 20.1-3 (1994): 223-243.</ref> − − 如果一个 <math>P</math>可以被分解为<math>P = P^- + P^{\epsilon}</math>，其中<math>P^-</math>是一个成块的矩阵，而<math>P^{\epsilon}</math>中的每个元素都小于<math>\epsilon</math>，<math>P</math>就是一个<math>\epsilon</math>-quasi-lumpable的矩阵。 − − 比如说，我们对上面的成块的例子加上一点扰动： − − <math> − \begin{aligned} − P = P_{s_i \rightarrow s_j} = \left [ − \begin{array}{cc:cc} − 0.40 & 0.18 & 0.11 & 0.31 \\ − 0.21 & 0.42 & 0.29 & 0.08 \\ − \hdashline − 0.12 & 0.30 & 0.38 & 0.20 \\ − 0.30 & 0.08 & 0.22 & 0.40 − \end{array} − \right ] − = − \left [ − \begin{array}{cc:cc} − 0.4 & 0.2 & 0.1 & 0.3 \\ − 0.2 & 0.4 & 0.3 & 0.1 \\ − \hdashline − 0.1 & 0.3 & 0.4 & 0.2 \\ − 0.3 & 0.1 & 0.2 & 0.4 − \end{array} − \right ] − + − \left [ − \begin{array}{cccc} − 0.00 & -0.02 & 0.01 & 0.01 \\ − 0.01 & 0.02 & -0.01 & -0.02 \\ − 0.02 & 0.00 & -0.02 & 0.00 \\ − 0.00 & -0.02 & 0.02 & 0.00 − \end{array} − \right ] − \end{aligned} − </math> − − 就能获得一个<math>\epsilon</math>-quasi-lumpable，<math>\epsilon=0.02</math>的矩阵。 − − − − ===比例成块性 Proportional Lumpability=== − − 比例成块性（Proportional Lumpability）<ref name=":6">Piazza, Carla, and Sabina Rossi. "Reasoning about proportional lumpability." International Conference on Quantitative Evaluation of Systems. Cham: Springer International Publishing, 2021.</ref>是基于连续时间马尔科夫链CTMC(Continuoous-time markov chain)的设定提出来的一个放松成块性限制的概念。目前暂未发现研究证明其能应用在离散时间马尔科夫链DTMC上。 − − 如果我们把DTMC的TPM <math>P</math>看作是一个差分的算子，相应的我们可以大概把CTMC的TPM <math>Q</math>看作是一个微分算子。 − − 强成块性在CTMC设定下跟DTMC是类似的，简单来说就是： − − 对于微观的离散状态空间 <math>S</math>，微观TPM<math>Q</math>，分组后的宏观状态空间<math>A</math>，如果<math>Q</math>满足强成块性的话： − − <math>Pr(A_m|s_i) = Pr(A_m|s_j), \forall s_i, s_j \in A_n,</math> − − <math>Pr(A_m|s_i) = \sum_{s_k \in A_m} Pr(s_j|s_i) = \sum_{s_k \in A_m} Q_{ij}</math> − − − 而比例成块性的定义是： − − 对<math>S</math>中的任意一个状态，存在一个函数<math>\kappa:S \rightarrow \mathcal{R}^+</math>，使得： − − <math>\forall A_m, A_n, A_m \neq A_n s_i, s_j \in A_m, \frac{Pr(A_m|s_i)}{\kappa(s_i)} = \frac{Pr(A_m|s_j)}{\kappa(s_j)}</math> − − 我们说服从这样的CTMC对分组<math>A</math> <math>\kappa</math>-proportionally lumpable。 − − − − 这六种成块性的定义按照限制严格度大概的排序是： − − 比例成块 Proportional < 准成块 Quasi < 弱成块 Weak < 精准成块 Exact < 强成块 Strong/Ordinary < 严格成块 Strict − − − − ==成块性和粗粒化== − − [[马尔科夫链的粗粒化]]可以理解为对一个马尔科夫TPM得到一个分组矩阵<math>\Phi</math>和它对应的宏观TPM<math>P'</math>。这个过程通常可以分为两部：先获取<math>\Phi</math>，再获取<math>P'</math>。 − − 对状态空间做粗粒化有硬划分和软划分两种。软划分可以看作把微观状态打散重构成了一些宏观状态，而硬划分则是更严格的，把若干个微观状态分成一个组。我们这里只讨论硬划分，不讨论软划分。 − − 成块性是对第一步，对<math>\Phi</math>的约束要求；而上面提到的宏观最大预测性、可交换性和一致性是对<math>P'</math>的约束。 − − 由上面的成块性公式（2）和例子中我们能获得一个直观上的说法：当马尔科夫矩阵存在block结构，或者状态明显可被分成几类的时候，根据这样的划分，该矩阵就是成块的。对于简单的<math>P</math>，如图6中的<math>\bar{P}</math>所示，我们能够根据上面的定理（1）很快的找出它的成块划分<math>\Phi</math>，然后非常快捷的通过定义（3）来找出其对应的<math>P'</math>。 − − − − ===基于成块性的粗粒化方法（未给定成块的划分的情况）=== − − [[文件:Lump fig1.png|缩略图|398x398像素|图6：Zhang<ref name=":4" /> 文章中的示意图。图中左面四个矩阵都是成块的马尔科夫矩阵，而右面的P_2是一个噪声矩阵，(P_1)^T P_2 = 0|替代=]] − − 但是，有时候有些成块的矩阵的状态排序被打乱了（如图（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>这样的矩阵，我们既无法确定它是否成块，也无法决定它的划分，我们甚至不知道它的马尔科夫秩。 − − 在这种情况下，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" />的文章中提供了一种寻找最优划分的方法。通过此方法我们能找到最优的划分，代入这个最优划分我们就能通过上面的充分必要条件来决定一个马尔科夫矩阵是否成块。具体步骤如下： − − #先获取一个n*n维的马尔科夫矩阵P，或者是马尔科夫链的频率采样； − #获取r<n 的马尔科夫秩，或指定一个r； − #对P进行SVD分解，<math>P = U \Sigma V^T</math>，其中U为左奇异向量，V为右奇异向量。 − #通过下列公式得到最优划分 <math>\Omega_1, \Omega_2, ... , \Omega_r</math> − − <math> − \Omega_1, \Omega_2, ... , \Omega_r = argmin_{\Omega_1, \Omega_2, ... , \Omega_r} min_{v_1, v_2, ... , v_r} \sum_{s=1}^r \sum_{i \in \Omega_s} || V_{[i,:r]} - v_s ||_2^2 − </math> − − 其中，<math>v_s</math>是第<math>s</math>类<math>\Omega_s</math>的特征向量。 − − 这个算法的意思是在最优的划分中，<math>\Omega_s</math>中的状态<math>i</math>的右奇异向量会和<math>v_s</math>距离最小，也就是说，让每个微观态的右特征向量和它对应的宏观态的右特征向量尽可能接近。 − − − − − 这个看起来非常眼熟，其实它就是在做kMeans聚类算法。让<math>v_s</math>和组里的<math>V[i:r]</math>距离最小的方法，就是让<math>v_s</math>成为<math>V[i:r]</math>这若干个点的中心。 − − 回顾一下kMeans算法把n个点聚成r类的目标函数，其中第<math>i</math>个点被归到第<math>c^i</math>类，而<math>\mu_j</math>为第<math>j</math>类点的中心点： − − <math>J(c^1, ... , c^n, \mu_1, ... , \mu_r) = \sum_{i=1}^n || x_i - \mu_{c^i} ||^2 </math> − − 我们看到这两个目标函数是非常相似的。所以，我们就可以通过上述算法或者kMeans来获取最优的状态划分，然后根据这个状态来判断马尔科夫矩阵的成块性。
清空全部内容