Почему алгоритмы кластеризации лица не используют матрицы расстояний, а не алгоритмы кластеризации?

Question

Я читал код кластеризации лица dlib и заметил, что процесс выглядит так:

1. Преобразование граней в вектор с использованием обученной сети
2. Использование алгоритма кластеризации китайского шепота для вычисления групп на основе расстояния

Китайская шепотная кластеризация может занять довольно много времени при попытке кластеризовать большое количество (> 10 000) изображений.

В этой статье pyimagesearch автор использует DBSCAN, еще один алгоритм кластеризации, для группировки нескольких изображений по человеку.

Поскольку векторы, сгенерированные нейронной сетью, можно использовать для вычисления сходства между двумя гранями, не лучше ли просто вычислить евклидову матрицу расстояний , а затем найти все значения, которые соответствуют доверительный порог (например, х <0,3 для 70% достоверности)? </p>

Зачем вообще использовать алгоритм кластеризации, когда вы можете просто сравнить каждое лицо с каждым другим лицом, чтобы определить, какие из них являются одним и тем же человеком? и DBSCAN, и кластеризация с китайским шепотом занимают гораздо больше времени, чем вычисление матрицы расстояний. С моим набором данных из 30 000 изображений время:

C-шепот - 5 минут

матрица расстояний + поиск - 10-20 секунд

Answer 1

DBSCAN на самом деле занимает лишь незначительно больше времени, чем вычисление матрицы расстояний (при правильной реализации 99% вычислений - это вычисления расстояний), и с индексированием иногда может быть намного быстрее, потому что ему не нужно каждое попарное расстояние, если индекс может сократитьвычисления.

Но вы не можете просто «считывать» кластеры из матрицы расстояний.Данные могут быть противоречивыми: детектор лица может считать A и B похожими, а B похожими на C, но A и C - разными!Что вы делаете тогда?Алгоритмы кластеризации пытаются решить именно такие ситуации.Например, одиночная ссылка и, в меньшей степени, DBSCAN сделают A и C одним и тем же кластером, тогда как полная связь будет определять либо AB, либо BC.

Answer 2

На самом деле, реализация dlib делает нечто очень похожее на то, о чем вы думаете. Здесь - код.Сначала он проверяет каждую пару и отклоняет пары, расстояние которых превышает пороговое значение.Это именно то, что вы предложили.Но тогда это делает тонкую кластеризацию на результат.Итак, что изменится?

Простое отрезание по расстояниям может сработать, если у вас есть четко разделенные точки данных.Однако, если ваши точки данных находятся очень близко друг к другу, эта проблема становится очень сложной.Вообразите 1D особенность.Точки данных - это целочисленные позиции от 0 до 10, и вы хотите соединить две точки данных в кластере, если их расстояние не превышает 1,5.Итак, что бы вы сделали?Если вы начнете с пары, вы можете сделать кластер.Но если вы выберете соседнюю точку, вы увидите, что она будет ближе, чем ваш порог, к одной точке в кластере и больше, чем порог для другой.Кластеризация - это решение этой двусмысленности.