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

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

• поиск оптимального числа групп;
• распределение всех объектов по найденному количеству групп.

Первую задачу точно решает алгоритм иерархической кластеризации. Работает он следующим образом:

1. Создается матрица расстояний между всеми объектами, подобная таблице расстояний между городами в автомобильных картах:

   

   Матрица расстояний

   
   

2. Запускается следующий итерационный процесс, в котором количество шагов равно числу объектов:
   1. вычисляется совокупное расстояние между объектами – полусумма всех попарных расстояний;
   2. находится минимальное расстояние в матрице. Точки, между которыми расстояние равно минимальному, схлопываются. На рисунке выше минимальное расстояние имеют точки A3 и А4. Число объектов уменьшается. При каждом шаге совокупное расстояние между объектами уменьшается, пока не станет равным 0.

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

Как работает кластеризация в Polymatica Analytics

Известная проблема иерархической кластеризации заключается в том, что при каждом шаге алгоритма (а количество шагов равно количеству объектов) нужно заново вычислять матрицу расстояний. Поэтому классический алгоритм иерархической кластеризации можно использовать только при малом числе объектов (не более 5 000).
В Polymatica Analytics этот алгоритм модифицирован так, что с его помощью можно обрабатывать десятки миллионов объектов без потери точности за разумное время (зафиксированный результат – 22 миллиона объектов с 400 характеристиками обработаны за 2,5 минуты).
Кроме того, в Polymatica Analytics запускается не один алгоритм, распределяющий объекты по группам, а три параллельных алгоритма. В итоге результат оказывается максимально объективным и верным практически для всех задач – описанные в литературе специфические распределения исходных данных (например, по периметру многомерной сферы) в бизнес-практике практически никогда не встречаются.
Таким образом, в Polymatica Analytics достигается точное распределение многомерных объектов на оптимальное количество групп с максимально возможной скоростью. Запуск различных алгоритмов настроен так, что пользователю не нужно вводить никаких параметров. Стала возможной ситуация, которой не было ни в одном продукте до Polymatica Analytics: автоматический запуск кластеризации без параметров, обеспечивающий 100%-точный результат!
Polymatica Analytics автоматически подбирает оптимальное соотношение количества кластеров и качества кластеризации. Тем не менее, при необходимости вы можете вручную выбрать наиболее удобное для вас количество кластеров. Оптимальное количество кластеров, автоматическое подобранное системой, указывается на кнопке Лучшее: