Сучасна диджитал-освіта для дітей — безоплатне заняття в GoITeens ×
Mazda CX 5
×

Попарное соответсвие объектов

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

Всем привет

Имеем два набора объектов X, Y.
Есть pdist2(X,Y).
Найти лучшее попарное соответствие объектов из двух наборов я могу.

Но мне хотелось найти k лучших попарных соответствий. Может кто пнет в направлении уже известных подходов и методов.

ДП влоб не применить, потому как матрица не симметричная и не квадратная (точнее даже не поэтому, а потому, что минимуму разбросаны случайным образом и их позиции зависят от порядка объектов в наборе).

Думал о kNN, то пока не вижу, как применить.

Забыл дописать:
Один объект из одного набора может соответствовать только одному из другого.

Т.е. хочется получить k лучших попарных соответствий.

👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

Кстати, а в чём принципиальная разница между одним лучшим попарным соответствием и k лучших? Просто вместо одного значения ты хранишь сортированный массив фиксированной длины, из которого по мере вычисления вытесняются значения. Если к — большое число, имеет смысл массив зациклить, то есть сделать круговым: будешь хранить в переменной индекс головы уробороса, и с каждым приростом голова будет откусывать хвост. Изначально массив проинициализировать минимальным значением, чтобы не проверять на null в каждой итерации — это проверишь уже после всех вычислений.

Тоже не понял в чем разница если уже нашел одно значение то в чем сложность найти несколько.

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

Я так понимаю, что задача самого вычисления попарных соответствий не оптимизируема. Матрица соответствий уменьшится вдвое если исходные массивы отсортировать — но что быстрее, сортировка или же дважды посчитать соответствие?

Что будет если посчитать соответствие дважды, то есть собрать двf объекта pdist2(X,Y) и pdist2(Y,X) — не нормализованный набор, зато отлично индексируемый и распределённо хранимый. Если нет цели поддерживать целостность данных в дальнейшем, можно вообще расслайсить по X или Y, и не заморачиваться недостаточностью данных. Далее, этот массив прекрасно льётся в медленную память потоком, не дёргая к примеру головки диска.

Ну и немаловажная особенность: готовый результат может быть оптимизирован уже после подсчёта. То есть первая копия X*Y остаётся рабочей, а фоновый процесс если есть время — проводит оптимизацию: сортирует X, сортирует Y, поочерёдно сортирует массивы результата. Если результат тяжёлый, заменяет копию ссылкой. Если результат высокоточный, можно построить грубый индекс и сортировать по нему. Можно построить таблицу распределения результата, чтобы знать в каких областях находятся значимые различия (если нет предварительных данных о ценности инфы).

Ну и понимай, что вычислительную мощность можно арендовать, это имеет свою цену. А вот алгоритмически выгодного решения скорее всего не существует, реальную выгоду может только мета-инфа. А именно, ПРЕДСКАЗАНИЕ распределения, и уже в строну этого предсказания оптимизировать цикл исполнения.

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

1 2

3 999

Твой «комбинаторный взрыв» станет не гигансткий, а всего в 2 раза больше. И всё. Так что решай вопрос в лоб и будет тебе счастье. К тому же алгоритм прекрасно подходит конвейрам процессора, в отличие от нелинейных.

Равно как и твой вариант работает: выбираешь сразу k минимумов, вычёркиваешь строку и столбец (кстати, я не совсем понял зачем столбец, если можно пройтись построчно). На второй строке ты просто потесняешь кандидатов, выдавливая за пределы k (вопрос что делать с одинаковыми на твоё усмотрение).

Я так вижу, что алгоритм прохода не оптимизируешь никак, посчитать полюбому надо всех со всеми. Но «вычёркивать» нет нужды, достаточно просто пробежаться по циклу. И если честно, я не совсем понял задачу: векторы X и Y у тебя идентичны, то есть де-факто это один вектор? Или какие есть основания вычёркивать строку и столбец?

Судячи з багатьох посилань у наукових статтях на суміжні теми, ваша проблема описана тут:
dl.acm.org/citation.cfm?id=142740
Але я не зміг знайти дану статтю у вільному доступі.

возможно я не понял до конца, что подразумевается под

попарных соответствий
, потому что не понятно на основании чего они должны быть в паре (дистанция друг от друга или еще что то), но если нужно определить k кластеров точек — то
K-Means clustering
не понятно на основании чего они должны быть в паре (дистанция друг от друга или еще что то)
pdist2(X,Y) это функция из матлаба, она выдает матрицу соответствий между элементами матриц X и Y, по дефолту это эвклидова дистанциия, все верно.

p.s. Вообще звучит так, что нужно просто найти в матрице, которую вернет pdist2 K элементов, у которых значение является близким к 0, что элементарно. Но ТС так описывает задачу, что понять тяжело.

p.p.s K-means здесь не подходит, потому два разных массива данных, а не кластеризация одного.

Так сколько у вас элементов в Х и Y ?

Думал о kNN, то пока не вижу, как применить.
Зачем сразу так усложнять? Просто сохраняйте в список struct плана {distance, X, Y} и потом отосртируйте по distance. Выбирайте K лучших из списка. Почему так нельзя?

p.s. Или вам нужно найти K-лучших для каждого элемента в наборе?

На этой идее можно построить что-то типа дерева
Скорее не дерево, а max-heap.

Підписатись на коментарі