WikiDer > Распространение сродства

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

Алгоритм

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

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

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

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

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

• Во-первых, рассылаются сообщения об ответственности: ${ Displaystyle г (я, к) leftarrow s (я, к) - макс _ {к ' neq k} влево {а (я, к') + s (я, к ') вправо }}$
• Затем доступность обновляется по

${ Displaystyle а (я, к) leftarrow мин влево (0, г (к, к) + сумма _ {я ' не в {я, к }} макс (0, г ( i ', k)) right)}$ за ${ Displaystyle я neq k}$ и

${ Displaystyle а (к, к) leftarrow сумма _ {я ' neq k} макс (0, г (я', к))}$.

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

Приложения

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

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

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

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