Алгоритм группировки похожих наборов

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

Например, ключевое слово 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, < em>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), где каждый набор результатов сравнивается с любым другим набором. Это занимает много времени.

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

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


set aggregate algorithm grouping similarity
person ddofborg    schedule 01.03.2011    source источник
comment
citeseerx.ist.psu.edu/viewdoc/summary?doi= 10.1.1.110.3089   -  person sclv    schedule 01.03.2011

Ответы (3)


arrow_upward
0
arrow_downward

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

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

person NirmalGeo    schedule 01.03.2011
comment
Вам все равно нужно будет комбинировать каждый набор с другим набором, что дает n * (n-1) комбинаций, верно? - person ddofborg; 01.03.2011

arrow_upward
0
arrow_downward

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

person jerry_sjtu    schedule 01.03.2011

arrow_upward
0
arrow_downward

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

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

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

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

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

Точно?

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

person CygnusX1    schedule 01.03.2011