Защо алгоритмите за групиране на лица не използват матрици на разстояние, а не алгоритми за групиране?

Четох кода за клъстериране на лица на dlib и забелязах, че процесът е така:

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

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

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

Тъй като векторите, генерирани от невронната мрежа, могат да се използват за изчисляване на приликата между две лица, не би ли било по-добре просто да изчислите евклидова матрица на разстоянието, след което потърсете всички стойности, които отговарят на праг на достоверност (напр. x ‹ 0,3 за 70% увереност)?

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

С-шепот - 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
@Nathan Добре, сега разбирам - диаграмата, която предоставихте, наистина отваря очите!   -  person A_toaster    schedule 02.04.2019

Отговори (2)


arrow_upward
2
arrow_downward

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

Но не можете просто да "четете" клъстери от матрицата на разстоянието. Данните там може да са противоречиви: детекторът на лица може да смята A и B за подобни и B за подобни на C, но A и C за различни! Какво правиш тогава? Алгоритмите за клъстериране се опитват да решат точно такива ситуации. Например единична връзка и в по-малка степен 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