Определение предпочтительного числа кластеров. Момент остановки метода одиночной связи



Кластерный анализ является одним из основных методов предварительной классификации большого количества информации. Актуальной задачей остаётся определение момента остановки процесса кластеризации. Можно рассмотреть кластерный анализ данных методом «одиночной связи» в виде дискретного случайного процесса и определить момент остановки с помощью квадратичных форм погрешности приближения «минимальных расстояний» функцией. В статье даётся определение «аппроксимационно-оценочным критериям». Применён один из критериев для кластеризации множества из 33 точек.

Ключевые слова: кластер, метод одиночной связи, аппроксимация, квадратичная форма, кластерный анализ.

Метод одиночной связи

Метод одиночной связи — иерархический агломеративный алгоритм, который выполняется в двумерном евклидовом пространстве со стандартной метрикой. За кластер мы берём центроиду всех точек, входящих в кластер, то есть изначально каждая точка является отдельным кластером, затем при увеличении кластера — средним арифметическим координат всех точек, входящих в кластер.

Итерации алгоритма можно описать следующим образом: на первом шаге необходимо определить расстояния между всеми n кластерами, построить множество минимальных расстояний, затем найти минимальное. Два кластера, расстояние между которыми минимально, объединяются, их центроида перевычисляется, получаем n-1 кластер [2]. Без остановки алгоритм в конечном итоге объединит все точки в один кластер, что является неудовлетворительным результатом.

Остановка процесса кластеризации

Множество минимальных расстояний является монотонно неубывающим, и при объединении больших кластеров испытывает «скачок». Например, для множества из 33 точек [2]

X={(0; 0); (2; 4); (3; 3); (1; 2); (3; 0); (3; 1); (1; 1); (12; 18); (13; 17); (11; 15); (13; 14); (14; 16); (11; 16); (12; 15); (13; 18); (12; 5); (13; 2); (14; 4); (12; 3); (13; 1); (14; 2); (24; 19); (22; 22); (21; 24); (23; 21); (24; 20); (22; 39); (23; 38); (24; 39); (21; 37); (2; 26); (24; 6); (10; 36)} график множества минимальных расстояний указан на рис.1.

Рис. 1. Множество минимальных расстояний. На оси абсцисс указаны номера итераций, на оси ординат — расстояние между кластерами

Для того чтобы избежать проблемы объединения точек в один большой кластер, необходимо ввести критерий остановки. Будем приближать множество минимальных расстояний функцией для того, чтобы зафиксировать скачок (объединение кластеров). Хорошие результаты даёт приближение не всех точек сразу, а последовательно по 3 или 4 точкам. «Аппроксимационно-оценочные критерии» [1] являются квадратичными формами, оценивающими разность между квадратичной погрешностью линейной аппроксимации и квадратичной погрешностью одного из видов нелинейной аппроксимации (например, биквадратной — четвёртой степени). С вычислением критериев можно ознакомиться в работе [1]. Биквадратный аппроксимационно-оценочный критерий по четырём точкам имеет вид:

Здесь три переменные, но точек четыре. Это связано с введением упрощения: — первая точка, по которой проводится аппроксимация, — вторая, — третья, — четвёртая; мы обнуляем первую точку и от значений остальных отнимаем — по сути, мы переносим начало координат в

. Подставляем вычисленные минимальные расстояния и считаем квадратичную форму — получаем число. Если это число больше нуля, то процесс кластеризации следует остановить, если меньше нуля — то следует продолжить. Данная квадратичная форма — разность погрешности аппроксимации линейной и биквадратной функциями по четырём точкам, и если линейная точнее, то вычисленное значение будет отрицательным. Это означает отсутствие скачка. Если приближение биквадратной функцией точнее, то функция испытывает скачок, и значение становится положительным. [1]

Результаты использования

Чувствительность критерия можно задать с помощью коэффициента q при линейном преобразовании , где i — номер итерации, — значение минимального расстояния на i итерации, q — чувствительность критерия.

Для рассмотренного множества Х данный способ показывает хорошие результаты — при q от 0.18 до 0.63 процесс кластеризации методом одиночной связи заканчивается после 25 итерации (рис.2)

Рис. 2. Множество Х, разбитое на кластеры, после 25 итерации. Начало координат находится в левом верхнем углу

Выводы

Необходимо отметить, что рассмотренный критерий не единственный — можно вычислить экспоненциальный, квадратичный, кубический критерии. Они достаточно просты в использовании (но иногда сложны в вычислении), показывают хорошие и устойчивые результаты.

Литература:

1. Орехов А. В. Аппроксимационно-оценочные критерии напряженно-деформируемого состояния твердого тела // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2018. Т. 14. Вып. 3. С. 230–242. https://doi.org/10.21638/11702/spbu10.2018.304
2. Орехов А. В. Марковский момент остановки агломеративного процесса кластеризации в евклидовом пространстве // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. 2019. Т. 15. Вып. 1. С. 00–00.