Содержание к диссертации
Введение
Глава 1. Автоматическая кластеризация текстовых коллекций 13
1.1. Общая постановка задачи кластеризации текстовых коллекций 13
1.2. Кластеризация текстовых коллекций и классификация текстов 16
1.3. Анализ предметной области 24
1.4. Подход к кластеризации текстовых коллекций, содержащих сложные термы 43
Глава 2. Метод сущностной кластеризации 50
2.1. Выделение сущностей из текстов 50
2.2. Формирование множества ключевых термов 60
2.3. Построение графа совместной встречаемости термов 67
2.4. Итоговая кластеризация текстовых коллекций 71
Глава 3. Алгоритм сущностной кластеризации и его применения 78
3.1. Описание алгоритма сущностной кластеризации 78
3.2. Создание программной реализации алгоритма сущностной кластеризации 88
3.3. Тестирование алгоритма сущностной кластеризации 94
3.4. Применения метода сущностной кластеризации 95
Заключение 99
Список литературы 102
Приложение 107
- Кластеризация текстовых коллекций и классификация текстов
- Подход к кластеризации текстовых коллекций, содержащих сложные термы
- Формирование множества ключевых термов
- Создание программной реализации алгоритма сущностной кластеризации
Введение к работе
Начиная с 1950-х годов количество и общий объем текстовых документов, используемых в научной работе, бизнесе и других областях человеческой деятельности неуклонно растет. Этот рост выражается как в увеличении общего объема текстовых коллекций, так и в значительном росте количества документов, требующих обработки и сортировки.
Согласно исследованию Калифорнийского университета (University of California- Berkley), в 2002 году в мире было произведено около 5 млн. терабайт информации. Для сравнения: объем информации библиотеки Конгресса США, где хранится 19 млн. книг и 56 млн. рукописей, - около 10 терабайт, т.е. в 500 тысяч раз меньше.
По данным исследовательской службы CyveiUance Inc., общее количество страниц в сети Интернет на 2001 год превысило 4 миллиарда и растет экспоненциально. Кроме того, существенный объем текстовой информации содержится в корпоративных базах данных и электронных библиотеках по всему миру.
1999 2000 2001 2002 2003 2004 2005 2006 2007 2005 2009 2010 ГОД
Рис. 1. Количество сообщений, ежедневно посылаемых по e-mail
Если в 2000 году (см. рис. 7) в мире отсылалось по 10 млрд. сообщений электронной почты в день, то в 2006 году - уже по 60 млрд. писем ежедневно [1].
Следствием столь бурного роста объема текстовых данных в мире, а также стремительного развития сети Интернет, стала необходимость предварительной систематизации текстовых массивов в автоматическом режиме: в первую очередь, появилась актуальная задача поиска нужной информации в больших и сверхбольших коллекциях текстовых данных (например, выдаваемых поисковыми системами в ответ на запросы пользователей).
Кроме того, без систематизации текстов невозможно решение и ряда других задач, в частности:
реферирования больших документальных массивов;
определения взаимосвязей между группами документов;
упрощения визуализации текстовой информации;
выявления дубликатов или близких по содержанию документов;
контент-анализа и др.
Несмотря на это, в настоящее время только 10% всей хранящейся в мире текстовой информации приходится на структурированные массивы данных (в первую очередь - базы данных и базы знаний) [2]. Одновременно, согласно данным исследования Reuters, до 38% менеджеров тратят, по их мнению, слишком много времени на поиск и систематизацию нужной информации, а из всех журналистов, обращающихся к Интернету в поисках новостей, лишь 20% находят информацию, которая им необходима.
В этих условиях разработка специальных методов кластеризации текстовых документов, т.е. разбиения текстовых массивов на систему (возможно иерархических) схожих подмножеств, становится важной задачей, без решения которой эффективная работа с текстовой информацией невозможна. Кластеризация текстового массива позволяет
систематизировать коллекцию и сузить область рассматриваемых документов. При необходимости можно провести кластеризацию второго уровня, применяя ту же процедуру разбиения к кластерам, полученным на первом этапе, и так далее. Таким образом, человек получает инструмент для решения задач, связанных с анализом больших массивов текстовой информации.
Актуальность разработки методов кластеризации возросла и с появлением концепции «информационной проходки». Эта концепция описывает различные методы анализа информации в базах данных с целью нахождения зависимостей, аномалий и трендов без выяснения смыслового значения записей.
Наиболее востребованной на сегодня и, вероятно, в ближайшем будущем является смысловая (или, по-другому, тематическая) кластеризация текстовых документов. Этот вид кластеризации предполагает разделение текстовых коллекций на множества текстов (далее - кластеры), такие, что тексты в пределах одного и того же кластера максимально схожи между собой по смыслу, в то время как тексты, относящиеся к разным кластерам, имеют различный смысл. При смысловой кластеризации текстов возможна «пометка» выделяемых кластеров их тематическими описателями. Именно смысловая кластеризация (далее просто кластеризация) текстов рассматривается в этой работе.
До 1980-х годов основными методами кластеризации текстов являлись экспертные (ручные) методы, основанные на использовании экспертных оценок для определения тематики документов. В то время использование экспертного подхода являлось единственной парадигмой, позволявшей разрабатывать широко применимые методы текстовой кластеризации.
Сегодня этот подход продолжает оставаться эффективным для решения задач, требующих принятия нетривиальных решений об отнесении тех или иных текстов к одному кластеру. Примером может служить кластеризация историй болезней пациентов в базах данных лечебных учреждений, так как наилучшее разделение пациентов на тематические группы должно учитывать факторы, которые на основе историй их болезней может выявить только опытный врач.
Однако, вместе с тем, ручные методы кластеризации обладают особенностями, существенно ограничивающими возможности их использования:
ручная кластеризация применима только для относительно небольших коллекций документов;
ручные методы требуют длительного времени для работы, так как эксперту необходимо время на принятие решения по каждому тексту.
Указанные особенности методов ручной кластеризации текстов сделали актуальной разработку полуавтоматических, а позднее и автоматических методов текстовой кластеризации.
В настоящее время существует большое количество задач, решение которых практически невозможно без применения автоматических методов кластеризации:
службы поддержки клиентов различных компаний сталкиваются с
задачей структурирования и анализа отзывов или жалоб клиентов
с целью определения наиболее сильных источников их
недовольства и раннего выявления новых причин их
неудовлетворенности;
эксплуатационным службам производственных компаний
необходимо проводить кластеризацию отчетов о нештатных
ситуациях для организации более эффективного управления
' производством, выявления опасных трендов, способных привести к повышению потенциальной аварийности;
исследователям и ученым необходимо проводить мониторинг публикаций по тематике их работы для выявления новых идей и трендов;
при работе с базами данных для уменьшения объема регулярно обновляемой выборки информации часто необходимо их сжатие, которое может быть проведено путем ее кластеризации: если исходная выборка избыточно большая, то можно сократить её, оставив по одному наиболее типичному представителю от каждого кластера.
Характерной чертой этих и многих других примеров задач кластеризации текстов является то, что документы, подлежащие кластеризации, представляют собой не фиксированный массив, а поток поступающих текстов, что делает актуальной также более сложную задачу отслеживания динамики распределения документов по кластерам во времени.
К этому типу относится, например, задача автоматической кластеризации новостного потока. Корректное разбиение новостного потока в соответствии с его тематической структурой важно не только для провайдеров новостей (как фактор, повышающий удобство и привлекательность этого сервиса для потребителей), но и для конечных пользователей, использующих новостную ленту.
При этом альтернатива автоматическим методам кластеризации, -ручная кластеризация, производимая экспертами, - во многих случаях
становится менее привлекательным вариантом. Это обусловлено не только указанными выше особенностями ручных методов кластеризации, но и постоянно растущей стоимостью ручного труда и сильной зависимостью полученных результатов от субъективного мнения эксперта.
История работ в предметной области ведет отсчет со второй половины XX века.
Следует отметить, что методы кластеризации текстов развивались параллельно с другими методами обработки текстовой информации: информационным поиском, классификацией текстовых коллекций, автоматическим выделением сущностей (блоков структурированной информации в тексте, отвечающих определенному шаблону и идентифицирующих объекты или свойства) и др. Вместе эти направления исследований образуют научную область, называемую углубленным текстовым анализом или (чаще) Text Mining.
Основные исследования в области разработки методов кластеризации текстовой информации, определяющие их дальнейшее развитие, приведены в таблице 1.
Табл. 1. Основные направления исследований в области кластеризации текстовой информации
Большое значение имели работы двух ученых из Корнельского Университета, G. Salton и A. Wang, которые дали существенный толчок к развитию методов автоматической кластеризации текстов. В 1975 году группа ученых из Корнельского университета опубликовала статью [3], предлагавшую описывать тексты в виде векторов в многомерном пространстве и, соответственно, использовать в работе с такими текстами-векторами стандартные меры близости в векторных пространствах.
Работа [3] послужила импульсом к развитию многочисленных исследований в области текстовой кластеризации, так как позволила уйти от семантических и лексических особенностей текстовой информации и рассматривать документы именно в качестве математических объектов. В числе прочего, была разработана одна из самых простых методик сопоставления векторов текстам, которая используется и сегодня, — модель векторного пространства (Vector Space Model, VSM). Описание VSM приведено в главе 1.
В настоящее время исследования в области разработки методов кластеризации текстов ведутся весьма интенсивно. Одна из причин этого -бурное развитие в последнее десятилетие информационных технологий, которые позволили исследовать сверхбольшие текстовые коллекции (объемом более терабайта).
В то же время, несмотря на значительное количество научных работ в области автоматической кластеризации текстовых массивов (одна из крупнейших электронных библиотек по информатике CiteSeer1 содержит около 3000 работ в этой области), регулярно продолжают появляться новые методы, а уже существующие уточняются для повышения их эффективности. При этом происходит все большая специализация предлагаемых методов автоматической кластеризации текстовых коллекций.
Новые подходы разрабатываются для решения конкретных задач: кластеризации юридических документов; кластеризации новостного потока; кластеризации текстов, содержащих большое количество сложных термов, т.е. устойчивых контекстуальных словосочетаний или составных нарицательных существительных, и др. Одним из таких подходов стало использование для кластеризации текстовой коллекции результатов предварительно проведенной кластеризации термов. В числе прочих, на этой идее основаны методы островной кластеризации.
Все эти факты указывают на то, что исследования в области повышения эффективности методов решения задач автоматической кластеризации текстовых коллекций продолжают оставаться актуальной проблемой. Эта диссертационная работа является одним из таких исследований.
Научная новизна исследования заключается в том, что в нем предлагается и развивается новая идея выделения и последующего использования сущностей при кластеризации текстовых коллекций. В работе предложен метод автоматической кластеризации коллекций документов, использующий выделенные из текстовой коллекции сущности
библиотека доступна онлайн по адресу
вместе с содержащимися в текстах ключевыми термами для построения графа их совместной встречаемости.
В ходе проведения диссертационного исследования использовались следующие области научного знания и относящиеся к ним методы:
математическая статистика;
методы оптимизации;
теория сложности вычислений;
методы извлечения сущностей (Named Entities Extraction I Recognition).
Практическая значимость работы обусловлена ее спецификой: предложенный метод позволяет решать задачу автоматической кластеризации коллекций текстов, в которых широко представлены сложные термы. В частности, метод может быть использован для кластеризации наборов политических статей, географических публикаций, аннотаций к научным работам, новостных сообщений - во всех приведенных примерах тексты содержат большое количество имен или географических названий. Исследовательские и образовательные учреждения могут использовать этот метод для разделения новых публикаций по соответствующей их профилю деятельности тематике на тематические кластеры.
Кроме того, разработанный метод позволяет снизить количество ситуаций, в которых отдельные слова, составляющие словосочетания, не включаются в граф совместной встречаемости термов из-за того, что частота их встречаемости в текстовой коллекции слишком мала, а мощность множества выбираемых из текстов значимых термов ограничена. Это может произойти, в частности, если проводится кластеризация документов, посвященных людям с одним и тем же именем,
но разной фамилией, или же местам, географические названия которых содержат одинаковые слова.
Результаты этой диссертационной работы успешно используются в
ряде организаций: построенный алгоритм реализован и внедрен в
технологический процесс сбора и аналитической обработки новостной
информации из зарубежных источников на головном предприятии
Федерального космического агентства; разработанный метод
кластеризации используется в деятельности российских архивов при
обработке архивных документов (в т.ч. в Историко-архивного институте
Российского государственного гуманитарного университета);
подразделения Департамента стратегического анализа и бюджетирования Минэкономразвития России применяют этот метод при анализе текстовой документации.
Построенный алгоритм был успешно протестирован в составе программного продукта для анализа данных.
Планируется включение программной реализации алгоритма в следующие версии системы.
Апробация работы была проведена в ходе нескольких международных и российских конференций, научных семинаров МФТИ и ВЦ РАН, а также в ходе работы Российской летней школы по информационному поиску в Екатеринбурге в 2007 г. (подробнее см. в Приложении).
Кластеризация текстовых коллекций и классификация текстов
Задача кластеризации коллекции текстов имеет много общего с задачей их классификации в заранее заданную пользователем систему категорий, каждой из которых соответствует массив заведомо правильно классифицированных текстов (задача определения самой системы категорий здесь считается уже решенной - см. определение 6). Такой массив текстов, каждому из которых сопоставлено подмножество системы категорий, обычно называют обучающим массивом текстов или обучающей выборкой.
В этом разделе на основе совместного рассмотрения процедур классификации текстов и кластеризации текстовых коллекций определяются требования, определяющие эффективность процедуры кластеризации.
Для этого вначале необходимо определить задачу классификации текстов (как и в случае кластеризации, по умолчанию рассматривается смысловая классификация текстов).
Определение 6. Задачей классификации текстов называется следующая задача: пусть задана коллекция X текстовых документов и система категорий Y. Пусть имеется конечная обучающая выборка текстов {х{,...,хт}еХ и отображение f:X- Y, заданное на множестве{хи...,хт}.
Требуется доопределить отображение/на всем множестве X, так, чтобы в одни и те же категории из Y отображались тексты, близкие по смыслу, а тексты, отображаемые в различные категории, отличались по смыслу.
Задачу классификации текстов часто называют также задачей категоризации или рубрикации документов.
Цели классификации текстов и кластеризации коллекции текстов могут быть различными в зависимости от особенностей конкретной задачи. Следующие типы задач кластеризации текстовых коллекций наиболее распространены: понять структуру множества текстов, разбив его на группы схожих объектов, и затем упростить дальнейшую обработку данных и принятия решений, работая с каждым кластером по отдельности. В этом случае часто целесообразно минимизировать количество кластеров; сократить объём хранимых данных в случае сверхбольшой выборки, оставив по одному наиболее типичному представителю от каждого кластера. В этом случае наиболее важным является обеспечение высокой степени сходства текстов внутри каждого кластера. Количество кластеров не определяется заранее; выделить нетипичные тексты, которые не подходят ни к одному из кластеров. Такую задачу называют одноклассовой классификацией текстов, а также обнаружением нетипичности или новизны {novelty detection). В этом случае наибольший интерес представляют отдельные тексты, не входящие в состав ни одного из кластеров.
Кластеризация текстовых коллекций может проводиться одним из двух способов: плоским и иерархическим.
Плоская кластеризация — простейший вид кластеризации. При плоской кластеризации текстов каждый документ связывается только с одной группой текстов. В большинстве случаев именно плоская кластеризация является основным способом кластеризации текстовых массивов. Другие названия плоской кластеризации: декомпозиция, к-кластеризация, разделение.
Иерархическая кластеризация — вид кластеризации текстов, при которой более крупные кластеры, выделенные на первом этапе, затем дробятся на более мелкие. Этот процесс повторяется для каждого из полученных кластеров до выполнения некоторого критерия остановки.
Задачи иерархической кластеризации множества текстов определенной предметной области называются задачами таксономии (taxonomy). Результатом таксономии является древообразная структура, выстраиваемая над текстами. Вместо одной метки кластера каждый документ характеризуется перечислением меток всех кластеров, которым он принадлежит (см. [5], [6]).
Таксономии строятся во многих областях знаний, чтобы упорядочить информацию о большом количестве объектов. В качестве примера на рис. 2 представлена таксономия текстовых описаний живых организмов на Земле.
Важное различие между задачами классификации текстов и кластеризации текстовых коллекций состоит в том, что, хотя решение обеих этих задач представляет собой субъективный процесс, субъективность решения задачи классификации в большей степени определяется выбором системы категорий, чем выбором алгоритма классификации текстов по этим категориям. Следовательно, при наличии заданной заранее системы категорий процесс построения решения задачи автоматической кластеризации текстовой коллекции более субъективен (а значит, более неоднозначен) чем процесс классификации принадлежащих ей текстов. Это обусловлено несколькими причинами: не существует однозначно лучшего критерия качества кластеризации. Известен целый ряд эмпирических критериев, несколько статистических критериев, а также ряд алгоритмов кластеризации, не имеющих чётко выраженного критерия оценки качества результатов их работы, но осуществляющих устойчивую кластеризацию в рамках заданной предметной области. Из-за этого разные алгоритмы кластеризации текстовых коллекций могут давать разные результаты, не сравнимые между собой; финальное количество кластеров обычно не известно заранее и выбирается автоматически или устанавливается в соответствии с субъективными критериями;результат кластеризации существенно зависит от метрики близости текстов, выбор которой, как правило, также субъективен и определяется экспертом.
Подход к кластеризации текстовых коллекций, содержащих сложные термы
На основании рассмотрения трех классификаций методов кластеризации текстовых коллекций возможно определить методы, которые могут быть взяты за основу для построения модифицированного метода кластеризации массивов текстов, содержащих сложные термы. Ими являются иерархические методы неэксклюзивной кластеризации, использующие нечисловые свойства текстов (в первую очередь, методы островной кластеризации).
Основные общие шаги (свойства), присущие большинству методов кластеризации текстовых коллекций, должны быть включены в разрабатываемый метод.
Для того чтобы различные формы одних и тех же термов не рассматривались как не связанные друг с другом, все термы, входящие в текстовую коллекцию, приводятся к нормальной форме.
Были разработаны специальные методы морфологического разбора текстов, впоследствии получившие название стемминга [19]. Можно выделить три направления стемминга: метод таблиц окончаний; метод правил словообразования; словарный метод. Метод таблиц окончаний [19] предполагает создание и последующее использование списка всех возможных окончаний в рассматриваемом языке. Каждое выделенное из текста слово ставится в соответствие предполагаемой начальной форме этого слова, которая получается отделением от слова максимально длинного окончания этого слова, содержащегося в таблице. Достоинство метода: высокая скорость работы (в большинстве используемых языков мощность множества возможных окончаний не превышает нескольких сотен: например, 250 для английского языка [19]). Недостаток этого метода: большая доля ошибок. Метод правил словообразования предполагает фиксацию набора правил построения форм слов языка. Каждое слово методом обратного хода проверяется на возможность отнесения к результатам действия некоторого правила. В простейшем случае далее выбирается такая начальная форма слова, что правило, индуцирующее данную форму, имеет наименьшее число шагов [19]. Достоинство метода: высокое быстродействие и малое количество ошибок. Недостаток метода: невозможность учета исключений. Для работы со словами-исключениями предназначен словарный метод стемминга, предполагающий использование уже существующего словаря форм слов в рассматриваемом языке и поиска по нему [19]. Для уменьшения мощности множества термов применяются следующие приемы: использование стоп-листов, содержащих списки «несмысловых» слов; использование методов лингвистики; использование словарей и тезаурусов для объединения нормальных форм в синонимические группы.
Сокращение набора признаков в максимальной степени служит для сокращения времени последующей кластеризации и используемых при кластеризации ресурсов, что актуально при обработке большого объема информации. Чаще всего уменьшение количества термов понижает качество кластеризации.
Несмотря на это, в случае однородных (т.е. содержащих схожие наборы термов) текстов в массиве можно достичь лишь небольшого понижения качества при существенном понижении количества термов, и, в отдельных случаях, даже получить более высокое качество. Можно выделить два способа сокращения множества термов: вычисление по эвристической формуле весов термов и выбор N термов с наибольшими весами (так называемый отсев характеристик —feature selection); кластеризация термов по близости степени влияния их на результаты классификации и подмена термов полученными кластерами в качестве характеристик.
Таким образом, методы кластеризации текстовых коллекций обладают набором схожих свойств, отраженных в реализующих их алгоритмах. Соответствующие этапы целесообразно включить в метод, разработке которого посвящена эта работа.
Теперь возможно сформулировать идею предлагаемого модифицированного метода кластеризации текстов.
Для ряда задач невозможность учесть семантические особенности текстов на естественном языке (в частности, омонимию и изменение смысла группы термов по сравнению с пересечением или объединением смыслов каждого терма в группе). Зачастую это приводит к тому, что кластеризация текстовых коллекций проводится с меньшей (по оценкам экспертов) эффективностью, чем было бы возможно при учете таких особенностей. Задача автоматической кластеризации коллекций текстов, содержащих сложные термы — одна из них.
Рассмотрение свойств, выявление достоинств и недостатков существующих методов кластеризации текстовых коллекций привело к идее построения модифицированного метода кластеризации множеств документов, содержащих сложные термы.
В части омонимии и синонимии предлагается использовать являющийся де-факто стандартом среди тезаурусов английского языка тезаурус WordNet [20]. В тезаурусе WordNet все слова и словосочетания сведены в синонимические группы (или, по-другому, синсеты). Одно слово может входить в несколько таких групп. Группы связываются между собой отношениями различных типов, зависящими от частей речи. Особый интерес имеют связывающие между собой группы существительных и группы глаголов отношения гипернимии («частное-общее»), а также связывающие группы существительных отношения голонимии («часть-целое»).
При использовании тезауруса WordNet можно заменять словоформу на набор маркеров синонимических групп, к которым она принадлежит, а затем, используя выбранный тип отношений, увеличивать веса групп, прямо или косвенно связанных с выбранными. Компонентам вектора признаков соответствуют в этом случае не слова, а синонимические группы. Синеет является базовой структурной единицей WordNet, объединяющий слова или словосочетания со схожим значением. Предполагается, что каждый синеет отражает в WordNet некоторое понятие языка. Таким образом, основой WordNet являются наборы синсетов, которые служат для выделения понятий. Например, «board» представляет по крайней мере два синсета: доска - board, plank; группа людей - board, committee. Эти наборы синсетов служат для разграничения лексических значений термов. В WordNet также представлены семантические отношения: синонимы, антонимы, гиперонимы и др. Связь обеспечивается наличием заданных наборов общих понятий, которые связаны через гипертекстовые ссылки (индексы) [21].
Формирование множества ключевых термов
Пусть Е — множество сущностей, выделенных из коллекции текстов Q. Множество Е дополняется множеством значимых термов коллекции Q, выбираемых в соответствии с определением 2 (см. [23]). Определение 2: терм t, содержащийся в текстовой коллекции Q, называется значимым (характерным) на уровне /3, если разница частоты встречаемости терма t в коллекции Q со средней частотой его встречаемости в большом массиве английских текстов превышает Д. В этом определении к термам отнесены слова и словосочетания, распознаваемые в коллекции Q с использованием тезауруса WordNet (см. главу 1). Пояснение определения 2: для любого документа характеризующие его термы в контексте этого исследования являются термами, связанными со смыслом текста, а значит, чаще, чем в среднем репрезентативном корпусе английских текстов, встречающиеся в этом документе. Следовательно, подмножество текстов, которое содержит каждый такой терм, целесообразно отнести к одному смысловому кластеру. Пороговый уровень /? выбирается равным нулю.
На начальном этапе проводится удаление стоп-слов коллекции Q и другие стандартные операции предварительного этапа обработки текстов (см. главу 1). Пусть К1 - множество значимых термов коллекции Q. Определение 3: начальным мноэюеством ключевых термов коллекции Q называется множество К = KI JE . Однако множество К содержит все значимые термы и сущности коллекции Q. Вследствие большой мощности это множество не всегда может быть использовано для построения вычислительно эффективного алгоритма кластеризации. В случае отсутствия дополнительной информации о результатах будущей кластеризации (нет предположений о центроидах получающихся кластеров), начальное множество ключевых термов фиксируется и принимается в качестве финального множества ключевых термов. В случае, когда известен результат экспертной кластеризации коллекции Q, либо коллекция Q является обучающей выборкой для кластеризации текстов определенного типа, либо известны предварительные центроиды получаемых кластеров (что часто встречается при решении реальных прикладных задач), возможно выделение из множества К части элементов для снижения размерности финального множества ключевых термов. Процесс определения весов элементов этого множества описан далее.
Далее используется представление текстов в стандартной модели VSM. Рассматривается «-мерное евклидово пространство, каждый текст представляется в нем вектором частот всех п рассматриваемых термов в этом тексте. Все вектора нормируются на единицу. Для таких векторов определено стандартное скалярное произведение в евклидовом простанстве. Определение 4: внутрикластерным отклонением вектора текста х., принадлежащего кластеру /, от центроида этого кластера сі по компоненте к называется величина где п — мощность множества К , J— количество текстов в коллекции Q; {Xj}, j є {1,...,/} - векторы текстов коллекции Q; {ct},i є {1,...,1} — множество известных центроидов (заданное или определенное на основе заданного результата кластеризации). Относящимися к данному кластеру і є {1,...,1} далее считаются все элементы JC, к которым центроид данного кластера с;. является ближайшим. Предлагаемая идея нахождения весов для х. заключается в следующем: рассматривается суммарное внутрикластерное отклонение текста х., принадлежащего кластеру /, от центроида этого кластера с(. как вектор, каждая компонента которого равна соответствующему внутрикластерному отклонению (2.8) с определенным весом vf, и затем это отклонение минимизируется. Однако непосредственная минимизация величины (2.9) приведет к вырожденному решению: внутрикластерное отклонение достигает минимума при равенстве весов всех элементов множества
К нулю, за исключением одного, который равен единице. Для получения невырожденного решения в методе сущностной кластеризации проводится минимизация суммы величины (2.9) и суммы квадратов весов элементов множества К при условии (2.10). Это отражено в следующем утверждении: Утверждение 2; оптимальными вектором V весов элементов множества К в методе сущностной кластеризации является решение задачи при условиях vf е[0,1],\/іє{1,...І},кє{1,...,п}и (2.10). Для решения задачи (2.11) используется следующая теорема.
Создание программной реализации алгоритма сущностной кластеризации
Описанный алгоритм был реализован с использованием программного продукта для анализа данных Megaputer Polyanalyst. Этот программный продукт позволяет не только использовать уже готовый код процедур для анализа текстовой информации, но и создавать новый.
Важнейшими факторами выбора этого программного продукта для реализации алгоритма стали следующие: Встроенная возможность удобной визуализации данных. Рис. 14 показывает пример такой визуализации.
В процессе исследования были разработаны различные регулярные выражения для тестирования извлечения сущностей из текстовых коллекций. В таблице 5 приведен список компонент регулярных выражений, которые могут быть объединены в логические выражения на этапе извлечения сущностей. Программное обеспечения для реализации шага 5 алгоритма было разработано вручную.
Для тестирования эффективности работы алгоритма сущностной кластеризации были сформированы две текстовых коллекции, содержащие сложные термы (подход к формированию коллекций соответствует подходу РОМИП [30]): выборки публикаций с сайтов новостей Google и Yahoo по тематикам George Bush/George Harrison и North Dakota/North Carolina (коллекции G и N соответственно). Подробное описание поставленных экспериментов приведено в приложении.
Как показано в прилооїсении, были получены следующие экспериментальные результаты в части полученных значений F-меры на двух коллекциях текстовых документов G и N:
Эти результаты подтверждают эффективность работы метода сущностной кластеризации на множествах текстов, которые содержат сложные термы.
Как показано далее, на обычных коллекциях текстов метод сущностной кластеризации показал в ходе опытной эксплуатации не худшие результаты, чем метод островной кластеризации. Метод сущностной кластеризации применяется для решения реальных прикладных задач.
Разработанный алгоритм был успешно протестирован в составе программного продукта для анализа данных Megaputer Polyanalyst. Планируется включение программной реализации алгоритма в следующие версии системы.
Описанный алгоритм реализован и внедрен в технологический процесс сбора и аналитической обработки новостной информации из зарубежных источников в Многофункциональном навигационно-информационном центре Федерального государственного унитарного предприятия «Российский научно-исследовательский институт космического приборостроения» (головного предприятия Федерального космического агентства).
Анализируемая информация в основном представляет собой наборы новостных сюжетов по тематике спутниковой навигации на английском языке.
Опытная эксплуатация показала высокую эффективность работы метода и не большее, чем в случае экспертной кластеризации, число ошибок в его работе.
Важным результатом является возможность использовать метод сущностной кластеризации для решения тех задач, для которых используется обычный метод островной кластеризации текстов. В частности, были кластеризованы массивы текстов о развитии спутниковой навигации в мире, содержащие среднее количество сложных термов.
Результаты этой диссертационной работы также активно используются в деятельности российских архивов при обработке архивных документов в ходе работ по совершенствованию системы научно-справочного аппарата. Работы проводятся специалистами и сотрудниками факультета технотронных архивов и документов (ФТАД) Историко-архивного института Российского государственного гуманитарного университета. Подразделения Департамента стратегического анализа и бюджетирования Минэкономразвития России применяют описанный метод при анализе текстовой документации.
Среди потенциальных применений метода сущностной кластеризации необходимо выделить классическую задачу, которую решает метод островной кластеризации: отслеживание динамики новостного потока. Следует ожидать, что как метод сущностной кластеризации позволит как автоматически выявить тонкую тематическую структуру массива новостей и других документов, содержащих сложные термы, так и проследить ее развитие во времени, при этом эффективность его работы окажется выше, чем у метода островной кластеризации.
Так как критерий принадлежности документа к тому или иному кластеру легко формализуется, то это позволит легко запрашивать соответствующие документы из хранилища на основе достаточно простых поисковых запросов.
Алгоритм сущностной кластеризации текстов позволяет проследить изменение тематической структуры потока текстов со временем.
Интересен пример отслеживания динамики новостной структуры. В такой задаче могут быть выявлены крупномасштабные направления динамики тем новостей, что определяется размером временного окна, используемого для разделения новостей по времени.
В подобном эксперименте, поставленном ранее на основе метода островной кластеризации, размер окна составлял примерно 2 недели [15]. Так как плотность новостей по времени в рассматриваемом массиве сильно понижалась в его более позднем по времени конце, все новости были разбиты на 6 частей и упорядочены по дате поступления. Были рассмотрены первые 5 частей. В каждом из этих временных слоев была проведена кластеризация новостей с помощью алгоритма островной кластеризации.
Пример соответствующей иерархической кластеризации, полученной алгоритмом островной кластеризации, приведен нарис. 19.
