Найти близкие пары в очень высокомерном пространстве с разреженными векторами

9

У меня есть (~ миллион) векторов признаков. Есть (~ миллион) бинарных объектов, но в каждом векторе только (~ тысяча) из них будет , остальные - . Я ищу пары векторов, которые имеют как минимум (~ сто) общих признаков ( в обоих). Количество таких пар имеет величину, аналогичную (~ миллион).NMК10L1N

Я думаю, что это можно рассматривать как поиск пар близких точек в очень многомерном пространстве. Функция расстояния может быть такой, чтобы она основывалась на том, сколько признаков имеют два общих вектора. Но это, вероятно, было бы полезно с более обычной метрикой расстояния (такой как Евклидово) также.

Какие известные алгоритмы будут полезны для решения этой проблемы? Все, что является квадратичным по или , не будет практичным.NM


Примером реальной постановки проблемы является рассмотрение людей, перемещающихся между несколькими местами. Если два человека были в одном месте в одно и то же время, мы говорим, что они встретились. (Количество комбинаций времени и местоположения, в которых присутствует как минимум 1 человек, равно ) Мы ищем друзей: людей, которые встречались как минимум раз.NML

Даниэль Дарабос
источник
1
Если вектор 1, признак 1 равен , а вектор 2, признак 1 также равен , есть ли у них этот признак «общего»? 000
gung - Восстановить Монику
@ user777, я полагаю, нет , и в этом случае ваш ответ будет идеальным, но было бы неплохо, чтобы это было явно указано ОП.
gung - Восстановить Монику
@ Gung, вы правы. Я отредактировал вопрос, чтобы уточнить. Спасибо!
Даниэль Дарабос
1
Сколько пар векторов имеют более 100 общих признаков - случайная выборка + грубая сила? Являются ли размеры 1М х 1М настоящей проблемой или вымышленными? См. Также подход в поиске бит-строки-ближайшего соседа в стеке потока.
Денис
1
Возможно, сумасшедшее предложение: просмотрите ваши векторные объекты длиной 1 Мбит как изображения размером 1000 x 1000 пикселей и найдите методы для кластеризации изображений, например stackoverflow.com/search?q=[image]+clustering . Afaik, вы должны найти хорошие функции (не одиночные пиксели), чтобы это работало, но я не эксперт.
Денис

Ответы:

6

Похоже, что подход, который вы ищете, представляет собой комбинацию сигнатур minhash и локального хеширования (LSH); (свободно доступный) pdf Mining Massive Datasets описывает этот подход (и другие меры сходства) в деталях в главе 3, но кратко:

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

Чтобы решить эту проблему, MMDS рекомендует, чтобы, если все, что вы хотите найти, это пары выше определенного порога сходства (что, по-видимому, применимо в вашем случае), то вы можете сосредоточиться только на тех парах, которые, скорее всего, будут похожи - этот подход называется Хеширование с учетом локальных особенностей, и в разделе 3.4 они рассматривают пример того, как объединить подход с использованием сигнатуры minhash и LSH.

В дополнение к тексту, есть также лекции, доступные на курсе Coursera с тем же названием.

цацка
источник
7

Я ищу пары векторов, которые имеют как минимум общих черт.L

Это просто внутреннее произведение векторов двоичных объектов. Когда внутреннее произведение больше, чем , пара будет иметь как минимум L общих элементов. Это должно быть относительно быстрое вычисление - по крайней мере, быстрее, чем евклидово расстояние, которое было бы расточительным и медленным для этих данных. Поскольку вы оговариваете, что ищете пары, это по сути означает, что вы должны выполнить вычисления для сравнения каждого вектора.L-1L(N2)

Поиск точек, которые находятся близко друг к другу, действительно является проблемой кластеризации. Но первый шаг алгоритмов кластеризации, с которыми я знаком, - это вычисление парных расстояний или сходств. Я уверен, что кто-то разработал более эффективные альтернативы. Пункт о терминологии: наличие как минимум общих соседей выражается как сходство , а не расстояние! Внутренние продукты в этом случае являются ненормализованным косинусным сходством.L

Вы можете сделать это более удобным, выполнив вычисление внутреннего произведения только тогда, когда сумма вектора признаков (которая в данном случае совпадает с нормой) для наблюдения больше , поскольку для этого вектора двоичных объектов это невозможно иметь внутренний продукт с другим бинарным вектором признаков , который будет удовлетворять мой критерий , когда эта сумма меньше , чем . Очевидно, что вычисление этих сумм - только сложность, поэтому я - дешевый способ снизить величину шага внутреннего продукта.L O ( N )L-1LО(N)

Но классический способ уменьшить масштабы этой проблемы - выполнить дополнительную предварительную фильтрацию. Вас особенно интересует, когда одна, несколько необычная функция принимает значение 1? Если это так, выполняйте вычисления только для этих векторов признаков.

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

После некоторой дополнительной мысли, у меня есть сильное подозрение , что данные вы работаете, какое - то граф . Весьма вероятно, что состоит из нескольких соединенных компонентов, и в этом случае вы можете разложить на набор графиков с приятным побочным эффектом уменьшения размерности данных. Даже если на графике только два соединенных компонента примерно одинакового размера, это означает, что ваши парные сравнения примерно равны общей стоимости!G G O ( N 2 ) 1гггО(N2)14

Если график симметричен, могут быть полезны следующие наблюдения:

  1. Определите лапласиан вашего графа как , где - диагональная матрица степени (сумма каждого вектора признаков), а - матрица смежности (укладка векторов признаков в матрицу).D Aпзнак равноD-ADA
  2. Времена числа отображается как собственное есть число компонент связности . Разложение графика на его связанные компоненты и работа исключительно с этими компонентами будет иметь побочный эффект уменьшения размера ваших данных; вычисление вашего количества интереса будет легче. Но вычисление собственного разложения будет дорого для миллиона вершин ...П Г0пг
  3. (После полной перестановки) представляет собой блок - диагональная матрица лапласианов из компонент связности .пг
  4. п положительно полуопределен. Это почти наверняка полезно как-то.
  5. Алгебраическая связность является значением второго-наименьшее собственное . Это говорит о том, насколько хорошо связан есть. Возможно, это ответит на некоторые интересующие вас вопросы: векторы, которые имеют общие черты. Теория спектральных графов развивает эту идею более подробно.гпг

"Это проблема СНС?" Я не уверен. В одном приложении функции описывают поведение, и мы стремимся связать людей с похожим поведением. Это делает это проблемой SNA?

Если у вас есть двудольный граф, связывающий людей с поведением, вы можете думать об этом как о сети присоединения , где люди представляют собой строки, а поведения - как столбцы. Если вы хотите , чтобы соединить людей с людьми с помощью поведения , который они имеют в общем, вы можете вычислить . - это общее поведение людей. Очевидно, множество вершин, где отвечает на ваш вопрос.ВВВTзнак равноAAяJAяJL

Sycorax говорит восстановить Монику
источник
Спасибо за отличный ответ! Это много вещей, которые мне придется исследовать дальше. Я не уверен, что парные сравнения неизбежны. Разве это не проблема кластеризации, когда я ищу кластеры размером> 1? Я ожидал, что некоторый пространственный подход к разделению может сильно сократить количество парных сравнений.
Даниэль Дарабос
Извините, я не очень разбираюсь в науке о данных. Но разве это не проблема кластеризации, когда мы пытаемся сгруппировать точки, расположенные близко друг к другу? У меня есть максимальное расстояние (L), и я хочу найти группы (пары) точек, которые находятся на этом расстоянии друг от друга. Это слишком сильно расширяет определение кластеризации?
Даниэль Дарабос
1
Это действительно можно сформулировать как проблему графа. В этом случае мы имеем двудольный граф из N точек и M объектов и хотим найти пары точек, которые имеют как минимум L общих соседей. Сейчас я специально смотрю на векторную характеристику, надеясь, что есть метод кластеризации, который мне пригодится. K-SVD предложили подобную проблему в stats.stackexchange.com/questions/93366/… , так что я сейчас читаю об этом. Спасибо!
Даниэль Дарабос
"Это проблема СНС?" Я не уверен. В одном приложении функции описывают поведение, и мы стремимся связать людей с похожим поведением. Это делает это проблемой SNA? Спасибо за то, что познакомили меня с терминологией, очень полезно вести мой поиск.
Даниэль Дарабос
Я пересмотрел свой ответ. Ваша конечная цель - просто перечислить людей, у которых много общего поведения, или это что-то еще?
Sycorax говорит восстановить Монику
2

При поиске людей, встречающихся в пространственно-временных блоках:
разделите пространство на блоки (городские кварталы, квадратные километры и т. Д.) И время на блоки . Есть большая вероятность, что если люди встретятся, они встретятся в одном квартале. Так что запускайте NN в каждом блоке. Время выполнения и частота ошибок, конечно, будут зависеть от размеров и форм блоков (также от того, что вы можете распараллелить / MapReduce), но у вас есть параметры, с которыми можно поиграть - инженерный, а не широко открытый .N t i m e O ( N 2 )NsпaсеNTяме
О(N2)

См. Также:
поиск ближайших соседей для очень больших размерных данных на datascience.stackexchange

pairwise.py :

использует библиотеку Python Gensim и heapq из стандартной библиотеки, чтобы сделать чрезвычайно быстрые и масштабируемые парные сравнения между большим количеством документов с использованием TF-IDF и косинусного расстояния.

Денис
источник
1

ИксееaT1:vaLUе1,ееaT101:vaLUе101ККК

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

ееaT1:{1,101,202},ееaT2:{7,202},ееaT3:{202},,,ееaTM:{3,45,6}ееaT3О(NК)

ИксИксИкспО(N2)

ИксYd(Икс,Y)<Икс,Y>ИксYО(К)

О(NпК)О(MN2)

Я применил этот метод для реализации KNN на большом текстовом наборе (поезд: 2 000 000 строк, тест 35 000 строк, количество объектов: 10 000, среднее количество объектов на элемент: 20), который выполнялся примерно через час. ,

RUser4512
источник
Я не совсем понимаю этот подход - это не потому, что я не верю вам, это полностью из-за моего недостаточного знакомства с различными стратегиями представления данных. Возможно, вы могли бы подробнее рассказать о том, что вы освещаете в первых двух параграфах?
Sycorax сообщает восстановить Monica
О(N2)
1

КО(LNжурнал(N))

Л. Эроц, М. Штайнбах и В. Кумар. «Новый общий алгоритм кластеризации ближайшего соседа и его приложения». Труды 1-го семинара по кластеризации высокомерных данных и их приложений, 2002.

Sycorax говорит восстановить Монику
источник
Спасибо, это интересное чтение. Как вы получили время O (LN log (N))? Это звучит здорово. Но описание алгоритма начинается с «Построить матрицу подобия», и, насколько я понимаю, это будет матрица NxN.
Даниэль Дарабос
@DanielDarabos Сложность описана в книге « Практическое графическое майнинг с Р.»,
говорит Сикоракс. Восстановите Монику
1

О(КжурналN)К<<N

Учитывая, что ваш k равен 100, а ваш n равен 1e6, это должно дать вам ~ 1e4x ускорение по сравнению с классическим FFT.

Если вам нужна еще 20-кратная скорость, и вы рискуете, то вместо того, чтобы сворачивать все строки в домене и искать пик, вы можете загрузить подмножество строк.

Вы также можете предварительно отфильтровать столбцы, удалив столбцы, суммы которых меньше 50, или некоторый другой порог, который составляет порядка половины числа строк, которые вы хотите сопоставить. По крайней мере, вы должны удалить столбцы всех нулей и всех 1 как неинформативные. То же самое со строками, которые полностью пусты или достаточно пусты, или строками, которые настолько полны, что они не имеют значения.

Дела: я должен привести пример с использованием синтетических данных и сравнить некоторые методы.

EngrStudent
источник
0

Я только что натолкнулся на статью, которая имеет прямое отношение к делу.

Рандомизированные алгоритмы и NLP: использование чувствительной к локальности хеш-функции для высокоскоростной кластеризации существительных (Ravichandran et al, 2005)

На самом деле это реализовано в https://github.com/soundcloud/cosine-lsh-join-spark, где я его и нашел.

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

Даниэль Дарабос
источник