Вариация информации - Variation of information

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

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

Определение

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

Позволять:

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

${\ displaystyle p_ {i} = | X_ {i} | / n}$ а также ${\ displaystyle q_ {j} = | Y_ {j} | / n}$

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

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

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

Это эквивалентно разделенному информационному расстоянию между случайными величинами i и j по отношению к равномерной вероятностной мере, определенной с помощью for . ${\ displaystyle A}$${\ Displaystyle \ му (В): = | В | / п}$${\ Displaystyle B \ substeq A}$

Явное информационное содержание

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

Множество всех разбиений набора образуют компактную Решетку, где частичный порядок индуцирует две операции, соединение и соединение , где максимум - это разделение только с одним блоком, то есть со всеми элементами, сгруппированными вместе, а минимум - это раздел, состоящий из всех элементов как одиночных. Встреча двух разделов, и это легко понять как раздел, образованный всеми парами пересечений одного блока,, of и одного ,, of . Из этого следует, что и . ${\ Displaystyle \ клин}$${\ displaystyle \ vee}$${\ Displaystyle {\ overline {\ mathrm {1}}}}$${\ displaystyle {\ overline {\ mathrm {0}}}}$${\ displaystyle X}$${\ displaystyle Y}$${\ displaystyle X_ {i}}$${\ displaystyle X}$${\ displaystyle Y_ {i}}$${\ displaystyle Y}$${\ Displaystyle X \ клин Y \ substeq X}$${\ Displaystyle X \ клин Y \ substeq Y}$

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

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

Тогда расстояние VI между и определяется выражением ${\ displaystyle X}$${\ displaystyle Y}$

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

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

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

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

Идентичности

Разнообразие информации удовлетворяет

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

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

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

где есть совместная энтропия в и , или ${\ Displaystyle H (X, Y)}$${\ displaystyle X}$${\ displaystyle Y}$

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

где и - соответствующие условные энтропии . ${\ Displaystyle H (X | Y)}$${\ Displaystyle H (Y | X)}$

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

${\ Displaystyle \ mathrm {VI} (X; Y) \ Leq \ log (п)}$,

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

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

Рекомендации

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

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

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

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