30. Линейная модель механизма поиска по логическому выражению.

Логическое выражение-это последовательность терминов, объединенных знаками логических операций; синтаксическая конструкция языка, вычисляющая величины, которые принимают значение «0» или «1».

Логические операции: AND, OR, XOR, NOT.

Первый этап вычисления логического выражения может состоять в построении двоичного дерева операций. Все логические операции (кроме операции НЕ) являются бинарными, могут представить любое логическое выражение запроса в виде несбалансированного двоичного дерева, прохождение по которому снизу вверх приводит к получению результата. В узлах такого дерева, включая корневую вершину, расположены логические операции (o_i), а листья (конечные узлы) представляют собой строки матрицы L₀, соответствующие терминам запроса ().

Будем называть операндом запроса отдельно вычисляемое выражение, соответствующее поддереву запроса.

Рассмотрим расширенную матрицу «термин-документ» L^’₀, строки которой могут представлять собой не только показатели встречаемости терминов в документах информационного массива, но и результирующие векторы запросов (Qi)

, где ,D- словарь.

K – количество включенных в матрицу результирующих векторов запросов,

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

Тогда алгоритм разрешения двоичного дерева поискового запроса состоит в последовательном выполнении снизу вверх логических операций и в пополнении на каждом шаге матрицы L₀ очередной строкой-результатом.

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

31. Линейная модель механизма поиска документов-аналогов.

Аналоги документа- документы, имеющие заданное количество общих терминов с исходными документами.

Выделим в матрице L₀ столбец , соответствующий поисковому образу документа (ПОД) рассматриваемого документа, и построим подматрицу L_doc, оставив в матрице L₀ те строки, в которых . По матрице L_doc строится результирующий вектор запроса на поиск аналогов (Q_doc ) и м.б. получен поисковый результат с учетом (или без) некоторого заданного порога «близости» (m).

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

Рассмотрим реализацию процедуры поиска аналогов для случая:

, Тогда ПОД заданного документа представляет собой объединение ПОДов, построенных для различных структурных единиц:, а подматрица аналогов - соединение подматриц:(,…,)’

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

Используя матрицу вместо матрицы L₀ в модели поиска по логическому выражению, можно выполнять процедуры построения дерева запроса с последовательным вычислением результата.

32. Линейная модель механизма эвристического поиска.

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

Шаг 1. Построение словника по массиву релевантных документов. Результатом является подматрица L_rel матрицы L₀, построенная путем выбора столбцов, характеризующих заданные пользователем документы:

n – количество документов, отмеченных пользователем как релевантные.

Шаг 2. Оценка терминов словника и построение Поискового Образа Темы (ПОТ).

Результатом оценивания должно быть выделение тех терминов, которые могут быть включены в ПОТ. Желательно, чтобы в основе формальной оценки лежали частотные характеристики, которые могут быть получены из матриц L₀ и L_rel:

(или i-тый элемент главной диагонали матрицы ),

(или i-тый элемент вектора ),

где F_i – частота термина в информационном массиве, F_iRel – частота термина в множестве релевантных документов, Q_rel – вектор релевантных документов (строка расширенной матрицы ).

Для оценки степени соответствия термина ПОТ может быть использована мера точности термина - отношение частоты термина в множестве релевантных документов к частоте термина в информационном массиве, в качестве порога для отбора в ПОТ – относит коэффициент CR, вычисляемый в зависимости от эвристического параметра n_s, характеризующего количество ожидаемых документов. Эвристический параметр характеризует минимальную (ненулевую) точность термина, возможную в ожидаемой выдаче:. В ПОТ отбираются термины, для кот выполняется неравенство:(4.12)

Шаг 3. Построение матрицы «термин-документ» для функции поиска аналогов. На этом шаге из матрицы L_rel должны быть удалены строки, для кот не выполняется неравенство. В результате получаем матрицу L_ПОТ:

, где M – количество терминов в ПОТ, определяющее порог «близости» для следующего шага.

Шаг 4. Выполнение функции поиска аналогов с пороговым значением M. По матрице L_ПОТ строится результирующий вектор запроса на отбор документов-аналогов (Q_ПОТ ) и формируется поисковый результат с учетом порога близости M. Если число документов полученного результата меньше, чем заданное в системе n_s, то пороговое значение M уменьшается на 1, и повторяется процедура поиска аналогов с новым пороговым значением. Таким образом, на каждой i-ой итерации пороговое значение равно M–i.

Цикл заканчивается: либо после выполнения очередной итерации число документов результата стало равно или превысило значение n_s, либо пороговое значение стало равно 0.

32. Линейная модель механизма поиска по технологии обратной связи по релевантности терминов.

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

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

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

Шаг 1. Построение и ранжирование словника релевантных документов.

Рез-том этого шага является вектор где k – количество терминов релевантных документов, а w_i - значение весового коэффициента для i-го термина, удовлетворяющее неравенству . Расчеты весовых коэффициентов могут основываться на различных мерах близости и на этом шаге не влияют на количество выдаваемых пользователю терминов (пользователь получает оценку всех терминов релевантных документов, которые находятся в частотном словаре).

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

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

Шаг 2. Формирование матрицы поисковых результатов.

Термины, отобранные пользователем на предыдущем шаге, рассматриваются как исходные для проведения поиска по совпадению терминов. Модель этого механизма поиска реализована построением подматрицы запроса (L_q), в которой отдельные строки могут быть нулевыми.

Рассмотрим подматрицу L_q как исходную для проведения процедуры поиска аналогов и последовательно для каждого ненулевого столбца построим вектор Q_i – результат поиска аналогов с max-ым порогом близости (задается количеством единиц в столбце, а контекст результата задается перечислением самих терминов). Полученные векторы рассмотрим как строки матрицы поисковых результатов:

,где n – количество ненулевых столбцов подматрицы L_q.

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

32. Матрицы ассоциации документов, терминов и их свойства.

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

l_i – совокупность лексических единиц некоторого документа (сообщения), который является элементом некоторого потока L:

Аналогично универсальному словарю введём понятие универсально массива L₀(прообразы – поисковый массив ИПС, отраслевой справочно-информационный фонд, массив библиотеки), подмножеством которого являются все документы:

Где n₀– мощность множества L₀.

Линейное представление теоретико-множественного образа документа:

Универсальный массив в линейном представлении есть матрица размерности D*n₀:

Подобные матрицы – матрицы «термин-документ». Каждый столбец соответствует документу и описывает множество терминов, содержащихся в нём.

Строка соответствует отдельному термину и является перечнем документов, содержащих данный термин.

32. Типология и показатели оценки эффективности информационного поиска. Определение первичных координат описания выхода ИПС.

При комплексной оценке учитываются два вида критериев:

экономический – денежные и временные затраты, необходимые для выполнения задачи

технический – способность обеспечить потребителям требуемый уровень информационного обслуживания

Существует анализ экономической эффективности затрат и анализ соотношения затраты - выигрыш.

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

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

Анализ эффективности затрат должен основываться:

• Четко определенные цели

• Для достижения целей должны быть предусмотрены альтернативы

• Определена стоимость альтернатив

• Создание модели для связи целей и альтернатив

• Ранжирование альтернатив путем оценки затрат и ожидаемой эффективности

Когда задан объем работы, основные альтернативы и выбор вариантов относятся к операциям индексирования и ввода документов, а также к процессам поиска и вывода информации.

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

Техническая эффективность. В этом вопросе существует 2 точки зрения-пользователя и администратора.

Оценки технической эффективности, интересующие пользователей:

• полнота поиска – способность выдавать все релевантные документы

• точность поиска – способность отбрасывать все нерелевантые документы

• усилия – на формулирование запросов и просмотр выданной информации

• время поиска

• форма представления выдачи (вопросы интерфейса)

• полнота информационного массива- степень охвата всех релевантных документов

Методика измерения показателей эффективности:

• затраты труда пользователей выражается через время, необходимое на формулирвоание запроса и тд

• время реакции системы

• форму представления выдачи оценивают в процентном отношении к полному тексту

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

Первичные координаты описания выхода ИПС, представляющие соотношение множеств выданных и невыданных документов:

Диаграмма <L> - соотношение множеств L₀-всего информационного потока, L^и- множество истинно релевантных документов и L^c- множество документов, выданных системой в ответ на поисковый запрос.

Таблица сопряженности <a,b,c,d> отображает количественное соотношение выданных системой множеств релевантных и нерелевантных документов и невыданных множеств релевантных и нерелевантных документов.

Диаграмма <n,x> -сочетание числа выданных релевантных (х) и всего выданных (n) документов.

32. Основные частные и интегральные критерии оценки АИПС.

На основе первичных координат построены частные показатели оценки технической эффективности:

• Полнота- доля выданных релевантных документов по сравнению с их общим количеством в информационном массиве: r=a/(a+c)= x/x₀=|L^И ∩L^C|/|L^И|

• Точность – доля релевантных документов во множестве выданных: p=a/(a+b)=x/n=|L^И ∩L^C|/|L^C|

• Специфичность- доля невыданных документов по сравнению с невыданными и выданными нерелевантными: σ=d/(b+d)=1- (n-x)/(n₀ – x₀)=|L₀\ (L^И UL^C)| / |L₀\L^И|

• Общность- характеризует качество комплектования поискового массива ( доля релевантных документов в информационном массиве): p₀=(a+c)/(a+b+c+d)=n/n₀=|L^И|/|L₀|

• Относительный объем выдачи: v=(a+b)/(a+b+c+d)=n/n₀=|L^C|/|L₀|

Отдельно взятое значение одного из частных показателей не отражает качество выдачи, поэтому обычно их используют парами <r,p>, <v,r> и тд. Пары показателей могут быть интерпретированы как прямоугольные координаты, тогда выдача системы отображается точкой на соответствующей плоскости.

Координаты <v,r> получаются путем нормирования к единице координат <n,x>, при этом заштрихованные области диаграммы соответственно сжимаются до треугольника с меньшей стороной, равной р_0. Т.к. р₀ очень мало, этими областями можно пренебречь и в дальнейшем координаты <v,r> могут изображаться в форме квадрата без указания областей.

Интегральные показатели оценки технической эффективности.

Использование частных показателей неудобно, т.к. невозможно определить какая из выдач будет предпочтительнее- с координатами <r₁,p₁> или <r₂,p₂>, если p1<p2 и r1>r2. Это вызывает необходимость построения интегральных показателей. Если частные показатели p,r, σ включают только часть переменных <a,b,c,d> (как правило 3), то интегральные охватывают все переменные и вполне однозначны.

Интегральные показатели: коэффициент линейной корреляции и показатель полезной работы.

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

32. Понятие рабочей характеристики АИПС.

Вывод показателя полезной работы АИПС базируется на предположении о том, что качество поиска АИПС тем выше, чем в большей степени потребитель освобождается от необходимости полного просмотра массива документов. Пусть потребителю требуются релевантные документы в количестве х. При непосредственном просмотре L0 трудозатраты (количество просмотренных документов) в среднем составляет:

В то время как при просмотре массива Lc, имеющего точность р, затраты

Работа АИПС равна разности данных величин или высвобожденной информационной деятельности потребителя:

(1)

С учётом других координат и переменных выражение примет вид:

Пусть прямые параллельны 0р0 и проходят через различные точки прямой 0И. Общее уравнение прямой, проходящей черези имеющей наклон р0, есть:

Подставим в формулу (1), имеем:

Тем самым, на прямых вида величина Сис остаётся постоянной. По мере приближения точки пересечения прямой с 0И к точке И данная константа увеличивается. Она приобретает значение, если линия проходит ниже прямой 0р0.

Таким образом, Сис удовлетворяет условиям:

Или в координатах <n,x>:

Установление пределов измерения Сис позволяет нормировать эту величину:

Мера полезной работы ИС изменяется от +1 до -1, причём:

в точке И ή=+1 (идеальная система, выдающая все релевантные и только релевантные сообщения)

в точке Д ή=-1 (система, выдающая все нерелевантные и только нерелевантные сообщения - дизинформирующая)

32. Матрицы "термин-документ", "термин-термин" и их свойства.

D-словарь, содержащий множество лексических единиц всего потока документов. Тогда

liдля всех i, где li- совокупность лексических единиц некоторого документа, который является элементом некоторого потокаL: L={l₁,…,l_i,…,l_n}, l_iL.

Существует универсальный массив L₀, подмножеством которого являются все документы:

L₀={ l₁,…,l_i,…,l_n}, l_iL₀ для всех i, причем |L₀|=n₀, где n₀- мощность множества L₀.

Линейное представление теоретико-множественного образа документа:

l_k=,где b_ik=1-еслиi-й термин входит в k-й документ;0- если не входит.

Универсальный массив в линейном представлении есть матрица размерности D*n₀:

L₀= Каждый столбец матрицы соответствует документу и описывает множество терминов, содержащихся в нем. Столбец матрицы характеризует ПОД. Строка матрицы соответствует отдельному термину и является перечнем документов, содержащих данный термин. Сумма элементов строки представляет собой частотную характеристику термина Fi, присутствующую обычно в частотном словаре информационного массива: F_i=∑b_ik.

32. Диаграмма Эйлера-Венна (диаграмма <L>). Критерии оценки АИПС в координатах <L>.

ЗдесьL₁ и L₂- множества документов, L₁₂-их пересечение, L₀-множество документов информационного массива. П₁ и П₂- множество терминов (все значимые термины, хотя бы 1 раз встречающиеся во множестве документов);П₁₂- пересечение информационных профилей;D-универсальный словарь.

Данные множества могут трактоваться: L₁ и L₂- множества документов, связанных по общему термину; П₁ и П₂- списки терминов каждого из двух документов (термины, хотя бы раз встречающиеся в документах потока или встречающиеся чаще чем некоторый порог ƒ_min или имеющие частоты, лежащие в интервале [ƒ_min, ƒ_max]

Рассмотрим случай когда L₁ и L₂- множества документов, связанных по общему термину. Выберем 2 произвольных термина T и t, входящие в какие-либо документы из L₀.

L₁- множество документов, содержащих термин T. L₂- множество документов, содержащих термин t.

X=|L₁₂|=|L1∩L₂|- количество документов, содержащих оба термина

Y= | L1\L₂|- количество документов, содержащих термин T, но не содержащих термин t.

Z= | L₂\L₁|- количество документов, содержащих термин t

V= |L₀\(L₁UL₂)|- количество документов, не содержащих ни одного из терминов.

X+y+z+v=|L₀|=n₀

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

40. Таблица сопряженности. Критерии оценки АИПС в координатах <a,b,c,d>.

Таблица сопряженности <a,b,c,d> отображает количественное соотношение выданных системой множеств релевантных ( с точки зрения потребителя) и нерелевантных документов и невыданных множеств релевантных и нерелевантных документов.

	Реле- вантные	Нереле- вантные
Выданные	a	b
Невыданные	c	d

Взаимосвязь представленных координат:

и с

Число выданных релевантных документов:a=x= |L∩L| ;

и

Общее число релевантных документов:a+ с =x۪= |L| ;

c

Количество выданных документов:a+ b =n= |L| ;

Общее число документов L0 :a+ b +x+d=n0 = |L0| ;

cи

Число выданных нерелевантных документов:b=n – x = | L \ L |

и c

Число невыданных релевантных документов:b=x0 – x = |L \ L | ;

c

Число невыданных документов:c + d = n0 – n = |L0 \ L | ;

и

Число нерелевантных документов:b + d = n0 – x0 = |L0\L | ;

и с

Число невыданных нерелевантных документов:d = n0 – x0 - (n - x) = |L0\ (L U L )|

41. Диаграмма <n,x>. Критерии оценки АИПС в координатах <n,x>.

Допустимые выдачи (имеющие смысл сочетания числа выданных релевантных – х и всего выданных документов - n) находятся в незаштрихованной области 0Иp0Д, ограниченной прямыми линиями:

0И: x = n; Ир0: х = х0; p0Д: х = n – (n0 – x0); Д0: х = 0

Взаимосвязь представленных координат:

и с

Число выданных релевантных документов:a=x= |L∩L| ;

и

Общее число релевантных документов:a+ с =x۪= |L| ;

c

Количество выданных документов:a+ b =n= |L| ;

Общее число документов L0 :a+ b +x+d=n0 = |L0| ;

cи

Число выданных нерелевантных документов:b=n – x = | L \ L |

и c

Число невыданных релевантных документов:b=x0 – x = |L \ L | ;

c

Число невыданных документов:c + d = n0 – n = |L0 \ L | ;

и

Число нерелевантных документов:b + d = n0 – x0 = |L0\L | ;

и с

Число невыданных нерелевантных документов:d = n0 – x0 - (n - x) = |L0\ (L U L )|