聚类余弦相似度矩阵

Question

有关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

方阵可以是任何尺寸.我想获得最大化集群中元素之间的值的集群(我不知道有多少).即上面的例子我应该得到两个集群:

1. 乙
2. A,C,D

原因是因为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)

如您所见,它会返回您提到的群集.

该算法采用对应于最大特征值的输入矩阵的前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])