ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Публикационная активность

(сведения по итогам 2017 г.)
2-летний импакт-фактор РИНЦ: 0,500
2-летний импакт-фактор РИНЦ без самоцитирования: 0,405
Двухлетний импакт-фактор РИНЦ с учетом цитирования из всех
источников: 0,817
5-летний импакт-фактор РИНЦ: 0,319
5-летний импакт-фактор РИНЦ без самоцитирования: 0,264
Суммарное число цитирований журнала в РИНЦ: 6012
Пятилетний индекс Херфиндаля по цитирующим журналам: 404
Индекс Херфиндаля по организациям авторов: 338
Десятилетний индекс Хирша: 17
Место в общем рейтинге SCIENCE INDEX за 2017 год: 527
Место в рейтинге SCIENCE INDEX за 2017 год по тематике "Автоматика. Вычислительная техника": 16

Больше данных по публикационной активности нашего журнале за 2008-2017 гг. на сайте РИНЦ

Вход


Забыли пароль? / Регистрация

Добавить в закладки

Следующий номер на сайте

4
Ожидается:
16 Декабря 2018

Метод автоматической кластеризации текстов и его применение

Статья опубликована в выпуске журнала № 2 за 2008 год.[ 24.06.2008 ]
Аннотация:
Abstract:
Авторы: Киселев М.В. () - , , , Эрлих А.И. () - , , , Шмулевич М.М. () - , ,
Ключевые слова: автоматическая кластеризация, использование, текстовые документы, метод
Keywords: automatic clustering, , text document, the method
Количество просмотров: 10911
Версия для печати
Выпуск в формате PDF (1.83Мб)

Размер шрифта:       Шрифт:

Объем массивов текстовых документов в научной сфере, бизнесе и других областях человеческой деятельности неуклонно растет. Этим обусловливается растущий интерес к методам автоматической текстовой кластеризации. В ряде методов кластеризации текстовых документов используются древовидные структуры, при этом часто применяется подход 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)


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=741
Версия для печати
Выпуск в формате PDF (1.83Мб)
Статья опубликована в выпуске журнала № 2 за 2008 год.

Возможно, Вас заинтересуют следующие статьи схожих тематик: