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

Начиная с 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. Разработана методика определения целесообразности применения разработанного алгоритма в зависимости от лексического состава и общих характеристик текстовой коллекции, подлежащей кластеризации.