Лекции

21

личительная сила становится положительной. В противном случае значение различительной силы отрицательно.

2.4.2. Распределение частоты встречаемости терминов

Практика показывает, что хорошие, средние и плохие индексационные термины

можно характеризовать по распределению их документной частоты (DF)i и рас-

1.Лучшими для индексации терминами с наивысшими значениями различительной силы являются термины со средними значениями суммарной частоты встречае-

мости Fi и документной частотой, составляющей менее половины его частоты как

термина (суммарной частоты в массиве).

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

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

Рис. Рис. 8 иллюстрирует вышеописанное разделение терминов. Если располо-

жить термины в порядке увеличения документной частоты (DF)i , то индексацион-

ные термины должны, насколько это возможно, попадать в средний интервал значений.

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

23

2.5. Определение весов терминов

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

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

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

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

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

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

– нулевой вес. Таким образом, все термины из поискового образа документа считаются равнозначными [].

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

Выходом из такой ситуации является приписывание терминам дифференцированных весов. Термины поискового образа одного и того же документа в таком слу-

25

онной потребностью и терминами, составляющими поисковый образ документа, разработана вероятностная модель оценки весов терминов [, ].

Вероятностная модель основана на точной оценке вероятности того, что данный документ является релевантным (точнее, пертинентным) данному запросу [, ].

Обозначим вероятность такого события как P(w1 |d), где w1 – событие, которое состоит в том, что документ d является релевантным по отношению к запро-

су q . Аналогично, предположим, что P(w2 |d) – вероятность того, что документ d

окажется нерелевантным.

релевантным, P(d) – вероятность того, что из всего множества документов для

рассмотрения выбран документ d , P(d | w1) – вероятность того, что документ d

выбран из множества релевантных документов.

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

Если вероятность появления термина ti в релевантном документе обозначить

как

27

вантного. Наименьший вес будут, очевидно, иметь общеупотребительные слова (термины из стоп-словаря), вероятности появления которых в релевантных и нерелевантных документах одинаковы и равны 50%.

Значение константы C одинаково для всех документов, поэтому обычно при вычислении релевантности ее игнорируют.

Для расчета вероятностей pi и qi часто используются упрощенные формулы

p= (DF)iR ,

i R

qi = (DF)i − (DF)iR . N − R

В этих формулах используются следующие обозначения:

(DF)i – число документов информационного массива, в которых встречается

термин ti ;

(DF)iR – число релевантных документов, в которых встречается этот термин;

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

При индексации величины (DF)iR и R полагаются равными нулю, и вес тер-

мина ti рассчитывается как

Wi = log N − (DF)i + 0.5 .

(DF)i + 0.5

28

При больших объемах информационного массива вес термина становится равным обратной документной частоте (2.4):

N

(DF)i .

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

ний (DF)iR и R и, как следствие, более точный расчет весов терминов согласно

выражению (2.10).

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

2.5.3. Латентно-семантический анализ

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

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

Другой проблемой является синонимия и полисемия (многозначность) [].

Под синонимией понимается тот факт, что любое явление или предмет могут быть выражены различными способами. В зависимости от контекста, знаний человека, манеры письма одни и те же сведения описываются разными терминами (синонимами). Например, синонимы «дисплей» и «монитор» определяют один и тот же предмет.

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

29

такой же термин. В качестве иллюстрации приведем слово «мышь», которое означает и грызуна, и компьютерное устройство [].

Описанные проблемы решает латентное семантическое индексирование1 [, ]. Суть этого подхода состоит в том, что каждый набор документов имеет неявную, латентную семантическую структуру2. Анализ такой структуры (латентно-семантиче- ский анализ) позволяет описать каждый документ не только с точки зрения наличия или отсутствия каких-либо терминов, но и с точки зрения его смысла (семантической направленности). Например, документ может быть адекватно описан терминами, которые не входят в его состав, и наоборот – некоторые термины не отражают смысла документа, и совпадение их с терминами запроса не делает документ релевантным [].

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

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

Математически латентно-семантическое индексирование реализуется с помощью одного из методов линейной алгебры – сингулярного разложения матрицы [, ]. Современные алгоритмы используют также аппарат теории вероятностей (вероятностное латентное семантическое индексирование) [].

Одним из важных направлений ЛСИ является межязыковое латентно-семанти- ческое индексирование3 []. Основным принципом здесь является тот факт, что запрос на одном языке может возвращать релевантные документы на других языках.

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

1 Латентное семантическое индексирование (ЛСИ) – англ. Latent Semantic Indexing (LSI)

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

3 Межязыковое ЛСИ – от англ. Cross-language Latent Semantic Indexing

30

Главное достоинство межязыкового ЛСИ – отсутствие необходимости перевода (ручного или машинного) запроса на другой язык. Это особенно актуально для поиска в сети Интернет, когда запросы являются неспециализированными, и их адекватный перевод вызывает значительные трудности [, , ].

Латентно-семантический анализ в настоящее время также часто применяется для анализа гипертекстовых документов. Практика показывает, что документы, связанные гиперссылками, обычно находятся в одном семантическом пространстве. Один из латентных факторов, которым в данном случае является структура гиперссылок, существенно влияет на точность поиска [].

Примером количественной характеристики этого фактора может служить величина PageRank , которая вычисляется на основе информации о других документах, имеющих ссылки на данный, и определяется выражением

ствует, и OLk, i = 1, если она существует.

Значение PageRank , которое рассчитывается для каждого документа, определяет его важность по сравнению с другими документами [].

Для реализации некоторых вспомогательных операций информационного поиска (автоматическая фильтрация2, классификация и др.) также используются алгоритмы ЛСИ [].

3. Хранение индексированных документов

Организация хранения массива поисковых образов документов – одна из критических частей поискового аппарата ИПС.

1 OL – англ. Outgoing Hyperlink – исходящая гиперссылка.

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