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

• Косинов, Дмитрий Иванович
• кандидат технических наук
• 2008

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

Введение

Глава 1. Проблема обнаружения схожих документов

1.1. Задача распознавания схожих документов

1.2. Определение понятия схожих документов

1.3. Источники схожих документов в Интернете

1.4. Основные метрики подобия документов.

1.5. Методы обнаружения схожих документов

1.6. Методы кластеризации

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

1.8. Постановка задачи.

Глава 2. Моделирование системы оценки схожести документов на уровне блоков.

2.1. Модель представления web-документа

2.2. Метод выделения блоков из web-документа

2.3. Метод оценки схожести блоков.

2.4. Подходы к формализации нечеткости знаний о схожести документов

2.5. Метод оценки схожести web-доку ментов

2.6. Выводы.

Глава 3. Алгоритмизация процедуры оценки схожести web-документов на уровне блоков

3.1. Алгоритмы разбиения web-страниц на блоки.

3.2. Алгоритмы создания единого отпечатка на основе локальных параметров документа

3.3. Выводы.

Глава 4. Программная реализация метода оценки схожести \veb-документов.

4.1. Структура программного обеспечения

4.2. Программная платформа.

4.3. Программная реализация.

4.4. Графический интерфейс

4.5. Последовательность работы с программой

4.6. Тестирование программы.

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

4.8. Выводы.

Введение диссертации (часть автореферата) на тему «Разработка математического обеспечения оценки схожести WEB-документов на основе структурно-семантического разбиения»

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

Одной из таких задач является задача определения схожести различных -^еЬ-документов между собой. Известно, что более 30% всего содержимого Интернета является дубликатами уже существующих страниц. Выявление дубликатов позволяет решить следующие задачи:

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

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

• распознавание массовых несанционированных рассылок электронной почты (спама), доля которых составляет более 90% всего потока электронной почты. Детектирование схожих документов, которыми являются подобные рассылки, позволяет эффективно находить и уничтожать огромные объемы нежелательной корреспонденции;

• автоматическая классификация. При условии качественной классификации документов возникает возможность более простой навигации по большим массивам документов (например, по результатам поиска), а также потенциал для оптимизации pá6oTbi с непредсказуемыми по содержимому информационными потоками;

• нахождение похожих по содержанию документов. Функция нахождения по запросу документов, подобных заданному, позволяет определять их версионность, а также обнаруживать цитирования и плагиат.

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

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

Для достижения цели работы необходимо решение следующих1 задач исследования:

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

2. Разработать математическую модель оценки сходства документов на уровне составляющих их блоков. Создать метод оценки схожести web-документов на основе их структурно-семантических блоков.

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

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

Методы исследования. Методы исследования основаны на использовании аппарата теории графов, нечетких множеств, теории вероятностей и математической статистики, объектно-ориентированного программирования.

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

• математическая модель для оценки схожести документов, отличающаяся наличием промежуточного звена в цепи «документ-блок-отпечаток» и позволяющая определять пересечения текста документов на уровне их блоков;

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

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

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

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

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

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

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

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

Исследование поддержано исследовательским грантом компании Яндекс в рамках конкурса «Интернет-Математика 2007»1.

Апробация работы. Основные результаты диссертационного исследования докладывались на VIII международной конференции «Информатика: проблемы, методология, технологии» (Воронеж, 2008), VII международной научно-технической конференции «Кибернетика и высокие технологии XXI века» (Воронеж, 2006), IV международной научно-практической конференции «Прогрессивные технологии развития» (Тамбов, 2007), научно-технических конференциях профессорско-преподавательского состава, сотрудников, аспирантов и студентов ГОУ ВПО «Воронежский государственный университет» (2006-2008).

Публикации. По материалам диссертации опубликовано 11 научных работ, в том числе 1 в изданиях, рекомендованных ВАК РФ.

В работах, опубликованных в соавторстве, лично соискателю принадлежат: классификация web-страниц на основе нечетких параметров [19], процедура выбора набора признаков, определяющих документ [20], экспериментальная оценка возможности применения данных о классе структурированности документа в задаче поиска подобных [21], адаптация классификацион

1http://company.yandex.ry/grant ного генетического алгоритма к задаче выделения признаков [22], алгоритм выделения логических блоков из web-страницы [23].

Структура и объем диссертации. Диссертационная работа изложена на 146 страницах, включает 3 таблицы и 29 рисунков. Состоит из введения, четырех глав и заключения, списка литературы из 85 наименований и 7 приложений.

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

4.8. Выводы

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

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

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

Заключение

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

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

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

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

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

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

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

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

1. Агеев М., Куралепок И., Некрестьянов И. Официальные метрики ромип 2006. — 2006.http://romip.narod.ru/romip2006/appendixametrics. pdf.

2. Агеев M., Вершинников И., Доброе Б. Извлечение значимой информации из web-страниц для задач информационного поиска // Материалы конференции Интернет-Математика 2005. — 2005.

3. Бодякин В. И., Чистяков А. А. Ассоциативные информационные структуры и модели памяти. — 2004.

4. Боровков А. А. Математическая статистика. — М.: Наука, 1984. — С. 472.

5. Вятченин Д. А. Нечеткие методы автоматической классификации.— УП Технопринт, 2004.

6. Гаршин Д. Моделирование и выбор оптимальных технологических цепочек на базе территориально-распределенных производственных систем // дисс. к.т.н. — 2007.

7. Губин М. Модели и методы представления текстового документа в системах информационного поиска // дисс. к.ф.-м.н. — 2005.

8. Емельянов В. В., Курейчик В. В., Курейчик В. М. Теория и практика эволюционного моделирования. — М.: Физматлит, 2003.— С. 432.

9. Зеленков Ю., Сегалович И. Сравнительный анализ методов определения нечетких дубликатов для web-документов // Труды 9ой Всероссийской научной конференции Электронные библиотеки: перспективные методы и технологии, электронные коллекции. — 2007.

10. Кириченко К., Герасимов М. Обзор методов кластеризации текстовых документов // Материалы международной конференции Диалог2001. — 2001. http://www.dialog-21.ru/Archive/2001/volume2/226.htm.

11. Кнут Д. Искусство программирования, том 1. Основные алгоритмы.— Вильяме, 2006.

12. Косинов Д. Методы формирования информационных запросов к поисковой системе // Современные проблемы прикладной математики и математического моделирования: Материалы конференции. — Воронеж: ВГ-ТА, 2005. С. 123.

13. Косинов Д. Особенности поиска обсуждений в информационно-поисковых системах // Информатика: проблемы, методология, технологии : материалы 6-ой регион, науч.-метод. конф.— Воронеж: ВГУ, 2006. С. 203-206.

14. Косинов Д. Эффективные методы выявления документов-дубликатов // Кибернетика и высокие технологии 21 века : 7 Международ, науч.-техн. конф., 16-18 мая 2006 г. Т. 2. - Воронеж: 2006. - С. 686-690.

15. Косинов Д. Использование статистической информации при выявлении схожих документов // Интернет-математика 2007: сб. работ участников конкурса науч. проектов по информ. поиску.— Екатеринбург: 2007.— С. 84-90.

16. Косинов Д. Некоторые методы уточнения сходства документов в интернет-поиске // Информатика: проблемы, методология, технологии : материалы 7-ой регион, науч.-метод. конф., 8-9 февр. 2007 г. — Воронеж: ВГУ, 2007. С. 205-207.

17. Косинов Д. Локальные параметры текстов и проблема определения почти-дубликатов // Вестник Воронежского государственного университета. Серия: Системный анализ и информационные технологии. — Т. 1. — 2008. С. 83-85.

18. Косипов Д., Тюкачев Н. Выделение логических блоков из web-страниц // Вестник Воронежского государственного технического университета. 2008. - Т. 4, № 4. - С. 97-101.

19. Левенштейн В. Двоичные коды с исправлением выпадений, вставок и замещений символов // Доклады Академий Наук СССР 163.4:845-848. — 1965.

20. Леоненков А. В. Нечеткое моделирование в среде MATLAB и fuzzyTECH.- Спб.: БХВ-Петербург, 2005.

21. Мелихов А. Н., Верштейн Л. С., Коровин С. Я. Ситуационные советующие системы с нечеткой логикой. — М.: Наука Физматлит, 1990.

22. Митюшкин Ю. ИМокин Б, И., Ротштейн A. Soft Computing: идентификация закономерностей нечёткими базами знаний. — Винница: УШВЕРСУМ-Вшниця, 2002.

23. Некрестьянов И. Тематико-ориентированные методы информационного поиска // дисс. к.т.н,— 2000.

24. Некрестъянов И., Павлова Е. Обнаружение структурного подобия html-документов // Труды четвертой всероссийской конференция RCDL'2002, том 2, стр. 38-54, Дубна, Россия, 2002. — 2002.

25. Непомнящий П., Юрин Д. Построение иерархического дерева детальности изображения через поиск минимальных разрезов графа // Труды 13-ой Международной Конференции по Графике и Компьютерному Зрению. — 2003.

26. Нечеткие гибридные системы. Теория и практика / И. 3. Батырщин, А. О. Недосекин, А. А. Стецко и др. — М.: Физматлит, 2007. — С. 208.

27. Обзор автоматических детекторов плагиата в программах / Ю. Лифшиц, Д. Антипов, О. Ефтифеева и др. — 2006. http://detector.spb.su/pub/ Sandbox/ReviewAlgorithms/survey.pdf.

28. Сабанин В. Р., Смирнов Н. И., Репин А. И. Модифицированный генетический алгоритм для задач оптимизации в управлении // Exponenta Pro. Математика в прилоэюениях. — 2004. — № 3-4.

29. Солодухин А. Классификация текстов'на основе приближенных оценок вероятностей классов // Вестник ВГУ. Серия: Системный анализ и информационные технологии. — 2006.

30. Тарасова А. Модификация алгоритма кластеризации с-средних на основе использования объемных прототипов и слияния схожих кластеров // Вестник ВГУ. Серия: Системный анализ и информационные технологии. — 2006.

31. Устенко А. С. Основы математического моделирования и алгоритмизации. — М., 2000.

32. Цыганов Н., Циканин М. Исследование методов поиска дубликатов веб-документов с учетом запроса пользователя // Интернет-математика 2007: сб. работ участников конкурса науч. проектов по информ. поиску. Екатеринбург: 2007. - С. 211-222.

33. Штовба С. Д. Введение в теорию нечетких множеств и нечеткую логику. 2003.

34. Эффективный способ обнаружения дубликатов web документов с использованием инвертированного индекса / С. Ильинский, М. Кузьмин, А. Мелков, И. Сегалович. — 2004. http://webmastera.org/files/File/ secur/FindClonDoc.pdf.

35. Ярушкина Н. Г. Нечеткие нейронные сети в когнитивном моделировании и традиционных задачах искуственного интеллекта. — 2005.

36. Baeza-Yates R. A., Ribeiro-Neto В. A. Modern Information Retrieval.— ACM Press / Addison-Wesley, 1999. http://citeseer.ist.psu.edu/ baeza-yates99modern.html.

37. Bar-Yossef Z., Rajagopalan S. Template detection via data mining and its applications // WWW '02: Proceedings of the 11th international conference on World Wide Web. New York, NY, USA: ACM, 2002. - Pp. 580-591.

38. Bayardo R. J., Ma Y., Srikant R. Scaling up all pairs similarity search // WWW '07: Proceedings of the 16th international conference on World Wide Web. New York, NY, USA: ACM, 2007,- Pp. 131-140.

39. Brin S., Davis J., Garcia-Molina H. Copy detection mechanisms for digital documents // SIGMOD '95: Proceedings of the 1995 ACM SIGMOD international conference on Management of data. — New York, NY, USA: ACM Press, 1995. Pp. 398-409.

40. Chakrabarti S. Mining the Web: Discovering Knowledge from Hypertext Data. — Morgan-Kauffman, 2002. http://www.cse.iitb.ac.in/~soumen/ mining-the-web/.

41. Collection statistics for fast duplicate document detection / A. Chowdhury, O. Frieder, D. Grossman, M. C. McCabe // ACM Trans. Inf. Syst. — 2002. -Vol. 20, no. 2.-Pp. 171-191.

42. Crovella M. E., Taqqu M. S., Bestavros A. Heavy-tailed probability distributions in the world wide web. — 1998. — Pp. 3-25.

43. Dom-based content extraction of html documents // WWW '03: Proceedings of the 12th international conference on World Wide Web. — New York, NY, USA: ACM, 2003. Pp. 207-214.

44. Dugas R. Www unplugged: An html to wml transcoding proxy. — 2003.

45. Efficient retrieval of partial documents // TREC-2: Proceedings of the second conference on Text retrieval conference.— Elmsford, NY, USA: Pergamon Press, Inc., 1995. Pp. 361-377.

46. Fetterly D., Manasse M., Najork M. the evolution of clusters of near-duplicate web pages.— 2003. http://citeseer.ist.psu.edu/ fetterly03evolution.html.

47. Fuller M., Zobel J. Conflation-based comparison of stemming algorithms // Proc. of the Third Australian Document Computing Symposium, Sydney, Australia.— 1998. http://citeseer.ist.psu.edu/ fuller98conflationbased.html.

48. Graves S. Automatic extraction of generic web page components, http : // stp.ling.uu.se/exarb/arch/2004graves.pdf.

49. Gupta S. Context-based content extraction of html documents: Ph.D. thesis. New York, NY, USA: Columbia University, 2006. — Adviser-Gail E. Kaiser.

50. Haas S. W., Grams E. S. Readers, authors, and page structure: A discussion of four questions arising from a content analysis of web pages / / J A SIS. — 2000. Vol. 51, no. 2. - Pp. 181-192.

51. Harman D. What we have learned, and not learned, from tree // In: BCS IRSG '2000 Proceedings, 2000, pp 2-20 http://irsg.eu.org/irsg2000online/papers/harman.htm. — 2000.

52. Heintze N. Scalable document fingerprinting // 1996 USENIX Workshop on Electronic Commerce. — 1996. — November, http : //citeseer. ist. psu. edu/heintze96scalable.html.

53. Hoad T., Zobel J. Methods for identifying versioned and plagiarised documents // Journal of the American Society of Information Science and Technology. 2003. - Vol. 54, no. 3. - Pp. 203-215.

54. Hodge V. J., Austin J. An evaluation of phonetic spell checkers, http:// citeseer.ist.psu.edu/463597.html.

55. Holland J. H. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. — Cambridge, MA, USA: MIT Press, 1992.

56. Jain A. K., Murty M. N., Flynn P. J. Data clustering: a review // ACM Computing Surveys. 1999. - Vol. 31, no. 3. - Pp. 264-323.

57. Lin D. An information-theoretic definition of similarity // ICML '98: Proceedings of the Fifteenth International Conference on Machine Learning. — San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1998.— Pp. 296-304.

58. Manber U. Finding similar files in a large, file system // WTEC'94: Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference. — Berkeley, CA, USA: USENIX Association, 1994. Pp. 2-2.

59. Mifflin H. The psycho-biology of language. — 1935.

60. Mooers C. Application of Random Codes to the Gathering of Statistical Information: Ph.D. thesis. — .Cambridge: MIT, 1948.

61. Pivoted document length normalization: Tech. rep. / A. Singhal, C. Buckley, M. Mitra, G. Salton. Ithaca, NY, USA: 1995.

62. Ponte J. M., Croft W. B. Text segmentation by topic // European Conference on Digital Libraries. — 1997. — Pp. 113-125.

63. Porter M. F. An algorithm for suffix stripping. 1997. - Pp. 313-316.

64. Purpura S., Hillard D. Automated classification of congressional legislation // dg.o '06: Proceedings of the 2006 international conference on Digital government research. New York, NY, USA: ACM, 2006. — Pp. 219-225.

65. Salton G., Allan J., Singhal A. Automatic text decomposition and structuring // Information Processing and Management — 1996. — Vol. 32, no. 2.— Pp. 127-138. http://citeseer.ist.psu.edu/article/ salton94automatic.html.

66. Salton G., Wong A., Yang C. S. A vector space model for automatic indexing // Commun. A CM. 1975. - Vol. 18, no. 11. — Pp. 613-620.

67. Shaozhi Ye Ruihua Song. Ji-Rong Wen W.-Y. M. A query-dependent duplicate detection approach for large scale search engines // APWeb. — 2004. — Pp. 48-58.

68. Syntactic clustering of the web // Selected papers from the sixth international conference on World Wide Web. — Essex, UK: Elsevier Science Publishers Ltd., 1997.-Pp. 1157-1166.

69. S. Park D.M. Pennock R. K. Analysis of lexical signatures for finding lost or related documents // Proceedings of the 25th annual international ACM125

70. SIGIR conference on Research and development in information retrieval. — 2002.-Pp. 11-18.

71. Tree-Report W. Web document retrieval using passage retrieval, connectivity information, and automatic link, http://citeseer.ist.psu.edu/673713. html.

72. Van Rijsbergen C. J. Information Retrieval, 2nd edition. — Dept. of Computer Science, University of Glasgow, 1979. http://citeseer.ist.psu.edu/ vanrij sbergen79information.html.

73. W3C. Document object model (dom) level 2 html specification, http: //www. w3.org/TR/D0M-Level-2-HTML/.

74. W. Pugh M. H. Detecting duplicate and near-duplicate files / / United States Patent 6658423 (December 2, 2003). 2003.

75. Ye S., Wen J.-R., Ma W.-Y. A systematic study of parameter correlations in large scale duplicate document detection // PAKDD. — 2006. — Pp. 275-284.

76. Zobel J., Bernstein Y. The case of the duplicate documents: Measurement, search, and science // Proceedings of the APWeb Asia Pacific Web Conference / Ed. by X. Zhao, J. Li, H. Shen et al. — China: 2006. Pp. 26-39. — LNCS 3841.