WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 2 | 3 || 5 |

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

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

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

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

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

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

Описанные проблемы решает латентное семантическое индексирование1 [, ].

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

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

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

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

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

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

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

Латентное семантическое индексирование (ЛСИ) – англ. Latent Semantic Indexing (LSI) Под семантической структурой здесь имеется в виду некоторая структура, в которую объединены отдельные термины в документе.

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

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

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

Примером количественной характеристики этого фактора может служить веPageRank личина, которая вычисляется на основе информации о других документах, имеющих ссылки на данный, и определяется выражением PageRank(Pk ) PageRank(Pi ) = (1 - d ) + d.

L(Pk ) Pk :OLk, i = Pi Pk Здесь и – документы информационного массива; – некоторый параd L(Pk ) – общее количество ссылок, выходящих из докуметр (обычно );

d 0.OLk, i – величина, характеризующая наличие гиперссылки из документа Pk мента ;

Pk в документ Pi (исходящей гиперссылки1). OLk, i = 0, если такая ссылка отсутOLk, i = 1, если она существует.

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

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

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

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

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

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

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

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

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

Рассмотрим общую структуру базы данных поисковых образов интернет-документов (гипертекстовых страниц) [,,, ].

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

Дата модификации Заголовки Ссылки страниц страниц (названия) страниц pageID pageID pageID дата индексации заголовок входящие ссылки дата модификации (pageID) исходящие ссылки (pageID) Адреса страниц (URL) pageID URL Прямой Инвертированный список список pageID kwdID kwdID pageID вес термина позиция термина в документе в документе Ключевые слова kwdID термин Рис. 10. Структура базы данных поисковых образов Таблица адресов страниц содержит уникальные идентификаторы (pageID) и адреса страниц (URL1).

Таблица ключевых слов содержит термины и их уникальные идентификаторы (kwdID).

Таблица с заголовками страниц ставит в соответствие каждому идентификатору страниц pageID название этой страницы.

Таблица с датами изменения страниц фиксирует для каждой страницы pageID дату последнего посещения этой страницы индексационным роботом (т. е. дату индексации этой страницы). Она используется при обновлении базы данных: если содержание страницы изменилось со времени последней индексации, ее следует проиндексировать заново. В этой таблице также хранятся даты модификации стра URL – сокр. от англ. Uniform Resource Locator – унифицированный указатель информационного ресурса (стандартизованная строка символов, указывающая местонахождение документа в сети Интернет).

ниц. Эта информация используется при ранжировании результатов поиска не по релевантности, а по дате.

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

Таблицы, содержащие информацию о ссылках, необходимы по двум причинам.

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

Таблица, называемая прямым списком, содержит список ключевых слов (kwdID) для каждой страницы (pageID). Эта таблица используется для вычисления частоты (TF )i и определения весов терминов, а также встречаемости термина в документе в алгоритмах обратной связи по релевантности и в функциях поддержки и актуализации массива индексированных документов.

Таблица – инвертированный список содержит для каждого ключевого слова (kwdID) список страниц (pageID), в которых это слово встречается. Кроме того, здесь указывается позиция (порядковый номер) данного термина в странице. Эта информация используется в тех запросах, где важным является взаимное расположение слов (контекстный поиск). Например, когда идет поиск по запросу «операционная система», важно получить не просто все документы, в тексте которых присутствуют термины «операционная» и «система», а только те, в которых эти два слова расположены друг за другом, т. е. объединены во фразу.

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

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

Для ускорения доступа к базе данных поисковых образов веб-документов применяются механизмы индексации1 и хеширования2. Часто для хранения и обработки описаний документов используются системы управления базами данных (СУБД). В таких случаях поиск по базе данных осуществляется с использованием встроенных средств СУБД [].

Список рекомендуемой литературы 1.Добрынин В. Ю. Теория информационно-логических систем. Информационный поиск: Метод. указания к курсу информационного поиска. – СПб. : Изд-во СПбГУ, 2002.

2.Дубинский А. Г. Некоторые вопросы применения векторной модели представления документов в информационном поиске // Управляющие системы и машины. – 2001. – № 4.

3.Капустин В. А. Основы поиска информации в Интернете. Методическое пособие. – СПб. : Институт "Открытое общество", С.-Петерб. отд-ние, 1998.

4.Когаловский М. Р. Перспективные технологии информационных систем. М. :

ДМК Пресс : Компания АйТи, 2003.

5.Кромер В. В. Об одной поправке к каноническому закону // Телеконференция "Информационные технологии в гуманитарных науках". – Казань, 1998.

6.Кураленок И. Е. Оценка систем текстового поиска / И. Е. Кураленок, И. С. Некрестьянов // Программирование. – 2002. – № 4.

7.Некрестьянов И. С. Системы текстового поиска для Веб / И. С. Некрестьянов, Н. Пантелеева // Программирование. – 2002. – № 4.

8.Попов А. Поиск в Интернете – внутри и снаружи // Internet. – 1996. – № 2.

9.Сегалович И. В. Как работают поисковые системы // Мир Internet. – 2002. – № 10.

10.Солтон Дж. Динамические библиотечно-информационные системы. – М. :

Мир, 1979.

11.Храмцов П. Информационно-поисковые системы Internet // Открытые системы. – 1996. – № 3(17).

12.Храмцов П. Моделирование и анализ работы информационно-поисковых систем Internet // Открытые системы. – 1996. – № 6(20).

13.Чугреев В. Л. Модель структурного представления текстовой информации и метод ее тематического анализа на основе частотно-контекстной классификации:

дис. … канд. техн. наук: 05.13.01 / С.-Петерб. гос. электротехн. ун-т им. В.И. Ульянова (Ленина) “ЛЭТИ”. – СПб., 2003.

14.Чурсин Н. Н. Популярная информатика. – Киев. : Техника, 1982.

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

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

15."Электронные библиотеки: перспективные методы и технологии, электронные коллекции", всерос. науч.-практ. конф. (5 ; 2003 ; СПб.) Сборник трудов пятой всероссийской научной конференции "Электронные библиотеки: перспективные методы и технологии, электронные коллекции", 29 – 31 октября 2003 г. / науч. ред. Л. А.

Калиниченко. – СПб, 2003.

16.Baeza-Yates R. Modern Information Retrieval. / R. Baeza-Yates, B. Ribeiro-Neto // ACM Press Series – New York : Addison Wesley, 1999. – http://citeseer.ist.psu.edu/baezayates99modern.html.

17.Brin S. The Anatomy of a Large-Scale Hypertextual Web Search Engine / S. Brin., L. Page // Computer Networks and ISDN Systems. – 1998. – № 18.Carmel D. Probabilistic Models of Information Retrieval // D. Carmel, A. Soffer/ – Israel : Haifa University, 2003.

19.Draper S. Mizzaro's Framework for Relevance. – 1998.– http://www.psu.gla.ac.uk/ ~steve/stefano.htm.

20.Dumais S. T. Using Latent Semantic Indexing (LSI) for Information Retrieval, Information Filtering, and Other Things. // Talk at Cognitive Technology Workshop. – April 4-5, 1997.

21.Gabrielli S. Negotiating a Multidimensional Framework for Relevance Space / S.

Gabrielli., S. Mizzaro // Proc. of the MIRA'99. – 1999.

22.Greisdorf H. Relevance: An Interdisciplinary and Information Science Perspective.

Informing Science, N3 (2), 2000.

23.Hofmann T. Probabilistic Latent Semantic Indexing. In 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Berkeley, CA, USA, 1999.

24.Indexing by Latent Semantic Analysis / S. Deerwester [and others] // Journal of the American Society for Information Science. – 1990. – № 41(6), 25.Landauer T. K. Fully Automatic Cross-Language Document Retrieval Using Latent Semantic Indexing. / T. K. Landauer, M. L. Littman. // Proceedings of the Sixth Annual Conference of the UW Centre for the New Oxford English Dictionary and Text Research. – Waterloo (Ontario), 1990.

26.Lin J. J. Indexing and Retrieving Natural Language Using Ternary Expressions // Master's Thesis of Massachusetts Institute of Technology. – 2001.

27.Mizzaro S. How Many Relevances in Information Retrieval // Interacting With Computers. – 1998. – № 10(3).

28.Mizzaro S. Relevance: The Whole History // Journal of the American Society of Information Science/ – 1997. – № 48(9).

Pages:     | 1 |   ...   | 2 | 3 || 5 |






















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

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