聚类余弦相似度矩阵

Question

Whosebug上的几个问题都提到了这个问题，但是一直没找到具体的解决方法

我有一个由余弦相似度（值介于 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

方阵可以是任意大小。我想获得最大化集群中元素之间的值的集群（我不知道有多少）。 IE。对于上面的例子，我应该得到两个集群：

B
甲、丙、丁

因为C&D的值最高，A&C的值也最高

一个项目只能在一个集群中。

对于这个问题来说召回率不是那么重要，但是精度非常重要。输出三个集群是可以接受的：1) B, 2) A, 3) C, D。但是输出任何 B 与另一个元素在一个簇中的解决方案是不可接受的。

我认为对角线 (1.0) 让我感到困惑。我的数据保证至少有一个 2+ 元素的簇，我想在不牺牲精度的情况下找到尽可能多的簇。

我将不得不在 Python 中实现它。

Answer 1

您可以使用谱聚类轻松地做到这一点。您可以使用现成的实现，例如 sklearn 中的实现，也可以自己实现。这是一个相当简单的算法。

这是一段使用 sklearn 在 python 中执行的代码：

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)

如您所见returns您提到的聚类。

该算法取输入矩阵中最大特征值对应的前 k 个特征向量，然后在新矩阵上运行 k-mean 算法。这是为您的矩阵执行此操作的简单代码：

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])

聚类余弦相似度矩阵

Clustering cosine similarity matrix

python

math

cluster-analysis

data-mining

scikit-learn