Рекомендательная система: полезные задачи текстмайнинга

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

    Автоматическое определение категорий для веб-страниц из RSS-лент


    Обычная схема добавления веб-страниц (вернее, ссылок на них) в Surfingbird такова: при добавлении новой ссылки пользователь должен указать до трёх категорий, к которым принадлежит эта ссылка. Понятно, что в такой ситуации задача автоматического определения категорий не стоит. Однако, кроме ручного добавления, ссылки попадают в базу и из RSS-потоков, которые предоставляют многие популярные сайты. Поскольку ссылок, поступающих через RSS-потоки, очень много, зачастую модераторы (а в этом случае именно они вынуждены проставлять категории) просто не справляются с таким объёмом. Возникает задача создания интеллектуальной системы автоматической классификации по категориям. Для ряда сайтов (например, lenta.ru или sueta.ru) категории можно вытащить непосредственно из rss-xml и вручную привязать к нашим внутренним категориям:

    image
    image

    Дела обстоят хуже для RSS-потоков, в которых отсутствуют фиксированные категории, а вместо этого указаны пользовательские теги. Введенные произвольным образом теги (типичный пример — теги в постах ЖЖ) невозможно вручную связать с нашими категориями. И здесь уже включается более тонкая математика. Из страницы извлекается текстовый контент (тайтл, теги, полезный текст) и применяется LDA-модель, краткое описание которой можно найти в моей предыдущей статье. В результате вычисляется вектор вероятностей принадлежности веб-страницы к тематическим LDA-топикам. Полученный вектор LDA-топиков сайта используется как вектор признаков для решения задачи классификации по категориям. При этом объектами классификации являются сайты, классами являются категории. В качестве метода классификации использовалась логистическая регрессия, хотя можно применить любой другой метод, например наивный байесовский классификатор.

    Для тестирования метода обучение моделей происходило на 5 тысячах классифицированных модератором сайтах из RSS-рассылок, для которых также было известно распределение по LDA-топикам. Результаты обучения на тестовой выборке представлены в таблице:

    image

    В результате приемлемое качество классификации (по доле ложных обнаружений и доле ложных пропусков) получилось только по следующим категориям: Pictures, Erotic, Humour, Music, Travel, Sport, Nature. По слишком общим категориям, например Photo, Video, News, ошибки большие.

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

    Поиск дубликатов и плагиата среди веб-страниц


    Еще одна задача, которую позволяет решить текстмайнинг, — это поиск и фильтрация ссылок с повторяющимся контентом. Повтор контента возможен по одной из следующих причин:
    1. по нескольким разным ссылкам происходит редирект на одну и ту же конечную ссылку;
    2. контент полностью скопирован на различных веб-страницах;
    3. контент скопирован частично или слегка изменён.

    Первый и второй пункты являются техническими и решаются получением конечных ссылок и буквальным сравнением полезного контента для всех страниц в базе. Однако даже при полном копипасте формальное сравнение полезного текста может не пройти по понятным причинам (например, попали случайные символы или слова из меню сайта), а текст может быть и слегка изменён. Этот третий вариант мы и рассмотрим более подробно. Типичный двойник может выглядеть так:

    image

    Задача определения заимствований в широком смысле слова довольно сложна. Нас же она интересует в более узкой постановке: нам не нужно искать плагиат в каждой фразе текста, а нужно просто сравнить документы по контенту целиком.
    Для этого можно эффективно использовать уже имеющуюся модель «мешка слов» (bag of words) и посчитанные веса TF-IDF всех термов сайта. Существует несколько различных техник.

    Для начала введем обозначения:
    image — cловарь всех различных слов;
    image — корпус текстов (контент веб-страниц);
    image — множество слов в документе.

    Для сравнения двух документов image и image сначала нужно построить объединённый вектор слов image из слов, которые встречаются в обоих документах:
    image
    Сходство текстов рассчитывается как скалярное произведение с нормализацией:
    image
    Если image (порог сходства), то страницы считаются двойниками.

    Другой подход не учитывает веса TF-IDF, а строит сходство по бинарным данным (есть слово в документе или нет). Для оценки различия страниц используется коэффициент Жаккара:
    image,
    где image — множество общих слов в документах.

    В результате применения этих методов выявлено несколько тысяч двойников. Для формальной оценки качества необходимо экспертным образом разметить двойников на обучающей выборке.

    На этом пока всё, надеюсь, статья окажется вам полезной. А мы будем рады новым идеям о том, как применить text mining для улучшения рекомендаций!
    Surfingbird
    Company
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 10

      0
      А как у Вас rss-потоки привязываются? Или это пока только разработки.
        0
        Загрузка из rss потоков уже давно в продакшене. А зечем их привязывать, просто запрашивается rss-xml по известному адресу и парсится. Вот, например, адрес rss-xml для Ленты.ру: lenta.ru/rss/news
          0
          Где-нибудь это описано? (Я имею ввиду привязку rss-потока к каналу на surfingbird)
            0
            Нет, к сожалению, не описано.

            Заведите сначала канал surfingbird.ru/publishers, и если он пройдет модерацию, попросите добавлять ссылки через RSS.
            Правда, вы должны понимать, мы фильтруем контент довольно строго и модерацию можно и не пройти. Или пройти, но контент может нам все же понравиться недостаточно, чтобы добавить RSS.
            Логика тут такова, что каждый RSS — это ручной (полуручной, но все же) труд модератора по простановке категорий.
        0
        Есть ли какие-нибудь причины тому, что Вы не используете Алгоритм шинглов для идентификации дубликатов?
          0
          Причина в том, что алгоритм поиска шинглов более сложный в реализации, чем представленные в статье. Если результаты внедрения более простых алгоритмов нас не устроят, будем двигаться дальше и рассмотривать более сложные алгоритмы определения плагиата (об этом в статье упомяналось)
            +3
            Если честно, немного удивительно, что Вы используете модель мешка слов, ведь она не учитывает порядок слов.

            На самом деле, реализация алгоритма шинглов использует тот же коэффициент Жаккара. Только в данном случае, вместо слов, оперируют шинглами (на практике — хэшами шинглов, но это уже детали...).

            Попросту говоря, шинглы — это кортежи из нескольких слов, построенные следующим образом (рисунок схематический):

            Чисто иллюстративный пример:

            • слон ест красное яблоко
            • яблоко ест красного слона

            (у некоторых слов разные окончания, но будем считать, что в качестве предварительной обработки мы используем лемматизатор).

            Если использовать модель мешка слов, то получится, что эти два предложения дубликаты, поскольку содержат идентичные наборы слов.

            Что на это скажет алгоритм шинглов:

            Если использовать в качестве шинглов — кортежы слов, взятых через одно, получим:
            • слон ест красное яблоко -> A = {слон, красный} и {ест, яблоко}
            • яблоко ест красного слона -> B = {яблоко, красный} и {ест, слон}

            Множества А и В не содержат одинаковых кортежей. Поэтому, пересечение A и B, даст пустое множество. Таким образом, можно заключить что данные тексты не дубликаты.

            Ещё раз обращаю внимание — пример чисто иллюстративный, но, надеюсь, что общую концепцию мне удалось проиллюстрировать :-)

            P.S. На самом деле, именно характер данных, их объём и другие особенности предметной области диктуют алгоритм обработки. Так что, если в Вашем случае описанный алгоритм работает хорошо, то, действительно, не стоит усложнять систему.

            В данном комментарии, я просто хотел показать, что в общем случае Алгоритм шинглов более эффективный для идентификации дубликатов.
              0
              Спасибо за такой развернутый комментарий. Да, действительно у модели мешка слов есть ряд недостатков. Главное же его преимущество — существенное упрощение предварительной обработки и дальнейшего анализа. Мы используем эту модель для обучения LDA, т.к. в тематических вероятностных моделях игнорирование порядка слов не является столь критичным. А выявление двойников — это побочная задача, которою хотелось решить наименьшей кровью… Вообще, мы уже начинали прорабатывать тему выделения ключевых словосочетаний из текста, вместо отдельных слов. Была попытка использовались API различных готовых систем, которые выделют ключевые фразы из текста. Я думаю, в ближайшее время мы продолжим работу в этом направлении, еще раз спасибо за ценный комментарий.
                0
                Желаю Вам успехов! :-)
          0
          О, математические формулы, здорово.

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