Software & Systems

Объем массивов текстовых документов в научной сфере, бизнесе и других областях человеческой деятельности неуклонно растет. Этим обусловливается растущий интерес к методам автоматической текстовой кластеризации. В ряде методов кластеризации текстовых документов используются древовидные структуры, при этом часто применяется подход BoW, в котором текст рассматривается как неупорядоченный набор начальных форм слов, входящих в него (Bag of Words).

Ни один из существующих основных методов автоматической кластеризации текстов не обладает набором свойств, необходимых для быстрого и эффективного решения кластеризационных задач, в частности, иерархической кластеризации новостей [2].

Одним из перспективных направлений повышения эффективности работы алгоритмов, использующих древовидные структуры для кластеризации текстов, является расширение пространства правил, находящихся в узлах деревьев.

Помимо унитарных правил, отвечающих наличию в тексте одного определенного терма, при формировании таких древовидных структур возможно учитывать агрегированные правила, построенные на основе статистических и семантических характеристик всей совокупности выделяемых из текстовых документов термов. Предложим один из таких методов, названный островной кластеризацией. Алгоритм основан на использовании статистической меры корреляции встречаемости в текстах термов, характеризующихся значимым превышением их частот над средним уровнем.

Начальная часть алгоритма состоит в построении так называемого графа корреляций термов. Этот граф задается матрицей парных корреляций булевых переменных aip, отражающих наличие терма i в документе p, так что связь между термами i и j считается существующей при достаточно сильной (больше пороговой) корреляции между переменными ai и ap. Степень корреляции между термами i и j определяется следующим образом. Пусть n – общее количество термов во всех документах; ni – количество термов в документах, в которых встречается терм i. Обозначим общее число термов j во всех текстах как Nj, а количество термов j в документах, содержащих терм i, как Nij. Если принять гипотезу, что термы i и j распределены в документах независимо друг от друга, то вероятность того, что в документах, содержащих терм i, окажется Nij или более термов j – это вероятность получения не менее Nij успехов в серии из Nj испытаний при вероятности успеха одного испытания, равной ni /n, то есть , где , b – функция биномиального распределения.

Вероятность может быть принята в качестве основы для расчета меры корреляции между термами i и j: чем она меньше, тем более коррелированны эти термы. Однако величина pij все же не совсем подходит для описания силы связи термов i и j, в частности, потому, что она, как легко видеть, не симметрична: pij¹pji. Поэтому в качестве меры корреляции термов принимается величина , а в программной реализации алгоритма выбирается определенное пороговое значение вероятности, определяющей достоверность связи межу термами.

Рассматриваемый метод удовлетворяет основным свойствам, которыми должна обладать процедура кластерного анализа для того, чтобы быть практически применимой к кластеризации больших массивов текстов вообще и к анализу динамики тематической структуры потока новостей в частности:

· интерпретируемость найденных кластеров в терминах смысла содержания относящихся к ним документов;

· статистическая значимость группирования текстов в кластеры;

· возможность отнесения документа более чем к одному кластеру;

· не более чем логлинейный рост времени работы кластеризатора с увеличением количества текстов;

· минимальная (а лучше вообще отсутствующая) настройка со стороны пользователя.

Рассматриваемый алгоритм может быть комбинирован с алгоритмом выделения из текстов содержащихся в них сущностей. Выделенные сущности используются для формирования решающих правил при построении деревьев решений. Задача выделения блоков структурированной информации (сущностей) из текстовых документов впервые была выделена как отдельная задача text mining в 1995 году [1]. За прошедшие с того времени годы было разработано несколько различных алгоритмов выделения сущностей. Работа любого такого алгоритма заключается в том, что на вход подается текст, написанный на естественном языке, а на выходе формируется информация, соответствующая заранее определенным паттернам, в структурированном виде.

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

гов (признаков) сущностей является их тип, что дает возможность исследовать влияние на результаты кластеризации включения в набор правил сущностей различных типов.

Помимо регулярных выражений, для выделения сущностей в алгоритме используются тезаурус WordNet и набор словарей.

Одна из важнейших областей применения метода автоматической кластеризации текстов с помощью выделения стандартных сущностей и учета совместной встречаемости в документах ключевых терминов – анализ динамики тематической структуры потока новостей.

Применение метода островной кластеризации к публично доступному массиву новостей Reuters-21578 на примере трех типов задач – плоская кластеризация, иерархическая кластеризация и прослеживание динамики тематической структуры – показало, что метод островной кластеризации может успешно решать эти типы задач, давая в каждом случае описание полученных результатов в понятных человеку терминах и позволяя как автоматически выявить тонкую тематическую структуру массива новостей и других документов, так и проследить ее развитие во времени [2].

В настоящее время получены первые результаты тестирования алгоритма на различных массивах информации, показывающие его эффективность в случае наличия достаточно большой встречаемости сущностей в текстовой коллекции. Выделение части простейших типов сущностей возможно и на этапе выбора совместно встречающихся терминов и построения графа связей термов: множества выделяемых сущностей и определяемых на основе высокой частоты совместной встречаемости словосочетаний пересекаются. Есть все основания ожидать, что использование сущностей, выделенных именно на базе словарей (в частности, географических названий), внесет весомый вклад в результат кластеризации.

При программной реализации алгоритма были использованы средства пакета для анализа данных PolyAnalyst [3].

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

1. van Zaanen, M., Molla, D. A Named Entity Recogniser for Question Answering, Proceedings PACLING 2007, 2007.

2. Киселев М.В., Пивоваров В.С., Шмулевич М.М. Метод кластеризации текстов, учитывающий совместную встречаемость ключевых терминов, и его применение к анализу тематической структуры новостного потока, а также ее динамики. // Междунар. сб. науч. раб.: Интернет-математика 2005: автоматическая обработка веб-данных. – М.: Яндекс, 2005.

3. PolyAnalyst data/text mining system. User manual. (http://www.megaputer.com)