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

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

• 1 Алгоритм
• 2 Приложения
• 3 Программное обеспечение
• 4 Ссылки

Пусть x 1 - x n будет набором точек данных без каких-либо предположений об их внутренней структуре, и пусть s будет функцией, которая количественно определяет сходство между любыми двумя точками, такое, что s (i, j)>s (i, k) iff xiбольше похоже на x j, чем на x k. В этом примере использовался отрицательный квадрат расстояния двух точек данных, т.е. для точек x i и x k, $s\; (i,\; k)\; =\; -\; \Vert \; xi\; -\; xk\; \Vert \; 2\; \{\backslash \; displaystyle\; s\; (i,\; k)\; =\; -\; \backslash \; left\; \backslash \; |\; x\_\; \{i\}\; -x\_\; \{k\}\; \backslash \; right\; \backslash \; |\; ^\; \{2\}\}$

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

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

• Матрица «ответственности» R имеет значения r (i, k), которые количественно определяют, насколько хорошо -подходит x k, чтобы служить примером для x i по сравнению с другими примерами-кандидатами для x i.
• Матрица «доступности» A содержит значения a (i, k), которые представляют, насколько «уместно» для x i выбрать x k в качестве своего образца, принимая во внимание предпочтение других точек для x k в качестве примера.

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

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

$a\; (i,\; k)\; \leftarrow \; min\; (0,\; r\; (k,\; k)\; +\; \sum \; i\; \prime \; \notin \; \{i,\; k\}\; макс\; (0,\; р\; (я\; \text{'},\; к)))\; \{\backslash \; Displaystyle\; а\; (я,\; к)\; \backslash \; leftarrow\; \backslash \; мин\; \backslash \; влево\; (0,\; г\; (к,\; к)\; +\; \backslash \; сумма\; \_\; \{я\text{'}\; \backslash \; not\; \backslash \; in\; \backslash \; \{\; i,\; k\; \backslash \}\}\; \backslash \; max\; (0,\; r\; (i\; \text{'},\; k))\; \backslash \; right)\}$для $i\; \ne \; k\; \{\backslash \; displaystyle\; i\; \backslash \; neq\; k\}$и

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

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

Изобретатели распространения сродства показали, что он лучше подходит для определенных задач компьютерного зрения и вычислительной биологии, например, для кластеризации изображений человеческие лица и идентификация регулируемых транскриптов, чем k-среднее, даже когда k-среднее было разрешено много случайных перезапусков и инициализировано с использованием PCA. Было обнаружено исследование, сравнивающее распространение аффинности и марковскую кластеризацию при разделении Марковская кластеризация лучше справляется с этой проблемой. Для приложений интеллектуального анализа текста был предложен вариант с полууправлением.

• A Java включена в ELKI фрейм интеллектуального анализа данных ork.
• A Джулия реализация распространения аффинности содержится в пакете Clustering.jl от Julia Statistics.
• A Версия Python является частью библиотеки scikit-learn.
• Реализация R доступна в пакете "apcluster".

=== !!! == Знак равно <2>{\ Displaystyle (г (я, я) + а (я, я))>0} <2><3>{\ Displaystyle s (я, к) = - \ влево \ | x_ {я} -x_ {k} \ right \ | ^ {2}} <3><4>i \ neq k <4><5>r (i, k) \ leftarrow s (i, k) - \ max_ {k <5><6>a (i, k) \ leftarrow \ min \ left (0, r (k, k) + \ sum_ {i <6><7>{\ displaystyle s (i, i)} <7><8>a (k, k) \ leftarrow \ sum_ {i <8>html