Как найти самое похожее лицо из базы данных?

Question

[Bleno]

Имеется база данных, в которой каждое лицо кодируется 128 числами. Например:

Лицо 1

[ -0.1130942776799202,
     0.1614537537097931,
     -0.006035998929291964,
     -0.1542104184627533,
     -0.06875834614038467,
     -0.032062552869319916,
     0.05085310339927673,
     -0.0772537812590599,
     0.20312847197055817,
     -0.03393673151731491,
     0.14966045320034027,
     0.015613612718880177,
     -0.2537919580936432,
     -0.055424273014068604,
     -0.0216793492436409,
     0.09997572004795074,
     -0.10322976112365723,
     -0.11479102075099945,
     -0.13069766759872437,
     -0.02312583476305008,
     0.052273452281951904,
     0.03703169524669647,
     -0.0002829816658049822,
     -0.0005055302754044533,
     -0.04392200708389282,
     -0.2537318468093872,
     -0.08467373996973038,
     -0.07383286952972412,
     -0.013739113695919514,
     -0.0824621170759201,
     0.05842585861682892,
     -0.02282029017806053,
     -0.29698559641838074,
     -0.15543779730796814,
     -0.012977054342627525,
     0.05585605651140213,
     -0.18177944421768188,
     -0.08584177494049072,
     0.1914125382900238,
     0.049033816903829575,
     -0.12426487356424332,
     0.07370023429393768,
     0.10151664912700653,
     0.2125469595193863,
     0.15979231894016266,
     0.004027041606605053,
     0.052840933203697205,
     -0.11493529379367828,
     0.10623033344745636,
     -0.24218681454658508,
     0.0558830089867115,
     0.11607223749160767,
     0.18381895124912262,
     0.1480993628501892,
     0.0934639647603035,
     -0.17770831286907196,
     0.09219089150428772,
     0.09511983394622803,
     -0.2078547477722168,
     0.11334264278411865,
     0.0864596962928772,
     -0.03732181340456009,
     -0.06170603632926941,
     0.014513085596263409,
     0.19028794765472412,
     0.08083567023277283,
     -0.07796188443899155,
     -0.13692373037338257,
     0.1674240529537201,
     -0.10188353061676025,
     -0.023299138993024826,
     0.13179853558540344,
     -0.06638269871473312,
     -0.2005026787519455,
     -0.1835901290178299,
     0.13835741579532623,
     0.3288293480873108,
     0.16999228298664093,
     -0.1326129138469696,
     -0.012811451219022274,
     -0.12992361187934875,
     -0.027557959780097008,
     -0.027281606569886208,
     0.020332694053649902,
     -0.08542351424694061,
     -0.018185008317232132,
     -0.09051108360290527,
     0.0608053132891655,
     0.20289434492588043,
     -0.032099973410367966,
     -0.04639098420739174,
     0.23962445557117462,
     0.07255730032920837,
     0.004598921164870262,
     -0.010999824851751328,
     0.023231782019138336,
     -0.11400877684354782,
     -0.0024917502887547016,
     -0.12924475967884064,
     -0.034801140427589417,
     0.07540622353553772,
     -0.14184702932834625,
     -0.03451569378376007,
     0.10676993429660797,
     -0.14829140901565552,
     0.14299613237380981,
     -0.016563797369599342,
     -0.059809811413288116,
     -0.09886705130338669,
     -0.021711565554142,
     -0.05889463424682617,
     0.01345861703157425,
     0.08860933780670166,
     -0.19535264372825623,
     0.30562612414360046,
     0.14268618822097778,
     -0.034439895302057266,
     0.09777306765317917,
     0.08058249950408936,
     0.0537114292383194,
     0.04592563211917877,
     -0.03586505353450775,
     -0.11147730052471161,
     -0.12388268858194351,
     0.0529785230755806,
     0.08037040382623672,
     0.08579140156507492,
     0.0404975451529026 ]

В базе может быть очень много записей (на данный момент около 150 тысяч, но планируется масштабировать до десятков и сотен миллионов).
Суть задачи состоит в том, что нам на вход подаётся новое лицо, вычисляются его точки (массив из 128 чисел), и нужно найти самый ближайший массив из базы, проще говоря, нужно найти точку с минимальным Евклидовым расстоянием.
Проблема в том, что вычислять Евклидово расстояние для всей базы каждый раз, когда на вход поступает новое лицо - очень долго. И ещё специфической особенностью этой задачи является то, что индексы тут никак не помогут.
Пробовал kd-деревья, у них сложность O(log n), но только для размерностей 2,3, а для размерностей выше (128, как в данном случае), этот тип дерева работает ну очень медленно. Пробовал сортировку по координате, по расстоянию до центра координат, слишком долго выходит. Так же пробовал модуль для python sklearn, а именно sklearn.KNeighborsClassifier, тоже медленно.

Чтобы понимать, что значит медленно, а что нет: рассчитываю на способность программы находить 10 самых похожих лиц из базы в миллиард записей за 1 секунду или медленнее. Если у вас есть идеи, как реализовать эту задачу, буду благодарен вас выслушать.

P.S Я думаю оптимизации, вроде разделения на пол и возраст, тут не самый лучший вариант, так как подобные алогоритмы нередко ошибаются, что в итоге может сделать вообще невозможным поиск лица в базе, учитывая пол и возраст. К тому же подобная оптимизация не даст сильного прироста скорости.

Comments

[longclaps]

Чтобы понимать, что значит медленно, а что нет

Не вижу ответа на вопрос, что значит медленно. А было бы прикольно узнать, каковы ваши достижения.

[Bleno]

longclaps, Обновил тему, добавив некоторые результаты.

[longclaps]

Bleno, Scikit-learn is not intended to be used as a deep-learning framework and it does not provide any GPU support.
Так что...

Answer 1

[Vindicar]

Как насчёт многоярусной кластеризации? Т.е. разбиваете базу лиц на кластеры схожих, затем эти кластеры делите на под-кластеры, и так далее. В итоге строите дерево, где каждый ярус описывает некоторое разделение лиц на подгруппы (не обязательно смысловые типа мужское/женское). Начинаете с верхнего яруса, найдя наиболее схожий узел/кластер, производите повторный поиск, но уже по его непосредственным потомкам. И так, пока не сузите диапазон поиска до приемлемого, когда можно будет прогонять поиск по всем лицам в данном кластере.
Параметры дерева (размер и число ярусов) придётся подбирать самостоятельно.

Есть возможные модификации. Во-первых, можно превратить дерево в ориентированный граф, задав каждому узлу более одного "родителя". Это может уменьшить ошибку классификации.
Во-вторых, можно попробовать обучить классификатор (например, SVM) так, чтобы он сообщал номер кластера, к которому скорее всего принадлежит это лицо, а затем искать внутри этого кластера.

Comments

[Bleno]

Идея отличная, но как определить создавать новый кластер, или добавлять лицо в существующий? Подбирать пороговое значение "похожести"? Кроме этого, на ум только нейросети приходят

[Vindicar]

Либо по пороговому значению, либо по мере наполнения базы время от времени "переобучать" алгоритм.

Answer 2

[U235U235]

Построийте диаграмму Вороного для набора точек.
см. https://habr.com/ru/post/309252/

Comments

[Bleno]

Честно говоря, не нашёл, как после построения диграммы, искать похожие точки

Answer 3

[Владимир Куц]

С использованием Elasticsearch
https://habr.com/ru/company/otus/blog/557210/

Answer 4

[ThunderCat]

Возможно будет проще если сделать 2 или 3 базовых параметра, которые точно исключат похожесть (ну например цвет кожи, разрез глаз, форма подбородка и т.п.), и/или например добавить поле со сниженным качеством кодирования до 64-32, дабы уменьшить выборку, и делать уже на основе остатка выборки перебор.

Comments

[Bleno]

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

[ThunderCat]

Bleno,

Осталось определить каким образом уменьшить размерность, не снизив точность сравнений.

Во первых, не заменить поле, а добавить. Во вторых я и не предлагаю оставить точность, наоборот, определить группы с минимальным совпадением. Их задача максимально быстро исключить заведомо неподходящие образцы, которых должно быть весьма много, и соответственно уменьшить группу перебираемых элементов до минимума. То есть в данном случае искать не максимальную похожесть, а максимальные различия.

А цвет кожи, разрез глаз, определить вручную не получится

Я привел пример, что можно легко внести в параметры, причем сделать это нужно 1 раз при определении лица в базу. И сразу у вас появится +N параметров, по которым можно исключить огромный кусок данных. Не обязательно приведенные мной, а например расстояние между самыми удаленными от центра лица точками или что-то такое... Тут уже чисто логика/фантазия нужна.