Выявление смысловых блоков в веб страницах (построение карты объектов)

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

Для начала к вопросу о том для чего это нужно и лишь потом что это такое. На самом деле задач для алгоритмов выявления смысловых блоков очень много, например:

  • выявление основного контента (primary page content) для более разумного индексирования веб сайтов без необходимости включения в индекс служебных блоков вроде рекламы, меню сайта и копирайтов
  • автоматизация процессов направленного индексирования выявлением только нужных блоков на веб страницах
  • возможность создания систем автоматической семантизации — превращения неструктурированного веб сайта в набор API
  • борьба со поисковым спамом
  • выявление вспомогательных классификационных признаков для тематической, географической и иной классификации.

Основная из давно решённых вышеперечисленных задач — это выявление основного контента уже давно используется во множестве поисковых систем. Это не очень сложная задача сама по себе, но её решение сильно влияет на качество поиска.

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

Лично экспериментирую с HTML — не столько в части программирования на нём, сколько в части анализа, уже давно. Из публично доступных моих наработок в этой области — это Скиур и анализатор платных ссылок в общем же прежде чем прийти к ним и паралелльно с ними я и занимаюсь тем что называется построением объектной карты — разделения веб страниц на совокупность смысловых блоков: меню, реклама, основное содержимое, списки, логотипы, блоки копирайтов и так далее.

Особенность в построении такой карты в том что прежде чем добиться разделения веб страницы на блоки и смысловые участки необходимо понять отношения между тэгами и группами тэгов внутри веб страницы и быть готовыми к тому что вариативность комбинаций тэгов и их атрибутов крайне высока, поэтому нужны признаки (features) по которым и необходимо производить кластеризацию и классификацию блоков.

Итак собственно сам подход.

1. HTML, вернее DOM дерево тэгов, рассматривается не как дерево, а как гибрид таблицы/матрицы и дерева. На практике, в идеальном случае, необходимо построение DOM парсера который бы при формировании дерева позволял бы назначать произвольное число атрибутов доступ к которым мог бы осуществляться по своему языку запросов — SQL в простейшем исполнении или SPARQL в более сложном. Сейчас лично я использую для этой целе два связанных объекта — дерево DOM и временная SQL таблица где в дереве находятся узлы и первичные данные, а в SQL таблице все извлечённые и рассчитанные признаки. Это несёт целый ряд неудобств связанных как с сопоставлением узлом записям в SQL, так и потерями производительности при необходимости кросс-обращения, но это работает.

2. Ключевое в работе с полученной структурой — это признаки. Некоторые из них предельно очевидные — вроде определённого типа атрибутов связанных с тэгом, например, такие ключевые атрибуты как id и class, но не только.

Признаки тэгов можно разделить на 3 типа:

  • естественные признаки (native features) — признаки по которым можно восстановить содержание веб страницы при желании и они извлекаются прямо из DOM дерева. Такой признак — это название тэга, значения классов id, class и ряда других;
  • признаки уточняющие (localization features) — эти рассчитываемые признаки на базе естественных которые помогают в задачах локализации смысловых блоков, например, это булевые признаки наличия тех или иных атрибутов, наличия текста внутри тэга и так далее.
  • признаки решения (decision level features) — признаки используемые непосредственно в процессах классификации блоков

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

3. При анализе DOM дерева из каждого узла извлекаются естественные признаки и рассчитываются признаки уточняющие. В совокупности таких признаков может набраться несколько десятков, например, в алгоритме выявления платных ссылок используется 17 таких признаков. Когда все уточняющие признаки собраны, то к ним начинают применяться алгоритмы классификации тэгов и выявления блоков по структурным признакам. В несколько проходов фильтры извлекают блоки кандидаты и группируют их в кластеры — группы на основе нескольких критериев схожести.

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

Далее можно использовать деревья решений, SVM, или, что я и делаю в экспериментах, мини Map/Reduce на основе которых можно создавать классификационные алгоритмы.

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

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

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

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

Другие алгоритмы — как то выявление меню навигации по сайту, выявление основного содержимого, выявление рекламных блоков и так далее гораздо проще. Они сводятся к направленному поиску блоков соответствующих определённым характеристикам.

В совокупности алгоритм формируется из 3-х компонентов:

1. Постановка искомой задачи для чего алгоритм создаётся

2. Правильный подбор классификационных признаков

3. Многочисленные эксперименты с полным расчётом всех признаков

4. Выявление ключевых признаков и упрощение алгоритма в части ненужных признаков насколько это возможно.

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

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

Да ещё добавлю что во всём вышеперечисленном может быть как мало так и много математики. Конечно, всё вышеперечисленное можно описать и более формально с упоминанием feature selection, feature weighting, svm и использованию дополнительных инструментов вроде Weka или Rapidminer, анализа с использованием Excel’я и других инструментов, но я лично предпочитаю искать те решения где можно обойтись без сложных формул и расчётов и обладающим простым описанием понятным не только тем кто любит математику и статистику.

About This Author

  • Гость

    Сколько слов для простой задачи 😉

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

    Работает как часу уже года три.

  • http://ivan.begtin.name ivbeg

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

Яндекс.Метрика