В теории вероятностей и теории информации , то изменение информации или общей информация расстоянии является мерой расстояния между двумя кластеризациями ( перегородками элементов ). Это тесно связано с взаимной информацией ; действительно, это простое линейное выражение, включающее взаимную информацию. Однако, в отличие от взаимной информации, вариация информации является истинной метрикой , поскольку подчиняется неравенству треугольника . [1] [2] [3]
Определение
Предположим, у нас есть два раздела а также из множества на непересекающиеся подмножества , а именно а также .
Позволять:
- а также
Тогда разброс информации между двумя разделами будет следующим:
- .
Это эквивалентно разделенному информационному расстоянию между случайными величинами i и j относительно равномерной вероятностной меры на определяется для .
Явное информационное содержание
Мы можем переписать это определение в терминах, которые явно выделяют информационное содержание этой метрики.
Множество всех разбиений набора образуют компактную Решетку, в которой частичный порядок индуцирует две операции: встреча и присоединение , где максимум это раздел, состоящий только из одного блока, т. е. все элементы сгруппированы вместе, и минимум равен , разбиение, состоящее из всех элементов как одиночных. Встреча двух перегородок а также легко понять как это разбиение, образованное всеми парными пересечениями одного блока, , из и один, , из . Отсюда следует, что а также .
Определим энтропию раздела в виде
- ,
где . Четко, а также . Энтропия разбиения - это монотонная функция на решетке разбиений в том смысле, что.
Тогда расстояние VI между а также дан кем-то
- .
Различия является псевдометрикой как не обязательно означает, что . Из определения, это .
Если на диаграмме Хассе мы проведем ребро от каждого раздела до максимума и присвоить ему вес, равный расстоянию VI между данным разделом и , мы можем интерпретировать расстояние VI как в основном среднее значение разницы весов ребер до максимума.
- .
Для как определено выше, считается, что совместная информация двух разделов совпадает с энтропией встречи
и у нас также есть это совпадает с условной энтропией встречи (пересечения) относительно .
Идентичности
Разнообразие информации удовлетворяет
- ,
где является энтропия в, а также является взаимный обмен информацией между а также относительно равномерной вероятностной меры на . Это можно переписать как
- ,
где является совместной энтропии в а также , или же
- ,
где а также - соответствующие условные энтропии .
Разнообразие информации также может быть ограничено числом элементов:
- ,
Или относительно максимального количества кластеров, :
Рекомендации
- ^ П. Араби, С. А. Бурман, С. А., "Многомерное масштабирование мер расстояния между разделами", Журнал математической психологии (1973), том. 10, 2, стр. 148–203, DOI: 10.1016 / 0022-2496 (73) 90012-6
- ^ WH Журек, Nature, том 341, P119 (1989); WH Zurek, Physics Review A, vol 40, p4731 (1989).
- ^ Марина Мейла, "Сравнение кластеризации по изменению информации", Теория обучения и ядерные машины (2003), т. . 2777, стр 173-187, DOI : 10.1007 / 978-3-540-45167-9_14 , Lecture Notes вкомпьютерных наук, ISBN 978-3-540-40720-1
дальнейшее чтение
- 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