Алгоритм кластеризації з використанням критерію

«ближнього сусіда»

Алгоритм агломераційної виду, який стирає рядки і стовпці в безпосередній матриці, і старі кластери формують нові.

Задана матриця розміром N*N. Вона межує з D = [d(i, j)].

Кластерам присвоюється порядковий номер 0, 1,..., (n-1) і L(k)- рівень k-ї кластерів. Кластери з порядковим номером m позначаються як (m) і зближаються з кластерами (r) і (s), які позначаються як d [(r), (s)]

Алгоритм складається з наступних кроків:

1. Почніть з непересічених кластерів, які мають рівень L (0) = 0 і порядковий номер m = 0;

2. Знайдіть найменш різнорідні (різних за складом) пари кластерів серед поточних кластерів, скажемо пару (r), (s), відповідно до

d[(r), (s)] = min d[(i), (j)],

де мінімум знаходиться по всім парам кластерів в поточній кластеризації;

3. Збільшуємо порядковий номер (інкрементуємо): m = m +1. Сортуємо кластери (r) і (s) в єдиний кластер, який утворює кластер m;

Встановлюємо рівень кластеризації відповідно за формулою:

L(m) = d[(r), (s)];

4. Оновлюємо матрицю, D, викреслюючи рядки і стовпці, відповідних кластерів (r) і (s) і додаємо рядки і стовпці, відповідних новостворених кластерів. Близькість між новим кластером, позначається (R, S) і старий кластер (k) визначається наступним чином: d[(k), (r, s)] = min d[(k), (r)], d[(k), (s)];

5. Якщо всі об'єкти знаходяться в одному кластері, зупиняємось. В іншому випадку, переходимо до кроку 2.

Кластеризація методами одиночного і повного зв'язку(ближнього і далекого сусіда)

В кластеризації методом одиночного зв'язку (single-link clustering, single-linkage clustering) схожістю двох кластерів є схожість між їх найбільш схожими елементами. Критерій об'єднання в методі одиночного зв'язку носить локальний характер. У цьому алгоритмі увага приділяється виключно області, в якій два кластери найбільш близькі один до одного. Інші, більш віддалені, частини кластера і його структура не враховується

У кластеризації методом повного зв'язку (complete-link clustering, complete-linkage clustering) схожістю двох кластерів є схожість між їх найбільш несхожими елементами. Це еквівалентно вибору пари кластерів, об'єднання яких має найменший діаметр. Критерій об'єднання в методі повного зв'язку носить нелокальний характер: рішення про об'єднання кластерів може впливати вся структура кластеризації. Це приводить до переважання компактних кластерів з маленькими діаметрами над довгими розтягнутими кластерами, але одночасно підвищує чутливість до викидів. Окремий документ, що знаходиться далеко від центру, може різко збільшити діаметр можливого об'єднання і повністю змінити остаточне розбиття.

Рис. 10. Кластеризація восьми документів методами одиночної зв'язку (ліворуч) і повною зв'язку (праворуч). Еліпси відповідають послідовним етапам кластеризації. Зліва: схожість на основі одиночної зв'язку між двома двоточковими кластерами вгорі дорівнює показнику подібності між документами d₂ і d₃ (суцільна лінія), яке перевищує схожість на основі одиночної зв'язку між двоточковими кластерами зліва (пунктирна лінія). Праворуч: схожість на основі повної зв'язку двох двоточкових кластерів вгорі дорівнює показнику подібності між документами d₁ і d₄ (пунктирна лінія), яка менше, ніж подібність на основі повної зв'язки між двома лівими двоточковими кластерами (суцільна лінія)

На рис. 10 продемонстрований процес кластеризації восьми документів методами одиночного і повного зв'язку. На перших етапах обидва методи формують по чотири ідентичні кластери, кожен з двох документів. Потім алгоритм методу одиночного зв'язку об'єднує верхні дві пари (а після — і нижні). Оскільки як міра схожості в даному алгоритмі використовується максимальна схожість між елементами, ці кластери вважаються найближчими. Алгоритм методу повного зв'язку об'єднує дві ліві пари (а потім і дві праві), оскільки ці пари ближче один до одного відповідно до визначення схожості кластерів як мінімальної схожості їх елементів. Приклад кластеризації за допомогою методу повного зв'язку — на рис. 11. Провівши відсікання останнього об'єднання на рис. 6, ми отримаємо два кластери однакового розміру (документи 1-16 від NYSE closing averages до Lloyds chief / U.S. grillingі документи 17-30 від Ohio Blue Cross до Clinton signs law). На рис. 3 не існує такого перетину дендрограми, яке приводило до розбиття на кластери приблизно однакового розміру.

Як кластеризацію методом одиночного зв'язку, так і кластеризацію методом повного зв'язку можна інтерпретувати за допомогою теорії графів. Хай s_k комбінаційна міра схожості між двома кластерами, об'єднаними наетапі k, а G(s_k) — граф, що зв'язує всі крапки, схожість між якими не менша, ніж s_k. Тоді кластери після етапу k в процесі кластеризації методом одиночного зв'язку є зв'язними компоненти графа G(s_k), а кластери після етапу k в процесі кластеризації методом повного зв'язку є максимальними кліками (cliques) графа G(s_k). Компонент зв’язності (connected component) — це максимальна множина вершин, сполучених між собою так, що для кожної пари існує ребро, що сполучає їх. Клік (clique) — це множина крапок, які створюють повний граф (тобто будь-які дві суміжні крапки).

Рис. 11. Дендрограма кластеризації за методом повної зв'язку.

Ці інтерпретації пояснюють назви методів: одиночного зв'язку і повного зв'язку. Кластери, отримані методом одиночного зв'язку на етапі k, — це максимальна множина крапок, між якими існує хоч би один зв'язок по схожості: s ≥ s_k. Кластери, отримані методом повного зв'язку на етапі k, — це максимальна множина крапок, в кожної з яких є зв'язок у міру схожості зі всіма іншими: s ≥ s_k.

Алгоритми кластеризації методами одиночного і повного зв'язку зводять завдання оцінки якості кластера до оцінки міри схожості між двома документами: двома найбільш схожими документами в алгоритмі методу одиночного зв'язку і двома найбільш несхожими документами в алгоритмі методу повного зв'язку. Оцінки схожості між двома документами не відображають властивості розподілу документів в кластері. З цієї причини не дивно, що обидва алгоритми часто породжують небажані кластери.

Кластеризація методом одиночного зв'язку може створити розкидані кластери, як показано на рис. 11. Оскільки критерій об'єднання в цьому алгоритмі носить строго локальний характер, ланцюжок пар може розтягнутися на велику відстань без врахування форми виникаючого кластера. Цей ефект називається зчепленням (chaining).

Останні одинадцять об’єднань в алгоритмі кластеризації методом одиночного зв'язку (що знаходяться над лінією d = 0, 1), які добавляють одиничний документ, або пару документів, утворюють ланцюжок. Кластеризація методом повного зв'язку, продемонстрована на рис. 11, дозволяє уникнути цього ефекту. Коли дендрограма розтинається на етапі останнього об'єднання, документи розділяються на дві групи приблизно однакового об'єму. Загалом, це корисніша організація даних ніж зчеплені кластери.

Проте кластеризація методом повного зв'язку має інший недолік. Вона надає велику вагу викидам, тобто крапкам, що не вписуються в загальну структуру кластера. У прикладі, показаному на рис. 12, чотири документи, d2, d3, d4, d5 не попали в один кластер із-за викиду d1. Кластеризація методом повного зв'язку в даному випадку не здатна створити найбільш природну структуру кластерів.

Рис. 12. Зчеплення, що виникає при кластеризації методом одиночної зв'язку. Локальний критерій у кластеризації методом одиночної зв'язку може породити не бажано витягнуті кластери

Рис.13. Викиди в кластеризації методом повної зв'язку. П'ять документів мають координати х, рівні 1 +2 е 4, 5 +2 е, 6 і 7е. Кластеризація методом повної зв'язку створює два кластери, показаних як еліпси. Найбільш правильним з інтуїтивною точки зору було б розбиття {{d1}, {d2, d3, d4, d5}}, але при кластеризації методом повної зв'язку викид d1 розбиває майстер {d2, d3, d4, d5} так; як показано на малюнку