Рассмотрим такую задачу: есть 1000 новостных сайтов, например: engadget.com, huffingtonpost.com, sbnation.com. Их нужно распределить по классам про игры, про бизнес и финансы, про IT, про кино и музыку, например. Как это сделать? Можно просто брать один сайт за другим и назначать ему класс, но чтобы обработать таким образом 1000 сайтов нужно иметь крепкую психику и уйму времени. Можно сделать более технично: взять граф похожих сайтов, выделить интересующий подграф на 1000 вершин и кластеризовать его. Про граф похожих сайтов было написано несколько месяцев назад мной и ребятами из DCA. Граф про новостные сайты будет выглядеть примерно так:
Действительно, некоторые классы получается выделить автоматически, например «игры» и «технологии»:
Но, например, сайты про военное дело, космос и науку почему-то объединились в один кластер. В этом можно даже найти какой-то смысл, но заказчик его скорее всего не поймёт и будет прав.
Напрашивается некоторый гибридный метод, в котором классификация происходит не совсем автоматически, но и не полностью вручную. Я нашёл для себя такой метод. Успешно его использовал несколько раз и сейчас хочу им поделиться. Идея такая: классифицируем вручную несколько десятков топовых сайтов, затем для каждого последующего угадываем класс на основе уже классифицированных, проверяем результат вручную. Интерфейс на основе виджетов Jupyter может выглядеть так:
Как угадывать класс сайта? Смотрим на вершины, с которыми у сайта есть связь, оставляем те, для которых проставлен класс, считаем какой класс встречается чаще всего, вуаля, искомый класс найден. Самое замечательное свойство этого алгоритма такое: чем больше сайтов классифицировано, то лучше он угадывает классы для новых. Через какое-то время процесс будет выглядеть примерно так:
60-70% сайтов можно будет пропускать, класс для них будет указан правильно. Это значительно ускоряет процесс классификации. Как показывает практика обработать 1000 сайтов получается за один день.
В конце можно раскрасить вершины графа в соответствии с ручной разметкой, убедиться, что военные и научные сайты разделяются правильно.
ссылка на оригинал статьи http://habrahabr.ru/post/265431/
Добавить комментарий