Реализация эффективной структуры данных графа для поддержания кластерных расстояний в алгоритме кластеризации ранжирования

Я пытаюсь реализовать кластеризацию 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. Я не могу придумать, как реализовать структуру данных так, чтобы абсолютные расстояния кластеров не приходилось пересчитывать каждый раз, когда они объединяются.

Ответы

Ответ 1

На высоком уровне, и это то, что делает OpenBR , нужна таблица поиска для идентификатора кластера → объект кластера, из которого создается новый список кластеров без пересчета.

Может видеть, где новый кластер создается из таблицы поиска ID в этот раздел в OpenBR.

Для вашего кода необходимо будет добавить идентификатор для каждого объекта Cluster, целые числа, вероятно, будут лучше всего использовать память. Затем обновите код слияния, чтобы создать список индексов, подлежащих объединению, в findClusters и создать новый список кластеров из существующих индексов кластера. Затем слияние и обновление соседей по их индексам.

Последний шаг, слияние соседних индексов можно увидеть здесь, в OpenBR.

Ключевой частью является то, что новые кластеры не создаются при слиянии, а расстояние для них не пересчитывается. Только индексы обновляются из существующих объектов кластера, а их соседние расстояния объединяются.

Ответ 2

Вы можете попытаться сохранить значения расстояния между лицами в словаре ex.

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

distances = {}

def find_nearest_distance_between_clusters(cluster1, cluster2):
    nearest_distance = sys.float_info.max
    for face1 in cluster1.faces:
        for face2 in cluster2.faces:
            if not distances.has_key( (face1.id, face2.id) ):
                distances[(face1.id, face2.id)] = np.linalg.norm(face1.embedding - face2.embedding, ord = 1) #calc distance only once
            distance = distances[(face1.id, face2.id)] #use precalc distances
            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)