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

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

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

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

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

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

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

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

0034Б4^ г ¿5

Москва 2009

003464273

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

Научный руководитель: Официальные оппоненты:

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

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

A.И. Эрлих

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

B.Н. Вагин

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

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

Защита диссертации состоится «_19_» _марта_ 2009 года в_часов на заседании

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

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

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

кандидат технических наук

Пономарева С.М.

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

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

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

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

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

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

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

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

Цель работы

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

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

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

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

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

• методы оптимизации;

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

• методы извлечения сущностей, т.е. блоков структурированной информации в тексте, отвечающих определенным шаблонам и идентифицирующих объекты или свойства (Named Entities Extraction/Recognition).

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

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

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

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

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

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

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

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

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

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

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

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

венного унитарного предприятия «Российский научно-исследовательский институт космического приборостроения» (головного предприятия Федерального космического агентства).

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

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

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

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

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

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

о 50-я научная конференция МФТИ (Москва, 2007);

о Международная конференция «Математические методы распознавания образов» (Санкт-Петербург, 2007);

о Научные семинары МФТИ, ВЦ РАН.

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

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

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

Публикации

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

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

Диссертационная работа состоит из введения, трех глав, заключения, списка литературы и приложения, включающего описание проведенных экспериментов и их результатов, а также справки о внедрении результатов исследования. Нумерация глав диссертации — сквозная иерархическая (основные разделы находятся в главах 1-3). Объем диссертации — 120 страниц, список литературы содержит 31 наименование. Работа включает 11 таблиц и 23 рисунка.

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

Введение

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

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

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

• ручная кластеризация применима только для относительно небольших коллекций документов;

• ручные методы требуют длительного времени для работы, так как эксперту необходимо время на принятие решения по каждому тексту.

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

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

Глава 1. Автоматическая кластеризации текстовых коллекций

В этой главе:

• осуществлена общая постановка задачи кластеризации коллекций текстовых документов;

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

• проведен анализ предметной области:

• определены методы кластеризации коллекций текстов, наиболее полно соответствующие сформированным требованиям эффективности;

• поставлена задача этого исследования;

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

Вначале в разделе I.1. описывается задача кластеризации текстовых коллекций в том виде, в котором она рассматривается в этой работе.

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

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

Примечание: пусть также задана метрика близости ц(*,дг') между текстами х.х'еХ. Тогда задача может быть уточнена: требуется разбить X на подмножества**,= %> называемые кластерами, так, чтобы количество различных троек

I

текстов х,х'.х"еХ, таких, что хеХ\;х\х* е Х„1 * к, а дс') <, было как можно меньше. При этом каждому тексту в процессе кластеризации приписывается номер содержащего его кластера.

Определение. Алгоритм кластеризации - это отображение /. X ->{ЛГ,}, которое любому тексту хеХ ставит в соответствие метку кластера X' е (Х:}.

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

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

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

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

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

• время работы алгоритма кластеризации желательно не более 0(п2), где п -количество документов в коллекции;

• наличие в алгоритме средств разрешения синонимии и омонимии.

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

Перед проведением анализа предметной области описывается модель УБМ представления текстов. В диссертационной работе рассматриваются только те методы кластеризации текстовых коллекций, которые опираются на представление документов в соответствии с моделью У5М.

В процессе анализа были:

• построены три классификации методов кластеризации текстовых коллекций по различным признакам (использованию нечисловых свойств текстов, эксклюзивности/иерархичности, направлению кластеризации);

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

• выявлены основные достоинства и недостатки рассмотренных методов;

• выбраны методы кластеризации текстов, наиболее полно соответствующие

требованиям, определяющим эффективность процедуры кластеризации. Были рассмотрены основные методы, используемые для автоматической кластеризации текстовых коллекций: Single/Complete/Average Link, Scatter/Gather, метод К-средних, Suffix Tree Clustering, группа методов островной кластеризации (см. рис. /).

Методы кластеризации текстов

Методы, использующие

только числовые характеристики текстов

Группа методов Single Unk/Complete Link/ Group Average

Группа методов K-means

Методы, использующие

в т.ч. нечисловые характеристики текстов

Метод STC

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

Метод LSA/LSI

Рис. 1. Методы кластеризации текстовых коллекций

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

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

• введения выделенных из текстов сущностей в состав ключевых термов текстовой коллекции;

• автоматического определения и учета весов термов (включая сущности) для уменьшения мощности множества термов.

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

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

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

Глава 2. Метод сущностной кластеризации

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

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

• даты - 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.

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

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

На начальном этапе работы метода проводится удаление стоп-слов и другие стандартные операции предварительного этапа обработки текстов.

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

Определение. Терм /, содержащийся в текстовой коллекции Q, называется значимым (характерным) на уровне ß, если разница частоты встречаемости терма I в коллекции Q и средней частоты его встречаемости в большом массиве английских текстов превышает/?.

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

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

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

Определение. Начальным множеством ключевых термов коллекции Q называется множество К' = Kl(J Е, где Kl - множество значимых термов коллекции Q.

Однако множество К' содержит все значимые термы и сущности коллекции Q. В Часто вследствие большой мощности это множество не может быть использовано для построения вычислительно эффективного алгоритма кластеризации.

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

Процесс определения весов описан далее в разделе 2.2. Используется представление текстов в стандартной модели VSM. В данном случае рассматривается евклидово пространство, в котором каждый текст представляется вектором частот всех рассматриваемых термов в этом тексте. Вектора нормируются на единицу.

Определение. Внутрикластерным отклонением вектора текста xj, принадлежащего кластеру /, от центроида этого кластера с, по компоненте к называется величина Dkt = — ~(х*. *с*), где п - мощность множества К', J - количество текстов в кол-с' п

лекции Q; {Xj},jе{1,...,./} - векторы текстов коллекции Q;{с,},/е{1,...,/} - множество известных центроидов (заданное или определенное на основе заданного результата кластеризации).

Относящимися к данному кластеру /е{1,...,/} считаются все тексты, к которым центроид данного кластера с, является ближайшим.

Предлагаемая идея нахождения весов для Xj заключается в следующем: рассматривается суммарное внутрикластерное отклонение й, = v*//, текста xf с определенными весами v*, и затем это отклонение минимизируется.

Однако непосредственная минимизация этой величины приводит к вырожденному решению: внутрикластерное отклонение достигает минимума при равенстве весов всех элементов множества К' нулю, за исключением одного, который равен единице.

Для получения невырожденного решения в методе сущностной кластеризации проводится минимизация суммы этой величины и суммы квадратов весов элементов множества К'.

Утверждение. Оптимальными вектором V весов элементов множества К' в мето-

де

сущностной

кластеризации

является

решение

F = arg^lvf)min

Ы X, 4=1 i=l 1=1

при

задачи

условиях

[0,1],У/б{1,.../}Де{1,...,и}и £v;=l,V/e{l,...,/}.

Теорема.

r = {vf} =

Решение

Л

42

п 2 Т1

1-1

поставленной

у

выше задачи достигается на векторе

-D\

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

Степень корреляции между термами / и ] определяется следующим образом: чем чаще эти термы встречаются в одних и тех же документах, тем более они коррелированны. Следующая теорема формализует этот подход.

Теорема. Пусть в коллекции 0. п- общее количество термов во всех документах, п,- количество термов в документах, в которых встречается терм /. Пусть общее число термов } ьо всех текстах - NJ,a. количество термов_/ в документах, содержа-

1 —

N/.

может служить мерой

щих терм / - N„. Тогда величина р., =

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

Лемма. Сила связи термов / и j p:j = max(pip рр) может служить мерой корреляции термов i и j в случае р. Ф pJt.

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

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

Затем проводится итоговая кластеризация текстов (раздел 2.4.).

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

• Критерий 1: пусть ТС = {Тегт[,...,ТегтТ} - кластер совместно встречающихся термов. Пусть Doc - текст. Тогда этот текст считается относящимся к кластеру ТС если и только если В/ е {1,..., Г}: Term, е Doc.

• Критерий 2: в условиях критерия 1 текст Doc считается относящимся к кластеру ТС если и только если 3i е {1 ,...,T},3j е {l,...,T},j ф i : Termt е Doc&Tertrij е Doc и связь между термами /' и у - существующая.

• Критерий 3: в условиях критерия ] текст Doc считается относящимся к кластеру ТС если и только если

3« е {I,..., Т}, 3j € {1,..., Г}, 3k е {I.....T},j*i,j*k,i*k: Term, е Doc &

&,Termj е Doc & Termt e Doc и связи между термами i, kuj- существующие.

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

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

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

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

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

Глава 3. Алгоритм сущностной кластеризации и его применения

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

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

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

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

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

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

Пример выделения имени: RegExp (Name) = [\U 7(\S)* \U '.' (\S)*\U (\L)+] ^ U [ \U(\L)+ (\S)+ '.' (\S)* \U '.'] ^ [\U (\L)+ +(\S)+ \U 7 (\S)* \U (\L)+]. Данное выражение приведено в стандартном синтаксисе и позволяет выделить такие имена, как Alexander V. Ivanov, J.N. Smith, Reem F.

Шаг 3. Выделение из текстов множества Kl значимых термов. Шаг 4. Построение объединенного множества К'= KI^jE, являющегося начальным множеством термов для кластеризации.

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

Иначе, если известен результат экспертной кластеризации, либо коллекция является обучающей выборкой для кластеризации массивов текстов определенного типа, либо известны предварительные центроиды получаемых кластеров, выполнить шага: Шаг 5.1. Обозначить {д; },j е {1,...,У} - нормированные на единицу векторы евклидова пространства, представляющие собой тексты коллекции; {ct},ie{l,...,/} -множество известных центроидов (заданное или определенное на основе заданного результата кластеризации).

Шаг 5.2. Для всех j е {!,..., J}, /' е {!,...,/} рассчитать величину

D\ = — -(** «с4), где п - мощность множества К', J - количество текстов в кол-п

лекции.

Шаг5.3. Обозначить v* =1 In,V/е{1,...,/},Vk.

Шаг 5.4. Рассчитать взвешенное внутрикластерное отклонение %, = ^ v'Dk, по

' t-l '

всем термам и по всем кластерам.

Шаг 5.5. Рассчитать новые значения v* = — + - У

п 2Т1

по всем термам и

по всем кластерам.

Шаг 5.6. Пересчитать центроиды кластеров. Если v* = 0, с* = 0. Если vf Ф 0,

рассчитать с, —.

Шаг 5.7. Если хотя бы один центроид кластера изменился, перейти на шаг 5.2. Шаг 5.8. Задать порогу. Включить в финальное множество ключевых термов К те и только те термы, веса которых отличаются от 1/п менее, чем на_у. Шаг 6. Построение графа связей термов.

Упорядочить термы и документы (последовательность термов и документов в соответствующих множествах выбирается произвольным образом): \к = {Term,, Тегтг,..., TerrnNurms} { Q = {Doci,Doc2,...,DocNlhcs]

Рассмотреть матрицу А =

иЮгт!,1

документов в коллекции, Nterms jl, Term, € Doc

- {%} >где Ndocs - количество

Nlerms,Ndocs j

количество термов в множестве К,

a<.r =

О,иначе

«Л

В обозначениях главы 2: если Ntj <,--, то положить ри = 0. Иначе: вычислить

п J

_ Л", / „

й] (l-ÜL п)\ п

Nt\

Р" {NrN,j)\

P,J при условии ру> рс =

и p,j = max(Pij, pJt ). Сформировать матрицу S из

0.03

-. В случае p,j - рс = •

0.03

выбирается рч = 0.

Шаг 7. Построение кластеров совместно встречающихся термов. Входными данными для процедуры кластеризации термов являются тройки < I, j, рц >, упорядоченные по возрастанию pv (вначале идут самые сильные связи).

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

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

sdœol teacher crew

comment

Mr. Albert Einstein

Рис. 2. Пример результата кластеризации термов

Шаг 8. Разбиение документов на кластеры в соответствии с результатом кластеризации на шаге 6. Документ О относится к кластеру документов, соответствующему кластеру термов К, если в £) содержится хотя бы одна пара термов из К, соединенных ребром в графе совместно встречающихся термов. Для определения кластеров, к которым будет относиться документ Д строится дерево решений.

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

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

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

Fi«!

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

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

G N

Сущностная кластеризация 0.92 0.94

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

К-средние 0.71 0.88

Average Link 0.78 0.69

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

Заключение

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

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

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

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

15

3. Построен алгоритм, реализующий метод сущностной кластеризации.

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

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

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

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

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

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], выполненной в соавторстве, автор разработал и сформулировал алгоритм кластеризации с использованием сущностей.

Отпечатано в ООО «Компания Спутник+» ПД № 1-00007 от 25.09.2000 г. Подписано в печать 13.02.09. Тираж 80 экз. Усл. п.л. 1 Печать авторефератов: 730-47-74,778-45-60

Введение.

Глава 1. Автоматическая кластеризация текстовых коллекций.

1.1. Общая постановка задачи кластеризации текстовых коллекций

1.2. Кластеризация текстовых коллекций и классификация текстов

1.3. Анализ предметной области.

1.4. Подход к кластеризации текстовых коллекций, содержащих сложные термы.

Глава 2. Метод сущностной кластеризации.

2.1. Выделение сущностей из текстов.

2.2. Формирование множества ключевых термов.

2.3. Построение графа совместной встречаемости термов.

2.4. Итоговая кластеризация текстовых коллекций.

Глава 3. Алгоритм сущностной кластеризации и его применения.

3.1. Описание алгоритма сущностной кластеризации.

3.2. Создание программной реализации алгоритма сущностной кластеризации.

3.3. Тестирование алгоритма сущностной кластеризации.

3.4. Применения метода сущностной кластеризации.

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

Согласно исследованию Калифорнийского университета (University of California - Berkley), в 2002 году в мире было произведено около 5 млн. терабайт информации. Для сравнения: объем информации библиотеки Конгресса США, где хранится 19 млн. книг и 56 млн. рукописей, - около 10 терабайт, т.е. в 500 тысяч раз меньше.

По данным исследовательской службы Cyveillance Inc., общее количество страниц в сети Интернет на 2001 год превысило 4 миллиарда и растет экспоненциально. Кроме того, существенный объем текстовой информации содержится в корпоративных базах данных и электронных библиотеках по всему миру.

Если в 2000 году (см. рис. 1) в мире отсылалось по 10 млрд, сообщений электронной почты в день, то в 2006 году - уже по 60 млрд. писем ежедневно [1].

Год

Рис. 1. Количество сообщений, ежедневно посылаемых по e-mail

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

Кроме того, без систематизации текстов невозможно решение и ряда других задач, в частности:

• реферирования больших документальных массивов;

• определения взаимосвязей между группами документов;

• упрощения визуализации текстовой информации;

• выявления дубликатов или близких по содержанию документов;

• контент-анализа и др.

Несмотря на это, в настоящее время только 10% всей хранящейся в мире текстовой информации приходится на структурированные массивы данных (в первую очередь - базы данных и базы знаний) [2]. Одновременно, согласно данным исследования Reuters, до 38% менеджеров тратят, по их мнению, слишком много времени на поиск и систематизацию нужной информации, а из всех журналистов, обращающихся к Интернету в поисках новостей, лишь 20% находят информацию, которая им необходима.

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

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

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

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

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

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

• ручная кластеризация применима только для относительно небольших коллекций документов;

• ручные методы требуют длительного времени для работы, так как эксперту необходимо время на принятие решения по каждому тексту.

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

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

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

• эксплуатационным службам производственных компаний необходимо проводить кластеризацию отчетов о нештатных ситуациях для организации более эффективного управления 1 производством, выявления опасных трендов, способных привести к повышению потенциальной аварийности;

• исследователям и ученым необходимо проводить мониторинг публикаций по тематике их работы для выявления новых идей и трендов;

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

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

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

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

История работ в предметной области ведет отсчет со второй половины XX века.

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

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

Табл. 1. Основные направления исследований в области кластеризации текстовой информации

Год Направление исследований

1958 Исследование статистических свойств языка

1961 Применение ассоциирования термов для кластеризации

1965-1968 Разработка модели векторного пространства

1975-1985 Разработка основных математических методов кластеризации текстов без учета семантики

1985 Разработка модели обобщенного векторного пространства

1990 Исследование метода латентного семантического индексирования

1998 Применение кластеризации термов, для кластеризации документов

2003 Улучшение методик выбора ключевых термов

2006 Применение метода поддерживающих векторов (SVM) для кластеризации текстов

Большое значение имели работы двух ученых из Корнельского Университета, G. Salton и A. Wang, которые дали существенный толчок к развитию методов автоматической кластеризации текстов. В 1975 году группа ученых из Корнельского университета опубликовала статью [3], предлагавшую описывать тексты в виде векторов в многомерном пространстве и, соответственно, использовать в работе с такими текстами-векторами стандартные меры близости в векторных пространствах.

Работа [3] послужила импульсом к развитию многочисленных исследований в области текстовой кластеризации, так как позволила уйти от семантических и лексических особенностей текстовой информации и рассматривать документы именно в качестве математических объектов. В числе прочего, была разработана одна из самых простых методик сопоставления векторов текстам, которая используется и сегодня, — модель векторного пространства (Vector Space Model, VSM). Описание VSM приведено в главе 1.

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

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

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

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

Научная новизна исследования заключается в том, что в нем предлагается и развивается новая идея выделения и последующего использования сущностей при кластеризации текстовых коллекций. В работе предложен метод автоматической кластеризации коллекций документов, использующий выделенные из текстовой коллекции сущности библиотека доступна онлайн по адресу http://citeseerx.ist.psu.edu вместе с содержащимися в текстах ключевыми термами для построения графа их совместной встречаемости.

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

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

• методы оптимизации;

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

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

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

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

Результаты этой диссертационной работы успешно используются в ряде организаций: построенный алгоритм реализован и внедрен в технологический процесс сбора и аналитической обработки новостной информации из зарубежных источников на головном предприятии Федерального космического агентства; разработанный метод кластеризации используется в деятельности российских архивов при обработке архивных документов (в т.ч. в Историко-архивного институте Российского государственного гуманитарного университета); подразделения Департамента стратегического анализа и бюджетирования Минэкономразвития России применяют этот метод при анализе текстовой документации.

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

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

Апробация работы была проведена в ходе нескольких международных и российских конференций, научных семинаров МФТИ и ВЦ РАН, а также в ходе работы Российской летней школы по информационному поиску в Екатеринбурге в 2007 г. (подробнее см. в Приложении).

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

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

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

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

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

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

31])

Заключение

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

Метод сущностной кластеризации представляет собой усовершенствованный метод островной кластеризации [15], существенно расширяющий его в части:

• введения выделенных из текстов сущностей в состав ключевых термов текстов;

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

В результате этого исследования получены следующие основные результаты:

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

2. Разработаны три классификации методов кластеризации текстовых коллекций по различным признакам.

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

4. Построен алгоритма, реализующий метод сущностной кластеризации.

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

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

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

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

1. How Much Information?", UC-Berkley, 2003,http://www2.sims.berkeley.edu/research/projects/how-much-info-2003/internet.htm

2. Д. Ландэ, «Добыча знаний», в журнале Chip1. Ukraine, #10, 2003

3. Joshua Zhexue Huang, Michael Ng, Liping Jing, "Introduction to Text Clustering", 2006 J. Quinlan, "C4.5: Programs for Machine Learning", Morgan Kaufman, 1993

4. A. Bharati, К. Varanasi, С. Kamisetti, R. Sangal, S.Bendre, "A Document Space Model for Automated Text Classification based on Frequency Distribution across Categories", HIT TechReport #06, 2002

5. Мисуно И.С., Рачковский Д.А., Слипченко C.B., Соколов A.M., «Поиск текстовой информации с помощью текстовых представлений», Проблеми програмування (4) 2005, стр. 50-59 van Rijsbergen C.J., "Information Retrieval", London, 1979

6. Computational Approaches", New York: Oxford University Press, 2000

7. Cutting D.R., Pedersen J.O., Karger D., and Tukey

8. J.W., "Scatter/gather: A cluster-based approach to browsing large document collections", In Proceedings of 15th Annual ACM-SIGIR, 1992, pp. 318-329

9. Beil F., "Frequent Term-based Text Clustering",

10. Proceedings of the eighth ACM SIGKDD, 2002

11. M. Губин, «Модели и методы представлениятекстового документа в системах информационного поиска», дисс. к.ф.-м.н., СПГУ, 2005

12. G. Miller, "WordNet: An Electronic Lexical Database", MIT Press, 1998, http://wordnet.princeton.edu/

13. Andreas Hotho, Steffen Staab, Gerd Stumme,

14. Wordnet improves text document clustering", proc. of the SIGIR 2003 Semantic Web Workshop, 2003

15. Айвазян C.A., Бежаева З.И., «Классификациямногомерных наблюдений» М.: Статистика, 1974.

16. Tao Liu, Shengping Liu, Zheng Chen, "An Evaluation on Feature Selection for Text Clustering", ICML, 2003

17. H. Frigui, O. Nasraoui, "Simultaneous categorizationof text documents and identification of cluster-dependent keywords", in Proceedings of FUZZIEEE,2003

18. Т. Mitchell, "Machine Learning", McGraw Hill, 1997

19. Polyanalyst User Manual, Megaputer Intelligence Inc., Moscow, 2002

20. Арсеньев С.Б., Бритков В.Б., Маленкова H.A., «Использование технологии анализа данных в интеллектуальных информационных системах», Москва, 2002

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

22. Ермаков А.Е., Плешко В.В., Митюнин В.А. Информатизация и информационнаябезопасность правоохранительных органов: XI Международная научная конференция. Сборник трудов Москва, 2003

23. Красильников П.В., «Воспроизведение лучших результатов ad hoc семинара РОМИП», IMAT 2007, Yandex, 2007

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