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

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

Алгоритм

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

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

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

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

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

Сначала обновления об ответственности рассылаются: $r(i,k)\gets s(i,k)-\max _{k'\neq k}{\left\{a(i,k')+s(i,k')\right\}}$
Затем доступность обновляется $a(i,k)\gets \min {\left(0,r(k,k)+\sum _{i'\not \in \{i,k\}}\max(0,r(i',k))\right)}\quad {\text{ for }}i\neq k$ и $a(k,k)\leftarrow \sum _{i'\neq k}\max(0,r(i',k)).$

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

Приложения

Изобретатели метода распространения аффинности показали, что он лучше подходит для некоторых задач компьютерного зрения и вычислительной биологии , например, для кластеризации изображений человеческих лиц и идентификации регулируемых транскриптов, чем $k$ -средние. ^[1] даже когда $k$ -means было разрешено множество случайных перезапусков и инициализировано с использованием PCA . ^[2]Исследование, сравнивающее распространение аффинности и марковскую кластеризацию при разделении графа взаимодействия белков, показало, что марковская кластеризация лучше справляется с этой проблемой. ^[3] был предложен полуконтролируемый вариант Для приложений интеллектуального анализа текста . ^[4] Еще одно недавнее применение было в экономике, когда распространение аффинности использовалось для обнаружения некоторых временных закономерностей в мультипликаторах выпуска экономики США в период с 1997 по 2017 год. ^[5]

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

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

Ссылки

^ Jump up to: ^а ^б ^с ^д ^и Брендан Дж. Фрей; Делберт Дуек (2007). «Кластеризация путем передачи сообщений между точками данных». Наука . 315 (5814): 972–976. Бибкод : 2007Sci...315..972F . CiteSeerX 10.1.1.121.3145 . дои : 10.1126/science.1136800 . ПМИД 17218491 . S2CID 6502291 .
^ Делберт Дуек; Брендан Дж. Фрей (2007). Неметрическое распространение сходства для неконтролируемой категоризации изображений . Международная конференция. по компьютерному зрению. дои : 10.1109/ICCV.2007.4408853 .
^ Джеймс Власблом; Шошана Водак (2009). «Марковская кластеризация и распространение аффинности для разделения графов взаимодействия белков» . БМК Биоинформатика . 10 (1): 99. дои : 10.1186/1471-2105-10-99 . ПМЦ 2682798 . ПМИД 19331680 .
^ Ренчу Гуань; Сяоху Ши; Маурицио Маркезе; Чэнь Ян; Яньчунь Лян (2011). «Кластеризация текста с распространением сродства семян». Транзакции IEEE по знаниям и инженерии данных . 23 (4): 627–637. дои : 10.1109/tkde.2010.144 . hdl : 11572/89884 . S2CID 14053903 .
^ Алмейда, Лукас Миланес де Лима; Баланко, Пауло Антонио де Фрейтас (01.06.2020). «Применение многомерного анализа как дополнительного инструмента в исследованиях структурных изменений: пример мультипликаторов в экономике США» . Структурные изменения и экономическая динамика . 53 : 189–207. doi : 10.1016/j.strueco.2020.02.006 . ISSN 0954-349X . S2CID 216406772 .

[science-1] Jump up to: ^а ^б ^с ^д ^и Брендан Дж. Фрей; Делберт Дуек (2007). «Кластеризация путем передачи сообщений между точками данных». Наука . 315 (5814): 972–976. Бибкод : 2007Sci...315..972F . CiteSeerX 10.1.1.121.3145 . дои : 10.1126/science.1136800 . ПМИД 17218491 . S2CID 6502291 .

[2] Делберт Дуек; Брендан Дж. Фрей (2007). Неметрическое распространение сходства для неконтролируемой категоризации изображений . Международная конференция. по компьютерному зрению. дои : 10.1109/ICCV.2007.4408853 .

[3] Джеймс Власблом; Шошана Водак (2009). «Марковская кластеризация и распространение аффинности для разделения графов взаимодействия белков» . БМК Биоинформатика . 10 (1): 99. дои : 10.1186/1471-2105-10-99 . ПМЦ 2682798 . ПМИД 19331680 .

[4] Ренчу Гуань; Сяоху Ши; Маурицио Маркезе; Чэнь Ян; Яньчунь Лян (2011). «Кластеризация текста с распространением сродства семян». Транзакции IEEE по знаниям и инженерии данных . 23 (4): 627–637. дои : 10.1109/tkde.2010.144 . hdl : 11572/89884 . S2CID 14053903 .

[5] Алмейда, Лукас Миланес де Лима; Баланко, Пауло Антонио де Фрейтас (01.06.2020). «Применение многомерного анализа как дополнительного инструмента в исследованиях структурных изменений: пример мультипликаторов в экономике США» . Структурные изменения и экономическая динамика . 53 : 189–207. doi : 10.1016/j.strueco.2020.02.006 . ISSN 0954-349X . S2CID 216406772 .

[1]

[2]

[3]

[4]

[5]