Существует огромное количество алгоритмов кластеризации. Основная идея большинства из них – объединить одинаковые последовательности в один класс или кластер на основе сходства. Как правило, выбор алгоритма определяется поставленной задачей. Что касается текстовых данных, то здесь сравниваемыми составляющими служат последовательности слов и их атрибутов (например, вес слова в тексте, тип именованной сущности, тональность и пр.). Таким образом, тексты изначально преобразуются в вектора, с которыми производят разного типа манипуляции. При этом, как правило, возникает ряд проблем, связанных с: выбором первичных кластеров, зависимостью качества кластеризации от длины текста, определением общего количества кластеров и т.п. Но наиболее сложной проблемой является отсутствие связи между близкими по смыслу текстами, в которых используется разная лексика. В таких случаях объединение должно происходить не только на основе сходства, а еще и на основе семантической смежности или ассоциативности.
В этой статье я сделаю обзор нескольких алгоритмов (KMeans Clustering, Agglomerative Hierarchical Clustering, community_detection) для кластеризации текста, а также проведу их сравнение.
KMeans Clustering - наиболее простой, но в то же время достаточно неточный метод кластеризации в классической реализации. Он разбивает множество элементов векторного пространства на заранее известное число кластеров k. Действие алгоритма таково, что он стремится минимизировать среднеквадратичное отклонение на точках каждого кластера. Основная идея заключается в том, что на каждой итерации перевычисляется центр масс для каждого кластера, полученного на предыдущем шаге, затем векторы разбиваются на кластеры вновь в соответствии с тем, какой из новых центров оказался ближе по выбранной метрике. Алгоритм завершается, когда на какой-то итерации не происходит изменения кластеров.
Рис. 1 – Принцип работы алгоритма
Проблемы алгоритма k-means:
1) Необходимо заранее знать количество кластеров;
2) Алгоритм очень чувствителен к выбору начальных центров кластеров. Классический вариант подразумевает случайный выбор кластеров, что очень часто являлось источником погрешности. Как вариант решения, необходимо проводить исследования объекта для более точного определения центров начальных кластеров. В моем случае на начальном этапе предлагается принимать в качестве центов самые отдаленные точки кластеров;
3) Не справляется с задачей, когда объект принадлежит к разным кластерам в равной степени или не принадлежит ни одному;
4) В том случае, когда центроиды кластеров выбираются случайным образом, результаты, получаемые над одной и той же выборкой документов, будут отличаться;
5) Алгоритм не инкрементен;
6) Кластеры не пересекаются.
Agglomerative Hierarchical Clustering - наиболее распространенный тип иерархической кластеризации, используемый для группировки объектов в кластеры на основе их сходства. Алгоритм начинается с обработки каждого объекта как одноэлементного кластера. Затем пары кластеров последовательно объединяются до тех пор, пока все кластеры не будут объединены в один большой кластер, содержащий все объекты. Результатом является древовидное представление объектов, называемое дендрограммой.
Агломерационная кластеризация работает по принципу «снизу вверх». То есть каждый объект изначально рассматривается как одноэлементный кластер. На каждом шаге алгоритма два наиболее похожих кластера объединяются в новый больший кластер (узлы). Эта процедура повторяется до тех пор, пока все точки не станут членами только одного большого кластера (корня).
Рис. 2 – Дендрограмма кластера
Проблемы алгоритма Agglomerative Clustering:
Основная проблема с иерархической кластеризацией заключается в том, что она не говорит нам, сколько существует кластеров или где разрезать дендрограмму для формирования кластеров.
util.community_detection - функция быстрого обнаружения сообщества. Находит во вложениях все сообщества, т.е. вложения близкие (ближе порога). Возвращает только сообщества, размер которых превышает min_community_size. Сообщества возвращаются в порядке убывания. Первый элемент в каждом списке является центральной точкой в сообществе.
Преимущества util. community_detection:
1) Не требует заранее указывать итоговое количество кластеров;
2) Работает быстро и точно;
3) Имеет гибкий порог и множество других параметров, которые позволяют наиболее чётко выполнить задачу кластеризации;
4) Наличие центроиды (всегда является первым элементом кластера, позволяет пополнять уже имеющиеся кластеры);
5) Ранжирование (сущности возвращаются в порядке убывания по степени близости с центроидой).
Существует еще множество алгоритмов для кластеризации текстов, но для выполнения моей задачи идеально подошел community_detection. Т.к. для меня основным требованием была возможность использование алгоритма при отсутствии заранее известного количества кластеров, а также основываясь на его, указанных выше, преимуществах, на нем и остановил свой выбор.
