我正在尝试实现排序聚类 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 Cun.
1: Initialize clusters C = { C1, C2, … CN }
by letting each face be a single-element cluster.
2: repeat
3: for all pair Cj and Ci in C do
4: Compute distances DR( Ci, Cj) by (4) and DN(Ci, Cj) by (5).
5: if DR(Ci, Cj) < t and DN(Ci, Cj) < 1 then
6: Denote ⟨Ci, Cj⟩ as a candidate merging pair.
7: end if
8: end for
9: Do “transitive” merge on all candidate merging pairs.
(For example, Ci, Cj, Ck are merged
if ⟨Ci, Cj⟩ and ⟨Cj, Ck⟩ 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 Cun.
13: return C and Cun.
我的实现:
我定义了一个 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 图,尽管这是我坚持的部分。我想不出如何实现数据结构,以便每次合并时都不必重新计算集群的绝对距离。
最佳答案
在高层次上,这就是 OpenBR seems to do as well , 需要的是一个簇 ID 的查找表 -> 簇对象,从中生成一个新的簇列表而无需重新计算。
可以从 this section on OpenBR 处的 ID 查找表中查看新集群的生成位置.
对于您的代码,需要为每个 Cluster
对象添加一个 ID,整数可能最适合内存使用。然后更新合并代码以在 findClusters
处创建待合并索引列表,并根据现有集群索引创建新的集群列表。然后根据索引合并和更新邻居。
最后一步,邻居索引合并can be seen here on OpenBR .
关键部分是合并时不会创建新的集群,并且不会重新计算它们的距离。只有索引从现有的集群对象更新,并且它们的相邻距离被合并。
关于python - 在排序聚类算法中实现一个有效的图数据结构来保持聚类距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43462035/