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

Будем очищать веб-страницы от «информационного шума».

Так в чем же проблема?

Проблема заключается в том, что добрая половина веб-сайтов содержит кучу ненужной информации на страницах — так называемый «информационный шум». К нему можно отнести навигацию, связанные ссылки, элементы дизайна, ну и, конечно, рекламу.

На сегодняшний момент все решения, связанные с фильтрацией контента, завязаны на технологическом уровне — блокировка всплывающих окон, Javascript, Flash, поиск по запрещенным словам или же удаление рекламных блоков из базы зарегистрированных хостов. Конечно, есть и другие способы, но сейчас не об этом…

Концепция информационных блоков

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

Определение важности информации для пользователя

Понятно, что не вся информация одинаково полезна (важна) для пользователя. Также понятно, что оценка важности — субъективное понятие, но здесь я не претендую на абсолютность. Но, интуитивно, важность информации можно поделить на три вида:

• важная информация (основной контент)
• маловажная информация (related links, most viewed, «с этим товаром также покупают» и т.д.)
• информационный мусор (шапка, подвал сайта, реклама и т.д.)

Можно, конечно, разбивать на большее количество уровней, но, думаю, пока обойдемся этими тремя.

Проблемы и задачи

Необходимо было решить следующие задачи для решения поставленной цели:

• разделение веб-страницы на информационные блоки
• создание модели для оценки важности конкретного блока
• логика для принятия решения какому блоку какой тип важности присвоить

Разделение веб-страницы на информационные блоки

Не совсем тривиальная задача, как может показаться на первый взгляд. Ранние подходы были связаны с 1) анализом DOM модели 2) анализом большого количества страниц внутри сайта и определения т.н. «шаблона» сайта. Как правило, эти подходы не давали хорошего результата.

Решение — использование алгоритма VIPS (Vision-based Page Segmentation Algorithm) от Microsoft Research Asia. Если кратко, то они используют комбинированный подход, а именно анализ DOM модели и собственные правила сегментации, выведенные экспертным или экспериментальным путем.

Замеченные минусы:

• библиотека на unmanaged C++, поэтому нет тесной интеграции с новыми элементами управления (например, с WebBrowser), поэтому пришлось поиграться с интеграцией
• алгоритм использует свойство Granularity — т.е. минимальное расстояние между информационными блоками. Понятно, что эти расстояния будут разными для разным сайтов. Сейчас подбирать нужно руками. Автоматический подбор granularity — тема отдельных исследований.
• на выходе алгоритм выдает что-то на подобие XML, но намного хуже, очень долго пришлось писать парсер, «понимающий» этот формат

Несмотря на это, VIPS достаточно удобный + за отсутствием альтернатив взяли его за основу.

Создание модели для оценки важности конкретного блока

Здесь все намного интересней, так как эту часть делал полностью сам.

Основной задачей было определить критерии оценки и то, по каким правилам различаются различные блоки. Или более конкретно: по каким признакам можно отличить набор ссылок и основной контент? В данном случае, процент вхождения слов, которые являются ссылками, несомненно выше, чем в обыкновенном тексте. Далее, средняя длина предложений основного контента, в основном больше, чем в блоке ссылок. Так вот, анализ основных параметров (характеристик) блоков могут подсказать, какой перед нами блок.

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

Среди параметров были следующие:

• средняя длина предложений
• количество слов
• количество стоп-слов
• количество ссылок, картинок, списков и т.д.
• относительные параметры типа количество слов-ссылок / количество всех слов, процент вхождения стоп-слов

и т.д.

Регрессионная модель важности информационных блоков

Для этого была разработана программа, которая:

• выбирала из Google 100-200 сайтов
• делила каждую веб-страницу на информационные блоки
• разбирала (парсила) содержимое блока по 20 параметрам
• складывала все это в базу

Далее несколько экспертов для каждого блока руками выставляли «важность» каждого блока на свое усмотрение.

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

Получилась регрессионная модель типа:

y(param1,..., param20) = coef1*param1 + coef2*param2 + coef3*param3 +… + coef20*param20

Скажу, что самым «важным» параметром оказался процент стоп-слов :)

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

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

Определение «важных» блоков

Вначале я использовал некоторые «границы» оценки важности по типу «больше 20 — основной контент, больше 10, но меньше 20 — не основной» и т.д. Но такой подход не дал результатов, так как «страница странице рознь» и коэффициенты могли существенно отличаться в рамках нескольких веб-страниц.

Хорошим решением стало использование нечеткого алгоритма кластеризации с-means, который для конкретной страницы «решает», как кластеризировать наши блоки по их числовых значениям, и «разносит» их по трем кластерам (трем, потому что три типы важности).

Что в результате?

В результате мы получаем ТОЛЬКО основной контент (ну это, конечно, в идеале, см. проблемы выше).

Реализация прототипа исполнена в виде браузера под кодовым названием «SmartBrowser» и спокойненько может быть стянут с сайта http://smartbrowser.codeplex.com/.

Требования:

• Windows 32bit (VIPS dll нужно регистрировать в системе)
• .NET Framework 3.5

Примеры

Примеры можно посмотреть на этой странице.

Так выглядит программа:

Отзывы

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

Ребята из Microsoft Research Asia (авторы алгоритма VIPS) позитивно отозвались об идеи и пожелали удачи в ее развитии.

Если у вас есть замечания, хотите развить данную тему или просто помочь советом — всегда рад. Если у кого-то есть наработки в данной области — давайте кооперироваться :)

Эта статья на хабрахабре