Бочкарёва Д.И., аспирант кафедры информационных технологий КубГУ

КубГУ (Краснодар)

Ранжирование результатов поиска с учетом различных категорий поискового объекта

В условиях развития информационного общества меняется отношение, как к самой информации, так и к поиску информации. В настоящее время центральным звеном процедур информационного поиска является уже не сам поиск информации, а ранжирование (сортировка) найденных документов. Показательным примером является ранжирование результатов работы систем поиска информации в Интернете, когда найденные документы ранжируются по степени соответствия запросу (релевантности). Без эффективного ранжирования результаты поиска теряют смысл, так как могут включать в себя ссылки на десятки и сотни тысяч документов. [1] При этом содержательная релевантность документа, трактующаяся как соответствие документа информационному запросу, определяемое неформальным путем [2], с каждым днем учитывает все больше различных внешних и внутренних критериев.

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

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

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

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

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

Рассмотрим подробно предложенный алгоритм:

Пусть в разрабатываемой нами поисковой системе имеется база объектов. Каждый объект характеризуется произвольным количеством параметров. Каждый объект относится к нескольким категориям по разным критериям. Осуществляется поиск подходящего объекта по произвольному выбору параметров. Разработаем формулу релевантности объекта набору параметров.

Пусть – категория объекта. j - номер категории, j= . Пусть Aⁱ – определенное значение категории, i – номер принимаемого значения. Каждая категория принимает m_i различных значений. i = , т.е. A_j = (A_j¹, A_j² … ).

Пусть – значение параметра k, определенного пользователем, участвующего в поиске. k= , где l – количество всех выбранных параметров, участвующих в поиске данного объекта.

Введем переменную , которая показывает вероятность, что объект, принимающий значение параметра , критерий принимает значение i.

Тогда для заданных - значений, найдем , где k= , - вероятность совмещения событий для всех выбранных параметров. То есть найдем вероятность, что рецепт в категории принимает значение i.

Так для первого критерия :

Далее находим max , он и определяет значение i для категории для наиболее релевантного объекта.

Если имеется два одинаковых произведения = , то приоритет отдается тому, в расчете которого участвует большая . То есть имеется большая вероятность выбора этого критерия.

Аналогично находятся значения всех категорий.

max и определяем i для заданной .

Таким образом, мы найдем значения по всем категориям, которым должен удовлетворять наиболее релевантный объект, наряду с выбранными параметрами. Найдем ( , ) и соответствующие ему i = (i₁ i₂ … i_n).

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

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

Допустим, у нас 3 категории и есть набор наибольших произведений ( ), характеризующий значения категорий, i = (1,3,2). А перед этими произведениями по величине находятся произведения ( ). Тогда вычисляем:

z1= - , z2= - , z3= - .

Допустим, z3<z2<z1. Тогда новый набор, характеризующий значения критериев будет:

, i = (1,3,3).

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

Рассмотрим, как работает данный алгоритм в конкретных областях.

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

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

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

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

Таблица 1 – Пример расчета

№	aj bk	помидоры	огурцы
1	супы	2/13	2/12	=	= 4/156
2	салаты	7/13	7/12		= 49/156
3	вторые блюда	2/13	1/12		= 2/156

Далее находим max , он и определяет значение категории «тип блюда» для наиболее релевантного рецепта. Для нашего примера это i=2 , т.е. искомый рецепт должен принадлежать типу салаты.

Аналогично находим для второго критерия «кухня».

№	aj bk	помидоры	огурцы
1	русская	2/13	3/12	=	= 6/156
2	японская	2/13	1/12		= 2/156

Находим max - это i=1 – русская кухня.

Мы получили вектор i = (1,2), который характеризует наиболее релевантный рецепт и означает, что будем искать рецепт содержащий ингредиенты помидоры и огурцы и принадлежащий типу салаты и русской кухне. Далее выведя все такие рецепты ослабляем поиск.

Берем предыдущее произведение, по категории, где разница между наибольшими произведениями меньшая:

(6/156-2/156) < (49/156-4/156)

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

Таким образом, мы получим выдачу, ранжированную по релевантности.

Библиографический список

1. Методы информационного поиска и ранжирования документов в компьютерных сетях Горбунов, Андрей Леонидович — 05.13.13 — Москва, 2005 Диссертация.

2. Словарь по кибернетике / Под редакцией академика В. С. Михалевича. — 2-е. — Киев: Главная редакция Украинской Советской Энциклопедии имени М. П. Бажана, 1989. — 751 с. — (С48).