Методы объединения или связи

Когда каждый объект представляет собой отдельный кластер, рас­стояния между этими объектами определяются выбранной мерой. Возни­кает следующий вопрос — как определить расстояния между кластерами? Существуют различные правила, называемые методами объединения или связи для двух кластеров.

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

Метод наиболее удаленных соседей, или полная связь. Здесь расстоя­ния между кластерами определяются наибольшим расстоянием между любыми двумя объектами в различных кластерах (т.е. "наиболее удаленными соседями"). Метод хорошо использовать, когда объекты действительно происходят из различных "рощ". Если же кластеры имеют в некотором ро­де удлиненную форму или их естественный тип является «цепочечным», то этот метод не следует использовать.

Метод Варда (Ward's method): в качестве расстояния между кластера­ми берется прирост суммы квадратов расстояний объектов до центров кла­стеров, получаемый в результате их объединения (Ward, 1963). В отличие от других методов кластерного анализа для оценки расстояний между кла­стерами, здесь используются методы дисперсионного анализа. На каждом шаге алгоритма объединяются такие два кластера, которые приводят к ми­нимальному увеличению целевой функции, т.е. внутригрупповой суммы квадратов. Этот метод направлен на объединение близко расположенных кластеров и "стремится" создавать кластеры малого размера.

Метод невзвешенного попарного среднего (метод не взвешенного попарного арифметического среднего — unweighted pair-group method using arithmetic averages, UPGMA (Sneath, Sokal, 1973)).

В качестве расстояния между двумя кластерами берется среднее расстояние между всеми парами объектов в них. Этот метод следует использовать, если объекты действительно происходят из различных "рощ", в случаях присутствия кластеров «цепочного» типа, при предположении неравных размеров кластеров.

Метод взвешенного попарного среднего (метод взвешенного попарно­го арифметического среднего — weighted pair-group method using arithmetic averages, WPGM A (Sneath, Sokal, 1973)). Этот метод похож на метод невзвешенного попарного среднего, разница состоит в том, что здесь в качестве весового коэффициента используется размер кластера (число объектов, содержащихся в кластере).