对矩阵进行排序，使其在每个对角线上都具有最大值

Question

我在 Whosebug 和其他论坛上寻找解决方案，但尚未找到仅使用 Base-R 的解决方案 - 这正是我需要使用的解决方案。

我正在尝试逐行最大化 NxN 矩阵中的对角线，因此该行的最大值在对角线上（我希望这是有意义的 - 特别是在聚类分析的上下文中）

到目前为止，我已经尝试对此进行硬编码，但感觉适得其反 - 这是通过尝试创建一个 'swap' 函数，在列中使用 for 循环并交换所需条目来完成的。即在第 1 行： 1,3,4,7 -> 7,3,4,1 第 2 行： 4,10,14,22 -> 4,22,14,10 等等

这是我尝试使用的矩阵示例：

CM <- table(expected, predicted)
CM
     1   2  3  4  
  A  11  1  0  66
  B  0   22 77 18  
  C  10  49 34 48  
  D  0   46 31 49  

#Desired:
CM

     1   2  3  4  
  A  66  1  0  11  #max 66
  B  0   77 22 18  #max 77
  C  10  34 49 48  #max 49
  D  0   46 31 49  #max 49

这是（糟糕的）交换功能的摘录，它不起作用。

swap <- function(x,y){
  a = c()       #create an empty vector
  a <- x        #assign x value to a (where x = diagonal location)
  x <- y        #assign y to x (where y = maximum value 
  y <- a        #re-assign a value back to y

}

以上显示了我对结果的期望 - 我希望有人可以为我提供一些有用的伪代码，或者让我知道是否有任何遗漏。

抱歉，如果这是一个简单或显而易见的问题！

Answer 1

所以看看这个，您似乎想要逐行遍历矩阵并通过交换最大元素与对角线中的元素来改变每一行。我对如何做到这一点的想法是使用这个交换功能：

swap <- function(matrixRow,x,y){
  #x is diagonal index
  #y is max of the row
    indexY <- which(matrixRow == y)
    valX <- matrixRow[x]
    matrixRow[x] <- y
    matrixRow[indexY] <- valX
    return(matrixRow)
}

这将 return 行的更改版本。然后您可以将这个新版本的行分配给当前行。例如，

vals <- c(11,0,10,0,  1,22,49,46,  0, 77, 34, 31,   66, 18, 48, 49)
mat <- matrix(vals, nrow = 4)

编辑：呜呜按错了键，发布得太早了。这是其余的：

for(i in 1:nrow(mat)){
rowI <- mat[i,]
y <- max(rowI)
mat[i,] <- swap(rowI, i, y)
}

Answer 2

执行此操作的优先方法是实施 Hungarian algorithm.

仅在每一行中选择最大值并不一定会使对角线最大化，因为一行中的最大值可能略好于次佳，而选择次佳将使您在另一行中获得更大的值行。

Answer 3

为使用 Python 的人添加匈牙利算法建议（我在搜索 Python 解决方案时发现了此评论。）

这是最高重新排序矩阵的代码片段，使得对角线具有所有最好的“聚类”。

y 是真实标签的向量。

pred 是簇标签的向量。

linear_sum_assignment是匈牙利算法。

-cm为最大化，cm为最小化。

contingency_matrix 是实际到预测的集群的非最高对角线排序。

输出显示最佳案例聚类的对角线，就像混淆矩阵对角线显示“正确”预测一样。

from sklearn.metrics.cluster import contingency_matrix as CM
from scipy.optimize import linear_sum_assignment
cm = CM(y,pred)
row_idx, col_idx = linear_sum_assignment(-cm) #-cm to maximize, o/w it minimizes 
print(cm[row_idx,col_idx])

对矩阵进行排序，使其在每个对角线上都具有最大值

Ordering a matrix to have the maximum value in each diagonal

r

cluster-analysis

k-means

confusion-matrix