Механика кластеризации аффинного распространения

Углубленное изучение и демонстрация Python

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

Образцы — это конкретные точки данных, которые служат представителями или прототипами для каждого кластера. По сути, образец — это точка данных в кластере, которая лучше всего суммирует или характеризует другие точки данных в этом кластере.

Каждая строка в визуализации кластеризации распространения сходства может соединять точку данных с соответствующим экземпляром, демонстрируя отношения между членами кластера и их репрезентативным экземпляром. В отличие от центроидов в других методах кластеризации, образцы представляют собой фактические точки данных в наборе данных. K-средние, хотя иногда и называют методом кластеризации на основе образцов, в этом отношении фундаментально отличаются от метода распространения сходства. В K-средних центроиды, представляющие кластеры, вычисляются на основе среднего значения точек данных внутри каждого кластера, и они могут не совпадать с фактическими точками данных. Это различие подчеркивает одно из ключевых различий между K-means и Affinity Propagation: в то время как Affinity Propagation выбирает образцы из существующих точек данных, K-mean вычисляет центроиды, которые могут не соответствовать какой-либо конкретной точке данных, что приводит к другому подходу к характеристике и образуя кластеры.

Кластеризация K-средних: введение
Исследование и реализация K-среднихblog.devgenius.io

Для набора N, состоящего из точек данных, его мощность обозначается N, так что N=|N|. Это означает, что N — общее количество точек данных в наборе. Индексы этих точек данных обозначаются n и m.

N: набор точек данных.
Н: количество баллов
n,m: индексы точек данных.
K: набор экземпляров
K: количество потенциальных экземпляров, K = |K|, K ≤ N
k, l: индексы потенциальных экземпляров.

По умолчанию мы можем предположить, что каждая точка считается потенциальным экземпляром. К = Н.

s обозначает сходство между точками. Кроме того, существует два типа сообщений. ρ — это сообщение, передаваемое от точки данных n потенциальному экземпляру, а α — это сообщение о доступности, отправленное от потенциального экземпляра k к точке данных n.

k(n): образец n. Если k является примером n, то k(n) = k.

Сходство

Сходство s(n, k) между двумя точками данных обычно определяется как отрицательное евклидово расстояние между ними. Однако в зависимости от характера данных можно использовать и другие меры расстояния.

Мера сходства показывает, насколько хорошо точка данных k может служить образцом для точки данных n. Более высокое значение сходства указывает на то, что две точки ближе или более похожи друг на друга.

Все сходства часто представляются в матричной форме: S = [s(n, k)]. S не обязательно должен быть симметричным.

Для каждой точки данных также существует концепция самоподобия s(n, n). Это значение имеет решающее значение, поскольку оно определяет потенциал точки данных в качестве образца. Его можно установить равным нулю или медиане (или значению, полученному из распределения) всех значений сходства, чтобы обеспечить разумное количество кластеров.

Целью алгоритма кластеризации распространения сходства является максимизация суммирования по каждой точке данных n сходства между n и его экземпляромk(n).

Чтобы точка данных считалась образцом для других точек данных, она сначала должна быть образцом для самой себя.

Мера сходства играет решающую роль в обновлениях сообщений об «ответственности» и «доступности», которые являются основой итеративного процесса распространения сходства. Эти сообщения обновляются на основе сходства и текущих оценок обязанностей и доступности.

Ответственность

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

Ответственность ρ(n, k), передаваемая от точки данных n к образцу-кандидату k, отражает накопленные данные о том, насколько хорошо подходит точка >k должен служить примером для точки n, принимая во внимание другие потенциальные образцы для n.

Он хранится в матрице N x K или N x N: R = [ρ(n, k)]. Его можно интерпретировать как логарифмические вероятности и инициализировать значением 0.

Для каждого n

Термин s(n, k) представляет сходство между точками данных n и k. Термин max находит максимальное значение среди всех потенциальных экземпляровl (исключая текущего кандидатаk). Для каждого потенциального экземпляра l, суммируется доступность α и сходство s.

Вычитая максимальное значение из сходства, мы, по сути, измеряем, насколько лучше (или хуже) k является образцом для n по сравнению с лучшим конкурирующим кандидатом.

Сообщение об ответственности играет ключевую роль в итеративном процессе алгоритма. Он обеспечивает обратную связь от точек данных к образцам-кандидатам об их пригодности. Если определенная точка k последовательно получает сообщения высокой ответственности от многих точек данных, она с большей вероятностью будет выбрана в качестве образца.

Высокое положительное значение ответственности от точки n до точки k указывает на то, что k особенно хорошо подходит в качестве образца для n, учитывая другие потенциальные экземпляры.

Доступность

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

Термин ρ(k, k) отвечает за то, что точка данных k является собственным экземпляром.

∑m!=n, kmax(0, ρ(m, k))term объединяет положительные обязательства, отправленные из других точек данных в сторону k, по существу обеспечивая поддержку поскольку k является образцом.

Сумма вычисляется по всем точкам данных m, за исключением текущей точки данных n и образца-кандидата k.

min(0, …) гарантирует, что значение доступности не превысит 0. Если сумма обязанностей (включая ответственность k перед самим собой) отрицательна, доступность будет отрицательным значением. В противном случае ему будет присвоено значение 0.

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

Полный процесс

Каждая точка данных рассматривается как потенциальный образец.
Матрицы ответственности и доступности инициализируются значением 0.
Алгоритм работает итеративно, при этом точки данных обмениваются сообщениями об ответственности и доступности до тех пор, пока не будет достигнута сходимость или не будет завершено заданное количество итераций.
На каждой итерации: Матрица ответственности обновляется на основе текущих значений сходства и доступности. Впоследствии матрица доступности обновляется на основе вновь вычисленных значений ответственности.
После обновления матриц на каждой итерации вычисляется сумма ответственности и доступности для каждой точки данных.
Для каждой точки данных n, если значение ρ(n, n) + α(n, n) положительное, то выбирается n как образец для себя. Это означает, что точка данных считает, что она должна быть образцом, и получила достаточно подтверждающих отзывов от других точек, чтобы поддержать это убеждение.
После определения образцов каждая точка данных, не являющаяся образцом, n присваивается образцу k, который максимизирует сумму ρ(n, k) + α(n , к). Это означает, что каждая точка, не являющаяся образцом, присваивается тому экземпляру, к которому она имеет наибольшее сходство.
Итерационный процесс останавливается, когда либо назначения образцов остаются неизменными в течение указанного количества итераций, либо когда достигается заранее определенное максимальное количество итераций.
В конце процесса алгоритм предоставляет набор образцов и присваивает этим образцам все остальные точки данных, эффективно разделяя данные на кластеры.

Реализация кода

Мы можем использовать Sklearn для применения кластеризации Affinity Propagation.

классsklearn.cluster.AffinityPropagation(*, damping=0.5, max_iter=200, convergence_iter=15, copy=True, preference=None, affinity='euclidean', verbose=False, random_state=None)

Параметры:

damping — это коэффициент от 0,5 до 1, который снижает влияние входящих сообщений при обновлении сообщений. Это помогает избежать числовых колебаний при обновлении сообщений.
max_iter — максимальное количество итераций.
convergence_iter — количество итераций без изменения количества оцениваемых кластеров, при котором сходимость прекращается. Если назначения кластеров остаются неизменными в течение этого количества последовательных итераций, алгоритм завершается.
copy копирует данные, если для него установлено значение True.
preference — это значение «предпочтения» для каждой точки данных. Если установлено значение None, используется медиана входных сходств. Это влияет на количество экземпляров, которые найдет алгоритм. Меньшее значение приводит к большему количеству кластеров.
affinity указывает, какую близость (меру сходства) использовать. euclidean — это отрицательный квадрат евклидова расстояния между точками данных. precomputed — это входные данные, предоставленные в виде заранее вычисленной матрицы сходства.

Во-первых, давайте сгенерируем несколько примеров данных, используя make_blobs.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import AffinityPropagation
from sklearn.datasets import make_blobs

centers = [[1, 1], [-1, -1], [1, -1]]
X, labels_true = make_blobs(n_samples=300, centers=centers, cluster_std=0.5, random_state=42)

plt.figure(figsize=(10, 6))
plt.scatter(X[:, 0], X[:, 1], c=labels_true, edgecolors='k', cmap=plt.cm.viridis)
plt.title('Generated Sample Data')
plt.xlabel('Feature 1')
plt.ylabel('Feature 2')
plt.grid(True)
plt.show()

Давайте теперь воспользуемся AffinityPropagation.

af = AffinityPropagation().fit(X)
cluster_centers_indices = af.cluster_centers_indices_
labels = af.labels_
labels

"""
array([ 6,  6,  1,  2,  9,  9, 11,  8, 12, 10, 13,  6, 11,  5, 11,  9, 13,
        8,  6,  3,  1,  0,  6,  1,  0, 10,  4,  2,  0, 10,  9,  3,  1,  1,
        1, 13,  3,  7, 10,  6,  7,  7,  4,  8,  5,  1,  0, 10, 11,  1, 12,
        6,  0,  2, 10,  7,  9, 13,  7,  5,  8,  7, 13,  7,  1, 10,  1, 12,
       11,  1,  3, 10,  6,  3,  1,  0,  9,  5,  6,  6,  3,  6,  6,  1,  5,
        4,  8,  5,  6, 13,  0,  3,  9, 11,  0,  1,  7,  6,  6, 13,  6,  6,
        2,  1, 12,  9,  2, 12, 11, 11,  7,  7,  0,  9,  4,  7,  5,  8, 11,
       11,  2,  6, 13,  6,  6,  6,  6,  1,  8,  6, 12, 10,  9,  1,  1,  7,
        8, 13,  0,  8,  3,  7,  9,  7, 12,  9,  5,  0,  2,  8,  2,  7, 10,
        5,  6,  9,  7,  0,  9,  4,  3, 13, 12,  6,  8,  9,  5,  6, 11, 11,
       11,  6,  7, 11, 11, 12,  1, 10, 10, 11,  3, 12,  0, 10,  5,  1,  7,
       11,  2, 10,  5,  9,  4,  9,  9,  3,  2,  8, 11,  4, 11,  3, 12, 13,
        7, 10,  4,  5,  1,  8,  1,  5,  3, 11, 12,  3,  1,  4, 12,  8,  6,
       11,  6,  4,  7,  2,  1,  3,  1, 11,  7,  2,  6,  7,  7,  2, 11,  3,
       11,  7,  2,  3,  4, 10,  9,  9,  2,  5,  5,  2,  5,  5,  6,  8,  9,
       11,  8,  0,  7,  5,  3,  3,  6,  6,  2,  2,  3, 11, 11,  1, 12, 12,
        6,  3,  3,  7,  2,  9,  0,  4,  3,  2,  4, 12,  2,  0, 12, 11, 13,
        7, 12,  5,  5,  9, 11,  2,  9,  3,  2, 12])

"""
len(cluster_centers_indices), cluster_centers_indices

"""
(14,
 array([ 21,  23,  27,  36,  42,  77,  97, 115, 128, 158, 205, 213, 271,
        288]))
"""

При конфигурации по умолчанию мы получили 14 разных кластеров.

plt.figure(figsize=(10, 6))
colors = ['r', 'g', 'b', 'c', 'm', 'y', 'k','r', 'g', 'b', 'c', 'm', 'y', 'k']
for k, col in zip(range(len(cluster_centers_indices)), colors):
    class_members = labels == k
    cluster_center = X[cluster_centers_indices[k]]
    plt.plot(X[class_members, 0], X[class_members, 1], col + '.')
    plt.plot(cluster_center[0], cluster_center[1], 'o', markerfacecolor=col, markeredgecolor='k', markersize=14)
    for x in X[class_members]:
        plt.plot([cluster_center[0], x[0]], [cluster_center[1], x[1]], col)

plt.title('Affinity Propagation Clustering')
plt.show()

Параметр preference в алгоритме распространения сходства играет решающую роль в определении количества экземпляров (или центров кластеров). Конкретно:

Более высокое (менее отрицательное или более положительное) значение preference повышает вероятность того, что точки данных станут образцами, что приводит к большему количеству кластеров.
Более низкое (более отрицательное) значение preference снижает вероятность того, что точки данных станут образцами, что приводит к меньшему количеству кластеров.

af = AffinityPropagation(preference=-50).fit(X)
cluster_centers_indices = af.cluster_centers_indices_
labels = af.labels_
len(cluster_centers_indices), cluster_centers_indices

# (3, array([ 55,  97, 153]))
plt.figure(figsize=(10, 6))
colors = ['r', 'g', 'b']
for k, col in zip(range(len(cluster_centers_indices)), colors):
    class_members = labels == k
    cluster_center = X[cluster_centers_indices[k]]
    plt.plot(X[class_members, 0], X[class_members, 1], col + '.')
    plt.plot(cluster_center[0], cluster_center[1], 'o', markerfacecolor=col, markeredgecolor='k', markersize=14)
    for x in X[class_members]:
        plt.plot([cluster_center[0], x[0]], [cluster_center[1], x[1]], col)

plt.title('Affinity Propagation Clustering')
plt.show()

Использование preferance=-50 уменьшило количество кластеров до 3.

Выбор правильного значения preference часто требует экспериментов. Для многих наборов данных установка preference на медиану (или иногда среднее значение) парных сходств (особенно при использовании евклидовых расстояний) может быть хорошей отправной точкой. Отсюда можно настроить значение в зависимости от желаемого количества кластеров или качества результатов кластеризации.

В заключение, Affinity Propagation выделяется как уникальный метод кластеризации, который работает без необходимости предварительного указания количества кластеров. Благодаря итеративному обмену сообщениями об «ответственности» и «доступности» между точками данных алгоритм эффективно идентифицирует образцы и формирует кластеры вокруг них.