Скорректированная взаимная информация

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

Взаимная информация двух разделов [ править ]

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

${\ Displaystyle U_ {i} \ cap U_ {j} = \ varnothing = V_ {i} \ cap V_ {j}}$

для всех и в комплекте:${\ displaystyle i \ neq j}$

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

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

${\displaystyle n_{ij}=\left|U_{i}\cap V_{j}\right|}$

Предположим, что объект выбран случайным образом из 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)}$

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

${\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)}}}$

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

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

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

Поправка на случайность [ править ]

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

${\displaystyle {\begin{aligned}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 {N\cdot n_{ij}}{a_{i}b_{j}}}\right)\times \\&{\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{aligned}}}$

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

${\displaystyle a_{i}=\sum _{j=1}^{C}n_{ij}}$

и

${\displaystyle b_{j}=\sum _{i=1}^{R}n_{ij}}$

Скорректированная мера ^[1] для взаимной информации может быть определена следующим образом:

${\displaystyle AMI(U,V)={\frac {MI(U,V)-E\{MI(U,V)\}}{\max {\{H(U),H(V)\}}-E\{MI(U,V)\}}}}$.

AMI принимает значение 1, когда два раздела идентичны, и 0, когда MI между двумя разделами равен значению, ожидаемому только по случайности.

Ссылки [ править ]

Внешние ссылки [ править ]

• Код Matlab для вычисления скорректированной взаимной информации
• Код R для быстрого и параллельного расчета скорректированной взаимной информации
• Код Python для вычисления скорректированной взаимной информации