Check Levi9 best QA positions to Backbase team!
×Закрыть

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

Всем привет

Имеем два набора объектов 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, поочерёдно сортирует массивы результата. Если результат тяжёлый, заменяет копию ссылкой. Если результат высокоточный, можно построить грубый индекс и сортировать по нему. Можно построить таблицу распределения результата, чтобы знать в каких областях находятся значимые различия (если нет предварительных данных о ценности инфы).

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

Матрица pdist маленькая и найти лучшее попарной соответствие элементарно.
Выбираешь минимум, вычеркиваешь строку и столбец. И так рекурсивно. Сумма расстояний этого соответствия будет минимальна из всех возможных.
Но я хочу не только лучшее найти и но и несколько похуже. Полный перебор всех соответствий отправляет нас в комбинаторный взрыв. Что не подходит.
И сделать некий граф я пока придумать не могу или утыкаюсь в комбинаторный взрыв — граф станет гигантский, что мне не нравиться сильно.
Поковырялся в подходе, что по ссылкам — слишком сложный для этой задачи — не очень он мне понравился. Но пока ничего лучше не нашел и не придумал.

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

1 2

3 999

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

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

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

Мне нужно чтобы одному вектору из 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 здесь не подходит, потому два разных массива данных, а не кластеризация одного.

Да, это оно, но это находит только одно соответствие. А я хочу найти k соответствий.
Всего их будет С_n^k. Все их считать и взять к минимальных — это безумие.
Вот хотелось бы получить советов или ссылок для такого случая.

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

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

Немного в X около 10 в Y около 30. Но объекты отсортировать нельзя — по сути это супервектора (объединение векторов различных признаков). Единственное, что есть это функция расстояния между вектора, что удовлетворяет Минковскому.

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

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

Потому что один объект из одного набора может соответствовать только одному из другого.
Тем ни менее спасибо за идею. На этой идее можно построить что-то типа дерева.

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

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