WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 | 2 || 4 | 5 |

(TF )i Ключевые слова ri Рис. 7. Выделение ключевых слов по закону Ципфа Границы выделения ключевых слов определяют качество поиска в ИПС. Высокочастотные термины хоть и не являются специфическими, но все же дают большое число совпадений при сравнении терминов запроса и документа. Тем самым обеспечивается выдача многих релевантных документов, то есть увеличивается полнота поиска. С другой стороны, низкочастотные термины вносят относительно небольшой вклад в поиск нужных документов, так как редкие термины дают малое число совпадений образов запроса и документа. Но если они все же совпадают, то соответствующий найденный документ почти наверняка является релевантным [, ].

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

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

Число служебных слов в отрицательном словаре составляет обычно несколько сотен, в зависимости от системы.

2.4. Анализ информационных массивов 2.4.1. Понятие относительной частоты Использование во время индексации частоты встречаемости термина в документе (абсолютной частоты) эффективно лишь в случае очень малого объема информационного массива. В действительности же современные массивы данных образованы тысячами и десятками тысяч документов, а в Интернете доступны миллиарды информационных объектов. Поскольку число слов, используемых при индексации, ограничено числом слов в естественном языке и стоп-словарем, для индексации разных документов использовались бы одни и те же термины. Применение абсолютных значений частоты привело бы к резкому уменьшению точности поиска из-за постоянного использования при индексировании высокочастотных терминов, которые встречаются в большинстве документов.

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

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

ti Определим документную частоту термина как число документов массива, в (DF)i. Тогда взвешивающую которых встречается этот термин, и обозначим ее функцию, обратную документной частоте1, можно определить следующим образом:

N (IDF )i = log (2.4) (DF )i, где – общее число документов в информационном массиве. Функция (2.4) N приписывает наибольшие значения терминам, появляющимся лишь в нескольких документах. Чем чаще термин встречается в документах массива, тем меньше значение обратной документной частоты.

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

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

ti (DV )i. Она Значимость термина измеряется его различительной силой определяется как разность между средним попарным подобием документов, когда ti термин отсутствует в векторах документов массива, и средним попарным подобиti ем, когда термин присутствует. Если данный термин представляет ценность для индексирования, его присутствие в векторе документа должно делать документы менее похожими друг на друга. Тогда среднее попарное подобие уменьшается, а раз IDF – англ. Inversed Document Frequency – обратная документная частота.

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

2.4.2. Распределение частоты встречаемости терминов Практика показывает, что хорошие, средние и плохие индексационные термины (DF)i и расможно характеризовать по распределению их документной частоты Fi пределению частоты встречаемости [].

ti Суммарная частота встречаемости термина в массиве документов определяется следующей формулой:

N Fi = fi.

k k = 1.Лучшими для индексации терминами с наивысшими значениями различительной силы являются термины со средними значениями суммарной частоты встречаеFi мости и документной частотой, составляющей менее половины его частоты как термина (суммарной частоты в массиве).

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

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

Рис. Рис. 8 иллюстрирует вышеописанное разделение терминов. Если располо(DF)i, то индексационжить термины в порядке увеличения документной частоты ные термины должны, насколько это возможно, попадать в средний интервал значений.

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

Низкая DF Средняя DF Высокая DF Нулевые Положительные Отрицательные значения DV значения DV значения DV Документная 2 1 частота DF N Улучшение полноты Улучшение точности Рис. 8. Характеристика терминов по распределению документной частоты На рис. Рис. 9 изображено несколько типичных распределений частот терминов. Наилучшими для индексации являются термины, имеющие распределение (рис. Рис. 9 а). Они обеспечивают приемлемые значения полноты и точности поиска.

Термины с распределениями (рис. Рис. 9 б) повышают точность, но резко снижают полноту поиска, а с распределениями (рис. Рис. 9 в) – наоборот, увеличивают полноту, но уменьшают точность. Наконец, равномерное распределение частоты (рис. Рис. 9 г) свойственно общеупотребительным терминам, которые не обеспечивают ни надлежащей точности поиска, ни его полноты.

(TF)i (TF)i 0 Документы Документы а б (TF )i (TF )i Документы Документы в г Рис. 9. Распределения частот терминов в документах 2.5. Определение весов терминов После того как из документа отобраны термины для поискового образа, возникает вопрос об оценке их значимости для поиска.

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

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

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

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

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

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

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

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

-частотная модель, -вероятностная модель, -латентно-семантический анализ.

Остановимся на них более подробно.

2.5.1. Частотная модель Частотная модель взвешивания терминов тесно связана с частотным методом индексирования (раздел 2.4). Одна из наиболее известных весовых функций записывается следующим образом []:

Wi = (TF)i (IDF )i.

Wi ti (TF )i – частота термина в докуЗдесь – вес, приписываемый термину, (IDF)i – обратная документная частота.

менте, Также на практике широко применяется весовая функция (TF)i Wi = 0.5+ 0.5 (IDF)i, (TF)max (TF )max – максимальная частота термина в k -ом документе, то есть чагде стота термина, который встречается в документе чаще всего. Весовой коэффициент ti Wi отражает значимость термина в k -ом документе.

При использовании различительной силы терминов их индексационные веса могут быть вычислены по формуле Wi = (TF)i (DV )i, ti (DV )i – значение различительной силы термина. Полнота поиска здесь где может быть обеспечена путем поиска высокочастотных терминов, а точность поиска определяется положительными значениями различительной силы.

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

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

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

P(w1 |d) воспользуемся теоремой Байеса:

Для определения вероятности P(d | w1)P(w1) P(w1 |d) =.

P(d) P(w1) – вероятность того, что случайно выбранный документ является Здесь P(d) релевантным, – вероятность того, что из всего множества документов для P(d | w1) рассмотрения выбран документ, – вероятность того, что документ d d выбран из множества релевантных документов.

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

d 0, ti d d = d1, d2,,di,,dD, di =, 1, ti d где – размер словаря поисковой системы.

D Далее, будем считать, что любая пара терминов входит в документ независимо друг от друга, то есть вероятности появления всех терминов в документе равны:

P(d1 | w1) = P(d2 | w1) = = P(dD | w1).

P(d | w1) Тогда вероятность для документа будет равна произведению соd ответствующих вероятностей для всех входящих в него терминов:

D P(d | w1) = P(t | w1) P(t | w1) = P(di | w1).

(2.5) t d t d i = ti Если вероятность появления термина в релевантном документе обозначить как pi = P(di = 1| w1), ) то выражение (2.5) можно представить в виде D d 1 - d P(d | w1) = pi i 1- pi i, (2.6) i = где 1- pi = P(di = 0| w1).

Аналогично, для нерелевантных документов D D d 1 - d P(d | w2) = P(di | w2)= qi i 1- qi i, (2.7) i = 1 i = qi ti где – вероятность появления термина в нерелевантном документе, которая равна qi = P(di = 1| w2), 1- qi = P(di = 0| w2).

В вероятностной модели считается, что адекватной мерой релевантности докуR(d) мента является отношение P(d | w1) R(d) =.

P(d | w2) Подставляя в это выражение формулы (2.6) и (2.7), получим d 1- d D pi i 1- pi i. (2.8) R(d) = qi 1- qi i = После логарифмирования и упрощения выражения (2.8) меру релевантности можно описать следующим образом:

D R(d) = Widi + C, (2.9) i = где pi (1- qi ) Wi = log, qi (1- pi ) D 1- pi C = log.

1- qi i = Wi ti В выражении (2.9) есть вес термина в документе. В данном случае d вес характеризует способность термина отличить релевантный документ от нерелевантного. Наименьший вес будут, очевидно, иметь общеупотребительные слова (термины из стоп-словаря), вероятности появления которых в релевантных и нерелевантных документах одинаковы и равны 50%.

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

pi qi Для расчета вероятностей и часто используются упрощенные формулы (DF)iR pi =, R (DF)i - (DF)iR qi =.

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

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

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

– общее число релевантных документов;

R – общее число документов в информационном массиве.

N ti Таким образом, формула для определения веса термина примет вид (DF)iR N - R - (DF)i + (DF)iR Wi = log.

(DF)i - (DF)iR R - (DF)iR На практике в основном используется несколько измененное выражение [, ]:

(DF)iR + 0.5 N - R - (DF)i + (DF)iR + 0. Wi = log. (2.10) (DF)i - (DF)iR + 0.5 R - (DF )iR + 0. (DF)iR и R обычно неизвестны. Для их Во время индексации величины определения используется динамический итерационный процесс обратной связи с пользователем, который заключается в следующем.

(DF)iR и R полагаются равными нулю, и вес терПри индексации величины ti мина рассчитывается как N - (DF)i + 0.Wi = log.

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

N Wi (IDF)i = log (DF)i.

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

Pages:     | 1 | 2 || 4 | 5 |






















© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.