Содержание к диссертации
Введение
Глава I. Общая характеристика проблемы тематического ранжирования, на основе автоматически построенного электронного каталога текстовых документов 18
1.1 Предлагаемая математическая модель поиска по ключевым словам с тематическим ранжированием 18
1.2 Предлагаемая математическая модель автоматического построения электронного каталога 20
1.3 Постановка задачи текстовой кластеризации 22
1.4 Обзор существующих алгоритмов текстовой кластеризации 24
1.4.1 Алгоритмы кластеризации, использующие критерий квадратичной ошибки 25
1.4.2 Алгоритмы основанные на технологии нейронных сетей 26
1.4.3 Алгоритмы кластеризации, основанные на концепции плотности 28
1.4.4 Алгоритмы, основанные на теории графов 29
1.4.5 Иерархические алгоритмы, строящие бинарное дерево 30
1.4.6 Алгоритм кластеризации основанный на суффиксном дереве 32
1.4.7 Методы нечеткой кластеризации 33
1.5 Оценка качества кластеризации текстовой коллекции 39
1.6 Оценка качества ранжирования поисковых результатов 41
1.7 Постановка задачи формирования информационных образов текстовых документов 42
1.8 Морфологический анализ 45
1.9 Обзор методов статического анализа формирования информационных образов документов 46
1.9.1 Критерий порога частоты встречаемости слова в документах коллекции 47
1.9.2 Критерий информационного веса слова в рубрике 48
1.9.3 Критерий прироста информации 48
1.10 Оценка важности терминов по формуле TF-IDF 49
Выводы по главе 1 50
Глава II Разработка математической модели поиска по ключевым словам с тематическим ранжированием на основании автоматического построения электронного каталога текстовых документов 53
2.1 Подготовка информационных образов текстовых документов 53
2.2 Построение инвертированного индекса 55
2.3 Иерархическая кластеризация по областям текстовых документов 56
2.3.1 Инициализация алгоритма иерархической кластеризации по областям. 60
2.3.2 Этап обработки входящего потока документов 60
2.3.3 Критерий качества уровня дерева 62
2.3.4 Операция разделения области 64
2.3.5 Операция интеграции подобластей 66
2.3.6 Анализ вычислительной сложности алгоритма иерархической кластеризации по областям 67
2.4 Преобразование иерархии кластеров в иерархию электронного каталога 68
2.5 Построение вербального описания иерархического каталога 68
2.6 Описание выбранной технологии распределенного программирования MapReduce 71
2.7 Параллельная реализация построения информационных образов текстовых документов 74
2.8 Параллельная реализация алгоритма иерархической кластеризации по областям текстовых документов 76
2.9 Поиск по ключевым словам с тематическим ранжированием, на основе электронного каталога 78
Выводы по главе II 81
Глава III. Программная реализация системы поиска с тематическим ранжированием, на основе автоматически построенного электронного каталога 82
3.1 Структура программного комплекса поисковой системы с тематическим ранжированием, на основе автоматически построенного электронного каталога 82
3.1.1 Компонент построения иерархической структуры каталога 84
3.1.2 Компонент построения образов текстовых документов 85
3.1.3 Компонент поиска с тематическим ранжированием результатов... 86
3.1.4 Компонент алгоритмов параллельного построения электронного каталога 88
3.2 Описание тестовых текстовых коллекций 89
3.3 Выбор параметров алгоритма иерархической кластеризации по областям 92
3.4 Результаты испытаний предлагаемой математической модели автоматического построения электронного каталога 93
3.4.1 Результаты испытаний последовательных версий разработанных алгоритмов 93
3.4.2 Исследование предлагаемого способа формирования описания кластеров 96
3.4.3 Результаты испытаний параллельных версий разработанных алгоритмов 98
3.5 Результаты испытаний качества работы предлагаемого алгоритма тематического ранжирования 101
Выводы по главе III 104
Выводы 105
Список литературы 107
- Постановка задачи формирования информационных образов текстовых документов
- Параллельная реализация построения информационных образов текстовых документов
- Поиск по ключевым словам с тематическим ранжированием, на основе электронного каталога
- Результаты испытаний последовательных версий разработанных алгоритмов
Введение к работе
В настоящее время в различных хранилищах знаний (электронных и традиционных) накоплены огромные массивы информации. При этом по причине больших объемов информации, ее слабой структурированности, представления в неэлектронном виде, получение актуальной и полной информации по конкретной теме является достаточно сложным, а также бесполезной становится, большая часть накопленных информационных ресурсов из-за их необозримости. Можно отметить, что решение конкретной научной задачи требует высоких трудозатрат по поиску и анализу информации по теме. Поэтому, в связис выше сказанным, возникает задача эффективного структурирования, хранения, обработки и поиска в информационных массивах.
Традиционными подходами к решению данной задачи являются: классификационный поиск и поиск по ключевым словам. К классификационному поиску относится поиск с использованием различных тематических классификаторов, рубрикаторов, электронных каталогов, которые позволяют искать (автоматически или вручную) документы в небольшом подмножестве исходной коллекции документов по интересующей' пользователя тематике. Рубрикатор (электронный каталог) обычно представляет собой множество рубрик, объединенных в иерархию. К каждой рубрике приписываются соответствующие ее тематике документы. В^ настоящее время распространены два вида рубрикации. -ручной и автоматизированный. При ручном процессе рубрикации при добавлении в каталог нового документа его нужно вручную проанализировать и определить, к каким рубрикам каталога он относится, после этого документ становится доступным для поиска. Среди традиционных ручных методов каталогизации можно выделить универсальные библиотечные классификаторы, например, УДК [1], ГРНТИ[2], ББК[3]. Данные классификаторы имеют фиксированную структуру и зачастую не поддерживают высоких темпов развития различных областей знаний в науке и технике, а также требуют высоких временных затрат на адаптацию классификаторов, и классификацию по ним документов.
Существуют автоматизированные системы поддержки рубрикатора, в которых для каждой рубрики хранится множество признаков, используя которые программа определяет, какой рубрике соответствует анализируемый документ. Можно выделить два существующих класса поддержки автоматизированных систем поддержки каталогов: а) методы, основанные на знаниях, когда список признаков для каждой рубрики составляется экспертом; б) методы, основанные на алгоритмах машинного обучения, которые автоматически извлекают признаки документов на основании подготовленного экспертами обучающего множества (заранее подготовленного множества отрубрицированных документов). Разработками в данной сфере занимались такие исследователи как М. С. Агеев [4], И. С. Некрестьянов [5], В. И. Шабанов [6], Т. Joachims [7], D. D. Lewis [8], Н. Schutze [9], F. Sebastiani [10], S. Т. Dumais [11], P. Bennett [12] и ряд других. Основным недостатком существующих автоматизированных систем является их статичность и невозможность автоматически, без участия эксперта перестроить сформированный ранее каталог. Для примера, трудоёмкость описания рубрик для первого класса методов составляет до 8 человеко-часов^ на одну рубрику [13].
При втором способе поиска пользователь вводит ключевые слова, отражающие его информационную-потребность. Приэтом результатом поиска, как правило, является достаточно-большое количество документов, среди которых пользователь должен выбрать нужные. Отметим, что одно и то же ключевое слово может соответствовать разным понятиям, поэтому результат поиска заведомо избыточен. Кроме этого, пользователь может ввести ключевые слова не соответствующие интересующему его документу. Для^ улучшения качества выдаваемых поисковых результатов не так давно появилось новое направление в области информационного поиска по>ключевым словам — поиск жьключевым словам с использованием категориальной- информации подготовленных вручную электронных каталогов. Среди наиболее известных работ можно выделить работы P. Bennett [14], S. Т. Dumais [15], R. White [15], М. Daoud [16], В. Xiang [17]. В данных работах использовался созданный и поддерживаемый группой экспертов-волонтеров по всему миру каталог ODP (Open Directory Project) [18]. Исследователям удалось повысить качество выдаваемых поисковых результатов за счет их тематического ранжирования, когда наиболее важные по тематике документы помещаются алгоритмом ранжирования выше в списке результатов. Однако, исследователи применяли тематическое ранжирование с заранее предопределенным набором тематических групп, а также использовали помощь экспертов при подготовке обучающего множества алгоритма ранжирования, поэтому для применения данного подхода на конкретной области знаний требуется подготовка соответствующего классификатора. Как было замечено, подготовка нового или адаптация существующего классификатора является достаточно затратной, поэтому требуется применение новых, более эффективных методов подготовки электронных тематических каталогов.
Среди известных подходов к решению задачи автоматического построения иерархического каталога можно выделить работы О.В. Песковой [19], а также Tao Li и Shenghuo Zhu [20], D.R. Cutting [63]. В данных работах использовались алгомеративные (построение иерархии снизу вверх) алгоритмы текстовой кластеризации построения иерархической структуры каталога. Однако в данных работах не предполагалось использование автоматически сформированного каталога в задаче тематического ранжирования. Предложенные в данных работах методы автоматического построения^ электронного каталога обладают высокой вычислительной трудоемкостью, что является существенным минусом при учете объемов накопленных текстовых данных. Также можно отметить, что в настоящее время уже невозможно иметь эффективную инфраструктуру без использования распределенных вычислений. Предложенные в упомянутых работах подходы не предлагают распределенных программных решений. Поэтому требуется разработать эффективные методы текстовой кластеризации, которые смогли бы автоматически строить электронный каталог, и позволяли распределенную поддержку больших коллекций текстовых документов.
Таким образом, актуальной является задача создания новых математических моделей информационного поиска по ключевым словам с тематическим ранжированием результатов поиска, на основе автоматически построенного с использованием методов автоматической каталогизации (способных без участия человека строить электронные каталоги заданных коллекций текстовых документов) электронного каталога.
Цель работы
Цель работы заключается в создании математических моделей и методов поиска по ключевым словам с тематическим ранжированием, на основе электронного каталога заданных коллекций текстовых документов (автоматически построенного с использованием разработанных алгоритмов текстовой кластеризации).
Для достижения данной цели были поставлены и решены следующие задачи: проведены исследования подходов к извлечению текстовых признаков документов, и обзор существующих алгоритмов текстовой кластеризации; разработаны последовательные и параллельные варианты предложенного метода иерархической текстовой кластеризации, учитывающие недостатки существующих подходов. разработаны последовательные и параллельные варианты алгоритмов извлечения текстовых признаков; разработана математическая модель поиска с тематическим ранжированием, на основе автоматически построенного электронного каталога; разработана модель автоматического построения электронного каталога, на основе предложенного в работе алгоритма иерархической кластеризации по областям; - разработана программная система поиска (поисковая система) на основе ма тематической модели поиска по ключевым словам с тематическим ранжирова нием, на основе автоматически построенного электронного каталога текстовых документов; - проведено исследование эффективности и качества работы предложенных математических моделей, и алгоритмов с использованием разработанной программной системы.
Методы исследований, достоверность и обоснованность результатов.
Для решения поставленных задач были использованы методы математического моделирования, системного анализа, методы математической статистики, кластерного анализа. Эффективность разработанных алгоритмов оценивалась с помощью математических методов анализа алгоритмов. В разработке программного обеспечения применялись методы объектно-ориентированного программирования с использованием инструментов интегрированной среды разработки Eclipse [21]. Для разработки параллельных версий алгоритма использовались программные средства платформы для распределенных вычислений Apache Hadoop [22].
Достоверность и обоснованность результатов подтверждается корректностью разработанных математических моделей, согласованностью данных экспериментов и научных выводов, сделанных в работе, результатами апробации алгоритмов и разработанной программной системы.
Научная новизна
В работе предложена новая математическая модель поиска по ключевым' словам с тематическим ранжированием результатов поиска, на основе автоматически построенного электронного каталога заданных коллекций текстовых документов (без ограничения на тематику и размер исходной текстовой коллекции). В рамках реализации этой модели разработаны:
Новый метод тематического ранжирования, основанный на автоматически построенном электронном каталоге.
Новую математическую модель автоматического построения электронного каталога, основанную на предложенном в работе методе текстовой кластеризации - иерархическая кластеризации по областям текстовых документов, учитывающем недостатки существующих методов иерархической текстовой кластеризации (разработаны последовательные и параллельные варианты предложенного метода кластеризации). Методы извлечения текстовых признаков (разработаны последовательные и параллельные варианты предложенных методов), используемые для построения индекса текстовой коллекции, необходимого во время кластеризации и поиска.
Практическая значимость работы
Предложенные в работе новая математическая модель информационного поиска по ключевым словам с тематическим ранжированием, математическая модель автоматического построения электронного каталога, и алгоритмы тематического ранжирования могут быть использованы в качестве поисковой системы по специализированным коллекциям научной литературы, и электронным хранилищам библиотек.
Внедрение
Произведена апробация и внедрение предложенных в данной работе математических моделей и методов поиска по ключевым словам с тематическим ранжированием, на основе автоматически' построенного электронного каталога, в качестве поисковой системы с тематическим ранжированием по статьям журнала "Вестник Нижегородского государственного университета им. Н.И. Лобачевского" () на интернет-портале Нижегородского государственного университета им. Н.И. Лобачевского.
Апробация результатов
Результаты диссертации докладывались и обсуждались на всероссийской конференции «Технологии Microsoft в теории и практике программирования 2009» (ДНовгород, 2009 г.) [23], международной научно-практической конференции по графическим информационным технологиям и системам «КО-ГРАФ-2009» (Н.Новгород,2009), 9-й международной конференции "Высокопроизводительные параллельные вычисления на кластерных системах" (Владимир, ВлГУ, 2009) [24], всероссийской- научной школе для молодежи "Управление информационными ресурсами образовательных, научных и производственных организаций" (Магнитогорск, Магнитогорский государственный университет, 2009) [25], всероссийской конференции «Технологии Microsoft в теории и практике программирования'2010» (Н.Новгород, 2010) [26], международном коллоквиуме SYRCoSE (Н.Новгород, 2010) [27], на семинаре кафедры математического обеспечения-ЭВМ факультета ВМК ННГУ.
Основные положения, выносимые на защиту
Новая математическая модель информационного поиска по ключевым сло- вам с тематическим ранжированием, основанная на использовании автоматически построенного электронного каталога.
Новая математическая' модель автоматического построения электронного каталога текстовых документов без. ограничения на тематику и размер исходной^текстовой коллекции:
Новый метод текстовой* кластеризации* - иерархическая кластеризация по областям текстовых документов, учитывающий недостатки существующих алгоритмов иерархической текстовой кластеризации. Последовательные и параллельные версии предложенного алгоритма.
Архитектура и функциональные возможности разработанной программной системы.
Результаты проведенных вычислительных экспериментов, подтверждаю- щих работоспособность предлагаемого подхода к автоматическому построению электронного каталога. Публикации и личный вклад автора.
Основное содержание диссертации нашло отражение в 6 опубликован- ных научных работах, в том числе 1 статья в рецензируемом издании, рекомендованном ВАК РФ. Также, принята в печать научная статья "Распределенная реализация построения индекса поискового каталога" в №1 (2011 г.) журнала Вестник ЫНГУ им. Н.И. Лобачевского, входящего в список ВАК. Результаты совместных научных работ [23,24,27,28], использованные в диссертационной работе, принадлежат лично автору диссертации.
Структура и объем работы*
Работа состоит из введения, трех глав, заключения, списка литературы. Общий объем работы составляет 115 страниц. Список литературы составляет 68 наименований. Основные результаты излагаются в главах 2 и 3.
Краткое содержание работы
Во введении обосновывается актуальность задачи создания новых моделей информационного поиска по ключевым словам с тематическим ранжированием результатов поиска, на основе автоматически построенного электронного каталога, сформулированы цели и задачи исследования. Приводится краткий обзор содержания диссертации.
В первой главе производится описание предлагаемой математической модели поиска по ключевым словам с тематическим ранжированием (раздел 1.1), которое основано на использовании автоматически построенного электронного каталога коллекции текстовых^ документов. В части 1.2 первой главы производится описание предлагаемой математической модели автоматического построения электронного каталога. Построение электронного каталога производится автоматически с использованием предложенного в работе алгоритма иерархической кластеризации по областям текстовых документов.
В частях 1.3-1.4 первой главы приводится постановка задачи текстовой кластеризации, и производится обзор и анализ существующих алгоритмов текстовой кластеризации. В части 1.5-1.6 первой главы производится обзор общепринятых методов оценки результатов текстовой кластеризации и методов оценки полученного ранжирования поисковых результатов. В частях 1.7-1.10 первой главы диссертации производится постановка задачи формирования образов текстовых документов, производится обзор существующих методов формирования информационных образов текстовых документов, их анализ и выбор оптимального подхода. Во второй главе приводится описание разработанных автором алгоритмов построения образов текстовых документов, алгоритмов автоматического построения электронного каталога, а также, алгоритмов тематического ранжирования, основанных на автоматически построенном электронном каталоге.
Функционирование предлагаемой математической модели поиска по ключевым словам с тематическим ранжированием можно разбить на следующие этапы:
Индексирование текстовой коллекции, включающее: подготовку информационных образов текстовых документов; построение инвертированного индекса текстовой коллекции(в индексе каждому слову (списку слов) будет соответствовать некоторый список документов, его содержащих). автоматическое формирование электронного каталога заданной» тек- стовой коллекции: иерархическая кластеризация по областям текстовых документов; преобразование иерархии кластеров в иерархию электронного каталога; автоматическое формирование названий и описания для сформированных кластеров автоматически построенного электронного каталога.
Поиск и тематическое ранжирование документов с использованием по- строенного индекса текстовой коллекции.
Для применения предложенных последовательных алгоритмов формирования иерархического каталога больших коллекций текстовых документов были разработаны их параллельные версии:
В части 2.7 второй главы данной работы представлено описание рас пределенной версии алгоритма подготовки образов текстовых документов.
В части 2.8 второй главы кандидатской диссертации представлена реа лизация параллельной версии алгоритма иерархической кластеризации по областям текстовых документов, которая позволяет масштабировать реше ние задачи на необходимое количество вычислительных узлов.
В части 2.9 второй главы диссертации представлено описание алгоритмов тематического ранжирования, основанных на автоматически построенном электронном каталоге.
В третьей главе приводится описание архитектуры разработанной программной системы, реализующей предлагаемые математические модели и методы поиска по ключевым словам с тематическим ранжированием,, на основе электронного каталога заданных коллекций-текстовых документов, автоматически построенного с использованием предлагаемого в работе алгоритма текстовой кластеризации. Приведено описание тестовых текстовых коллекций и результаты испытаний,предлагаемого метода автоматического построения электронного каталога^ исследование качества тематического ранжирования результатов поиска по ключевым словам.
Программная поисковая система по ключевым словам с тематическим ранжированием, на основе автоматически построенного- электронного каталога, разработана с использованием технологий объектно-ориентированного анализа с использованием инструментов интегрированной среды разработки Eclipse и платформы для распределенных вычислений Apache Hadoop:
Разработанная программная система- состоит из четырех основных компонент:
Компонент построения иерархической структуры каталога;
Компонент поиска с тематическим ранжированием результатов;
Компонент построения информационных образов документов;
Компонент алгоритмов параллельного построения электронного каталога.
По; итогам проведенных исследований; предлагаемый* способ автоматиче ского формирования электронного каталога показал результаты^ превосхо дящие по качеству и< скорости существующие подходы. Проведенное экс периментальное исследование предложенного-в работе алгоритма тексто вой* кластеризации, на> котором основано построение иерархии электронно го каталога, на* различных; коллекциях реальных текстовых данных показа ло' высокое качество кластеризации; текстов; (лучший результат по сравнению с 3 другими^ алгоритмами, способными* строить иерархические структуры);.
Результаты апробации представленных в настоящей работе параллельных версий*алгоритмов индексирования:и*иерархической?кластеризации жпобластям-показали линейное ускорение в зависимости; от количества задействованных вычислительныхузлов; Таким?образом^ в;результате;применения; используемой в настоящей: работе парадигмы, распределенных вычислений^ MapReduce удалось существенно»сократить время построения;индекса коллекции текстовых документов и проведения^ кластеризации текстовых данных.
Используя введенный критерий? оценки'качества ранжирования (NDGG@10? [30]), были проведены численные эксперименты по измерению качества работы предлагаемых алгоритмов ранжирования на коллекции научных статей журнала "Вестник Нижегородского государственного университета им. Н.И. Лобачевского", которые показали превосходство предлагаемого алгоритма ранжирования по сравнению с базовым алгоритмом Okapi ВМ25 [31].
По итогам проведенных исследований предлагаемый способ тематического ранжирования, на основе автоматически построенного электронного каталога, показал результаты, превосходящие по качеству и скорости существующие подходы. Таким образом, предложенная математическая модель поиска с тематическим ранжированием, на основе автоматически построенного электронного каталога удовлетворяет всем требованиям, вытекающим из цели исследования.
Постановка задачи формирования информационных образов текстовых документов
При подготовке данных для алгоритма кластеризации текстовые документы на некотором естественном языке проходят процедуру индексирования, результатом которой является формирование информационно-поискового образа документа. Далее система кластеризации работает не с самим документом, а с его поисковым образом. Процесс формирования поискового образа документа заключается в автоматической обработке документов и выявлении признаков, которые в дальнейшем будут использоваться для «представления» их содержания. С обработкой информации на естественном языке также связан ряд проблем, основные из которых перечислены ниже: Синонимия. Одно и то же понятие может быть выражено различны ми словами. Устойчивые сочетания слов. Словосочетания могут иметь смысл отличный от смысла, который имеют слова по отдельности. Омонимия и явления «смежные с омонимией». Грамматические омо нимы - разные по значению слова, но совпадающие по написанию в отдельных грамматических формах. Это могут быть слова одной или разных частей речи. Лексические омонимы - слова одной части речи, одинаковые по звучанию и написанию, но разные по лексическому значению. Морфологические вариации. Во многих естественных языках слова имеют несколько морфологических форм, различающихся по написанию. Например, в русском языке одно и то же слово может иметь различные окончания и формы. В настоящее время выделяют два различных подхода к построению поискового образа документа [51]: 1) Статистический подход - в текстовой коллекции анализируется частота встречаемости отдельных слов или словосочетаний. В качестве образа документа формируется многомерный вектор слов. При этом использу ютсяразличные методики отборанаиболее важных слов. 2) Лингвистический подход, когда для обработки текста используется ав томатические методы: Целью морфологического анализа является определение морфологических характеристик слова и его основной словоформы. Особенности анализа сильно зависят от выбранного естественного языка. Морфологический анализ важен для таких флективных языков, как русский язык, поскольку позволяет привести обрабатываемые признаки к некоторой нормальной форме. На этапе графематического анализа производится выделение элементов структуры текста: параграфов, абзацев, предложений, отдельных слов. Целью синтаксического анализа является определение синтаксической зависимости слов в предложении. В связи с присутствием в русском языке большого количества синтаксически омонимичных конструкций, наличием тесной связи между семантикой и синтаксисом, процедура автоматизированного синтаксического анализа текста является трудоемкой. Сложность алгоритма,увеличивается экспоненциально при увеличении количества слов в предложении и числа используемых правил. Как показали эксперименты, проведенные в работе [52], наилучших результатов потенциально можно добиться при комбинации статистического и лингвистического подходов. Однако из-за высокой вычислительной трудоемкости методов синтаксического анализа, они не находят широкого применения в существующих коммерческих системах. В настоящее время в большинстве коммерческих систем используется статистический подход в сочетании с морфологическим анализом [19]. Таким образом, наиболее целесообразным считается совместное применение комбинации методов статистического и морфологического анализа. Процесс формирования информационного образа документа, при использовании комбинации средств статистического и морфологического анализа, можно разделить на три этапа: 1) Преобразования текстов документов заданной коллекции с помощью средств морфологического анализа к нормальной форме. Нормальной формой текста мы будем называть текст, каждое слово которого приведено средствами морфологического анализа к некоторой начальной форме, называемой "основа слова". 2) Формирование статических данных встречаемости различных слов в преобразованной на первом- шаге текстовой- коллекции. Формирование пространства признаков документов заданной коллекции. 3) Выделение наиболее значимых слов и словосочетаний каждого, документа. Понижение размерности пространства признаков документов. 1.8 Морфологический анализ
Для того чтобы разрешить проблему морфологических вариаций, различные морфологические формы слова отображаются в одну координату пространства признаков, и каждое слово исходного текста приводится к своей нормализованной форме. Рассматривается понятие основы слова — это часть слова, которая предшествует окончанию и выражает лексическое значение данного слова. Например, для русского языка в изменяемых (склоняемых или спрягаемых) словах основа определяется как часть слова без окончания и формообразующих суффиксов. Чтобы выделить основу слова, необходимо отбросить окончание и формообразующие суффиксы. Одним из распространенных методов выделения основы слова является процедура, стемминга (нормализации слов), которая заключается в отсечении окончания. слова. Стемминг позволяет сократить количество слов документа представляя документ в виде вектора основ слов. Портер (1980) [47], и Левине (1968) [48] предложили алгоритмы стемминга которые достаточно часто используются. В этих алгоритмах используются независимые от языка эвристические правила определения основы слова.
При проведении, морфологического анализа возникает проблема многозначности для некоторых слов, а именно одному и тому же слову, может. соответствовать несколько различных начальных форм. Например, для слова "суда" можно сгенерировать две начальные формы: "суд" и "судно". В таких случаях имеет смысл добавлять в, вектор описания документа обе начальные формы слова.
Параллельная реализация построения информационных образов текстовых документов
Отметим, что значительные вычислительные затраты требуются на этапе подготовки исходных данных для алгоритма кластеризации, когда каждый документ представляется в виде вектора ключевых слов (индексирование текстовой коллекции документов). Поэтому было решено применить вычислительную парадигму MapReduce для реализации индексирования коллекции текстовых документов. В данной части работы рассматривается расширение стандартной реализации построения образов текстовых документов (вычисление TF-IDF) [65]. Алгоритм построения образов документов представлен в виде двух шагов. На первом шаге (рис. 14) происходит построение вектора DF встречаемости слов в документах коллекции (см. раздел 1.7 и 1.8 первой главы), который состоит из записей основа слова, количество документов, содержащее данную основу слова : в функции Map производится подсчет уникальных вхождений основ слов в рассматриваемый документ, в функции Reduce аккумулируются результаты подсчетов для каждой основы слова по всей коллекции документов.
Map Произвести анализ и разбор текста. Выделить основы слов, для каждой основы слова единожды выдать в результат пару основа слова, 1 . Reduce (на вход функции Reduce подается итератор по всем вхождениям основы слова) Произвести суммирование элементов итератора и выдать сумму в результат. На втором шаге построения образов документов (рис.15) происходит формирование результирующих векторов ключевых слов текстовых документов. При этом для подсчета важности слова по отношению к документу используется вектор DF, полученный на первом шаге. В функции Map второго шага производится следующие действия: обработка документа, извлечение из него основ слов, подсчитывается частота извлеченных основ слов документа; производится удаление стоп слов из построенного списка основ слов; производится принудительная редукция пространства признаков документа с использованием критерия порога частоты встречаемости слова в документах коллекции; в качестве результата формируется вектор частот основ слов. В функции Reduce второго шага подготовки образов документов производятся следующие действия: Подсчет важности слова производится с применением формулы TF-IDF (1.10.1). Отбор ключевых слов документа, имеющих наибольший вес в качестве результата. Входные данные Документы в текстовом формате. Map Построить вектор частот встречаемости основ слов документа. Reduce Из построенного на шаге Map вектора основ слов - рассчитать вес каждой основы слова, отбросить стоп слова и слова, частота которых в коллекции не входит в заданные пределы. В качестве результата (образ документа) построить вектор основ слов, имеющих наибольший вес. Параллельная реализация алгоритма иерархической кластеризации по областям текстовых документов Обработка больших объемов текстовой информации требует значительных вычислительных ресурсов, а также зачастую не может быть выполнена на одном вычислительном узле в силу ограничения по объему физической памяти. В данной работе реализована параллельная версия алгоритма иерархической кластеризации по областям текстовых документов (ПИКО), которая позволяет масштабировать решение задачи на необходимое количество вычислительных узлов. Работа распределенной версии представлена в виде двух шагов. На первом шаге алгоритма производится подготовка дерева областей верхнего уровня (рис. 16). Входные данные Образы документов в виде векторов ключевых слов. Map Построить дерево областей из входящего потока документов последовательным алгоритмом кластеризации, в результат выдать вектор областей верхнего уровня (с одинаковым ключом для всех процессов Map; каждая область характеризуется вектором ключевых слов). Reduce Произвести кластеризацию областей верхнего уровня полученных на шаге Map последовательным алгоритмом кластеризации. В результат выдать дерево областей верхнего уровня. Рис. 16. Формирование дерева областей верхнего уровня Входные данные Образы документов в виде векторов ключевых слов, дерево верхнего уровня. Мар Для каждого входного образа документа определить область дерева верхнего уровня. Выходные пары (ключ,значение) = (идентификатор области верхнего уровня, образ документа). Внутренними средствами Hadoop выходные пары Map группируются по ключу и далее передаются на вход Reduce. Reduce Для всех документов отображенных на шаге Мар в подобласть дерева верхнего уровня - построить поддерево областей. На втором шаге, запускается распределенная кластеризация документов, которая работает следующим образом: при поступлении на обработку в-функцию Мар для каждого документа определяется область дерева верхнего уровня, далее он отправляется на вычислительный узел, ответственный за обработку документов-данной области, и на этом вычислительном узле последовательным алгоритмом иерархической кластеризации по областям строится поддерево областей. На рис. 17 представлена схема алгоритма иерархической кластеризации по областям. Для каждого из результатов поиска имеется два источника информации о его релевантности (под релевантностью понимается важность, актуальность рассматриваемого документа по отношению к запросу) по отношению к поисковому запросу: вес, рассчитанный.базовым алгоритмом ранжирования; факт того, включен ли рассматриваемый результат поиска в превали рующую тематическую группу (см. раздел 1.1 первой главы). В качестве критерия качества ранжирования в данной работе используется метрика, подробно рассмотренная в разделе 1.6 первой главы (1.6.1):
Поиск по ключевым словам с тематическим ранжированием, на основе электронного каталога
Компонент построения образов текстовых документов содержит в себе следующие компоненты: Компонент извлечения данных из других форматов документов. Дан ный компонент использует библиотеки извлечения текста: Библиотека Apache PDFBox для извлечения текстовых данных из Pdf (http://pdfbox.apache.org/). Библиотека javax.swing.text.html для извлечения текстовых данных из Html формата. Компонент извлечения ключевых слов из текста, содержащий: Лексический анализатор текста, исключающий знаки препинания, знаки разметки, цифры, производящий перевод из высокого регистра в низкий регистр. Porter стеммер, для извлечения основ слов из текста [61]. Компонент подсчета DF статистики (встречаемости слов в доку ментах коллекции), подсчета статистки основ слов в рассматриваемом документе. Компонент расчета весов основ слов документа и отбора наибо лее важных основ слов документа в виде вектора ключевых слов. Компонент построения образов текстовых документов, используя алгоритм, описанный в разделе 2.1 второй главы, производит построение образов текстовых документов. Каждый из образов документов представляется в виде хешированной таблицы с записями цифровой идентификатор ключевого слова, вес ключевого слова . Компонент построения образов текстовых доку ментов использует во время своей работы файл словаря, содержащий: а) таблицу с записями длина основы слова, указатель на таблицу с записями Строковая основа слова, цифровой идентификатор основы слова», б) Таблицу с записями цифровой идентификатор основы слова, строковая основа слова . Во время работы алгоритма индексирования и кластеризации словарь располагается в динамической памяти вычислительного узла. На рис. 19 изображена схема структуры словаря. 3.1.3 Компонент поиска с тематическим ранжированием результатов Компонент поиска с тематическим ранжированием содержит в себе: Компонент преобразования запроса от пользователя системы в список ключевых слов. Компонент поиска результатов в инвертированном индексе по ключевым словам запроса (поисковая машина); Компонент базового ранжирования на основе функции Okapi ВМ25. Компонент тематического ранжирования результатов поиска. Веб интерфейс для взаимодействия с пользователем. Функционирование компонента поиска с тематическим ранжированием можно выразить следующим образом: 1) Пользовательпоисковой системы формализует запрос и вводит его в по-исковую систему с использованием Веб интерфейса! 2) Компонент Веб- интерфейса передает запрос в поисковую машину, которая производит анализ и разбор запроса, далее производит извлечение информации о документах, соответствующих запросу из построенного индексатором индекса-и передает извлеченную информацию, включая тематическую информацию по данным документам, компоненту ранжирования ре-зультатовпоиска. 3) Компонент ранжирования результатов поиска производит двухступенчатое ранжирование поисковых результатов: На первом шаге производится оценка веса,каждого из поисковых ре зультатов на основе функции ранжирования Okapi ВМ25. На втором шаге с использованием извлеченной тематической инфор мации производится ранжирование поисковых результатов с использованием- предложенной в данной работе функции тематического ранжирования. 3) Список ранжированных результатов выдается пользователю через Веб интерфейс. Таким образом, можно выделить пять основных функциональных блоков-предлагаемой поисковой системы (рис. 20): индексатор, ответственный за построение индекса коллекции тексто вых документов; поисковая машина, с помощью которой осуществляется поиск доку ментов по индексу в соответствии с запросами пользователей. компонент базового ранжирования результатов поиска; компонент тематического ранжирования результатов поиска; веб-интерфейс, с помощью, которого предлагается осуществлять взаи модействие с пользователем и отображать результаты поиска.
Результаты испытаний последовательных версий разработанных алгоритмов
Используя введенный критерий оценки качества ранжирования (NDCG@10), были проведены численные эксперименты по измерению качества работы предлагаемых алгоритмов ранжирования на коллекции научных статей "Вестник", которые показали превосходство предлагаемого алгоритма ранжирования по сравнению с базовым алгоритмом Okapi ВМ25 (рис. 27). Улучшение качества ранжирования по сравнению с базовым алгоритмом ранжирования на коллекции научных статей "Вестник" составило: 1 % для алгоритма ранжирования с тематической группировкой результа тов; 15% для алгоритма ранжирования результатов по заданной тематике ранжирования. Отметим, что для оценки качества работы алгоритма ранжирования необходимо подготовить тестовое множество запросов и сортированные списки поисковых результатов, соответствующие различным алгоритмам ранжирования. Для каждого из результатов заданных списков эксперт выставляет оценку соответствия рассматриваемого документа по отношению к запросу в диапазоне от 0 до 4 (0 - документ не соответствует запросу, 4 - документ является высококачественным результатом поиска по отношению к рассматриваемому запросу). При выборе числа запросов тестового множества в основном ориентируются на критерий [67, 68] стоимости трудозатрат экспертов для его подготовки. Также, предлагается оценить устойчивость оценки ранжирования (если при увеличении количества запросов тестового множества оценка ранжирования остается в заданных переделах, то далее предлагается не увеличивать мощность тестового множества запросов). На рис. 28 приведен график изменения метрики в зависимости от количества запросов: при увеличении количества запросов до 30 наблюдается стабилизация значения критерия качества NDCG@10. При подготовке множества тестовых запросов принимало участие 14 экспертов.
Запросы, использованные для тестирования коллекции "Вестник": "параллельное программирование примеры алгоритмов", "инвестиции в машиностроение", " фондовый рынок", "основы бухгалтерского учета", " информационный поиск", "графовые модели в приборостроении", "моделирование аэродинамики", "дистанционное обучение", "задача о заключенном теория игр", "математическое моделирование экономических систем", "методы оптимизации", "нанотехно-логии в образовании", "развитие информационных технологий университета", "устойчивость в экономике", "предварительное расследование", "уголовная ответственность", "прокурорский надзор", "исковое заявление", "компьютерный перевод", "философия Сократа", "высокопроизводительные вычисления", "вычисления общего назначения на графическом процессоре", "графические шейдеры", "Imagine Cup", "патчи Безье", "метод опорных векторов", "глобальная оптимизация", "линейное программирование", "задача о рюкзаке".
В целом; по итогам проведенных испытаний, программной реализации предложенных в настоящей работе математической модели и методов поиска с тематическим ранжированием, математической модели и методов автоматического построения электронного каталога, были показаны следующие результаты, превосходящие по качеству и скорости существующие подходы: Предложенные математическая модель и методы тематического ранжирования позволили улучшить качество ранжирования ре зультатов поискаот 1% до 15;6% по метрике NDCG@10. " Предложенный в работе алгоритм иерархической кластеризации по областям; используемый для построения иерархии1 электронного каталога показал преимущество в-качестве и скорости по? сравнению с; тремях традиционными алгоритмами кластеризации., Улучшение качества1 кластеризации составило от 9 % до 22% по,1 метрике F1. Предложенные варианты, распределенных версий алгоритмові построения образов текстовых документов, и иерархической кластеризации по областям показали; линейное ускорение в-.за висимости от количества? задействованных в вычислениях про цессорных ядер. При этомфаспараллеливание дает максимальный» эффект при обработке больших объемов текстовых данных.. Таким образом; предложенная; математическая модель поиска с тема-тическим ранжированием, на .основе автоматически построенного электронного каталога удовлетворяет всем требованиям, вытекающим из цели исследования. Основные результаты кандидатской диссертации: 1) Разработана новая математическая модель информационного поис ка с тематическим ранжированием, основанным на автоматически построенном электронном каталоге. Предложенные методы темати ческого ранжирования показали улучшение качества ранжирования результатов поиска от 1% до Л 5,6% по метрике NDCG@10. 2) Разработана новая математическая модель автоматического по строения электронного каталога текстовых документов без ограни чения на тематику и размер исходной текстовой коллекции. 3) Предложен новый метод текстовой кластеризации - иерархическая» кластеризация по областям текстовых документов, учитывающий не достатки существующих алгоритмов иерархической текстовой кла стеризации. Разработаны последовательные и параллельные версии предложенного алгоритма. Проведенные испытания показали пре имущество в качестве предложенного алгоритма иерархической кла стеризации по областям по сравнению с тремя традиционными алго ритмами кластеризации. Улучшение качества кластеризации состави ло от 9 % до 22% по метрике Fl\ 4) Разработаны параллельные версии алгоритмов извлечения тексто вых признаков и иерархической кластеризации по областям тексто вых документов. Проведенные эксперименты показали линейное ус корение в зависимости от количества вычислительных узлов. 5) Разработан метод автоматического выбора названия и описания для сформированных кластеров автоматически построенного элек тронного каталога. 6) Разработан, апробирован и внедрен в качестве поисковой системы по публикациям программный комплекс, реализующий предложенную математическую модель поиска по ключевым словам с тематическим ранжированием, основанным на использовании предложенного подхода к автоматическому построению электронного каталога.
