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

       

Информационный поиск (Information Retrieval): бикластеризация документов


В задачах информационного поиска и анализа текстов (text mining) бикластеризация применяется для обнаружения кластеров документов, обладающих сходными свойствами только по нескольким признакам, таким как слова и изображения. Такая информация очень важна для запросов и индексации поисковых интернет-систем. Диллон в своей работе [29] использует бикластеризацию для одновременного группирования документов и слов. Исходные данные представляют собой матрицу F, в которой строки отвечают словам, а столбцы — документам, а ненулевой элемент

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

в документе

:
, где

показывает число вхождений слова

в документ

,

— общее число документов, а

— число документов, содержащих слово

. Такую матрицу принято называть матрицей инциденций, а вместо термина бикластеризация использовать кокластеризация (co-clustering).

Проблемы кластеризации документов и слов в отдельности хорошо изучены в контексте информационного поиска и анализа текстов. Однако кластеризации лишь по одному измерению оказывается недостаточно. Допустим, имеется коллекция документов никак не сгруппированных. Тогда кластеризация помогает организовать коллекцию для целей дальнейшей навигации и поиска. Слова могут быть кластеризованы на основе документов в которых они встречаются. Кластеры слов полезны для автоматического построения статистических тезаурусов, уточнения запросов и автоматической классификации документов.

В этой работе Диллон пытается выявить подмножества слов и документов, сильно связанных друг с другом. В его модели, как и в работе Танай и др.[76], матрице исходных данных сопоставляется двудольный граф, и автор использует спектральный подход, похожий на предложенный Клугер и др. [45]. Эксперименты проводятся на трех коллекциях документов: Medline (1033 медицинских статьи), Cranfield (1400 статей про системы аэронавтики) и Cisi (1460 статьи по информационному поиску). Другие примеры бикластеризации для этого типа матриц можно найти в работе Диллона [30].

Для задачи выявления документов-дубликатов было предпринято две относительно успешные попытки использования ФАП и частых замкнутых множеств признаков (см. работы Кузнецова и Игнатова [6,3] и более позднюю статью другого исследователя [38]). Подробное описание постановки задачи, вычислительной модели см. в разделе 4.1.



Содержание раздела