Приветствую всех!
Предыдущие мои статьи были, в основном, о теоретической части 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) позитивно отозвались об идее и пожелали удачи в ее развитии.
Если у вас есть замечания, хотите развить данную тему или просто помочь советом — всегда рад. Если у кого-то есть наработки в данной области — давайте кооперироваться :)
Предыдущие мои статьи были, в основном, о теоретической части 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) позитивно отозвались об идее и пожелали удачи в ее развитии.
Если у вас есть замечания, хотите развить данную тему или просто помочь советом — всегда рад. Если у кого-то есть наработки в данной области — давайте кооперироваться :)
