匈牙利算法

目标看是否存在一对一映射应用场景假设有n个被试每个被试有一个功能连接矩阵然后有一个预测功能连接矩阵我们想看被试预测的功能连接矩阵是否能够完美匹配自己的真实功能连接矩阵。1.首先构建真实-预测功能连接的相关矩阵A列是被试的真实功能连接行是预测功能连接。矩阵取负以转换为“代价”矩阵。相关越高代价越小。2.然后对于每一行找出最小的元素并从该行的每个元素中减去它找到每列中最小的元素也从该列的每个元素中减去它。3.用尽可能少的水平和垂直线覆盖矩阵中的所有零点如果最少的线数仍然少于n则进行下一步。4.找到最小的未覆盖元素m。将该值从所有未覆盖元素中减去并加到所有被竖线和横线一起覆盖的元素中。相当于对没有覆盖的每一行都减去一次m行最小值-m然后对覆盖的每列都加一次m只被列覆盖一次没有行覆盖的就不改变因为减了m又加了m同时被列和行覆盖就加m。重复第三步如果线数等于n停止不等于n则继续第四步-第三步。如果线数等于n每一行都可以找到与其它行不同列的0每一列也可以找到与其它列不同行的0。 这样也就是可以得到N个最佳匹配的行列的组合。然后把最终的矩阵中的0设置为1其它值为0。算矩阵的迹/n则得到这n个被试真实-预测one-to-one最佳匹配的程度。如果只是算一个真实-预测之间的相关矩阵的话可能得到一对多关系也就是被试1/2/3的真实功能连接都与被试1的预测功能连接最相关。原理基于下面的帖子再写清楚点写的很好稍作修改算法分享匈牙利算法Hungarian Algorithm详解步骤、正确性分析、时间复杂度分析 - 知乎匈牙利算法的目的是找到最大化所有匹配的相似性或者说代价最小同时要找到完美的一对一匹配关系。原问题的写法如下其中cij就是cost就是取负后矩阵中的每一个值xij就是是否选中这个组合作为最佳匹配之一选中就是1不选中就是0约束条件xij的数量为n而且所有的xij不能出现在同一行或者同一列对偶问题是让算法运行过程中减的值最大。其中每一行减的值为ui每一列减的值为vj。对偶问题目标函数如下约束1.ui vj cij2.最佳匹配的数量为N而且所有的xij不能出现在同一行或者同一列。满足这个条件停止。对偶问题最大值等于原问题最小值。ui的初始值为每行的最小值vj的初始值为减去每行最小值后每列的最小值。然后迭代就是在做下面的事情其中1到r为选中的行1到s为被选中的列当只要没到最后都有rsn也就是横和竖线之和都小于n因为rsn所以每一步对偶问题目标函数都在增加。当rs n时目标函数达到最大。这样1.可以满足约束条件ui vj cij2.没到算法终止条件前因为rsn所以每一步对偶问题目标函数都在增加。当目标函数达到最大时r s n。假设最小代价为OPT任何匹配的代价cost都大于等于OPT而∑ui ∑vj OPT当r s n时∑ui ∑vj cost自然此时∑ui ∑vj OPT cost参考资料HungarianAlgorithm.com - 解决作业问题(14 封私信) 算法分享匈牙利算法Hungarian Algorithm详解步骤、正确性分析、时间复杂度分析 - 知乎Predicting an individual’s functional connectivity from their structural connectome: Evaluation of evidence, recommendations, and future prospects