Сравнение кластеров: индекс Рэнда и вариация информации

Мне было интересно, есть ли у кого-нибудь понимание или интуиция, стоящие за разницей между вариацией информации и индексом Рэнда для сравнения кластеризаций.

Я прочитал статью Марины Мелии « Сравнение кластеризаций - расстояние, основанное на информации » (Журнал многомерного анализа, 2007), но, кроме того, что я заметил разницу в определениях, я не понимаю, что такое изменение информации фиксирует, что индекс ранда не захватывает.

Разница между этими двумя методами невелика. Лучший способ подумать об этом - рассмотреть решетку, определенную операцией слияния-разделения на кластерах. Обе эти меры можно восстановить, определив функцию в кластеризации, а затем определив расстояние между двумя кластеризациями по формуле:$f$

Теперь пусть и пусть, Установка дает индекс рандов, а установка дает VI.n i = | C я | е ( С ) = Σ п 2 я е ( С ) = Σ п я войти п $C = \{ C_1, C_2, \ldots, C_k\}$$n_i = |C_i|$$f(C) = \sum n_i^2$$f(C) = \sum n_i \log n_i$

На мой взгляд, есть огромные различия. На индекс Рэнда очень сильно влияет гранулярность кластеров, на которых он работает. В дальнейшем я буду использовать расстояние Миркина, которое является скорректированной формой индекса Рэнда (легко увидеть, но см., Например, Мейлу). Я также буду использовать расстояние разделения / объединения, которое также упоминается в некоторых статьях Мейлы (отказ от ответственности: расстояние разделения / объединения было предложено мной). Предположим, что вселенная состоит из ста элементов. Я буду использовать Top для обозначения кластеризации с одним кластером, содержащим все элементы, Bottom для обозначения кластеризации, где все узлы находятся в отдельных одноэлементных наборах, слева для обозначения кластеризации {{1,2, .. 10}, {11, 12..20}, {21,22..30}, ..., {91,92, .. 100}} и Право обозначать кластеризацию {{1,11, .. 91}, {2, 12, .. 92}, {3,13, .. 93}, ..., {10,20, .. 100}},

На мой взгляд, Bottom и Top - это согласованные (вложенные) кластеры, а Left и Right - максимально конфликтующие кластеры. Расстояния от упомянутых метрик для этих двух парных сравнений следующие:

               Top-Bottom     Left-Right 

Mirkin            9900          1800
VI                4.605         4.605
Split/join        99            180

Из этого следует, что Миркин / Рэнд рассматривают непротиворечивую пару «верх-низ» гораздо дальше друг от друга, чем максимально конфликтующая пара «левый-правый». Это крайний пример, чтобы проиллюстрировать это, но Миркин / Рэнд в целом очень сильно зависят от гранулярности кластеров, на которых он работает. Причиной, лежащей в основе этого, является квадратичная связь между этой метрикой и размерами кластера, объясняемая тем, что учитывается подсчет пар узлов. По сути, расстояние Миркина - это расстояние Хэмминга между наборами ребер объединений полных графов, индуцированных кластеризацией (я думаю, это ответ на ваш вопрос).

Что касается различий между изменением информации и разделением / объединением, первое более чувствительно к определенным конфликтным ситуациям, как продемонстрировал Мейла. Таким образом, Split / Join рассматривает только лучшее соответствие для каждого кластера и игнорирует фрагментацию, которая может возникнуть в оставшейся части этого кластера, тогда как Variation of Information подхватит это. Тем не менее, Split / Join легко интерпретируется как количество узлов, которые необходимо переместить, чтобы получить один кластер из другого , и в этом смысле его диапазон легче понять; на практике проблема фрагментации также может быть не такой распространенной.

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

               Top-Bottom     Left-Right 

Mirkin          0,9900          900,900
VI              0,4.605       2.303,2.303
Split/join      0,99             90,90

Отношения между потреблением сверху и снизу сразу становятся понятными. Часто очень полезно знать, согласуются ли две кластеризации (т. Е. Одна (почти) является субкластерингом другой), чтобы ослабить вопрос о том, близки ли они . Кластеризация может быть довольно далека от золотого стандарта, но все же быть последовательной или почти последовательной. В таком случае, возможно, нет оснований считать кластеризацию плохой в отношении этого золотого стандарта. Конечно, тривиальные кластеризации Top и Bottom будут согласованы с любой кластеризацией, поэтому это необходимо учитывать.

Наконец, я считаю, что такие метрики, как Mirkin, Variation of Information и Split / Join, являются естественными инструментами для сравнения кластеров. Для большинства приложений методы, которые пытаются включить статистическую независимость и исправить случайность, являются чрезмерно надуманными и запутывают, а не уточняют.

Второй пример Рассмотрим следующие пары кластеров: C1 = {{1, 2, 3, 4, 5, 6, 7, 8}, {9, 10, 11, 12, 13, 14, 15, 16}} с C2 = {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, {11, 12, 13, 14, 15, 16}}

и C3 = {{1, 2, 3, 4}, {5, 6, 7, 8, 9, 10}, {11, 12, 13, 14, 15, 16}} с {{1, 2, 3 , 4}, {5, 6, 7, 8, 9, 10, 11, 12}, {13, 14, 15, 16}}

Здесь C2 может быть сформирован из C1 путем перемещения узлов 9 и 10, а C3 может быть сформирован из C3 путем перемещения узлов 11 и 12. Оба изменения идентичны («перемещать два узла») за исключением того факта, что размеры участвующих кластеров различаются , Таблица метрик кластеризации для этих двух примеров такова:

            C1-C2         C3-C4

Mirkin       56            40 
VI            0.594         0.520
Split/Join    4             4

Можно видеть, что на размер Mirkin / Rand и Variation информации влияют размеры кластера (и Mirkin в большей степени; это будет более выражено при расхождении размеров кластера), тогда как расстояние Split / Join не имеет (его значение равно 4 поскольку он «перемещает» узлы из одной кластеризации в другую всегда через наибольшую общую субкластеризацию). Это может быть желательной чертой в зависимости от обстоятельств. Стоит знать простую интерпретацию Split / Join (количество перемещаемых узлов) и независимость от размера кластера. Между Миркиным и Вариацией Информации я думаю, что последнее очень предпочтительнее.