Назовите известные Вам алгоритмы агломерации

Алгоритмы агломерации:

- Метод дальнего соседа

- Метод ближнего соседа

- Метод Варда

- Центроидный метод (ищем центр тяжести)

- Метод средней связи (среднее значение всех расстояний между кластерами)

Методы кластеризации подразделяются на иерархические и неиерархические. Иерархические методы подразделяются на агломерационный и дивензивный.

Даны 4 трехмерных наблюдения. Реализуйте их кластеризацию на основе метода ближнего соседа (дальнего соседа, средней связи) и расстояния Евклида (Манхеттен, Чебышев). Постройте дендрограмму

A=(3;5;7)

B=(4;6;12)

C=(9;8;2)

D=(5;8;3)

 

a) Евклид+метод ближнего соседа

 

d_ab^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(3-4)²+(5-6)²+(7-12)²=√27

d_ac^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(3-9)²+(5-8)²+(7-2)²=√70

d_ad^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(3-5)²+(5-8)²+(7-3)²=√29

d_bc^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(4-9)²+(6-8)²+(12-2)²=√129

d_bd^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(4-5)²+(6-8)²+(12-3)²=√86

d_cd^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(9-5)²+(8-8)²+(2-3)²=√17

 

 

	A	B	C	D
A		√27	√70	√29
B			√129	√86
C				√17
D

 

 

Выбираем самое маленькое расстояние (√17) и объединяем два наблюдения(C и D). Получаем новую матрицу (в качеств расстояния в новой матрице между наблюдением и группой выбираем наименьшее: для A сравниваем √70 и √29, для B √129 и √86)

 

	A	B	CD
A		√27	√29
B			√86
CD

 

 

Опять выбираем самое маленькое расстояние (√27) и объединяем два наблюдения(A и B). Получаем новую матрицу (в качеств расстояния в новой матрице между группами выбираем наименьшее: сравниваем √29 и √86)

 

	AB	CD
AB		√29
CD

 

 

Получаем два кластера AB и CD

Дендрограма: (наблюдения идут abcd)

 

a

 

b

c

 

d

 

b) Евклид+метод дальнего соседа

 

d_ab^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(3-4)²+(5-6)²+(7-12)²=√27

d_ac^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(3-9)²+(5-8)²+(7-2)²=√70

d_ad^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(3-5)²+(5-8)²+(7-3)²=√29

d_bc^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(4-9)²+(6-8)²+(12-2)²=√129

d_bd^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(4-5)²+(6-8)²+(12-3)²=√86

d_cd^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(9-5)²+(8-8)²+(2-3)²=√17

 

 

	A	B	C	D
A		√27	√70	√29
B			√129	√86
C				√17
D

 

 

Выбираем самое маленькое расстояние (√17) и объединяем два наблюдения(C и D). Получаем новую матрицу (в качеств расстояния в новой матрице между наблюдением и группой выбираем наибольшее: для A сравниваем √70 и √29, для B √129 и √86)

 

	A	B	CD
A		√27	√70
B			√129
CD

 

 

Опять выбираем самое маленькое расстояние (√27) и объединяем два наблюдения(A и B). Получаем новую матрицу (в качеств расстояния в новой матрице между группами выбираем наибольшее: сравниваем √70 и √129)

 

	AB	CD
AB		√129
CD

 

 

Получаем два кластера AB и CD

 

c) Евклид+метод средней связи

 

d_ab^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(3-4)²+(5-6)²+(7-12)²=√27

d_ac^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(3-9)²+(5-8)²+(7-2)²=√70

d_ad^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(3-5)²+(5-8)²+(7-3)²=√29

d_bc^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(4-9)²+(6-8)²+(12-2)²=√129

d_bd^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(4-5)²+(6-8)²+(12-3)²=√86

d_cd^ев=√ (x₁⁽¹⁾ -x₂⁽¹⁾)² + (x₁⁽²⁾ -x₂⁽²⁾)² +(x₁⁽³⁾ -x₂⁽³⁾)² = √(9-5)²+(8-8)²+(2-3)²=√17

 

 

	A	B	C	D
A		√27	√70	√29
B			√129	√86
C				√17
D

 

 

Выбираем самое маленькое расстояние (√17) и объединяем два наблюдения(C и D). Получаем новую матрицу (в качеств расстояния в новой матрице между наблюдением и группой берется среднее значение всех расстояний, измеренных между объектами двух кластеров)

 

	A	B	CD
A		√27	(√70+√29)/2=√47.3
B			(√129+√86)/2=√106.414
CD

 

 

Опять выбираем самое маленькое расстояние (√27) и объединяем два наблюдения(A и B). Получаем новую матрицу (в качеств расстояния в новой матрице между группами берется среднее значение всех расстояний, измеренных между объектами двух кластеров)

 

	AB	CD
AB		(√70+√29+√129+√86)/4
CD

 

 

Получаем два кластера AB и CD

Для других расстояний разница только в методе расчета расстояния, а принцип объединения тот же