Я пытаюсь реализовать кластеризацию Rank-Order вот ссылка на бумагу (который является своего рода агломеративным кластеризацией) с нуля. Я прочитал статью (много раз), и у меня есть реализация, которая работает, хотя она намного медленнее, чем я ожидаю.
Вот ссылка на мой Github, у которой есть инструкции по загрузке и запуску ноутбука Jupyter.
Алгоритм:
Алгоритм 1 Кластеризация на основе ранжирования с ранжированием
Ввод:
& emsp; & emsp; N лиц, пороговое значение ранга-ордера T.
Вывод:
& emsp; & emsp; Набор кластеров C и "негруппированный" кластер C <суб > ипсуб > .
1: Инициализировать кластеры C= {C 1, C 2, & hellip; C N}
& emsp; позволяя каждой грани быть одноэлементным кластером.
2: повторить
3: & emsp; для всех пары C j и C i в C do
4: & emsp; & emsp; Вычислить расстояния D R ( C i, C j) по (4) и D N (C i, C j) по (5).
5: & emsp; & emsp; , если D R (C i, C j) < t и D N (C i, C j) < 1 , затем
6: & emsp; & emsp; & emsp; Обозначить ⟨C i, C j⟩ как кандидат, объединяющий пару.
7: & emsp; & emsp; конец, если
8: & emsp; конец для
9: & emsp; "транзитивный" слияние на всех сходящихся парах кандидатов.
& emsp; & emsp; (Например, C i, C j, C k объединены
& emsp; & emsp; если ⟨C i, C j⟩ и ⟨C j, C k⟩ являются кандидатами слияние пар.)
10: & emsp; Обновить C и абсолютные расстояния между кластерами по (3).
11: до Слияния не происходит
12: Переместите все одноэлементные кластеры в C в "негруппированный" граничный кластер C un.
13: вернуть C и C un.
Моя реализация:
Я определил класс Cluster следующим образом:
class Cluster:
def __init__(self):
self.faces = list()
self.absolute_distance_neighbours = None
A 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):
Это наименьшее L1-нормальное расстояние между всеми гранями в C_i (cluster i) и C_j (cluster j)
После слияния кластеров
Поскольку мне приходится пересчитывать абсолютные расстояния между вновь созданными кластерами каждый раз, когда я заканчиваю поиск слияния кандидатов в steps 3 - 8. Я в основном должен сделать вложенный цикл for для всего созданного кластера, а затем ДРУГОЙ, вложенный в цикл, чтобы найти два лица, которые имеют самое близкое расстояние. Впоследствии мне все равно придется сортировать соседей на ближайшем расстоянии!
Я считаю, что это неправильный подход, поскольку я рассмотрел OpenBR, который также реализовал тот же алгоритм кластеризации Rank-Order, который Я хочу, чтобы оно находилось под именем метода:
Clusters br::ClusterGraph(Neighborhood neighborhood, float aggressiveness, const QString &csv)
Хотя я не знаком с С++, я уверен, что они не пересчитывают абсолютные расстояния между кластерами, что заставляет меня думать, что это часть алгоритма, который я реализую неправильно.
Кроме того, в верхней части объявления их метода комментарии говорят, что они предварительно вычислили график kNN, который имеет смысл, когда я пересчитываю абсолютные расстояния между кластерами. Я делаю много вычислений, которые я ранее делал. Я считаю, что ключ состоит в том, чтобы прекомпутеровать график kNN для кластеров, хотя это та часть, в которой я застрял at. Я не могу придумать, как реализовать структуру данных так, чтобы абсолютные расстояния кластеров не приходилось пересчитывать каждый раз, когда они объединяются.
