如何有效地进行类间匹配以计算结果准确性

卢卡斯·普根斯·费尔南德斯

我正在尝试将类(黄金数据)与聚类预测进行匹配。在我的过程结束时,我会看到以下内容:

              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!)。我需要连续执行数千次。有什么建议吗?

我之所以需要它,是因为我正在研究每个新数据集的类都不同的问题,但是当我运行测试时,我仍然拥有一些数据集的黄金,如果能够更快地完成测试,我将不胜感激。

保罗·潘泽

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

说明:首先请注意,如果您将解决方案写为置换矩阵,则目标函数是线性的。如果我们可以表达约束,即解决方案必须是线性方程和不等式的置换,那么我们可以交给标准求解器。事实上,我们不能,但是我们可以做第二件事,允许所有置换矩阵的凸包。由于问题是线性的,因此无法引入更好的解决方案,因此已基本完成。

请注意,如果解决方案是唯一的,则应该找到它。如果有多个解决方案,则理论上可能会混合使用它们(以凸组合的形式;实际上,似乎没有,但我不够熟练,无法完全排除它)。如果只对角线总和感兴趣,则可以忽略它。

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.]]

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章