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

Размещено на http://www.allbest.ru/

О ПОИСКЕ СХОДСТВА ИНТЕРНЕТ-ДОКУМЕНТОВ С ПОМОЩЬЮ ЧАСТЫХ ЗАМКНУТЫХ МНОЖЕСТВ ПРИЗНАКОВ^{** Работа выполнена при по}ддержке “Яндекс” (номер гранта 102820)

Д.И. Игнатов¹¹ 101000, г. Москва, ул. Мясницкая, д. 20, ГУ ВШЭ, idm-viniti@yandex.ru , С.О. Кузнецов²² 101000, г. Москва, ул. Мясницкая, д. 20, ГУ ВШЭ, skuznetsov@hse.ru

Множество документов в Интернете имеют дубликаты, в связи с чем необходимы средства эффективного вычисления кластеров документов-дубликатов [Broder 2000, Ilyinsky et al 2002, Kolcz 2004, Pugh et al 2003]. В работе исследуется применение алгоритмов Data Mining для поиска кластеров дубликатов с использованием синтаксических и лексических методов составления образов документов. На основе экспериментальной работы делаются некоторые выводы о способе выбора параметров методов.

Введение

кластер дубликат документ программный

Огромное число документов (по некоторым источникам до 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], параметры шинглирования, величина порога сходства образов документов. Одной из задач проекта было связать вычисление попарного сходства образов документов с построением кластеров документов, так чтобы, с одной стороны, получаемые кластеры были бы независимы от порядка рассмотрения документов (в отличие от методов кластерного анализа), а с другой стороны гарантировали бы наличие реального попарного сходства всех образов документов в кластере.

1. Описание вычислительной модели

В качестве методов представления документов (создания образа документа) мы использовали стандартные синтаксические и лексические подходы с разными параметрами.

В рамках синтаксического подхода была реализована схема шинглирования и составление краткого образа (скетча) документов на основе методов «n минимальных элементов в перестановке» и «минимальные элементы в n перестановках», описание, которое можно найти, например, в [Broder et al 1998, Broder 2000]. Программа shingle с двумя параметрами length и offset порождает для каждого текста набор последовательностей слов (шинглов) длины length, так что отступ от начала одной последовательности до начала другой последовательности в тексте имеет размер offset. Полученное таким образом множество последовательностей хэшируется, так что каждая последовательность получает свой хэш-код.

Далее из множества хэш-кодов, соответствующему документу, выбирается подмножество фиксированного (с помощью параметра) размера с использованием случайных перестановок, описанных в работах [Broder 1997, Broder et al 1998, Broder 2000]. При этом вероятность того, что минимальные элементы в перестановках хэш-кодов на множествах шинглов документов A и B (эти множества обозначаются через и , соответственно) совпадут, равна мере сходства этих документов sim(A,B):

Основные определения, связанные с частыми замкнутыми множествами, естественно даются в терминах анализа формальных понятий (АФП) [Ganter et al, 1999]. Контекстом в АФП называют тройку K = (G, M, I), где G -- множество объектов, M -- множество признаков, а отношение I G M говорит о том, какие объекты какими признаками обладают. Для произвольных A G и B M определены операторы Галуа:

A' = {m M | g A (g I m)};

B' = {g G | m B (g I m)}.

Оператор '' (двукратное применение оператора ') является оператором замыкания: он идемпотентен (A'''' = A''), монотонен (A B влечет A'' B'') и экстенсивен (A A ''). Множество объектов A G, такое, что A'' = A, называется замкнутым. Аналогично для замкнутых множеств признаков - подмножеств множества M. Пара множеств (A, B), таких, что A G, B M, A' = B и B' = A, называется формальным понятием контекста K. Множества A и B замкнуты и называются объемом и содержанием формального понятия (A, B) соответственно. Для множества объектов A множество их общих признаков A' служит описанием сходства объектов из множества A, а замкнутое множество A'' является кластером сходных объектов (с множеством общих признаков A'). Для произвольного B M величина |B'| = |{g G | m B (g I m)}| называется поддержкой (support) B и обозначается sup(B). Нетрудно видеть, что множество B замкнуто тогда и только тогда когда для любого D B имеет место sup(D) < sup(B). Именно это свойство используется для определения замкнутости в методах Data Mining. Множество B M называется k-частым если |B'| > k (то есть множество признаков B встречается в более чем k объектах), где k - параметр. Вычисление частых замкнутых множеств признаков (содержаний) приобрело важность в Data Mining благодаря тому, что по этим множествам эффективно вычисляются множества всех ассоциативных правил [Pasquier et al, 1999].

Хотя теоретически размер множества всех замкнутых множеств признаков (содержаний) может быть экспоненциальным относительно числа признаков, на практике, таблицы данных сильно «разрежены» (то есть среднее число признаков на один объект весьма мало) и число замкнутых множеств невелико. Для таких случаев существуют весьма эффективные алгоритмы построения всех наиболее частых замкнутых множеств признаков (см. также наш обзор по алгоритмам построения всех замкнутых множеств [Kuznetsov et al, 2002]). В последние годы проводился ряд соревнований по быстродействию таких алгоритмов на серии международных семинаров под общим названием FIMI (Frequent Itemset Mining Implementations). Пока лидером по быстродействию считается алгоритм FPmax* [Grahne, 2003], показавший наилучшие результаты по быстродействию в соревновании 2003 года. Мы использовали этот алгоритм для построения сходства документов и кластеров сходных документов. При этом в роли объектов выступали элементы описания (шинглы или слова), а в роли признаков - документы. Для такого представления «частыми замкнутыми множествами» являются замкнутые множества документов, для которых число общих единиц описания в образах документов превышает заданный порог.

2. Программная реализация и компьютерные эксперименты

Программные средства для проведения экспериментов в случае синтаксических методов включали следующие блоки:

1. Парсер формата XML для коллекции ROMIP

2. Снятие html-разметки.

3. Нарезка шинглов с заданными параметрами

4. Хэширование шинглов

5. Составление образа документов путем выбора подмножества (хэш-кодов) шинглов с помощью методов «n минимальных элементов в перестановке» и «минимальные элементы в n перестановках».

6. Составление по результатам методов 4-5 инвертированной таблицы «список идентификаторов документов - шингл» - подготовка данных к формату программ вычисления замкнутых множеств .

7. Вычисление частых замкнутых множеств с заданным порогом общего числа документов, в которое входит данное множество шинглов: программа MyFim (реализующая алгоритм FPmax*)

8. Сравнение со списком дубликатов РОМИП - программа Comparator.

В качестве экспериментального материала нами использовалась URL-коллекция РОМИП, состоящая из 52 файлов, общего размера 4,04 Гб. Для проведения экспериментов коллекция разбивалась на несколько частей, включающих от трех до двадцати четырех файлов (приблизительно от 5% до 50% от размера всей коллекции).

Параметры шинглирования, использовавшиеся в экспериментах: число слов в шингле 10 и 20, отступ между началом соседних шинглов 1. Данное значение отступа означает, что начальное множество шинглов включало все возможные последовательности цепочек слов.

Эксперименты проводились на персональном компьютере P-IV HT с тактовой частотой 3.0 ГГц, объемом оперативной памяти 1024 Мб и операционной системой Windows XP Professional. Результаты экспериментов и время, затраченное на их проведение, частично приводятся в следующих таблицах.

1. Результаты работы метода “n минимальных элементов в перестановке”.

2. Результаты работы метода “минимальные элементы в n перестановках”

3. Время работы MyFim для метода “n минимальных элементов в перестановке”.

4. Время работы MyFim для метода “минимальные элементы в n перестановках”.

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

5. Сравнение эффективности алгоритмов поиска максимальных замкнутых множеств.

По диаграмме видно, что наилучшие результаты показали алгоритмы Fpmax* и Afopt. А алгоритм AddIntent* из сообщества FCA-алгоритмов даже превзошел Mafia из FIMI, что является неплохим результатом для, как правило, более ресурсоемких алгоритмов первой группы.

Заключение

По результатам наших экспериментов по использованию методов порождения частых замкнутых множеств в сочетании с традиционными синтаксическими и лексическими средствами можно сделать следующие выводы.

Методы порождения частых замкнутых множеств представляют эффективный способ определения сходства документов одновременно с порождением кластеров сходных документов.

На результаты синтаксических методов определения дубликатов значительное влияние оказывает параметр «длина шингла». Так в наших экспериментах результаты для длины шингла, равной 10, были существенно ближе к списку дублей РОМИП чем для длины шингла, равной 20, 15 и 5.

В экспериментах для всех значений параметров не было обнаружено существенного влияния использования метода «минимальные элементы в n перестановках» на качество результатов. По-видимому, случайности, задаваемой отбором шинглов с помощью метода «n минимальных элементов в перестановке» достаточно на практике. Необходимы дальнейшие эксперименты с использованием различных значений параметров синтаксических методов, и их сравнение с результатами лексических методов, использующих инвертированные индексы коллекций. Необходимо сравнение методов кластеризации использующих замкнутые множества признаков с алгоритмами, основанными на поиске минимальных разрезов вершин (cut) в двудольных графах, в которых множества вершин соответствуют множествам документов и множествам - признаков [Dhillon, 2001, Zhao et al, 2004]. Эти методы родственны, поскольку замкнутые множества документов естественным образом выражаются через минимальные разрезы такого рода двудольных графов.

Список литературы

[Broder, 1997] A. Broder, On the resemblance and containment of documents, in Proc. Compression and Complexity of Sequences (SEQS: Sequences'97) .

[Broder et al, 1998] A. Broder, M. Charikar, A.M. Frieze, M. Mitzenmacher, Min-Wise Independent Permutations, in Proc. STOC, 1998.

[Broder, 2000] A. Broder, Identifying and Filtering Near-Duplicate Documents, in Proc. Annual Symposium on Combinatorial Pattern Matching, 2000.

[Cho et al, 1999] J. Cho, N. Shivakumar, H. Garcia-Molina, Finding replicated web collections, 1999

[Chowdhury et al, 2002]A. Chowdhury, O. Frieder, D.A.Grossman, and M.C. McCabe, Collection statistics for fast duplicate document detection, ACM Transactions on Information Systems, 20(2): 171-191, 2002

[Ganter et al, 1999]. B. Ganter and R. Wille, Formal Concept Analysis: Mathematical Foundations, Springer, 1999.

[Grahne, 2003] G. Grahne and J. Zhu, Efficiently Using Prefix-trees in Mining Frequent Itemsets, in Proc. FIMI Workshop, 2003.

[Haveliwala et al, 2002] T. H. Haveliwala, A. Gionis, D. Klein, and P. Indyk ,

Evaluating Strategies for Similarity Search on the Web, in Proc. WWW'2002, Honolulu, 2002.

[Ilyinsky et al, 2002] S. Ilyinsky, M.Kuzmin, A. Melkov, I. Segalovich, An efficient method to detect duplicates of Web documents with the use of inverted index, in Proc. 11th Int. World Wide Web Conference (WWW'2002).

[Kolcz, 2004] A. Kolcz, A. Chowdhury, J. Alspector, Improved Robustness of Signature-Based Near-Replica Detection via Lexicon Randomization, in Proc. KDD'04, Seattle, 2004.

[Kuznetsov et al, 2002]. S.O. Kuznetsov and S.A. Obiedkov, Comparing Performance of Algorithms for Generating Concept Lattices, Journal of Experimental and Theoretical Artificial Intelligence, vol. 14 (2002), pp. 189-216.

[Pasquier et al, 1999] N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal, Efficient Mining of Association Rules Using Closed Itemset Lattices, Inform. Syst., 24(1), 25-46, 1999.

[Shivakumar et al 1998] N. Shivakumar, H. Garcia-Molina, Finding near-replicas of documents on the web, 1998

[Pugh et al 2003].W. Pugh, M. Henzinger, Detecting duplicate and near-duplicate files

United States Patent 6658423 (December 2, 2003).

[Dhillon, 2001] I.S. Dhillon, Co-clustering documents and words using bipartite spectral graph partitioning. In Knowledge Discovery and Data Mining, pp. 269-274, 2001.

[Zhao et al, 2004] Y.Zhao and G. Karypis, Empirical and Theoretical Comparison of Selected Criterion Functions for Document Clustering. Machine Learning, vol. 55, pp. 311-331, 2004.

Размещено на Allbest.ru