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

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

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

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

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

для всех $i\neq j$и завершить:

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

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

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

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

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

Энтропия , связанная с разделением U, равна:

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

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

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

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

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

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

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

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

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

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

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

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

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

и

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

Скорректированная мера тогда взаимная информация может быть определена как:

$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 для вычисления скорректированной взаимной информации