Комбинаторный подход к оптимальному представлению текстовых документов информационно-поисковых систем

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

Кубанский государственный технологический университет

Комбинаторный подход к оптимальному представлению текстовых документов информационно-поисковых систем

Занин Дмитрий Евгеньевич, аспирант

Кранодар

Аннотация

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

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

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

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

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

Дано:

1. Множество V критериев значимости (значимости запросов) информационно-поисковой системы при поиске документов, V = {v_i}, i=1,…,n, n - общее количество критериев значимости информационно-поисковой системы на одной итерации ранжирования.

2. Множество D документов найденных ИПС {d_s}, s = 1,…,U, где U - общее количество документов найденных ИПС на одной итерации ранжирования.

3. Каждому элементу v_i множества критериев значимости, в результате статистических исследований либо экспертных оценок, сопоставлена функция цены - c_i, i=1,...,N, характеризующая степень условного "информационного" убытка владельца информационной системы, в случае оценки документа по i-му критерию.

4. Каждый документ d_j обладает некоторой релевантностью g_j, j= 1,…,M на множестве критериев запроса {v_i} и стоимостью p'_j, j= 1,…, M (затратами на его размещение в отранжированном списке результатов поиска ИПС).

Требуется:

Синтезировать алгоритм, позволяющий определить подмножество элементов из множества {d_j} документов, при котором реализуется одно из следующих условий:

- минимум суммарного ущерба, при заданной P стоимости (ограничениях на стоимость) размещения документов в отранжированном списке ИПС;

- максимум суммарной релевантности G итогового списка отранжированных документов на множестве V критериев значимости, при заданном C ущербе размещения списка.

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

Обозначим через - NM матрицу производительностей, элементы которой r_ji представляют собой релевантность документа с номером j относительно i-й позиции в итоговом списке (табл.1).

Таблица 1 - Таблица задачи о назначениях

4. Обозначим через NM матрицу неизвестных, элемент которой x_ji принимает значение 1, если документ с номером j будет находиться в позиции с номером i, и значение 0, в противном случае.

5. Ограничения математической модели представлены системой уравнений:

(1)

Здесь первое уравнения означает, что каждому документу будет назначено не более чем одна (наиболее эффективная) порядковая позиция в итоговом списке.

Требуется:

Определить матрицу назначений X, при которой имеет место критерий оптимальности:

. (2)

Задача (1) - (2) называется задачей о назначениях с аддитивным критерием оптимальности.

При рассмотрении задачи о назначениях в стандартной форме предполагается, что количество документов равно количеству позиций итогового списка: M=N. Нетрудно показать, что введением фиктивных документов или фиктивных номеров позиций математическая модель в открытой форме (1) эквивалентна модели (3).

(3)

Исходя из того, что матрица ограничений условий (3) является абсолютно унимодулярной (целочисленная матрица называется абсолютно или вполне унимодулярной, если любой ее минор равен 1, -1 или 0), то любой опорный план математической модели (3) является целочисленным, отсюда вытекает эквивалентность математических моделей (1) и (3) [1]. Кроме того, так как из условий (3) и условий неотрицательности переменных автоматически следует, что переменные не могут быть больше 0, исходная математическая модель (1) эквивалентна (с точки зрения поиска оптимального решения задачи о назначениях) математической модели с ограничениями (3), условиями M = N и ограничениями x_ji, 0, j=1,2,...,M, i=1,2,...,N. информационный текстовый сервер кун

Рассмотрим постановку задачи о назначениях в открытой форме алгоритма Куна (2)-(3). Двойственная к ней задача имеет вид [2]:

(4)

(5)

где M = N.

Не уменьшая общности, будем считать, что коэффициенты r_ji целые. Пусть y' и z' - допустимое решение задачи (4), (5), т.е. .

Допустимое решение может быть построено двумя способами. Пусть y'_j = max r_ji, где максимум берется по всем i=1,2,...,N, z'_i = 0, i=1,2,...,N. Обозначим через P множество тех пар (j,i), для которых y'_j + z'_i = r_ji. Рассмотрим простейшую задачу о назначениях с матрицей D, элементы которой d_ji = 1, если (j,i) P и d_ji = 0 в противном случае.

Способ 1. Простейшая задача о назначениях с матрицей D имеет решение, т.е. каждый документ назначается на свою позицию и каждая позиция занимается своим документом. Пусть X' - оптимальное решения простейшей задачи о назначениях, тогда X' - будет оптимальным решением и исходной задачи (2)-(3). Действительно, x_ji = 1, если (j,i) P, т.е. y'_j + z'_ji = r_ji, отсюда

т.е. по теореме о равенстве линейных форм прямой и двойственной задач , X' - оптимальное решение исходной задачи.

Способ 2. Простейшая задача о назначениях с матрицей D не имеет решения. Тогда найдется множество документов K, которые могут назначаться согласно матрице D позициям из множества Q, причем мощности множеств равны, соответственно, k и q и при этом k<q. Рассмотрим новые двойственные переменные:

y''_j = y'_j - 1 , если j K и y''_j = y'_j в противном случае;

z''_i = z'_i +1 , если i Q и z''_i = z'_i в противном случае.

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

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

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

.

Литература

1. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.- М.: Мир, 1982. - 416с.

2. Таха Х. Введение в исследование операций. Т. 1. - М.: Мир, 1985.- 282с.

3. Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. - М.: Мир, 1998.

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