Минимизация классификации классификации кластеров

Question

Предположим, что у нас есть некоторые помеченные данные X с N точками данных. Используя некоторый алгоритм кластеризации, скажем, k-означает, мы разбиваем X на k кластеров C_1, ..., C_k. Пусть S_1, ..., S_k являются истинными наборами разбиения и определяют классификационную ошибку кластеризации следующим образом:

Я хочу найти оптимальное «совпадение» кластеров с истинными кластерами, минимизируя эту ошибку. Таким образом, для k = 3 оптимальная перестановка может быть {(C_1 и S_2), (C_2 и S_3), (C_3 и S_1)}. Очевидным способом найти оптимальную перестановку было бы посмотреть на все k! перестановки и результирующей ошибки, и выберите ту, которая дает наименьшую ошибку. Это, однако, требует k! время, так что мой вопрос, можно ли было бы разработать алгоритм, чтобы сделать это более эффективно?

Answer 1

Есть хорошие и хорошо проверенные алгоритмы для нахождения наилучшего соответствия, например,

Hungarian algorithm.

Но, как правило, не рекомендуется сопоставлять кластеры с классами.

Хорошая кластеризация - это тот, который вам что-то говорит новый о ваших данных. Так что должен быть существенно отличным от известных классов.