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

Материал из MachineLearning.

Огромное число документов (по некоторым источникам до 30 %) в Интернете имеют дубликаты, в связи с чем поисковые машины должны обладать эффективными средствами вычисления кластеров дубликатов. Наличие таких средств позволяет существенно сократить объем необходимых для решения задачи вычислительных и аппаратных ресурсов предприятия. Происхождение дубликатов может быть разным — от дублирования компаниями собственной информации на разных серверах (создание зеркал) до злонамеренных — обмана программ индексаторов веб-сайтов, незаконного копирования и спамерских рассылок. В данной работе сходство рассматривается не как отношение на множестве документов, а как операция, сопоставляющяя двум документам множество общих элементов их сокращенных описаний, в виде синтаксических единиц. Кластер дубликатов определяется как множество документов, у которых число общих элементов описания превышает определенный порог. Одной из задач проекта было связать вычисление попарного сходства образов документов с построением кластеров документов, так чтобы, с одной стороны, получаемые кластеры были бы независимы от порядка рассмотрения документов (в отличие от методов кластерного анализа), а с другой стороны гарантировали бы наличие реального попарного сходства всех образов документов в кластере.

В рамках синтаксического подхода была реализована схема «шинглирования» (от англ. shingle — черепица) и составление краткого образа (скетча) документов на основе методов «n минимальных элементов в перестановке» и «минимальные элементы в n перестановках», описание которого можно найти, например, в~[A.~Broder, 1998, 2000]. Шинглирование осуществляется с двумя параметрами $length$ и $offset$ и позволяет порождать для каждого текста набор последовательностей слов или символов (шинглов) длины length, так что отступ от начала одной последовательности до начала другой последовательности в тексте имеет размер $offset$ . Полученное таким образом множество последовательностей хэшируется, так что каждая последовательность получает свой хэш-код. Далее из множества хэш-кодов, соответствующему документу, выбирается подмножество фиксированного (с помощью параметра) размера с использованием случайных перестановок, описанных в работах~[A.~Broder, 1997, 1998, 2000]. При этом вероятность того, что минимальные элементы в перестановках хэш-кодов на множествах шинглов документов $A$ и $B$ (эти множества обозначаются через $F_A$ и $F_B$ , соответственно) совпадут, равна мере сходства этих документов $sim(A,B)$ :

$P[min\{\pi (F_A)\}=min\{\pi (F_B)\}]=\frac{|F_A \cap F_B|}{|F_A \cup F_B|}=sim(A,B)$

Опишем предлагаемую модель. Рассмотрим формальный контекст $\mathbb{K}_{DF}=(D,F,I)$ , где $D$ — множество документов, а $F$ — множество хеш-кодов (fingerprints), отношение $I$ показывает, что некий объект $d$ обладает признаком $f$ в том и только том случае, когда $dIf$ . Для множества документов $A \subseteq D$ множество их общих признаков $A'$ служит описанием их сходства, а замкнутое множество $A''$ является кластером сходных объектов (с множеством общих признаков $A'$ ). Для произвольного $B \subseteq F$ величина $|B'| = |\{g \in G | \forall m \in B (g I m)\}|$ является поддержкой $B$ и обозначается $supp(B)$ . Нетрудно видеть, что множество $B$ замкнуто тогда и только тогда, когда для любого $C \supset B$ имеет место $supp(D) < supp(B)$ . Именно это свойство используется для определения замкнутости в методах Data Mining. Множество $B \subseteq M$ называется $k$ -частым, если $|B'| > k$ (то есть множество признаков B встречается в более чем $k$ объектах), где $k$ --- параметр. Фактически будем вычислять частные замкнутые множества признаков для дуального к $\mathbb{K}_{DF}$ контекста, т.е. находить такие множества документов-признаков контекста $\mathbb{K}_{FD}=(F,D,I)$ , для которых размер множества их общих шинглов превышает заданный порог сходства.

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

Публикации

Кузнецов С.О., Игнатов Д.И., Объедков С.А., Самохин М.В. Порождение кластеров документов дубликатов: подход, основанный на поиске частых замкнутых множеств признаков. 2005. Автоматическая обработка веб-данных. Москва: “Яndex”, 2005, стр. 302 – 319 ([1])
Игнатов Д.И., Кузнецов С.О. О поиске сходства Интернет-документов с помощью частых замкнутых множеств признаков // Труды 10-й национальной конференции по искусственному интеллекту с международным участием (КИИ’06). – М.:Физматлит, 2006, Т.2, стр.249-258 ([2])
Д.И. Игнатов, С.О.Кузнецов, В.Б. Лопатникова, И.А. Селицкий. Разработка и апробация системы поиска дубликатов в текстах проектной документации. Бизнес-информатика//междисциплинарный научно-практический журнал, № 4, 2008, стр. 21 - 28 ([3])
D. Ignatov, K. Jánosi-Rancz, Towards a framework for near-duplicate detection in document collections based on closed sets of attributes// Acta Universitatis Sapientiae, Informatica, 1, 2 (2009) 215−233 ([4])
D.I. Ignatov, S.O. Kuznetsov. Frequent Itemset Mining for Clustering Near Duplicate Web Documents// In proceedings of The 17th International Conference on Conceptual Structures, S. Rudolph, F. Dau, and S.O.Kuznetsov (Eds.): ICCS 2009, LNCS (LNAI) 5662, pp. 185–200, Springer-Verlag Berlin Heidelberg, 2009 ([5])