Содержание к диссертации
Введение
Глава 1. Общая характеристика проблемы интеллектуальной обработки текста 10
1.1.Предметная область 10
1.2. Общая характеристика направлений в области интеллектуальной обработки текста 14
1.3.Общая характеристика моделей представления и методов интеллектуальной обработки текста 24
1.4. Общая характеристика перспективных моделей представления и методов интеллектуальной обработки текста и сложность их применения в настоящее время 30
1.5.Общая характеристика задач и основная терминология интеллектуальной обработки текста 39
1.6. Постановка задачи 46
Выводы по главе 1 47
Глава 2. Выбор модели представления и методов интеллектуальной обработки текста 49
2.1. Выбор модели представления текста 49
2.2. Выбор метода первоначальной обработки текста и формы представления конечного результата 54
2.3. Выбор методов интеллектуальной обработки текста 63
2.4. Выбор метода кластеризации семантической сети и метода получения агрегирующих характеристик 81
2.5. Выбор метода иерархической кластеризации для формирования оглавления текста 84
Выводы по главе 2 86
Глава 3. Разработка методов и алгоритмов интеллектуальной обработки текста 88
3.1. Разработка методов кластеризации семантической сети и получения агрегирующих характеристик 88
3.2. Разработка алгоритма иерархической кластеризации и формирования оглавления текста 94
3.3. Разработка алгоритма синтеза заголовков выделенных разделов текста 98
3.4. Разработка алгоритма формирования связанного текста 101
Выводы по главе 3 105
Глава 4. Экспериментальное исследование методов и алгоритмов интеллектуальной обработки текста 107
4.1. Общее описание и характеристика эксперимента 107
4.2. Экспериментальное исследование метода получения агрегирующих характеристик 112
4.3. Экспериментальное исследование метода иерархической кластеризации и формирования структуры текста 123
4.4. Экспериментальное исследование метода синтеза заголовков выделенных разделов текста 128
4.5. Экспериментальное исследование метода формирования связанного текста 133
Выводы по главе 4 136
Заключение 137
Список использованной литературы 139
- Общая характеристика направлений в области интеллектуальной обработки текста
- Выбор метода первоначальной обработки текста и формы представления конечного результата
- Разработка алгоритма иерархической кластеризации и формирования оглавления текста
- Экспериментальное исследование метода синтеза заголовков выделенных разделов текста
Введение к работе
Актуальность работы. В настоящее время история развития информационных систем, т. е. систем, предназначенных для хранения и обработки информации с использованием ЭВМ, насчитывает уже более полувека. Еще относительно недавно в ходу были перфораторы в качестве устройств ввода данных, листинги в виде рулонов бумаги длиной порой до нескольких метров в качестве носителя результатов машинной обработки, недельные, либо месячные временные интервалы — в качестве нормативных сроков обработки информации. В последнее десятилетие прошлого века ситуация претерпела качественные изменения. Основу информационной системы в настоящее время составляют: база данных, как правило, реляционного типа, поддерживающая доступ на основе стандарта SQL, программные средства, обеспечивающие логику обработки данных, и интерфейс пользователя.
Применение баз данных благодаря специальным методам хранения и представления данных и соответствующим алгоритмам оперирования ими позволяет обеспечивать высокую производительность информационных систем, а наличие единого стандарта доступа к данным обеспечивает высокую эффективность их разработки и функционирования. Но с другой стороны применение баз данных требует специальной процедуры ввода данных, и если исходная информация представлена в виде неструктурированного естественноязыкового текста, то эта процедура становится весьма трудоёмкой, в виду чего становится актуальной задача автоматизации этой процедуры. Эта задача требует применения методов интеллектуальной обработки текста, которые активно развиваются в настоящее время. Хотя существующие на настоящее время методы интеллектуальной обработки текста не способны оценивать его структурированность в той степени, в какой эта характеристика текста отражается в человеческом восприятии, что не позволяет создавать полностью автоматические системы ввода данных, а кроме того производительность вычислительной техники на настоящее время остаётся всё ещё недостаточной для эффективной работы многих методов интеллектуальной обработки текста, тем не менее применение частично автоматизированных систем может существенно сократить трудоёмкость процедуры ввода данных, что обусловливает актуальность задачи разработки этих автоматизированных систем.
В области интеллектуальной обработки текста первым значительным успехом было появление контекстно-свободных грамматик Н. Хомского. В нашей стране большее распространение получила модель "смысл-текст" И. А. Мельчука. Возможные доработки и модификации этой модели были предложены Ю. Д. Апресяном, а также Е. В. Падучевой. В практическую реализацию систем интеллектуальной обработки текста, основанных на этой модели, большой вклад внесли А. В. Сокирко, П. В. Толпегин, И. М. Ножов, их предшественниками в этой работе были Н. Н. Леонтьева, С. Л. Никогосов, И. М. Кудряшова, О. Б. Малевич.
Развитие Internet'a потребовало широкого применения других методов интеллектуальной обработки текста, в первую очередь методов информационного поиска. Первый метод информационного поиска был предложен К. Муром в 1948 году, сначала его применение ограничивалось обеспечением доступа к книгам, журналам и другим документам в университетах и библиотеках. Первая поисковая система для Internet'a разработана М. Грэем из Массачусетского технологического института в 1993 году. Ранее в 1988 году С. Диэрвестером был предложен латентно-семантический анализ, основанный на теории сингулярного разложения, разработанной Дж. Сильвестром в 1889 году. Также в качестве одного из методов интеллектуальной обработки текста стал активно использоваться кластерный анализ, впервые предложенный Р. Трионом в 1939 году.
Тем не менее все эти подходы к интеллектуальной обработке текста не могли обеспечить качество решения различных задач, адекватное восприятию естественно-языковых текстов человеком. Одной из попыток достичь более высокого качества интеллектуальной обработки текста является начатый в США в 90-е годы прошлого века проект «Микрокосмос», работа над которым продолжается в настоящее время. Этот проект ориентирован преимущественно на решение задачи машинного перевода и основные его наработки касаются английского и испанского языков. Среди работ, выполненных в нашей стране, можно отметить семантический анализатор, разработанный В. А. Тузовым, а также разрабатываемый в настоящее время в Санкт-Петербургском институте лингвистических исследований открытый лингвистический процессор. Ещё один подход к интеллектуальной обработке текста предложен В. А. Фомичевым.
Сложность применения перечисленных более новых подходов к интеллектуальной обработке текста для построения автоматизированной системы ввода данных в информационные системы с формализованной
структурой документа состоит в том, что не существует ни одной завершённой, общедоступной и практически применимой реализации какого-либо из этих подходов для русского языка. В связи с этим предлагается основывать интеллектуальную обработку текста на модели "смысл-текст" И. А. Мельчука, сочетая с элементами подходов, появившихся в связи с развитием Internet'а.
Объектом исследования являются информационные системы, использующие в своих данных естественно-языковый текст и использующие его формализованную структуру.
Предметом исследования являются модели представления естественноязыкового текста и алгоритмы для его формализованного структурирования.
Цель и задачи исследования. Основной целью представленной диссертации является разработка модели представления, методов и алгоритмов интеллектуальной обработки текста с целью его формализации в информационных системах. При этом решаются следующие задачи:
Разработать модель представления естественно-языкового текста на основе семантической сети для его интеллектуальной обработки текста с целью формализации в информационных системах
Разработать алгоритм структурирования естественно-языкового текста для его формализации в информационных системах в соответствии с такими критериями структурированности текста, как наличие иерархического оглавления, наличие заголовков у каждого из разделов оглавления, семантическая связанность внутри каждого из разделов.
Разработать методы и алгоритм интеллектуальной обработки текста на основе иерархической и бинарной кластеризации семантической сети для формирования иерархического оглавления естественно-языкового текста.
Разработать алгоритм интеллектуальной обработки текста на основе методов квазиреферирования для формирования заголовков у каждого из разделов оглавления.
Разработать алгоритм интеллектуальной обработки текста на основе исчисления предикатов для обеспечения семантической связанности внутри каждого из разделов оглавления.
Методы исследования. Для проведения исследований были использованы методы графематического, морфологического, синтаксического и первичного семантического анализа естественно-языковых текстов, методы иерархической и бинарной кластеризации, матричные вычисления, методы квазиреферирования, исчисление предикатов.
Основные положения, выносимые на защиту:
Модель представления естественно-языкового текста на основе семантической сети.
Алгоритм структурирования естественно-языкового текста для его формализации в информационных системах.
Методы и алгоритм для формирования иерархического оглавления естественно-языкового текста.
Алгоритм для формирования заголовков у каждого из разделов оглавления.
Алгоритм для обеспечения семантической связанности внутри каждого из разделов оглавления.
Научная новизна работы.
Предложена модель представления естественно-языкового текста, базирующаяся на модели «смысл-текст» в виде семантической сети, отличающаяся единой семантической сетью для всего текста, использованием числовых значений для узлов и связей, позволяющая реализовать алгоритм формирования структуры естественно-языкового текста для его формализации в информационных системах.
Предложен алгоритм структурирования естественно-языкового текста для его формализации в информационных системах в соответствии с такими критериями структурированности текста, как наличие иерархического оглавления, наличие заголовков у каждого из разделов оглавления, семантическая связанность внутри каждого из разделов.
Разработаны методы и алгоритм интеллектуальной обработки текста на основе иерархической и бинарной кластеризации семантической сети для формирования иерархического оглавления естественно-языкового текста, отличающиеся предварительным вычислением агрегирующих характеристик для абзацев и возможностью получать переменное
количество структурных элементов на каждом уровне объединения.
Разработаны алгоритм интеллектуальной обработки текста на основе методов квазиреферирования для формирования заголовков у каждого из разделов оглавления, позволяющий формировать заголовки из фрагментов сгруппированных частей исходного неструктурированного естественно-языкового текста, делимого по лексемам.
Разработан алгоритм интеллектуальной обработки текста на основе исчисления предикатов для обеспечения семантической связанности внутри каждого из разделов оглавления, отличающийся использованием правил для предикатов, позволяющих расставить предложения в изначально несвязанных фрагментах естественно-языкового текста в порядке, обеспечивающем наибольшую семантическую связанность получаемого в итоге текста.
Достоверность научных результатов и выводов результатов исследований, полученных автором диссертации, подтверждена строгостью применяемых математических методов и приемлемой степенью согласованности теоретических научных положений с результатами экспериментальных исследований.
Научная и практическая ценность диссертационной работы заключается в том, что результаты, полученные в данной работе, могут быть использованы при обработке неструктурированных текстов, для выделения смысловой нагрузки в учебных и руководящих технических материалах, для определения наиболее актуальных тем при работе RSS-агрегаторов, для педагогических измерительных материалов.
Апробация работы.
Основные положения и результаты диссертации докладывались и обсуждались на 5-й научно-методической конференции «Инновации в науке, образовании и бизнесе» (г. Пенза, 2007 г.), на 14-й научно-методической конференции «Телематика'2007» (г. Санкт-Петербург, 2007 г.), на 15-й научно-методической конференции «Телематика'2008» (г. Санкт-Петербург, 2008 г.) и на научной конференции «Региональная информатика-2008» (г. Санкт-Петербург, 2008 г.)
Публикации.
Основные теоретические и практические результаты диссертации опубликованы в 9 статьях и докладах, из них по теме диссертации 9, среди которых 1 публикация в ведущих рецензируемых изданиях, рекомендованных в действующем перечне ВАК, 3 статьи в других изданиях. Доклады доложены и получили одобрение на 4 международных, всероссийских и межвузовских научно-практических конференциях перечисленных в конце автореферата. Основные положения защищены 1 патентом.
Структура и объем работы.
Диссертация состоит из введения, четырех глав с выводами, заключения. Она изложена на 148 страницах машинописного текста, включает 11 рисунков, 12 таблиц и содержит список литературы из 112 наименований, среди которых 85 отечественных и 27 иностранных авторов.
Общая характеристика направлений в области интеллектуальной обработки текста
Обработка текста может выполняться на разных уровнях его интерпретации и, начиная с определённого уровня, и при более глубинной интерпретации такая обработка может считаться интеллектуальной. Простейшим и самым нижним уровнем является работа со строками как с последовательностью символов.
Обработку текста на этом уровне интерпретации нельзя назвать интеллектуальной, и в этом случае действия сводятся к хорошо известному набору, поддерживаемому стандартными функциями во многих средах программирования, как сравнение по символам, сравнение по длине, поиск подстроки и т. п. Притом такой уровень интерпретации в равной степени применим как к естественно-языковым текстам, так и к любым другим последовательностям символов.
Следующим уровнем интерпретации можно считать обработку текста как множества слов и разделительных символов. В отличие от самого нижнего уровня интерпретации, на этом уровне возможна работа только естественно-языковыми текстами. Сам по себе процесс разбиения текста на слова и разделительные символы таюке нельзя признать интеллектуальной обработкой, и в современных средах программирования для решения этой задачи также предоставляется стандартный инструмент, а именно, регулярные выражения, но в зависимости от применяемых в дальнейшем методов работы с выделенными словами обработка текста на этом уровне интерпретации также может считаться интеллектуальной. Особенностью этого уровня интерпретации текста является независимость от конкретного языка, а зависимость лишь от особенностей пунктуации.
На этом уровне интерпретации естественно-языковых текстов чаще всего решаются два вида задач: прямое сравнение текстов с получением некоторой числовой или логической величины, как результата сравнения, и статистическая обработка текста для решения задач с более широким разнообразием форм представления конечных результатов. Классическим примером задач первого вида является задача информационного поиска, состоящая в присвоении каждому из присутствующих в системе текстовых документов некоторого значения его релевантности в диапазоне от 0 до 1 заданному поисковому запросу. В более сложном варианте задача поиска может быть отнесена одновременно и к задачам второго вида, если поиск выполняется не на основе прямого сравнения, а на основе исследования статистических закономерностей. К задачам второго вида могут быть отнесены также классификация и кластеризация документов, реферирование, машинный перевод, если эти задачи решаются на уровне интерпретации текста в виде множества слов и разделителей с применением статистических методов обработки.
Информационный поиск, как задача первого вида, получил широкое распространение в Internet-поисковиках [6], где в качестве методов поиска чаще всего используются инвертированные индексы, а также прямой поиск некоторых случаях. Для работы с инвертированными индексами применяются различные методы повышения производительности [7], отводится значительная роль принципам поддержания актуальности состояния инвертированного индекса в условиях меняющегося набора документов, используются методы распределения инвертированных индексов на вычислительных кластерах, причём предпочтительным, с учётом особенностей работы поисковых алгоритмов, является распределение по документам с наличием полного набора слов на каждом узле вычислительной системы.
Другими подходами к решению задачи информационного поиска как задачи прямого сравнения текстов являются суффиксные деревья и В-деревья. Суффиксные деревья чаще всего применяются при поиске по запросам сложного вида в не очень большом и достаточно постоянном объёме текстов, поскольку этот алгоритм требует значительных вычислительных затрат на обработку текста, но обеспечивает высокую производительность при сложных запросах. Этот подход подробно описан в диссертации [8]. В-деревья получили широкое распространение при проектировании систем управления базами данных (DBMS), в то время как на уровне интерпретации текста как множества слов такой подход применяется значительно реже.
Среди методов, применяемых при решении задач второго вида, можно отдельно отметить латентно-семантический анализ (LSA) [9]. Этот метод применим и к задаче информационного поиска, и к ряду других задач. При решении задач классификации и кластеризации используется отдельная группа статистических методов, а именно методов снижения размерности. При решении задач кластеризации помимо снижения размерности часто также стоит задача сокращения количества рассматриваемых объектов, использующая схожие с задачей снижения размерности методы решения. Также можно отметить возможность применения статистической обработки текста к решению задач машинного перевода, что было реализовано корпорацией «Google» на основе N-грамм.
Следующим уровнем интерпретации текста является использование морфологического анализа. Обработку текста с использованием этого уровня интерпретации и всех последующих можно считать интеллектуальной, причём этот уровень интерпретации текста в отличие от предыдущего зависит от конкретного языка, на котором написан текст. В морфологическом анализе обычно решают две задачи: лемматизацию — приведение текущей формы слова к начальной и определение парадигматических категорий текущей формы слова.
Для решения этих задач традиционно применяется метод конечных автоматов, в формате которого описаны правила морфологии того или иного языка. Поскольку в естественных языках всегда существуют исключения из общих правил морфологии, требуется также использование словаря исключений. Но использование в словаре только исключений не всегда позволяет качественно лемматизировать слова, поскольку в отдельных случаях часть корня может совпадать с реляционной морфемой, и тогда при использовании только морфологических правил возникает ошибочная лемматизация, поэтому требуется использование как можно более объёмного словаря, содержащего не только исключения. Тем не менее, поскольку поиск в большом словаре требует много процессорного времени, в ряде систем, где важна производительность, применяется только набор правил и небольшой словарь исключений.
Можно также заметить, что использование даже большого словаря не всегда позволяет правильно лемматизировать слова, поскольку, во-первых, явление совпадения частей корня с реляционными морфемами может всё равно присутствовать в тех словах, которые не вошли в словарь, а во-вторых, некоторые формы слов, не вошедшие в словарь, могут совпадать с отдельными формами слов, вошедших в словарь, и если в таких случаях отдавать приоритет входящим в словарь словам, то тоже возникает неправильная лемматизация. Однозначного решения этой сложности в настоящее время не существует [10].
Отдельная задача разметки частей речи (POST), связана с тем фактом, что существуют омонимы и омоформы [11], т. е., с одной стороны одна и та же словоформа может быть какой-либо формой разных слов, а с другой стороны, в изменении одного слова по парадигматическим категориям нередко присутствуют повторы. Чаще всего эту задачу требуется решить, если выполняется обработка на следующих уровнях, поскольку в этом случае важно однозначно определить и начальную форму слова, и парадигматические категории текущей формы.
Для решения этой задачи существуют два основных подхода: использование набора правил, позволяющих исключить неправильные варианты, и использование статистических закономерностей. Второй подход в целом показывает большую эффективность, поскольку малый набор правил способен допускать ошибки, а использование большого количества правил начинает напоминать обработку на следующем уровне интерпретации, и в этом случае производительность становится низкой, в то время как статистические закономерности позволяют обеспечить высокую точность при малых вычислительных затратах. Можно также отметить, что в ряде систем эта задача отдельно не решается, но в этом случае производительность системы оказывается ниже [12].
Среди методов решения этой задачи, основанных на использовании статистических закономерностей, можно отметить скрытые марковские модели (НММ), метод наибольшей энтропии (ME), правила, основанные на преобразованиях (TBR) [13]. В таблице 1.2.1 приведена сравнительная характеристика нескольких подходов к реализации POST, основанных на различных методах.
Выбор метода первоначальной обработки текста и формы представления конечного результата
Как было сказано в предыдущем параграфе, критерий наличия достаточно завершённых и практически применимых и при этом общедоступных систем первоначальной обработки текста, т. е. преобразования естественно-языкового текста, представленного в виде последовательности символов кодовой таблицы, к этой модели обусловлен тем, что качество первоначальной обработки текста является важным. Поскольку поставленная задача решается для реальных текстов, в которых могут содержаться самые разные ошибки — орфографические, пунктуационные, грамматические и т. д., — важным показателем практической применимости системы первоначальной обработки текста является устойчивость этой системы к подобным ошибкам, т. е. способность выполнить обработку естественно-языкового текста в т. ч. при наличии ошибок и получить при этом достаточно качественные результаты, т. е. результаты, достаточно близкие к тому, как этот текст понял бы человек.
В виду вышесказанного, главным критерием выбора системы, выполняющей преобразования исходного естественно-языкового текста к выбранной модели, основанной на модели "смысл-текст" И. А. Мельчука, является качество выполняемого преобразования, и, в первую очередь, получение достаточно качественной модели естественно-языкового текста, содержащего ошибки. По этому критерию предлагается выбирать систему первоначальной обработки текста среди общедоступных систем, выполняющих преобразование исходного текста к выбранной модели "смысл-текст" И. А. Мельчука. Перечень известных систем, позволяющих выполнять первоначальную обработку текста для решения задач интеллектуальной обработки текста, присутствует в [90] и приведён в таблице 2.2.1.
Среди приведённых в таблице 2.2.1 систем, предлагается выбрать систему ДИАЛИНГ, разработанную А. В. Сокирко. В [66] отмечено, что эта система является доведённой до практического применения. Результаты первичного семантического анализа, выполняемого этой системой, соответствуют модели "смысл-текст" И. А. Мельчука [17] и содержат данные, требуемые для разработанной модели.
Система ДИАЛИНГ использует последовательное применение графематического, морфологического, синтаксического и первичного семантического анализа. Графематический анализатор принимает входной текст и приписывает символам этого текста графематические дескрипторы, отражающие расположение слов и границ между ними, других комплексов символов, не входящих в лексику русского языка и использующих не алфавитные символы (числовые комплексы и т. д.), расположение границ предложений и абзацев, знаков препинания и т. д. Деление текста на слова, предложения и абзацы использует различные правила, как невозможность пересечения их границ, использование алфавитных символов верхнего регистра в начале предложений и т. д. Приписываемые согласно имеющимся правилам графематические дескрипторы задокументированы и могут быть получены для выполнения строковых действий над текстом.
На морфологическом уровне выполняется лемматизация, т. е. определение начальной формы слова. Основой применяемого морфологического анализа является использование словарей, в качестве общего словаря морфологии русского языка используется словарь А. А. Зализняка. Наряду с ним используется ряд дополнительных словарей. Словарная информация дополняется информацией о парадигмах, позволяющей лемматизировать не входящие в словарь слова. Для этого в системе ДИАЛИНГ подбирается парадигма известного слова, имеющая наибольшее сходство, и, таким образом, выполняется лемматизация неизвестного слова.
Наряду с лемматизацией в ходе морфологического анализа выполняется определение части речи и граммем. При этом учитывается возможность наличия омонимов и омоформ. Для определения правильной начальной формы и парадигмы при их наличии используется система МАПОСТ, позволяющая на основе набора правил исключить неправильные морфологические интерпретации.
При синтаксическом анализе система ДИАЛИНГ использует сегментацию, корректируемую в процессе построения связей между словами. Выделение сегментов, границы которых непосредственные составляющие в связях внутри них не пересекают, позволяет повысить производительность синтаксического анализатора. В результате внутри сегмента для заданных номеров слов выбираются из возможных комбинаций связи между ними те, что соответствуют грамматическим правилам, и эти же правила позволяют определить необходимость объединения или разделения сегментов, границы которых первоначально определяются по знакам препинания и союзам.
С помощью правил первичного семантического анализа и необходимой словарной информации синтаксические связи преобразуются к семантическим. Набор семантических связей является документированным, что позволяет использовать его для дальнейших действий. В ходе первичного семантического анализа в узлах также формируются лексемы, состоящие из нескольких слов.
Использование DLL для работы описанных модулей системы ДИАЛИНГ позволяет осуществлять их вызов с разных платформ, на которых ведётся разработка.
Разработка алгоритма иерархической кластеризации и формирования оглавления текста
После получения агрегирующих характеристик для единиц текста необходимо выполнить иерархическую кластеризацию этих единиц текста, определив место той или иной единицы текста в определённом разделе сформированной структуры текста. Специфика этой задачи состоит в том, что формируемая структура текста предусматривает переменное количество единиц подуровня какого-либо уровня, в то время как при иерархической кластеризации предполагается объединение в кластеры фиксированного числа объектов, обычно по два. Поэтому эта задача включает в себя две подзадачи:
иерархическая кластеризация единиц текста по две на каждом уровне объединения;
перегруппировка уровней объединения с получением переменного количества единиц подуровня.
В предыдущей главе был определён выбор агломеративного алгоритма и добавления на каждом уровне по одному новому элементу. Как было отмечено, в этом случае необходимо после получения нового кластера определять расстояние до его центра от каждого из других кластеров по формуле: drs = pdps + aqdqs+fidpq +y\dps-dq\ (3.2.1).
Как было сказано в предыдущей главе, необходимо определить значения ар, aq, и у. Также помимо вычисления расстояний до новых центров необходимо преобразование структуры данных из исходного линейного списка элементов в иерархическую форму представления.
Таким образом, можно выделить две подзадачи:
выбор коэффициентов ар, aq, р и у для вычисления расстояний до новых центров;
разработка алгоритма преобразования линейного списка в иерархическую структуру.
Выбор коэффициентов ар, aq, р и у для вычисления расстояний до новых центров обычно выполняется из некоторого стандартного набора значений, приведённых в таблице 3. 2. 1.
По результатам экспериментальной проверки вариант расстояния между ближайшими соседями — ближайшими объектами кластеров с ар = о,5, aq = о,5, р = о, у = о,5 показывает приемлемые результаты. Другие значения можно рассматривать в качестве опционального варианта настроек при использовании разрабатываемой системы.
Алгоритм преобразования линейного списка в иерархическую структуру схематически представлен на рисунке 3. 2. 1.
После того, как была выполнена иерархическая кластеризация единиц текста по их агрегирующим характеристикам с объединением на каждом уровне фиксированного числа элементов, требуется изменить размещение единиц текста по уровням, получив на каждом уровне иерархии переменное количество элементов. В предыдущей главе в качестве конечного варианта иерархии было предложено использовать фиксировано три уровня объединения, разделяемые двумя граничными уровнями. Для выполнения указанного объединения с фиксированным количеством уровней требуется:
определить меру расстояния между первоначальными уровнями объединения при иерархической кластеризации;
определить значения граничных уровней в единицах выбранной меры расстояния;
разработать алгоритм перегруппировки.
Мера расстояния между первоначальными уровнями объединения при иерархической кластеризации может использовать в качестве основы те величины, что были получены в процессе кластеризации. Поскольку выбранный агломеративный алгоритм иерархической кластеризации основывается на выборе объектов с наименьшим расстоянием и вычислении расстояний до нового центра, именно эти расстояния и могут послужить основой меры расстояния между первоначальными уровнями объединения при иерархической кластеризации. Для этой цели предлагается использовать значения расстояний между центром, к которому выполняется присоединение, и присоединяемым объектом drs. Но, поскольку эти значения основываются на величинах агрегирующих характеристик произвольного масштаба, при использовании значений drs непосредственно в качестве меры расстояния между первоначальными уровнями объединения при иерархической кластеризации возникнет сложность с определением значения граничных уровней в единицах выбранной меры расстояния из-за имеющейся неопределённости этих единиц. В виду этого предлагается нормировать значения drs, используя в качестве меры расстояния между первоначальными уровнями объединения при иерархической кластеризации не сами значения d , а их отношения к сумме drs по всем г и s: d=4 - С3-2-2) а IX V(r,5) В этом случае значение меры расстояния для определения граничных уровней будет равно сумме всех предыдущих d;: h,=± j (3-2-3) Полученные величины hj будут меняться в диапазоне [0; 1].
Значения граничных уровней в единицах выбранной меры расстояния, соответственно, будут находиться в указанном диапазоне [0; 1], и эти значения имеет смысл подобрать экспериментально. Значения граничных уровней в единицах выбранной меры расстояния, равные 0,3 и 0,7 для двух уровней соответственно показывают приемлемые результаты перегруппировки уровней объединения с получением переменного количества единиц подуровня.
Сам алгоритм перегруппировки сводится к рекурсивному вызову подпрограммы перегруппировки уровня, первоначально вызываемой с параметром верхнего объекта в иерархии, схематически представленной на рисунке 3. 2. 2.
Экспериментальное исследование метода синтеза заголовков выделенных разделов текста
Особенностью экспериментального исследования метода синтеза заголовков выделенных разделов текста, как и экспериментального исследования иерархической кластеризации и формирования оглавления для текста, является в первую очередь отсутствие возможности прямого количественного выражения достигнутого результата, т. е. результат также поддаётся лишь качественной оценке. Но кроме этого, в отличие от экспериментального исследования иерархической кластеризации и формирования оглавления для текста, при экспериментальном исследовании метода синтеза заголовков выделенных разделов текста отсутствует возможность оценивать результат путём сравнения с исходной структурой текста, поскольку сформированное с помощью разработанных алгоритмов оглавление в значительной степени отличается от оглавления в исходной структуре текста, ввиду чего наиболее точно соответствующие сформированному оглавлению заголовки будут также в значительной степени отличаться от заголовков исходного текста. Поэтому для оценки результата предлагается использовать качественную оценку соответствия заголовков основному содержанию выделенных разделов, рассматривая при этом так же, как и при экспериментальном исследовании методов решения предыдущих подзадач, время решения задачи формирования структуры изначально неструктурированного естественно-языкового текста.
Как и в случае экспериментального исследования иерархической кластеризации и формирования оглавления для текста, на результат работы метода синтеза заголовков выделенных разделов текста наибольшее влияние оказывают и параметры, используемые разработанными алгоритмами синтеза заголовков выделенных разделов текста, и основные параметры, влияющие на качество агрегирующих характеристик, а именно количество агрегирующих характеристик и значение пороговой частоты понятий в тексте. При экспериментальном исследовании влияния количества агрегирующих характеристик и пороговой частоты понятий в тексте на качество решения задачи синтеза заголовков выделенных разделов текста, как и при экспериментальном исследовании влияния количества агрегирующих характеристик и пороговой частоты понятий в тексте на качество решения задачи иерархической кластеризации и формирования оглавления для текста предлагается рассмотреть ограниченное количество сочетаний этих параметров, опираясь на закономерности, полученные в ходе экспериментального исследования метода получения агрегирующих характеристик. При этом, поскольку основное экспериментальное исследование метода синтеза заголовков выделенных разделов текста будет выполняться при фиксированных значениях количества агрегирующих характеристик и пороговой частоты понятий в тексте, предлагается именно в первой части экспериментального исследования метода синтеза заголовков выделенных разделов текста подобрать оптимальные значения этих параметров, проводя дальнейшее экспериментальное исследование при подобранных их оптимальных значениях. При этом, разумеется, подобранные оптимальные значения количества агрегирующих характеристик и пороговой частоты понятий в тексте должны согласовываться со значениями, выбранными как оптимальные, при экспериментальном исследовании метода получения агрегирующих характеристик и других подзадач задачи формирования структуры изначально неструктурированного естественно-языкового текста.
Результаты экспериментального исследования влияния количества агрегирующих характеристик и пороговой частоты понятий в тексте на качество решения задачи синтеза заголовков выделенных разделов при учёте времени полного выполнения задачи формирования структуры изначально неструктурированного естественно-языкового текста приведены в таблице 4.4.1.
Как видно из результатов экспериментального исследования методов иерархической кластеризации и формирования оглавления для текста и синтеза заголовков выделенных разделов текста, большее значение пороговой частоты понятий в тексте, несмотря на более высокое визуально оцениваемое качество получаемых агрегирующих характеристик, снижает качество решения задачи иерархической кластеризации и формирования оглавления для текста и особенно снижает качество решения задачи синтеза заголовков выделенных разделов текста. Тем не менее, при выбранном при экспериментальном исследовании метода получения агрегирующих характеристик значений пороговой частоты понятий в тексте, определяемом как начинающееся от 1 для самых коротких текстов и с увеличением на 1 для каждых 4000 символов, обеспечивает наивысшее качество из полученных при экспериментальном исследовании метода синтеза заголовков выделенных разделов текста результатов. Но в отличие от результатов экспериментального исследования методов получения агрегирующих характеристик и иерархической кластеризации и формирования оглавления для текста, наивысшие результаты для метода синтеза заголовков выделенных разделов текста получены при 10 агрегирующих характеристиках. Исходя из того, что по результатам экспериментального исследования методов получения агрегирующих характеристик и иерархической кластеризации и формирования оглавления для текста при 10 агрегирующих характеристиках заметного снижения качества не наблюдается, поэтому оптимальным можно считать 10 агрегирующих характеристик, и, именно при этом значении их количества, предлагается выполнить вторую часть экспериментального исследования метода синтеза заголовков выделенных разделов текста, используя значение пороговой частоты понятий в тексте равное 5 для текста длиной 17448 символов.
Основными параметрами, используемые разработанными алгоритмами синтеза заголовков выделенных разделов текста, являются количество понятий, выбираемых как наиболее релевантные выделенному разделу текста, и пороговое значение количества наиболее близко распложенных в тексте групп выбранных понятий, используемых для синтеза заголовка. При этом, исходя из принципа работы алгоритма, количество понятий, выбираемых как наиболее релевантные выделенному разделу текста, не должно превышать количество понятий, частота которых в тексте превышает пороговую, а пороговое значение количества наиболее близко распложенных в тексте групп выбранных понятий не должно превышать квадрата количества понятий, выбираемых как наиболее релевантные выделенному разделу текста. Результаты второй части экспериментального- исследования метода синтеза заголовков выделенных разделов текста приведены в таблице 4.4.2.
Как видно из результатов второй части экспериментального исследования метода синтеза заголовков выделенных разделов текста, наилучшие результаты достигаются при количестве понятий, выбираемых как наиболее релевантные выделенному разделу текста, значительно превышающем квадратный корень из порогового значения количества наиболее близко распложенных в тексте групп выбранных понятий, используемых для синтеза заголовка. В то же время, увеличение количества понятий, выбираемых как наиболее релевантные выделенному разделу текста, при сохранении пропорций с квадратным корнем из порогового значения количества наиболее близко распложенных в тексте групп выбранных понятий, используемых для синтеза заголовка, не оказывает существенного влияния на качество результатов, и лишь в незначительной степени при определённых пороговых значениях количества наиболее близко распложенных в тексте групп выбранных понятий, используемых для синтеза заголовка, позволяет повысить производительность. Ввиду этого, для обеспечения значительной разницы количества понятий, выбираемых как наиболее релевантные выделенному разделу текста, и квадратного корня из порогового значения количества наиболее близко распложенных в тексте групп выбранных понятий, используемых для синтеза заголовка, целесообразно использовать пороговое значение количества наиболее близко распложенных в тексте групп выбранных понятий не менее 3-х, а пороговое значение количества наиболее близко распложенных в тексте групп выбранных понятий, используемых для синтеза заголовка, приблизительно равным или чуть меньшим, чем пороговое значение количества наиболее близко распложенных в тексте групп выбранных понятий.
Таким образом, наилучший результат синтеза заголовков выделенных разделов текста достигается при использовании 10 агрегирующих характеристик и пороговой частоты понятий в тексте от 1 для самых коротких текстов с увеличением на 1 для каждых 4000 символов, при пороговом значении количества наиболее близко распложенных в тексте групп выбранных понятий, большим, либо равным 3 и равным ему или меньшем пороговом значении количества наиболее близко распложенных в тексте групп выбранных понятий, используемых для синтеза заголовка.
![Научное обоснование и разработка модели прогнозирования исходов болезней системы кровообращения на уровне популяции на основании оценки индивидуального риска [Электронный ресурс]](/i/i/4472/168245.png "Научное обоснование и разработка модели прогнозирования исходов болезней системы кровообращения на уровне популяции на основании оценки индивидуального риска [Электронный ресурс] Леонов Николай Вячеславович")
