Journal influence
Bookmark
Next issue
Abstract:
Аннотация:
Authors: () - , () - , () - | |
Keywords: automatic clustering, , text document, the method |
|
Page views: 17169 |
Print version Full issue in PDF (1.83Mb) |
Объем массивов текстовых документов в научной сфере, бизнесе и других областях человеческой деятельности неуклонно растет. Этим обусловливается растущий интерес к методам автоматической текстовой кластеризации. В ряде методов кластеризации текстовых документов используются древовидные структуры, при этом часто применяется подход 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) |
Permanent link: http://swsys.ru/index.php?page=article&id=741&lang=en |
Print version Full issue in PDF (1.83Mb) |
The article was published in issue no. № 2, 2008 |
Perhaps, you might be interested in the following articles of similar topics:
- О задаче ретроконверсии неформатных документов в системах формирования и предоставления цифрового контента
- Программная система реструктуризации группы предприятий электроэнергетики
- Методы и инструментальные средства разработки веб-ориентированных интегрированных экспертных систем
- Обобщенный метод иерархического подкрепленного обучения для интеллектуальных систем поддержки принятия решений
- Основы моделирования системы поддержки принятия решений по комплексному применению сил и средств ПВО надводных кораблей
Back to the list of articles