Матрица сходства косинусов кластеризации

Несколько вопросов о stackoverflow упоминают эту проблему, но я не нашел конкретного решения.

У меня есть квадратная матрица, которая состоит из сходств косинусов (значения от 0 до 1), например:

  |  A  |  B  |  C  |  D
A | 1.0 | 0.1 | 0.6 |  0.4
B | 0.1 | 1.0 | 0.1 |  0.2
C | 0.6 | 0.1 | 1.0 |  0.7
D | 0.4 | 0.2 | 0.7 |  1.0

Квадратная матрица может быть любого размера. Я хочу получить кластеры (я не знаю, сколько), которые максимизируют значения между элементами в кластере. То есть для приведенного выше примера я должен получить два кластера:

  • В
  • A, C, D

Причина в том, что C и D имеют самое высокое значение между ними, а A и C также имеют самое высокое значение между ними.

Элемент может находиться только в одном кластере.

Напомним, что это не важно для этой проблемы, но точность очень важна. Допустимо выводить три кластера: 1) B, 2) A, 3) C, D. Но не приемлемо выводить какое-либо решение, где B находится в кластере с другим элементом.

Я думаю, что диагональ (1.0) меня сбивает с толку. У моих данных, как минимум, есть как минимум один кластер из 2+ элементов, и я хочу найти как можно больше кластеров, не жертвуя точностью.

Мне нужно реализовать это на Python.

Ответы

Ответ 1

Вы можете легко сделать это, используя спектральную кластеризацию. Вы можете использовать готовые реализации, такие как один в sklearn или реализовать его самостоятельно. Это довольно простой алгоритм.

Вот фрагмент кода, выполняющий его в python с помощью sklearn:

import numpy as np
from sklearn.cluster import SpectralClustering
mat = np.matrix([[1.,.1,.6,.4],[.1,1.,.1,.2],[.6,.1,1.,.7],[.4,.2,.7,1.]])
SpectralClustering(2).fit_predict(mat)
>>> array([0, 1, 0, 0], dtype=int32)

Как вы можете видеть, он возвращает упомянутую кластеризацию.

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

from sklearn.cluster import KMeans
eigen_values, eigen_vectors = np.linalg.eigh(mat)
KMeans(n_clusters=2, init='k-means++').fit_predict(eigen_vectors[:, 2:4])
>>> array([0, 1, 0, 0], dtype=int32)

Обратите внимание, что реализация алгоритма в библиотеке sklearn может отличаться от моего. Пример, который я дал, - это самый простой способ сделать это. В Интернете есть несколько полезных руководств, в которых подробно описывается алгоритм спектральной кластеризации.

Для случаев, когда алгоритм должен вычислять количество кластеров сам по себе, вы можете использовать алгоритмы кластеризации на основе плотности, например DBSCAN:

from sklearn.cluster import DBSCAN
DBSCAN(min_samples=1).fit_predict(mat)
array([0, 1, 2, 2])