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

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

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

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

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

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

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

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

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


python face-recognition cluster-analysis algorithm dlib
person A_toaster    schedule 02.04.2019    source источник
comment
Но откуда вам знать, что такое хороший порог для расстояния? 0,3 кажется довольно произвольным - почему вы говорите, что это дает 70% уверенности?   -  person Nathan    schedule 02.04.2019
comment
@Nathan Ну, любой может выбрать значение расстояния, это не имеет большого значения. В примере с Dlibs он выбирает 0,5, что соответствует достоверности 0,5. Этот вопрос был о том: зачем использовать алгоритм кластеризации, когда матрица расстояний будет работать так же хорошо /, возможно, даже лучше?   -  person A_toaster    schedule 02.04.2019
comment
Это действительно важно; именно поэтому я бы использовал алгоритм кластеризации вместо того, чтобы просто проверять, какие лица достаточно близки к данному лицу. Если бы вы волшебным образом знали, какое расстояние означает, что лица достаточно похожи, это прекрасно работает. Но кластеризация хороша тем, что вам не нужно указывать этот порог   -  person Nathan    schedule 02.04.2019
comment
@Nathan Натан Оооо, хорошо, я думаю, это ответ на мой вопрос! В кластеризации китайского шепота вам все равно нужно указать порог - в примере с dlibs они используют 0,5 - это как-то отличается от использования достоверности 0,5?   -  person A_toaster    schedule 02.04.2019
comment
Я до сих пор не уверен, что вы имеете в виду, когда говорите о доверии. Я лишь смутно знаком с китайским шепчущим алгоритмом кластеризации, но я не знаю доверительного значения, которое он возвращает, и, конечно же, не DBSCAN, а только назначения кластеризации. Тем не менее, правда, что каждый алгоритм кластеризации имеет свои собственные параметры, которые вам необходимо установить, так что вы не сможете полностью избежать проблемы указания порогов или других параметров своего рода. Есть надежда, что проще указать параметры алгоритма кластеризации, чем просто задать жесткое ограничение расстояния.   -  person Nathan    schedule 02.04.2019
comment
Также обратите внимание, что многие алгоритмы кластеризации делают что-то более сложное, чем просто использование жесткого ограничения расстояния - тогда это будет одинаковым для всех изображений. Кластеризация, с другой стороны, обычно имеет кластеры разных размеров, где некоторые могут исключать точки, которые не слишком далеко, в то время как другие кластеры могут по-прежнему включать точки на этом расстоянии (например, в зависимости от того, есть ли в середине область с низкой плотностью). .   -  person Nathan    schedule 02.04.2019
comment
Взгляните на это сравнение алгоритмов кластеризации. Многое из того, что мы, люди, считаем хорошими кластерами в этих примерах пространств, было бы невозможно определить с помощью жесткого ограничения расстояния.   -  person Nathan    schedule 02.04.2019
comment
@ Натан Хорошо, теперь я понял - предоставленная вами диаграмма действительно открывает глаза!   -  person A_toaster    schedule 02.04.2019

Ответы (2)


arrow_upward
2
arrow_downward

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

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

person Has QUIT--Anony-Mousse    schedule 02.04.2019

arrow_upward
1
arrow_downward

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

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

person Nico Schertler    schedule 02.04.2019