Очищаем веб-страницы от информационного шума

    Приветствую всех!

    Предыдущие мои статьи были, в основном, о теоретической части 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

    Примеры


    Примеры можно посмотреть на этой странице, где впервые была опубликована новость об программе.

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

    image

    Отзывы


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

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

    Если у вас есть замечания, хотите развить данную тему или просто помочь советом — всегда рад. Если у кого-то есть наработки в данной области — давайте кооперироваться :)
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 33

      +8
      Исходя из первого абзаца:
      «Проблема заключается в том, что добрая половина веб-сайтов содержит кучу ненужной информации»
      получается, что вот этот сервис как раз делает эту работу
      lab.arc90.com/experiments/readability/
      Или я чего-то недопонял?
        0
        Вы поняли правильно. Большое спасибо за ссылку.
          0
          У меня по данному урлу не заходит, может закралась ошибка?
            +3
            Интересный сервис, считает что контентом на хабре являются комментарии а не сама статья :)
              +2
              У меня наоборот осталась только статья, без комментариев
              0
              По вашей ссылке, выходит, что ваш комментарий самая полезная часть данной страницы:

              полезный комментарий
              0
              Спасибо очень интересная тема, сам только недавно начал копать в эту сторону. Ваш пост дал понять мне, на сколько далек я еще от «истины» =)
                +1
                search.cpan.org/~jzhang/HTML-ContentExtractor-0.02/lib/HTML/ContentExtractor.pm
                  0
                  Очень интересно.

                  А как вы определяли вклад каждого фактора в общую картину? По регрессионной модели?
                    0
                    Да, для каждого фактора был найдет его «вес» в общей регрессионной модели.
                    +5
                    имхо такой продукт должен существовать в виде расширения к одному из браузеров (или для всех :) )
                    думаю не очень удобно будет каждый раз копипастить ссылки в отдельную программу.
                    даешь чистый веб! :)
                      0
                      для FF оно, разумеется, существует ;o) tidyread называется.
                        0
                        да, интернет уже не тот..
                        раньше все эти банеры, ссылки и прочий crap был только на порно сайтах :))
                      +2
                      По моему первичную фильтрацию контента удобнее представлять на конечном сайте. Всегда приятно пользоваться веб сервисом на котором контент можно настроить под себя, а не читать всю кучу ненужной информации. Согласен с предыдущим комментарием по поводу расширения к браузеру. :)
                      • UFO just landed and posted this here
                          0
                          Вы рассуждаете с точки зрения практического использования и я с Вами полностью согласен. В данный момент идея состоит в том, чтобы очистить, а как после этого мы применим ее и где — уже вопрос следующих этапов.

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

                            Ещё комиксные сайты некоторые проблемы доставляют. Мне на них оказалось проще зафильтровать всё, что точно не является контентом, чем пытаться выделить контентный IMG.
                          0
                          Что Вы думаете о возможности для пользователя скрывать/отключать блоки с маловажной информацией и «мусором»? До прочтения Вашей статьи считал, что нельзя позволять юзерам такие вольности.
                          • UFO just landed and posted this here
                              0
                              может пропустил. А регрессия линейная или нет?
                                0
                                В данном примере регрессия линейная. Как следующий этап исследований — это нахождение факторов которые вообще должны учавствовать в регрессионной модели, ведь по определению все факторы должны быть независимыми, что на практике не всегда верно.
                                +1
                                Да, SmartBrowser в качестве плагина для лисы был бы очень полезен, единственно не понимаю зачем Микрософту спонсировать разработку — не думаю что им это выгодно.

                                А количество плагинов для лисы, позволяющих настраивать вид страницы огромно, вот только для автоматического клинапа нашелся только один — Clean the junk — https://addons.mozilla.org/ru/firefox/addon/13193
                                  0
                                  > Clean the junk

                                  AdBlock неплохо с этим справляется. Особенно если с ElementHidingHelper совмещен.
                                  А вы ищете TidyRead.
                                  –1
                                  В примере отлично видно, что данная технология фильтрует рекламные баннеры, как и многие расширения для браузеров.
                                  Не может ли сложиться такой ситуации, что сайты, основной статьей монетизации которых являются те самые клики по баннерам, просто будут «байкотировать» этот браузер, не показывая ему контент? Ведь используемое расширение для браузера сложно определить, а сам браузер — вполне реально.
                                    0
                                    «An error has been occured while processing the query. Please try again.» — И ни в какую. Windows 7 7100
                                    Было бы неплохо, если бы программа пыталась открыть url не только при клике мышкой по кнопочке, но и при нажатии клавиши Enter.
                                      0
                                      тоже проблемы:

                                      System.IO.FileNotFoundException: Невозможно загрузить файл или сборку «Microsoft.mshtml, Version=7.0.3300.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a» или один из зависимых от них компонентов. Не удается найти указанный файл.
                                      Имя файла: «Microsoft.mshtml, Version=7.0.3300.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a»
                                    0
                                    Больше чем уверен, такую штуку можно было бы скомпилять и для Net 2.0. Просто многие еще висят на XP. Или вы использовали фичи более поздних версий фреймворка, еслс ДА, то какие — интересно как разработчику. Сам стараюсь все под 2.0 подгонять…
                                      0
                                      Конечно, можно было писать и на 2.0.

                                      В 3.5 использую упрощенную запись свойств типа «public string SomeProp {get;set;}» — при большом количестве свойств ощущается экономия места. Ну и Linq + лямбда-выражения, без них никак… :)
                                        0
                                        ну про «без них никак» вы лукавите ))
                                        Собственно, почему написал пост выше — на большинстве предприятий большая инертность, редко кто ставит что-то выше XP (тут и финансирование[софт, компы], переобучение и др. факторы), поэтому и задал вопрос… мне вот приходится вторым фреймворком обходиться(очень здорово, что софт без особых проблем под mono работает).
                                          0
                                          Когда привыкаешь к хорошему, трудно себя заставить делать это по другому.

                                          Я, например, убедил начальство использовать ASP.NET 3.5 SP1 ради ASP.NET Dynamic Data для разработки корпоративного сайта. Основной аргумент — сокращение времени разработки (а, значит, экономия денег для компании). А хостинг найти для 3.5 (даже с SP1) сейчас не проблема.
                                      0
                                      Кстати, по реализации.

                                      Чтобы не приходилось «дискретно» решать мусор это или что-то важное, можно просто использовать яркость/прозрачность контента.
                                      Чуть приглушить «маловажную информацию» и чуть более приглушить «мусор», и чтение станет гораздо более приятным. В то же время это даст возможность все-таки добраться до информации, распознанной как «шум».
                                      Плюс дать возможность по, к примеру, Ctrl-Shift-Mouse Scroll восстанавливать/приглушать яркость и цены такой штуке не будет! А еще если в виде плагинов :)

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

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

                                        Only users with full accounts can post comments. Log in, please.