Извлечение информации из полуструктурированных веб-источников Евгения Яковлева ragvena@yandex-mail.ru Владимир Батыгин vbatygin@yandex-team.ru. - презентация

1 Извлечение информации из полуструктурированных веб-источников Евгения Яковлева Владимир Батыгин

2 План o Мотивация; o Направления Web Mining; o Отбор источников информации; o Извлечение структурированной информации o Основные этапы процесса, o Классификация методов, o Примеры существующих подходов и систем, o Заключение. 2

3 План Мотивация; o Направления Web Mining; o Отбор источников информации; o Извлечение структурированной информации o Основные этапы процесса, o Классификация методов, o Примеры существующих подходов и систем, o Заключение. 3

4 o Структурированная информация в веб- источниках, как правило, содержит полезную информацию. o Анализ контента страницы повышает качество работы сервисов. Мотивация 4

5 Мотивация: пример

6 Мотивация: способ решения Извлечение структурированных данных из веб-источников является задачей Web Content Mining(WCM). Web Content Mining – направление Web Mining, занимающееся извлечением полезной информации из веб-страниц. 6

7 Знаешь, что такое Web Mining? 7

8 План Мотивация; Направления Web Mining; o Отбор источников информации; o Извлечение структурированной информации o Основные этапы процесса, o Классификация методов, o Примеры существующих подходов и систем, o Заключение. 8

9 Направления Web Mining 1996Web Mining 9 «The World-Wide Web: quagmire or gold mine?» Professor Oren Etzioni Director of the Turing Center

10 Направления Web Mining Web Mining Web Content Mining Web Usage Mining 10

11 Направления Web Mining Web Mining Web Content Mining Web Structure Mining Web Usage Mining 11

12 Направления Web Mining: Характеристика Web Usage Mining Логи веб- серверов; Предпочтений посетителей. Web Structure Mining Ссылки Взаимосвязь между страницами Web Content Mining HTML- страницы; Информация и знания. 12

13 Задачи Web Content Mining Извлечение структурированной информации; Извлечение фактов и связей. – Построение баз знаний, – PROSPERA. – Послать к Герхарду. 13 Извлечение структурированной информации Извлечение фактов и отношений

14 «Георгий Иванович, он же Жора, он же Гоша, он же Гога…» 14 Web Harvesting Web Scraping Web Data Extraction Information Extraction Web Content Mining Wrapper Induction

15 Задачи Web Content Mining 15 Извлечение структуриро- ванных данных Извлечение фактов и отношений

16 Задачи Web Content Mining 16 Извлечение фактов и отношений Свободный текст Gerhard Weikum Max Planck Institute for Informatics «Scalable knowledge harvesting with high precision and high recall» [2011] PROSPERA Oren Etzioni University of Washington KnowItAll [2004]

17 План Мотивация; Направления Web Mining; Отбор источников информации; o Извлечение структурированной информации o Основные этапы процесса, o Классификация методов, o Примеры существующих подходов и систем, o Заключение. 17

18 Конференции Computer Science Conference Ranking НаправлениеКонференции Data MiningSIGMOD: ACM SIGMOD Conf on Management of Data SIGKDD: ACM Knowledge Discovery and Data Mining ICDM: IEEE International Conference on Data Mining PAKDD: Pacific-Asia Conf on Know. Discovery & Data Mining DatabaseVLDB: Very Large Data Bases ICDE: IEEE Intl Conf on Data Engineering Information RetrievalSIGIR: ACM SIGIR Conf on Information Retrieval Web and Information Systems WWW: World-Wide Web Conference 18

19 Критерии отбора статей o Престижность конференции; o Год публикации; o Индекс цитируемости; o «Серийные» авторы. 19

20 «Серийные» авторы Bing, Liu Professor University of Illinois at Chicago (UIC) WONG, Tak-Lam PhD,Lecturer The Hong Kong Institute of Education Chang, Chia-Hui Professor National Central University 20

21 Исследовательские центры на карте мира 21 Microsoft Research Yahoo!Labs University of Illinois at Chicago Università di Roma Tre Università della Basilicata Microsoft Research Asia

22 План Мотивация; Направления Web Mining; Отбор источников информации; Извлечение структурированной информации o Основные этапы процесса, o Классификация методов, o Примеры существующих подходов и систем, o Заключение. 22

23 Данные в Веб Виды данных: текст, графика, аудио, видео. 23

24 Данные в Веб Виды данных: текст, графика, аудио, видео. Текстовая информация: Неструктурированная – свободный текст; Полуструктурированная – HTML-страницы; Структурированная – документы, генерирующиеся из БД. 24

25 Данные в Веб Виды данных: текст, графика, аудио, видео. Текстовая информация: Неструктурированная – свободный текст; Полуструктурированная – HTML-страницы; Структурированная – документы, генерирующиеся из БД. 25

26 План Мотивация; Направления Web Mining; Отбор источников информации; Извлечение структурированной информации Основные этапы процесса, o Классификация методов, o Примеры существующих подходов и систем, o Заключение. 26

27 Основные этапы процесса CrawlingПостроение wrapper-овИзвлечение данныхАнализ данных 27

28 Основные этапы процесса CrawlingПостроение wrapper-овИзвлечение данныхАнализ данных 28

29 «Георгий Иванович, он же Жора, он же Гоша, он же Гога…»- 2 «То, что извлекает данные со страницы» 29 Wrapper Правила извлечения Parser Pattern Спец. робот Экстрактор Посредник между исходными и извлеченными данными

30 «Георгий Иванович, он же Жора, он же Гоша, он же Гога…»- 2 «То, что извлекает данные со страницы» 30 Wrapper Правила извлечения Parser Pattern Спец. робот Экстрактор Посредник между исходными и извлеченными данными Строится заново для каждой страницы и не использует знаний о структуре ранее обработанных страниц Строится на этапе обучения и использует знания о строе предыдущих страниц

31 План Мотивация; Направления Web Mining; Отбор источников информации; Извлечение структурированной информации Основные этапы процесса, Классификация методов, o Примеры существующих подходов и систем, o Заключение. 31

32 Wrapper Induction System Классификация методов [Chang2006] 32 Wrapper Extracted Data Test Page Un-labeled Training Web Pages

33 Manual | Supervised | Semi-supervised | Un-supervised Wrapper Induction System Классификация методов [Chang2006] 33 Wrapper Extracted Data Test Page Un-labeled Training Web Pages Manual

34 Manual | Supervised | Semi-supervised | Un-supervised Wrapper Induction System Классификация методов [Chang2006] 34 Wrapper Extracted Data Test Page Un-labeled Training Web Pages Supervised Labeled Web Pages

35 Manual | Supervised | Semi-supervised | Un-supervised Wrapper Induction System Классификация методов [Chang2006] 35 Wrapper Extracted Data Test Page Un-labeled Training Web Pages Semi-supervised

36 Manual | Supervised | Semi-supervised | Un-supervised Wrapper Induction System Классификация методов [Chang2006] 36 Wrapper Extracted Data Test Page Un-labeled Training Web Pages Unsupervised

37 План Мотивация; Направления Web Mining; Отбор источников информации; Извлечение структурированной информации Основные этапы процесса, Классификация методов, Примеры существующих подходов и систем, o Заключение. 37

38 Существующие подходы ManualSupervisedSemi-supervisedUnsupervised TSIMMIS [Hammer1997] Minerva [Crescenzi1998] WebQOL [Arocena1998] XWRAP [Liu2000] W4F [Saiiuguet2001] WIEN [Kushmerick1997] SRV [Freitag1998] RAPIER [Califf1998] NoDoSe [Adelberg1998] SoftMealy [Hsu1998] WHISK [Soderland1999] STALKER [Muslea1999] DEByE [Laender2002] SinglePage IEPAD [Chang2001] OLERA [Chang2004] Thresher [Hogue2005] IDE [Zhai2005] RoadRunner [Crescenzi2001] DeLa [Wang2002] EXALG [Arasu2003] DEPTA [Znai2005] NET [Zhai2005] IEKA [Wong2007] ViDE [Liu2010] 38

39 Примеры существующих подходов и систем o Группа «Manual»; o Группы «Supervised» и «Semi-supervised»; o Группа «Unsupervised»; 39

40 Примеры существующих подходов и систем Группа «Manual»; o Группы «Supervised» и «Semi-supervised»; o Группа «Unsupervised»; 40

41 Группа «Manual» Особенности: Wrapperы пишутся вручную; Для разбора используют – Xpath; – RegExp. 41

42 Flashback: Существующие подходы ManualSupervisedSemi-supervisedUnsupervised TSIMMIS [Hammer1997] Minerva [Crescenzi1998] WebQOL [Arocena1998] XWRAP [Liu2000] W4F [Saiiuguet2001] WIEN [Kushmerick1997] SRV [Freitag1998] RAPIER [Califf1998] NoDoSe [Adelberg1998] SoftMealy [Hsu1998] WHISK [Soderland1999] STALKER [Muslea1999] DEByE [Laender2002] SinglePage IEPAD [Chang2001] OLERA [Chang2004] Thresher [Hogue2005] IDE [Zhai2005] RoadRunner [Crescenzi2001] DeLa [Wang2002] EXALG [Arasu2003] DEPTA [Znai2005] NET [Zhai2005] IEKA [Wong2007] ViDE [Liu2010] 42

43 Группа «Manual»: Инструменты 43

44 WebHarvest: Easy Web Scraping from Java 44 Ах, вот ты какой, рукописный wrapper …

45 Manual. Инструменты

46 Таких инструментов много Digits Web Extractor Software Djuggler Happy Harvester Irobot Soft ListGrabber

47 Примеры существующих подходов и систем Группа «Manual»; Группы «Supervised» и «Semi-supervised»; o Группа «Unsupervised». 47

48 Группы «Supervised» и «Semi-supervised» Особенность: Правила извлечения генерируются автоматически или под контролем пользователя. 48

49 Flashback: Существующие подходы ManualSupervisedSemi-supervisedUnsupervised TSIMMIS [Hammer1997] Minerva [Crescenzi1998] WebQOL [Arocena1998] XWRAP [Liu2000] W4F [Saiiuguet2001] WIEN [Kushmerick1997] SRV [Freitag1998] RAPIER [Califf1998] NoDoSe [Adelberg1998] SoftMealy [Hsu1998] WHISK [Soderland1999] STALKER [Muslea1999] DEByE [Laender2002] SinglePage IEPAD [Chang2001] OLERA [Chang2004] Thresher [Hogue2005] IDE [Zhai2005] RoadRunner [Crescenzi2001] DeLa [Wang2002] EXALG [Arasu2003] DEPTA [Znai2005] NET [Zhai2005] IEKA [Wong2007] ViDE [Liu2010] 49

50 Группы «Supervised» и «Semi-supervised»: Инструменты 50

51 51

52 Группы «Supervised» и «Semi-supervised» Инструменты

53 Примеры существующих подходов и систем Группа «Manual»; Группы «Supervised» и «Semi-supervised»; Группа «Unsupervised» 53

54 Группа «Unsupervised» Особенности: Полностью автоматические. не требуют контроля со стороны пользователя. 54

55 Flashback: Существующие подходы ManualSupervisedSemi-supervisedUnsupervised TSIMMIS [Hammer1997] Minerva [Crescenzi1998] WebQOL [Arocena1998] XWRAP [Liu2000] W4F [Saiiuguet2001] WIEN [Kushmerick1997] SRV [Freitag1998] RAPIER [Califf1998] NoDoSe [Adelberg1998] SoftMealy [Hsu1998] WHISK [Soderland1999] STALKER [Muslea1999] DEByE [Laender2002] SinglePage IEPAD [Chang2001] OLERA [Chang2004] Thresher [Hogue2005] IDE [Zhai2005] RoadRunner [Crescenzi2001] DeLa [Wang2002] EXALG [Arasu2003] DEPTA [Znai2005] NET [Zhai2005] IEKA [Wong2007] ViDE [Liu2010] 55

56 Flashback: Исследовательские центры на карте мира 56 University of Illinois at Chicago Università di Roma Tre Università della Basilicata Microsoft Research Asia

57 Flashback: Исследовательские центры на карте мира 57 University of Illinois at Chicago Università di Roma Tre Università della Basilicata Microsoft Research Asia

58 Crescenzi et al. Организации: – Università di Roma Tre, – Università della Basilicata; Направление исследования: – Автоматическая экстракция. Работы: – RoadRunner[2001]; – Flint[2008]; – Automatically building probabilistic databases from the web [2011] 58

59 Crescenzi et al: RoadRunner Дано множество «хороших» страниц; Строится wrapper в форме RegExp. Подход Wrapper строится на основании сравнения двух страниц одинаковой структуры. 59

60 60

61 61

62 62

63 63

64 Crescenzi et al: RoadRunner. Пример ABCDEFGHI Albani a Football Association of Albania PAPADHOPULLI Dhimiter STAROVA Sulejman None * ZHEGA Medin 64

65 Flashback: Исследовательские центры на карте мира 65 University of Illinois at Chicago Università di Roma Tre Università della Basilicata Microsoft Research Asia

66 Flashback: Исследовательские центры на карте мира 66 University of Illinois at Chicago Università di Roma Tre Università della Basilicata Microsoft Research Asia

67 Liu et al. Организации: – University of Illinois at Chicago. Направление исследования: – Очистка страниц от «шума», – Автоматическая экстракция данных из каталожных страниц. Работы: – Web Page Cleaning for Web Mining through Feature Weighting [2003]; – MDR[2003] DEPTA[2005] NET[2005]; 67

68 Liu et al: Mining Data Records (MDR) 68 Data Region Data Reсord

69 Liu et al: MDR. Пример 69

70 Liu et al: MDR. Пример 70

71 Liu et al: MDR. Пример 71

72 Flashback: Исследовательские центры на карте мира 72 University of Illinois at Chicago Università di Roma Tre Università della Basilicata Microsoft Research Asia

73 Flashback: Исследовательские центры на карте мира 73 University of Illinois at Chicago Università di Roma Tre Università della Basilicata Microsoft Research Asia

74 Направление исследования: – Сегментация страницы; – Извлечение информации; – Вероятностные модели для извлечения информации. Работы: – VIPS: a Vision-based Page Segmentation Algorithm[2003]; – 2d conditional random fields for web information extraction[2005]; – Simultaneous record detection and attribute labeling in web data extraction [2006]; 74

75 Microsoft Research Asia: Vision-based Page Segmentation Algorithm (VIPS) 75

76 Microsoft Research Asia: Vision-based Page Segmentation Algorithm (VIPS) 76

77 План Мотивация; Направления Web Mining; Отбор источников информации; Извлечение структурированной информации Основные этапы процесса, Классификация методов, Примеры существующих подходов и систем, Заключение. 77

78 Заключение Сложности Manual -Свой на каждый сайт; Supervised, Semi-supervised – Дорого поддерживать; Unsupervised – Проблема с полнотой; 78

79 Заключение Автоматизация: От ручной обработки через полностью автоматическую к гибридной. Уровень решения задачи: от страницы к вертикали. Используемые параметры: От тегов к использованию визуальных особенностей оформления и контекста. 79

80 Спасибо за внимание! Вопросы? 80

81 Евгения Яковлева Владимир Батыгин 81