Извлечение информации из полуструктурированных веб-источников Евгения Яковлева Владимир Батыгин
План o Мотивация; o Направления Web Mining; o Отбор источников информации; o Извлечение структурированной информации o Основные этапы процесса, o Классификация методов, o Примеры существующих подходов и систем, o Заключение. 2
План Мотивация; o Направления Web Mining; o Отбор источников информации; o Извлечение структурированной информации o Основные этапы процесса, o Классификация методов, o Примеры существующих подходов и систем, o Заключение. 3
o Структурированная информация в веб- источниках, как правило, содержит полезную информацию. o Анализ контента страницы повышает качество работы сервисов. Мотивация 4
Мотивация: пример
Мотивация: способ решения Извлечение структурированных данных из веб-источников является задачей Web Content Mining(WCM). Web Content Mining – направление Web Mining, занимающееся извлечением полезной информации из веб-страниц. 6
Знаешь, что такое Web Mining? 7
План Мотивация; Направления Web Mining; o Отбор источников информации; o Извлечение структурированной информации o Основные этапы процесса, o Классификация методов, o Примеры существующих подходов и систем, o Заключение. 8
Направления Web Mining 1996Web Mining 9 «The World-Wide Web: quagmire or gold mine?» Professor Oren Etzioni Director of the Turing Center
Направления Web Mining Web Mining Web Content Mining Web Usage Mining 10
Направления Web Mining Web Mining Web Content Mining Web Structure Mining Web Usage Mining 11
Направления Web Mining: Характеристика Web Usage Mining Логи веб- серверов; Предпочтений посетителей. Web Structure Mining Ссылки Взаимосвязь между страницами Web Content Mining HTML- страницы; Информация и знания. 12
Задачи Web Content Mining Извлечение структурированной информации; Извлечение фактов и связей. – Построение баз знаний, – PROSPERA. – Послать к Герхарду. 13 Извлечение структурированной информации Извлечение фактов и отношений
«Георгий Иванович, он же Жора, он же Гоша, он же Гога…» 14 Web Harvesting Web Scraping Web Data Extraction Information Extraction Web Content Mining Wrapper Induction
Задачи Web Content Mining 15 Извлечение структуриро- ванных данных Извлечение фактов и отношений
Задачи 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]
План Мотивация; Направления Web Mining; Отбор источников информации; o Извлечение структурированной информации o Основные этапы процесса, o Классификация методов, o Примеры существующих подходов и систем, o Заключение. 17
Конференции 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
Критерии отбора статей o Престижность конференции; o Год публикации; o Индекс цитируемости; o «Серийные» авторы. 19
«Серийные» авторы 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 Microsoft Research Yahoo!Labs University of Illinois at Chicago Università di Roma Tre Università della Basilicata Microsoft Research Asia
План Мотивация; Направления Web Mining; Отбор источников информации; Извлечение структурированной информации o Основные этапы процесса, o Классификация методов, o Примеры существующих подходов и систем, o Заключение. 22
Данные в Веб Виды данных: текст, графика, аудио, видео. 23
Данные в Веб Виды данных: текст, графика, аудио, видео. Текстовая информация: Неструктурированная – свободный текст; Полуструктурированная – HTML-страницы; Структурированная – документы, генерирующиеся из БД. 24
Данные в Веб Виды данных: текст, графика, аудио, видео. Текстовая информация: Неструктурированная – свободный текст; Полуструктурированная – HTML-страницы; Структурированная – документы, генерирующиеся из БД. 25
План Мотивация; Направления Web Mining; Отбор источников информации; Извлечение структурированной информации Основные этапы процесса, o Классификация методов, o Примеры существующих подходов и систем, o Заключение. 26
Основные этапы процесса CrawlingПостроение wrapper-овИзвлечение данныхАнализ данных 27
Основные этапы процесса CrawlingПостроение wrapper-овИзвлечение данныхАнализ данных 28
«Георгий Иванович, он же Жора, он же Гоша, он же Гога…»- 2 «То, что извлекает данные со страницы» 29 Wrapper Правила извлечения Parser Pattern Спец. робот Экстрактор Посредник между исходными и извлеченными данными
«Георгий Иванович, он же Жора, он же Гоша, он же Гога…»- 2 «То, что извлекает данные со страницы» 30 Wrapper Правила извлечения Parser Pattern Спец. робот Экстрактор Посредник между исходными и извлеченными данными Строится заново для каждой страницы и не использует знаний о структуре ранее обработанных страниц Строится на этапе обучения и использует знания о строе предыдущих страниц
План Мотивация; Направления Web Mining; Отбор источников информации; Извлечение структурированной информации Основные этапы процесса, Классификация методов, o Примеры существующих подходов и систем, o Заключение. 31
Wrapper Induction System Классификация методов [Chang2006] 32 Wrapper Extracted Data Test Page Un-labeled Training Web Pages
Manual | Supervised | Semi-supervised | Un-supervised Wrapper Induction System Классификация методов [Chang2006] 33 Wrapper Extracted Data Test Page Un-labeled Training Web Pages Manual
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
Manual | Supervised | Semi-supervised | Un-supervised Wrapper Induction System Классификация методов [Chang2006] 35 Wrapper Extracted Data Test Page Un-labeled Training Web Pages Semi-supervised
Manual | Supervised | Semi-supervised | Un-supervised Wrapper Induction System Классификация методов [Chang2006] 36 Wrapper Extracted Data Test Page Un-labeled Training Web Pages Unsupervised
План Мотивация; Направления Web Mining; Отбор источников информации; Извлечение структурированной информации Основные этапы процесса, Классификация методов, Примеры существующих подходов и систем, o Заключение. 37
Существующие подходы 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
Примеры существующих подходов и систем o Группа «Manual»; o Группы «Supervised» и «Semi-supervised»; o Группа «Unsupervised»; 39
Примеры существующих подходов и систем Группа «Manual»; o Группы «Supervised» и «Semi-supervised»; o Группа «Unsupervised»; 40
Группа «Manual» Особенности: Wrapperы пишутся вручную; Для разбора используют – Xpath; – RegExp. 41
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
Группа «Manual»: Инструменты 43
WebHarvest: Easy Web Scraping from Java 44 Ах, вот ты какой, рукописный wrapper …
Manual. Инструменты
Таких инструментов много Digits Web Extractor Software Djuggler Happy Harvester Irobot Soft ListGrabber
Примеры существующих подходов и систем Группа «Manual»; Группы «Supervised» и «Semi-supervised»; o Группа «Unsupervised». 47
Группы «Supervised» и «Semi-supervised» Особенность: Правила извлечения генерируются автоматически или под контролем пользователя. 48
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
Группы «Supervised» и «Semi-supervised»: Инструменты 50
51
Группы «Supervised» и «Semi-supervised» Инструменты
Примеры существующих подходов и систем Группа «Manual»; Группы «Supervised» и «Semi-supervised»; Группа «Unsupervised» 53
Группа «Unsupervised» Особенности: Полностью автоматические. не требуют контроля со стороны пользователя. 54
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
Flashback: Исследовательские центры на карте мира 56 University of Illinois at Chicago Università di Roma Tre Università della Basilicata Microsoft Research Asia
Flashback: Исследовательские центры на карте мира 57 University of Illinois at Chicago Università di Roma Tre Università della Basilicata Microsoft Research Asia
Crescenzi et al. Организации: – Università di Roma Tre, – Università della Basilicata; Направление исследования: – Автоматическая экстракция. Работы: – RoadRunner[2001]; – Flint[2008]; – Automatically building probabilistic databases from the web [2011] 58
Crescenzi et al: RoadRunner Дано множество «хороших» страниц; Строится wrapper в форме RegExp. Подход Wrapper строится на основании сравнения двух страниц одинаковой структуры. 59
60
61
62
63
Crescenzi et al: RoadRunner. Пример ABCDEFGHI Albani a Football Association of Albania PAPADHOPULLI Dhimiter STAROVA Sulejman None * ZHEGA Medin 64
Flashback: Исследовательские центры на карте мира 65 University of Illinois at Chicago Università di Roma Tre Università della Basilicata Microsoft Research Asia
Flashback: Исследовательские центры на карте мира 66 University of Illinois at Chicago Università di Roma Tre Università della Basilicata Microsoft Research Asia
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
Liu et al: Mining Data Records (MDR) 68 Data Region Data Reсord
Liu et al: MDR. Пример 69
Liu et al: MDR. Пример 70
Liu et al: MDR. Пример 71
Flashback: Исследовательские центры на карте мира 72 University of Illinois at Chicago Università di Roma Tre Università della Basilicata Microsoft Research Asia
Flashback: Исследовательские центры на карте мира 73 University of Illinois at Chicago Università di Roma Tre Università della Basilicata Microsoft Research Asia
Направление исследования: – Сегментация страницы; – Извлечение информации; – Вероятностные модели для извлечения информации. Работы: – 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
Microsoft Research Asia: Vision-based Page Segmentation Algorithm (VIPS) 75
Microsoft Research Asia: Vision-based Page Segmentation Algorithm (VIPS) 76
План Мотивация; Направления Web Mining; Отбор источников информации; Извлечение структурированной информации Основные этапы процесса, Классификация методов, Примеры существующих подходов и систем, Заключение. 77
Заключение Сложности Manual -Свой на каждый сайт; Supervised, Semi-supervised – Дорого поддерживать; Unsupervised – Проблема с полнотой; 78
Заключение Автоматизация: От ручной обработки через полностью автоматическую к гибридной. Уровень решения задачи: от страницы к вертикали. Используемые параметры: От тегов к использованию визуальных особенностей оформления и контекста. 79
Спасибо за внимание! Вопросы? 80
Евгения Яковлева Владимир Батыгин 81