Обсуждаемый подход является частью исследований проекта интеллектуальной системы информационной поддержки инноваций в науке и образовании.
ABSTRACT
The article represents the main features of the proposed approach to organization of search queries and filtering of documents search results. This approach based on the genetic algorithms and describes the main steps of the modified genetic algorithm, proposed solutions, tailored to the search procedures. The considered algorithm is one of the elements of an intelligent system of information support of innovation in science and education.
Ключевые слова: генетический алгоритм, поисковый запрос, релевантность, фильтрация, ранжирование, популяция, скрещивание, мутация, селекция, приспособленность.
Keywords: genetic algorithm, search query, relevancy, filtering, ranking, population, crossover, mutation, selection, fitness.
Введение. Одним из видов поиска в Интернет является поиск достаточной информации о каком-либо объекте или явлении. В отличие от поиска определенных сведений и фактов, касающихся отдельных сторон искомой сущности, решить нетривиальную задачу формулировки поискового запроса для подбора релевантных документов непросто (иногда, может быть, и невозможно). Например, требуется узнать экономические показатели шахты ОАО «Распадская» за первое полугодие 2013 год? Используя эту фразу в качестве поискового запроса, можно получить релевантный ответ в первом десятке результатов поиска Google. Но как подобрать материалы, например, для анализа научно-технических, экономических и социальных факторов влияния на угледобычу в восточных районах России?
Для решения подобных задач пользователи вынуждены применять множество сочетаний ключевых слов и понятий, уточняя их в ходе анализа промежуточных результатов. Неочевидно, что при этом будет строго использована какая-либо обоснованная методика. В ходе поиска неизбежно встает ряд вопросов. Как совместно оценить релевантность документов, найденных разными запросами? Как отфильтровать документы, не относящиеся по сути к искомой тематике? Все ли релевантные документы будут показаны в результатах поиска? Правильно ли определялась релевантность документов? Невозможно однозначно ответить на эти вопросы в рамках тривиальных решений.
В настоящей статье описываются основные особенности предложенного автором подхода к организации поисковых запросов и фильтрации результатов поиска документов, основанного на использовании идей генетических алгоритмов.
Работы проводились при финансовой поддержке РФФИ (договор № НК13-07-0034213). Они являются частью исследований, касающихся проектных спецификаций модулей интеллектуальной системы информационной поддержки инноваций в науке и образовании [1].
Постановка задачи. Предположим, что задано множество ключевых слов 
, 
, которые формируют поисковый образ документа (ПОД). Например, 
. Любой поисковый запрос 
может быть сформирован, как некоторая совокупность ключевых слов из множества 
. Результатом выполнения запроса в какой-либо поисковой системе является некоторое множество адресов найденных документов. Очевидно, что множества результатов различных запросов могут пересекаться.
Задача состоит в том, чтобы из множеств результатов, полученных после выполнения нескольких запросов, выбрать такое множество адресов документов (целевое множество результатов поиска), которое будет наиболее релевантным заданному ПОД.
Можно предположить, что целевое множество результатов поиска с большой вероятностью должно формироваться такими адресами документов, которые (а) находятся в первых позициях ранжированного списка, построенного поисковой системой, и (б) присутствуют в списках результатов, полученных при выполнении всех или большинства запросов.
Опишем подход к решению этой задачи с помощью генетического алгоритма. Отметим, что теория и практика применения генетических алгоритмов — «адаптивных поисковых методов, основанных на селекции лучших элементов в популяции» [2] — в настоящее время является обширным направлением в решении задач оптимизации и моделирования.
Исходная популяция. Предположим, что исходная популяция будет состоять из особей — поисковых запросов. Пусть каждый поисковый запрос образуется парой ключевых слов (генов). В этом случае исходную популяцию из 
запросов можно представить множеством 
, 
, 
, 
, где 
— случайно образованная пара и 
.
Количество запросов в исходной популяции является параметром алгоритма и должно быть задано.
Целевая функция. Значения целевой функции должны определять приспособленность особей популяции. В нашем случае приспособленность особи может быть интерпретирована как способность соответствующего поискового запроса сгенерировать такие результаты, которые попадают в следующее поколение популяции.
Пусть
— частота появления адреса документа в результатах выполнения поисковых запросов, вычисляемая следующим образом: 
, где 
— количество появлений адреса документа в результатах выполнения поисковых запросов. Отметим, что 
, 
, а также 
, если адрес документа появился в результатах выполнения всех запросов.
Далее, пусть 
— позиция в списке первых 
результатов выполнения поискового запроса 
, а 
— средний номер позиции адреса документов в списке результатов выполненных поисковых запросов, где данный адрес документа присутствует. Тогда 
, где 
— число запросов, в результатах которых присутствует данный адрес документа.
Для нормировки на диапазон от 0 до 1 можно использовать линейное преобразование 
, где 
— нормированное значение , 
и 
— соответственно минимальное и максимальное значения из всех рассчитанных на текущем шаге, 
.
Вес каждого результата, полученных после выполнения всех запросов можно вычислить по следующей формуле: 
. Значение 
определяет позицию 
результата в общем для всех запросов списке результатов.
Значение целевой функции для каждого запроса (приспособленность особи) вычисляется как средний вес результатов запроса 
, где — количество адресов документов, рассматриваемых как результат поискового запроса. Эта величина является параметром алгоритма и должна быть задана.
Селекция особей. Операция селекции должна обеспечивать участие в формировании следующего поколения только тех особей, у которых значение целевой функции 
не меньше некоторой пороговой величины. Например, среднего значения 
по текущей популяции: 
, где 
— значение целевой функции (приспособляемости особи) для каждого из запросов.
Выбор родительских пар. Здесь целесообразно использовать метод генотипного аутбридинга. Первая родительская особь выбирается случайно, а второй особью будет являться максимально «далекая» от первой. Расстояние между особями может быть вычислено как 
. Такой подход позволит обеспечить максимально полное участие всех текущих запросов в формировании следующего поколения запросов.
Скрещивание. Как указывалось выше, каждая особь (поисковый запрос) популяции состоит из пары ключевых слов, то есть . Отметим, что каждому ключевому слову 
соответствует множество его синонимов 
. Для скрещивания будем применять операцию дискретной рекомбинации, которая соответствует обмену генами между особями (в нашем случае обмену ключевыми словами между запросами).
Особенность предлагаемой реализации операции скрещивания состоит в том, что ключевое слово запроса-родителя замещается не ключевым словом другого запроса-родителя, а его синонимом 
. Это позволяет генерировать существенно больше запросов-потомков при сохранении свойств (семантики) запросов-родителей.
Проиллюстрируем предлагаемую реализацию операции скрещивания на примере. Пусть на предыдущем шаге алгоритма отобраны две родительских пары: 
и 
.
Пусть для запроса-потомка 
в качестве первого гена отобран второй ген первого запроса-родителя, а в качестве второго гена – первый ген второго запроса-родителя. Тогда, в результате скрещивания с учетом синонимии можем получить следующий запрос 
.
Мутация. Суть мутации в рассматриваемом подходе заключается в изменении случайно выбранного гена в особи (ключевого слова запроса). Вероятность мутации 
может быть фиксированным случайным числом на отрезке [0; 1]. Как правило, 
Далее, поскольку число ключевых слов в запросе фиксировано, невозможно применение таких операторов мутации, как: присоединение нового гена, вставка нового гена, удаление гена. Также, обмен местами членов пары 
в контексте выполнения поисковых запросов лишен смысла.
Поэтому наиболее адекватной операцией мутации можно считать замена ключевого слова в запросе (или гена в особи). В этом случае порядок шагов мутации особи может быть таким:
· Для каждого запроса замена с вероятностью 
случайного ключевого слова запроса его синонимом.
· Если на предыдущем шаге мутация не произошла, то замена с вероятностью 
случайного ключевого слова запроса ключевым словом, случайно выбранным из множества .
Вычисление значений целевой функции. Вычисление значений целевой функции для запросов проиллюстрируем на примере. Пусть исходная популяция включает три запроса: 
, а значение 
.
Результаты выполнения этих запросов могут быть сведены в табл. 1
Таблица 1.
Нужна помощь в написании статьи?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.
Результаты выполнения этих запросов
Результаты расчетов промежуточных параметров целевой функции представлены в табл. 2, а значения целевой функции для запросов – в табл. 3.
Таблица 2.
Промежуточные параметры целевой функции
