Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Введение

На сегодняшний день практические все научные статьи публикуются в электронном виде. Доступ к таким статьям предоставляется в сети Интернет как самими авторами, так и электронными библиотеками. Пожалуй, из самых крупных электронных библиотек стоит выделить такие, как IEEE Xplore, ACM Digital Library и Springer - вместе они предоставляют доступ более чем к 10 миллионам различных научных статей и книг. Анализ всего этого разнообразия статей сейчас является актуальной задачей: анализ может использоваться, например, в целях оптимизации поиска релевантной информации, а также для образования базы фактов (знаний). Безусловно, одному человеку практически невозможно уследить за всеми новыми методами, инструментами и знаниями, которые скрывают в себе миллионы статей и книг. В связи с этим, автоматизированный анализ естественного языка сегодня является важной проблемой.

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

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

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

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

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

Что касается самих методов бикластерного анализа, помимо метода, предложенного Диллоном, мы рассматриваем также другой подход к задаче бикластеризации, представленный Миркиным и Крамаренко. Если метод Диллона разбивает множества слов и текстов на непересекающиеся подмножества, то на алгоритм Миркина и Крамаренко (“BBox”) такое ограничение не накладывается. Это позволяет рассматривать одни и те же словосочетания в различных «контекстах» (бикластерах), что может быть важно при построении таксономии или графов зависимостей.

Цель работы.

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

1. Загрузка коллекции научных статей из электронной библиотеки (IEEE, Springer);

2. Получение набора ключевых слов и словосочетаний из приобретённой коллекции статей;

3. Построение векторов релевантности для каждой ключевого фразы (i-ый элемент вектора определяет релевантность ключевой фразы к i-ой статье в коллекции);

4. Вычисление матрицы схожести между ключевыми фразами на основе их векторов релевантности;

5. Бикластерный анализ матрицы релевантности фраза/текст;

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

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

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

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

1. Использование кластеризации для анализа текстовых данных: Обзор

1.1 Кластерный анализ текстовых данных

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

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

Кластерный анализ документов чаще всего основывается на модели «мешка слов», в котором тексты рассматриваются как векторы принадлежности или векторы релевантности слов. При этом количество различных слов в документах может быть очень большим - десятки тысяч, а значит полная матрица релевантности слово/документ может содержать десятки или даже сотни миллионов элементов. Работа с матрицами такого размера является сложной вычислительной задачей, поэтому исследователи часто прибегают к методам извлечения ключевых слов или фильтруют слова на основе частоты их встречаемости в документах. Идея фильтрации заключается в том, чтобы исключить из рассмотрения слова, которые встречаются в слишком большом или, наоборот, слишком малом количестве текстов. Слова, встречающиеся в большом количестве текстов можно считать стоп-словами, так как туда обычно попадают такие слова, как “a”, “the”, “this” и так далее. В то же время, слова, которое встречаются в небольшом количестве документов можно считать шумом.

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

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

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

1.2 Использование бикластеров в анализе текстовых данных

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

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

Пожалуй, первым, кто предложил использовать такую симметричность для параллельной кластеризации текстов и слов был Диллон в 2001 году. Бикластерный анализ (в английской литературе принято также называть анализ такого рода ко-кластеризацией - co-clustering) документов в том виде, в котором он был предложен Диллоном, позволял одновременно находить связанные кластеры слов и документов. Такой подход помогает посмотреть на структуру коллекции текстов сразу на двух уровнях: наборы документов и наиболее характерные для них слова. Сам алгоритм использует модель «мешка слов» для представления текстов, то есть объектом бикластеризации является матрица релевантности, а именно двудольный граф связей между словами и текстами, построенный на основе матрицы релевантности.

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

В дальнейшем были предложены новые алгоритмы бикластеризации текстов совместно со словами, которые основываются на других моделях представления текстовых данных. Так, в 2006 году был представлен алгоритм бикластеризации текстов, основанный на представлении текстов в виде случайной смеси различных тем, где тема характеризуется вероятностью генерируемых ею слов (используемая в работе модель похожа на распространённую в анализе текстовых данных моделью Латентного Размещения Дирихле).

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

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

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

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

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

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

1.3 Программное обеспечение для бикластерного анализа

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

Также в 2008 году был представлен алгоритм бикластеризации DisCo, работающий поверх архитектуры Hadoop MapReduce и реализующий алгоритм бикластеризации Брегмана, представленный в 2007 году.

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

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

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

Упор здесь делается на анализ именно англоязычных текстов, так как большинство существующих методов обработки естественного языка заточено на работу с английскими словами. Также наиболее популярные электронные библиотеки (такие как IEEE Xplore и Springer) предоставляют доступ только к англоязычным статьям. Однако в дальнейшем планируется адаптировать реализованный инструмент для работы и с русскоязычными текстами.

2. Алгоритмы и метрики для бикластерного анализа текстов

В данной главе представлены подходы к решению задач, необходимых для проведения бикластерного анализа текстовых данных. Данные задачи включают в себя:

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

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

· Построение матрицы релевантности по заданной коллекции текстов, набору ключевых фраз и метрике релевантности;

· Построение матрицы схожести между ключевыми фразами на основе матрицы релевантности и по заданному порогу релевантности;

· Бикластерный анализ матриц релевантности, матриц схожести или других созданных пользователем матриц;

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

2.1 Загрузка аннотаций статей

Для загрузки аннотаций к научным статьям было выбрано два источника: IEEE Xplore Digital Library и библиотека Springer Link. Оба выбранных источника предоставляют HTTP интерфейс для загрузки аннотаций к научным статьям и другой метаинформации, такой как название статьи, дата публикации, автор(ы) статьи, название журнала и некоторые другие данные.

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

· Inspec: controlled indexing - словосочетания из тезауруса базы данных Inspec;

· Inspec: not controlled indexing - словосочетания свободного формата (не только из тезауруса);

· Авторские ключевые слова;

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

2.2 Ключевые слова и словосочетания

В данной работе рассмотрены три источника ключевых слов: искусственно составленный список ключевых словосочетаний (см. Приложение 1), ключевые словосочетания, предоставляемые электронной библиотекой IEEE Xplore, а также сами научные статьи.

1) Алгоритмы выделения ключевых словосочетаний.

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

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

Очень часто при выделении ключевых слов используются метрики релевантности - например, TF-IDF. Для получения ключевых слов на основе метрики, можно из каждого текста в коллекции выделять ограниченное количество наиболее релевантных слов (то есть тех слов из текста, для которых метрика показывает наилучший результат), после чего объединять полученные слова в единое множество ключевых слов. Для того, чтобы слова, не отражающие специфику документа, как the, a, however и тому подобные, не попадали в множество ключевых слов, используются списки так называемых стоп-слов (stop-words). Слова, попадающие в стоп-лист, просто не учитываются алгоритмами выделения ключевых слов.

Другим популярным подходом к выделению ключевых слов является подход на основе графов зависимостей между словами. Пожалуй, наиболее известным таким методом является TextRank, на котором мы и остановимся. Создателями метода TextRank было показано, что их метод превосходит по точности даже алгоритмы, использующие обучение, на одинаковых данных. Основная идея метода TextRank заключается в построении графа связей между словами из текста. Такой граф содержит в качестве вершин все слова, которые встречаются в тексте. Этот набор слов можно ограничивать - например, не включать слова из стоп-листа и/или включать только слова, относящиеся к определённым частям речи, например, только существительные и прилагательные.

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

Граф, построенный по описанному выше принципу, далее обрабатывается известным алгоритмом индексирования веб-страниц PageRank, который был представлен Брином и Пейджем в 98 году. Этот алгоритм является итеративным и основывается на той идее, что вершины, в которые входит большое количество рёбер, имеют большой вес. Таким образом, конечный вес вершины определяется из весов других вершин, связанных с ней ребром. После того, как конечные веса для всех слов были подсчитаны алгоритмом, TextRank выделяет k слов с самым высоким весом и помечает их как ключевые. Следующим шагом является выделение ключевых фраз на основе уже выделенных ключевых слов. Все вхождения ключевых слов в текст помечаются, после чего последовательности ключевых слов (стоящих подряд) объединяются в ключевые фразы. В качестве примера, приведено предложение «Matlab code for plotting ambiguity functions». Если TextRank выделил слова Matlab и code, то из них будет образовано единое ключевое словосочетание Matlab code, при этом объединяться может более двух слов сразу.

2) Модификация TextRank.

При обработке аннотаций к научным статьям по отдельности алгоритмом TextRank, всё же получается довольно много «шума», то есть слов, которые сложно использовать в качестве ключевых. Поэтому в данной работе была реализована модифицированная версия TextRank, в которой граф слов строился на основе всей коллекции аннотаций (алгоритм тестировался на коллекциях размером от 300 до 3000 аннотаций на одну тематику). После обработки такого графа с помощью метода PageRank, «склеивание» ключевых слов в ключевые словосочетания происходило, если полученное словосочетание встречается хотя бы в текстах (аннотациях) из коллекции - параметр может настраиваться пользователем. В экспериментах над аннотациями к научным статьям брался равным трём, чтобы избежать попадания «шумовых» словосочетаний в коллекцию. Если ключевое слово присутствует хотя бы в одном из «склеенных» словосочетаний, то оно больше не используется как самостоятельное ключевое слово. Это сделано для того, чтобы исключить из потенциальных бикластеров ключевых фраз явные зависимости между фразой и словами, содержащимися в ней, так они несут в себе очень мало информации. Также при обработке аннотаций, в граф связей добавлялись только существительные, как кандидаты на роль ключевых слов. Однако пользователь конечной программы может задавать части речи, которые он хотел бы учитывать. В дополнение, для повышения эффективности TextRank все слова из текстов предварительно обрабатываются при помощи лемматизации, то есть все слова приводятся к словарной форме (“better” “good”, “cats” “cat” и т.п.).

3) Частотный анализ.

В программной реализации данной работы также представлен другой метод выделения ключевых слов, который отсекает все слова, встречающиеся в слишком малом или слишком большом количествах текстов (слова из стоп-листа не рассматриваются). Такой метод был использован в экспериментах Диллона для бикластеризации матриц релевантности слово/текст. Диллон рассматривал только те слова, которые встречаются не менее, чем в 0,2% и не более, чем в 15% статей из коллекции. В программной же реализации данной работы пользователю даётся возможность указать собственные минимальный и максимальный пороги. Разработанное программное обеспечение также даёт возможность использовать гибридный метод выделения ключевых словосочетаний, объединяющий модифицированный TextRank и частотный анализ. Идея заключается в том, что после обработки слов по методу PageRank, кандидаты на роль ключевых слов дополнительно фильтруются на основе их частоты встречаемости в коллекции. Пороги частоты для фильтрации по умолчанию используются такие же, как и в экспериментах Диллона, но могут регулироваться пользователем.

2.3 Метрики релевантности

Интуитивно понятно, что чем чаще некоторое слово встречается в тексте, тем оно более релевантно для этого текста. Отсюда получаем базовую метрику релевантности:

,

где - это количество вхождений слова w в текст d. Однако такая метрика, например, для слова the в англоязычном тексте, скорее всего, даст очень высокое значение, тогда как значимость этого слова при анализе текста чаще всего очень мала. Далее в этом разделе мы рассмотрим несколько более сложных метрик, хорошо себя зарекомендовавших в практических приложениях.

1) TF-IDF

Пожалуй, самой известной и распространённой метрикой релевантности слово-текст является TF-IDF (Term Frequency - Inverse Document Frequency). В основу этой метрики легла идея о том, что слова, встречающиеся в малом количестве текстов, скорее всего, несут в себе больше информации и лучше отражают назначение текстов, по сравнению с широко используемыми словами - как уже много раз упомянутое слово the. Таким образом, появилась концепция IDF, которая в какой-то степени отражает «вес» слова в коллекции текстов:

,

где D - коллекция документов (текстов). Отношение под логарифмом в явном виде отражает широту использования слова w. Данную формулу также иногда интерпретируют как собственную информацию, которую несёт слово w, для данной коллекции. Это следует из того, что отношение можно рассматривать, как условную вероятность появления слова w в тексте - Pw, тогда собственная информация этого события будет равна:

.

Общая формула для подсчёта релевантности по метрике TF-IDF выглядит следующим образом:

.

Эта метрика хорошо себя зарекомендовала себя для ранжирования документов по поисковому запросу.

2) Okapi BM25.

Так же, как и TF-IDF, метрика Okapi BM25 - далее просто BM25 - является эвристической моделью, которая, помимо уже рассмотренных компонентов tf и idf, также учитывает длину текста. В дополнение, BM25 включает в себя два настраиваемых параметра, назначение которых можно будет скоро увидеть. Чаще всего данная метрика записывается в следующем виде:

,

где - длина документа d в словах, а - средняя длина документов в коллекции D. Здесь и b являются настраиваемыми параметрами. Можно заметить, что от величины зависит вес - частоты слова - в метрике: при значении , равном нулю, частота слова, как и длина документа, не учитываются вовсе, тогда как большое значение параметра приводит метрику к виду практически идентичному метрике TF-IDF. Аналогично, параметр b влияет на «значимость» длины документа d относительно средней длины по коллекции. При b = 0, метрика не учитывает относительную длину документа, тогда как при b = 1, относительная длина имеет наиболее значительный вклад в подсчёт релевантности. При выборе значений этих двух параметров рекомендуется выбирать из отрезка и b = 0,75.

3) Метод АСД.

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

Суффиксное дерево - это дерево, хранящее все суффиксы некоторой строки в виде последовательности символов.

Рисунок 1. Аннотированное суффиксное дерево для строки XABXAC

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

Для того, чтобы ввести эту метрику нужно сначала ввести несколько понятий. Условной вероятностью вершины v будем называть , где f(v) - это частота, присвоенная вершине v, а parent(v) - родительская вершина для v. Теперь, если мы хотим рассчитать степень вхождения подстроки s в дерево A, то сперва нужно найти цепочку максимальной длины от корня дерева к некоторой вершине (…), которая совпадает с префиксом подстроки s. Теперь:

Для того, чтобы подсчитать степень вхождения всей строки S в дерево A необходимо сперва оценить степень вхождения всех её суффиксов в A, после чего объединить их по формуле:

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

4) Методы подсчёта метрик релевантности.

Разработанное программное обеспечение предоставляет пользователю возможность выбирать одну из метрик TF-IDF, BM25 или метод АСД. Также могут использоваться простые метрики: количество вхождения слова/фразы в текст и количество вхождений в текст, делённое на длину текста без учёта слов из стоп-листа.

При подсчёте всех метрик, в которых тексты представляются в формате «мешка слов» (то есть всех перечисленных выше, кроме метода АСД), тексты из коллекции предварительно обрабатываются. Для этого был разработан следующий подход: для каждого текста составляется хеш-таблица, где ключём выступает основа (стем) слова, - фрагменты слов, полученные удалением аффиксов - а значением является массив индексов. Такой массив содержит порядковые индексы тех слов в тексте, основы которых совпадают с ключем.

Например, в предложении “Development of an effective cluster validity measure with outlier detection and cluster merging algorithms for support vector clustering” три раза встречается основа “cluster” (один раз в изменённой форме “clustering”). Соответственно, если нумеровать слова в предложении с нуля, то массив индексов для основы «cluster» будет содержать индексы {4, 11, 17}. Важно отметить, что массивы индексов в хеш-таблицах упорядочены по возрастанию (что получается естественным образом, так как данные массивы заполняются по мере прохождения циклом по всем словам в тексте)

Такое представление текстов было выбрано в связи с тем, что массивы индексов для разных основ слов легко объединять в единый упорядоченный список, пользуясь которым можно быстро находить вхождения ключевых словосочетаний в текст. Допустим, необходимо найти количество вхождений словосочетания “cluster validity” в рассмотренное выше предложение. Для этого посмотрим в хэш-таблицу на основы слов “cluster” и “valid” и объединим массивы индексов:

Таблица 1. Массивы индексов

“cluster”	“valid”	Объединённый массив
{4, 11, 17}	{5}	{4, 5, 11, 17}

После объединения массивов необходимо найти все группы последовательных индексов нужной длины (в данном случае длины 2, так как ключевое словосочетание состоит из двух слов) и проверить, действительно ли они составляют вместе ключевое словосочетание. В данном примере присутствует только одна такая группа - (4, 5) - которая как раз соответствует ключевому словосочетанию “cluster validity”. Заметим, что при поиске в предложении изменённых словосочетаний, таких как «clustering validity» или «clustering validation», в данном примере также найдётся вхождение, так как проверяются не сами слова, а их основы.

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

Возвращаясь к методу АСД: для подсчёта релевантности по этому методу используется линейный алгоритм, представленный Михаилом Дубовым в 2014 году, и реализованный в модуле для языка Python - EAST.

Что касается ключевых словосочетаний, предоставляемых библиотекой IEEE Xplore, при анализе аннотаций к научным статьям, метрики релевантности не использовались. Вместо этого матрицы релевантности фраза/текст строились, как бинарные, то есть для каждой статьи помечались единицей те словосочетания, которые были указаны авторами самой статьи или были выбраны специалистами при индексации в базе данных Inspec.

2.4 Подсчёт схожести между ключевыми фразами

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

Далее, основываясь на векторах релевантности, мы высчитываем схожесть между двумя ключевыми словами и по формуле:

,

где - это множество текстов, таких, что для каждого выполняется следующее свойство:

.

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

2.5 Алгоритмы бикластерного анализа

В данном разделе мы рассмотрим два подхода к бикластерному анализу матриц. Первый был представлен в статье Диллона “Co-clustering documents and words using Bipartite Spectral Graph Partitioning”, а второй в статье Бориса Миркин и Андрея Крамаренко “Approximate Bicluster and Tricluster Boxes in the Analysis of Binary Data”. Также здесь представлен новый жадный алгоритм, основанный на результатах работы Миркина и Крамаренко.

1) Спектральное разложение двудольного графа.

В статье «Co-clustering documents and words using Bipartite Spectral Graph Partitioning» Диллон предложил идею одновременной кластеризации текстов и ключевых слов. Эта идея строится на том, что типичная схема кластеризации документов основана на идее представления документов в виде векторов ключевых слов с весами (релевантностями). В то же время, кластеризация слов часто основывается на симметричной модели: слова сравниваются по векторам их принадлежности к документам в коллекции.

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

Задача разбиения такого графа на две части (два кластера) становится задачей нахождения минимального разреза в графе. Разрез вершин на два подмножества вершин определяется как:

,

где - это матрица смежности графа . На основе этого определяется вес разреза для большего количества подмножеств вершин:

Рассмотрим теперь общую матрицу релевантности слово/текст A. Заметим, что матрицу смежности соответствующего двудольного графа можно записать как:

,

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

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

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

где . Такой вектор q удовлетворяет уравнению:



Матрица L в данном уравнении является матрицей Лапласа и определяется как:

Отсюда получаем, что необходимо минимизировать функцию:

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

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

- сумма весов рёбер смежных со словом i,

- сумма весов рёбер смежных с текстом j.

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

А второй собственный вектор матрицы L равен:

где - левый и правый сингулярные векторы матрицы соответственно.

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

Программная реализация данного метода присутствует в довольно популярной библиотеке алгоритмов машинного обучения для Python - Scikit-Learn. Эта реализация и была использована в данной работе для предоставления метода спектрального разложения двудольного графа.

2) “Коробочная” кластеризация - BBox.

Для удобства будем считать, что матрица связей между объектами имеет бинарный вид, то есть матрица содержит единицу, если соответствующие два объекта связаны между собой, и ноль в противном случае. Пусть дана матрица R = , где - объекты первого типа, - объекты второго типа, тогда назовём бикластером пару подмножеств , , таких, что:

,

при этом нельзя расширить подмножества V или W, не нарушив это свойство.

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

,

где - остаток, l - константа для бикластера, а и - бинарные векторы принадлежности множествам V и W соответственно, то есть тогда и только тогда, когда . Данная модель приводит к следующему критерию для минимизации суммы квадратов остатков:

В свою очередь, было показано, что данный критерий привёл к оптимальному l, равному плотности бикластера:



Что привело авторов к основному критерию для максимизации:

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

Алгоритм BBox(i):

1. Инициализация: V = {i}, W = {j| };

2. Для всех ;

3. Для всех ;

4. Для всех ;

5. Для всех ;

6. Найти максимум среди всех и , и, если он больше , добавить/удалить соответствующую строку/столбец из бикластера, после чего перейти к шагу 2. Иначе вернуть текущий бикластер.

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

· Для всех плотность однострочного бикластера меньше половины плотности всего бикластера ;

· Для всех плотность однострочного бикластера больше или равна половине плотности бикластера ;

· Аналогичное свойство выполняется и для столбцов матрицы.

Данная модель бикластеризации была также обобщена авторами для нахождения трикластеров и даже кластеров большей размерности (P-кластеры).

1) Новый жадный алгоритм.

Более формально, представленные выше свойства оптимального бикластера, найденного алгоритмомо BBox, можно записать так:

· ;

· ;

· ;

· .

Здесь .

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

Алгоритм GreedyBBox

Вход: матрица и индекс начального ряда k

Выход: бикластер

1. ;

2. ;

3.

4. Добавить все ряды к , для которых ;

5. Удалить все столбцы из , для которых ;

6. ;

7. ;

8.

9. Если перейти к шагу 3, иначе вернуть бикластер .

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

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

В силу того, что алгоритм GreedyBBox основан на жадном итеративном подходе, получаемые бикластеры могут быть похожи на локальные оптимумы, получаемые алгоритмом BBox, но, всё же, несколько отличаться. В ходе экспериментирования над аннотациями к научным статьям было замечено, что среди бикластеров, полученных алгоритмом GreedyBBox, содержится очень большое число похожих бикластеров - отличающихся на один-два элемента по строкам и/или столбцам. В связи с этим, полученные бикластеры фильтруются на основе схожести между ними. Схожесть между бикластерами высчитывается на основе коэффициента Жаккарда:

,

,

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

2) Мемоизация в BBox.

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

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

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

2.6 Визуализация бикластеров ключевых фраз

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

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

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

...