如何有效地进行 class-to-cluster 匹配以计算结果精度

Question

我正在尝试将类（黄金数据）与聚类预测相匹配。在我的过程结束时，我有类似的东西：

              0  1  2  3  4  5  6  7  8  9
Class1        0  0  0  0  0  0  1  0  0  0
Class2        0  0  2  0  0  0  0  0  0  0
Class3        6  0 10  0  0  0  0  0  4  0
Class4        0  4  0  0  0  2  0  0  0  0
Class5        4  0  0  5  0  0  2  0  0  2
Class6        0  0  0  0  0  0  0  2  0  0
Class7        2  0  0  0  0  0  0  0  1  0
Class8        0  0  0  0  3  0  0  0  0  0
Class9        0  0  0  2  0  0  0  0  0  0
Class10       0  0  0  0  0  0  0  0  1  0

我基本上需要最大化主对角线总和切换列，将其变成类似

的形式

              6  5   2  1  3  7  0  4  9  8
Class1        1  0   0  0  0  0  0  0  0  0
Class2        0  0   2  0  0  0  0  0  0  0
Class3        0  0  10  0  0  0  6  0  0  4
Class4        0  2   0  4  0  0  0  0  0  0
Class5        2  0   0  0  5  0  4  0  2  0
Class6        0  0   0  0  0  2  0  0  0  0
Class7        0  0   0  0  0  0  2  0  0  1
Class8        0  0   0  0  0  0  0  3  0  0
Class9        0  0   0  0  2  0  0  0  0  0
Class10       0  0   0  0  0  0  0  0  0  1

我现在做的是（可运行的例子）(python/pandas/numpy):

import numpy as np
import pandas as pd
from itertools import permutations
from functools import partial
from operator import itemgetter

def diag_sum(cm, columns):
    return np.trace(cm[:,list(columns)])

def confusion_matrix(y_true, y_pred):
    classes = list(set(y_true))
    clusters = list(set(y_pred))
    cm = {cla: [0]*len(clusters) for cla in classes}

    for y_t, y_p in zip(y_true, y_pred):
        cm[y_t][y_p] += 1

    cm = pd.DataFrame.from_dict(cm, orient='index')

    matrix_cm = cm.as_matrix()
    column_perm = list(permutations(range(matrix_cm.shape[1])))

    result = map(partial(diag_sum, matrix_cm), column_perm)

    index, value = max(enumerate(result), key=itemgetter(1))

    cm = cm[list(column_perm[index])]
    return cm

# Same example as the matrixes above
y_true = ['Class1']*1 + ['Class2']*2 + ['Class3']*20 + ['Class4']*6 + ['Class5']*13 + ['Class6']*2 + ['Class7']*3 + ['Class8']*3 + ['Class9']*2 + ['Class10']*1
y_pred = [6]*1 + [2]*2 + [0]*6 + [2]*10 + [8]*4 + [1]*4 + [5]*2 + [0]*4 + [3]*5 + [6]*2 + [9]*2 + [7]*2 + [0]*2 + [8]*1 + [4]*3 + [3]*2 + [8]*1

print(confusion_matrix(y_true, y_pred))

归根结底，它是有效的，但排列确实很昂贵 O(n!)。我需要连续执行它数千次。有什么建议吗？

我需要这个，因为我正在处理一个问题，其中类对于每个新数据集都是不同的，但我仍然有一些数据集是我的运行我的测试并且会非常感谢能够快速制作。

Answer 1

这是使用 scipy.optimize.linprog 的方法。

说明：首先请注意，如果您将解写为置换矩阵，则 objective 函数是线性的。如果我们可以表达解决方案必须是线性方程和不等式方面的排列的约束，我们可以将其交给标准求解器。事实上我们不能，但我们可以做次优的事情并允许所有置换矩阵的凸包。因为问题是线性的，所以不能引入更好的解决方案，所以我们基本上完成了。

请注意，如果解决方案是唯一的，则应该直接找到它。如果有多个解决方案，理论上它可能会混合它们（在凸组合中；在实践中，它似乎没有，但我不够专业，无法完全排除它）。如果你只对对角线和感兴趣可以忽略这个。

import numpy as np
from scipy.optimize import linprog

def best_perm(A):
    n, n = A.shape
    res = linprog(-A.ravel(),
                  A_eq=np.r_[np.kron(np.identity(n), np.ones((1, n))),
                             np.kron(np.ones((1, n)), np.identity(n))],
                  b_eq=np.ones((2*n,)), bounds=n*n*[(0, None)])
    assert res.success
    return res.x.reshape(n, n).T

import pandas as pd
from io import StringIO

df = pd.read_csv(StringIO("""              0  1  2  3  4  5  6  7  8  9
Class1        0  0  0  0  0  0  1  0  0  0
Class2        0  0  2  0  0  0  0  0  0  0
Class3        6  0 10  0  0  0  0  0  4  0
Class4        0  4  0  0  0  2  0  0  0  0
Class5        4  0  0  5  0  0  2  0  0  2
Class6        0  0  0  0  0  0  0  2  0  0
Class7        2  0  0  0  0  0  0  0  1  0
Class8        0  0  0  0  3  0  0  0  0  0
Class9        0  0  0  2  0  0  0  0  0  0
Class10       0  0  0  0  0  0  0  0  1  0"""), index_col=0, delimiter='\s+')

shuffle = best_perm(df.values)

print(shuffle)

print(df.values @ shuffle)

输出：

[[ 0.  0.  0.  0.  0.  0.  1.  0.  0.  0.]
 [ 0.  0.  0.  1.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  1.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  1.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  1.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  1.  0.]
 [ 1.  0.  0.  0.  0.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  1.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  0.  0.  0.  0.  1.]
 [ 0.  1.  0.  0.  0.  0.  0.  0.  0.  0.]]
[[  1.   0.   0.   0.   0.   0.   0.   0.   0.   0.]
 [  0.   0.   2.   0.   0.   0.   0.   0.   0.   0.]
 [  0.   0.  10.   0.   0.   0.   6.   0.   0.   4.]
 [  0.   0.   0.   4.   0.   0.   0.   0.   2.   0.]
 [  2.   2.   0.   0.   5.   0.   4.   0.   0.   0.]
 [  0.   0.   0.   0.   0.   2.   0.   0.   0.   0.]
 [  0.   0.   0.   0.   0.   0.   2.   0.   0.   1.]
 [  0.   0.   0.   0.   0.   0.   0.   3.   0.   0.]
 [  0.   0.   0.   0.   2.   0.   0.   0.   0.   0.]
 [  0.   0.   0.   0.   0.   0.   0.   0.   0.   1.]]

Answer 2

Hungarian algorithm因正是这个赋值问题而广为人知。它将在 O(n³) 中找到 最优值。

但是，对于评估聚类，存在更好的措施。使用 ARI 和 NMI。他们只需要 O(n²) 并且被广泛接受。

如何有效地进行 class-to-cluster 匹配以计算结果精度

How to efficiently make class-to-cluster matching in order to calculate resulting accuracy

python

numpy

cluster-analysis

confusion-matrix