[ на главную ] 

Метод иерархической кластеризации.

Евгений Борисов

среда, 5 февраля 2014 г.


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

В этой статье мы рассмотрим методы анализа данных, которые называются иерархической кластеризацией. Общая идея этих методов - последовательное объединение наиболее близких к друг другу групп объектов разбитое на несколько шагов. Таким образом в результате мы получаем историю объединений групп в виде дерева, которое называется дендрограммой.

1 Введение

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

n ρ(x, y) = ∑ (xi − yi)2 i=1
(1)

Для реализации метода иерархической кластеризации нам понадобиться способ оценивать расстояния между множествами точек. Есть разные варианты:

и другие способы.

Будем использовать расстояние Уорда [1] для определения расстояния между множествами точек W и S

( ∑ ∑ ) Rward(W, S) = |W-| ⋅ |S-|-⋅ ρ -w--, -s- |W | + |S| w∈W |W | s∈S |S |

и формулу Ланса-Уильямса[1] для определения расстояния между объединением множеств точек W = U ∪ V и множеством точек S

Rlnwl(U ∪ V, S) = αU ⋅ Rward(U, S) + αV ⋅ Rward (V, S) + β ⋅ Rward (U, V )
(2)

где

|U | + |S| |V | + |S| − |S | αU = ----------; αV = ----------; β = ---------- |W | + |S | |W | + |S | |W | + |S|

2 Описание алгоритма

Базовый алгоритм иерархической кластеризации выглядит следующим образом.

  1. инициализировать множество кластеров одноэлементными кластерами
    C := {x },{x },...,{x } 1 2 m
  2. рассчитать начальную матрицу расстояний R по (1)
  3. найти пары кластеров P из C c наименьшими расстояниями R друг до друга
  4. объединить во множестве кластеров C найденные пары близких кластеров P
  5. рассчитать новую матрицу расстояний R по (2)
  6. если количество кластеров |C| > 1
    то переход на п.3
  7. конец

Для регулирования глубины дендрограммы (дерева истории объединений кластеров) и улучшения результатов кластеризации можно ввести порог расстояний δ. Алгоритм модифицируется следующим образом.

  1. инициализировать множество кластеров одноэлементными кластерами
    C := {x1 },{x2},...,{xm }
    и значение порога d := δ
  2. рассчитать начальную матрицу расстояний R по (1)
  3. найти пары кластеров P из C c расстояниями R < d друг до друга
  4. если пары не найдены |P| < 1
    то увеличить порог d := min(R) + δ и переход на п.3
  5. объединить во множестве кластеров C найденные пары близких кластеров P
  6. рассчитать новую матрицу расстояний R по (2)
  7. если количество кластеров |C| > 1
    то переход на п.3
  8. конец

 
 

 

3 Реализация

В этом примере был обработан набор из 360 точек, количество слоёв дендрограммы равно 67. На рисунках ниже приведены часть дендрограммы и соответствующие ей промежуточные результаты работы иерархического кластеризатора.

 

 
Рис.1: верхушка дерева дендрограммы  
 
Рис.2: результат кластеризации - 5 кластеров Рис.3: результат кластеризации - 4 кластера
 
Рис.4: результат кластеризации - 3 кластера Рис.5: результат кластеризации - 2 кластера

 
 

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

 
 

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

[2]    Воронцов К.В. Методы кластеризации – http://shad.yandex.ru/lectures/machine_learning.xml

[3]    GNU Octave – http://www.gnu.org/software/octave/

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