Affinity propagation

Affinity Propagation — алгоритм кластеризации на основе передачи сообщений между объектами, предложенный Б. Фреем и Д. Дьюком. **Основная идея:** Алгоритм рассматривает каждый объект как потенциальный exemplar — representative point, вокруг которого может сформироваться кластер. Между парами объектов итеративно передаются два типа сообщений: 1. **responsibility** $r(i,k)$ — насколько объект $k$ подходит на роль представителя для объекта $i$; 2. **availability** $a(i,k)$ — насколько объект $k$ готов быть представителем для объекта $i$. **Параметр preference:** Количество кластеров не задается напрямую. Оно регулируется через предпочтение объекта быть представителем. Чем выше preference, тем больше exemplars и тем больше итоговых кластеров. **Преимущества:** Метод может находить неравномерные группы и не требует заранее указывать число кластеров $k$. **Ограничения:** Требует матрицу попарного сходства, поэтому плохо масштабируется на очень большие выборки. На практике алгоритм полезен для задач, где важно выбрать реальные объекты-представители, а не абстрактные центроиды.