Назовите известные Вам алгоритмы агломерации
Алгоритмы агломерации:
- Метод дальнего соседа
- Метод ближнего соседа
- Метод Варда
- Центроидный метод (ищем центр тяжести)
- Метод средней связи (среднее значение всех расстояний между кластерами)
Методы кластеризации подразделяются на иерархические и неиерархические. Иерархические методы подразделяются на агломерационный и дивензивный.
Даны 4 трехмерных наблюдения. Реализуйте их кластеризацию на основе метода ближнего соседа (дальнего соседа, средней связи) и расстояния Евклида (Манхеттен, Чебышев). Постройте дендрограмму
A=(3;5;7)
B=(4;6;12)
C=(9;8;2)
D=(5;8;3)
a) Евклид+метод ближнего соседа
dabев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(3-4)2+(5-6)2+(7-12)2=√27
dacев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(3-9)2+(5-8)2+(7-2)2=√70
dadев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(3-5)2+(5-8)2+(7-3)2=√29
dbcев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(4-9)2+(6-8)2+(12-2)2=√129
dbdев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(4-5)2+(6-8)2+(12-3)2=√86
dcdев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(9-5)2+(8-8)2+(2-3)2=√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) Евклид+метод дальнего соседа
dabев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(3-4)2+(5-6)2+(7-12)2=√27
dacев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(3-9)2+(5-8)2+(7-2)2=√70
dadев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(3-5)2+(5-8)2+(7-3)2=√29
dbcев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(4-9)2+(6-8)2+(12-2)2=√129
dbdев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(4-5)2+(6-8)2+(12-3)2=√86
dcdев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(9-5)2+(8-8)2+(2-3)2=√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) Евклид+метод средней связи
dabев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(3-4)2+(5-6)2+(7-12)2=√27
dacев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(3-9)2+(5-8)2+(7-2)2=√70
dadев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(3-5)2+(5-8)2+(7-3)2=√29
dbcев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(4-9)2+(6-8)2+(12-2)2=√129
dbdев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(4-5)2+(6-8)2+(12-3)2=√86
dcdев=√ (x1(1) -x2(1))2 + (x1(2) -x2(2))2 +(x1(3) -x2(3))2 = √(9-5)2+(8-8)2+(2-3)2=√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
Для других расстояний разница только в методе расчета расстояния, а принцип объединения тот же