Разработка и реализация нейросетевого поиска в рамках проекта "AIST"

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

2

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

1

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

Кафедра информационных технологий

КУРСОВАЯ РАБОТА

Разработка и реализация нейросетевого поиска в рамках проекта «AIST»

Работу выполнил студент 4 курса ФКТиПМ

спец. 010501 «Прикладная математика и информатика»

Б.И. Трофимов

Научный руководитель,

А.В. Харченко

Краснодар 2013



СОДЕРЖАНИЕ

Введение

1. Обзор использованных технологий

2. Требования к разрабатываемой системе поиска

3. Методы решения поставленных задач

3.1 Векторная модель текста

3.2 Метод построения векторной модели

3.3 Нейронные сети

3.3.1 Кластерный анализ

3.3.2 Нейронная сеть Кохонена

3.3.3 Алгоритм расширяющего нейронного газа

4. Применение ИНС Кохонена к векторной модели текста. Модификация алгоритма расширяющегося нейронного газа

5. Достоинства нейросетевого подхода

6. Описание работы механизма поиска

7. Структура системы

7.1 Пакет main.engine

7.2 Пакет main.trainer

7.3 Пакет main.search

7.4 Пакет main.test

8. Настройка параметров поискового механизма. Статистический анализ построенной сети

Заключение

Список использованных источников

поисковый механизм алгоритм нейронная сеть



Введение

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

В данной курсовой работе рассмотрены такие технологии как Java, JDBC, JSON, SQL, RegExp. Методики и алгоритмы: кластеризация данных, нейронная сеть Кохонена, алгоритм расширяющегося нейронного газа, векторная модель текста, TF-IDF, полнотекстовый поиск, средства статистического анализа нейронной сети Кохонена.

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



1. Обзор использованных технологий

· JSON (JavaScript Object Notation) -- текстовый формат обмена данными, основанный на JavaScript и обычно используемый именно с этим языком. Как и многие другие текстовые форматы, JSON легко читается людьми.

За счёт своей лаконичности по сравнению с XML, формат JSON может быть более подходящим для сериализации сложных структур. Если говорить о веб-приложениях, в таком ключе он уместен в задачах обмена данными как между браузером и сервером (AJAX), так и между самими серверами (программные HTTP-интерфейсы). Формат JSON также хорошо подходит для хранения сложных динамических структур в реляционных базах данных или файловом кэше.

Поскольку формат JSON является подмножеством синтаксиса языка JavaScript, то он может быть быстро десериализован встроенной функцией eval(). Кроме того, возможна вставка вполне работоспособных JavaScript-функций.

· SQL (англ. Structured Query Language) - универсальный компьютерный язык, применяемый для создания, модификации и управления данными в реляционных базах данных. SQL основывается на исчислении кортежей.

· RegExp (англ. Regular Expressions) Регулярные выражения -- это формальный язык поиска и осуществления манипуляций с подстроками в тексте, основанный на использовании метасимволов (символов-джокеров, англ. wildcard characters). По сути это строка-образец (англ. pattern, по-русски её часто называют «шаблоном», «маской»), состоящая из символов и метасимволов и задающая правило поиска [7].

· JDBC (англ. Java DataBase Connectivity -- соединение с базами данных на Java) -- платформенно-независимый промышленный стандарт взаимодействия Java-приложений с различными СУБД, реализованный в виде пакета java.sql, входящего в состав Java SE [7]. JDBC основан на концепции так называемых драйверов, позволяющих получать соединение с базой данных по специально описанному URL. Драйверы могут загружаться динамически (во время работы программы). Загрузившись, драйвер сам регистрирует себя и вызывается автоматически, когда программа требует URL, содержащий протокол, за который драйвер отвечает.

Использованные термины и соглашения:

· Точность поиска - оценка условной вероятности того, что выданный системой документ действительно релевантен запросу [12];

· Полнота поиска - оценка условной вероятности того, что релевантный запросу документ будет выдан системой пользователю [12];

· Документ (в рамках данной работы) - совокупность термов;

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

· Кластер - совокупность элементов конкретного набора данных, близких в отношении введенной для кластеризации метрики;

· Эпоха обучения - один проход алгоритма обучения через обучающую выборку.



2. Требования к разрабатываемой системе поиска

Поисковая система является частным случаем системы обработки данных, и должна удовлетворять следующим требованиям:

· Оптимальная эффективность вычислений и эффективность использования ресурсов системы;

· Наилучшее соответствие результатов поиска поисковому запросу пользователя: увеличение точности и полноты поиска;

· Функциональная полнота системы;

· Разработка архитектурных решений, гарантирующих автономность, устойчивость, точность и безошибочность работы системы;

· Информационная безопасность решений системы;

· Расширяемость и масштабируемость системы.



3. Методы решения поставленных задач

3.1 Векторная модель текста

В конце 80-х годов была предложена векторная модель как альтернатива лексическому бесконтекстному индексированию. В простейшем случае векторная модель предполагает сопоставление каждому документу частотного спектра слов и соответственно вектора в лексическом пространстве. В процессе поиска частотный портрет запроса рассматривается как вектор в том же пространстве и по степени близости (расстоянию или углу между векторами) определяются наиболее релевантные документы. В более продвинутых векторных моделях размерность пространства сокращается отбрасыванием наиболее распространенных или редко встречающихся слов, увеличивая тем самым процент значимости основных слов. Главным достоинством векторной модели является возможность поиска и ранжирования документов по подобию, то есть по их близости в векторном пространстве. Однако практика показывает, что при оценке близости запроса к документу результаты поиска могут быть не всегда удовлетворительными, что особенно проявляется, когда запрос содержит малое количество слов. Для получения лучшей релевантности отклика в 1990 году была предложена модель скрытого семантического индексирования Ї Latent Semantic Indexing (LSI) [8]. Модель использовала Singular Value Decomposition (SVD) для перехода от разреженной матрицы слов к компактной матрице главных собственных значений. LSI показала значительное превосходство в результатах поиска по сравнению с лексическим методом, однако сложность модели часто приводила к существенному проигрышу в скорости на больших коллекциях документов по сравнению с традиционной булевой техникой. Одна из наиболее работоспособных систем на основе LSI была создана в Беркли в 1995 году Майклом Берри и Тодом Летче [8].



3.2 Метод построения векторной модели

При построении векторной модели текста используется статистическая характеристика TF-IDF, структура формулы которой представлена ниже:

· TF (term frequency -- частота слова) -- отношение числа вхождения некоторого слова к общему количеству слов документа. Таким образом, оценивается важность слова в пределах отдельного документа:

где есть число вхождений слова в документ, а в знаменателе -- общее число слов в данном документе.

· IDF (inverse document frequency -- обратная частота документа) -- инверсия частоты, с которой некоторое слово встречается в документах коллекции. Учёт IDF уменьшает вес широкоупотребительных слов. Для каждого уникального слова в пределах конкретной коллекции документов существует только одно значение IDF:

где

· -- количество документов в корпусе;

· -- количество документов, в которых встречается (когда ).

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

Таким образом, мера TF-IDF является произведением двух сомножителей: Большой вес в TF-IDF получат слова с высокой частотой в пределах конкретного документа и с низкой частотой употреблений в других документах.

Существуют различные формулы, основанные на методе TF-IDF. Они отличаются коэффициентами, нормировками, использованием логарифмированных шкал. В частности, поисковая система Яндекс долгое время использовала нормировку по самому частотному термину в документе [7].

В данной работе мера TF-IDF используется для представления документов коллекции в виде числовых векторов, отражающих важность использования каждого слова из некоторого набора слов (количество слов набора определяет размерность вектора) в каждом документе. Такая модель называется векторной моделью (en: Vector space model) и даёт возможность сравнивать тексты, сравнивая представляющие их вектора в какой либо метрике (евклидово расстояние, косинусная мера, манхэттенское расстояние, расстояние Чебышева и др.), т. е. производя кластерный анализ.

3.3 Нейронные сети

3.3.1 Кластерный анализ

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

Кластерный анализ выполняет следующие основные задачи:

· Разработка типологии или классификации.

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

· Порождение гипотез на основе исследования данных.

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

Независимо от предмета изучения применение кластерного анализа предполагает следующие этапы:

· Отбор выборки для кластеризации. Подразумевается, что имеет смысл кластеризовать только количественные данные.

· Определение множества переменных, по которым будут оцениваться объекты в выборке, то есть признакового пространства.

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

· Применение метода кластерного анализа для создания групп сходных объектов.

· Проверка достоверности результатов кластерного решения.

В качестве целей кластеризации выделяют:

· Понимание данных путём выявления кластерной структуры. Разбиение выборки на группы схожих объектов позволяет упростить дальнейшую обработку данных и принятия решений, применяя к каждому кластеру свой метод анализа (стратегия «разделяй и властвуй»).

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

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

Общепринятой классификации методов кластеризации не существует, но можно выделить ряд групп подходов [7]:

1. Вероятностный подход. Предполагается, что каждый рассматриваемый объект относится к одному из k классов. Выделяют такие методы как:

o K-средних (K-means)

o K-medians

o EM-алгоритм

o Алгоритмы семейства FOREL

o Дискриминантный анализ

2. Подходы на основе систем искусственного интеллекта: весьма условная группа, так как методов очень много и методически они весьма различны:

o Метод нечеткой кластеризации C-средних (C-means)

o Нейронная сеть Кохонена

o Генетический алгоритм

3. Другие методы. Не вошедшие в предыдущие группы.

o Статистические алгоритмы кластеризации

Несмотря на значительные различия между перечисленными методами все они опираются на исходную «гипотезу компактности»: в пространстве объектов все близкие объекты должны относиться к одному кластеру, а все различные объекты соответственно должны находиться в различных кластерах.

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

Алгоритм кластеризации -- это функция , которая любому объекту ставит в соответствие номер кластера . Множество в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации [7].

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

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

· число кластеров, как правило, неизвестно заранее и устанавливается в соответствии с некоторым субъективным критерием. Это справедливо только для методов дискриминации, так как в методах кластеризации выделение кластеров идёт за счёт формализованного подхода на основе мер близости.

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



3.3.2 Нейронная сеть Кохонена

Нейронные сети Кохонена - класс нейронных сетей, основным элементом которых является слой Кохонена.

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

На выходе -го линейного элемента получаем сигнал:

,

где -- весовой коэффициент -го входа -го нейрона,  -- пороговый коэффициент.

После прохождения слоя линейных элементов сигналы посылаются на обработку по правилу «победитель забирает всё»: среди выходных сигналов ищется максимальный;

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

Геометрическая интерпретация сети Кохонена заключается в том, что при обучении заданное - мерное пространство разбивается на соответствующие многогранники Вороного-Дирихле : многогранник состоит из точек, которые ближе к , чем к другим .

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



Рисунок 1 - Разбиение Вороного-Дирихле

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

где состоит из тех точек , которые ближе к , чем к другим . Другими словами, состоит из тех точек , которые кодируются кодовым вектором .

Если совокупность задана и хранится в памяти, то стандартным выбором в обучении соответствующей сети Кохонена является метод K-средних. Это метод расщепления:

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

· при данном разбиении на множества минимизацией находим оптимальные позиции кодовых векторов  -- для оценки по методу наименьших квадратов это просто средние арифметические:

где  -- число элементов в .

Далее итерируем. Этот метод расщепления сходится за конечное число шагов и даёт локальный минимум искажения.

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

где  -- шаг обучения. Остальные кодовые векторы на этом шаге не изменяются. Для обеспечения стабильности используется онлайн метод с затухающей скоростью обучения: если  -- количество шагов обучения, то полагают . Функцию выбирают таким образом, чтобы монотонно при и чтобы ряд [7]:

расходился, например:

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

Алгоритм работы сети состоит из следующих шагов:

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

· Цикл. Пусть  -- номер итерации (инициализация соответствует номеру 0):

· Выбор произвольного наблюдения - вектора из множества входных данных.

· Найти расстояния от него до векторов веса всех узлов карты и определить ближайший по весу узел . Это -- BMU или победитель. Условие на отбор :



,

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

· Определение с помощью функции (функции соседства) соседей и изменение их векторов веса по формуле:

.

· Определение ошибки карты по формуле:

где - весовые вектора узлов карты, - количество элементов набора входных данных,

Функция определяет "меру соседства" узлов и и изменение векторов веса. Она должна постепенно уточнять их значения, сначала у большего количества узлов и сильнее, потом у меньшего и слабее. Часто в качестве функции соседства используется гауссова функция:

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

,  -- координаты узлов и на карте;

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

Параметры, и их характер убывания задаются аналитиком.

Более простой способ задания функции соседства:

,

если находится в окрестности заранее заданного аналитиком радиуса, и 0 в противном случае.

Функция равна для BMU и уменьшается с удалением от BMU.

3.3.3 Алгоритм расширяющегося нейронного газа

Расширяющийся нейронный газ (Growing Neural Gas, GNG) -- это алгоритм, позволяющий осуществлять адаптивную кластеризацию входных данных, то есть не только разделить пространство на кластеры, но и определить необходимое их количество исходя из особенностей самих данных. Это новый класс вычислительных механизмов, являющийся развитием сетей Кохонена. Количество и расположение искусственных нейронов в пространстве признаков не задается заранее, а вычисляется в процессе обучения в соответствии с особенностями входных данных, самостоятельно подстраиваясь под них [7].

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

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

Начиная всего с двух нейронов, алгоритм последовательно изменяет (по большей части, увеличивает) их число, одновременно создавая набор связей между нейронами, наилучшим образом отвечающих распределению входных векторов. У каждого нейрона имеется внутренняя переменная, в которой накапливается «локальная ошибка», . Соединения между узлами характеризуются переменной, называемой «возраст» . Алгоритм включает следующие шаги [15]:

· Сперва создаются два узла (здесь и далее, узел означает нейрон) с векторами весов, разрешенными распределением входных векторов, и нулевыми значениями локальных ошибок ;

· Узлы соединяются связью, которой можно установить возраст. На начальном этапе возраст равен .

· Затем на вход нейросети подаётся вектор .

· На следующем этапе находятся два нейрона и , ближайших к ( ближе, чем ), то есть узлы с векторами весов и , такими, что -- минимальное, а -- второе минимальное значение расстояния среди всех узлов.

· Обновляется локальная ошибка, наиболее близкого нейрона -- победителя , к ней добавляется квадрат расстояния между векторами и :

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

· Нейрон-победитель и все его топологические соседи (то есть все нейроны , имеющие соединение с победителем) смещаются в сторону входного вектора на расстояния, равные долям и от полного:

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

· Увеличить на 1 возраст всех соединений, исходящих от победителя .

· Если два лучших нейрона и соединены, . В противном случае создать связь между ними.

· Удалить все соединения, возраст которых превышает максимальный возраст. Если после этого имеются нейроны, не имеющие связей с другими узлами, удалить эти нейроны.

· Уменьшить ошибки всех нейронов на долю :



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

· Найти нейрон с наибольшей локальной ошибкой.

· Среди соседей найти нейрон с максимальной ошибкой.

· Создать узел «посередине» между и :

Заменить связь между и на связи между и , и .

Уменьшить ошибки нейронов и , установить значение ошибки нейрона :

Большое значение этой ошибки служит указанием на то, что соответствующий нейрон лежит в области небольшого числа нейронов.



4. Применение ИНС Кохонена к векторной модели текста. Модификация алгоритма расширяющегося нейронного газа

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

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

При добавлении документа :

При удалении документа :

Это делается для того, чтобы оценить местоположение с наименьшей локальной ошибкой для кластера.

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

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

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

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

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

· если у нейрона не обнаружено ни одной свизи с документами, увеличить значение если у нейрона есть хотя бы одна связь с документом, пересчитать значение :

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



5. Достоинства нейросетевого подхода

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

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

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

Кроме того, при правильном выборе алгоритма кластеризации появляется возможность ускорить процесс поиска.



6. Описание работы механизма поиска

Пусть имеется множество документов , , и - множество уникальных термов, содержащихся в докуметнах множества , .

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

Обучение нейронной сети Кохонена предполагается производить онлайн методом [9], обучая сеть на новых векторных представлениях по мере добавления индексатором документов к уже индексированным документам. В результате обучения нейронной сети Кохонена будет получена кластеризация документов, представленных векторами в -мерном пространстве характеристик TF-IDF термов, что позволит сократить количество расчетов при выполнении операции поиска и улучшить показатель точности и полноты поиска при правильном подборе параметров сети и архитектуры системы. Также при обучении сети Кохонена может быть использовано несколько этапов:

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

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

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

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



7. Структура системы

Практическая реализация построена на базе объектно-ориентированного языка Java с применением СУБД postgreSQL для хранения индексной информации о документах (в виде описанной ранее векторной модели с подходом TF-IDF), а также данных относительно построенной сети Кохонена: весовых векторов нейронов, связей нейрон-нейрон и нейрон-документ. Решение о использовании этих программных продуктов было принято на основе анализа и сравнения их преимуществ перед альтернативными способами реализации. Ниже представлена часть результатов анализа: Язык программирования Java:

o Высокая скорость разработки и поддержки прикладных приложений:

§ Быстрый рефакторинг кода в IDE Eclipse;

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

§ Удобные методы реализации многопоточности, в сравнении с многими другими языками (Deplhi, c++, C#);

o Кроссплатформенность, что позволяет запускать полученное приложение на средах, поддерживающих JVM (Java Virtual Machine), без приложения дополнительных усилий по поддержке данной возможности;

o Наличие драйвера JDBC для СУБД postgreSQL. Преимуществами JDBC считают:

§ Лёгкость разработки: разработчик может не знать специфики базы данных, с которой работает;

§ Код не меняется при переходе на другую базу данных;

§ Не нужно устанавливать громоздкую клиентскую программу;

§ К любой базе можно подсоединиться через легко описываемый URL.

· СУБД postgreSQL:

o Свободное ПО;

o Кроссплатформенное ПО;

o Концепция ACID: Atomicity - Атомарность, Consistency - Согласованность, Isolation - Изолированность, Durability - Долговечность;

o Поддержка ссылочной целостности;

o Поддержка транзакций;

o Поддержка схем БД;

o Поддержка временных таблиц;

o Поддержка представлений (видов);

o Поддержка материализованных представлений;

o Поддержка вычисляемых индексов;

o Поддержка частичных индексов;

o Поддержка обращенных индексов;

o Поддержка индексов по битовым картам;

o Поддержка доменов;

o Поддержка курсоров;

o Поддержка функций, определенных пользователем;

o Поддержка триггеров;

o Поддержка хранимых процедур;

o Поддержка табличных пространств.

Программный комплекс состоит из четырех пакетов:

1. main.engine;

2. main.trainer;

3. main.search; main.test.

7.1 Пакет main.engine

Целью данного пакета является реализация основного функционала ядра системы - создание нейронной сети, предоставление API для работы с ней, хранение базовых настроек ядра. Пакет содержит такие классы как:

· Vector - класс для представления векторов произвольной размерности, также предоставляет функционал работы с векторами:

· Вычисление расстояния между векторами в евклидовой метрике

· Сравнение векторов на признак равенства

· Обращение, сложение, вычитание, вычисление квадрата скалярного произведения, вычисление квадрата нормы

· масштабирование и нормализация вектора

· DataObject extends Vector - класс, экземпляры которого представляют собой документы коллекции в векторной форме. Содержит в себе ссылку на нейрон, с которым он соединен связью. Предоставляет методы для обеспечения согласованности операции добавления и удаления связи нейрон-документ (при этом подразумевается документ, представляемый экземпляром данного класса).

· Neuron extends Vector - класс нейрона сети. Экземпляр данного класса содержит в себе связи нейрон-нейрон и нейрон-документ нейрона, представляемого данным объектом; значение среднего арифметического для векторных представлений документов, содержащихся в данном кластере и локальной ошибки нейрона. Предоставляет методы, позволяющие добавлять, удалять и изменять связи нейрон-нейрон и нейрон-документ, обеспечивающие согласованность вложенных структур данных; данные методы также производят пересчет параметров нейрона при добавлении и удалении связей.

· Network - класс нейронной сети Кохонена. Содержит в себе ссылки на все экземпляры созданных нейронов и методы работы с ними:

· Получение номера нейрона, ближайшего к указанному вектору, а также второго по близости нейрона

· Получение нейрона сети с наибольшей ошибкой

· Получение нейрона с наибольшей ошибкой среди соседей выбранного нейрона

· Вычисление общей ошибки карты

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

7.2 Пакет main.trainer

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

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

7.3 Пакет main.search

Пакет содержит класс Search, который отвечает за обработку поисковых запросов пользователя и выдачу результатов поиска. Предоставляет метод int[] search(request), который и осуществляет поиск по индексированным документам, используя API класса Network. Параметр request представляет собой список термов и управляющих символов, введенных пользователем системы и обрабатывается методом Search с использованием регулярных выражений для дальнейших манипуляций с полученным набором выделенных термов и управляющих символов. Далее метод производит перевод набора термов поискового запроса в векторное представление, используя те же правила, что и при построении векторной модели для документов, после чего производит поиск ближайшего кластера к полученному вектору. Содержимое кластера (также, возможно, содержимое его топологических соседей, в порядке ранжирования по возрастанию расстояния от вектора поискового запроса, если меньше, чем требуемое минимальное число файлов) в виде номеров файлов составляет результат работы функции - массив значений типа int.

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

7.4 Пакет main.test

Назначением данного пакета является тестирование и отладка работы системы. С использованием пакета визуального интерфейса awt в нем реализованы следующие классы:

· MainCanvas extends Canvas - представляет собой визуальный компонент, ответственный за прорисовку элементов выбранной сети и внутреннюю поддержку актуальности контекста рисования на данном элементе (контекст рисования может быть потерян при возникновении определенных событий, возникающих в операционоой системе; компонент занимается отслеживанием этих событий и восстановлением контекста при необходимости).

· SOMFrame extends JFrame - класс, отвечающий за создание фрейма, на котором будут представлены визуализированные данные о выбранной сети. Является контейнером для экземпляра класса MainCanvas и предоставляет последнему место в иерархии визуальных компонентов. Содержит в себе обработчики событий клавиатуры и мыши, необходимых для работы с визуальным интерфейсом данного пакета. Предоставляет возможность вывода статистики о выбранной сети, что позволяет оценить правильность настройки параметров системы и сделать соответствующие изменения, если это требуется.

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



8. Настройка параметров поискового механизма. Статистический анализ построенной сети

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

Первое из полученных правил - зависимость максимального количества нейронов в сети от количества документов в коллекции:

где значение было подобрано на практике, как 0,67. Такой выбор был обоснован тем, что такая зависимость обеспечивает невозрастание средней ошибки сети при росте количества документов в коллекции и сравнительно незначительный рост дисперсии ошибки при выбранном алгоритме обучения. С таким распределением, при количестве документов в коллекции максимальное количество нейронов в сети будет достигать числа порядка , что приблизительно соответствует 1000 документов в каждом кластере.

Максимальный возраст связи устанавливается числом в диапазоне , наилучшим на практике было выбрано значение 30, так как в данном случае достигается бОльшая стабильность топологических связей нейрон-нейрон.

Множитель пересчета ошибки нейронов при добавлении нового нейрона в сеть был выбран значением 0,8; множитель пересчета ошибки всех нейронов по завершении эпохи обучения был выбран 0,9.

Начальная настройка производилась на примере двуметного пространства признаков, что позволило создать удобную визуализацию полученной сети, которую иллюстрирует рисунок 2.

Рисунок 2 - Выборка для обучения

На рисунке 2 отображена выборка для обучения сети. Крестиками обозначены вектора, составляющие выборку.

После нескольких эпох обучения начинают добавляться кластеры, что отображается на рисунке 3.

Рисунок 3 - Сеть, после нескольких эпох обучения



На рисунке 3 пунктирными линиями показаны связи нейрон-нейрон, сплошными - нейрон-документ, кругами обозначены нейроны сети.

Рисунок 4 - Окончательный результат обучения сети

На рисунке 4 изображен окончательный результат обучения сети на данной выборке. Как видно, получено разбиение данных на кластеры, в сети 22 кластера, 100 векторов выборки; каждый кластер содержит в среднем вектора выборки; средняя ошибка кластера равна (в пиксель², масштаб 1:1); дисперсия количества объектов в кластере ; дисперсия ошибки кластера ; при этом средняя ошибка, приходящаяся на объект ; такие параметры являются пригодными для данной задачи.



Заключение

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

В процессе проделанной работы было рассмотрено большое количество материалов по нейронным сетям, методик разработки, и прикладных технологий, среди которых: нейронные сети Кохонена векторного квантования, алгоритм расширяющегося нейронного газа, векторная модель текста, методика TF-IDF, кластерный анализ, поисковые системы, статистические подходы к решению задачи кластеризации, работа с СУБД postgreSQL, язык программирования Java и его взаимодействие с СУБД, приведение данных к нормальной форме, а также оптимизированные методы работы с данными, хранящимися в БД. Также было проведено сравнение различных методик с целью выявления наилучших для применения в данной работе.

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

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



Список использованных источников

1.Левенштейн В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академий Наук СССР, 1965. 163.4:845-848.

2.Кулагина О. С. О современном состоянии машинного перевода // Математические вопросы кибернетики, вып. 3, М.: Наука, 1991, стр. 5--50. Библиография из 140 названий. ISBN 5-02-014323-5.

3.Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ IntroductiontoAlgorithms / Под ред. Красикова И. В. -- 2-е изд. -- М.: Вильямс, 2005. -- 1296 с. -- ISBN 5-8459-0857-4.

4.Барцев С. И., Охонин В. А. Адаптивные сети обработки информации. Красноярск : Ин-т физики СО АН СССР, 1986. Препринт N 59Б. -- 20 с.

5.Уоссермен, Ф. Нейрокомпьютерная техника: Теория и практика = NeuralComputing. TheoryandPractice -- М.: Мир, 1992. -- 240 с. -- ISBN 5-03-002115-9.

6.Кохонен Т. «самоорганизующиеся карты», Third Edition, Springer, перевод 3-его английского издания Агеева В. Н. под редакцией Тюменцева Ю. В., 2008