1 Введение

Кластеризация или естественная классификация это процесс объединение в группы объектов, обладающих схожими признаками. В отличие от обычной классификации, где количество групп объектов фиксировано и заранее определено набором идеалов, здесь ни группы и ни их количество заранее не определены и формируются в процессе работы системы исходя из определённой меры близости объектов. Существует несколько основных методов разбиения групп объектов на кластеры. В данной статье описан кластеризатор на основе алгоритма k-means [1,2].

2 Постановка задачи

Рассмотрим набор точек X в n-мерном пространстве признаков

с заданной на нём метрикой ρ.

Необходимо разбить это множество на K частей или кластеров ( K < m ), объеденив близкие элементы. Кластеры можно определить с помощью особых точек-центроидов μ _i ∈ ℝ ⁿ   ;   ( i = 1 , … K ) . Точка x ^{( i )} принадлежит кластеру k если расстояние ρ до центроида k минимально.

Задача сводиться к нахождению точек-центройдов μ .

3 Решение

Для определения центройдов μ будем использовать алгоритм k-means. На первом этапе случайным образом инициализируются центройды. Далее на каждой итерации центройды сдвигаются по определённым правилам. Алгоритм выглядит следующим образом.

1. случайным образом инициализровать центройды μ
2. для каждого центройда μ _k вычислить расстояния l_k⁽ⁱ⁾ до всех точек x ^{( i )}
   l_k⁽ⁱ⁾ = ρ ( x⁽ⁱ⁾ , μ_k )
3. сформировать кластеры,

   для каждого центройда μ _k из множества X отобрать подмножество точек X _k с минимальным расстоянием до μ _k

   
4. вычислить новые центройды как среднее всех точек кластера X _k
   

   где s _k – количество точек в кластере k

5. если значения μ _k изменились (центройды сдвинулись)
   то переход на п. 2
   иначе конец работы

Результат работы этого алгоритма сильно зависит от начальной инициализации цетройдов.

 
 

Рассмотрим функцию оценки Q качества работы кластеризатора.

Q= c ^. d_i / d_o

где

c – количество кластеров;
d_i – среднее внутрикластерное расстояние;
d_o – среднее межкластерное расстояние;

Для получения наилучшего результата можно несколько раз выполнить алгоритм кластеризации, после чего выбрать результат с наименьшим значением Q .

 
 

Рис. 1: начальное состояние

Рис. 2: результат кластеризации Q=0.22

 
 

Рис. 3: начальное состояние

Рис. 4: результат кластеризации Q=0.36

 
 

Реализация в системе Octave [  здесь  ].

 
 

Список литературы

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