如何比较集群？

Question

希望可以用Python完成！我在同一份数据上使用了两个聚类程序，现在有来自这两个程序的聚类文件。我重新格式化了文件，使其看起来像这样：

Cluster 0:
Brucellaceae(10)
    Brucella(10)
        abortus(1)
        canis(1)
        ceti(1)
        inopinata(1)
        melitensis(1)
        microti(1)
        neotomae(1)
        ovis(1)
        pinnipedialis(1)
        suis(1)
Cluster 1:
    Streptomycetaceae(28)
        Streptomyces(28)
            achromogenes(1)
            albaduncus(1)
            anthocyanicus(1)

etc.

这些文件包含细菌物种信息。我有聚类号（Cluster 0），下面是“家族”（Brucellaceae）和该家族中细菌数量（10）。在此之下是该家族中的属（名称后跟数字，Brucella(10)），最后是每个属中的物种（abortus(1)等）。

我的问题是：我有两个这样格式的文件，并想编写一个程序来查找两者之间的差异。唯一的问题是这两个程序以不同的方式进行聚类，因此即使实际的“聚类号”不同，两个聚类也可能是相同的（因此，在一个文件中，聚类1的内容可能与另一个文件中的聚类43匹配，唯一的区别是实际的聚类号）。所以我需要忽略聚类号，关注聚类内容。

有没有办法比较这两个文件以查看差异？是否可能？任何想法都将非常感激！

- Jen

---

将其解析为类并比较该类的对象。 - Henrik Andersson

@TimPietzcker 是的，每个群集中可能有多个家族。 - Jen

@MarkusUnterwaditzer 我研究了diff，但我担心它不具备忽略聚类编号所需的灵活性。 - Jen

它们是行为和数据的容器。 - Henrik Andersson

你看过聚类分析的维基百科页面吗？它讨论了外部评估指标，用于比较两个聚类。 - Has QUIT--Anony-Mousse

Answer 1

仅供帮助，因为我看到评论中有很多不同的答案，我将给你提供一个非常简单的脚本实现，你可以从这里开始。

请注意，这个脚本并不能回答你的完整问题，但是指向了评论中的其中一个方向。

通常如果你没有经验，我建议去学习Python（无论如何，我会在答案底部加入一些链接）

现在进入有趣的部分吧！ :)

class Cluster(object):
  '''
  This is a class that will contain your information about the Clusters.
  '''
  def __init__(self, number):
    '''
    This is what some languages call a constructor, but it's not.
    This method initializes the properties with values from the method call.
    '''
    self.cluster_number = number
    self.family_name = None
    self.bacteria_name = None
    self.bacteria = []

#This part below isn't a part of the class, this is the actual script.
with open('bacteria.txt', 'r') as file:
  cluster = None
  clusters = []
  for index, line in enumerate(file):
    if line.startswith('Cluster'):
      cluster = Cluster(index)
      clusters.append(cluster)
    else:
      if not cluster.family_name:
        cluster.family_name = line
      elif not cluster.bacteria_name:
        cluster.bacteria_name = line
      else:
        cluster.bacteria.append(line)

我尽力将此内容变得简单易懂，没有花哨的东西，适用于Python 2.7.2。您可以将此文件复制到.py文件中，并直接从命令行运行python bacteria.py，例如。

希望这有所帮助，如果您有任何问题，请随时访问我们的Python聊天室！ :)

链接：

http://learnpythonthehardway.org/

http://www.diveintopython.net/

http://docs.python.org/2/tutorial/inputoutput.html

检查列表中的所有元素是否相同

在使用Python的集合差异时保留顺序

- Henrik Andersson

Answer 2

给定：

file1 = '''Cluster 0:
 giant(2)
  red(2)
   brick(1)
   apple(1)
Cluster 1:
 tiny(3)
  green(1)
   dot(1)
  blue(2)
   flower(1)
   candy(1)'''.split('\n')
file2 = '''Cluster 18:
 giant(2)
  red(2)
   brick(1)
   tomato(1)
Cluster 19:
 tiny(2)
  blue(2)
   flower(1)
   candy(1)'''.split('\n')

这是您需要的吗？

def parse_file(open_file):
    result = []

    for line in open_file:
        indent_level = len(line) - len(line.lstrip())
        if indent_level == 0:
            levels = ['','','']
        item = line.lstrip().split('(', 1)[0]
        levels[indent_level - 1] = item
        if indent_level == 3:
            result.append('.'.join(levels))
    return result

data1 = set(parse_file(file1))
data2 = set(parse_file(file2))

differences = [
    ('common elements', data1 & data2),
    ('missing from file2', data1 - data2),
    ('missing from file1', data2 - data1) ]

查看差异：

for desc, items in differences:
    print desc
    print 
    for item in items:
        print '\t' + item
    print

打印

common elements

    giant.red.brick
    tiny.blue.candy
    tiny.blue.flower

missing from file2

    tiny.green.dot
    giant.red.apple

missing from file1

    giant.red.tomato

- Steven Rumbalski

---

尽管我个人更希望看到一些更具挑战性的问题，但对于一个好的解决方案，我还是要点赞的 ;) - Henrik Andersson

感谢您发布这个答案！这已经接近我所需要的了。问题是，当我运行它时，所有内容都显示在“共同元素”下，因为两个文件具有完全相同的内容，只是排序方式不同（明白吗？）。例如，在我的第一个文件中，Cluster 4 包含细菌 Sphingomonadaceae.Blastomonas.natatoria 和 Sphingomonadaceae.Sphingomonas.ursincola。在我的第二个文件中，这两种细菌位于不同的簇中（11和23）。所以我想得到这个变化的通知。希望这讲得清楚！ - Jen

Answer 3

你需要编写一些代码来解析文件。如果忽略集合，你应该能够根据缩进区分家族、属和物种。

最简单的方法是定义一个命名元组：

import collections
Bacterium = collections.namedtuple('Bacterium', ['family', 'genera', 'species'])

您可以像这样创建此对象的实例：

b = Bacterium('Brucellaceae', 'Brucella', 'canis')

你的解析器应逐行读取文件，并设置家族和属。如果它找到一个物种，它应该将一种细菌添加到列表中。

with open('cluster0.txt', 'r') as infile:
    lines = infile.readlines()
family = None
genera = None
bacteria = []
for line in lines:
    # set family and genera.
    # if you detect a bacterium:
    bacteria.append(Bacterium(family, genera, species))

一旦你有了每个文件或聚类中所有细菌的列表，你可以像这样从所有细菌中进行选择：

s = [b for b in bacteria if b.genera == 'Streptomycetaceae']

- Roland Smith

Answer 4

比较两个聚类并不是一件容易的事情，重新发明轮子很可能不会成功。请查看此软件包，其中包含许多不同的聚类相似度指标，并且可以比较树状图（您拥有的数据结构）。

该库名为CluSim，可在此处找到： https://github.com/Hoosier-Clusters/clusim/

- ircecho

---

请提供链接中的一些基本细节，因为链接在未来很可能会过期或重定向。 - Abhishek Gurjar

Answer 5

在Stackoverflow学到了很多东西之后，我终于有机会回馈社区了！与迄今为止提供的方法不同的一种方法是重新标记聚类以最大化对齐，然后比较变得容易。例如，如果一个算法将标签分配给六个项目集合，如L1=[0,0,1,1,2,2]，另一个算法将L2=[2,2,0,0,1,1]分配给它们，您希望这两个标签分配等效，因为L1和L2本质上是相同地将项目分割成聚类。这种方法重新标记L2以最大化对齐，在上面的示例中，将导致L2==L1。

我在"Menéndez, Héctor D. A genetic approach to the graph and spectral clustering problem. MS thesis. 2012."中找到了解决此问题的方法，并且以下是使用numpy在Python中的实现。我对Python相对较新，因此可能有更好的实现方式，但我认为这可以完成工作：

def alignClusters(clstr1,clstr2):
"""Given 2 cluster assignments, this funciton will rename the second to 
   maximize alignment of elements within each cluster. This method is 
   described in in Menéndez, Héctor D. A genetic approach to the graph and 
   spectral clustering problem. MS thesis. 2012. (Assumes cluster labels
   are consecutive integers starting with zero)

   INPUTS:
   clstr1 - The first clustering assignment
   clstr2 - The second clustering assignment

   OUTPUTS:
   clstr2_temp - The second clustering assignment with clusters renumbered to
   maximize alignment with the first clustering assignment """
K = np.max(clstr1)+1
simdist = np.zeros((K,K))

for i in range(K):
    for j in range(K):
        dcix = clstr1==i
        dcjx = clstr2==j
        dd = np.dot(dcix.astype(int),dcjx.astype(int))
        simdist[i,j] = (dd/np.sum(dcix!=0) + dd/np.sum(dcjx!=0))/2
mask = np.zeros((K,K))
for i in range(K):
    simdist_vec = np.reshape(simdist.T,(K**2,1))
    I = np.argmax(simdist_vec)
    xy = np.unravel_index(I,simdist.shape,order='F')
    x = xy[0]
    y = xy[1]
    mask[x,y] = 1
    simdist[x,:] = 0
    simdist[:,y] = 0
swapIJ = np.unravel_index(np.where(mask.T),simdist.shape,order='F')
swapI = swapIJ[0][1,:]
swapJ = swapIJ[0][0,:]
clstr2_temp = np.copy(clstr2)
for k in range(swapI.shape[0]):
    swapj = [swapJ[k]==i for i in clstr2]
    clstr2_temp[swapj] = swapI[k]
return clstr2_temp

- Larry522