单链接聚类

Question

我想用OpenCV来做单链聚类。我的情况是：

• 有成百上千个特征向量（每个向量的维度可以达到大约800个特征）。
• 聚类的数量是未知的（可能会远远少于向量的数量）。
• 有一个固定的相似性阈值E - 如果两个向量之间的l1范数小于E，那么这两个向量应该在同一个聚类里。
• 我不需要聚类内部的向量都很紧凑。也就是说，我不要求聚类里的所有向量都彼此相距小于E。这样可能会形成很长的“链”，但我对此没问题。

我试过用K均值聚类，但因为我不知道聚类的数量，所以这方法不太适用。我可以做迭代的K均值聚类，寻找最佳的K值，但这听起来效率不高。有没有更合适的聚类算法可以在OpenCV中使用呢？

理想情况下，我需要类似于SLINK算法的东西，因为这是我目前正在尝试实现的论文中提到的。我可以选择直接实现SLINK（这有点麻烦，因为需要调试和测试），或者寻找一个现成的类似算法。

有什么建议吗？

Answer 1

我建议你根据相似度的阈值来构建一个图，然后找到连通分量。一旦你构建了这个图，找到连通分量就会变得相对简单和高效。如果你喜欢的话，NetworkX已经有一个用来找连通分量的函数。

Answer 2

我最后自己实现了一个方案：

import cv
def main():
    import sys
    x = cv.Load(sys.argv[1])
    epsilon = float(sys.argv[2])
    y = cv.CloneImage(x)
    labels = range(x.height)
    tmp = cv.CreateImage((x.width, 1), x.depth, x.nChannels)
    for i in range(x.height):
        cv.SetImageROI(x, (0, i, x.width, 1))
        for j in range(i+1, x.height):
            cv.SetImageROI(y, (0, j, x.width, 1))
            cv.AbsDiff(x, y, tmp)
            dist, _, _, _ = cv.Avg(tmp)
            if dist < epsilon:
                for k, lbl in enumerate(labels):
                    if lbl == j:
                        labels[k] = i

    for i, lbl in enumerate(labels):
        print i, lbl

if __name__ == '__main__':
    main()

x 是一个 N x M 的矩阵，里面包含了 N 个向量。每个向量的维度是 M。这个方法主要是比较每一对向量，使用的是 L1 范数，如果它们的差值小于 epsilon，就认为这对向量是相同的。这个算法速度很慢——复杂度是 O(N^3)，不过目前对我来说已经足够用了。