Кластеризация текстовых документов по семантическим признакам (часть первая: описание алгоритма)

    Существует огромное количество алгоритмов кластеризации. Основная идея большинства из них – объединить одинаковые последовательности в один класс или кластер на основе сходства. Как правило, выбор алгоритма определяется поставленной задачей. Что касается текстовых данных, то здесь сравниваемыми составляющими служат последовательности слов и их атрибутов (например, вес слова в тексте, тип именованной сущности, тональность и пр.). Таким образом, тексты изначально преобразуются в вектора, с которыми производят разного типа манипуляции. При этом, как правило, возникает ряд проблем, связанных с: выбором первичных кластеров, зависимостью качества кластеризации от длины текста, определением общего количества кластеров и т.п. Но наиболее сложной проблемой является отсутствие связи между близкими по смыслу текстами, в которых используется разная лексика. В таких случаях объединение должно происходить не только на основе сходства, а еще и на основе семантической смежности или ассоциативности.



    Например,

    В Лондоне передумали объявлять России новую холодную войну
    Борис Джонсон: Запад не находится в состоянии новой холодной войны с РФ
    В британском МИД заявили, что Запад не хочет новой холодной войны с Россией


    Все три примера являются одной новостью, тем не менее, лексика используется разная. В таких случаях уже не помогают алгоритмы кластеризации, основанные на лексическом сходстве.
    Задачи такого типа решаются двумя путями: 1) составлением тезаурусов и 2) использованием разного рода «хитрых» алгоритмов, устанавливающих ассоциативно-семантические связи между словами, как-то: латентно-семантический анализ (LSA), вероятностный латентно-семантический анализ (pLSA), латентное размещение Дирихле (LDA) и т.п.

    Первый путь – получение тезаурусов – достаточно трудоемок и полностью определяется поставленной задачей. Это значит, что создать универсальный тезаурус пока не представляется возможным.

    Второй путь – алгоритмический – также имеет свои недостатки. Прежде всего, это «туманность» самих методов и неочевидность их применения для текстовых данных. Скажем, LDA требует условия нормальности распределения, что при решении лингвистических задач не всегда удовлетворяется. Как правило, все эти алгоритмы имеют большое количество параметров, определение которых является эмпирическим и может существенно повлиять на качество решения (например, сокращение сингулярных значений диагональной матрицы в LSA очень нелинейно влияет на результат).

    Мы попробовали обойти ряд вышеуказанных проблем, воспользовавшись результатами работы алгоритма Word2Vec.

    Word2Vec


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

    Алгоритм имеет два способа обучения и несколько вариантов демонстрации результатов. Нас, в частности, будет интересовать представление результата classes – получение ассоциативно-семантических классов (с использованием k-mean, кстати).

    Как показывают эксперименты, даже на небольших коллекциях в несколько миллионов словоупотреблений получаются более-менее «осмысленные» классы слов. Но как использовать такой результат, если у слов нет веса (например, предлоги и «ключевые» слова имеют одинаковое представление в такой модели)? Другой проблемой является то, что классы не идеальны и, например, служебные слова могут попасть в семантически значимый класс. Использовать стоп-лист? Тогда есть риск выплеснуть из корыта вместе с водой ребенка. Вообще применение стоп-списков имеет свои существенные недостатки (например, выкидывая местоимения, мы теряем общероссийское молодёжное общественное политическое движение «НАШИ»; выбрасывая однобуквенные слова, мы не обнаружим информации о «Ъ» — сокращение газеты «Коммерсантъ» и т.д.).

    Наконец, какое количество классов будет оптимальным для кластеризации текста? Зависит ли это от объема обучающей или тестовой выборки, тематики текста, его объема? На эти ключевые вопросы мы ответим во второй части публикации, а пока кратко опишем алгоритм.

    Описание алгоритма


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

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

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

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

    По полученной модели все слова из тестовой выборки преобразуются в цифры, соответствующие семантическим классам, и дальнейшие манипуляции происходят только с цифрами. Для кластеризации используется простой алгоритм сравнения накопленных документов между собой. Сравниваются целочисленные типы (int), поэтому скорость получается достаточно высокой. При этом на сравнение наложен ряд фильтров, типа ограничений по количеству семантических классов в одном документе, минимального количества документов в кластере, меры близости – количество совпавших классов. Логика алгоритма организована так, что один и тот же документ может попадать в разные кластеры (поскольку первичные кластеры не определены). Вследствие такой «нечеткости» первичный результат представляет собой достаточно объемный набор близких по тематике кластеров. Поэтому требуется пост кластеризация, которая просто объединяет близкие кластеры, сравнивая их по количеству одинаковых документов (по их id).

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

    Результаты и выводы


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

    Как показали тесты по классификации документов векторным методом на униграммах (сравнение по косинусу), модели кластеризации почти не уступают в точности моделям на «словах». Это значит, классификация «без учителя» (модели в этом смысле универсальны) может показывать результаты лишь немного хуже, чем полноценное обучение с учителем. Ухудшение составляет 1-10% и зависит от тестируемого материла. Но это ведь и не является целью! Просто это значит, что модели кластеризации, полученные с помощью алгоритма Word2Vec вполне валидны для их применения на любом типе материала с любым количеством классов (в данном случае кластеров).

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

    В целом, алгоритм универсален: он может работать на любом количестве материала. Хотя при больших объемах лучше работать окнами по 10-100 тысяч документов; полученные таким образом первичные кластеры затем объединяются в пост кластеризации. Алгоритм так же слабо чувствителен к длине документа: желательно, чтобы «длинные» документы были семантически однородны (принадлежали одной теме).

    Тем не менее, в данном алгоритме существует ряд проблем. Прежде всего, это зависимость результата от количества классов в модели: иногда это может стать чувствительным, особенно для «слабых» кластеров, т.е. кластеров с небольшим объемом документов. Вторая проблема следует из-за неидеального определения семантических классов, вследствие чего иногда близкие по смыслу документы попадают в разные кластеры (отличающиеся, скажем, парой классов). Такие проблемы устраняются дополнительным пост объединением, основанным на факторизации документов: выделении именованных объектов и связей между ними. Но такая задача решается уже проще, ибо количество кластеров небольшое относительно первичного объема документов и большая часть из них уже объединена.

    Таким образом, представленный алгоритм имеет ряд преимуществ:

    • кластеризация происходит не по словам, а семантическим классам;
    • независимость результата от длины документов;
    • независимость результатов от объема материала;
    • автоматическое определение количества кластеров;
    • отсутствие необходимости определения первичных кластеров;
    • высокая скорость работы, что позволяет использовать данный алгоритм на большом потоке текстовых сообщений.

    Несмотря на то, что алгоритм не чувствителен к объему входящего материала, его рекомендуется использовать для кластеризации больших потоков неструктурированной информации, когда важны не только качество кластеризации, но и скорость получения результата. Для небольших объемов тематически обособленного материала (например, фармацевтики, игровых чатов и т.п.) лучше использовать тезаурусы, поскольку модель Word2Vec может не содержать профессиональную терминологию или узкоспециализированный жаргон.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 9

      +2

      Алгоритм-то где? )

        0
        Присоединюсь к вопросу el777 — более удобоваримое описание было бы не лишним (хоть формулами, хоть побитый на отдельные пункты текст :-) ). А то вроде часть понятна, но смысл ускользает.

        И да — как я понимаю — обучал word2vec на наборе текстов и кластеризовал полученные вектора? Было бы интересно получить набор кластеров (ну и вектора word2vec, для которых он составлен, конечно).

        «В результате обучения получается список, где почти к каждому слову текста приписан какой-либо класс» — как я понимаю, в его качестве берется N ближайших кластеров? А есть ли смысл это делать на этапе работы с отдельными словами (если я верно помню суть описанного в https://habrahabr.ru/post/277563/ — можно было провести отбор уже на стадии работы с вектором текста)
          0
          Алгоритм, действительно, прост и его достаточно описать на словах. Интереснее само получение моделей. Во второй части будут и формулы, картинки и примеры. Возможно, что-то выложу в гит.
          И да — как я понимаю — обучал word2vec на наборе текстов и кластеризовал полученные вектора? Было бы интересно получить набор кластеров (ну и вектора word2vec, для которых он составлен, конечно).

          Да, обучал на большом объеме текстов, но не кластеризовал, а использовал при обучении параметр "-classes", например:
          time $BIN_DIR/word2vec -train $TEXT_DATA -output $CLASSES_DATA -cbow 0 -size 200 -window 5 -negative 0 -hs 1 -sample 1e-3 -threads 12 -classes 500
          — там уже вшит k-mean.
          +1
          Предлагаю пойти немного глубже.А именно:

          1. Один токен имеет отношение к нескольким кластерам. То есть, каждому токену ставится в соответсвие вектор действительных чисел, значения которого — дистанция от токена до центра кластера
          2. Проводить нормализацию. Речь о том, что кластеры сильно неравновесны — в одних (обычно наиболее ценных для классификации) располагаются редкие слова — названия и аббревиатуры, в других — частотные слова — общая лексика. Наша цель — выровнять эти кластеры по частоте так, что бы они оказывали соизмеримое влияние на итоговую оценку. Без нормализации документы разделяются более по стилю (общеупотребительным словам), а после нормализации — по смыслу (названия, термины, специфические обороты)
          3. Можно пойти ещё дальше и разметить обучающий текстовый файл метками классов, в результате кластеры лягут не случайным образом, а разведутся в векторном пространстве на максимальную дистанцию для документов разных классов.

          Почитать об этом можно тут:
          https://habrahabr.ru/post/277563/
          http://servponomarev.livejournal.com/10604.html
            –1
            Спасибо, с ваши публикации читал, разумеется.
            1 — пробовал, но выбрал другой вариант (напишу во второй части), более простой (и более быстрый). А поскольку результат удовлетворил, то на том пока и остановился.
            2 — именно это и является главным. Если в вкратце: для нормализации использовал df и дисперсию (или sd — без разницы).
            3 — интересная мысль, но это уже будет классификация, наподобие обучения с учителем. А нужна чистая кластеризация: идет поток сообщений по всем популярным источникам (сотни сообщений в секунду), нужно поймать основные кластеры, скажем, за четверть часа…
              0

              Тут вопрос в том, что кластеризация тоже не в вакууме делается. Можно ведь кластеризовать текст и по
              количеству вхождений буквы А. А если нужна тематическая кластеризация, то нужны темы, относительно которых кластеризуем документы. Можно использовать Вики в качестве источника тем. Но все равно — качественной кластеризуем, если у нее под капотом нет классификации — не получится.

            0
            В том-то и дело, что темы заранее не определены: может быть поток соц медиа, а может СМИ. Поэтому приходится решать обратную задачу: сначала получить кластеры, а потом с помощью NER или концептов того же вики выяснять между ними отношения.Так просто быстрее на больших объемах.
              –2
              Вместо изнасилования word2vec можно обратить свой взор на целый раздел машинного обучения, который называется тематическое моделирование.

              А если жажда применять word2vec неискоренима, то можно посмотреть например на такие штуки:
              https://arxiv.org/pdf/1605.02019.pdf

              Я и тематически кластера найдутся и самому себе можно будет говорить: «Я юзаю word2vec».
                0
                topic models — да, лет 10-15 назад с этого все и началось: LDA, LSA, pLSA etc. Порой что-то получалось. Но, к слову, даже очень неплохая разработка д. ф.-м. н. тов. Воронцова не показала требуемых результатов на Big data. А нам нужен результат, а не досужие опусы.

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