Программные продукты и системы

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

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

Рассмотрим многокритериальную задачу:

                                         (1)

где каждая задача

r                                              (2)

рассматривается на конечном множестве  – векторов из линейного пространства  размерности m над полем коэффициентов .  – оператор проекции на линейное пространство , порожденное вектором q [1-3]. В  зафиксируем базис  и рассмотрим некоторую совокупность функций r. Данные функции характеризуют силу попарных связей между векторами из T, являются неотрицательными и симметричными. В литературе они получили название мер близости, или симметрик. Обозначим  множество  решений  задачи (2) через

r,             (3)

а через G – совокупность симметрик rs:

G={rs:,,, i=1,2, если , то rsrs}.

Класс G достаточно широк и применим на практике [5].

Приведем несколько примеров:

– мера близости Минковского

r1(x,y)= целое;

– мера близости Расела-Рао

r2(x,y)=();

– мера близости Танимото-Роджерса

r3(x,y)=;

– геометрическая мера близости

r4(x,y)=.

Если для решения задачи (1) использовать способы сведения к однокритериальной задаче (к примеру, путем линейной свертки), то она фактически сведется к задаче (2).

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

Введем в рассмотрение следующие понятия.

Определение. Любые два вектора t', t" будем называть сравнимыми, если для всех i= справедливо: либо , либо , где l=dim.

Неравенства вида и  будем понимать в смысле приведенного определения.

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

=: =,

при этом отметим, что , =p, pn. Обозначим через R множество

R={: =r(x,q)},

Утверждение 1. Справедливо следующее вложение: .

Доказательство. Пусть Îrs, с=1, l, lp. Если : =, j=1, , то (), а, следовательно, . Если таковых векторов нет, то .

Следствие 1. Справедливо вложение , где ={:rs } и

rs .

Подмножества R и P, которые представляют собой псевдорелевантное и релевантное подмножества векторов соответственно, являются своего рода первым приближением множеств  и  соответственно.

Следствие 2. Если  (), то подмножество  не содержит решения задачи (1) (не содержит векторов :r).

Определим далее для  вектор , где  (операция рассматривается в кольце целых чисел), с=.

Утверждение 2. Если , , с=1,l, lp, где I={} – индексы векторов базиса, соответствующие линейному подпространству , то в подмножестве  нет векторов .

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

Следствие 1. Если приведенное утверждение выполнено для всех с= , то .

Следствие 2. Если  и , то r – число векторов в соответствующем подмножестве , которые следует присоединить к подмножеству  с целью его дополнения до .

Следствие 3. Алгоритм расширения подмножества .

1.   Построить подмножество. Пусть, не ограничивая общности рассуждений,

={}, p.

2.   Определить подмножество

={}, где =, .

3.   Если все , то  и перейти к п. 7.

4.   Построить множество

5.   Для каждого  определить

.

6.   Для каждого  построить

, далее ,

где .

7.   Стоп.

Заметим, что построение подмножества R по причинам, приведенным выше, может вызвать затруднение. В этом случае следует положить  и повторить процедуру разбиения и необходимых построений.

Подытожим полученные результаты. Метод построения множества  состоит из двух этапов. Первый – построение подмножества R (этим гарантируется нахождение хотя бы одного решения задачи (1) за р векторных операций сравнения). Второй – дополнение подмножества R до множества .

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

Утверждение 3. Задачу (1) можно свести к задаче вида

rs,  

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

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

Утверждение 4. Пусть для каждого s определены различные rs, (r*s=rs, , тогда задачу (1) можно свести к задаче

,                                                            (4)

где (rs(Aquc,q)–r*s)2)1/2 – евклидово расстояние от точки r1(Aqt,q),…,rr(Aqt,q) до точки «абсолютного минимума» r*1,…,r*r в пространстве критериев.

Чтобы найти все решения задачи (3), следует получить решения каждой из задач минимизации, используя алгоритм расширения, а далее решать задачу (4) на , где Q – объединение всех присоединенных векторов.

Для нахождения всех решений рассматриваемой задачи (1) можно использовать идею алгоритма отсечения [6-8].

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

,

.

Введем следующие обозначения: I={1, …, c, …, p},

r, r.

Утверждение 5. Пусть подмножества ,  упорядочены таким образом, что справедливо .

Тогда, если , где подмножество индексов J=, то подмножества , где , не содержат решения задачи (3) (или псевдорешения уравнения (1)) в смысле рассматриваемой симметрики.

Доказательство. , следуя (5), справедливы следующие неравенства:

и соответственно

, .

Тогда по условию справедливы следующие неравенства:

r£r£r=.

Пусть . Очевидно, что . Тогда для  справедлива следующая последовательность неравенств:

rr.

С учетом определения (2) утверждение доказано.

Утверждение 6. Пусть , где r:r, , .

Тогда  не содержит решения задачи (3).

Доказательство. Пусть r, , тогда из условия следует, что .  справедливо неравенство r.

Утверждение доказано.

Следствие. Алгоритм отсечения для зада- чи (2).

1.   Вычислить значения  и , .

2.   Упорядочить  по возрастанию.

3.   Определить множества индексов J:

.

4.   Если , то векторы подмножеств  исключить из рассмотрения на принадлежность к множеству P, иначе перейти к п. 9.

5.   Определить множество индексов .

6.   Вычислить .

7.   Определить множество индексов , где r.

8.   Перейти к п. 4.

9.   Стоп.

Понятно, что в случае сведения задачи (1) к однокритериальной целесообразно использовать приведенные выше утверждения для оптимизации ее решения [9].

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

Утверждение 7. Пусть для каждого s определим различные rs, r*s=rs,  и  – множества индексов тех , которые не содержат решений соответствующих задач (2) в задаче (1). Тогда, если  : , то задачу (1) можно свести к задаче ,

где (rs(Aqt,q)–rs(Aqt*s,q))2)1/2.

Доказательство. Пусть  – множества, не содержащие псевдорешений соответствующих задач из (4). Тогда  справедливо следующее неравенство: rsrs.

Так как rs, то (rs(Aqt,q)-r*s)2½tÎT\TK < (rs(Aqt,q)-r*s)2½tÎTK.

Далее очевидно, что .

Тогда , что и требовалось доказать.

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

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

1. Решетников В.Н. Алгебраическая теория информационного поиска. // Программирование. - 1979.- № 3. - C. 78-83.

2. Решетников В.Н. Моделирование информационного поиска в информационно-поисковых системах. // Кибернетика. - 1979. - №5. - C. 129-132.

3. Решетников В.Н. Алгебраические модели информационного поиска. // Математические методы в исследовании операций. -М.: Изд-во МГУ, 1981. - С.186-192.

4. Boyce B., Kraft D.H. Principles and theories in information science. // Annv.Rev.Inf.Sci.Tech.1985.20.P.153-178.

5. Лейбкинд А.Р., Рудник Б.В. Моделирование организационных структур. - М., 1981.

6. Сотников А.Н. Алгоритм отсечения для различных мер сходства в задаче информационного поиска. // Вестник Моск. ун-та. Сер.15: Вычисл. матем. и киберн. - 1986. - №1. - С.70-77.

7. Решетников В.Н., Сотников А.Н. Алгоритмы отсечения для построения псевдорелевантных множеств.//Программное обеспечение вычислительных комплексов. - М.: Изд-во МГУ, 1985. - С.60-64.

8. Терехин А.Н. О применимости алгоритма отсечения для решения задач многокритериального информационного поиска. // Вестник Моск. ун-та. Сер.15: Вычисл. матем. и киберн. - 1989. - №4.- С.57-62.

9. Терехин А.Н., Пшенко С.Ю. О решении многокритериальных задач информационного поиска на матричных архивах. // Программное обеспечение и модели системного анализа. - М.: Из-во МГУ, 1991.- С.19-26.

10. Cотников А.Н. Терехин А.Н. Методы исследования задач псевдорелевантного информационного поиска. // Вопросы кибернетики. Анализ больших систем. - М., 1992. - С. 166-178.