'єкти як «різні», якщо вони розрізняються з якої-небудь одній координаті (яким одним виміром). Відстань Чебишева обчислюється за формулою: відстань
(x, y)=Максимум | xi - yi |
ступеня відстані
Іноді бажають прогресивно збільшити або зменшити вагу, що відноситься до розмірності, для якої відповідні об'єкти сильно відрізняються. Це може бути досягнуто з використанням статечного відстані. Ступовий відстань обчислюється за формулою: відстань
(x, y)=(i | xi - yi | p) 1 / r
де r і p - параметри, які визначаються користувачем. Кілька прикладів обчислень можуть показати, як «працює» ця міра. Параметр p відповідальний за поступове зважування різниць по окремих координатах, параметр r відповідальний за прогресивне зважування великих відстаней між об'єктами. Якщо обидва параметри - r і p, рівні двом, то це відстань збігається з відстанню Евкліда.
Правила об'єднання або зв'язку:
На першому кроці, коли кожен об'єкт являє собою окремий кластер, відстані між цими об'єктами визначаються обраної заходом. Однак коли зв'язуються разом кілька об'єктів, виникає питання, як слід визначити відстані між кластерами? Іншими словами, необхідно правило об'єднання або зв'язку для двох кластерів. Тут є різні можливості: наприклад, ви можете пов'язати два кластери разом, коли будь-які два об'єкти в двох кластерах ближче один до одного, ніж відповідну відстань зв'язку. Іншими словами, ви використовуєте «правило найближчого сусіда» для визначення відстані між кластерами; цей метод називається методом одиночній зв'язку. Це правило будує «волокнисті» кластери, тобто кластери, «зчеплені разом» тільки окремими елементами, випадково опинилися ближче інших один до одного. Як альтернативу ви можете використовувати сусідів у кластерах, які знаходяться далі всіх інших пар об'єктів один від одного. Цей метод називається метод повного зв'язку. Існує також безліч інших методів об'єднання кластерів, подібних тим, що були розглянуті.
Одиночна зв'язок (метод найближчого сусіда)
Як було описано вище, в цьому методі відстань між двома кластерами визначається відстанню між двома найбільш близькими об'єктами (найближчими сусідами) в різних кластерах. Це правило повинне, у відомому сенсі, нанизувати об'єкти разом для формування кластерів, і результуючі кластери мають тенденцію бути представленими довгими «ланцюжками».
Повна зв'язок (метод найбільш віддалених сусідів)
У цьому методі відстані між кластерами визначаються найбільшою відстанню між будь-якими двома об'єктами в різних кластерах (тобто «найбільш віддаленими сусідами»). Цей метод зазвичай працює дуже добре, коли об'єкти відбуваються насправді з реально різних «гаїв». Якщо ж кластери мають в деякому роді подовжену форму або їх природний тип є «цепочечную», то цей метод непридатний.
невиважені попарне середнє
У цьому методі відстань між двома різними кластерами обчислюється як середня відстань між усіма парами об'єктів в них. Метод ефективний, коли об'єкти в дійсності формують різні «гаю», проте він працює однаково добре і у випадках протяжних («цепочного» типу) кластерів.
Виважена попарне середнє
