Алгоритм группировки похожих множеств

Question

У меня есть поисковая система.Поисковая система генерирует результаты при поиске по ключевому слову.Мне нужно найти все другие ключевые слова, которые дают похожие результаты.

Например, ключевое слово k1 дает набор результатов R1 = {1,2,3,4,5, ... 40}, который содержит до 40 идентификаторов документов.И мне нужно получить список всех других ключевых слов K1 , которые генерируют результаты, аналогичные тем, которые генерирует k1 .

Сходство S ( R1 , R2 ) между двумя наборами результатов R1 и R2 вычисляется следующим образом:
2 * (number of same elements both in _R1_ and _R2_) / ( (total number of elements in _R1_) + (total number of elements in _R2_) ).Пример: R1 = {1,2,3} и R2 = {2,3,4,5} дает S ( R1 , R2) = (2 * | {2,3} |) / | {1,2,3} |+ | {2,3,4,5} |= (2 * 2) / (3 + 4) = 4/7 = 0,57.

Существует более 100 000 ключевых слов, следовательно, более 100 000 наборов результатов.До сих пор мне удалось решить эту проблему только трудным путем O (N ^ 2), где каждый набор результатов сравнивается с любым другим набором.Это занимает много времени.

Есть кто-то с лучшей идеей?

Некоторые подобные сообщения, которые не решают проблему полностью:

• Какхранить наборы, быстро находить похожие шаблоны?
• эффективный алгоритм сравнения сходств между наборами чисел?

Answer 1

Чтобы упростить задачу, предполагается, что все ключевые слова имеют 10 результатов, а k1 - ключевое слово для сравнения. Вы удаляете 9 результатов из набора каждого ключевого слова. Теперь сравните последний результат с k1, и ключевые слова с тем же последним результатом - это то, что вы хотите. Если ключевое слово имеет 1 общий результат с k1, остается только 1% вероятность , что оно останется. Ключевое слово с 5 общими для k1 результатами будет иметь 25% вероятность . Возможно, вы подумаете, что 1% слишком велик, тогда вы можете повторить процесс выше n раз, и ключевое слово с общим результатом 1 будет иметь вероятность 1% ^ n. Время составляет O (N) .

Answer 2

Исправлен ли ваш критерий сходства , или мы можем применить немного разнообразия для ускорения поиска?

Альтернатива:

Альтернатива, которая пришла мне в голову:

Учитывая ваш результирующий набор R1, вы можете просмотреть документы и создать гистограмму для других ключевых слов, с которыми эти документы будут сопоставлены. Затем, если данное альтернативное ключевое слово получает, скажем, по крайней мере # R1 / 2 хитов, вы указываете его как «схожий».

Большая разница в том, что вы не рассматриваете документы, которые вообще не находятся в R1.

---

Целый

Если вам нужно решение, точно соответствующее вашим требованиям, я считаю, что было бы достаточно вычислить набор R2 только для тех ключевых слов, которые удовлетворяют вышеуказанному «альтернативному» критерию. Я думаю (необходимо математическое доказательство!), Что если «альтернативный» критерий не будет выполнен, то нет никаких шансов, что ваш будет.

Answer 3

Один вопрос - результаты в отсортированном порядке?

Что-то, что пришло в голову, объединяет оба набора, сортирует это и находит дубликаты. Может быть уменьшено до O (nlogn)