聚类结构3D数据

Question

比方说，我有许多对象（类似于蛋白质，但不完全），每个对象都由n个3D坐标的向量表示。这些对象中的每一个都面向太空中的某个地方。可以通过使用Kabsch Algorithm对齐它们并计算对齐坐标的均方根偏差来计算它们的相似性。

我的问题是，以这样一种方式聚集大量这些结构的建议方式是提取人口最多的聚类（即大多数结构所属的聚类）。另外，有没有办法在Python中做到这一点。通过举例的方式，这里有一个无足轻重组非集群结构（每个由四个顶点的坐标表示）：

然后将所需的聚类（使用两个簇）：

我试着将所有结构对齐到参考结构（即第一个结构），然后使用Pycluster.kcluster对参考和对齐坐标之间的距离执行k-means，但是这看起来有点笨拙，并且不会不行k很好。每个集群中的结构不会最终彼此非常相似。理想情况下，这种聚类不会在差异向量上完成，而是在实际结构本身上完成，但结构具有维数（n，3），而不是k均值聚类所需的（n，）。

我试过的其他选项是scipy.clustering.hierarchical。这似乎工作得很好，但我无法确定哪个群集的人数最多，因为通过移动到树的下一个分支，总能找到更多的群集。

任何想法或建议或想法关于不同的（已经在python中实现）聚类算法将不胜感激。

Answer 1

为了给我自己的问题提供一个介绍性答案，我建议可以使用形状中每个点之间的距离列表作为衡量指标来执行聚类。

让我们创建一些形状：

shapes = np.array([[[1,4],[4,2],[11,2],[14,0]], 
      [[4,5],[4,2],[11,2],[13,0]], 
      [[1,3],[4,2],[11,2],[14,1.5]], 
      [[3,5],[4,2],[10,7],[7,9]], 
      [[5,5],[4,2],[10,7],[6,6]]]) 

def random_rotation(): 
    theta = 3 * np.pi * np.random.random() 
    rotMatrix = numpy.array([[np.cos(theta), -np.sin(theta)], 
          [np.sin(theta), np.cos(theta)]]) 
    return rotMatrix 

new_shapes = [] 
for s in shapes: 
    rr = random_rotation() 
    new_shapes += [[list(rr.dot(p)) + [0] for p in s]] 
new_shapes = np.array(new_shapes) 

for i, s in enumerate(new_shapes): 
    plot(s[:,0], s[:,1], color='black') 
    text(np.mean(s[:,0]), np.mean(s[:,1]), str(i), fontsize=14) 

然后我们创建一些辅助功能和创建包含所有为每个形状（darray）的顶点间距离的阵列。

import itertools as it 

def vec_distance(v1, v2): 
    ''' 
    The distance between two vectors. 
    ''' 
    diff = v2 - v1 
    return math.sqrt(sum(diff * diff)) 

def distances(s): 
    ''' 
    Compute the distance array for a shape s. 
    ''' 
    ds = [vec_distance(p1, p2) for p1,p2 in it.combinations(s, r=2)] 

    return np.array(ds) 


# create an array of inter-shape distances for each shape 
darray = np.array([distances(s) for s in new_shapes]) 

使用Pycluster将它们分为两个群集。

import Pycluster as pc 

clust = pc.kcluster(darray,2) 
print clust 

并看到我们最终在第一个集群中有三个条目，而在另一个集群中有两个条目。

(array([0, 0, 0, 1, 1], dtype=int32), 4.576996142441375, 1) 

但是他们对应哪些形状？

import brewer2mpl 

dark2 = brewer2mpl.get_map('Dark2', 'qualitative', 4).mpl_colors 

for i,(s,c) in enumerate(zip(new_shapes, clust[0])): 
    plot(s[:,0], s[:,1], color=dark2[c]) 
    text(np.mean(s[:,0]), np.mean(s[:,1]), str(i), fontsize=14) 

看起来不错！问题是随着形状变大，距离数组相对于顶点的数量以二次方增长。我发现了一个描述这个问题的presentation，并提出了一些解决方案（比如我认为是降维的一种形式的SVD）来加速它。

我不打算接受我的答案，因为我对任何其他想法或关于如何解决这个简单问题的想法感兴趣。