812
个编辑
更改
跳到导航
跳到搜索
第625行：
第625行： − + − + − + − + − + − −
→最大化有效信息的谱分解方法
'''输入'''：原始包含 <math>N</math> 个状态的马尔科夫链 <math>P</math>和距离超参<math>\epsilon</math>；
'''输入'''：原始包含 <math>N</math> 个状态的马尔科夫链 <math>P</math>和距离超参<math>\epsilon</math>；
# 对 <math>P</math> 进行矩阵的[[特征值分解]]，得到特征值集合 <math>\Lambda=\{\lambda_i\}^N_{i=1}</math> 与特征向量集合 <math>E=\{e_i\}^N_{i=1}</math>。
# 对 <math>P</math> 进行矩阵的[[特征值分解]]，得到特征值集合 <math>\Lambda=\{\lambda_i\}^N_{i=1}</math> 与特征向量集合 <math>E=\{e_i\}^N_{i=1}</math>；
# 构建新的有偏的特征向量集合 <math>E’=\{\lambda_ie_i|\lambda_i≠0\}^N_{i=1}</math>，该集合中的每个向量被其对应的特征值所加权，同时去除了零特征值和对应的特征向量（新的状态数量为<math>N'=rank(A)</math>）。直观地说，忽略特征值为0的特征向量是有意义的，因为它对应了动力学中的简并性，并且非零特征值和相应的特征向量包含了丰富的网络拓扑结构信息；
# 构建新的有偏的特征向量集合 <math>E’=\{\lambda_ie_i|\lambda_i≠0\}^N_{i=1}</math>，该集合中的每个向量被其对应的特征值所加权，同时去除了零特征值和对应的特征向量（新的状态数量为<math>N'=rank(A)</math>）。直观地说，忽略特征值为0的特征向量是有意义的，因为它对应了动力学中的简并性，并且非零特征值和相应的特征向量包含了丰富的网络拓扑结构信息；
# 依据<math>E'</math>计算状态间的相似矩阵<math>D_{N'×N'}</math>：
# 依据<math>E'</math>计算状态间的相似矩阵<math>D_{N'×N'}</math>：
## 如果状态 <math>v_i</math> 和 <math>v_j</math> 分别在对方的马尔可夫毯中，则通过新的特征向量计算两个节点的cosine相似性作为两者间的相似度 <math>d_{ij}</math> 和 <math>d_{ji}</math>
## 如果状态 <math>v_i</math> 和 <math>v_j</math> 分别在对方的马尔可夫毯中，则通过新的特征向量计算两个节点的cosine相似性作为两者间的相似度 <math>d_{ij}</math> 和 <math>d_{ji}</math>；
## 否则将两个节点间的相似度设为无穷大 <math>\infty</math>（可以设个比较大的值，如10000）
## 否则将两个节点间的相似度设为无穷大 <math>\infty</math>（可以设个比较大的值，如10000）；
# 基于相似度矩阵<math>D_{N'×N'}</math>和一个超参<math>\epsilon</math>（需要线性搜索，可以选择EI最大的参数），使用[[OPTICS]]算法（是一种基于密度的划分算法，旨在识别数据集中不同密度的划分结构）进行划分，输出对应超参<math>\epsilon</math>下的划分方式
# 基于相似度矩阵<math>D_{N'×N'}</math>和一个超参<math>\epsilon</math>（需要线性搜索，可以选择EI最大的参数），使用[[OPTICS]]算法（是一种基于密度的划分算法，旨在识别数据集中不同密度的划分结构）进行划分，输出对应超参<math>\epsilon</math>下的划分方式。
该方案的时间复杂度为<math>O(N^3)</math>
该方案的时间复杂度为<math>O(N^3)</math>。
'''缺点'''：
'''缺点'''：
# 对大规模动力学进行粗粒化时，对转移矩阵进行特征值分解的计算复杂度也较高
# 对大规模动力学进行粗粒化时，对转移矩阵进行特征值分解的计算复杂度也较高
# 聚类算法所需的距离超参<math>\epsilon</math>需要线性搜索，需要加入人为的先验知识
# 聚类算法所需的距离超参<math>\epsilon</math>需要线性搜索，需要加入人为的先验知识
===寻找成块划分的谱分解方法===
===寻找成块划分的谱分解方法===