Существует огромное количество алгоритмов кластеризации.
Основная идея большинства из них заключается в группировке идентичных последовательностей в один класс или кластер на основе сходства.
Как правило, выбор алгоритма определяется поставленной задачей.
Что касается текстовых данных, то сравниваемыми компонентами являются последовательности слов и их атрибуты (например, вес слова в тексте, тип именованной сущности, тональность и т. д.).
Таким образом, тексты изначально преобразуются в векторы, с которыми производятся различные виды манипуляций.
При этом, как правило, возникает ряд проблем, связанных с: выбором первичных кластеров, зависимостью качества кластеризации от длины текста, определением общего количества кластеров и т. д. Но самая сложная проблема Это отсутствие связи между текстами, близкими по смыслу и использующими разную лексику.
В таких случаях ассоциация должна происходить не только на основе сходства, но и на основе смысловой смежности или ассоциативности.
Например, Лондон передумал объявлять новую холодную войну России
Борис Джонсон: Запад не находится в состоянии новой холодной войны с Россией
В МИД Великобритании заявили, что Запад не хочет новой холодной войны с Россией
Все три примера — это одни и те же новости, однако использованная лексика разная.
В таких случаях алгоритмы кластеризации, основанные на лексическом сходстве, уже не помогают. Задачи такого типа решаются двумя способами: 1) составлением тезаурусов и 2) применением разного рода «хитрых» алгоритмов, устанавливающих ассоциативно-семантические связи между словами, таких как: латентно-семантический анализ (ЛСА), вероятностный латентно-семантический анализ (ПЛСА).
, скрытое распределение Дирихле (LDA) и т. д. Первый путь - получение тезаурусов - достаточно трудоемкий и полностью определяется поставленной задачей.
Это означает, что пока невозможно создать универсальный тезаурус.
Второй способ – алгоритмический – также имеет свои недостатки.
Прежде всего, это «размытость» самих методов и неочевидность их применения к текстовым данным.
Допустим, LDA требует условия нормального распределения, которое не всегда выполняется при решении лингвистических задач.
Как правило, все эти алгоритмы имеют большое количество параметров, определение которых является эмпирическим и может существенно повлиять на качество решения (например, приведение сингулярных значений диагональной матрицы в LSA имеет очень нелинейное влияние на результат).
Ряд вышеперечисленных проблем мы попытались обойти, используя результаты алгоритма Word2Vec.
Word2Vec
Описание алгоритма можно найти в Википедия или другой информационный ресурс.Алгоритм создавался в первую очередь для поисковых задач, поэтому непосредственно для других лингвистических целей его следует использовать с осторожностью.
Алгоритм имеет два метода обучения и несколько вариантов демонстрации результатов.
В частности, нас будет интересовать представление результата занятий — получение ассоциативно-семантических классов (кстати, с использованием k-средних).
Как показывают эксперименты, даже небольшие коллекции из нескольких миллионов слов образуют более или менее «значимые» классы слов.
Но как использовать такой результат, если слова не имеют веса (например, предлоги и «ключевые» слова имеют в такой модели одинаковое представление)? Другая проблема заключается в том, что классы несовершенны и, например, служебные слова могут попасть в семантически значимый класс.
Использовать стоп-лист? Тогда есть риск выплеснуть вместе с водой и ребенка.
В целом использование стоп-листов имеет свои существенные недостатки (например, выбрасывая местоимения, мы теряем общероссийское молодёжное общественно-политическое движение «НАШИ»; выбрасывая однобуквенные слова, мы не найдём информацию о « «Коммерсант» — сокращение газеты «Коммерсантъ» и др.
).
Наконец, какое количество классов будет оптимальным для кластеризации текста? Зависит ли это от размера обучающей или тестовой выборки, темы текста, его объема? На эти ключевые вопросы мы ответим во второй части публикации, а пока кратко опишем алгоритм.
Описание алгоритма
Идея алгоритма состоит в том, чтобы сравнивать не сами слова или составленные из них последовательности (так называемые n-граммы), а семантические классы, в которые они попадают. Для обучения требуется большой объем текстового материала (сотни тысяч, а лучше десятки миллионов словоупотреблений; чем больше выборка, тем меньше тематическая связь модели с текстом, тем реже приходится корректировать модель к тексту).В результате обучения получается список, где практически каждому слову текста присвоен класс (количество классов указывается на этапе обучения).
Затем этот список на основе частотных распределений слов в тексте и по соответствующему им классу приводится к формату: слово – класс – вес, сглаживается по определенному алгоритму.
Важными параметрами здесь являются общее количество классов и коэффициенты сглаживания (подробнее во второй части публикации).
Вот пример небольшого семантического класса.
| малыш | дочь |
| мама | свекровь |
| учитель | дочь |
| малыш | родственники |
| учитель | моложе |
| младшая сестра | жена |
| малыш | папины |
| сестра | бывший |
| тетя | бабушка |
| бабушка | старшая |
| Подруга | Подруга |
| мать | госпожа |
| супруг | гражданин |
| тетя | семья |
| внучка | девочка |
| девичий | мамина |
| ее |
Он может мешать кластеризации материала, поскольку увеличивает частоту и «тянет одеяло» на себя.
Такие «выбросы» можно убрать последующим сглаживанием модели.
Согласно полученной модели все слова из тестовой выборки преобразуются в числа, соответствующие семантическим классам, и дальнейшие манипуляции происходят только с числами.
Для кластеризации используется простой алгоритм сравнения накопленных документов друг с другом.
Сравниваются целые типы (int), поэтому скорость достаточно высокая.
При этом на сравнение накладывается ряд фильтров, таких как ограничения на количество семантических классов в одном документе, минимальное количество документов в кластере, меры близости - количество совпадающих классов.
Логика алгоритма организована таким образом, что один и тот же документ может попадать в разные кластеры (поскольку первичные кластеры не определены).
Из-за этой «размытости» первичным результатом является довольно большой набор кластеров со схожими темами.
Поэтому необходима посткластеризация, которая просто объединяет близкие кластеры, сравнивая их по количеству одинаковых документов (по их id).
Таким образом, используя описанную выше логику, можно добиться не только высокой скорости кластеризации, но и не заморачиваться ни с определением первичных кластеров, ни с их общим количеством.
Результаты и выводы
При кластеризации сложно говорить о качестве результата, поскольку оно во многом зависит от кластеризуемого материала.В этом смысле особых оснований для введения «золотого» стандарта нет. Но имеет смысл протестировать модели на разных корпусах на предмет классификации (о чем речь пойдет, опять же, во второй части статьи).
Как показали тесты на классификацию документов векторным методом по униграммам (косинусное сравнение), модели кластеризации почти так же точны, как модели на основе «слов».
Это означает, что «неконтролируемая» классификация (модели в этом смысле универсальны) может показывать результаты лишь немногим хуже, чем полноценное контролируемое обучение.
Износ составляет 1-10% и зависит от испытуемого материала.
Но это не цель! Это просто означает, что модели кластеризации, полученные с помощью алгоритма Word2Vec, вполне пригодны для их использования на любом типе материала с любым количеством классов (в данном случае кластеров).
Качество результата определяется порогами фильтрации: например, если нам нужно просто выявить нечеткие дубликаты, то нужно задать более строгие параметры; и наоборот, если вам нужно просто просмотреть основные темы публикуемого материала, то можно задать более мягкие параметры.
В целом алгоритм универсален: он может работать на любом объеме материала.
Хотя для больших объемов лучше работать в окнах по 10-100 тысяч документов; Полученные таким образом первичные кластеры затем объединяются в посткластеры.
Алгоритм также слабо чувствителен к длине документа: желательно, чтобы «длинные» документы были семантически однородны (принадлежали одной теме).
Однако у этого алгоритма есть ряд проблем.
Прежде всего, это зависимость результата от количества классов в модели: иногда это может стать чувствительным, особенно для «слабых» кластеров, т.е.
кластеров с небольшим объемом документов.
Вторая проблема возникает из-за несовершенства определения семантических классов, в результате чего иногда схожие по смыслу документы попадают в разные кластеры (различающиеся, скажем, в паре классов).
Такие проблемы устраняются дополнительным пост-слиянием, основанным на факторизации документов: выборе именованных объектов и связей между ними.
Но эту задачу решить проще, поскольку количество кластеров невелико по отношению к начальному объему документов и большая часть из них уже объединена.
Таким образом, представленный алгоритм имеет ряд преимуществ:
- кластеризация происходит не по словам, а по семантическим классам;
- независимость результата от длины документов;
- независимость результатов от объема материала;
- автоматическое определение количества кластеров;
- нет необходимости определять первичные кластеры;
- высокая скорость работы, что позволяет использовать данный алгоритм на большом потоке текстовых сообщений.
Для небольших объемов тематически обособленного материала (например, фармацевтика, игровые чаты и т.п.
) лучше использовать тезаурусы, так как модель Word2Vec может не содержать профессиональной терминологии или узкоспециализированного жаргона.
Теги: #word2vec #кластеризация #обработка текста #Семантика #Интеллектуальный анализ данных #Алгоритмы #Машинное обучение
-
Доступна Версия Zabbix 5.2.
19 Oct, 24 -
Шесть Техник Дизайна 2.0
19 Oct, 24 -
Востро, Через Нетбук
19 Oct, 24 -
Новый Грязный.ру. Сейчас 2.0
19 Oct, 24
