автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Использование связей между web-страницами и закономерностей рассеяния информации для повышения эффективности поиска в WWW

ВВЕДЕНИЕ.

Глава 1. Поиск информации в WWW. Методы оценки релевантности web-страниц, выдаваемых поисковой машиной.

1.1 Представление WWW в виде графа.

1.2 Поисковые системы в WWW и проблема оценки релевантности web-страниц, выдаваемых поисковой машиной.

1.2.1 Каталог и поисковая машина.

1.2.2 Поисковые машины и проблема оценки релевантности ответа.

1.3 Индекс научного цитирования SCI и используемые им типы связей между научными публикациями.

1.4 Методы оценки релевантности web-страниц, учитывающие связи между ними в WWW.

1.4.1. Релевантность документа и критерии для оценки релевантности.

1.4.2 Первые попытки учета связей между web-страницами для оценки релевантности ответов, выдаваемых поисковой машиной.

1.4.3 Метод HITS и его модификации.

1.4.4 Метод PageRank.

1.4.5 Анализ существующих методов.

1.5 Результаты и выводы.

Глава 2. Разработка новых методов для повышения эффективности поиска в WWW с использованием связей между web-страницами и закономерностей рассеяния информации.

2.1 Модель процесса броузинга с возвратом.

2.2 Улучшение оценки релевантности web-страниц на основе учета связей между ними по отдельной теме.

2.3 Применение закона рассеяния информации Бредфорда для формирования ядра информационного потока.

2.4 Структурная схема усовершенствованной поисковой машины.

2.5 Результаты и выводы.

Глава 3. Применение разработанных методов при поиске в Интернете информации по теме «железнодорожный транспорт».

3.1 Методика эксперимента.

3.2 Полученные результаты.

3.2.1 Количество web-страниц по теме «железнодорожный транспорт» в зонах рассеяния информации.

3.2.2 Словарь терминов и термин-подмножества в WWW.

3.2.3 Оценки релевантности, вычисленные по методам PageRank, HITS и МОРСТ.

3.3 Формирование ядра информационного потока по теме «железнодорожный транспорт» в WWW.

3.4 Анализ полученных результатов.

3.5 Результаты и выводы.

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

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

Количество web-страниц в WWW растет по экспоненциальному закону. Поиск информации в этом огромном пространстве становится трудно решаемой задачей. В настоящее время используются два основных средства поиска: каталог и поисковая машина. Ограничения каталогов по объему индексированных web-страниц и по частоте их обновления заставляют пользователей чаще обращаться к поисковым машинам, чем к каталогам.

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

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

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

Проблемы оценки релевантности web-страниц на основе гиперссылок между ними нашли определенное отражение в работах многих ученых. В последние годы много внимания этой проблеме посвятили: Клейнберг Дж., Пейдж Л., Брин С., Чакрабарти С., Дом Б., Гибсон Д., Кумар С.Р., Рагаван П., Разагопалан С., Ботафого Р., Ривлин Е., Шнейдерман Б., Бхарат К., Хензингер М.Р., Марчиори М., Пироли П., Питкоу Дж., Храмцов П.Б. и другие. Было разработано несколько методов оценки релевантности, учитывающих связи между web-страницами в WWW. Выделяются два метода: PageRank, который используется в поисковой машине Google, и HITS - ядро механизма оценки релевантности новой поисковой машины CLEVER фирмы IBM.

Однако, методы оценки релевантности на основе учета связей между web-страницами в WWW находятся только в начальной стадии своего развития. Все существующие методы имеют свои сильные и слабые стороны. Это служит стимулом для новых исследований, направленных на развитие и совершенствование методов оценки релевантности. 6

Значимость этих исследований в повышении эффективности поисковой машины, в частности, и поисковых систем, в общем, определила выбор темы диссертации.

Целью диссертационной работы является использование связей между web-страницами и закономерностей рассеяния информации для повышения эффективности поиска в WWW.

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

- Анализ WWW, как информационного потока, и проблемы поиска информации в нем, изучение принципа работы различных поисковых систем, существующих в WWW;

- Анализ существующих методов оценки релевантности web-страниц, выдаваемых поисковой машиной, сравнение и выявление преимуществ, а также недостатков таких методов;

- Исследование процесса навигации пользователя в WWW и, на этой основе, разработка новой модели этого процесса;

- Разработка нового метода для улучшения оценки релевантности web-страниц с учетом связей между этими страницами в WWW;

- Разработка нового метода для выделения ядра информационного потока с применением закона рассеяния информации Бредфорда;

- Разработка структурной схемы новой поисковой машины и рекомендации для разработчиков поисковой машины;

- Применение разработанных методов для поиска информации в WWW по теме «железнодорожный транспорт».

Предметом исследования являются методы оценки релевантности web-страниц, учитывающие связи между ними.

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

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

Научная новизна работы состоит в развитии и разработке новых научно обоснованных методов для повышения эффективности поиска в WWW, учитывающих связи между web-страницами и закономерностей рассеяния информации. В соответствии с этим:

- разработана модель процесса броузинга в WWW с применением теории марковских процессов;

- разработан новый метод для улучшения оценки релевантности web-страниц на основе учета связей между этими страницами в WWW;

- разработан метод для определения ядра информационного потока с применением закона рассеяния информации Бредфорда;

- усовершенствована структурная схема, которая использует комбинированный механизм оценки релевантности для повышения эффективности поисковой машины.

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

Основные положения работы докладывались на научно-технической конференции «Неделя науки 2001», на шестой Международной научно-практической конференции «Информационные технологии на железнодорожном транспорте - Infotrans 2001».

Основные положения диссертации отражены в 3 научных публикациях общим объемом 2.625 печатного листа. 8

Диссертация состоит из введения, трех глав, заключения, списка использованной литературы (65 наименований) и приложений. В работе представлено 2 схемы, 29 рисунков, 16 таблиц, 6 приложений.

ЗАКЛЮЧЕНИЕ

По результатам диссертационной работы, сформулированы следующие выводы:

1. Исследование показало, что WWW - это огромная база гипертекстовых документов, которая может быть представлена в виде ориентированного графа. Большинство вершин этого графа образует слабо-связную компоненту.

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

3. Показано, что плодотворным подходом является использование статистики цитирования и ссылок, подобно тому, как это делается в Индексе научного цитирования SCI. В нем реализуется важная идея об использовании наличия ссылок для поиска информации и оценки научных публикаций. Эта идея нашла применение в методах оценки релевантности с использованием связей между web-страницами в WWW.

4. Анализ различных методов оценки релевантности с учетом наличия связей между web-страницами в WWW показал, что все они применяют и развивают идею, использованную в индексе научного цитирования для

90 оценки научных публикаций. Выделяются два наиболее интересных метода: PageRank и HITS. PageRank использует «цитаты» и их веса для определения оценки релевантности web-страницы. Таким образом, оценки релевантности каждой web-страницы зависят от количества её «цитат» и от оценок релевантности самих этих «цитат». HITS для этой цели использует два понятия «авторитеты» и «центры». Авторитеты и центры учитывают взаимно-усиливающуюся связь: «хорошие» центры ссылаются на многие «хорошие» авторитеты а «хорошие» авторитеты цитируются многими «хорошими» центрами.

5. Тем не менее, применение существующих методов оценки релевантности на основе структуры связей между web-страницами в WWW, включая PageRank и HITS, так и как применение традиционных методов, не обеспечивает релевантных ответов поисковой машины. Поэтому необходимо найти более совершенный метод оценки релевантности, учитывающие связи между web-страницами в WWW.

6. Полученная в диссертационной работе новая модель процесса броузинга в WWW позволяет построить новую формулу для оценки релевантности. В этой модели, кроме вероятностей движения по ссылкам и прыжка в случайную web-страницу, учитывается и вероятность перемещения в предыдущую web-страницу путем нажатия на кнопку «назад» программы броузера.

7. Разработанный новый метод оценки релевантности МОРСТ с использованием связей между web-страницами в WWW, показал свою эффективность в механизме оценки релевантности поисковой машины. В этом методе вводится новое понятие «термин-подмножество». Согласно новому методу, для оценки релевантности учитываются только те связи, которые соединяют web-страницы внутри термин-подмножества. Каждая web-страница может находиться одновременно в нескольких термин-подмножествах, и, таким образом, может иметь несколько оценок реле

91 вантности. С применением термин-подмножеств, шум ссылок чисто навигационного характера уменьшается до минимума.

8. Применение закона рассеяния информации Бредфорда позволяет разработать новый метод, с помощью которого выделяется ядро информационного потока WWW.

9. Разработанная усовершенствованная структурная схема для поисковой машины позволяет создать новую более эффективную поисковую машину.

10.Экспериментальные исследования показали преимущества разработанных методов оценки релевантности.

11 .Отдельные положения диссертации могут быть использованы при обучении студентов технического университета по специальности «ЭВМ, комплексы, системы и сети» в рамках дисциплин «Структура данных» и «Сети ЭВМ».

92

1. Бродер А., Винет Дж., Кумар Р., Магул Ф., Рагхаван П., Раджагопалан Ш., Стата Р., Томкинс Э. Структура Веба в виде графа // Банковские технологии № 1, 2001. VAVw.bizcom.ru/internet/2001 -01 /02.html

2. Гарфилд Ю. Можно ли выявлять и оценивать научные достижения и научную продуктивность // Вестник АН СССР № 7, 1982. с. 42-50 www.prometeus.nsc.ru/science/citation/garfild.ssi

3. Ефимов А.Н. Информация: ценность, старение, рассеяние. М.: Знание, 1978.-64 с.

4. Ефимов А.Н. Информационный взрыв: проблемы реальные и мнимые. М.: Наука, 1985.

5. Ефимов А.Н., Шойхер М.В. Интернет как информационный массив. Применимы ли общие информационные законы к Интернет // М.,1998. www.corbina.ru/~msh/papers/paperl/nodel .html

6. Игер Б. Работа в Интернет. М.:, Бином, 1996. 313 с.

7. Кара-Мурза С.Г. Цитирование в науке и подходы к оценке научного // Вестник АН СССР № 5, 1981. с. 68-75. www.prometeus.nsc.ru/science/citation/karmurza.ssi

8. Кемени Дж. Снелл Дж. Конечные цепи Маркова М.: Наука, 1970.- 271 с.

9. Кузнецов С. Методы поиска информации внутри Интернет. М.: Познавательная книга плюс, 2001. 224 с.

10. Ю.Кульгин М. Технология корпоративных сетей. Санкт-Петербург: Питер, 1999. 699 с.

11. И.Морозов В.П., Тихомиров В.П., Хрусталев Е.Ю. Гипертексты в экономике. М.: Финансы и статистика, 1997. 254 с.

12. Налимов В.В., Мульченко З.М. Наукометрия. М.: Наука, 1969. 192 с.

13. Нанс Б. Компьютерные сети. М.: Бином, 1996. 395 с.93

14. Нестеров А.В. Гипертекст: тензорный подход // НТИ, серия 2, № 8, 1991. с. 22-26.

15. Нестеров А.В. Тензорный подход к анализу и синтезу систем // НТИ, серия 2, № 9,1995. с. 26-31.16.0'Брайен Т., Подж С., Уайт Дж. Microsoft Access 97 Разработка приложений. Киев: BHV, 1998. - 633 с.

16. Плинатус А.А. Сборник лекции по курсу «Информатика» (раздел первый). М.: Московский юридический институт МВД РФ, 1996. 36 с. www.km.ru/education/refshow.asp?id=BEE9086152E946C7A7EDC2310974 6A86&search=%F0%E5%EB%E5%E2%E0%ED%F2%ED%EE%Fl%F2%FC

17. Прайс Д.С. Квоты цитирования в точных и не точных технике и ненауке // Вопросы философии № 3,1971 с. 149-155. www.prometeus.nsc .ru/science/ citation/price, ssi

18. Семенов Ю.А. Протоколы и ресурсы Интернет. М.: Радио и связь, 1996. -318с.

19. Субботин М.М. Новая информационная технология: создание и обработка гипертекстов // НТИ, серия 2, № 5, 1988.

20. Субботин М.М. Гипертекст новая форма письменной коммуникации. М.: Итоги науки и техники, серия «Информатика», том. 18, 1994. -158 с.

21. Феллер В. Введение в теорию вероятностей и ее приложения. М.: Мир, т. 1, 1967.-500 с.

22. Фридман В. Поиск в Internet новые методики // Компьютерные вести - № 27, 28, 2000.www.kv.by/index.cgi?id=2000270601. www.kv.by/index.cgi?id=2000280601.

23. Фролов А.В., Фролов Г.В. Глобальные компьютерные сети. М.: Диалог-МИФИ, 1996.-283 с.

24. Храмцов П.Б. Моделирование и анализ работы информационно-поисковых систем Интернет // Открытые системы № 6, 1996.94www.osp.ru/os/1996/06/46.htm.

25. Храмцов П.Б. Теоретическое обоснование и разработка распределенной гипертекстовой информационной системы: Автореф. . кан. тех. наук. М., 1997.-20 с.

26. Штат С. Мир компьютерных сетей. Киев: BHV, 1996. 287 с.

27. Шуткин JI.B. Применение теории паттернов к разработке гипертекстовых и мультимедиа программных продуктов // НТИ, серия 2, № 8, 1994.-с. 22-24.

28. Шуткин JI.B. Анализ структур гипермедиа изделий с помощью теории паттернов // НТИ, серия 2, № 7, 1995. с. 19-23.

29. Шуткин JI.B. Паттерновое моделирование гипертекстов // НТИ, серия 2, №9, 1995.-с. 20-26.

30. Эпштейн B.JI. Гипертекст новая парадигма информатики // Автоматика и телемеханика, № 11,1991.

31. Яблонский А.И. Модели и методы исследования науки. М.: Эдиториал УРСС, 2001. 400 с.

32. Atkins Н. The ISI Web of Science Links and Electronic Journals // D-Lib Magazine, Vol. 5, Num. 9, September 1999. www.dlib.org/dlib/september99/atkins/09atkins.html.

33. Botafogo R., Shneiderman B. Identifying aggregates in hypertext structures // Proc. of ACM Hypertext'91, 1991. pp. 63-74.

34. Botafogo R, Rivlin E., Shneiderman B. Structural analysis of Hypertext: Identifying hierarchies and useful metrics // ACM Trans. Inf. Sys., 1992. -pp. 142-180.

35. Bradford S.C. Documentation. Washington, D.C.: Public Affairs Press, 1950. -156 p.

36. Brahat K., Broder A. A technique for measuring the relative size and overlap of public web search engines // Proceedings of the 7th World Wide Web conference (WWW7), 1998.95

37. Brahat К., Henzinger M. R. Improved algoritms for topic distillation in hyperlinked environment I I Proceedings of the 21st ACM SIGIR conference on research and development in information retrieval, 1998. pp. 469-477.

38. Brin S., Page L. The Anatomy of a Large-Scale Hypertextual Web Search Engine // Proc. 7th International WWW Conferences, 1998. itman.narod.m/articles/html/googleanat.htm.

39. Chakrabarti S., Dom В., Gibson D., Kleinberg J., Kumar R., Raghavan P., Ra-jagopalan S., Tomkins A. Mining the link structure of the World Wide Web // February 1999. www.cs.cornell.edu/home/kleinber/kleiber.htm#papers.

40. Chakrabarti S., Dom В., Kumar R., Raghavan P., Rajagopalan S., Tomkins A. Hypersearching the Web // Scientific American, June 1999.

41. Chakrabarti S., Dom В., Gibson D., Kumar R., Raghavan P., Rajagopalan S., Tomkins A. Topic Distillation and Spectral Filtering // Artificial Intelligence Review № 13, 1999. pp. 409-435.

42. Chakrabarti S., Dom В., Indyk P. Enhanced hypertext classification using hyperlinks // ACM SIGMOD conference on management of data, Seattle, WA, 1998.

43. Garfield E. Citation indexes to science: a new dimension in documentation through association of ideas // Science № 3159, vol. 122, July 1955. pp. 108-111. garfield.library.upenn.edu/essays/v6p468yl983.pdf.

44. Garfield E. The Impact Factor // Current Contents, June 1994. www.isinet.com/isi/hot/essays/journalcitationreports/7.html

45. Garner R. A computer oriented, graph theoretic analysis of citation index structures Drexel Press - 1967. - 46 p.96

46. Gibson D., Kleinberg J., Raghavan P. Structural analysis of the World Wide

47. Web // www.w3.org/1998/! 1/05/WC-workshop/Papers/kleinberl .html.

48. Gibson D., Kleinberg J., Raghavan P. Inferring Web Communities from Link Topology // Proc. 9th ACM Conference on Hypertext and Hypermedia, 1998. www.es.cornell.edu/home/kleinber/kleiber.htm#papers.

49. Golub G., Van Loan C.F. Matrix Computation. Baltimore, Maryland: John Hopkins University Press, 1989.

50. Huberman В., Pirolli P., Pitkow J., Lukose R. Strong regularities in World Wide Web Surfing // Science, vol. 280, April 1998. pp. 95-97.

51. Kleinberg J. Authoritative Sources in a Hyperlinked Environment. Proc. ACM-SIAM Symposium on Discrete Algorithms, 1998. www.cs.cornell.edu/home/kleinber/kleiber.htm#papers.

52. Kumar R., Raghavan P., Rajagopaian S., Sivakumar D., Tomkins A., Upfalt E. The Web as a graph // www.citeseer.org.

53. Kumar R., Raghavan P., Rajagopaian S., Sivakumar D., Tomkins A., Upfalt E. Stochastic models for the web graph // www.citeseer.org.

54. Marchiori M. The quest for correct information on the web: Hyper search engines // Proceedings of the 6th World Wide Web conference (WWW6), 1997.

55. Page L. PageRank: Bringing Order to the Web // Stanford Digital Libraries Working Paper 1997-0072.www-ped. standford.edu/page/papers/pagerank/index.htm.

56. Pirolli P., Pitkow J., Rao R. Silk from s sow's ear: Extracting useable structures from the web // Proc. of ACM SHIGCHI conference of human factor in computing, 1996.

57. Rivlin E., Botafogo R., Shneiderman B. Navigating in hyperspace: Designing a structure-based toolbox // Communication of the ACM, 1994. pp. 87-96.

58. Rosie J. Inside a Search Engine // SPECTRUM, June, 2000. pp. 92-93.www.komisc.ru/mathematic/uspensky/works/insideasearchengine.html.97