查找在 Python 中将一个集群列表转换为另一个集群列表的映射

Question

我正在使用 scikit-learn 对一些数据进行聚类，我想比较不同聚类技术的结果。我立即面临这样一个问题，即不同运行的聚类标签不同，因此即使它们完全相同地聚类，列表的相似度仍然很低。

说我有

list1 = [1, 1, 0, 5, 5, 1, 8, 1]
list2 = [3, 3, 1, 2, 2, 3, 8, 3]

我（理想情况下）喜欢一个函数，它以翻译字典的形式返回最佳映射，如下所示：

findMapping(list1, list2)
>>> {0:1, 1:3, 5:2, 8:8}

我说“最佳映射”是因为假设list3 = [3, 3, 1, 2, 2, 3, 8, 4]thenfindMapping(list1, list3)仍然会返回相同的映射，即使最终1变成 a4而不是 a 3。

所以最好的映射是最小化两个列表之间差异数量的映射。我认为这是一个很好的标准，但可能有更好的标准。

我可以编写一个试错优化算法来做到这一点，但我并不是第一个想要比较聚类算法结果的人。我希望这样的东西已经存在，我只是不知道它叫什么。但我四处寻找，并没有找到任何答案。

关键是在应用最佳翻译后，我将测量列表之间的差异，所以也许有一种方法可以测量不同索引的数字列表之间的差异，而无需将翻译作为中间步骤，这也很好。

====================================

根据 Pallie 的回答，我能够创建 findMapping 函数，然后我更进一步创建了一个翻译函数，该函数返回转换为第一个列表标签的第二个列表。

def translateLabels(masterList, listToConvert):    
  contMatrix = contingency_matrix(masterList, listToConvert)
  labelMatcher = munkres.Munkres()
  labelTranlater = labelMatcher.compute(contMatrix.max() - contMatrix)

  uniqueLabels1 = list(set(masterList))
  uniqueLabels2 = list(set(listToConvert))

  tranlatorDict = {}
  for thisPair in labelTranlater:
    tranlatorDict[uniqueLabels2[thisPair[1]]] = uniqueLabels1[thisPair[0]]

  return [tranlatorDict[label] for label in listToConvert]

即使使用这种转换（我需要一致地绘制集群颜色），使用 Rand 索引和/或标准化互信息似乎也是比较不需要共享标签的差异的好方法。

我也喜欢首先根据 data 中的值对两个列表进行排序的想法，但是当比较来自非常不同的数据的集群时，这可能不起作用。

Answer 1

您可以尝试计算两个结果之间的调整后的兰德指数。这给出了 -1 和 1 之间的分数，其中 1 是完美匹配。

或者通过使用混淆矩阵的argmax：

list1 = ['a', 'a', 'b', 'c', 'c', 'a', 'd', 'a']
list2 = [3, 3, 1, 2, 2, 3, 8, 3]
np.argmax(contingency_matrix(list1, list2), axis=1)
array([2, 0, 1, 3])

2 表示第 2 行（值 2，簇 3）最匹配“a”列 0（索引 2）。第 0 行然后匹配第 1 列，依此类推。

对于匈牙利方法：

m = Munkres()
contmat = contingency_matrix(list1, list2)
m.compute(contmat.max() - contmat)
[(0, 2), (1, 0), (2, 1), (3, 3)]

使用：https : //github.com/bmc/munkres