Решение задачи тематического информационного поиска в рунет тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Козлов, Дмитрий Дмитриевич

  • Козлов, Дмитрий Дмитриевич
  • кандидат физико-математических науккандидат физико-математических наук
  • 2004, Москва
  • Специальность ВАК РФ05.13.11
  • Количество страниц 76
Козлов, Дмитрий Дмитриевич. Решение задачи тематического информационного поиска в рунет: дис. кандидат физико-математических наук: 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей. Москва. 2004. 76 с.

Оглавление диссертации кандидат физико-математических наук Козлов, Дмитрий Дмитриевич

i* Введение.

Задача тематического информационного поиска в Интернет.

Рекомендованный список диссертаций по специальности «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», 05.13.11 шифр ВАК

Введение диссертации (часть автореферата) на тему «Решение задачи тематического информационного поиска в рунет»

Цель работы.7

Метод решения.7

Структура работы.7

1. Существующие средства и методы ИП в Интернет.9

1.1 Промышленные ИПС в Интернет.9

1.1.1 Системы поиска по ключевым словам.9

1.1.2 Алгоритм PageRank.13

1.1.3 Классификаторы.14

1.1.4 Метапоисковые системы.14

1.2 Методы тематического ИП в Интернет.17

Ъ 1.2.1 Тематические роботы.18

1.2.2 Поиск тематических сообществ в Web.21

1.2.2.1 Поиск тематических сообществ на основе двудольных графов.22

1.2.2.2 Поиск тематических сообществ на основе построения NK-клан графа.24

1.2.2.3 Поиск тематических сообществ на основе максимального потока.25

1.2.2.4 Алгоритмы семейства HITS.27

1.2.2.5 Алгоритм SALSA.32

1.3 Выводы.34

2. Модель тематического информационного поиска в Интернет.36

2.1 Традиционная модель информационного поиска.36

2.2 Анализ задачи тематического ИП в Интернет.37

2.2.1 Особенности задачи тематического ИП.37

2.2.2 Особенности Интернет как хранилища информации.38 л 2.2.3 Выводы.41

2.3 Модель тематического ИП в Интернет.42

14 2.4 Формальная постановка задачи тематического ИП в Интернет.43

3. Решение задачи тематического информационного поиска в Интернет.44

3.1 Общая схема работы системы для тематического ИП в Интернет.44

3.2 Общий подход к построению пространства поиска.47

3.3 Фаза построения пространства поиска.48

3.3.1 Типы гиперссылок.48

3.3.2 Типы страниц.48

3.3.3 Эвристики отбора ссылок.49

3.3.4 Построение пространства поиска.50

3.3.5 Построение графа ресурсов.52

3.4 Фаза анализа.53

3.4.1 Оценка релевантности страниц.54

3.4.2 Оценка значимости ресурсов.55

3.4.3 Выбор направления поиска.56

3.4.4 Предварительный отбор ресурсов для включения в модель темы.57

3.4.5 Фильтрация ресурсов по языку и по оценке релевантности.57

3.5 Обратная связь.58

3.6 Выводы.59

4 Экспериментальное исследование подхода.60

Л 4.1 Цели и методы экспериментального исследования.60

4.2 Экспериментальная реализация предложенного алгоритма.62

4.3 Результаты экспериментального исследования.64

4.3.1 Общие результаты экспериментов.64

4.4 Оценка вычислительной сложности.67

4.5 Выводы.69

Заключение.71

Литература.72 Л Л

Введение

Задача тематического информационного поиска в Интернет

С конца 50-х годов [36] применительно к библиотечным системам активно разрабатывались методы решения так называемой традиционной задачи информационного поиска (ИП) [8].

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

Традиционная задача ИП основывалась на следующих предположениях об информационной потребности пользователя:

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

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

• в процессе поиска информационная потребность пользователя не изменяется. Результат поиска определяется одним запросом.

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

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

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

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

• статичность (новые документы появляются относительно редко);

• локальность (документы собраны в базу данных);

• существует определенный регламент появления документов.

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

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

Свойства пространства поиска:

• отсутствует централизованное хранилище метаинформации об объектах поиска;

• невозможно построить единую базу данных объектов поиска;

• объекты поиска не содержат описания их содержимого;

• отсутствует регламент создания объектов поиска;

• большинство объектов поиска представляют собой гипертекстовые страницы, которые могут содержать гиперссылки на другие страницы. Страницы, связанные гиперссылками, образуют граф Web.

Свойства информационной потребности пользователя:

• в начале поиска пользователь не знает четко свою информационную потребность, а имеет о ней лишь общее представление — тему. Поэтому он не может сформулировать запрос к ИПС, в ответ на который будут выданы интересующие его объекты;

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

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

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

Актуальность темы

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

Для информационного поиска в Интернет в настоящее время наиболее широко используются системы поиска по ключевым словам (СПКС), например, Google [64] или Yandex [65]. В работах [15],[18] была обоснована неэффективность применения таких систем для тематического ИП в силу того, что они построены на основе традиционной модели ИП (см. раздел 2.1), не учитывающей особенностей тематического ИП.

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

В последние годы исследования тематической структуры Интернет [16], [45], [46] продемонстрировали принципиальную возможность решать некоторые частные случаи задачи тематического ИП в Интернет без предварительной обработки данных (построения базы данных объектов поиска) и без наличия информации об организации предметной области (например, онтологии). Однако методы, предложенные в [45],[55], не учитывают важных особенностей задачи тематического ИП: они не позволяют пользователю осуществлять поиск итерационно, уточняя информационную потребность в процессе поиска.

Цель работы

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

В рамках данной работы ставятся следующие задачи:

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

2. Разработать алгоритм тематического ИП в Интернет, который реализует эту модель.

3. Провести экспериментальное исследование эффективности предложенного алгоритма по сравнению с существующими методами тематического ИП в Интернет.

Метод решения

В данной работе предлагается метод решения задачи тематического ИП в Интернет, который обобщает широко применяемые в этой области методы поиска тематических сообществ в части направленной организации итерационного процесса поиска, новой интерпретации механизма обратной связи, расширения алгоритма анализа структуры гиперссылок (алгоритма SALSA [55]) средствами анализа текста.

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

Структура работы

Похожие диссертационные работы по специальности «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», 05.13.11 шифр ВАК

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Козлов, Дмитрий Дмитриевич

Основные результаты работы заключаются в следующем:

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

2. Разработан алгоритм тематического информационного поиска в Интернет, обобщающий методы поиска тематических сообществ в части:

- направленной организации итерационного процесса поиска;

- новой интерпретации механизма обратной связи;

- расширения алгоритма анализа структуры гиперссылок (алгоритма SALSA) средствами анализа текстов страниц.

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

Результаты данной работы могут быть применены в следующих областях:

1. Для расширения функциональности систем поиска по ключевым словам с целью предоставления пользователям средств тематического ИП в Интернет.

2. Для автоматизации построения вторичных тематических информационных ресурсов — тематических каталогов (portholes [48]).

Наиболее перспективным представляется развитие предложенных в работе методов по следующим направлениям:

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

2. Внедрение в алгоритм более развитых средств анализа текста, в частности, средств автоматической классификации.

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

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Козлов, Дмитрий Дмитриевич, 2004 год

1. Ахо А., Ульман Д., Теория синтаксического анализа, перевода и компиляции, М., Мир, 1978.

2. Крюков Д.В. Поисковая система "Turtle". Физиология и анатомия. http://www.turtle.ru/db/architecture/

3. Мальковский М. Г., Грацианова Т. Ю., Полякова И. Н., Прикладное программное обеспечение: системы автоматической обработки текстов, Учебное пособие для студентов факультета ВМиК МГУ, Москва, МГУ, 2000

4. Мидоу Ч., Анализ информационно-поисковых систем, М., Мир, 1970

5. Некрестьянов И. Тематико-ориентированные методы информационного поиска. Диссертация. Санкт-Петербург, 2000

6. Райдингс К. Растолкованный PageRank. http://digits.ru/articles/promotion/pagerank.html. (пер. Садовский А.)

7. Россеева О., Загорулько Ю. Организация эффективного поиска на основе онтологий. Труды Международного семинара Диалог'2001.

8. Солтон Дж., Динамические библиотечно-информационные системы, М., Мир, 1979.

9. Сэлтон Г., Автоматическая обработка, хранение и поиск информации, М., «Советское радио», 1973

10. Черный А. И., Введение в теорию информационного поиска, М., Наука, 1975

11. Хензингер М. Анализ гиперссылок в Web. Открытые системы, 2001, N10, http://www.osp.ru/2001/10/050.htm.

12. Bates М., The design of browsing and berrypicking techniques for the online search interface. Online Review 13,5,1989

13. Belkin N., Cool C., Stein A., Thiel U. Cases, Scripts, and Information-Seeking Strategies: On the Desingn of Interactive Information Retrieval Systems, Expert Systems and Applications, 9(3): 379-395 1994

14. Bergman K., The Deep Web: Surfacing Hidden Value, BrightPlanet.com LLC, http://www.completeplanet.com/Tutorials/DeepWeb/index.asp

15. Brahat K. SearchPad: explicit Capture of Search Context to Support Web Search, Proceedings of the WWW9 Conference.

16. Davison В. Topical locality in the Web. Proceedings of the ACM SIGIR'2000 Conference, 2000.

17. Etzioni 0., The World Wide Web: quagmire or gold mine?, Communications of the ACM, November 1996.

18. O'Day V., Jeffries R. Orienteering in an Information Landscape: How Information Seekers Get From here to There. Proceedings of INTERCHI '93, 1993.

19. Seberg E., Etzioni O., The MetaCrawler Architecture for Resource Aggregation on the Web, http://www.cs.washington.edu/research/metacrawler. 1998

20. Inktomi Corp., Web Surpasses One Billion Documents, press release issued January 18, 2000, http://www.inktomi.com/new/press/billion.html

21. Mladenic D. Turning Yahoo Into an Automatic Web-Page Classifier. European Conference on Artificial Intelligence, 1998

22. Gruber T. Towards Principles for the Design of Ontologies Used for Knowledge Sharing. International Workshop on Formal Ontology, 1993.

23. Koenemann J. Supporting Interactive Information Retrieval Through Relevance Feedback, Proceedings of ACM CHI'96 Conference.

24. Pirolli P., Pitkow J., Rao R., Silk from a Sow's Ear: extracting Usable Structures from the Web, Proc. ACM Conf. Human Factors in Computing Systems, CHI'96, 1996

25. Flake G., Lawrence S., Giles C., Coetzee F. Self-Organization of the Web and Identification of Communities. IEEE Computer, 35(3), pp 66-71,2002.

26. Lawrence S., Bollacker K., Giles C., Digital Libraries and Autonomous Citation Indexing, IEEE Computer, pp. 67-71, June 1999

27. Lawrence S., Bollacker K., Giles C., Indexing and Retrieval of Scientific Literature, Proceedings of CIKM 1999 Conference, pp. 139-146

28. Lawrence S., Giles C., Accessibility of Information on the Web, Nature, vol.400, pp. 107-109,1999

29. Lawrence S., Giles C., Context and page analysis for improved web search, IEEE Internet Computing, July 1998, pp.3 8-46

30. Lawrence S., Giles C., Inquirus: The NECI Search Software, http://www.neci .nj .nec.com/homepages/lawrence/inquirus.html

31. Lawrence S., Giles C., Searching the Web: General and Scientific Information Access, IEEE Communications Magazine, January 1999, pp 116-122

32. Bollacker К., Lawrence S., Giles C., CiteSeer: An Autonomous {Web} Agent for Automatic Retrieval and Identification of Interesting Publications, Proceedings of the Second International Conference on Autonomous Agents, ACM Press, 1998, pp. 116— 123

33. Glover E., Lawrence S., Birmingham W., Giles C., Architecture of a Metasearch Engine that Supports User Information needs, Proceedings of CIKM-99 Conference, pp. 210216, ACM, 1999

34. Research Index Computer Science Directory http://citeseer.ni.nec.com/directory.html

35. Rijsbergen C., Information Retrieval, London, Butterworths, 1979

36. Salton G., Historical Note: The Past Thirty Years in Information Retrieval, Cornell University Technical Report 87-827

37. Salton G., Mathematics and information retrieval Cornell University Technical Report 78-332

38. Salton G., Buckley C., Term Weighting Approaches in Automatic Text Retrieval, Cornell University Technical Report 87-881

39. Salton G., Fox E., Wu H., Extended Boolean Information Retrieval, Cornell University Technical Report 82-511

40. Salton G., Buckley C. Improving retrieval performance by relevance feedback. Journal of the American Society for Information Science 41:288—297, 1990

41. Brin S., Page L. The anatomy of a large-scale hypertextual Web search engine. Proceedings of the WWW7 Conference, 1998.

42. Brin S., Page L., Motwani R., Winograd T. The PageRank citation ranking: Bringing order to the Web. Stanford Digital Library Technologies, Working Paper 1999-0120, 1998.

43. Bharat K., Henzinger M. Improved Algorithms for Topic Distillation in a Hyperlinked Environment. ACM SIGIR conference on Research and Development in IR, 1998.

44. Henzinger M. Link Analysis in Web Information Retrieval. IEEE Bulletin on Data Engineering, Vol. 23, N3,2000.

45. Chakrabarti S., Dom В., Kumar S., Raghavan P., Tomkins A., Gibson D., Kleinberg J. Mining the Web's link structure. IEEE Computer, 32(8) pp 60-67,1999

46. Chakrabarti S., В. Dom, D. Gibson, J. Kleinberg, P. Raghavan, S. Rajagopalan, Automatic resource list compilation by analyzing hyperlink structure and associated text. Proc. 7th International World Wide Web Conference, 1998.

47. Chakrabarti S. Integrating the Document Object Model with Hyperlinks for Enhanced Topic Distillation and Information Extraction. Proceedings of WWW 10 Conference, 2001

48. Chakrabarti S., Van Den Berg M., Dom B. Focused crawling: A new approach to topic-specific Web resource discovery. Eights World Wide Web Conference, Toronto, May 1999.

49. Kleinberg J. Authoritative sources in a hyperlinked environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998.

50. Gibson D., Kleinberg J., Raghavan P. Inferring Web communities from link topology. Proc. 9th ACM Conference on Hypertext and Hypermedia, 1998.

51. Kleinberg J., Kumar S., Raghavan P., Rajagopalan S., Tomkins A. The Web as a graph: Measurements, models and methods. Invited survey at the International Conference on Combinatorics and Computing, 1999.

52. Kumar S., Raghavan P., Rajagopalan S., Tomkins A. Trawling the Web for emerging cyber-communities. Eighth World Wide Web Conference, Toronto, Canada, May 1999.

53. Terveen L., Hill W., Amento B. Constructing, Organizing, and Visualizing Collections of Topically Related Web Resourses. ACM Transactions on Computer-Human Interaction, Vol 6, No 1, March 1999, Pages 67-94

54. Amento В., Terveen L., Hill W. Does "Authority" Mean Quality? Predicting Expert Quality Ratings of Web Documents. ACM SIGIR conference on Research and Development in IR, 2000.

55. Lempel R., Moran S. The Stochastic Approach for Link-Structure analysis (SALSA) and the TKS Effect. Ninth World Wide Web Conference, 2000

56. Borodin A., Roberts G., Rosenthal J., Tsaparas P. Finding Authorities and Hubs From Link Structures on the World Wide Web. Tenth World Wide Web Conference, Hong Kong, 2001

57. Shivakumar N., Garcia-Molina H. Finding Near-Replies of documents on the Web. Porceedings inWebDB'99,1999.

58. Broder A. Z., Kumar S. R., Maghoul F., Raghavan P., Rajagopalan S., Stata R., Tomkins A., Wiener J. L. Graph structure in the web. In Proc. of the WWW9, pp. 309-320,2000.

59. Hermans В., Intelligent Software Agents on the Internet: an inventory of currently offered functionality in the information society and a prediction of future developments, http://www.hermans.org/agents, 1996

60. Cavnar W., Trenkle J., N-gram-based text categorization, in Proceedings of SDAIR-94, 3rd Annual Symposium on Document Analysis and Information Retrieval, pp.161-175, 1994.

61. TREC-2002 Web Track Guidelines, TREC, 2002.

62. Сегалович И.В. Как работают поисковые системы, www.yandex.ru/papers/

63. Open Directory Project http://www.dmoz.org проект по созданию некоммерческого каталога.64. Google www.googIe.com65. Yandex www.vandex.ru

64. Стеммер Snowball http://snowball.tartarus.org

65. Davison В., Recognizing nepotistic links on the Web. AAAI-2000 Workshop on Artificial Intelligence for Web Seasrch, 2000.

66. Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962

67. СУБД Informix http://www.informix.com

68. Проект Jakarta, http://iakarta.apache.org

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