Скорректированная взаимная информация - Adjusted mutual information

В теория вероятности и теория информации, скорректированная взаимная информация, вариант взаимная информация может использоваться для сравнения кластеры.^[1] Он исправляет эффект соглашения исключительно из-за случайности между кластеризацией, аналогично тому, как скорректированный индекс ранда исправляет Индекс Rand. Это тесно связано с изменение информации:^[2] когда аналогичная корректировка сделана для индекса VI, он становится эквивалентным AMI.^[1] Однако скорректированная мера больше не является метрической.^[3]

Взаимная информация двух разделов

Учитывая набор S из N элементы ${displaystyle S = {s_ {1}, s_ {2}, ldots s_ {N}}}$ рассмотрим два перегородки из S, а именно ${displaystyle U = {U_ {1}, U_ {2}, ldots, U_ {R}}}$ с р кластеры и ${displaystyle V = {V_ {1}, V_ {2}, ldots, V_ {C}}}$ с C кластеры. При этом предполагается, что перегородки являются так называемыми жесткие кластеры; разбиения попарно не пересекаются:

{displaystyle U_ {i} cap U_ {j} = varnothing = V_ {i} cap V_ {j}}

для всех ${displaystyle ieq j}$ , и заполните:

{displaystyle cup _ {i = 1} ^ {R} U_ {i} = cup _ {j = 1} ^ {C} V_ {j} = S}

В взаимная информация кластера перекрытия между U и V можно резюмировать в виде рИксC Таблица сопряженности ${displaystyle M = [n_ {ij}] _ {j = 1ldots C} ^ {i = 1ldots R}}$ , куда ${displaystyle n_ {ij}}$ обозначает количество объектов, общих для кластеров ${displaystyle U_ {i}}$ и ${displaystyle V_ {j}}$ . Это,

{displaystyle n_ {ij} = left | U_ {i} cap V_ {j} ight |}

Предположим, что объект выбран случайным образом из S; вероятность попадания объекта в кластер ${displaystyle U_ {i}}$ является:

{displaystyle P_ {U} (i) = {frac {| U_ {i} |} {N}}}

В энтропия связанные с разделением U является:

{displaystyle H (U) = - sum _ {i = 1} ^ {R} P_ {U} (i) log P_ {U} (i)}

H (U) неотрицательна и принимает значение 0 только тогда, когда нет неопределенности, определяющей принадлежность объекта к кластеру, т.е., когда есть только один кластер. Аналогично энтропия кластеризации V можно рассчитать как:

{displaystyle H (V) = - sum _ {j = 1} ^ {C} P_ {V} (j) log P_ {V} (j)}

куда ${Displaystyle P_ {V} (j) = {| V_ {j} |} / {N}}$ . В взаимная информация (MI) между двумя разделами:

{displaystyle MI (U, V) = sum _ {i = 1} ^ {R} sum _ {j = 1} ^ {C} P_ {UV} (i, j) log {frac {P_ {UV} (i , j)} {P_ {U} (i) P_ {V} (j)}}}

куда ${displaystyle P_ {UV} (i, j)}$ обозначает вероятность того, что точка принадлежит как кластеру ${displaystyle U_ {i}}$ в U и кластер ${displaystyle V_ {j}}$ в V:

{displaystyle P_ {UV} (i, j) = {frac {| U_ {i} cap V_ {j} |} {N}}}

MI - неотрицательная величина, ограниченная сверху энтропиями ЧАС(U) и ЧАС(V). Он количественно определяет информацию, совместно используемую двумя кластерами, и, таким образом, может использоваться в качестве кластеризации. мера сходства.

Поправка на случай

Словно Индекс Rand, базовое значение взаимной информации между двумя случайными кластеризациями не принимает постоянного значения и имеет тенденцию к увеличению, когда два раздела имеют большее количество кластеров (с фиксированным количеством установленных элементов N). Приняв гипергеометрический Модель случайности, можно показать, что ожидаемая взаимная информация между двумя случайными кластерами:

{Displaystyle {egin {выровнено} E {MI (U, V)} = & sum _ {i = 1} ^ {R} sum _ {j = 1} ^ {C} sum _ {n_ {ij} = (a_ { i} + b_ {j} -N) ^ {+}} ^ {min (a_ {i}, b_ {j})} {frac {n_ {ij}} {N}} log left ({frac {Ncdot n_ {ij}} {a_ {i} b_ {j}}} ight) imes & {frac {a_ {i}! b_ {j}! (N-a_ {i})! (N-b_ {j}) !} {N! N_ {ij}! (A_ {i} -n_ {ij})! (B_ {j} -n_ {ij})! (N-a_ {i} -b_ {j} + n_ {ij })!}} end {выровнены}}}

куда ${displaystyle (a_ {i} + b_ {j} -N) ^ {+}}$ обозначает ${displaystyle max (1, a_ {i} + b_ {j} -N)}$ . Переменные ${displaystyle a_ {i}}$ и ${displaystyle b_ {j}}$ - частичные суммы таблицы непредвиденных обстоятельств; то есть,