автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Тематико-ориентированные методы информационного поиска

1. Информационный поиск

1.1. Задачи информационного поиска.

1.2. Поиск в Интернет.

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

1.2.2. Индексы поисковых систем.

1.2.3. Распределенные поисковые системы.

1.3. Модели информационного поиска.

1.3.1. Векторная модель.

1.3.2. Латентно-семантический анализ.

1.4. Критерии оценки эффективности.

1.5. Тестовые наборы данных.

1.5.1. Тестовые коллекции ТЯЕС.

1.5.2. Набор данных Яеи1ег8

1.6. Тематико-ориентированные методы поиска.

2. Поиск документов заданной тематики в Интернет

2.1. Архитектура сетевого робота.

2.2. Оценка тематической близости.

2.2.1. Уточнение тематического фильтра.

2.3. Стратегия обхода Интернет ресурсов.

2.4. Экспериментальные результаты.

2.4.1. Тестирование тематического фильтра.

2.4.2. Эксперименты со стратегией обхода.

2.5. Выводы.

3. Маршрутизация запросов в распределенных поисковых системах 35 3.1. Маршрутизация запросов.

3.1.1. Критерии оценки качества.

3.2. Методы маршрутизации запросов.

3.2.1. Построение описаний коллекций.

3.2.2. Выбор коллекций.

3.2.3. Распределение ресурсов.

3.3. Эксперименты.

3.3.1. Тестовый набор данных.

3.3.2. Экспериментальные результаты.

3.4. Выводы.

4. Оценка тематического подобия текстовых документов

4.1. Описание метода.

4.1.1. Предварительная обработка документов.

4.1.2. Построение тематического окружения документа

4.1.3. Формирование множеств ключевых слов.

4.1.4. Вычисление относительных оценок тематического подобия.

4.2. Экспериментальные результаты.

4.2.1. Эксперименты с коллекцией статей по комбинаторике

4.2.2. Эксперименты с Reuters

4.3. Обсуждение.

4.4. Выводы.

5. Классификация документов по тематикам

5.1. Классификация с учетом семантической близости слов

5.1.1. Описания тематик и документов.

5.1.2. Вычисление оценок близости.

5.1.3. Тематическая близость термов.

5.2. Проверка эффективности метода.

5.2.1. Экспериментальная база.

5.2.2. Эксперименты.

5.2.3. Ошибки классификации

5.3. Вычислительная трудоемкость.

5.4. Выводы.

5.4. Выводы

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

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

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

Заключение

В работе получены следующие основные результаты:

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

2. Предложен метод построения описаний коллекций и выбора коллекций для обслуживания запроса в распределенных поисковых системах, учитывающий тематическую специализацию коллекций. Использование тематических описаний позволяет значительно (до 40%) сократить размер описаний без потерь в качестве маршрутизации.

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

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

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

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

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

8. Проведена обширная экспериментальная проверка предложенных методов на основе стандартных наборов тестовых данных.

Многие из этих результататов согласуются с результатами полученными другими исследователями [41, 24], что важно в связи с эмпирическим характером методов информационного поиска.

Отметим также, что результат, сформулированный в пункте 4, демонстрирует неточность вывода о возможности удаления информации о редких термов из описаний, сделанного в [23]. Эта неточность обусловлена использованием в [23] относительно грубых критериев оценки качества маршрутизации.

Предложенные методы и полученные результаты использованы при разработке распределенной поисковой системы OASIS, прототип которой доступен по адресу www.oasis-europe.org.

1. Д.О. Брюхов, В.И. Задорожный, J1.A. Калиниченко, М.Ю. Курошев, С.С. Шумилов Интероперабельные информационные системы: архитектуры и технологии. Системы управления базами данных, 4, 1995.

2. Даниэла Флореску, Ал он Леви, Альберто Мендельсон. Технологии баз данных для World-Wide Web: обзор. Системы управления базами данных, 4, 1998.

3. И.С. Некрестьянов, В.Ю. Добрынин, В.В. Клюев. Оценка тематического подобия текстовых документов. Труды второй всероссийской научной конференции "Электронные библиотеки", стр. 204210, Протвино, Россия, сентябрь 2000.

4. Е.В. Романова, М.В. Романов, И.С. Некрестьянов. Использование интелектуальных сетевых роботов для построения тематических коллекций. Программирование, 3:63-71, 2000.

5. Дж. Голуб, Ч. Ван Лоун. Матричные вычисления. Издательство "Мир", Москва, 1999.

6. В.Ю. Добрынин, И.С. Некрестьянов. Задача выбора тематических коллекций, релевантных запросу. Труды Всероссийской научно-методической конференции "Интернет и современное сообщество", Санкт-Петербург, декабрь 1998.

7. Илан Гринберг, Ли Гарбер. Разработка новых технологий информационного поиска. Открытые Системы, 10, 1999.

8. И.Е. Кураленок, И.С. Некрестьянов. Автоматическая классификация документов с использованием семантического анализа. Программирование, 4:31-41, 2000.

9. В. К. Степанов. Русскоязычные поисковые механизмы в Интернет. ComputerWorld Россия, 11, 1997.

10. И.С. Некрестьянов. Маршрутизация запросов в системах распределенного поиска. Труды второй всероссийской научной конференции "Электронные библиотеки", стр. 280-287, Протвино, Россия, сентябрь 2000.

11. O.JI. Жижимов. Введение в Z39.50. Издательство НГОНБ, Новосибирск, 2000.

12. Елена Карташева. Интеллектуальные поисковые системы Excalibur. Сети, б, 1997.

13. I.J. Aalbersberg. Incremental relevance feedback. In Proceedings of the Fifteenth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 11 22, 1992.

14. J. Allan. Incremental relevance feedback. In Proceedings of the 19th International Conference on Research and Development in Information Retrieval (SIGIR '96), pages 298-306, April 1996.

15. A. Ardo and S. Lundberg. A regional distributed WWW search and indexing service — the DESIRE way. Computer Networks and ISDN Systems, 30:173-183, 1998.

16. Ricardo Baeza-Yates and Berthier Ribeiro-Neto. Modern Information Retrieval. ACM Press, 1999.

17. Douglas L. Baker and Andrew Kachites McCallum. Distributional clustering of words for text classification. In Proceedings of the SIGIR '98, pages 96-103, 1998.

18. M. Berry. Large scale singular value computations. International Journal of Supercomputer Applications, 6:13-49, 1992.

19. C. M. Bowman, Peter B. Danzig, Darren R. Hardy, Udi Manber, and Michael F. Schwartz. The harvest information discovery and access system. Computer Networks and ISDN Systems, pages 119-125, December 1996.

20. J. Callan. Document filtering with inference networks. In Proceedings of the 19th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 262-269, 1996.

21. J. Callan. Learning while filtering documents. In Proc. of SIGIR'98, pages 224-231, Melbourne, Australia, 1998.

22. James P. Callan, Zhihong Lu, and W. Bruce Croft. Searching distributed collections with inference networks. In Proceedings of the SIGIR'95, 1995.

23. Soumen Chakrabarti, Martin van den Berg, and Byron Doxn. Focused crawling: A new approach to topic-specific web resource discovery. In Proc. of the WWW-8, May 1999.

24. A. S. Chakravarthy and K. B. Haase. NetSerf: Using semantic knowledge to find internet information archives. In Proc. of the SIGIR'95, pages 4 11, 1995.

25. F. Cheong. Internet agents: Spiders, wanders, brokers, and bots. New Riders, 1996.

26. Bruce W. Croft and Jinxi Xu. Query expansion using local and global document analysis. In Proc. of the SIGIR'96, pages 4-11, 1996.

27. Carolyn J. Crouch. Experiments in automatic statistical thesaurus construction. In Proc. of the SIGIR'92, pages 77-88, Copenhagen, Denmark, 1992.

28. J. Cullum and R. Willougby. Lanczos algorithms for large symmetric eigenvalue computations, chapter Real rectangular matrix. Brikhauser, Boston, 1985.

29. P. Danzig, S. Li, and K. Obraczka. Distributed indexing of autonomous internet services. Computing Systems, 5(4):433-459, 1992.

30. Peter B. Danzig, Jongsuk Ahn, John Noll, and Katia Obraczka. Distributed indexing: A scalable mechanism for distributed information retrieval. In Proc. of the SIGIR'91, 1991.

31. Koller Daphen and Sahami Mehran. Hierarchically classifying documents using very few words. In Proc. of the ICML'97, pages 170178, 1997.

32. D. Drelinger and A. E. Howe. Expiriences wth selecting search engines using MetaSearch. ACM Transactions on Information Systems, 15(3):195-222, 1997.

33. S. Dumais. Improving the retrieval of information from external sources. 1991.

34. S. Dumais. Latent semantic indexing: TREC-3 report. In Proc. of the Third Text REtrieval Conference, 1995.

35. P.W. Foltz. Using latent semantic indexing for information filtering. In ACM Conference on Office Information Systems (COIS), pages 40-47, 1990.

36. J. French, A. Powell, C. Viles, T. Emmitt, and K. Prey. Evaluating database selection techniques: A testbed and experiment. In Proc. of the SIGIR'98, Melbourne, Australia, August 1998.

37. L. Gravano and H. Garcia-Molina. Generalizing GIOSS to vector-space databases and broker hierarchies. In Proc. of the VLDB'95, 1995.

38. L. Gravano, H. Garcia-Molina, and A. Tomasic. Precision and recall of GIOSS estimators for database discovery. In Proc. of the 3rd International Conference on Parallel and Distributed Information Systems (PDIS'94), 1994.

39. L. Gravano, H. Garcia-Molina, and A. Tomasic. Proc. of the the effectiveness of GIOSS for the text-database discovery problem. In Proc. of the SIGMOD'94, 1994.

40. Luis Gravano. Querying Multiple Document Collections Accross the Internet. PhD thesis, Stanford University, August 1997.

41. Luis Gravano, Chen-Chuan K. Chang, Hector Garcia-Molina, and Andreas Paepcke. STARTS: Stanford proposal for internet meta-searching. In Proceedings of the International Conference on Management of Data, 1997.

42. D. Harman. Latent semantic indexing (LSI) and TREC-2. In Proc. of the Second Text REtrieval Conference, 1994.

43. Vasileios Hatzivassiloglou, Luis Gravano, and Ankineedu Maganti. An investigation of linguistic features and clustering algorithms for topical document clustering. In Proc. of the SIGIR'2000, 2000.

44. Allison Powell James. The impact of database selection on distributed searching. In Proc. of the SIGIR'OO, 2000.

45. T. Joachims. A probabilistic analysis of the Rocchio algorithm with TFIDF for text categorization. In Proc. of the International Conference on Machine Learning (ICML), 1997.

46. Cho Junghoo, Garcia-Molina Hector, and Page Lawrence. Efficient crawling through URL ordering. In Proceedings of the Seventh International World Wide Web Conference, 1998.

47. B. Kahle. Preserving the Internet. Scientific American, pages 82-83, March 1997.

48. B. Kahle, H. Morris, J. Goldman, T. Erickson, and J. Curran. Interfaces for distributed systems of information servers. Journal of the American Society for Information Science, 44(8):453-485, 1993.

49. Fredrik Kilander, Eva Fehraeus, and Jacob Palme. PEFNA: The private filtering news agent. Technical report, Department of Computer and Systems Sciences, Stockholm University, February 1997.

50. David King. Specialized search engines: Alternatives to the big guys. ONLINE, 24(3), May 2000.

51. T. Koch, A. Ardo, A. Bremmer, and S. Lundberg. The building and maintenance of robot based internet search services: A review of current indexing and data collection methods. Technical report, Lund University Library, Sweden, 1996.

52. M. Koster. Robots in the Web: threat or treat? Connexions, 4(9), 1995.

53. T. Landauer, P. Foltz, and D. Laham. An introduction to latent semantic analysis. Discourse Processes, 25:259-284.

54. Steve Lawrence and C. Lee Giles. Searching the World Wide Web. Science, 280(5360):98-100, 1998.

55. Anna Le Calve and Jacques Savoy. Database merging strategy based on logistic regression. Information Processing and Management, 36(3):341-359, May 2000.

56. D. Lewis and M. Ringuette. A comparison of two learning algorithms for text categorisation. In Proc. of the Third Annual Symposium on Document Analysys and Information Retrieval, pages 81-93, 1994.

57. Qi Lu, Matthias Eichstaedt, and Daniel Ford. Efficient profile matching for large scale webcasting.

58. Z. Lu, J. Callan, and W. Croft. Measures in collection ranking evaluation. Technical Report TR96-39, University of Massachusetts, 1996.

59. Dietr Merkl. Lessons learned in text document classification. In Proc. of the Workshop on Self-Organizing Maps (WSOM'97), pages 316-321, Helsinki, Finland, June 1997.

60. Dietr Merkl. A Handbook of Natural Language Processing: Techniques and Applications for the Processing of Language as Text, chapter Text data mining. Marcel Dekker, New York, 1998.

61. Lawrence Page, Sergey Brin, and Rajeev Motwani. The PageRank citation ranking: Bringing order to the Web. February 1998.

62. Ron Papka and James Allan. Document classification using multiword features. In Proc. of the CIKM'98, pages 124-131, New-York, November 1998.

63. A. Patel, L. Petrosjan, and W. Rosenstiel, editors. OASIS: Distributed Search System in the Internet. St. Petersburg State University Published Press, St. Petersburg, 1999.

64. Brian Pincerton. Finding what people want: Expirences with the webcrawler. In Proc. of the second International World-Wide Web Conference, 1992.

65. Yonggang Qui and H. P. Frei. Concept based query expansion. In Proc. of the SIGIR'93, pages 160-169, Pitsburgh, USA, 1993.

66. G. Salton and C. Buckley. Term-weighting approaches in automatic text retrieval. Information Processing and Management, 24:513-523, 1988.

67. G. Salton and M. J. McGill. Introduction to modern Information Retrieval. McGraw-Hill Computer Science Series. McGraw-Hill, New York, 1983.

68. Gerald Salton, James Allan, and Amit Singhal. Automatic text decomposition and structuring. Information Processing & Management, 32(2):127-138, 1996.

69. Gerald Salton, Amit Singhal, Mandar Mitra, and Chris Buckley. Automatic text decomposition and summarization. Information Processing & Management, 33(2):193-208, 1997.

70. Jacques Savoy and Justin Picard. Report on the TREC-8 Experiment: Searching on the Web and in Distributed Collections. In Proc. of the TREC'8, 1999.

71. Amit Singhal, Mandar Mitra, and Chris Buckley. Learning routing queries in a query zone. In Proc. of the SIGIR'97, pages 25-32, July 1997.

72. Raymie Stata, Krishna Bharat, and Farzin Maghoul. The term vector database: fast access to indexing terms for web pages. In Proc. of the WWW-9, May 2000.

73. Atsushi Sugiura and Oren Etzioni. Query routing for web search engines: Architecture and experiments. In Proc. of the WWW-9, May 2000.

74. A. Tomasic, L. Gravano, C. Lue, P. Schwarz, and L. Haas. Data structures for efficient broker implementation. ACM Transactions on Information Systems, 15(2), April 1997.

75. C. Viles and J. French. Dissemination of collection wide information in a distributed information retrieval system. In Proc. of the SIGIR'95, pages 12 20, 1995.

76. Elen Voorhees and Donna Harman. Overview of the Sixth Text REtrieval Conference (TREC-6). In NIST Special Publication 500-240: The Sixth Text REtrieval Conference (TREC-6), 1997.

77. Scott A. Weiss, Simon Kasif, and Eric Brill. Text classification in USENET newsgroups: A progress report.

78. Jinxi Xu and Jamie Callan. Effective retrieval with distributed collections. In Proc. of the SIGIR'98, 1998.

79. Y. Yang and J. Pederson. Feature selection in statistical learning of text categorization. In Proc. of the ICML'97, pages 412-420, 1997.