Как работает полная кластеризация ссылок и как нарисовать дендрограмму.
Иерархическая кластеризация: ее медленный :: сложный :: повторяемый :: не подходит для больших наборов данных.
Возьмем 6 простых векторов.
Использование евклидова расстояния позволяет вычислить матрицу расстояний. Euclidean Distance = sqrt( (x2 -x1)**2 + (y2-y1)**2 )
Пример: расстояние между точками A и B
sqrt ((18–22) ** 2 + (0–0) ** 2))
sqrt ((16) + 0)
sqrt ( 16) = 4
Полная кластеризация ссылок: учитывает максимальное значение всех расстояний. Приводит к множеству небольших скоплений.
Матрица расстояний: диагонали будут равны 0, а значения будут симметричными.
Шаг a: кратчайшее расстояние в матрице - 1, а векторами, связанными с ним, являются C и D.
Итак, первый кластер - это C - D
Расстояние между другими векторами и CD
От A до CD = max (A- ›C, A-› D) = max (25,24) = 25
B до CD = max (B- ‹C, B-› D) = max (21, 20) = 21
и аналогично найти для E - ›CD & F -› CD
Шаг b. Теперь 2 - это кратчайшее расстояние, и векторы, связанные с ним, - E и F.
Второй кластер - E - F
От A до EF = max (A- ›E, A-› F) = max (9,7) = 9
от CD до EF = max (CD- ›E, CD-› F) = max (15, 17) = 17
Шаг c. Теперь 4 - это кратчайшее расстояние, и связаны векторы A и B.
Третий кластер - A - B
От CD до AB = max (CD - ›A, CD -› B) = max (25,21) = 25
EF до AB = max (EF - ›A, EF -› B) = max (9, 5) = 9
Шаг d. Теперь 9 - это кратчайшее расстояние, и связаны векторы AB и EF.
Четвертый кластер - AB - EF
CD в ABEF = макс (CD- ›AB, CD-› EF) = макс (25,18) = 25
Шаг e: последний кластер - CD - ABEF
Давайте посмотрим на дендрограмму, чтобы увидеть полный кластер ссылок.
Простой скрипт Python 3 для достижения того же.
import numpy as np from scipy.cluster.hierarchy import dendrogram, linkage from scipy.spatial.distance import squareform import matplotlib.pyplot as plt mat = np.array([[0,4,25,24,9,7], [4,0,21,20,5,3], [25,21,0,1,16,18], [24,20,1,0,15,17], [9,5,16,15,0,2], [7,3,18,17,2,0] ]) dists = squareform(mat) linkage_matrix = linkage(dists, "complete") dendrogram(linkage_matrix, labels=["A","B","C","D","E","F"]) plt.title("Complete Link") plt.show()