Распространение сродства - Affinity propagation

В статистика и сбор данных, распространение сродства (AP) - это алгоритм кластеризации основан на концепции «передачи сообщений» между точками данных.^[1]В отличие от алгоритмов кластеризации, таких как k-средства или же k-медоиды, распространение аффинности не требует определения или оценки количества кластеров перед запуском алгоритма. Похожий на k-medoids, распространение аффинности находит «образцы», элементы входного набора, которые представляют кластеры.^[1]

Алгоритм

Позволять Икс₁ через Икс_п быть набором точек данных без каких-либо предположений об их внутренней структуре, и пусть s - функция, которая количественно определяет сходство между любыми двумя точками, так что s(я, j) > s(я, k) если только Икс_я больше похоже на Икс_j чем Икс_k. В этом примере использовался отрицательный квадрат расстояния двух точек данных, т.е. для точек Икс_я и Икс_k, ${\displaystyle s(i,k)=-\left\|x_{i}-x_{k}\right\|^{2}}$^[1]

Диагональ s (т.е. ${\displaystyle s(i,i)}$) особенно важен, поскольку он представляет предпочтение экземпляра, означающее, насколько вероятно, что конкретный экземпляр станет образцом. Когда для всех входов установлено одинаковое значение, он контролирует, сколько классов генерирует алгоритм. Значение, близкое к минимально возможному сходству, дает меньше классов, в то время как значение, близкое или большее, чем максимально возможное сходство, дает много классов. Обычно он инициализируется средним подобием всех пар входных данных.

Алгоритм выполняется путем чередования двух этапов передачи сообщений, которые обновляют две матрицы:^[1]

• Матрица «ответственности» р имеет ценности р(я, k) которые определяют, насколько хорошо подходят Икс_k служить образцом для Икс_я, относительно других образцов-кандидатов на Икс_я.
• Матрица «доступности» А содержит значения а(я, k) которые представляют, насколько "подходящим" было бы для Икс_я подобрать Икс_k в качестве своего образца, учитывая предпочтение других точек Икс_k как образец.

Обе матрицы инициализируются всеми нулями и могут рассматриваться как логарифмическая вероятность таблицы. Затем алгоритм итеративно выполняет следующие обновления:

• Во-первых, рассылаются сообщения об ответственности: ${\displaystyle r(i,k)\leftarrow s(i,k)-\max _{k'\neq k}\left\{a(i,k')+s(i,k')\right\}}$
• Затем доступность обновляется по

${\displaystyle a(i,k)\leftarrow \min \left(0,r(k,k)+\sum _{i'\not \in \{i,k\}}\max(0,r(i',k))\right)}$ за ${\displaystyle i\neq k}$ и

${\displaystyle a(k,k)\leftarrow \sum _{i'\neq k}\max(0,r(i',k))}$.

Итерации выполняются до тех пор, пока либо границы кластера не останутся неизменными в течение нескольких итераций, либо не будет достигнуто некоторое заранее определенное количество (итераций). Образцы извлекаются из окончательных матриц, поскольку те, чья «ответственность + доступность» для себя положительна (т.е. ${\displaystyle (r(i,i)+a(i,i))>0}$).

Приложения

Изобретатели распространения аффинности показали, что это лучше для определенных задач компьютерного зрения и вычислительной биологии, например кластеризация изображений человеческих лиц и идентификация регулируемых транскриптов, чем k-средства,^[1] даже когда k-средство было разрешено много случайных перезапусков и инициализировано с помощью PCA.^[2]Исследование, сравнивающее распространение аффинности и Марковская кластеризация на график взаимодействия белков разделение обнаружило, что марковская кластеризация лучше подходит для решения этой проблемы.^[3] Предложен полууправляемый вариант для интеллектуальный анализ текста Приложения.^[4]

Программного обеспечения

• А Ява реализация включена в ELKI фреймворк интеллектуального анализа данных.
• А Юля реализация распространения аффинности содержится в пакете Julia Statistics Clustering.jl.
• А Python версия является частью scikit-learn библиотека.
• An р реализация доступна в пакете "apcluster".

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

1. Брендан Дж. Фрей; Делберт Дюк (2007). «Кластеризация путем передачи сообщений между точками данных». Наука. 315 (5814): 972–976. CiteSeerX  10.1.1.121.3145. Дои:10.1126 / science.1136800. PMID  17218491.
2. Делберт Дюк; Брендан Дж. Фрей (2007). Неметрическое распространение сходства для неконтролируемой категоризации изображений. Междунар. Конф. по компьютерному зрению. Дои:10.1109 / ICCV.2007.4408853.
3. Джеймс Власблом; Шошана Водак (2009). «Марковская кластеризация против распространения аффинности для разбиения графиков взаимодействия белков». BMC Bioinformatics. 10 (1): 99. Дои:10.1186/1471-2105-10-99. ЧВК  2682798. PMID  19331680.
4. Ренчу Гуань; Сяоху Ши; Маурицио Марчезе; Чен Ян; Янчунь Лян (2011). «Кластеризация текста с распространением родства семян». IEEE Transactions по разработке знаний и данных. 23 (4): 627–637. Дои:10.1109 / tkde.2010.144. HDL:11572/89884.