Лаборатория анализа данных Кукушкина Александра
–1,6
рейтинг
28 декабря 2015 в 03:07

Разработка → Полуавтоматическая классификация сайтов

Рассмотрим такую задачу: есть 1000 новостных сайтов, например: engadget.com, huffingtonpost.com, sbnation.com. Их нужно распределить по классам про игры, про бизнес и финансы, про IT, про кино и музыку, например. Как это сделать? Можно просто брать один сайт за другим и назначать ему класс, но чтобы обработать таким образом 1000 сайтов нужно иметь крепкую психику и уйму времени. Можно сделать более технично: взять граф похожих сайтов, выделить интересующий подграф на 1000 вершин и кластеризовать его. Про граф похожих сайтов было написано несколько месяцев назад мной и ребятами из DCA. Граф про новостные сайты будет выглядеть примерно так:



Действительно, некоторые классы получается выделить автоматически, например «игры» и «технологии»:



Но, например, сайты про военное дело, космос и науку почему-то объединились в один кластер. В этом можно даже найти какой-то смысл, но заказчик его скорее всего не поймёт и будет прав.



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



Как угадывать класс сайта? Смотрим на вершины, с которыми у сайта есть связь, оставляем те, для которых проставлен класс, считаем какой класс встречается чаще всего, вуаля, искомый класс найден. Самое замечательное свойство этого алгоритма такое: чем больше сайтов классифицировано, то лучше он угадывает классы для новых. Через какое-то время процесс будет выглядеть примерно так:



60-70% сайтов можно будет пропускать, класс для них будет указан правильно. Это значительно ускоряет процесс классификации. Как показывает практика обработать 1000 сайтов получается за один день.

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

Кукушкин Александр @alexkuku
карма
151,0
рейтинг –1,6
Лаборатория анализа данных Кукушкина Александра
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (7)

  • +1
    А теперь на основе этого сделать web-сервис, который принимает url, а отдаёт класс. И редиректор для squid, который этот web-сервис будет дёргать и раздавать пользователям доступ только к определённым классам сайтов.
  • 0
    60-70% сайтов можно будет пропускать, класс для них будет указан правильно.


    Александр, спасибо за статью, у вас интересный подход с кластеризацией. Но получается, что точность классификации составляет всего 70%? Не самый хороший результат, практически аналогичную задачу классификации сайтов я решал с помощью k-NN классификатора и точность определения категории составляла более 90%. Правда, в отличие от кластеризации там есть свои особенности, связанные с необходимостью предварительного обучения алгоритма и фиксированным набором категорий. Но тестовая выборка из ~1000 сайтов автоматически классифицировалась где-то за час, причём 95% времени уходило на скачивание контента.
    • 0
      Да, точность 60-70%.
  • 0
    Доброе утро, не могли бы вы выложить ipython notebook файл?
    • 0
      Нет
      • 0
        Несмотря на это, огромное спасибо вам за ваши публикации.
  • 0
    А на чем это все сделано? Можно подробнее про технологии и языки, книги…? Интересно попробовать.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.