Scipy分层聚类适当的链接方法

Question

抱歉，因为我昨天问了一个类似的问题，但我觉得我的问题缺乏内容，希望现在能更容易理解

我有一个个体间成对距离的对称矩阵（见下文），我想以一种方式对个体组进行聚类，使一个集群的所有成员的成对距离为零。我使用不同的链接方法和聚类标准应用了scipy.cluster.hierarchy，但没有得到预期的结果。在下面的例子中，我认为ind5不应该是集群#1的一部分，因为它到ind9的距离是1而不是0

from scipy.cluster.hierarchy import linkage, fcluster
from scipy.spatial.distance import squareform
import numpy as np
import pandas as pd

df = pd.read_csv(infile1, sep = '\t', index_col = 0)
print(df)

      ind1  ind2  ind3  ind4  ind5  ind6  ind7  ind8  ind9
ind1     0    29    27     1     2     1     2     1     1
ind2    29     0     2    30    31    29    31    30    30
ind3    27     2     0    28    29    27    29    28    28
ind4     1    30    28     0     0     0     1     2     0
ind5     2    31    29     0     0     0     2     2     1
ind6     1    29    27     0     0     0     1     2     0
ind7     2    31    29     1     2     1     0     3     1
ind8     1    30    28     2     2     2     3     0     2
ind9     1    30    28     0     1     0     1     2     0

X = squareform(df.to_numpy())
print(X)

[29 27  1  2  1  2  1  1  2 30 31 29 31 30 30 28 29 27 29 28 28  0  0  1
  2  0  0  2  2  1  1  2  0  3  1  2]

Z = linkage(X, 'single')
print(Z)

[[ 3.  4.  0.  2.]
 [ 5.  9.  0.  3.]
 [ 8. 10.  0.  4.]
 [ 0. 11.  1.  5.]
 [ 6. 12.  1.  6.]
 [ 7. 13.  1.  7.]
 [ 1.  2.  2.  2.]
 [14. 15. 27.  9.]]

max_d = 0
clusters = fcluster(Z, max_d, criterion='distance')
sample_list = df.index.to_list()
clust_name_list = clusters.tolist()
result = pd.DataFrame({'Inds': sample_list, 'Clusters': clust_name_list})
print(result)

   Inds  Clusters
0  ind1         2
1  ind2         5
2  ind3         6
3  ind4         1
4  ind5         1
5  ind6         1
6  ind7         3
7  ind8         4
8  ind9         1

我希望更熟悉这些方法的任何人都能提出建议，是否有任何链接方法可以将距离大于；0到群集中至少一个其他元素

谢谢你的帮助

冈萨洛

Answer 1

你的解决方案是正确的

您将获得以下群集：

• 簇1，元素ind4、ind5、ind6和ind9（彼此之间的距离为0）
• 带有元素ind1
• 带有元素ind7
• 带有元素ind8
• 带有元素ind2
• 带有元素ind3

根据需要，只有距离为0的图元才会聚集在簇1中。簇2到簇6是简并簇，具有单个孤立元素

让我们修改距离，以便创建更合适的簇：

X = np.array([ 0, 27,  1,  2,  1,  2,  1,  1,
                   2, 30, 31, 29, 31, 30, 30,
                      28, 29, 27, 29, 28, 28,
                           0,  0,  1,  2,  0,
                               0,  2,  2,  1,
                                   1,  2,  0,
                                       0,  1,
                                           2])
Z = linkage(X, 'single')
max_d = 0
clusters = fcluster(Z, max_d, criterion='distance')
print("Clusters:", clusters)
for cluster_id in np.unique(clusters):
    members = np.where(clusters == cluster_id)[0]
    print(f"Cluster {cluster_id} has members {members}")

获取：

Clusters: [2 2 4 3 3 3 1 1 3]
Cluster 1 has members [6 7]
Cluster 2 has members [0 1]
Cluster 3 has members [3 4 5 8]
Cluster 4 has members [2]

Answer 2

您可以将问题重新解释为graph中的问题查找cliques。通过将距离0解释为在两个节点之间创建边，可以从距离矩阵中获得图形。一旦你有了这个图，你就可以使用networkx（或者其他一些图论库）在图中找到派系。图中的派系将是一组节点，其中所有派系中的成对距离为0

这是您的距离矩阵（但请注意，您的距离不满足三角形不等式）：

In [136]: D
Out[136]: 
array([[ 0, 29, 27,  1,  2,  1,  2,  1,  1],
       [29,  0,  2, 30, 31, 29, 31, 30, 30],
       [27,  2,  0, 28, 29, 27, 29, 28, 28],
       [ 1, 30, 28,  0,  0,  0,  1,  2,  0],
       [ 2, 31, 29,  0,  0,  0,  2,  2,  1],
       [ 1, 29, 27,  0,  0,  0,  1,  2,  0],
       [ 2, 31, 29,  1,  2,  1,  0,  3,  1],
       [ 1, 30, 28,  2,  2,  2,  3,  0,  2],
       [ 1, 30, 28,  0,  1,  0,  1,  2,  0]])

将距离矩阵转换为邻接矩阵A：

In [137]: A = D == 0

In [138]: A.astype(int)  # Display as integers for a more compact output.
Out[138]: 
array([[1, 0, 0, 0, 0, 0, 0, 0, 0],
       [0, 1, 0, 0, 0, 0, 0, 0, 0],
       [0, 0, 1, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 1, 1, 1, 0, 0, 1],
       [0, 0, 0, 1, 1, 1, 0, 0, 0],
       [0, 0, 0, 1, 1, 1, 0, 0, 1],
       [0, 0, 0, 0, 0, 0, 1, 0, 0],
       [0, 0, 0, 0, 0, 0, 0, 1, 0],
       [0, 0, 0, 1, 0, 1, 0, 0, 1]])

创建networkx图G，并用^{}查找派系：

In [139]: import networkx as nx

In [140]: G = nx.Graph(A)

In [141]: cliques = nx.find_cliques(G)

In [142]: list(cliques)
Out[142]: [[0], [1], [2], [3, 5, 8], [3, 5, 4], [6], [7]]

（列表中的值是索引；例如，集团[2]对应于标签集['ind3']。）

请注意，有两个非平凡的派系，[3,5,8]和[3,5,4]，其中3和5都出现。这是距离具有此异常数据的结果：距离（ind5，ind4）=0，距离（ind4，ind9）=0，但距离（ind5，ind9）=1（即triangle inequality不满足）。因此，根据您对“集群”的定义，有两种可能的非平凡集群：[ind4，ind5，ind9]或[ind4，ind5，ind6]

最后，请注意networkx documentation中的警告：“在图中查找最大团是NP完全问题，因此大多数算法的运行时间都是指数级的”。如果距离矩阵很大，则此计算可能需要很长时间