Методы бикластеризации для анализа интернет-данных
На основе отношения сходства документы
На основе отношения сходства документы объединяются в кластеры (полу-)дубликатов. Определение кластера также может варьироваться. Одно из возможных определений, часто используемых на практике (например, в компании AltaVista), но наиболее слабых, упоминается в обзоре [20]: если документам Интернета сопоставить граф, вершины которого соответствуют самим документам, а ребра — отношению «быть (почти) дубликатом», то кластером объявляется компонента связности такого графа. Достоинством такого определения является эффективность вычислений. Недостаток такого подхода очевиден: отношение «быть (почти) дубликатом» не является транзитивным, поэтому в кластер сходных документов могут попасть абсолютно разные документы.
В качестве противоположного — «самого сильного» — определения кластера, опирающимся на отношение «быть (почти) дубликатом», можно принять клики графа. При этом каждый документ из кластера должен быть сходным со всеми другими документами того же кластера. Такое определение кластера более адекватно передает представление о групповом сходстве, но, к сожалению, практически не применимо в масштабе Интернета, поскольку поиск клик в графе — классическая труднорешаемая задача.
Исходя из предложенных формулировок, можно было бы находить необходимый баланс между соответствием определения кластеров множествам «в самом деле» сходных документов и сложностью вычисления кластеров. Здесь мы рассматриваем сходство не как отношение на множестве документов, а как операцию, сопоставляющую двум документам множество общих элементов их сокращенных описаний, где в качестве элементов описания выступают либо синтаксические, либо лексические единицы. Кластер дубликатов определяется как множество документов, у которых число общих элементов описания превышает определенный порог.
Приводятся результаты экспериментальной проверки данного метода на основе сравнения результатов его применения (для разных значений порогов) со списком дубликатов, составленным на основе результатов применения других методов к тому же множеству документов. Исследовалось влияние на результат следующих параметров модели: использование синтаксических или лексических методов представления документов, использование методов «n минимальных элементов в перестановке» и «минимальные элементы в n перестановках» [20], параметры шинглирования, величина порога сходства образов документов. Одна из задач проекта заключалась в том, чтобы связать вычисление попарного сходства образов документов с построением кластеров документов, чтобы, с одной стороны, получаемые кластеры были бы независимы от порядка рассмотрения документов (в отличие от методов кластерного анализа), а с другой стороны гарантировали бы наличие реального попарного сходства всех образов документов в кластере.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий