Метод одиночных связей (ближайшего соседа)

В этом методе расстояние между двумя кластерами определяется расстоянием между двумя наиболее близкими объектами (ближайшими соседями) в различных кластерах. Это правило должно, в известном смысле, нанизывать объекты вместе для формирования кластеров, и результирующие кластеры имеют тенденцию быть представленными длинными "цепочками", т.е. кластеры "сцепляются" только отдельными элементами, случайно оказавшимися ближе остальных друг к другу. Главное преимущество этого метода заключается в его математических свойствах: результаты, полученные по этому методу, инвариантны к монотонным преобразованиям матрицы сходства; применению метода не мешает наличие "совпадений" в данных. Это означает, что метод одиночной связи является одним из немногих методов, результаты применения которых не изменяются при любых преобразованиях данных, оставляющих без изменения относительное упорядочение элементов матрицы сходства. Временная сложность алгоритмов кластерного анализа, использующих метод объединения по принципу ближайщего соседа обычно выражается как O(N²). Пространственная сложность выражается как O(N).

Метод полных связей (дальнего соседа)

В этом методе расстояния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. "наиболее удаленными соседями"). Этот метод обычно работает очень хорошо, когда объекты происходят на самом деле из реально различных скоплений точек в пространстве и образуют в пространстве признаков шаровидные облака. Если же кластеры имеют в некотором роде удлиненную форму или их естественный тип является "цепочечным", то этот метод непригоден. Кроме того, временная сложность алгоритмов кластерного анализа, использующих метод объединения по принципу дальнего соседа обычно выражается как O(N³), O(N⁴). Пространственная сложность выражается как O(N²).