Мы (да и не только мы) уже рассказывали на хабре пару раз о проекте интеллектуального извлечения данных Convextra. Но предыдущие статьи это, по сути, обзоры сервиса, и его функциональности, а сегодня я хотел бы затронуть теоретическую и технологическую сторону вопроса извлечения данных. В русскоязычном сегменте очень немного информации, посвященной данной теме, и почти полностью отсутствует статьи о механизмах полуавтоматического или автоматического (интеллектуального) извлечения данных. Так как data extraction имеет непосредственное отношение к таким актуальным темам как data mining и Big Data, то, думаю, восполнение «информационного пробела» будет интересно довольно широкой аудитории. Намеренно постараюсь излагать на простом языке, поближе к этой самой «широкой аудитории». А извращенцев любителей матана ждут ссылки на источники внизу статьи, пройдя по которым, можно удовлетворить себя формулами, дифурами, матмоделями и строгим математическим описанием некоторых вопросов.
В сегодняшней статье речь пойдет о проблеме интеллектуального извлечения данных с веб-страниц (web data extraction), и, если тема окажется интересной, я продолжу цикл постов.
Data extraction
Извлечение данных (или, как еще называют, извлечение информации) — это процесс получения структурированных данных из слабоструктурированных или неструктурированных источников. В приложении к вебу, классическими задачами извлечения данных являются сбор информации о товарах интернет магазинов, результатов выдачи поисковых систем или получение списка всех статей какого-либо сайта. Важно понимать разницу между понятиями data extraction и data mining, чтобы не путать их. Задачей data extraction является сбор и систематизация данных, в то время как data mining занимается извлечением знаний из данных. Чаще всего, результат извлечения данных является входом для какого-либо дальнейшего анализа, включая data mining. Поэтому задача извлечения данных иногда сводится к переводу человекопонятных данных в машиночитаемые (например, парсеры переводят человекопонятные веб-страницы в машиночитаемые таблицы).
Условно, способы извлечения данных можно разделить на три группы:
- Ручной. Например, в некоторых агентствах недвижимости аналитики регулярно просматривают появившиеся на рынке предложения и вручную заносят их в свою базу.
- Полуавтоматический. К этому типу относятся решения, которые, после некоторой настройки пользователем, способны автоматизировать процесс извлечения данных. В вышеуказанном примере с агентствами недвижимости, роль полуавтоматического приложения извлечения данных может выполнять программа, в которой указано, с каких сайтов и по каким правилам нужно собирать объявления. Также к этой части относятся любые специализированные парсеры. Очевидным недостатком таких систем является зависимость от верстки целевых страниц и сложность подключения новых источников данных (чтобы подключить новый сайт нужно составить сложные правила регулярных выражений, XPATH или указать данные явно, используя визуальный интерфейс). Наиболее распространенными универсальными коммерческими приложениями для полуавтоматического извлечения данных являются Mozenda и Visual Web Ripper
- Автоматический (интеллектуальный). Качественным отличием систем данного типа является возможность автоматического распознавания данных и их структуры. В примере с недвижимостью это означает, что система способна автоматически распознавать объявления на любом сайте без предварительной настройки пользователем. Вряд ли существуют и в ближайшее время будут существовать универсальные технологии интеллектуального извлечения данных любого рода, но наиболее близкими к данному типу являются технологии поисковых гигантов и больших аналитических агентств.
Очевидно, что в сфере все нарастающего интереса к Big Data и data mining, наибольшую ценность представляют системы именно автоматического извлечения данных.
Структура приложений для интеллектуального извлечения данных
Извлечение структурированных связных данных с веб-страниц сводится к последовательному решению пяти задач:
- поиску и получению целевых страниц для извлечения данных (проблема навигации),
- распознаванию участков, содержащих нужные данные (проблема распознавания данных),
- поиску структуры найденных данных (проблема поиска общей структуры данных),
- обеспечению однородности извлекаемых данных (проблема сопоставления атрибутов извлекаемых данных)
- и объединению данных с разных источников (проблема объединения данных).
Несмотря на то, что в данной статье мы рассматриваем именно web data extraction, эти пять шагов применимы к извлечению данных вообще. Например, при решении задачи извлечения данных с бумажных документов приходится поочередно проходить эти же пять пунктов.
Далее мы поговорим о каждом из пунктов подробнее. Для большей наглядности рассмотрим их применительно к конкретной задаче, например, парсингу avito.ru.
Проблема навигации (Navigation problem)
Чтобы извлечь данные с веб-страниц, нужно, для начала, эти страницы получить. Но современный веб устроен так, что получение страниц с интересующей вас информацией превращается в совершенно нетривиальную задачу. К сожалению, протоколами не предусмотрено кнопки «скачать все интернеты» или, хотя бы, «скачать весь сайт». Кнопки «скачать авито» мы тоже не найдем, поэтому проблему придется решать каким-либо другим способом. Вариантов решения множество: написание своего велосипеда, использование возможностей краулера wget (да, он умеет ходить по ссылкам), сторонние библиотеки, использование результатов поисковых систем вроде гугла и т.д. На практике, несмотря на кажущуюся простоту, вы столкнетесь с огромным количеством подводных камней, таких как исполнение Javascript и AJAX навигация, ограничения по IP, авторизация страниц, капча, данные во флеш, отправка форм, определение логических дубликатов страниц… Короче говоря, полностью решить задачу очень затруднительно, поэтому, чаще всего, просто достигается результат, приемлемый для конкретного случая. Для avito подойдет самый простой сетевой паук, хотя бы тот же wget.
Проблема распознавания данных (Data extraction problem)
Хорошо, допустим мы получили все необходимые страницы. Но ведь нам нужны только данные (в случае с авито — объявления), а не все страницы целиком. Здесь мы плавно подходим к одной из главных проблем интеллектуального извлечения данных — распознаванию. Зайдя на любую из страниц авито, мы увидим примерно следующую картину:
Человеку сразу понятно, что здесь является релевантными данными для извлечения, но нужно научить этому машину (помните, выше мы говорили о переводе из человекопонятного в машиночитаемый?).Так вот, в случае с web data extraction, задача распознавания чаще всего (но не всегда) сводится к задаче поиска повторяющихся структур данных. Если мы научим алгоритм находить часто повторяющиеся структуры данных, то, с большой вероятностью, это и будет то, что человек считает «релевантными данными». Для авито это список объявлений, для яндекс маркета — каталог товаров, для соцсети — карточка пользователя, для сайта кинотеатра — расписание фильмов. То есть, указав системе какой-либо сайт, мы получим его «полезное содержимое». На этом хорошие новости заканчиваются :) Реализация алгоритма определения повторяющихся структур данных — это тема отдельных научных работ (ссылки на некоторые из них приведены в конце поста) и все существующие (опубликованные) алгоритмы даже в довольно простых случаях много ошибаются.
Существует несколько концептуально разных подходов к реализации алгоритма определения повторяющихся структур данных:
- Основанный на текстовом содержимом страницы
- Основанный на семантичность html разметки (ищется, например, наибольшая таблица в теге <content>)
- Основанный на определении занимаемого места в DOM дереве (ищется элемент, содержащий наибольшее количество дочерних элементов
- Основанный на построении некоторого хеша для каждого из элементов DOM дерева и группировке элементов с похожими хешами
- Основанный на визуальной картинке веб-страницы (грубо говоря, берется скриншот страницы, визуально анализируется, а результаты анализа обратно преобразуются в место элемента в исходном html коде).
В чистом виде эти подходы применяются редко, чаще используется комбинированное решение. Сама по себе тема алгоритмов очень интересна, и, возможно, ей будет посвящена отдельная статья.
Проблема поиска общей структуры данных (Structure synthesis problem)
Следующим шагом для извлечения данных является определения их структуры. На практике очень редко встречаются ситуации, когда все элементы набора данных имеют одинаковые свойства (атрибуты данных). Например, на авито некоторые объявления могут содержать адрес или информацию о продавце, а другие — нет. Проблема усложняется, если в качестве поставщика данных используются разные источники и тогда одни и те же атрибуты могут иметь разное представление. Как вы уже догадались, задача нетривиальная и универсального решения не существует. Чаще всего используется комбинированное решение в виде лексического анализа данных и анализа структуры DOM.
Проблема сопоставления атрибутов извлекаемых данных (Data mapping problem)
На предыдущем шаге мы получили некую «сетку атрибутов» наших данных (в простейшем случае она одномерная и может быть выражена просто их списком) и теперь необходимо каждый элемент из набора данных разложить по этой сетке. На данном этапе происходит нормализация атрибутов и обеспечивается однородность извлекаемых данных. Например, на avito дата объявления представляется в разных форматах: «Сегодня 11:42», «5 часов назад» или «21 июня». Для обеспечения однородности все такие атрибуты приводятся к общему формату (дата переводится в какой-либо абсолютный формат времени, адреса и станции метро тоже могут нормализоваться).
Проблема объединения данных (Data integration problem)
Последним этапом является объединение данных с разных страниц (одного или нескольких сайтов). Для чего это необходимо? Во-первых, информация об одном и том же элементе может находиться на разных страницах (на авито — в списке объявлений краткая информация, а на отдельной странице уже подробная). Во-вторых, как мы говорили выше, одни и те же данные из разных источников могут иметь разную структуру и ее придется приводить к общему виду. На этом шаге также выявляются логические дубликаты данных и отсеиваются элементы, не удовлетворяющие каким-либо исходным критериям (осуществляется пост-обработка данных).
Как это использовать?
С теорией, в общих чертах, мы разобрались. Но как это все можно применять на практике? Несмотря на то, что пока технологии интеллектуального извлечения данных по большей части применяются в закрытых узкоспециализированных решениях, сфера их применения очень широка. Наиболее очевидная область — создание разного рода агрегаторов и поисковых систем. К примеру, можно создать аналог ЯндексМаркета, который не будет нуждаться в предоставлении от магазинов специального файла с каталогом товаров (технология интеллектуального распознавания данных автоматически сможет получить всю необходимую информацию о товарах). Более интересным применением, на мой взгляд, является создание поисковых систем. Например, введя в такую поисковую систему «Эйфелева башня» можно будет на выходе получить всю информацию об этом объекте: высота, время работы, количество смотровых площадок, годовую аудиторию, вес, географические координаты и так-далее — все, что где-либо когда-либо было описано. Такую информацию не умеют предоставлять современные поисковики (хотя, и гугл и яндекс делают шаги в этом направлении), а использование технологии интеллектуального извлечения данных позволяет сделать такой поисковик благодаря механизму распознаванию атрибутов данных. В качестве менее глобальных примеров применения технологии можно привести задачи разового парсинга данных (например, импорт товаров в свой интернет магазин с других сайтов) и разного рода конечные решения. Например, становится возможным реализовать сервис сравнения цен различных интернет магазинов, где все, что требуется от пользователя — ввести адреса сайтов.
Мы, в качестве эксперимента, написали свой интеллектуальный парсер, который позволяет получать данные с сайта всего в одно нажатие кнопки, просто указав его адрес (аналог той волшебной кнопки «скачать сайт», о которой мы говорили выше). Конечно, пока это всего лишь прототип, написанный «на коленке», но даже в таком виде он позволяет получать достаточно вменяемые результаты для многих источников. Вот некоторые примеры его работы:
Ozone.ru: результат
Avito.ru: результат
Ebay.com: результат
Поиграться с парсером можно здесь. Просто вводите URL и на выходе получаете данные сайта. Количество загружаемых страниц с сайта — не более ста.
На этом все. Если было интересно, то в следующий раз можно поговорить подробнее о реализации конкретных алгоритмов для интеллектуального распознавания данных.
Литература
1. Retrieving and integrating data from multiple information sources. International Journal of Intelligent and Cooperative Information Systems (Y. Arens, C.Y. Chee, C-N. Hsu, and C.A. Knoblock.)
2. Template-baaed information mining from html documents. In Proceedings of the Fourteenth National Conference on Artificial Intelligence. (J.Y.-J. Hsu and W.-T. Yih)
3. Information extracting for semistructured documents. In Proceedings of the Workshop on Management of Semi-Structunzd Data. (D. Smith and M. Lopez.)
4. An XML-enabled data extraction toolkit for web sources. (Ling Liu, Calton Pu, Wei Han)
5. Web data extraction based on structuralsimilarity. (Zhao Li, Wee Keong Ng, Aixin Sun)
Найти эти и некоторые другие статьи, посвященные web data extraction вы можете, например здесь.
Автор: Napolsky
