单链接聚类

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向量的N x M矩阵。向量的维数是M。它基本上使用 L1 范数比较每对向量，如果它们的差异小于 epsilon，则认为一对向量是相同的。这个算法非常慢 --- O(N^3)，但目前对我来说已经足够了。