Изменение информации

В теории вероятностей и теории информации изменение информации или расстояние между общей информацией является мерой расстояния между двумя кластерами ( разделами элементов ). Это тесно связано с взаимной информацией ; на самом деле это простое линейное выражение, включающее взаимную информацию. Однако, в отличие от взаимной информации, изменение информации является истинной метрикой , поскольку она подчиняется неравенству треугольника .

Информационная диаграмма, иллюстрирующая связь между информационной энтропией , взаимной информацией и изменением информации.

Определение

Предположим, у нас есть два раздела $X$ и $Y$ из набора $A$ на непересекающиеся подмножества , а именно $X=\{X_{1},X_{2},\ldots ,X_{k}\}$ и $Y=\{Y_{1},Y_{2},\ldots ,Y_{l}\}$.

Позволять:

$n=\sum _{i}|X_{i}|=\sum _{j}|Y_{j}|=|A|$

$p_{i}=|X_{i}|/n$ и $q_{j}=|Y_{j}|/n$

$r_{ij}=|X_{i}\cap Y_{j}|/n$

Тогда изменение информации между двумя разделами будет:

$\mathrm {VI} (X;Y)=-\sum _{i,j}r_{ij}\left[\log(r_{ij}/p_{i})+\log(r_{ij}/q_{j})\right]$.

Это эквивалентно общему информационному расстоянию между случайными величинами i и j относительно равномерной вероятностной меры на $A$ определяется $\mu (B):=|B|/n$ для $B\subseteq A$.

Явный информационный контент

Мы можем переписать это определение в терминах, которые явно подчеркивают информационное содержание этого показателя.

Набор всех разбиений множества образует компактную решетку , где частичный порядок индуцирует две операции: встречу $\wedge$ и объединение $\vee$, где максимум ${\overline {\mathrm {1} }}$ — это раздел только с одним блоком, т. е. все элементы сгруппированы вместе, а минимум равен ${\overline {\mathrm {0} }}$, раздел, состоящий из всех элементов в виде одиночных элементов. Встреча двух перегородок $X$ и $Y$ легко понять, поскольку это разделение образовано всеми парными пересечениями одного блока, $X_{i}$, из $X$ и один, $Y_{i}$, из $Y$. Отсюда следует, что $X\wedge Y\subseteq X$ и $X\wedge Y\subseteq Y$.

Определим энтропию раздела $X$ как

$H\left(X\right)\,=\,-\sum _{i}\,p_{i}\log p_{i}$,

где $p_{i}=|X_{i}|/n$. Четко, $H({\overline {\mathrm {1} }})=0$ и $H({\overline {\mathrm {0} }})=\log \,n$. Энтропия разбиения — монотонная функция на решетке разбиений в том смысле, что $X\subseteq Y\Rightarrow H(X)\geq H(Y)$.

Тогда расстояние VI между $X$ и $Y$ дается

$\mathrm {VI} (X,Y)\,=\,2H(X\wedge Y)\,-\,H(X)\,-\,H(Y)$.

Разница $d(X,Y)\equiv |H\left(X\right)-H\left(Y\right)|$ является псевдометрикой, поскольку $d(X,Y)=0$ не обязательно подразумевает это $X=Y$. Из определения ${\overline {\mathrm {1} }}$, это $\mathrm {VI} (X,\mathrm {1} )\,=\,H\left(X\right)$.

Если в диаграмме Хассе мы проведем ребро от каждого разбиения к максимальному ${\overline {\mathrm {1} }}$ и присвойте ему вес, равный расстоянию VI между данным разделом и ${\overline {\mathrm {1} }}$, мы можем интерпретировать расстояние VI как среднее значение различий весов ребер до максимального значения.

$\mathrm {VI} (X,Y)\,=\,|\mathrm {VI} (X,{\overline {\mathrm {1} }})\,-\,\mathrm {VI} (X\wedge Y,{\overline {\mathrm {1} }})|\,+\,|\mathrm {VI} (Y,{\overline {\mathrm {1} }})\,-\,\mathrm {VI} (X\wedge Y,{\overline {\mathrm {1} }})|\,=\,d(X,X\wedge Y)\,+\,d(Y,X\wedge Y)$.

Для $H(X)$ как определено выше, считается, что совместная информация двух разделов совпадает с энтропией встречи

$H(X,Y)\,=\,H(X\wedge Y)$

и у нас тоже есть такое $d(X,X\wedge Y)\,=\,H(X\wedge Y|X)$ совпадает с условной энтропией места встречи (пересечения) $X\wedge Y$ относительно $X$.

Личности

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

$\mathrm {VI} (X;Y)=H(X)+H(Y)-2I(X,Y)$,

где $H(X)$ это энтропия ​ $X$, и $I(X,Y)$ это взаимная информация между $X$ и $Y$ относительно равномерной вероятностной меры на $A$. Это можно переписать как

$\mathrm {VI} (X;Y)=H(X,Y)-I(X,Y)$,

где $H(X,Y)$ это энтропия совместная $X$ и $Y$, или

$\mathrm {VI} (X;Y)=H(X|Y)+H(Y|X)$,

где $H(X|Y)$ и $H(Y|X)$ являются соответствующими условными энтропиями .

Изменение информации также может быть ограничено либо по количеству элементов:

$\mathrm {VI} (X;Y)\leq \log(n)$,

Или относительно максимального количества кластеров, $K^{*}$:

$\mathrm {VI} (X;Y)\leq 2\log(K^{*})$

Неравенство треугольника

Чтобы проверить неравенство треугольника $\mathrm {VI} (X;Z)\leq \mathrm {VI} (X;Y)+\mathrm {VI} (Y;Z)$, разверните, используя тождество $\mathrm {VI} (X;Y)=H(X|Y)+H(Y|X)$. Достаточно доказать $$H(X|Z)\leq H(X|Y)+H(Y|Z)$$Правая часть имеет нижнюю границу $$H(X|Y)+H(Y|Z)\geq H(X|Y,Z)+H(Y|Z)=H(X,Y|Z)$$что не меньше левой стороны.

Дальнейшее чтение

• Араби, П.; Бурман, С.А. (1973). «Многомерное масштабирование меры расстояния между перегородками». Журнал математической психологии . 10 (2): 148–203. дои : 10.1016/0022-2496(73)90012-6 .
• Мейла, Марина (2003). «Сравнение кластеров по изменению информации». Конспекты лекций по информатике. Том. 2777. стр. 173–187. дои : 10.1007/978-3-540-45167-9_14 . ISBN  978-3-540-40720-1 . S2CID   4341039 . {{cite book}}: |journal= игнорируется ( помощь ) ; Отсутствует или пусто |title= ( помощь )
• Мейла, М. (2007). «Сравнение кластеров — расстояние, основанное на информации» . Журнал многомерного анализа . 98 (5): 873–895. дои : 10.1016/j.jmva.2006.11.013 .
• Кингсфорд, Карл (2009). «Заметки по теории информации» (PDF) . Проверено 22 сентября 2009 г.
• Красков, Александр; Харальд Стёгбауэр; Ральф Г. Анджейак; Питер Грассбергер (2003). «Иерархическая кластеризация на основе взаимной информации». arXiv : q-bio/0311039 .

Внешние ссылки

• Partanalyzer включает реализацию VI и других метрик и индексов на C++ для анализа секций и кластеризации.
• Реализация C++ с файлами MATLAB mex