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



Например,

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

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

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

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

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

Word2Vec

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

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

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

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

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

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

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

Вот пример небольшого семантического класса.

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

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

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

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

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

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

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

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

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

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

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

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

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