Исследование применения алгоритмов Data Mining для поиска кластеров дубликатов с использованием синтаксических и лексических методов составления образов документов. Программная реализация и компьютерные эксперименты. Способ выбора параметров методов.
Аннотация к работе
Обычно дубликаты документов определяются на основе отношения сходства на парах документах: два документа сходны, если некоторая числовая мера их сходства превышает некоторый порог [Broder, 1997]. На третьем этапе определяется отношение сходства на документах, с помощью некоторой метрики сходства, сопоставляющей двум документам число в интервале [0, 1], и некоторого параметра - порога, выше которого находятся документы дубликаты. Одно из возможных определений, часто используемых на практике (например, в компании ALTAVISTA), но наиболее слабых, упоминается в обзоре [Broder, 1997]: если документам Интернета сопоставить граф, вершины которого соответствуют самим документам, а ребра - отношению «быть (почти) дубликатом», то кластером объявляется компонента связности такого графа. Мы исследовали влияние следующих параметров модели на результат: использование синтаксических или лексических методов представления документов, использование методов «n минимальных элементов в перестановке» или «минимальные элементы в n перестановках» [Broder, 1997], параметры шинглирования, величина порога сходства образов документов. Одной из задач проекта было связать вычисление попарного сходства образов документов с построением кластеров документов, так чтобы, с одной стороны, получаемые кластеры были бы независимы от порядка рассмотрения документов (в отличие от методов кластерного анализа), а с другой стороны гарантировали бы наличие реального попарного сходства всех образов документов в кластере.По результатам наших экспериментов по использованию методов порождения частых замкнутых множеств в сочетании с традиционными синтаксическими и лексическими средствами можно сделать следующие выводы. Методы порождения частых замкнутых множеств представляют эффективный способ определения сходства документов одновременно с порождением кластеров сходных документов. На результаты синтаксических методов определения дубликатов значительное влияние оказывает параметр «длина шингла».