Методы информационного поиска и ранжирования документов в компьютерных сетях тема диссертации и автореферата по ВАК РФ 05.13.13, кандидат технических наук Горбунов, Андрей Леонидович

• Горбунов, Андрей Леонидович
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Горбунов, Андрей Леонидович

Введение.

1 Особенности совершенствования теоретической базы компьютерных сетей посредством развития методов информационного поиска (ИП).

1.1 Место методов ИП в современных компьютерных сетях и проблема показателей качества ИП.

1.2 Анализ методов ИП.

1.2.1 Поисковые системы.

1.2.2 Кластерный анализ.

1.3 Основные направления исследований.

Введение диссертации (часть автореферата) на тему «Методы информационного поиска и ранжирования документов в компьютерных сетях»

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

Термин «информационный поиск» (Information Retrieval) введён в научный оборот Моирсом (Calvin Moeers) в 1951 году [66]. Исследования в этой области эволюционировали от разработок, сфокусированных на технических аспектах в 50/60-х годах прошлого столетия (информационно-поисковая система с автоматическим индексированием, впервые разработанная в нашей стране под руководством B.C. Чернявского и Д.Г. Лахути), через интенсивно развиваемые в 70/80-е годы методы, связанные с ориентированными на пользователя интерфейсами поиска к специализированным поисковым инструментам, получившим мощное развитие в связи с появлением всемирной сети в 90-е годы.

Тематика ИП широко освещается в научной литературе. В работах Д. Аветисяна и Р. Аветисяна описываются энтропийная модель на основе статистической теории связи Шенона и корреляционная модель документарного поиска. Заметный вклад в развитие методов ИП внесли своими работами Пархоменко В.Ф., Дюк В.А., Бухштаб Ю.А., Некрестьянов И.С. Одним из основоположников ИП является Д. Сэлтон (G. Salton) -создатель модели векторного пространства, относящейся к числу базовых моделей построения поисковых процедур. Схемы взвешивания при сравнении векторов запроса и документа исследуются в трудах С. Думайса (S. Dumais). Хорошо известны работы Ф. Гея (F. Gey), посвященные поиску с использованием модели логической регрессии, а также исследования Р. Фанга (R. Fung) по байесовским моделям ИП. Доминирующий в настоящее время подход к организации процедуры установления соответствия запроса и документа (метод индекса цитирования) отражен в работах С. Брина (S. Brin) и JI. Пэйджа (L. Page).

Укрепляющийся интерес современных исследователей к данной тематике очевидно обусловлен информационной глобализацией, в сфере компьютерных сетей наиболее выпукло представленной феноменом Интернета. Появление огромных и общедоступных хранилищ информации с постоянным и быстрым обновлением отличающихся сильной неоднородностью данных (база данных лидера поисковой индустрии google.com содержит информацию о более чем 8,5 миллиардов документов) вывело на первый план сложную комплексную задачу разработки методов, обеспечивающих быстрый и качественный поиск в таких хранилищах, их эффективное автоматическое пополнение, определение связей между хранимыми документами, структурирование содержимого хранилищ. Тенденция лавинообразного роста информационной насыщенности сделала подсистемы ИП не только неотъемлемым, но и наиболее важным элементом архитектуры компьютерных сетей.

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

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

• исследование методов и средств поиска информации в компьютерной сети Интернет;

• разработка методов учета предпочтений пользователей при осуществлении поиска (поисковая персонализация);

• совершенствование методов учета статистики переходов и поискового поведения пользователей в ходе поисковых сессий;

• формирование новых критериев ранжирования документов Интернета, комплексно учитывающих стохастическую природу посещения веб-сайтов;

• улучшение процедур поиска новостной информации в Интернете.

В диссертации осуществляется теоретический анализ и экспериментальное исследование функционирования телекоммуникационных систем и компьютерных сетей для специальных приложений - ПС. Разрабатываются научные подходы, методы и алгоритмы для ПС. ПС, будучи объектами седьмого (прикладного) уровня эталонной модели OSI ISO, в случае Интернета с характерным для этой среды мощным поисковым трафиком, оказывают значительное влияние на архитектуру объектов уровней 2-6 (канальный, сетевой, транспортный, сеансовый, представительный): разрабатываемые в диссертации методы снижают объём поискового трафика и, тем самым, высвобождают ресурсы уровней 2-6 для полезной нагрузки.

На защиту выносятся представленные в диссертации:

• метод персонализированного ИП с ранжированием результатов поиска через функцию релевантности в виде целевой функции задачи линейного программирования;

• метод персонализированного ИП через ранжирование результатов поиска с учётом статистики переходов по ссылкам на найденные документы и поведения пользователя ПС;

• метод ранжирования веб-страниц по критериям посещаемости и доступности для посетителей, построенным на базе полумарковской модели изменения состояния системы пользователь-сайт;

• метод ранжирования сайтов по критерию общей эффективности, построенной на базе марковской модели, отображающей траекторию перемещения посетителя сайта по его структуре;

• метод ранжирования новостных источников в Интернете по критерию информативности, основанный на модели, построенной с применением элементов дисперсионного анализа.

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

• предложена новая процедура определения релевантности для результатов поисковых сессий в Интернете в виде решения задачи линейного математического программирования, применяемая в целях персонализированного ранжирования результатов поиска информации;

• построен оригинальный критерий релевантности для результатов информационного поиска в Интернете с учётом статистики переходов по ссылкам на найденные документы и поведения пользователя ПС в течение поисковой сессии;

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

• разработана оригинальная модель поведения пользователя во время работы с сайтом в терминах «погружения» в структуру сайта;

• разработана модель обработки онлайновой новостной информации на базе схемы дисперсионного анализа;

• построен оригинальный критерий категоризации новостных источников с учётом их рыночной востребованности.

Апробация полученных результатов. Основные положения диссертационный работы докладывались и обсуждались на кафедрах «Вычислительные машины, комплексы и сети» и «Радиотехнические устройства» Московского государственного Технического Университета ГА, «Вычислительная техника» Московского Государственного Института Электроники и Математики, на международной конференции «Российский Интернет Форум 2002». По теме диссертации опубликовано 6 печатных работ. Описываемые в диссертации методы ранжирования разработаны и апробированы автором в период работы в проекте Рубрикон (www.rubricon.com). Рубрикон - крупнейший в мире энциклопедический Интернет-ресурс: более 590 тыс. полнотекстовых энциклопедических статей, более 86 тыс. карт и иллюстраций, 81 наименование энциклопедий, справочников и книг, включая 30 томов главной на сегодня российской национальной энциклопедии БСЭ. Компания Microsoft включила встроенную функцию прямого поиска по Рубрикону в свой наиболее массовый продукт, присутствующий практически на каждом компьютере в России - пакет MS-Office 2003 (http://www.microsoft.com/rus/news/issue.asp720-ll-2003-MicrosoftOfficeSystem.xml). Инфраструктура контент-продаж Рубрикона используется старейшей и самой известной в мире энциклопедией на английском языке -энциклопедией «Британика» - для организации доступа российских подписчиков к своим онлайновым ресурсам. Рубрикон имеет совместные проекты с лидирующей российской ПС Яндекс («Яндекс-Энциклопедии» http://encycl.yandex.ru). Таким образом, проект Рубрикон является наиболее представительной в современных условиях средой для развития и проверки разработанных методик.

Исследования базируются на использовании математических аппаратов:

• линейного математического программирования;

• теории марковских процессов;

• статистического дисперсионного анализа.

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

• построить специализированный поисковый сервис, обеспечивающий персонализацию информационного поиска в Интернете;

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

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

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

Заключение диссертации по теме «Телекоммуникационные системы и компьютерные сети», Горбунов, Андрей Леонидович

ЗАКЛЮЧЕНИЕ

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

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

В ходе исследований, проведённых в настоящей диссертационной работе, получены следующие основные результаты:

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

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

3. Определена структура диалоговой сессии для выявления предпочтений искателя при персонализированном поиске информации.

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

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

6. Разработана модель учёта поведения пользователей Интернета внутри пространства ссылок при выработке критерия релевантности с учётом статистики переходов.

7. Разработан новый метод ранжирования веб-страниц, страниц по критериям посещаемости и доступности для посетителей, построенным на базе полумарковской модели изменения состояния системы пользователь-сайт;

8. Разработан новый метод ранжирования сайтов по критерию общей эффективности, построенной на базе марковской модели, отображающей траекторию перемещения посетителя сайта по его структуре;

9. Разработан новый метод ранжирования новостных источников в Интернете по критерию информативности, основанный на модели, построенной с применением элементов дисперсионного анализа.

10. Сконструирован критерий категоризации новостных источников с учётом их рыночной востребованности.

11. Построены программные модули, реализующие разработанные методы.

Полученные результаты позволяют сформулировать следующие основные выводы: i. Улучшение качества поиска информации в Интернете связано с механизмами персонализации поисковых процедур, реализация которых требует применения развитых математических аппаратов, обеспечивающих широкие возможности настройки на предпочтения искателя. К таковым относится аппарат математического программирования, использованный в настоящей диссертации для выработки новых критериев релевантности. ii. Разработанные в диссертации методы специального ранжирования информационных объектов Интернета с учётом статистики переходов пользователей ПС и их поискового поведения являются серьёзным базисом для повышения качества ИП. iii. Поиск оптимальных площадок для реализации задач рыночного продвижения в Интернете не обеспечивается в должной мере существующими методами оценки посещаемости веб-сайтов. Обращение к марковским моделям позволило выработать набор новых оценок, комплексно учитывающих стохастическую природу процесса посещения сайта. iv. Доля ручного труда при обработке первичной информации из онлайновых новостных источников при осуществлении конкурентной разведки весьма значительна и во многом связана с оценкой информативности источников. Разработанная автоматическая процедура категоризации источников новостей по степени информативности снижает эту долю и, соответственно, повышает эффективность работы маркетинговых подразделений компаний и организаций.

Список литературы диссертационного исследования кандидат технических наук Горбунов, Андрей Леонидович, 2005 год

1. Адамович И.М., Заикии М.Ю., Земсков Д.В., Пешков А.И. Поиск информации в WEB. Сравнительная оценка поисковых машин. Системы и средства информации. 2003, № 13, с. 84-105.

2. Барзилович Е.Ю. Модели технического обслуживания сложных систем. М.: Высшая школа, 1982.

3. Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и её инженерные приложения. М.: Наука, 1991.

4. Горбунов А.Л. Массовый платный контент. Материалы Шестого Российского Интернет Форума 2002 (РИФ-2002), с.с. 119-120. М: РОЦИТ, 2002.

5. Горбунов А.Л. Об учёте опыта коллег, argc & argv. Журнал для программистов. № 2. Киев: Сич, Украина, 2004.

6. Горбунов А.Л. Построение сканирующего полумарковского процесса. Межвузовский сборник научных трудов "Автоматизация обработки первичной информации". Пенза: ППИ,1988,вып. 13 с.42-48.

7. Елисов Л.Н., Баранов В.В. Управление и сертификация в транспортной системе. -М.: Воздушный транспорт, 1999.

8. Исикава К. Японские методы управления качеством./Под ред. Гличева А.В. М.: Экономика, 1998.

9. Казаков В.Н. Введение в теорию марковских процессов и некоторые радиотехнические задачи. М: «Советское радио», 1973.

10. Карасева Н.В. Применение технологий Data Mining для анализа данных. Сборник трудов научной сессии МИФИ-2004. Т. 12 М.: Изд-во МИФИ. 2004, с. 59-61.

11. Касумов В.А. Методы информационного поиска в Internet на основе нечётких отношений предпочтений. Автоматика и вычислительная техника. 2003, №4, с. 7178.

12. Комаров И.И. Методы автоматического поиска релевантной информации в тексте на естественном языке. Автореф. на соиск. уч. степени к.ф.м.н. С.-Петербургский Государственный университет. С.-П. 2003.

13. Кулик С.Д. Исследование нейросетевых программ и автоматизированные фактографические ИПС. Нейрокомпьютеры: разработка, применение. 2003, № 8-9, с. 38-50.

14. Курилец М.А. Транспортный менеджмент: Учебное пособие. М.: МГТУ ГА, 2001.

15. Мамедова Г. А. Сравнительный анализ современных методов поиска информации в Интернет-среде. Материалы семинара «Информационные сети, системы и технологии». -М.: Информсвязьиздат. 2003, с.121-122.

16. Миронов М.А., Тихонов В.И. Марковские процессы. Москва: Радио, 1977.

17. Некрасов И.В., Толчеев В.О. Сравнительный анализ методов классификации текстовых документов. Сборник трудов научной сессии МИФИ-2004. Т. 2 М.: Изд-во МИФИ. 2004, с. 169-170.

18. Некрестьянинов И., Павлова Е. Обнаружение структурного подобия HTML-документов. Труды 4-й Всероссийской конференции «RCDL'2002». Дубна: Изд-во ОИЯИ. 2002, с. 38-54.

19. Сальникова С.М., Попов Ю.А. Развитие проекта «Система поиска знаний в INTERNET». Сборник трудов научной сессии МИФИ-2004. Т. 11 М.: Изд-во МИФИ. 2004, с. 172-177.

20. Шабанов В.И., Власова А.Е. Алгоритм формирования функциональных связей и его применение в поисковых системах. Труды Международной конференции Диалог-2003. М.: Наука. 2003, с. 603-608.

21. Шеффе Г. Дисперсионный анализ. Пер. с англ. М: Мир, 1963.

22. Arasu A., Cho J., Garcia-Molina Н., Paepcke A., Raghavan S. (2001). Searching the Web. ACM Transactions on Internet Technology, Vol. 1, No. 1

23. Baeza-Yates R., Ribiero-Neto B. (1999). Modern Information Retrieval. Reading, MA: Addison Wesley.

24. Berry M., Brown M. (1999). Understanding Search Engines: mathematical modeling and text retrieval. Philadelphia: SIAM.

25. Bharucha-Reid A. (1960). Elements of the Theory of Markov Processes and ТЬеИП Applications. NY: McGraw-Hill.

26. Bolch G., Greiner S., Meer H., Trivedi K. (1998). Queueing Networks and Markov Chains. NY: John Wiley & Sons.

27. Boyce В., Kraft D., Meadow C. (1999). Text Information Retrieval Systems (Library and Information Science Series). Academic Pr.

28. Brin S., Page L. (2001). The Anatomy of a Large-Scale Hypertextual Web Search Engine. On-line]. Available: http://www7.scu.edu.au/programme/fullpapers/1921/coml921.htm

29. Bucy E., Lang A., Potter R., Grabe M. (1999). Formal features of cyberspace: Relationships between Web page complexity and site traffic. Journal of the American Society for Information Science. Volume 50, Issue 13, pp. 1246-1256. NY: John Wiley & Sons.

30. Calvo R., Williams K. (2002). Automatic Categorization of Announcements on the Australian Stock Exchange. On-line. Available: http://www.ted.cmis.csHno.au/adcs2002/papers/calvo-williams.pdf

31. Chen Н., Cooper М. (2001а). Predicting the Relevance of a Library Catalog Search. Journal of the American Society for Information Science and Technology. Vol. 52, No. 10. NY: John Wiley & Sons.

32. Chen H., Cooper M. (2001b). Using Clustering Techniques to detect Usage Patterns in a Web-Based Information System. Journal of the American Society for Information Science and Technology. Vol. 52, No. 10. NY: John Wiley & Sons.

33. Chen H., Cooper M. (2002). Stochastic Modeling of Usage in a Web-Based Information System. Journal of the American Society for Information Science and Technology. Vol. 53, No. 7. NY: John Wiley & Sons.

34. Cothey V. (2002). A Longitudinal Study of World Wide Web Users' Information Searching Behavior. Journal of the American Society for Information Science and Technology. Vol. 53, No. 2. NY: John Wiley & Sons.

35. Cristianini N., Shawe-Taylor J. (2000). An Introduction to Support Vector Machines. Cambridge University Press, 2000.

36. Dumais S. (1991). Improving the retrieval of information from external sources. Behavior Research Methods, Instruments & Computers, 23, pp. 211-218.

37. Fisher R. (1925). Statistical methods for research workers. Edinburgh.

38. Frommholz I. (2001). Automatic Categorization of Web Documents. On-line]. Available: http://www.is.infoimatik.uni-uisburg.de/teaching/seminars/dido/2001-01-16-frommholz-slides.pdf

39. Fung R., Favero B. (1995). Applying networks to information retrieval. Communications of the ACM, 58, pp. 27-30.

40. Gey F. (1994). Inferring probability of relevance using the method of logistic regression. In Processing of the Seventeenth Annual ACM-SIGHIl Conference, W. B. Croft and C. Van Rijsbergen, eds., London, Springer-Verlag, Berlin, New York, pp. 222-241.

41. Gorbunov A. (2002). Relevance of Web Documents: Ghosts Consensus Method. Journal of the American Society for Information Science and Technology. Vol. 53, No. 10, pp. 783788. NY: John Wiley & Sons.

42. Gorbunov A. (2005). Markov Models of WebSite Visitation. Applied Stochastic Models in Business and Industry. NY: John Wiley & Sons. Forthcoming.

43. GregoMlI S., Lenglart F. (2000). Measuring the probability of a business cycle turning point by using a multivariate qualitative hidden Markov model. Journal of Forecasting. Volume 19, Issue 2, p.p. 81-102. NY: John Wiley & Sons.

44. Guedon Y. (1999). Computational methods for discrete hidden semi-Markov chains. Applied Stochastic Models in Business and Industry. Volume 15, Issue 3, pp. 195-224. NY: John Wiley & Sons.

45. H. Luo, Q. Huang (2002). Automatic categorization design for broadcast news. Proc. SPIE Vol. 4676, Storage and Retrieval for Media Databases 2002, p.p. 285-295.

46. Hung С. ,Wermter S. (2004). A Dynamic Adaptive Self-Organising Hybrid Model for Text Clustering. On-line]. Available: http://www.his.sunderland.ac.uk/ps/hungcclustering.pdf

47. Jansen В., Spink A., Saraevic T. (2000). Real Life, Real users and Real needs: a Study and Analysis of User Queries on the Web. Information Processing and Management. 36: 207227.

48. Janssen J. (ed). (1986). Semi Markov Models: Theory and Applications. NY: Plenum Press

49. Jing H., Tzoukermann E. (1999). Information retrieval based on context distance and morphology. In Proceedings of the 22nd annual international ACM SIGMII conference on Research and development in information retrieval, p.p. 90 96.

50. Kohonen T. (2001). Self-organizing maps. Springer-Verlag, 2001.

51. Korfhage R. (1997) Information Storage and Retrieval. New York : John Wiley & Sons.

52. Korolyuk V., Swishchuk A. (1994). Semi-Markov Random Evolutions. Mathematics and its applications. Hardbound: Kluwer Academic Publishers

53. Kuo J., Chen H., Huang S., Lin C., Wung H. (2003). A Summarization System for Chinese News from Multiple Sources. Journal of the American Society for Information Science and Technology. Vol. 54, No. 13, pp. 1224- 1227. NY: John Wiley & Sons.

54. Lam W., Ruiz M., Srinivasan P. (1999). Automatic Text Categorization and Its Application to Text Retrieval. IEEE Transactions on Knowledge and Data Engineering. November/December 1999 (Vol. 11, No. 6), p.p. 865-879.

55. Lamb R., King J., Kling R. (2003). Informational EnvHFIonments: Organizational Contexts of Online Information Use. Journal of the American Society for Information Science and Technology. Vol. 54, No. 2., pp. 97-114. NY: John Wiley & Sons.

56. Liere R., Tadepalli P. (2004). Active Learning with Committees: Preliminary Results inComparing Winnow and Perceptron in Text Categorization. On-line]. Available: http://www.rdrop.com/~lierer/conald98.ps

57. Moens M., Dumortier J. (2004). Automatic Categorization of Magazine Articles. On-line]. Available: http://wwwis.win.tue.nl/infwet99/proceedings/moens.html

58. Morris S., Yen G., Wu Z., Asnake B. (2003). Time Line Visualization of Research Fronts. Journal of the American Society for Information Science and Technology. Vol. 54, No. 5, pp. 413-422. NY: John Wiley & Sons.

59. Qiu I. (1993). Markov Models of Search State Patterns in a Hypertext Information Retrieval System. Journal of the American Society for Information Science and Technology. Vol. 44: 413-427. NY: John Wiley & Sons.

60. Salton G., Buckley C. (1983). Introduction to Modern Information Retrieval. New York : McGraw-Hill.

61. Salton G., Buckley С. (1988). Term weighting approaches in automatic text retrieval. Information Processing and Management. No. 24, pp. 513-523.

62. Salton G., Buckley C. (1990). Improving retrieval performance by relevance feedback. Journal of the American Society for Information Science. Vol. 41, pp. 288-297.

63. Shamim Khan M., Khor S. (2004). Enhanced Web Document Retrieval Using Automatic Query Expansion. Journal of the American Society for Information Science and Technology. Vol. 55, No. 1, pp. 29-35. NY: John Wiley & Sons.

64. StatSoft, Inc. Электронный учебник по промышленной статистике. М: StatSoft, 2001.

65. Stewart W. (1991). Numerical Solution of Markov Chains. NY: Dekker.

66. Moeers C. (1951). Zatocoding applied to mechanical organization of Knowledge. American documentation. Vol. 2, No. 1, pp. 20-32.

67. Горбунов A.JI. О методе ранжирования новостных источников в Интернете. Научный вестник МГТУ ГА. Сер. Информатика. Прикладная математика. М.: МГТУ ГА, 2005.