在Rank-Order Clustering算法中实现有效的图数据结构以维护簇距离

Question

我正在尝试实现Rank-Order Clustering,这是从头开始的文章(这是一种凝聚聚类)算法的链接.我已经阅读了这篇论文(很多次)并且我有一个正在运行的实现,尽管它比我预期的要慢很多.

这是我的Github 的链接,其中包含下载和运行Jupyter Notebook的说明.

算法:

算法1基于秩序距离的聚类

输入:
  N个面,秩 - 顺序距离阈值 t .
输出:
  集群集C和"未分组"集群 C _un.
1:  通过让每个面都是单个元素簇来初始化簇C = { C ₁,C ₂,... C _N }
.
2:重复
3:   为所有一对Ç _Ĵ和Ç _我在Ç 做
4:计算距离d ^{- [R} ( Ç _我,Ç _Ĵ)由(4)和 d ^Ñ(Ç _我,Ç _Ĵ通过)(5).
5:    如果 d ^{- [R} (Ç _我,Ç _Ĵ)< 吨和d ^Ñ(Ç _我,Ç _Ĵ)<1 则
6:记⟨ Ç _我,Ç _Ĵ ⟩作为候选合并对.
7:    结束如果
8:   结束
9:在所有候选合并对上进行"传递"合并.
  (例如,Ç _我,Ç _Ĵ,Ç _ķ被合并
  如果⟨ Ç _我,Ç _Ĵ ⟩和⟨ Ç _Ĵ,Ç _ķ ⟩是候选合并对.)
10:更新Ç由簇之间和绝对距离(3).
11:直到没有合并发生
12:将C中的所有单元素集群移动到"未分组"的面集群C _un.
13:返回C和C _un.

我的实施:

我已经定义了一个Cluster这样的类:

class Cluster:
    def __init__(self):
        self.faces = list()
        self.absolute_distance_neighbours = None

Face像这样的一个类:

class Face:
    def __init__(self, embedding):
        self.embedding = embedding # a point in 128 dimensional space
        self.absolute_distance_neighbours = None

我还实现了查找等级距离(D^R(C_i, C_j))和使用的归一化距离(D^N(C_i, C_j)),step 4因此可以认为这些是理所当然的.

这是我在两个集群之间找到最接近的绝对距离的实现:

def find_nearest_distance_between_clusters(cluster1, cluster2):
    nearest_distance = sys.float_info.max
    for face1 in cluster1.faces:
        for face2 in cluster2.faces:
            distance = np.linalg.norm(face1.embedding - face2.embedding, ord = 1)

            if distance < nearest_distance: 
                nearest_distance = distance

            # If there is a distance of 0 then there is no need to continue
            if distance == 0:
                return(0)
    return(nearest_distance)


def assign_absolute_distance_neighbours_for_clusters(clusters, N = 20):
    for i, cluster1 in enumerate(clusters):
        nearest_neighbours = []
        for j, cluster2 in enumerate(clusters):
            distance = find_nearest_distance_between_clusters(cluster1, cluster2)    
            neighbour = Neighbour(cluster2, distance)
            nearest_neighbours.append(neighbour)
        nearest_neighbours.sort(key = lambda x: x.distance)
        # take only the top N neighbours
        cluster1.absolute_distance_neighbours = nearest_neighbours[0:N]

这是我的秩序聚类算法的实现(假设执行find_normalized_distance_between_clusters和find_rank_order_distance_between_clusters正确):

import networkx as nx
def find_clusters(faces):
    clusters = initial_cluster_creation(faces) # makes each face a cluster
    assign_absolute_distance_neighbours_for_clusters(clusters)
    t = 14 # threshold number for rank-order clustering
    prev_cluster_number = len(clusters)
    num_created_clusters = prev_cluster_number
    is_initialized = False

    while (not is_initialized) or (num_created_clusters):
        print("Number of clusters in this iteration: {}".format(len(clusters)))

        G = nx.Graph()
        for cluster in clusters:
            G.add_node(cluster)

        processed_pairs = 0

        # Find the candidate merging pairs
        for i, cluster1 in enumerate(clusters):

            # Only get the top 20 nearest neighbours for each cluster
            for j, cluster2 in enumerate([neighbour.entity for neighbour in \
                                          cluster1.absolute_distance_neighbours]):
                processed_pairs += 1
                print("Processed {}/{} pairs".format(processed_pairs, len(clusters) * 20), end="\r")
                # No need to merge with yourself 
                if cluster1 is cluster2:
                    continue
                else: 
                    normalized_distance = find_normalized_distance_between_clusters(cluster1, cluster2)
                    if (normalized_distance >= 1):
                        continue
                    rank_order_distance = find_rank_order_distance_between_clusters(cluster1, cluster2)
                    if (rank_order_distance >= t):
                        continue
                    G.add_edge(cluster1, cluster2) # add an edge to denote that these two clusters are to be merged

        # Create the new clusters            
        clusters = []
        # Note here that nx.connected_components(G) are 
        # the clusters that are connected
        for _clusters in nx.connected_components(G):
            new_cluster = Cluster()
            for cluster in _clusters:
                for face in cluster.faces:
                    new_cluster.faces.append(face)
            clusters.append(new_cluster)


        current_cluster_number = len(clusters)
        num_created_clusters = prev_cluster_number - current_cluster_number
        prev_cluster_number = current_cluster_number


        # Recalculate the distance between clusters (this is what is taking a long time)
        assign_absolute_distance_neighbours_for_clusters(clusters)


        is_initialized = True

    # Now that the clusters have been created, separate them into clusters that have one face
    # and clusters that have more than one face
    unmatched_clusters = []
    matched_clusters = []

    for cluster in clusters:
        if len(cluster.faces) == 1:
            unmatched_clusters.append(cluster)
        else:
            matched_clusters.append(cluster)

    matched_clusters.sort(key = lambda x: len(x.faces), reverse = True)

    return(matched_clusters, unmatched_clusters)

问题:

究其原因,性能下降是由于step 10: Update C and absolute distance between clusters by (3)那里(3)是:

这是C_i (cluster i)和中所有面之间的最小L1范数距离C_j (cluster j)

合并簇之后
因为每次我找到候选合并对时,我必须重新计算新创建的簇之间的绝对距离steps 3 - 8.我基本上必须为所有创建的集群执行嵌套for循环,然后使用ANOTHER嵌套for循环来查找具有最近距离的两个面.之后,我仍然要按最近距离对邻居进行排序!

我认为这是错误的方法,因为我已经看过OpenBR,它也实现了相同的Rank-Order聚类算法,我希望它在方法名称下:

Clusters br::ClusterGraph(Neighborhood neighborhood, float aggressiveness, const QString &csv)

虽然我不熟悉C++,但我很确定他们不会重新计算群集之间的绝对距离,这让我相信这是我错误实现的算法的一部分.

此外,在他们的方法声明的顶部,评论说他们已经预先计算了一个kNN图,这是有意义的,因为当我重新计算集群之间的绝对距离时,我正在做我之前做过的大量计算.我认为关键是为集群预先计算kNN图,尽管这是我坚持的部分.我想不出如何实现数据结构,以便每次合并时都不必重新计算簇的绝对距离.

Answer 1

从高层次来看，这也是 OpenBR 所做的，需要的是一个集群 ID 的查找表 -> 集群对象，从中生成新的集群列表，而无需重新计算。

可以在OpenBR 上的本节中从 ID 查找表中查看新集群是在哪里生成的。

对于您的代码，需要为每个Cluster对象添加一个 ID，整数可能最适合内存使用。然后更新合并代码以创建要合并的索引列表，findClusters并从现有集群索引创建新的集群列表。然后合并并更新邻居的索引。

最后一步，邻居索引合并可以在 OpenBR 上看到。

关键部分是合并时不会创建新的簇，并且不会重新计算它们的距离。仅根据现有集群对象更新索引并合并其相邻距离。