Сравнительная характеристика методов поиска информации в базе знаний

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

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

СРАВНИТЕЛЬНАЯ ХАРАКТЕРИСТИКА МЕТОДОВ ПОИСКА ИНФОРМАЦИИ В БАЗЕ ЗНАНИЙ

Михайловский В.О.¹, Галиуллина Н.А.

^{2 1}Михайловский Вадим Олегович - студент;

²Галиутина Наиля Альбертовна - студент, кафедра информатики и прикладной математики,

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

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

информация поиск обучение машинный

COMPARATIVE CHARACTERISTIC OF INFORMATION SEARCH METHODS ON THE KNOWLEDGE BASE

Mikhailovskiy V.O.¹, Galiullina N.A.^{2 1}Mikhailovskiy Vadim Olegovich - Student;

²Galiullina Nailia Albertovna - Student,

DEPARTMENT OF COMPUTER SCIENCE AND APPLIED MATHEMATICS, FEDERAL STATE BUDGETARY EDUCATIONAL INSTITUTION OF HIGHER PROFESSIONAL EDUCATION KAZAN NATIONAL RESEARCH TECHNOLOGICAL UNIVERSITY, KAZAN

Abstract: the article discusses the basic methods of optimizing the search for information on a knowledge base. A comparative analysis of the methods and the introduction of a more optimal search method to solve the problem of finding instructions on the knowledge base is carried out. In addition to the classical methods of searching for information on a knowledge base, which includes a full database scan and scanning by a full-text index, the article analyzes a version using machine learning that has significant advantages over other methods.

Keywords: information system, knowledge base, search optimization, index, full-text index, machine learning.

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

• точность поиска увеличилась;

• время поиска уменьшилось или не изменилось.

• в процессе исследования использовали следующие методы:

• полное сканирование базы - при поиске инструкций по разделами и ключевым словам;

• сканирование по полнотекстовому индексу - при поиске инструкций по заголовку;

• отбор при соответствии смысловых векторов - при усовершенствованном поиске инструкций по заголовку.

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

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

Некоторые общие принципы, связанные с созданием индексов:

• индексы необходимо создавать для столбцов, которые используются в джойнах, по которым часто производится поиск и операции сортировки. При этом необходимо учесть, что индексы всегда автоматически создаются для столбцов, на которые накладывается ограничение primary key. Чаще всего они создаются и для столбцов с foreign key (в Access - автоматически);

• индекс обязательно в автоматическом режиме создается для столбцов, на которые наложено ограничение уникальности;

• лучше всего индексы создавать для тех полей, в которых - минимальное число повторяющихся значений и данные распределены равномерно. В Oracle есть специальные битовые индексы для столбцов с большим количеством повторяющихся значений, в SQL Server и Access такой разновидности индексов не предусмотрено;

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

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

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

Full text index - полнотекстовый специализированный индекс, для больших объемов текстовых данных, которые хранятся в столбцах строкового типа VARCHAR, TEXT. Для относительно небольших типов данных используется обычный индекс.

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

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

Следует рассмотреть положительные и отрицательные характеристики.

Плюсы:

• Компактность и точность запросов за счет комбинирования структурных и полнотекстовых критериев.

• Нет необходимости устанавливать дополнительное программное обеспечение.

• Поиск по готовому индексу проходит достаточно быстро.

• Простота и точность.

Минусы:

• Необходимо содержать дополнительное поле.

• Потери производительности при вставке и обновлении записей будут довольно ощутимыми.

• Дополнительная нагрузка на сервер.

• Несколько дополнительных объектов в схеме.

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

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

На рисунке 1 показан пример поиска по разделу, здесь: 1 - номер шаблона для поиска, “Установка программных компонентов” - название раздела. В примере видно, что метод поиска напрямую чувствителен к регистру и совершенно не подходит для решения задачи поиска в базе знаний.

Рис. 1. Пример поиска инструкций по разделу

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

- регистр не имеет значения;

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

На рисунке 2 показаны эксперименты с поиском инструкций по заголовку, здесь: 3 - номер шаблона, “инструкция” - слово, встречающееся в заголовке.

Рис. 2. Поиск инструкций по заголовку

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

Рис. 3. Пример поиска по заголовку в другом падеже

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

Реализуем данный алгоритм следующим образом:

1. разделим запрос на слова;

2. найдем вектора каждого слова;

3. определим вектор выражения;

4. перебором по матрице заголовков инструкций найдем косинусное сходство между каждым из заголовков и входным запросом;

5. найдем самые близкие по смыслу к входному запросу заголовки;

6. сформулируем результат поиска.

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

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

На рисунке 4 изображен результат работы word2ve^ по запросу “установка программных компонентов” нашлись самые подходящие по смыслу инструкции. Среди достоинств можно отметить:

• независимость от регистра введенного запроса;

• поиск инструкций по смыслу;

• быстрота поиска.

Рис. 4. Результат поиска с использованием word2vec

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

Список литературы /References

1. Воройский Ф. Информатика. Новый систематизированный толковый словарь. Litres, 2018.

2. Лесковец Ю., Раджараман А., Ульман Д.Д. Анализ больших наборов данных // М.: ДМК Пресс, 2016. Т. 488.

3. Бабкин А.В. и др. Формирование цифровой информатики в России: сущность, особенности, техническая нормализация, проблемы развития // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета, 2017. Т. 10. № 3.

4. Ярке Матиас, Кох Юрген. “Query Optimization in Database Systems”. Computing Surveys, Vol. 16. № 2. June, 1984.

5. Кузнецов С. “Методы оптимизации выполнения запросов в реляционных СУБД”. [Электронный ресурс]. Режим доступа: http://citforum.ru/database/artides/art_26.shtml, свободный/ (дата обращения: 14.07.2020).

6. Chaudhuri S., Shim K. Optimization of Queries with User-Defined Predicates. In Proc. of VLDB. Mumbai, 1996.

Размещено на Allbest.ru