Рассмотрим такую задачу: есть 1000 новостных сайтов, например: engadget.com, huffingtonpost.com, sbnation.com. Их нужно распределить по классам про игры, про бизнес и финансы, про IT, про кино и музыку, например. Как это сделать? Можно просто брать один сайт за другим и назначать ему класс, но чтобы обработать таким образом 1000 сайтов нужно иметь крепкую психику и уйму времени. Можно сделать более технично: взять граф похожих сайтов, выделить интересующий подграф на 1000 вершин и кластеризовать его. Про граф похожих сайтов было написано несколько месяцев назад мной и ребятами из DCA. Граф про новостные сайты будет выглядеть примерно так:
Действительно, некоторые классы получается выделить автоматически, например «игры» и «технологии»:
Но, например, сайты про военное дело, космос и науку почему-то объединились в один кластер. В этом можно даже найти какой-то смысл, но заказчик его скорее всего не поймёт и будет прав.
Напрашивается некоторый гибридный метод, в котором классификация происходит не совсем автоматически, но и не полностью вручную. Я нашёл для себя такой метод. Успешно его использовал несколько раз и сейчас хочу им поделиться. Идея такая: классифицируем вручную несколько десятков топовых сайтов, затем для каждого последующего угадываем класс на основе уже классифицированных, проверяем результат вручную. Интерфейс на основе виджетов Jupyter может выглядеть так:
Как угадывать класс сайта? Смотрим на вершины, с которыми у сайта есть связь, оставляем те, для которых проставлен класс, считаем какой класс встречается чаще всего, вуаля, искомый класс найден. Самое замечательное свойство этого алгоритма такое: чем больше сайтов классифицировано, то лучше он угадывает классы для новых. Через какое-то время процесс будет выглядеть примерно так:
60-70% сайтов можно будет пропускать, класс для них будет указан правильно. Это значительно ускоряет процесс классификации. Как показывает практика обработать 1000 сайтов получается за один день.
В конце можно раскрасить вершины графа в соответствии с ручной разметкой, убедиться, что военные и научные сайты разделяются правильно.
Действительно, некоторые классы получается выделить автоматически, например «игры» и «технологии»:
Но, например, сайты про военное дело, космос и науку почему-то объединились в один кластер. В этом можно даже найти какой-то смысл, но заказчик его скорее всего не поймёт и будет прав.
Напрашивается некоторый гибридный метод, в котором классификация происходит не совсем автоматически, но и не полностью вручную. Я нашёл для себя такой метод. Успешно его использовал несколько раз и сейчас хочу им поделиться. Идея такая: классифицируем вручную несколько десятков топовых сайтов, затем для каждого последующего угадываем класс на основе уже классифицированных, проверяем результат вручную. Интерфейс на основе виджетов Jupyter может выглядеть так:
Как угадывать класс сайта? Смотрим на вершины, с которыми у сайта есть связь, оставляем те, для которых проставлен класс, считаем какой класс встречается чаще всего, вуаля, искомый класс найден. Самое замечательное свойство этого алгоритма такое: чем больше сайтов классифицировано, то лучше он угадывает классы для новых. Через какое-то время процесс будет выглядеть примерно так:
60-70% сайтов можно будет пропускать, класс для них будет указан правильно. Это значительно ускоряет процесс классификации. Как показывает практика обработать 1000 сайтов получается за один день.
В конце можно раскрасить вершины графа в соответствии с ручной разметкой, убедиться, что военные и научные сайты разделяются правильно.
Комментарии (6)
kypexin
29.12.2015 09:4460-70% сайтов можно будет пропускать, класс для них будет указан правильно.
Александр, спасибо за статью, у вас интересный подход с кластеризацией. Но получается, что точность классификации составляет всего 70%? Не самый хороший результат, практически аналогичную задачу классификации сайтов я решал с помощью k-NN классификатора и точность определения категории составляла более 90%. Правда, в отличие от кластеризации там есть свои особенности, связанные с необходимостью предварительного обучения алгоритма и фиксированным набором категорий. Но тестовая выборка из ~1000 сайтов автоматически классифицировалась где-то за час, причём 95% времени уходило на скачивание контента.
TheDeadOne
А теперь на основе этого сделать web-сервис, который принимает url, а отдаёт класс. И редиректор для squid, который этот web-сервис будет дёргать и раздавать пользователям доступ только к определённым классам сайтов.