三维聚类结构

Question

假设我有很多对象（类似于蛋白质，但不完全相同），每个对象都由n3d坐标向量表示。每一个物体都指向空间的某个地方。它们的相似性可以通过使用Kabsch Algorithm对齐并计算对齐坐标的均方根偏差来计算。在

我的问题是，以这样一种方式将大量的这些结构聚集在一起，以便提取出最密集的集群（即大多数结构所属的集群），推荐的方法是什么。另外，在python中是否有这样的方法呢。举个例子，下面是一组简单的未聚集结构（每个都由四个顶点的坐标表示）：

然后是所需的集群（使用两个集群）：

我尝试过将所有的结构与一个引用结构（即第一个结构）对齐，然后使用Pycluster.kcluster对引用和对齐坐标之间的距离执行k-means，但这似乎有点笨拙，效果不太好。每个集群中的结构最终不会彼此非常相似。理想情况下，这种聚类不是对差分向量进行的，而是对实际结构本身进行的，但是这些结构具有k均值聚类所需的维数（n，3），而不是（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）的所有顶点间距离。在

^{pr2}$

使用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)

{2美元^

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

我现在还不接受我的回答，因为我对如何处理这个简单问题的任何其他想法或想法感兴趣。在