python - 聚类结构 3D 数据

Question

假设我有许多对象(类似于蛋白质，但不完全相同)，每个对象都由一个包含 n 个 3D 坐标的向量表示。这些物体中的每一个都指向空间中的某个地方。可以通过使用 Kabsch Algorithm 对齐它们来计算它们的相似性。并计算对齐坐标的均方根偏差。

我的问题是，以提取人口最多的集群(即大多数结构所属的集群)的方式对大量这些结构进行聚类的推荐方法是什么。另外，有没有办法在 python 中执行此操作。举例来说，这是一组简单的非聚类结构(每个结构都由四个顶点的坐标表示):

然后是所需的聚类(使用两个聚类):

我已经尝试将所有结构与引用结构(即第一个结构)对齐，然后使用 Pycluster.kcluster 对引用和对齐坐标之间的距离执行 k-means，但是这看起来有点笨拙，而且效果不佳。每个集群中的结构最终不会彼此非常相似。理想情况下，这种聚类不会在差异向量上进行，而是在实际结构本身上进行，但结构具有维度 (n,3) 而不是 k-means 聚类所需的 (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，我认为它是一种降维形式)来加速它。

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