Метод автоматической кластеризации текстов, основанный на извлечении из текстов имен объектов и последующем построении графов совместной встречаемости ключевых термов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат физико-математических наук Шмулевич, Марк Михайлович

• Шмулевич, Марк Михайлович
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Шмулевич, Марк Михайлович

Введение.

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

Список литературы диссертационного исследования кандидат физико-математических наук Шмулевич, Марк Михайлович, 2009 год

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.