Метод полной связи

Метод полной связи (англ. Complete-linkage clustering) — один из алгоритмов иерархической кластеризации.

Исходно каждый элемент выборки считается отдельным кластером. После чего кластеры последовательно объединяются, пока все элементы не попадут в один кластер. На каждом шаге алгоритма объединяются два кластера, расстояние между которыми минимальное. Формализация понятия «минимальное расстояние» может зависеть от модификаций алгоритма, в методе полной связи минимальное расстояние определяется как максимум из множества расстояний между элементом первого кластера и элементом второго кластера. То есть, расстояние $\text{[math]}$ $\text{[math]}$ $D(X,Y)$ $D(X,Y)$ между кластерами $\text{[math]}$ $\text{[math]}$ $X$ $X$ и $\text{[math]}$ $\text{[math]}$ $Y$ $Y$ считается по формуле:

\text{[math]}

D(X,Y)=\max _{x\in X,y\in Y}d(x,y)

D(X,Y)=\max _{x\in X,y\in Y}d(x,y)

,

где $\text{[math]}$ $\text{[math]}$ $d(x,y)$ $d(x,y)$ — расстояние между $\text{[math]}$ $\text{[math]}$ $x\in X$ $x\in X$ и $\text{[math]}$ $\text{[math]}$ $y\in Y$ $y\in Y$ ; $\text{[math]}$ $\text{[math]}$ $X$ $X$ и $\text{[math]}$ $\text{[math]}$ $Y$ $Y$ — различные кластеры.

ПримечанияПравить

СсылкиПравить

H. Späth. Cluster Analysis Algorithms. — Chichester: Ellis Horwood, 1980.