Введение. О поиске сходства интернет-документов с помощью частых замкнутых множеств признаков

Огромное число документов (по некоторым источникам до 30%) в Интернете имеют дубликаты, в связи с чем поисковые машины должны обладать эффективными средствами вычисления кластеров дубликатов. Наличие таких средств позволяет существенно сократить объем необходимых для решения задачи вычислительных и аппаратных ресурсов предприятия. Происхождение дубликатов может быть разным — от дублирования компаниями собственной информации на разных серверах (создание зеркал) до злонамеренных — обмана программ индексаторов веб-сайтов, незаконного копирования и спамерских рассылок. Обычно дубликаты документов определяются на основе отношения сходства на парах документах: два документа сходны, если некоторая числовая мера их сходства превышает некоторый порог [Broder, 1997]. По отношению сходства вычисляются кластеры сходных документов, например, по транзитивному замыканию отношения сходства [1]. Вначале, после снятия HTML-разметки, документы, как линейные последовательности слов (символов), преобразуются во множества. Здесь двумя основными схемами (определяющими весь возможный спектр смешанных методов) являются синтаксический и лексический метод. К синтаксическим относится метод шинглирования [Broder, 2000], в котором документ в итоге представляется набором хеш-кодов, метод находил применение в поисковой системе Google и AltaVista. В лексических методах [Ilyinsky et al, 2002] большое внимание уделяется построению словаря — набора дескриптивных слов, известны его разновидности, такие I-match и метод ключевых слов Ильинского [Ilyinsky et al, 2002]. На втором этапе из документа, представленного множеством синтаксических или лексических признаков, выбирается подмножество признаков, образующее краткое описание (образ) документа. На третьем этапе определяется отношение сходства на документах, с помощью некоторой метрики сходства, сопоставляющей двум документам число в интервале [0, 1], и некоторого параметра — порога, выше которого находятся документы дубликаты. На основе отношения сходства документы объединяются в кластеры (полу-)дубликатов. Определение кластера также может варьироваться. Одно из возможных определений, часто используемых на практике (например, в компании AltaVista), но наиболее слабых, упоминается в обзоре [Broder, 1997]: если документам Интернета сопоставить граф, вершины которого соответствуют самим документам, а ребра — отношению «быть (почти) дубликатом», то кластером объявляется компонента связности такого графа. Достоинством такого определения является эффективность вычислений. Недостаток такого подхода очевиден: отношение «быть (почти) дубликатом» не является транзитивным, поэтому в кластер сходных документов могут попасть абсолютно разные документы. Противоположным — «самым сильным» — определением кластера, исходя из отношения «быть (почти) дубликатом», было бы рассмотрение в его качестве клик графа. При этом каждый документ из кластера должен быть сходным со всеми другими документами того же кластера. Такое определение кластера более адекватно передает представление о групповом сходстве, но, к сожалению, практически не применимо в масштабе Интернета, в силу того, что поиск клик в графе — классическая труднорешаемая задача. Исходя из предложенных формулировок, можно было бы находить необходимый баланс между соответствием определения кластеров множествам «в самом деле» сходных документов и сложностью вычисления кластеров. В данной работе мы рассматриваем сходство не как отношение на множестве документов, а как операцию, сопоставляющую двум документам множество общих элементов их сокращенных описаний, где в качестве элементов описания выступают либо синтаксические, либо лексические единицы. Кластер дубликатов определяется как множество документов, у которых число общих элементов описания превышает определенный порог. В работе приводятся результаты экспериментальной проверки данного метода на основе сравнения результатов его применения (для разных значений порогов) со списком дубликатов, составленным на основе результатов применения других методов к тому же множеству документов. Мы исследовали влияние следующих параметров модели на результат: использование синтаксических или лексических методов представления документов, использование методов «n минимальных элементов в перестановке» или «минимальные элементы в n перестановках» [Broder, 1997], параметры шинглирования, величина порога сходства образов документов. Одной из задач проекта было связать вычисление попарного сходства образов документов с построением кластеров документов, так чтобы, с одной стороны, получаемые кластеры были бы независимы от порядка рассмотрения документов (в отличие от методов кластерного анализа), а с другой стороны гарантировали бы наличие реального попарного сходства всех образов документов в кластере.