python - 在排序聚类算法中实现一个有效的图数据结构来保持聚类距离

Question

我正在尝试实现排序聚类 here is a link to the paper (这是一种凝聚聚类)算法从头开始。我已经通读了这篇论文(多次)并且我有一个正在运行的实现，尽管它比我预期的要慢很多。

这是一个link到我的 Github，其中有下载和运行 Jupyter Notebook 的说明。

算法:

Algorithm 1 Rank-Order distance based clustering

Input:
  N faces, Rank-Order distance threshold t .
Output:
  A cluster set C and an “un-grouped” cluster C_un.
1: Initialize clusters C = { C₁, C₂, … C_N }
 by letting each face be a single-element cluster.
2: repeat
3:  for all pair C_j and C_i in C do
4:   Compute distances D^R( C_i, C_j) by (4) and D^N(C_i, C_j) by (5).
5:   if D^R(C_i, C_j) < t and D^N(C_i, C_j) < 1 then
6:    Denote ⟨C_i, C_j⟩ as a candidate merging pair.
7:   end if
8:  end for
9:  Do “transitive” merge on all candidate merging pairs.
  (For example, C_i, C_j, C_k are merged
  if ⟨C_i, C_j⟩ and ⟨C_j, C_k⟩ are candidate merging pairs.)
10:  Update C and absolute distances between clusters by (3).
11: until No merge happens
12: Move all single-element clusters in C into an “un-grouped” face cluster C_un.
13: return C and 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)

问题:

性能缓慢的原因是由于第 10 步:通过 (3) 更新 C 和簇之间的绝对距离 其中 (3) 是:

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

合并集群后
因为每次在 steps 3 - 8 中找到候选合并对时，我都必须重新计算新创建的集群之间的绝对距离。我基本上必须为所有创建的集群做一个嵌套的 for 循环，然后有另一个嵌套的 for 循环来找到距离最近的两个面。之后，我仍然必须按最近距离对邻居进行排序!

我认为这是错误的方法，因为我看过 OpenBR它也实现了我想要的相同的排序聚类算法，它在方法名称下:

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

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

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

Answer 1

在高层次上，这就是 OpenBR seems to do as well , 需要的是一个簇 ID 的查找表 -> 簇对象，从中生成一个新的簇列表而无需重新计算。

可以从 this section on OpenBR 处的 ID 查找表中查看新集群的生成位置.

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

最后一步，邻居索引合并can be seen here on OpenBR .

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