Реферат: Стратегия поиска в автоматизированных информационных системах

КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ КУЛЬТУРЫ И ИСКУССТВ

Кафедра информатики

Вступительныйреферат по теме:

Стратегия поиска в Автоматизированных информационно-поисковыхсистемах

Выполнил:

Султанов Ильнур Ильдусович

Казань, 2004
Содержание

 TOC o «1-3» h z u Введение. PAGEREF _Toc84433917 h 3

Проблемыпоиска информации. PAGEREF _Toc84433918 h 5

Поисковыеалгоритмы… PAGEREF _Toc84433919 h 7

Оценкакачества. PAGEREF _Toc84433920 h 16

Дополнительныевозможности предоставляемые поисковыми машинами. PAGEREF _Toc84433921 h 18

Лингвистика. PAGEREF _Toc84433922 h 20

Заключение. PAGEREF _Toc84433923 h 22

Списоклитературы… PAGEREF _Toc84433924 h 23

Глоссарий:PAGEREF _Toc84433925 h 24

<span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-font-kerning:16.0pt;mso-ansi-language: RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">
Введение

<span Arial",«sans-serif»">Проблема поиска и сбораинформации ‑ одна из важнейших проблем информационно поисковых систем.Конечно, нельзя сравнивать в этом отношении, скажем, средние века, когда поискинформации был проблемой потому, что этой информации было мало, и требовалисьусилия только для того, чтобы найти хоть что-то по более или менеезначительному интересующему вопросу. Проблема поиска информации приобрела новыйхарактер в 20-м столетии, с началом развития века информационных технологий.Теперь она заключается не в том, что информации мало и поэтому ее трудно найти,а в том, что ее теперь наоборот становится все больше и больше, и от этогонайти ответ на интересующий вопрос может оказаться тоже довольно сложнойзадачей [2].

<span Arial",«sans-serif»">Так, сначалапоявилась возможность пойти в библиотеку и, потратив там время на выбор нужнойкниги по каталогу, найти необходимую информацию. Но каталоги не решаютполностью проблем поиска информации даже в рамках одной библиотеки, так как вкаталожную запись входит относительно мало информации: заголовок, автор, местоиздания и т.п. Проблема поиска информации значительно усложняется прииспользование виртуальных источников. Здесь используется технология онлайновыхкаталогов, в результате применения которой пользователь имеет возможностьвыполнять поиск в каталогах сразу нескольких библиотек, чем, на самом деле, ещебольше усложняет себе задачу, но, с другой стороны, увеличивает шансы решить ее[1].

<span Arial",«sans-serif»">На современном этапе всеинформационное пространство, в котором мы живем, все больше погружается вИнтернет. Интернет становится основной формой существования информации, неотменив традиционных, такие как журналы, радио, телевидение, телефон,всевозможные справочные службы.

<span Arial",«sans-serif»">Вданной работе объектом исследованияявляется Автоматизированная информационно поисковая система. Это система гдехранится информационный массив, из которого пользователю выдается нужнаяинформация, осуществляющаяся либо автоматически, либо вручную.

<span Arial",«sans-serif»">Предмет исследования

<span Arial",«sans-serif»"> включает в себя те свойства, стороныи отношения объекта исследования, которые необходимо изучить. Предметобозначает границы, в пределах которых объект изучается в данном конкретномисследовании. Предметом исследования является стратегия информационного поиска.

<span Arial",«sans-serif»">Цель исследования

<span Arial",«sans-serif»">: Цель исследования ставится, обзор ивыявление поисковых сервисов (возможностей предоставляемые на сегодняшний день),написание рекомендации к проведению поиска, анализ развития поисковых систем.

<span Arial",«sans-serif»">Для выполненияпоставленной цели в рамках исследования необходимо решение следующих задач:

<span Arial",«sans-serif»; mso-fareast-font-family:Arial"><span Times New Roman"">       

<span Arial",«sans-serif»">аналитический обзорпоисковых систем;

<span Arial",«sans-serif»; mso-fareast-font-family:Arial"><span Times New Roman"">       

<span Arial",«sans-serif»">определение механизма поискав поисковых системах;

<span Arial",«sans-serif»; mso-fareast-font-family:Arial"><span Times New Roman"">       

<span Arial",«sans-serif»">создание информационнойсистемы, по АИПС;

<span Arial",«sans-serif»; mso-fareast-font-family:Arial"><span Times New Roman"">       

<span Arial",«sans-serif»">оценка эффективностисозданной системы;

<span Arial",«sans-serif»; mso-fareast-font-family:Arial"><span Times New Roman"">       

<span Arial",«sans-serif»">разработка рекомендаций к проведениюпоиска используя информационную систему.<span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-font-kerning:16.0pt;mso-ansi-language: RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">
Проблемы поиска информации

<span Arial",«sans-serif»">Ключ проблемы заключается в том, что вырослоколичество пользователей не обладающие профессиональными навыками при поискеинформации на языке запросов. Естественно с такой проблемой столкнулся нетолько интернет, но и электронные библиотеки (ЭБ) и электронные каталоги (ЭК).К таким системам относятся библиотеки НЭБ-НСН, Интегрум — Техно в России,Лексис-Нексис, Рейтер на Западе.

<span Arial",«sans-serif»">Более строгая организациякаталогов в библиотеках, полное единство форматов (или почти полное) внутриодной библиотеки не является решением проблемы современных поисковых систем.Поиск это искусство. Ясно, что в области искусства нельзя добитьсягарантированного, или массового результата.

<span Arial",«sans-serif»">Существует убеждение, чтокаждое новое поколение программ поиска совершенней предыдущего. И иная точказрения, что «все новое — это хорошо забытое старое». Думаю, что применительно кпоисковым системам истина лежит где-то посередине.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">Но что же поменялось вдействительности за последние годы? Не алгоритмы и не структуры данных, нематематические модели. Поменялась парадигма использования систем. Системойпоиска стали пользоваться пользователи не имеющие профессиональные навыки.

<span Arial",«sans-serif»">Особенно поисковые системыстали востребованы с возникновением интернета. В процессе эволюции поисковых систем, стали очевидны следующиеизменения. Во-первых, люди не только «думают словами», но и «ищут словами». Вответе системы они ожидают увидеть слово, набранное в строке запроса. Второе:«человека ищущего» трудно «переучить искать», так же как трудно переучитьговорить или писать. Научная мысль 60-х – 80-х об итеративном уточнениизапросов, о понимании естественного языка, о поиске по смыслу, о генерациисвязного ответа на вопрос, пока не удаётся создать и не выдерживает критики.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">

<span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-font-kerning:16.0pt;mso-ansi-language: RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">
Поисковые алгоритмы

<span Arial",«sans-serif»">Как илюбая программа, поисковая система оперирует со структурами данных и исполняеталгоритм. Есть четыре класса поисковых алгоритмов. Три алгоритма из четырехтребуют «индексирования», предварительной обработки документов, при которомсоздаются вспомогательный файл, сиречь «индекс», призванный упростить иускорить сам поиск. Это алгоритмы инвертированных файлов, суффиксныхдеревьев, сигнатур. В вырожденном случае предварительный этапиндексирования отсутствует, а поиск происходит при помощи последовательногопросмотра документов. Такой поиск называется прямым.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">Прямой поиск

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">Нижепредставлена простейшая его версия знакома многим.

<span Arial",«sans-serif»"><span Arial",«sans-serif»;mso-ansi-language:EN-US">char* strstr(char *big,
        char *little) {
    char *x, *y, *z;
    for (x = big; *x; x++) {
        for (y = little, z = x;
                *y; ++y, ++z)
        {
            if (*y != *z)
                break;
        }
        if (!*y)
            return x;
    }
    return 0;<span Arial",«sans-serif»;mso-ansi-language:EN-US;font-weight: normal">
} <span Arial",«sans-serif»;mso-ansi-language:EN-US"> <span Arial",«sans-serif»;mso-ansi-language:EN-US; font-weight:normal"> <span Arial",«sans-serif»;font-weight:normal">ПРЯМОЙ ПОИСК ТЕКСТА.
В этой функции языка <span Arial",«sans-serif»; mso-ansi-language:EN-US;font-weight:normal">C<span Arial",«sans-serif»;font-weight:normal"> текст строки <span Arial",«sans-serif»;mso-ansi-language:EN-US">big<span Arial",«sans-serif»;font-weight:normal"> просматривают слева направо и для каждой позиции <span Arial",«sans-serif»;mso-ansi-language:EN-US">x<span Arial",«sans-serif»;font-weight:normal"> запускают последовательное сравнение с искомой подстрокой <span Arial",«sans-serif»;mso-ansi-language:EN-US">little<span Arial",«sans-serif»;font-weight:normal">. Для этого, двигая одновременно два указателя <span Arial",«sans-serif»;mso-ansi-language:EN-US">y<span Arial",«sans-serif»;font-weight:normal"> и <span Arial",«sans-serif»;mso-ansi-language:EN-US">z<span Arial",«sans-serif»;font-weight:normal">, попарно сравнивают все символы. Если мы успешно дошли до конца искомой подстроки, значит она найдена! <span Arial",«sans-serif»"> <span Arial",«sans-serif»;font-weight:normal">

<span Arial",«sans-serif»">Несмотря на кажущуюсяпростоту, последние 30 лет прямой поиск интенсивно развивается. Было выдвинутонемалое число идей, сокращающих время поиска в разы. При этом надо учесть, чтоновые алгоритмы и их улучшенные варианты появляются постоянно.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">Хотя прямой просмотр всехтекстов – довольно медленное занятие, не следует думать, что алгоритмы прямогопоиска не применяются в интернете. Норвежская поисковая система Fast(www.fastsearch.com) использовала чип, реализующий логику прямого поиска упрощенныхрегулярных выражений, и разместила 256 таких чипов на одной плате. Этопозволяло Fast-у обслуживать довольно большое количество запросов в единицувремени.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">Кроме того, есть массапрограмм, комбинирующих индексный поиск для нахождения блока текста сдальнейшим прямым поиском внутри блока. Например, весьма популярный, в томчисле и в Рунете, glimpse.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">У прямых алгоритмов естьположительные черты. Например, неограниченные возможности по приближенному инечеткому поиску. Ведь любое индексирование всегда сопряжено с упрощением инормализацией терминов, а, следовательно, с потерей информации. Прямой же поискработает непосредственно по оригинальным документам безо всяких искажений.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">Инвертированный файл

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">Эта простейшая структураданных. Первая категория людей знает, что это такое, по «конкордансам» — алфавитно упорядоченным исчерпывающим спискам слов из одного текста илипринадлежащих одному автору (например «Конкорданс к стихам А. С. Пушкина»

<span Arial",«sans-serif»">, <span Arial",«sans-serif»">«Словарь-конкорданспублицистики Ф. М. Достоевского»). Вторые имеют дело с той или иной формойинвертированного списка всякий раз, когда строят или используют «индекс БД поключевому полю». <span Arial",«sans-serif»">

<img src="/cache/referats/18126/image002.gif" align=«left» hspace=«12» v:shapes="_x0000_s1109"><span Arial",«sans-serif»">Проиллюстрируем эту структуру припомощи замечательного русского конкорданса — «Симфонии», выпущенной московскойпатриархией по тексту синодального перевода Библии [симфония].

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">                               Рис.1

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">Перед нами упорядоченныйпо алфавиту список слов. Для каждого слова перечислены все «позиции», в которыхэто слово встретилось. Поисковый алгоритм состоит в отыскании нужного слова изагрузке в память уже развернутого списка позиций.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">Чтобы сэкономить надисковом пространстве и ускорить поиск, обычно прибегают к двум приемам.Во-первых, подробность самой позиции. Чем подробнее задана такая позиции,например, в случае с «Симофонией» это «книга+глава+стих», тем больше местапотребуется для хранения инвертированного файла.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">В наиподробнейшем вариантев инвертированном файле можно хранить и номер слова, и смещение в байтах отначала текста, и цвет и размер шрифта, да много чего еще. Чаще же просто указываюттолько номер документа, скажем, книгу Библии, и число употреблений этого словав нем. Именно такая упрощенная структура считается основной в классическойтеории информационного поиска – Information Retrieval (IR).

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">Второй (никак не связанныйс первым) способ сжатия: упорядочить позиции для каждого слова по возрастаниюадресов и для каждой позиции хранить не полный ее адрес, а разницу отпредыдущего. Вот как будет выглядеть такой список для нашей странички впредположении, что мы запоминаем позицию вплоть до номера главы:

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">ЖЕНЩИНА:[Быт.1],[+11],[0],[+2],[+4],[+2],[+4],..

<span Arial",«sans-serif»">Дополнительно наразностный способ хранения адресов накладывают какой-нибудь способ упаковки:зачем отводить небольшому целому числу фиксированное «огромное» количествобайт, ведь можно отвести ему почти столько байт, сколько оно заслуживает. Здесьуместно упомянуть коды Голомба или встроенную функцию популярного языка Perl:pack(“w”).

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">В литературе встречается иболее тяжелая система упаковочных алгоритмов самого широкого спектра: арифметический,Хафман, LZW, и т.д. Прогресс в этой области идет непрерывно. На практике впоисковых системах они используются редко: выигрыш невелик, а мощностипроцессора расходуются неэффективно.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">В результате всехописанных ухищрений размер инвертированного файла, как правило, составляет от 7до 30 процентов от размера исходного текста, в зависимости от подробностиадресации.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">занесеныв «Красную книгу»

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">Неоднократно предлагалисьдругие, отличные от инвертированного и прямого поиска алгоритмы и структурыданных. Это, прежде всего, суффиксные деревья, а также сигнатуры.

<span Arial",«sans-serif»; mso-fareast-font-family:«Arial Unicode MS»">

<span Arial",«sans-serif»">Первый из нихфункционировал и в интернете, будучи запатентованным алгоритмом поисковойситемы OpenText.

<span Arial",«sans-serif»">Мне доводилось встречатьсуффиксные индексы в отечественных поисковых системах.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">Второй — метод сигнатур — представляет собой преобразование документа к поблочным таблицам хеш-значенийего слов — «сигнатуре» и последовательному просмотру«сигнатур» во время поиска.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">Широкого распространения этидва метода не получили.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">МАТЕМАТИЧЕСКИЕМОДЕЛИ

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">Приблизительно 3 из 5поисковых систем и модулей функционируют безо всяких математических моделей. Ихразработчики не ставят перед собой задачу реализовывать абстрактную модель.Принцип здесь: лишь бы программа хоть что-нибудь находила.

<span Arial",«sans-serif»">Как только речь заходит оповышении качества поиска, о большом объеме информации, о потокепользовательских запросов, кроме эмпирически проставленных коэффициентовполезным оказывается оперировать каким-нибудь пусть и несложным теоретическимаппаратом. Модель поиска – это некоторое упрощение реальности, наосновании которого получается формула (сама по себе никому не нужная),позволяющая программе принять решение: какой документ считать найденным и какего ранжировать. После принятия модели коэффициенты приобретают физическийсмысл и становятся понятней.

<span Arial",«sans-serif»;mso-bidi-font-weight:bold">Всемногообразие моделей

<span Arial",«sans-serif»">традиционногоинформационного поиска (IR) принятоделить на три вида:теоретико-множественные (булевская, нечетких множеств, расширенная булевская),алгебраические<span Arial",«sans-serif»;mso-fareast-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA;mso-bidi-font-weight:bold">[1][1] (векторная, обобщенная векторная, латентно-семантическая,нейросетевая) и вероятностные.

<span Arial",«sans-serif»">Булевское семействомоделей самое известное, реализующие полнотекстовый поиск. Есть слово — документ считается найденным, нет – не найденным. Собственно, классическаябулевская модель – это мостик, связывающий теорию информационного поиска стеорией поиска и манипулирования данными.

<span Arial",«sans-serif»">Критика булевской модели,вполне справедливая, состоит в ее крайней жесткости и непригодности дляранжирования. Поэтому еще в 1957 году Joyce и Needham (Джойс и Нидхэм)предложили учитывать частотные характеристики слов, чтобы «… операциясравнения была бы отношением расстояния между векторами...».

<span Arial",«sans-serif»">Векторная модель

<span Arial",«sans-serif»"> и была с успехом реализована в 1968году отцом-основателем науки об информационном поиске Джерардом Солтоном(Gerard Salton)<span Arial",«sans-serif»;mso-fareast-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">[2][2] в поисковой системе SMART (Salton'sMagical Automatic Retriever of Text). Ранжированиев этой модели основано на естественном статистическом наблюдении, что чембольше локальная частота термина в документе (TF) и больше «редкость»(т.е. обратная встречаемость в документах) термина в коллекции (IDF),тем выше вес данного документа по отношению к термину. Обозначение IDF ввелаKaren Sparck-Jones  (Карен Спарк-Джоунз)в 1972 в статье про различительную силу (term specificity).С этого момента обозначение TF*IDF широко используется как синоним векторноймодели.

<span Arial",«sans-serif»;mso-bidi-font-weight:bold">Наконец,в 1977 году Robertson и Sparck-Jones (Робертсон и Спарк-Джоунз) обосновали и реализовали вероятностнуюмодель (предложенную еще в 1960), также положившую начало целому семейству.Релевантность в этой модели рассматривается как вероятность того, чтоданный документ может оказаться интересным пользователю. При этомподразумевается наличие уже существующего первоначального набора релевантныхдокументов, выбранных пользователем или полученных автоматически прикаком-нибудь упрощенном предположении. Вероятность оказаться релевантным длякаждого следующего документа рассчитывается на основании соотношениявстречаемости терминов в релевантном наборе и в остальной, «нерелевантной»части коллекции. Хотя вероятностные модели обладают некоторым теоретическимпреимуществом, ведь они располагают документы в порядке убывания«вероятности оказаться релевантным», на практике они так и неполучили большого распространения.

<span Arial",«sans-serif»;mso-bidi-font-weight:bold">Важнозаметить, что в каждом из семейств простейшая модель исходит из предположения овзаимонезависимости слов и обладает условием фильтрации: документы, несодержащие слова запроса, никогда не бывают найденными. Продвинутые(«альтернативные») модели каждого из семейств не считают слова запросавзаимонезависимыми, а, кроме того, позволяют находить документы, не содержащиени одного слова из запроса.

<span Arial",«sans-serif»; mso-bidi-font-weight:bold">

<span Tahoma",«sans-serif»; color:#400040">Сингулярным разложением действительной матрицы A размеров m*n называется всякое ее разложение вида A = USV, где U — ортогональная матрица размеров m*m, V — ортогональная матрица размеров n*n,

<span Tahoma",«sans-serif»; color:#400040"> S — диагональная матрица размеров m*n, элементы которой <span Tahoma",«sans-serif»">sij= 0, если <span Tahoma",«sans-serif»">i не равно <span Tahoma",«sans-serif»">j, и <span Tahoma",«sans-serif»">sii = <span Tahoma",«sans-serif»">si >= 0. Величины si называются сингулярными числами матрицы и равны арифметическим значениям квадратных корней из соответствующих собственных значений матрицы AAT. В англоязычной литературе сингулярное разложение принято называть SVD-разложением.<span Tahoma",«sans-serif»;color:#400040">

<span Arial Unicode MS",«sans-serif»">

<img src="/cache/referats/18126/image003.gif" align=«left» hspace=«12» =" USV, где U — ортогональная матрица размеров m*m, V — ортогональная матрица размеров n*n, S — диагональная матрица размеров m*n, элементы которой" sij=" 0, если i не равно j, и sii" =" si" >=" 0. Величины si называются сингулярными числами матрицы и равны арифметическим значениям квадратных корней из соответствующих собственных значений матрицы AAT. В англоязычной литературе сингулярное разложение принято называть SVD-разложением. " v:shapes="_x0000_s1110"><span Arial",«sans-serif»">Поиск «по смыслу»<span Arial",«sans-serif»">

<span Arial",«sans-serif»;mso-bidi-font-weight:bold">Способностьнаходить и ранжировать документы, не содержащие слов из запроса, часто считаютпризнаком искусственного интеллекта или поиска по смыслу и относятаприори к преимуществам модели.

<span Arial",«sans-serif»;mso-bidi-font-weight:bold">Дляпримера опишу лишь одну,  самуюпопулярную модель, работающую по смыслу. В теории информационного поиска даннуюмодель принято называть латентно-семантически индексированием (инымисловами, выявлением скрытых смыслов). Эта алгебраическая модель основана насингулярном разложении прямоугольной матрицы, ассоциирующей слова сдокументами. Элементом матрицы является частотная характеристика, отражающаястепень связи слова и документа, например, TF*IDF. Вместо исходноймиллионно-размерной матрицы авторы метода

<span Arial",«sans-serif»">, <span Arial",«sans-serif»;mso-bidi-font-weight:bold">предложилииспользовать 50-150 «скрытых смыслов»<span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA;mso-bidi-font-weight:bold">[3][3], соответствующих первым главнымкомпонентам <span Arial",«sans-serif»">ее сингулярного разложения.

<span Arial",«sans-serif»;mso-bidi-font-weight:bold">Доказано,что если оставить в рассмотрении первые k сингулярных чисел (остальныеприравнять нулю), мы получим ближайшую из всех возможных аппроксимацию исходнойматрицы ранга k (в некотором смысле ее «ближайшую семантическуюинтерпретацию ранга k»). Уменьшая ранг, мы отфильтровываем нерелевантныедетали; увеличивая, пытаемся отразить все нюансы структуры реальных данных.

<span Arial",«sans-serif»">Операции поиска илинахождения похожих документов резко упрощаются, так как каждому слову икаждому документу сопоставляется относительно короткий вектор из kсмыслов (строки и столбцы соответствующих матриц). Однако по причине малой лиосмысленности «смыслов», или по какой иной<span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA;mso-bidi-font-weight:bold">[4]

[4],но использование LSI в лоб для поиска так и не получило распространения. Хотяво вспомогательных целях (автоматическая фильтрация, классификация, разделениеколлекций, предварительное понижение размерности для других моделей) этотметод, по-видимому, находит применение. <span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-font-kerning:16.0pt;mso-ansi-language: RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">
Оценка качества

Consistency checking has shown that the overlap of relevant documents between any two assesors is on the order of 40% on average…cross-assesor recall and precision of about 65% …This implies a practical upper bound on retrieval system performance of 65% …<span Times New Roman",«serif»;mso-fareast-font-family:«Times New Roman»; mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">[1]

[1]

Donna Harman

What we have learned, and not learned, from TREC [harman]

 

<span Arial Unicode MS",«sans-serif»; mso-ansi-language:EN-US">

<span Arial",«sans-serif»">Каковабы ни была модель, поисковая система нуждаетсяв «тюнинге» — оценке качествапоиска и настройке параметров. Оценка качества – идея, фундаментальная длятеории поиска. Ибо именно благодаря оценке качества можно говорить оприменимости или не применимости той или иной модели и даже обсуждать ихтеоретичеcкие аспекты.

<span Arial",«sans-serif»">В частности, одним изестественных ограничений качества поиска служит наблюдение, вынесенное вэпиграф: мнения двух «асессоров» (специалистов, выносящих вердикт орелевантности) в среднем не совпадают друг с другом в очень большой степени!Отсюда вытекает и естественная верхняя граница качества поиска, ведь качествоизмеряется по итогам сопоставления с мнением асессора.

<span Arial",«sans-serif»">Обычно<span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA">[5]

[5] для оценки качества поиска меряют двапараметра:

·<span Times New Roman"">       

<span Arial",«sans-serif»">точность(precision) – доля релевантного материала в ответе поисковой системы

·<span Times New Roman"">       

<span Arial",«sans-serif»">полнота(recall) – доля найденных релевантных документов в общем числе релевантныхдокументов коллекции

<span Arial",«sans-serif»">Именно эти параметрыиспользовались и используются на регулярной основе для выбора моделей и ихпараметров в рамках созданной Американским Интститутом Стандартов (NIST)конференции по оценке систем текстового поиска (TREC — text retrival evaluationconference)<span Arial",«sans-serif»;mso-fareast-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">[6]

[6]. Начавшаяся в 1992 году консорциумом из25 групп, к 12-му году своего существования конференция накопила значительныйматериал, на котором до сих пор оттачиваются поисковые системы. К каждойочередной конференции готовится новый материал (т.н. «дорожка») по каждому изинтересующих направлений. «Дорожка» включает коллекцию документов и запросов.Приведу примеры:

·<span Times New Roman"">       

<span Arial",«sans-serif»">Дорожкапроизвольных запросов (ad hoc) – присутствует на всех конференциях

·<span Times New Roman"">       

<span Arial",«sans-serif»">Многоязычныйпоиск

·<span Times New Roman"">       

<span Arial",«sans-serif»">Маршрутизацияи фильтрации

·<span Times New Roman"">       

<span Arial",«sans-serif»">Высокоточныйпоиск (с единственным ответом, выполняемый на время)

·<span Times New Roman"">       

<span Arial",«sans-serif»">Взаимодействиес пользователем

·<span Times New Roman"">       

<span Arial",«sans-serif»">Естестственно-языковая«дорожка»

·<span Times New Roman"">       

<span Arial",«sans-serif»">Ответына «вопросы»

·<span Times New Roman"">       

<span Arial",«sans-serif»">Поискв «грязных» (только что отсканированных) текстах

·<span Times New Roman"">       

<span Arial",«sans-serif»">Голосовойпоиск

·<span Times New Roman"">       

<span Arial",«sans-serif»">Поискв очень большом корпусе (20GB, 100GB и т.д.)

·<span Times New Roman"">       

<span Arial",«sans-serif»">WEBкорпус (на последних конференциях он представлен выборкой по домену .gov)

·<span Times New Roman"">       

<span Arial",«sans-serif»">Распределенныйпоиск и слияние результатов поиска из разных систем

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">

<span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-font-kerning:16.0pt;mso-ansi-language: RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">
Дополнительные возможностипредоставляемые поисковыми машинами

<span Arial",«sans-serif»">Каквидно из «дорожек» TREC, к самому поиску тесно примыкает ряд задач, либоразделяющих с ним общую идеологию (классификация, маршрутизация, фильтрация,аннотирование), либо являющихся неотъемлемой частью поискового процесса(кластеризация результатов, расширение и сужение запросов, обратная связь,«запросо-зависимое» аннотирование, поисковый интерфейс и языки запросов). Нетни одной поисковой системы, которой бы не приходилось решать на практике хотябы одну из этих задач.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">Зачастую наличие того илииного дополнительного свойства является решающим доводом в конкурентной борьбепоисковых систем. Например, краткие аннотации состоящие из информативных цитатдокумента, которыми некоторые поисковые системы сопровождают результаты соейработы, помогают им оставаться на полступеньки впереди конкурентов.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">Обо всех задачах испособах их решения рассказать невозможно. Для примера рассмотрим «расширениезапроса», которое обычно производится через привлечение к поискуассоциированных терминов. Решение этой задачи возможно в двух видах – локальном(динамическом) и глобальном (статическом). Локальные техники опираются на текстзапроса и анализируют только документы, найденные по нему. Глобальные же«расширения» могут оперировать тезаурусами, как априорными (лингвистическими),так и построенными автоматически по всей коллекции документов. По общепринятомумнению, глобальные модификации запросов через тезаурусы работают неэффективно,понижая точность поиска. Более успешный глобальный подход основан напостроенных вручную статических классификациях, например, ВЕБ-директориях. Этотподход широко использутся в интернет-поисковиках в операциях сужения илирасширения запроса.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">Нередко реализациядополнительных возможностей основана на тех же самых или очень похожихпринципах и моделях, что и сам поиск. Сравните, например, нейросетевуюпоисковую модель, в которой используется идея передачи затухающих колебаний отслов к документам и обратно к словам (амплитуда первого колебания – все тот жеTF*IDF), с техникой локального расширения запроса. Последняя основанна на обратнойсвязи (relevance feedback), в которой берутся наиболее смыслоразличительные(контрастные) слова из документов, принадлежащих верхушке списка найденного.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»">К сожалению, локальные методырасширения запроса, несмотря на эффектные технические идеи типа «Term VectorDatabase» и очевидную пользу, все еще остаются крайне дорогими.

<span Arial",«sans-serif»">

<span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-font-kerning:16.0pt;mso-ansi-language: RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">
Лингвистика

<span Arial",«sans-serif»">Немногов стороне от статистических моделей и структур данных стоит класс алгоритмов,традиционно относимых к лингвистическим. Точно границы между статистическим илингвистическими методами провести трудно. Условно можно считатьлингвистическими методы, опирающиеся на словари (морфологические,синтаксические, семантические), созданные человеком. Хотя считается доказанным,что для некоторых языков лингвистические алгоритмы не вносят существенногоприроста точности и полноты (например, английский), все же основная массаязыков требует хотя бы минимального уровня лингвистической обработки. Приведутолько список задач, решаемый лингвистическими или окололингвистическимиприемами:

<span Arial",«sans-serif»">

·<span Times New Roman"">       

<span Arial",«sans-serif»">автоматическоеопределение языка документа

·<span Times New Roman"">       

<span Arial",«sans-serif»">токенизация(графематический анализ): выделение слов, границ предложений

·<span Times New Roman"">       

<span Arial",«sans-serif»">исключениенеинформативных слов (стоп-слов)

·<span Times New Roman"">       

<span Arial",«sans-serif»">лемматизация(нормализация, стемминг): приведение словоизменительных форм к «словарной». Втом числе и для слов, не входящих в словарь системы

·<span Times New Roman"">       

<span Arial",«sans-serif»">разделениесложных слов (компаундов) для некоторых языков (например, немецкого)

·<span Times New Roman"">       

<span Arial",«sans-serif»">дизамбигуация:полное или частичное снятие омонимии

·<span Times New Roman"">       

<span Arial",«sans-serif»">выделениеименных групп

<span Arial",«sans-serif»">Еще реже в исследованиях ина практике можно встретить алгоритмы словообразовательного, синтаксического идаже семантического анализа. При этом под семантическим анализом чащеподразумевают какой-нибудь статистический алгоритм (LSI, нейронные сети), аесли толково-комбинаторные или семантические словари и используются, то вкрайне узких предметных областях.

<span Arial",«sans-serif»; mso-fareast-font-family:«Times New Roman»;mso-font-kerning:16.0pt;mso-ansi-language: RU;mso-fareast-language:RU;mso-bidi-language:AR-SA">
Заключение

<span Arial",«sans-serif»">Преждевсего, очевидно, что поиск в большом информационном массиве, не может бытьсколько-нибудь корректно выполнен, будучи основан на анализе одного лишь текстадокумента. Ведь внетекстовые (off-page) факторы играют порой и большуюроль, чем текст самой страницы. Положение на сайте, посещаемость,авторитетность источника, частота обновления, цитируемость страницы и ееавторов – все эти факторы играют важную роль.

<span Arial",«sans-serif»">Cтав основным источником получения справочнойинформации для человека, поисковые системы стали основным источником трафикадля интернет -сайтов. Как следствие, они немедленно подверглись «атакам»недобросовестных авторов, желающих оказаться в первых страницах результатовпоиска. Искусственная генерация входных страниц, насыщенных популярнымисловами, техника клоакинга, «слепого текста» и многие другие приемы,предназначенные для обмана поисковых систем.

<span Arial",«sans-serif»">Кроме проблемы корректногоранжирования, создателям поисковых систем пришлось решать задачу обновления исинхронизации колоссальной по размеру коллекции с гетерогенными форматами,способами доставки, языками, кодировками, массой бессодержательных идублирующихся текстов. Необходимо поддерживать базу в состоянии максимальнойсвежести, может быть учитывать индивидуальные и коллективные предпочтенияпользователей. Многие из этих задач никогда прежде не рассматривались втрадицонной науке информационного поиска.

<span Arial",«sans-serif»;mso-fareast-font-family: «Times New Roman»;mso-font-kerning:16.0pt;mso-ansi-language:RU;mso-fareast-language: RU;mso-bidi-language:AR-SA">
Списоклитературы

<span Arial",«sans-serif»">

<span Arial",«sans-serif»;

еще рефераты
Еще работы по компьютерным сетям