Python: 单链接聚类算法

Question

我刚开始学习Python，想找一个简单的单链接聚类算法的例子，这个算法是基于创建一个接近度矩阵，然后从中去掉一些节点。我知道有像numpy这样的库，但我想尽量不使用它们。
我在网上搜索过，但没找到简单到我能理解并且能自己复制的代码。

首先，从不相交的聚类开始，设定级别L(0) = 0，序列号m = 0。

在当前的聚类中，找到最相似的一对聚类，比如说对(r)，(s)，根据公式d[(r),(s)] = min d[(i),(j)]，这里的最小值是当前聚类中所有聚类对的距离。

增加序列号：m = m + 1。将聚类(r)和(s)合并成一个新的聚类，形成下一个聚类m。将这个聚类的级别设为L(m) = d[(r),(s)]。

更新接近度矩阵D，删除与聚类(r)和(s)对应的行和列，并添加与新形成的聚类对应的行和列。新聚类(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 = { "人类": "MGDVEKGKKIFIMKCSQCHTVEKGGKHKTGPNLHG", "黑猩猩": "MGDVEKGKKIFIMKCSQCHTVEKGGKHKTGPNLHG", "西方懒猴":"MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGXNLHG", "老鼠": "MGDAEAGKKIFVQKCAQCHTVEKGGKHKTGPNLWG", "兔子": "MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGPNLHG", "狗": "MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGPNLHG", "猪": "MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGPNLHG", " snapping turtle":"MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGPNLNG", "鳄鱼": "MGDVEKGKKIFVQKCAQCHTVEKGGKHKTGPNLHG", "蜜蜂": "AGDPEKGKKIFVQKCAQCHTIESGGKHKVGPNLYG", }

Answer 1

你可以看看一个叫做scipy的包，它里面有很多层次聚类的算法（可以在scipy.cluster.hierarchy找到）。你可以在scipy.spatial模块里找到一个叫做pdist的函数。

从那里你应该能找到很多不错的使用示例。

详细信息可以查看这个链接：http://docs.scipy.org/doc/scipy/reference/cluster.hierarchy.html