Методы информационного поиска тематических сообществ в Веб-пространстве тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Блеканов, Иван Станиславович

• Блеканов, Иван Станиславович
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Блеканов, Иван Станиславович

ВВЕДЕНИЕ.

1. Технические задачи информационного поиска.

2. Поиск в Веб-пространстве.

3. Постановка задачи данной работы.

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

5. Основные задачи работы.

6. Положения научной новизны.

7. Результаты.

ГЛАВА

ПРЕДСТАВЛЕНИЕ ВЕБ-ПРОСТРАНСТВА.

1.1. Структура Веб-графа.

1.2. Степенной закон распределения гиперссылок в Веб-графе.

1.3. Обход Веб-Графа.

1.4. Выводы.

ГЛАВА

ВЕБ-КРАУЛЕРЫ В ИНФОРМАЦИОННОМ ПОИСКЕ.

2.1. Критерии эффективной работы Веб-краулера.

2.2. Архитектурные особенности Веб-краулеров.

2.3. Архитектура Веб-краулера с универсальным ядром и ее реализация.

2.4. Поиск и обновление значимых Веб-страниц.

2.4.1. Метрики значимости Веб-страниц.

2.4.2. Типы Веб-краулеров.

2.4.3. Обновление Веб-страниц.

ГЛАВА

МЕТОДЫ И МОДЕЛИ ИНФОРМАЦИОННОГО ПОИСКА.

3.1. Модель документа.

3.2. Модель на множестве слов.

3.2.1. Проблемы выделения слов в документе.

3.2.2. Модель на стемминге документа.

3.2.3. Модель на взвешивании слов документа.

3.3. Модель с использованием пар слов.

3.4. Семантическая модель документа.

3.5. Модель на анализе гиперссылок.

3.5.1. Модель на алгоритме Клейнберга HITS.

3.5.1.1. Построение фокусированного Веб-графа в HITS алгоритме.

3.5.1.2. Вычисление индексных и авторитетных источников информации.

3.5.2. Модель на PageRank алгоритме.

3.5.2.1. Стандартный PageRank.

3.5.2.2. Модифицированный PageRank.

3.5.2.3. Итеративное вычисление PageRank.

ГЛАВА

ОЦЕНКА КАЧЕСТВА ИНОРМАЦИОННОГО ПОИСКА.

4.1. Базовые метрики оценки качества.

4.2. Дополнительные метрики оценки качества.

4.3. 11-точечный график полноты и точности.

4.4. Стандартные тестовые коллекции.

4.5. Выводы.

ГЛАВА

РЕАЛИЗАЦИЯ.

5.1. Реализация тематического Веб-краулера.

5.1.1. Тематический Веб-краулер на основе TF-IDF взвешивания.

5.1.2. Тематический Веб-краулер на основе алгоритма HITS.

5.1.3. Тематический Веб-краулер на основе совместного использования алгоритма HITS и взвешивания TF-IDF.

5.2. Сравнение с аналогами.

5.3. Среда разработки.

5.4. Выводы.

ГЛАВА

ЭКСПЕРИМЕНТ.

6.1. Описание эксперимента.

6.2. Результаты эксперимента.

6.3. Выводы.

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

В течение последнего десятилетия наблюдается экспоненциальный рост числа Веб-документов в информационном Веб-пространстве. Только в открытой (индексированной) части Веб-пространства на сегодняшний день насчитывается более 20 миллиардов документов и более 200 миллионов Вебсайтов, не говоря уже о скрытой (неиндексированной) части, в которой эти показатели больше в несколько раз [60]. Для эффективной работы с таким объемом информации требуются современные инструменты и технологии, роль которых играют различные средства информационного поиска.

1. Технические задачи информационного поиска

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

- сбор информации. Проблему обхода коллекции с целью нахождения документов, соответствующих заданной тематике, можно рассматривать как отдельную задачу. Для решения данной задачи применяются различные техники обхода, которые можно разбить на две группы. Первая — различные стратегии обхода, повышающие количество найденных тематически связанных документов среди общего объема найденных. Вторая - простая фильтрация, которая позволяет быстро отсеивать документы, не соответствующие тематике, уменьшая вычислительную стоимость нахождения очередного интересующего документа [20, 24, 33, 36]. Для решения задач сбора информации используются так называемые поисковые роботы (краулеры) [17, 18, 22, 45], которые получают из коллекции документы и извлекают из них гиперссылки, по которым осуществляется дальнейший сбор информации.

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

- ранжирование информации. Различные документы могут иметь различную ценность для конкретного пользователя, независимо от его конкретной информационной потребности [36]. Критериями такой ценности может быть размер и тематическая целостность документа, авторитетность его автора, время его создания. В процессе ранжирования должен оцениваться вес документа в коллекции. Оценка веса документа может зависеть от поискового запроса, либо от него не зависеть. В последнем случае она вычисляется на этапе индексации. При этом учитывается смысловое содержание текста или гиперссылочная структура документа.

- выбор модели документа. Для организации процедуры информационного поиска требуется формировать и сохранять упрощенные модели документов (модели с определенными наборами характеристик, по которым оцениваются документы) 5 коллекции. Моделью документа обычно называют набор характеристик документа, которые учитываются системой поиска при его обработке. Причем, для каждой из возможных задач подбирается индивидуальный набор характеристик, по которому оценивается документ или группы документов. - оценка качества поиска. На данный момент существует несколько моделей оценки качества информационного поиска. Используются как автоматические средства оценки качества, так и оценка путем опроса пользователей системы. Существуют общепринятые тестовые наборы, критерии и открытые результаты оценки качества различных информационных систем на этих наборах [36, 51, 56, 62, 64]. Проводятся различные конференции по проблемам оценки качества информационного поиска, как на международном (ТИЕС) [63], так и на российском (РОМИП) [57] уровне

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Блеканов, Иван Станиславович

6.3. Выводы

Целью данного эксперимента было оценить качество поиска тематического Веб-краулера на основе совместного использования алгоритмов ШТБ и ТР-ГОР, сравнив его с Веб-краулерами, построенных с использованием алгоритмов ШТБ и ТР-ГОР по отдельности.

Из поставленного эксперимента можно сделать следующие выводы:

- разработанный тематический поисковый робот с новым алгоритмом обхода Веб-пространства показал значительно лучшее качество поиска тематических сообществ, чем два других поисковых робота. А также для него наблюдается высокая стабильность полученных результатов, которая характеризуется высокими значениями различных оценок качества, так, например, значение оценки по всем запросам МАР(Р^ш+1р1С)1. =0.65, что, практически, в 2 раза больше значения МАР(0)Н1Т5 = 0.34.

- тематические Веб-краулеры на основе алгоритма Клейнберга и на основе взвешивания ТР-ГОР эффективней ищут информацию в тестовых английских коллекциях, в то время, как разработанный поисковый робот (который совместно использует оба алгоритма) обладает, примерно, одинаковым качеством поиска информации и в русских, и в английских коллекциях.

- множество объединений релевантных документов, найденных тематическими Веб-краулерами на основе алгоритма HITS и на основе взвешивания TF-IDF, является подмножеством множества релевантных документов, найденных разработанным поисковым роботом с новым алгоритмом поиска. Данный факт говорит о хорошей полноте созданной системы поиска тематических сообществ в Веб-пространстве.

- все документы, найденные по запросам тематическим Веб-краулером на основе совместного использования алгоритмов HITS и TF-IDF, релевантны теме соответствующих запросов в зависимости от личных потребностей пользователей, использующих данную систему поиска.

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

Список литературы диссертационного исследования кандидат технических наук Блеканов, Иван Станиславович, 2011 год

1. Берж, К. Теория графов и ее применения / К. Берж. М: Иностранная литература, 1962. —319 с.

2. Блеканов, И. С. Оценка эффективности методов поиска тематических сообществ в Веб-пространстве / И. С. Блеканов, Д. С. Бондаренко // Научно-технические ведомости СПбГПУ. 2010. -№5(102). -С. 109-119.

3. Блеканов, И. С. Тематический краулинг на основе алгоритма HITS / И. С. Блеканов, Д. С. Бондаренко // Научно-технические ведомости СПбГПУ.-2010.-№3(101).-С. 111-118.

4. Губин, М. В. Исследование качества информационного поиска с использованием пар слов / М. В. Губин // In Труды RCDL-2003. -2003.-С. 186-191.

5. Захарова, И. Математическая модель онтологии для задач анализа текстов / И.В.Захарова // Актуальные проблемы в науке и технике: тр. 4-й всероссийской школы сем. Уфа. - 2009. - Т. 1. - С. 210215.

6. Кобрицов, Б.П. Мофология и синтаксис в проекте «русский стандарт» (Создание корпуса грамматически размеченных русских текстов) / Б.П. Кобрицов // Статьи международной конференции Диалог.-2003.-6 с.

7. Некрестьянов, И.С. Тематико-ориентированные методы информационного поиска / Игорь Сергеевич Некрестьянов // канд. т. н.: 05.13.11 / Санкт-Петербургский государственный университет. СПб, 2000. - С. 88.

8. Рощин, И. Автоматическое определение кодировки текста / И. Рощин // Радиомир. Ваш компьютер. — 2002. — М. — С. 5-6.

9. Agrawal, R. Searching with numbers / R. Agrawal, R. Srikant // In Proceedings of the eleventh international conference on World Wide Web. ACM Press: NA, USA. - 2002. - P. 420-431.

10. Arampatzis, A. Linguistically motivated information retrieval. Marcel Dekker / A. Arampatzis, T. van der Weide, C. Koster, P. van Bommel. New York, USA: Encyclopedia of Library and Information Science, December 2000. - P. 69.

11. Arasu, A. Searching the web / A.Arasu, J. Cho, H. Garcia-Molina, A. Paepcke, S. Raghavan // ACM Transactions on Internet Technology. -Aug. 2001.- Volume 1, № 1. P. 2-43.

12. Bahle, D. Efficient phrase querying with an auxiliary index / D. Bahle, H. E. Williams, J. Zobel // Proceedings of the 25th annual international1.t

13. ACM SIGIR conference on Research and development in information retrieval. 2002. - ACM Press: NY, USA. - P. 215-221.

14. Barabasi, A. Emergence of scaling in random networks / A. Barabasi, R. Albert // Science, USA. 1999. - Volume 286, № 5439. - P. 509512.

15. Bharat, K. Mirror, mirror on the web: A study of host pairs with replicated content / K. Bharat, A. Broder // In Proceedings of the eighth international conference on World Wide Web. Elsevier North-Holland: NY, USA. - 1999. - P. 1579-1590.

16. Brewington, B. Keeping up with the changing Web / B. Brewington, G. Cybenko // IEEE Computer Society Press. Los Alamitos, CA, USA. -2000. - Volume 33, № 5. P. 52-58.

17. Brin, S. The anatomy of a large-scale hyper textual Web search engine / S. Brin, L. Page // Computer Networks and ISDN Systems. 1998. -Volume 30, № 1-7.-P. 107-117.

18. Broder, A. Graph structure in the Web: Experiments and models / A. Broder, R. Kumar, F. Maghoul, P. Raghavan, S. Rajagopalan, R. Stata, A. Tomkins, J. Wiener // In WWW9. May 2000. - Amsterdam. -Elsevier Science. - Volume 33, №1-6. - P. 309-320.

19. Cho, J. Estimating frequency of change / J. Cho, H. Garcia-Molina // ACM Transactions on Internet Technology. NY, USA. - 2003. -Volume 3, № 3. - P. 256-290.

20. Cho, J. The evolution of the web and implications for an incremental crawler / J. Cho, H. Garcia-Molina // In Proceedings of the 26th International Conference on Very Large Databases. CA, USA. -2000. - P. 200-209.

21. Coffman, E.G. Optimal robot scheduling for web search engines / E.G. Coffman, Z. Liu, R.R. Weber // INRIA: Technical report. № 3317. -1997.-P. 14-22.

22. Davison, B. Recognizing Nepotistic Links on the Web / B. Davison // AAAI Workshop on Artificial Intelligence for Web Search. Technical Report WS-00-01, AAAI Press. - 2000. - P. 23-28.

23. Flake, G. Self-Organization of the Web and Identification of Communities / G. Flake, S. Lawrence, C. Giles, F. Coetzee // IEEE Computer. 2002. - Volume 35, № 3. - P. 66-71.

24. Gibson, D. Inferring Web communities from link topology / D. Gibson, J. Kleinberg, P. Raghavan // Proc. 9th ACM Conference on Hypertext and Hypermedia. ACM Press. - New York. - 1998. - NY, USA. - P. 225-234.

25. Golub, G. Matrix Computations / G. Golub, C.F. Van Loan. Johns Hopkins University Press, 3rd edition. -1996. - P. 308.

26. Hull, D. A. Stemming algorithms: A case study for detailed evaluation / D. A. Hull // Journal of the American Society of Information Science. -1996. John Wiley & Sons, Inc. - Volume 47, № 1. - P. 70-84,

27. Kahle, B. Preserving the Internet / B. Kahle // Scientific American. -Mar. 1997.-P. 82-83.

28. Kleinberg, J. Authoritative sources in a hyperlinked environment / J. Kleinberg // Proc. 9th ACM-SIAM Symposium on Discrete Algorithms. 1998. - Extended version in Journal of the ACM 46(1999). - ACM Press. - New York. - Volume 46, № 5. - P. 604632.

29. Koster, M. Robots in the web: threat or treat? / Koster M. // Connexions. April 1995. - Volume 9, № 4. - P. 2-12.118

30. Lawrence, S. Accessibility of information on the web / S. Lawrence, C. Lee Giles // Intelligence. ACM: NY, USA. - 2000. - P. 32-39.

31. Lovins, J.B. Development of a stemming algorithm / J.B. Lovins // Mechanical Translation and Computation. 1968. - Massachusetts Institute of Technology. - Volume 11, № 1. - P. 22-31.

32. Manning, C. An Introduction to Information Retrieval / C. Manning, P. Raghavan, H. Schütze. Cambridge, England: Cambridge University Press. - April 2009. - P. 544 (84-133, 151-217, 443-481).

33. Mohr, G. Introduction to Heritrix: an open source archival quality web crawler / Mohr, G., Kimpton, M., Stack, M., Ranitovic, I. // Proceedings of the 4th International Web Archiving Workshop (IWAW'04). Bath, UK. - 2005. - P. 15.

34. Momoi, K. A composite approach to language/encoding detection / K. Momoi, S. Li // In 19th International Unicode Conference. 2002. - P. 12.

35. Najork, M. High-Performance Web Crawling / M. Najork, A. Heydon // Kluwer Academic Publishers. MA, USA. - 2002. pp. 25-45.

36. Page, L. The Pagerank Citation Ranking: Bringing Order to the Web / L. Page, S. Brin, R. Motwani, T. Winograd. Technical report. -Computer Science Department: Stanford University. - 1998. - P. 17.

37. Porter, M.F. An algorithm for suffix stripping / M.F. Porter // Program. 1980. - Volume 14, № 3. - P. 130-137.

38. Raghavan, S. Crawling the Hidden Web / S. Raghavan, H. GarciaMolina // Morgan Kaufmann Publishers Inc. San Francisco, CA, USA.-2001.-P. 129-138.

39. Rezgui, Y. Text-based domain ontology building using tf-idf and metric clusters techniques / Y. Rezgui // Cambridge University Press New York, NY, USA. Vol. 22 Issue 4. - 2007. - P. 379-403.

40. Salton, G. Automatic text processing: the transformation, analysis, and retrieval of information by computer / G. Salton. Boston, MA, USA: Addison-Wesley Longman Publishing Co. - 1989. - P. 530.

41. Sang Ho Lee. On URL normalization / Sang Ho Lee, Sung Jin Kim, Seok Hoo Hong // Proceedings of the International Conference on Computational Science and its Applications (ICCSA). 2005. -Volume 2.-P. 1076-1085.

42. Sidorov, G. Zipf and heaps laws' coefficients depend on language / G. Sidorov, A. Gelbukh. Mexico: In Proceeding of Conference on Intelligent Text Processing and Computational Linguistics, 2001. - P. 332-335.

43. Singhal, A. A case study in web search using tree algorithms / A. Singhal, M. Kaszkiel // Proceedings of the 10th international conference on World Wide Web. 2002. - ACM Press: Hong Kong. -P. 708-716.

44. Song, F. A general language model for information retrieval (poster abstract) / F. Song, W. B. Croft // In Research and Development in Information Retrieval. 1999. - ACM Press: USA. - P. 279-280.

45. Terveen L. Constructing, Organizing, and Visualizing Collections of Topically Related Web Resources / L. Terveen, W. Hill, B. Amento // ACM Transactions on Computer-Human Interaction. March 1999. -Volume 6, № 1. - P. 67-94.

46. Voorhes, E. The TREC-8 Question Answering Track Report / E. Voorhes // In Proc. of the TREC-8. 1999. - National Institute of Standards and Technology, Gaithersburg. - P. 77-82.

47. Williams, H. E. What's next? Index structures for efficient phrase querying / H. E. Williams, J. Zobel, P. Anderson // In M. Orlowska, editor, Proc. Australasian Database Conference. 1999. - Auckland, New Zealand. - P. 141-152.

48. Zakharova, I. An approach to automated ontology building in text analysis problems / I. V. Zakharova, A. V. Melnikov, J. A. Vokhmitsev // Workshop on Computer Science and Information Technologies. -2006.-P. 177-178.

49. Zobel, J. How reliable are the results of large-scale information retrieval experiments? / J. Zobel // Annual ACM Conference on

50. Research and Development in Information Retrieval. 1998. - NY, USA.-P. 307-314.

51. Российский семинар по Оценке Методов Информационного Поиска Электронный ресурс]. 2003. - Режим доступа: http://romip.ru/, свободный. - Загл. с экрана.

52. Heritrix Электронный ресурс]. 2004. - Режим доступа: http://crawler.archive.org/, свободный. - Загл. с экрана.

53. Methanol Web Crawling System Электронный ресурс]. Режим доступа: http://metha-sys.org/, свободный. — Загл. с экрана.

54. Most Reliable Hosting Company Sites Электронный ресурс]. -Режим доступа: http://news.netcraft.com/, свободный. Загл. с экрана.

55. OpenWebSpider Электронный ресурс]. Режим доступа: http://www.openwebspider.org, свободный. - Загл. с экрана.

56. Program to evaluate TREC results using SMART evaluation procedures Электронный ресурс]. Documentation. - Режим доступа: http://www-nlpir.nist.gov/projects/trecvid/trecvid.tools/treceval, свободный. -Загл. с экрана.

57. Text Retrieval Conference (TREC) Электронный ресурс]. 2000. -Режим доступа: http://trec.nist.gov/, свободный. - Загл. с экрана.