Python:单链接聚类算法

Question

我是 Python 的新手，我正在寻找一个简单的单链接聚类 python 算法示例，该算法基于创建邻近矩阵并从中删除节点。我知道有像 numpy 这样的包，但我宁愿避免使用它们。
我在网上搜索过，但找不到任何足够简单的代码，以便能够理解以便以后自己复制它。

从级别 L(0) = 0 和序列号 m = 0 的不相交聚类开始。

根据 d[(r),(s)] = min d[(i),(j)] 找到当前聚类中最相似的一对簇，比如 pair (r), (s)，其中最小值遍及当前聚类中的所有聚类对。

递增序列号:m = m + 1。将簇 (r) 和 (s) 合并为一个簇，形成下一个簇 m。将此聚类的级别设置为 L(m) = d[(r),(s)]

通过删除与簇 (r) 和 (s) 对应的行和列并添加与新形成的簇对应的行和列来更新邻近矩阵 D。表示为 (r,s) 的新集群和旧集群 (k) 之间的接近度定义为 d[(k), (r,s)] = min d[(k),(r)], d[( k),(s)].

如果所有对象都在一个簇中，则停止。否则，转到步骤 2。

这些是维基百科中描述的步骤。我已经创建了距离矩阵，但不确定如何从那里继续。

这是我目前所拥有的:

比较

def comparison(protein1, protein2): 

  l = [i for i in range(len(protein1)) if protein1[i] != protein2[i]] 

  return len(l)

创建矩阵

def matrix (r1,r2):

  r = [] 
  for p1 in proteins: 
    r2 = [] 
    for p2 in proteins: 
      r2 += [comparison(p1, p2)] 
    r += [r2] 
  return r

这些是我要比较的序列:

seqlist = { "Human": "MGDVEKGKKIFIMKCSQCHTVEKGGKHKTGPNLHG", "Chimpanzee": "MGDVEKGKKIFIMKCSQCHTVEKGGKHKTGPNLHG", "Western tarsier":"MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGXNLHG", "Mouse": "MGDAEAGKKIFVQKCAQCHTVEKGGKHKTGPNLWG", "Rabbit": "MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGPNLHG", "Dog": "MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGPNLHG", "Pig": "MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGPNLHG", "Snapping turtle":"MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGPNLNG", "Alligator": "MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGPNLHG", "Honeybee": "AGDPEKGKKIFVQKCAQCHTIESGGKHKVGPNLYG", }

Answer 1

您应该查看包 scipy，它实现了多个层次聚类算法(参见 scipy.cluster.hierarchy)。在 scipy.spatial 模块中查找函数 pdist。

您应该能够从那里获得很多不错的用法示例。

参见 http://docs.scipy.org/doc/scipy/reference/cluster.hierarchy.html