автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Метод автоматической кластеризации текстов, основанный на извлечении из текстов имен объектов и последующем построении графов совместной встречаемости ключевых терминов

Учреждение Российской академии наук ИНСТИТУТ ПРОГРАММНЫХ СИСТЕМ РАН

На правах рукописи

Шмулевич Марк Михайлович

МЕТОД АВТОМАТИЧЕСКОЙ КЛАСТЕРИЗАЦИИ ТЕКСТОВ, ОСНОВАННЫЙ НА ИЗВЛЕЧЕНИИ ИЗ ТЕКСТОВ ИМЕН ОБЪЕКТОВ И ПОСЛЕДУЮЩЕМ ПОСТРОЕНИИ ГРАФОВ'СОВМЕСТНОЙ ВСТРЕЧАЕМОСТИ

КЛЮЧЕВЫХ ТЕРМИНОВ

05.13.17 — Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

003456155

Москва —2008

003456155

Работа выполнена на кафедре Интеллектуальные системы Московского Физико-Технического Института (на базе Учреждения Российской академии наук Вычислительного центра им. A.A. Дородницына РАН)

Научные руководители:

доктор технических наук, профессор А.И. Эрлих

кандидат технических наук М.В. Киселев

Официальные оппоненты:

доктор технических наук, профессор В.Н. Вагин

кандидат технических наук Е.П. Куршев

Ведущая организация:

Учреждение Российской академии наук Институт Системного Анализа РАН

Защита диссертации состоится « [ 3 » _декабря_ 2008 года в /часов н-

заседании диссертационного совета ДМ 002.084.01 при ИПС РАН по адресу: 152020 Ярославская область, Переславский район, с. Веськово, ул. Петра Первого, д. 4а.

С диссертацией можно ознакомиться в библиотеке ИПС РАН. Автореферат разослан « »_ноября_2008 года

Ученый секретарь диссертационного совета ДМ 002.084.01,

кандидат технических наук Пономарева С.М.

Общая характеристика работы

Актуальность темы

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

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

2005]. Эти методы не превосходят по сложности > где N - количество

документов в коллекции, и дают интерпретируемые человеком устойчивые результаты.

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

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

Цель работы

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

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

Основные методы исследования

В ходе проведения диссертационного исследования использовались следующие

Ры

области научного знания и относящиеся к ним методы:

- математическая статистика;

- теория сложности вычислений;

- методы извлечения сущностей (Named Entities Extraction/Recognition);

- теория алгоритмов.

Разработка метода и построение алгоритма были проведены на основ теоретических положений. Эффективность созданного алгоритма доказывается помимо математического обоснования, способом экспериментальной проверки использованием разработанной программной реализации.

Научная новизна

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

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

Все основные результаты исследования являются новыми.

Практическая значимость работы

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

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

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

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

Реализация и внедрение результатов работы

Описанный алгоритм реализован и внедрен в технологический процесс сбора и аналитической обработки новостной информации из зарубежных источников в Многофункциональном навигационно-информационном центре Федерального государственного унитарного предприятия «Российский научно-исследовательский институт космического приборостроения» (головного предприятия Федерального космического агентства).

Результаты данной работы активно используются в деятельности российских архивов при обработке архивных документов в ходе работ по совершенствованию

системы научно-справочного аппарата. Работы проводятся специалистами и сотрудниками факультета технотронных архивов и документов (ФТАД) Историко-архивного института Российского государственного гуманитарного университета.

В Международном фонде технологий и инвестиций предложенный автором метод используется для выявления публикаций о перспективных инновационных технологических проектах.

Подразделения Департамента стратегического анализа и бюджетирования Министерства экономического развития России применяют описанный метод при анализе текстовой документации.

Разработанный алгоритм был успешно протестирован в составе программного продукта для анализа данных (Data Mining) Megaputer Polyanalyst. Планируется включение программной реализации алгоритма в следующие версии системы.

Апробация работы

- Основные результаты обсуждались на следующих конференциях и семинарах:

о Международная конференция «Высокие технологии XXI века»

(Москва, 2006); о 50-я научная конференция МФТИ (Москва, 2007); о Международная конференция «Математические методы

распознавания образов» (Санкт-Петербург, 2007); о Научные семинары МФТИ, ВЦ РАН.

- В 2007 году автором был проведен цикл семинаров по методам текстового анализа (Text Mining) на факультете Вычислительной математики и кибернетики МГУ им. Ломоносова с участием специалистов в данной области, в ходе которых были рассмотрены основные результаты диссертации.

- Результаты исследования обсуждались в ходе работы Российской летней школы по информационному поиску в Екатеринбурге в 2007 г.

- На всем протяжении работы над диссертационным исследованием его состояние и результаты обсуждались с научными сотрудниками компании «Мегапьютер Интеллидженс», ведущей исследования и разработки в области анализа данных и кластеризации текстов в частности.

Публикации

По теме диссертационной работы опубликовано 5 научных статей, из них 1 - в издании ВАК. Список статей приведен в конце данного автореферата.

Все основные результаты диссертационного исследования, описанные в приведенных публикациях, получены автором самостоятельно.

Структура и объем работы

Диссертационная работа состоит из введения, трех глав, заключения и приложения, включающего список литературы. Нумерация глав диссертации — сквозная иерархическая (основные разделы находятся в главах 1-3). Объем диссертации — 140 страниц, список литературы содержит 26 наименований. Работа включает 8 таблиц и 12 рисунков.

Краткое содержание диссертации

Введение

Во введении рассматривается постановка задачи автоматической кластеризации текстов; приводится история основных научных работ в этой области; описываются цели исследования; приводится краткий обзор содержания диссертации.

Вначале описывается задача кластеризации текстов в том виде, в котором она

и = {Т ... Т\

рассматривается в данном исследовании: дано множество текстов р ' "

т

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

максимально схожими по тематике, а тексты в разных подмножествах отличны по тематике. Число т выбирается автоматически.

Такие подмножества далее называются тематическими кластерами, или просто кластерами.

В данном исследовании рассматриваются тексты на английском языке.

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

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

После постановки задачи приводится описание основных требований к кластеризационной процедуре и их отличия от требований к процедуре классификации (категоризации) текстов.

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

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

- результат кластеризации должен быть устойчив к увеличению количества текстов в коллекции.

Кроме того, алгоритм кластеризации текстов должен быть масштабируем:

0( АПояЛО N

сложность алгоритма не должна превосходить 4 ° ' , где 1У — количество документов в коллекции.

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

т

подмножеств

У]фк,\< ] <к<п

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

Далее приводится краткая история работ в предметной области. Затем рассматриваются основные методы, используемые для автоматической кластеризации текстов: Single/Complete/Average Link, Scatter/Gather, алгоритм IC-средних, алгоритм Suffix Tree Clustering, островная кластеризация. Каждый метод рассматривается на предмет применимости для решения поставленной задачи.

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

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

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

Глава 1. Метод автоматической кластеризации текстов, основанный на извлечении из текстов имен объектов и последующем построении графов совместной встречаемости ключевых терминов

В данной главе описывается новый метод автоматической кластеризации текстов и обосновываются утверждения, лежащие в основе всех этапов работы метода. Описание алгоритма, реализующего этот метод, приводится в Главе 2.

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

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

даты - 06/05/2004 или 3 January 2003;

имена людей - John Doe, Mr. Geraldo de Gonzalez de Riviera;.

названия организаций - Red Cross, IBM;

адреса - Woodland park drive 22 - 3, 1234 Boston MA, USA;

географические названия - the Russian Federation, USA, New England.

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

Пусть Е. множество сущностей, выделенных из коллекции текстов ^.

Дополним множество Е множеством значимых терминов коллекции ^, выбираемых по следующему признаку: разница частоты их встречаемости в

коллекции ^ со средней частотой их встречаемости в большом массиве английских текстов превышает заданный порог. При этом терминами здесь являются как слова, так и словосочетания и даже синонимические ряды, которые можно распознать, используя тезаурус \VordNet, являющийся де-факто стандартом среди тезаурусов английского языка. Базовой структурной единицей \VordNet является синонимический ряд (синсет), объединяющий слова или словосочетания со схожим значением. Предполагается, что каждый синсет репрезентирует в словаре некоторое понятие языка. Синсеты в \VordNet связаны между собой такими семантическими отношениями, как гипонимия, отношения вида часть-целое и др.

Объединение множеств К1 п Е даех множество ключевых терминов

К = К1 и Е коллекции ^ .

Затем на полученном множестве К строится (возможно, несвязный) граф совместной встречаемости терминов: в каждую связную компоненту этого графа попадают те и только те ключевые термины, совместная встречаемость которых в

текстах коллекции ^ статистически значима.

Граф совместной встречаемости ключевых терминов задается матрицей парных

а

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

(больше пороговой) корреляции между переменными и р. Степень корреляции между термами 1 и j определяется следующим образом. Пусть п - общее количество

п.

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

• ^ . • N.

встречается терм 1. Обозначим общее число термов ] во всех текстах как , а

количество термов J в документах, содержащих терм 1 - как 1. Если принять гипотезу, что термы \ и j распределены в документах независимо друг от друга, то

N..

вероятность того, что в документах, содержащих терм ¡, окажется или более термов J — это вероятность получения не менее 4 успехов в серии из 1

У

«лытании при вероятности успеха одного испытания, равной ' п , т.е.

п , где /=и , b — биномиальное

аспределение.

p^P^N^NjA)

Вероятность п может быть принята в качестве основы для

асчета меры корреляции между термами inj- чем она меньше, тем более

оррелированы эти термы. Однако величина ^ все же не совсем подходит для писания силы связи термов i и j, в частности, и потому что она, как легко видеть, не

P'J Ф Pß

имметрична:

Ра = max(P,rPj,)

Лемма: сила связи термов I и ] 4 '' р является степенью

орреляции термов i и j в случае ^ ^''.

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

р..

Следует отметить, что процесс вычисления матрицы { 1]} не является - ычислительно сложным, что утверждает следующая лемма.

р.. т

Лемма: время работы алгоритма вычисления матрицы { и } 1 линейно зависит от количества документов в коллекции

Кроме того, возможна оптимизация скорости вычисления этой матрицы путем

"Д/

N.. <

р.. и

пропуска вычисления значений 4 для пар термов с п (для них

полагается равной нулю).

На основе графа совместной встречаемости терминов строятся кластеры совместно встречающихся терминов (см. Главу 2).

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

Далее проводится итоговая кластеризация текстов.

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

текстам коллекции ^. Для построения дерева решений используется алгоритм

Information Gain и критерий следующего вида: текст 7 относится к кластеру ' соответствующему кластеру ключевых терминов , если он содержит в себе хот

С

бы одну пару ключевых терминов из кластера ', соединенных ребром в граф совместной встречающихся терминов.

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

Приведенный новый метод удовлетворяет всем основным требованиям эффективной кластеризационной процедуре.

В то же время, этот метод применим в случае наличия в текстах сложных термов Так как большинство сложных термов выделяются на этапе извлечения сущностей то они входят неделимыми единицами во множество ключевых терминов коллекции Это позволяет не рассматривать такие термы как отдельные составляющие их слов (каждое из этих слов может быть, во-первых, малочастотно и в коллекции текстов, \ в языке вообще, и не войти в список терминов, которыми описывается текст, а во вторых, если в текстах встречаются George Harrison и George Bush, то связи слов George в музыкальном и в политическом смыслах будут перемешаны, что н позволит произвести тематическую кластеризацию).

Глава 2. Описание алгоритма, реализующего метод автоматическо" кластеризации текстов

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

Шаг 1. Предобработка текстов, включающая в себя:

- морфологический анализ и нормализацию текстов;

- удаление стоп-слов;

- выделение устойчивых словосочетаний и синсетов WordNet.

Шаг 2. Выделение из текстов множества сущностей Е. Для этого используютс регулярные выражения, направленные на извлечение имен и географических названий, а также соответствующие словари.

Пример выделения имени человека:

RegExp (Name) =

= [VU (\s)* vu (\S)* \U (\L)+] U [ \U (\L)+ (\S)+ \U 7 (\S)* \U 7] U [\U (\L)+ +(\S)+\U7(\S)*\U(\L)+]

Данное выражение приведено в стандартном синтаксисе и позволяет выделить такие имена, как Alexander V. Ivanov, J.N. Smith, Reem F.

Шаг 3. Выделение их текстов множества Kl значимых термов. Характерным для данного массива текстов считаются те из найденных терминов, которые имею наиболее статистически значимое превышение частоты их встречаемости в этом массиве над фоновой частотой. Количественным порогом выбора характерных терминов может быть либо напрямую заданное максимальное число терминов, либо

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

Шаг 4. Построение объединенного множества ^ ~ 01 Е; являющегося инальным множеством термов для кластеризации.

Шаг 5. Построение графа связей терминов.

Шаг 6. Построение кластеров совместно встречающихся терминов.

Входными данными для процедуры кластеризации термов являются тройки

<Uj,Pij> р(1(

J , упорядоченные по возрастанию ' (т.е. в начале идут самые сильные вязи). Каждый шаг алгоритма будет соответствовать очередной связи из этого абора связей. Алгоритм имеет один параметр Ts - минимальный размер кластера окументов, при котором он перестает расти. Каждый кластер термов задается ножеством его термов и множеством связей между ними.

Определения:

G - множество растущих кластеров термов;

F — множество зафиксированных кластеров термов-,

Left - разница между множеством всех термов в графе связей терминов и ножеством G ^ F;

PRO - множество термов, из которых состоят кластеры множества F (изначально ножества F, G и PRO пустые).

Doc С - множество документов, принадлежащих кластеру термов С.

Документ считается принадлежащим кластеру термов С, если он содержит ару термов, соответствующих хотя бы одной связи кластера термов С.

Операция фиксации кластера термов С из множества G:

1. С удаляется из множества G;

2. С добавляется ко множеству F;

3. Все термы С добавляются ко множеству PRO.

Каждая итерация алгоритма состоит в рассмотрении очередной связи

>J'P* из списка связей с убывающей силой, пока все связи не будут счерпаны, после чего алгоритм останавливается. Во время каждой итерации горитма выполняется следующая процедура:

С iе PRO 7 е PRO

- Если 1 е * и J , переити к следующей связи.

- Если * е PRO,

о если существует кластер термов С, содержащий терм j, С фиксируется;

PRO <— PRO и {у }.

о иначе перейти к следующей связи.

„ jePRO

Если J ,

о если существует кластер термов С, содержащий терм i, С фиксируется;

PRO <- PRO u {/}

о иначе 1> ;

перейти к следующей связи. Если ни i, ни j не принадлежат ни одному кластеру термов, добавить к множеству G кластер, состоящий из термов i и j и связи между ними;

перейти к следующей связи. Если i и j принадлежат одному кластеру термов, добавить к этому кластеру связь между термами i и j;

перейти к следующей связи. Если i и j принадлежат двум разным кластерам термов С и D,

о если |doc С| > Ts или |doc D| > Ts, С фиксируется, D фиксируется; о иначе удалить С и D из G и добавить к G кластер термов,

являющийся объединением С и D и связи между термами i и j; перейти к следующей связи. Если i принадлежит некоторому кластеру термов, a j не принадлежит ни одному кластеру термов, добавить к этому кластеру термов связь между термами i и j и терм j;

перейти к следующей связи. Если j принадлежит некоторому кластеру термов, a i не принадлежит ни одному кластеру термов, добавить к этому кластеру термов связь между термами i и j и терм i;

перейти к следующей связи.

Пример результата (Mr. Albert Einstein - сущность):

school

teacher

student

comment

synopsis

alien

crew

Mr. Albert Einstein

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

Глава 3. Программная реализация и экспериментальная проверка [горитма

Были проведены исследования для подтверждения работоспособности остроенного алгоритма и его сравнения с существующими алгоритмами. В данной лаве приводятся результаты экспериментальных исследований применения азработанного метода кластеризации текстов. Для проведения экспериментов была остроена и реализована программная модель алгоритма на базе программного родукта для анализа данных PolyAnalyst 5.0.

Для тестирования алгоритма использовались две текстовых коллекции: оллекция G, состоящая из текстов про Джорджа Буша и про Джорджа Харрисона на англ. языке), и коллекция N, состоящая из текстов про штаты Северная Дакота и еверная Каролина соответственно (на англ. языке). В обеих коллекциях было оровну текстов по каждой из двух тематик.

Приведем основные характеристики этих коллекций:

G N

Количество текстов в 144 348

коллекции

Средний размер текста 5.6 Kb 2.2 Kb

Вследствие простоты коллекций (заранее известно количество кластеров, эти астеры равного размеры) применение стандартной меры качества кластеризации, снованной на энтропии, является неэффективным. Для оценки качества астеризации использовалась простая, но эффективная в данном случае мера Fe, вляющаяся F-мерой [15]:

1с,|

Fe =

С

ÇJ

где

1 - множество документов, отнесенных алгоритмом к первому кластеру,

С

1е - исходное множество документов в первом кластере. Для сравнения были проанализированы результаты работы трех других горитмов на тех же коллекциях: алгоритма островной кластеризации, алгоритма К-редних и алгоритма Average Link.

Полученные результаты (значения Fe-мгры):

G N

Островная кластеризация + 0.89 0.91

сущности

Островная кластеризация 0.81 0.8

К-средние 0.71 0.78

Average Link 0.78 0.69

Таким образом, разработанный алгоритм продемонстрировал лучшие результать в смысле Fe-меры на обеих текстовых коллекциях в сравнении с другим рассмотренными алгоритмами.

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

Заключение

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

Основные результаты

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

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

3. Доказано, что построенный алгоритм масштабируем, т.е. имеет мест линейный рост времени его работы с увеличением количества документов.

4. Построена программная реализация разработанного алгоритма на основ программного продукта Megaputer Polyanalyst.

5. Выполнена экспериментальная проверка эффективности работы данного алгоритма на реальных текстах.

6. Разработана методика определения целесообразности применения разработанного алгоритма в зависимости от лексического состава и общих характеристик текстовой коллекции, подлежащей кластеризации.

Список работ автора по теме диссертации

1. М.М. Шмулевич, «Классификация текстов с помощью деревьев решений, построенных на основе кластеров совместно встречающихся терминов», Современные проблемы фундаментальных и прикладных наук, часть VII, Москва-Долгопрудный, 2004, стр. 69-70.

2. Шмулевич М.М., Киселев М.В., Пивоваров B.C., «Метод кластеризации текстов, учитывающий совместную встречаемость ключевых терминов, и его применение к анализу тематической структуры новостного потока, а также ее динамики», Интернет-математика 2005, изд-во Яндекс, Москва, 2005, стр. 412-435.

3. Шмулевич М.М., «Метод кластеризации текстов, учитывающий совместную встречаемость ключевых терминов, и его применение к анализу тематического состава потока новостей», Труды 50-й научной конференции МФТИ, Москва-Долгопрудный, 2007, стр. 123 - 125.

4. Шмулевич М.М., Киселев М.В., «Метод кластеризации текстов, учитывающий совместную встречаемость ключевых терминов, и его применение к анализу тематического состава потока новостей», Математические методы распознавания образов, Москва, 2007, стр. 562 -564.

5. Киселев М.В., Шмулевич М.М., Эрлих А.И., «Метод автоматической кластеризации текстов и его применение», Программные продукты и системы №2 2008, Москва, 2008, стр. 47-50.

Личный вклад. Все результаты исследований, составляющие основное одержание диссертации, получены автором самостоятельно. В работе [2], ыполненной в соавторстве, автор выполнил разработку кластеризационной части горитма, ее тестирование на массиве новостных сообщений и создание писательной части работы. В работе [4], выполненной в соавторстве, автор ыполнил настройку и экспериментальную проверку работы алгоритма для тслеживания динамики тематической структуры новостного потока. В работе [5], ыполненной в соавторстве, автор разработал и сформулировал алгоритм астеризации с использованием сущностей.