Методы бикластеризации для анализа интернет-данных


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


У множества документов в Интернете имеются дубликаты, в связи с чем необходимы средства эффективного вычисления кластеров документов-дубликатов [20, 21, 22, 26, 27, 40, 44, 46, 70, 61]. В этом разделе описываются исследования, посвященные применению алгоритмов Data Mining для поиска кластеров дубликатов с использованием синтаксических и лексических методов составления образов документов. На основе экспериментов делаются некоторые выводы о способе выбора параметров методов.

Постановка задачи

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

Обычно дубликаты документов определяются на основе отношения сходства на парах документах: два документа сходны, если некоторая числовая мера их сходства превышает некоторый порог [20]. По отношению сходства вычисляются кластеры сходных документов, например, по транзитивному замыканию отношения сходства [20]. Вначале, после снятия HTML-разметки документы, как линейные последовательности слов (символов), преобразуются во множества. Здесь двумя основными схемами (определяющими весь возможный спектр смешанных методов) являются синтаксические и лексические методы. К синтаксическим относится метод шинглирования [22], в котором документ в итоге представляется набором хеш-кодов; этот метод испоьзовался в поисковых системах Google и AltaVista. В лексических методах [44] большое внимание уделяется построению словаря — набора дескриптивных слов; известны его разновидности, такие I-match и метод ключевых слов Ильинского [44].

На втором этапе из документа, представленного множеством синтаксических или лексических признаков, выбирается подмножество признаков, образующее краткое описание (образ) документа. На третьем этапе определяется отношение сходства на документах с помощью некоторой метрики сходства, сопоставляющей двум документам число в интервале [0, 1], и некоторого параметра — порога, выше которого находятся документы-дубликаты.




Начало  Назад  Вперед



Книжный магазин