Обнаружение нечетких дубликатов документов. Алгоритмы

Недавно в Переславле-Залесском проходила конференция RCDL – «National Russian Research Conference: Digital Libraries». На ней Илья Сегалович читал доклад «Сравнительный анализ методов определения нечетких дубликатов для Web-документов».

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

Алгоритм по нахождению дубликатов документов должен обладать двумя взаимоисключающими свойствами:

1. Находить все без исключения дубликаты документов без ложных срабатываний.
2. Иметь огромную производительность, так как в разумное время необходимо обрабатывать миллирады документов.

Задача по разработке такого алгоритма не нова и в мире существует множество алгоритмов стремящихся содержать оба свойства.

Илья Сегалович, совместно с Зеленковым Ю.Г, провели исследование 9 существующих алгоритмов. Алгоритмы сравнивались по F-мере (гармоническое среднее меры и полноты).

Также для сравнения в исследование был включен алгоритм поиска точных дубликатов документов и было предложена два экспериментальных алгоритма поиска неточных дубликатов. Исследования проводились на коллекции сайтов РОМИП (около 500.000 документов).

Краткое описание алгоритмов

A0 – MD5
Вычисляет сигнатуру документа по алгоритму MD5. Алгоритм ищет не неточные, а точные дубликаты документов.

A1 – TF
Построение частотного словаря слов документа. Слова выбираются и сцепляются в строку 6 слов в алфавитном порядке с наибольшим значением нормированной внутридокументной частоты слова в документе (tf). Сигнатура документа вычисляется по алгоритму CRC32 для полученной строки.

A2 - TF*IDF
В строку сцепляются 6 слов в алфавитном порядке, имеющих максимальный «вес» (wt). «Вес» слова (wt) вычисляется по формуле Okapi BM25 с параметрами k = 2 и b = 0.75. Вес слова зависит от числа документов, в которых оно встретилось хотя бы один раз, и от средней длины документа. Сигнатура документа вычисляется по алгоритму CRC32 для полученной строки.

A3 - TF*RIDF
В строку сцепляются 6 слов в алфавитном порядке, имеющих максимальный «вес» (wt). «Вес» слова вычисляется на основе алгоритма Residual IDF и зависит от числа документов, в которых слово встречается хотя бы один раз, и от суммарной частоты каждого слова в коллекции. Сигнатура документа вычисляется по алгоритму CRC32 для полученной строки.

A4 - Long Sent
В строку сцепляются два самых длинных предложения (по числу слов) в документе. Сигнатура документа вычисляется по алгоритму CRC32 для полученной строки.

A5 - Heavy Sent
В строку сцепляются два предложения с максимальным «весом» (ws). «Вес» предложения вычисляется как сумма «весов» (wt), входящих в него слов. «Веса» слов определяются по формулам алгоритма A2. Сигнатура документа вычисляется по алгоритму CRC32 для полученной строки.

A6 – Megashingles
В исследовании выбирались 36 5-словных шинглов, которые разбивались на 6 групп по 6 и получалось 6 «супершинглов». Из «супершинглов» составлялись всевозможные парные сочетания, т.е. всего 15 «мегашинглов». Все эти 15 мегашинглов составляют сигнатуру документа.

A7 - Lex Rand
Для документа строится словарь, аналогично алгоритму A2. Из словаря выбрасываются слова с максимальным и минимальным значением IDF (инверсия частоты, с которой некоторое слово встречается в документах коллекции). На основе этого словаря строятся еще 11 словарей, содержащих на 30% слов меньше случайным образом. Далее строится 11 I-Match сигнатур (хеш-функция SHA1). Если хотя бы одна сигнатура совпадает, то документы считаются дубликатами.

A8 - Log Shingles
Из всего множества 5-словных шинглов выбираются шинглы, делящиеся на степени числа 2. Они составляют сигнатуру документа.

A9 - Descr Words
Для документов строится словарь из «опорных» слов, из которых вычисляются двоичные векторные сигнатуры документов. Сигнатуры кластеризуются в группы нечетких дубликатов на основе признака совпадения.

A10 - Opt Freq
В строку выбираются и сцепляются 6 слов с максимальным «весом» (wt) в алфавитном порядке. «Вес» слова зависит от IDF (инверсия частоты, с которой некоторое слово встречается в документах коллекции), которая повышается по закону параболы, если она меньше «оптимальной», или уменьшается по закону гиперболы, если она больше оптимального. Сигнатура документа вычисляется по алгоритму CRC32 для полученной строки.

Метод «декомпозиции» (A11)
Алгоритм основан на наблюдении, что размер документа в словах служит хорошим разделяющим свойством и на нахождении общих списков документов, обладающих одинаковым признаком. Экспериментальный алгоритм.

Метод «3+5» (A12)
Для документа строятся сигнатуры трех самых длинных предложений. Сигнатуры документов заносятся в файл сигнатур и сортируются с учетом коэффициентом сходства документов. В итоге исходный файл преобразуется во множество сравнительно коротких цепочек, содержащих компактные (с небольшим разбросом) монотонно неубывающие последовательности длин документов. Два документа считаем дубликатами, если у них совпадают сигнатуры самых длинных предложений или из трех сигнатур совпадают две, неважно в каком порядке. Экспериментальный алгоритм.

Результаты исследований и экспериментальная проверка новых алгоритмов

Алгоритм A11 показал практически 100% полноту и точность на тестовой коллекции, одновременно при вполне приемлемой производительности. К сожалению, Илья Сегалович не привел конкретных цифр по нему.

В таблице алгоритмы отсортированы по F-мере. «Полнота» означает число найденных неточных дубликатов. «Точность» показатель числа ложных срабатываний. Всего все (неэкспериментальные) алгоритмы обнаружили 17.471.200 пар дубликатов.

Лучше всего на коллекции сайтов РОМИП проявил себя алгоритм A4 - Long Sent. Родственный ему алгоритм A5 - Heavy Sent тоже показал хорошие результаты. Но нельзя забывать, что коллекция сайтов РОМИП – не реальный индекс поисковой машины и в реальности лучшие показатели могут быть у алгоритмов серии A1-A3 или у алгоритма A10 - Opt Freq. Ухудшение на практике может происходить за счет уменьшения «полноты», что можно наблюдать в основном поиске Яндекс или Google.

На коллекции сайтов РОМИП экспериментальный алгоритм Метод «3+5» (A12) показал себя лучше существующих. Причем, ясно, что он особенно хорошо справляется с малыми документами (менее 5 предложений). Главное отличие этого метода, от других, состоит в том, что при его создании И. Сегалович и Ю. Зеленков старались опираться только на «локальные» свойства документов, а не использовать глобальные параметры всей коллекции.

Литература:

1. Сравнительный анализ методов определения нечетких дубликатов для Web-документов. Зеленков Ю.Г, Сегалович И.В. 2007.
2. TF-IDF. Википедия. http://ru.wikipedia.org/wiki/TF-IDF
3. F-мера. Википедия.