4.1 Класифікація кластер-процедур. Ієрархічні агломеративні й ітеративні кластер-процедури

Об’єднання схожих об’єктів у групи може бути здійснене різними способами. Виділяють певні групи методів кластерного аналізу (рис. 4.1):

Рис. 4.1: Групи методів кластерного аналізу

Класифікація методів кластерного аналізу

1. За способом обробки даних:
   • ієрархічні (агломеративні, дивізимні);
   • неієрархічні.
2. За способом аналізу даних:
   • чіткі;
   • нечіткі.
3. За кількістю застосування алгоритмів кластеризації:
   • з одноетапною кластеризацією;
   • з багатоетапною кластеризацією.
4. За можливістю розширення обсягу оброблюваних даних:
   • масштабовані;
   • немасштабовані.
5. За часом виконання кластеризації:
   • потокові (on-line);
   • не потокові (off-line).

Розглянемо особливості різних методів кластеризації (рис. 4.2):

Рис. 4.2: Особливості ієрархічних методів кластерного аналізу

Найбільш поширеними є ієрархічні методи, серед яких розрізняють агломеративний і дивізимний методи.

Головна ідея агломеративного методу:

на першому кроці кожен об’єкт вважається окремим кластером. Два найбільш близьких об’єкти об’єднуються, і утворюється новий кластер. Процедура триває, доки всі об’єкти не будуть об’єднані в один кластер.

Головна ідея дивізимного методу:

спочатку всі об’єкти належать одному кластеру. Від цього кластера відокремлюються групи схожих між собою об’єктів. Так, на кожному кроці кількість кластерів зростає, а міра відстані між класами зменшується.

Візуалізація кластерної структури наведена на рис. 4.3:

Рис. 4.3: Візуалізація кластерної структури у застосуванні ієрархічних методів

Алгоритм агломеративної ієрархічної кластеризації:

1. Нормування вихідних даних.
2. Розрахунок матриці відстаней або матриці мір подібності.
3. Знаходиться пара найближчих кластерів. За обраним алгоритмом ці два кластери об’єднуються. Новому кластеру присвоюється менший з номерів об’єднуваних кластерів.
4. Кроки 2, 3 і 4 повторюються, поки всі об’єкти не будуть об’єднані в один кластер або до досягнення заданого «порогу» подібності.

Алгоритм дивізимної ієрархічної кластеризації:

1. Нормування вихідних даних.
2. Розрахунок матриці відстаней або матриці мір подібності.
3. Знаходиться пара найвіддаленіших об’єктів \(ni\), \(nj\).
4. Оцінюється відстань об’єктів, що залишилися, до виділених об’єктів \(ni\) та \(nj\) і визначається до якого з них вони ближче знаходяться.
5. Близькі об’єкти об’єднуються в кластер. Так, початковий єдиний кластер розбивається на два.
6. Кроки 3, 4 і 5 повторюються, поки всі об’єкти не будуть розділені на кластери.

Дивізимний алгоритм не вимагає перерахунку матриці відстаней на кожному кроці класифікації на відміну від агломеративного, що сприяє зниженню трудомісткості розрахунків.

Методи групування

Метод «найближчого сусіда» / одиничного зв’язку

Ступінь подібності оцінюється за ступенем подібності між найбільш схожими (найближчими) об’єктами цих кластерів (рис. 4.4).

Рис. 4.4: Графічне зображення методу «найближчого сусіда»

Метод «дальнього сусіда» / повного зв’язку

Ступінь подібності оцінюється за ступенем подібності між найбільш віддаленими (несхожими) об’єктами цих кластерів (рис. 4.5).

Рис. 4.5: Графічне зображення методу «дальнього сусіда»

Метод середнього зв’язку

Ступінь подібності оцінюється як середня величина ступенів подібності між об’єктами кластерів (рис. 4.6).

Рис. 4.6: Графічне зображення методу середнього зв’язку

Метод медіанного зв’язку

Відстань визначається як відстань від центру будь-якого кластера \(S\) до середини відрізка, що з’єднує центри нового кластера, який об’єднав об’єкти \(p\) і \(q\) (рис. 4.7).

Рис. 4.7: Графічне зображення методу медіанного зв’язку

Відстань між кластерами розраховується за формулою Ланса-Уїльямса:

\[ d_{US}=α_p d_{ps}+α_q d_{qs}+βd_{pq}+γ\,|d_{ps}-d_{qs}|. \tag{4.1} \]

Значення параметрів формули для різних методів групування подані в табл. 2.1.

Табл. 2.1: Значення параметрів для формули Ланса-Уільямса

Методи	Параметри
Найближчого сусіда	\(α_p=α_q=0,5\); \(β=0\); \(γ=-0,5\)
Дальнього сусіда	\(α_p=α_q=0,5\); \(β=0\); \(γ=-0,5\)
Середнього зв’язку	\(α_p=\frac{n_p}{n_p+n_q}\); \(α_p=\frac{n_q}{n_p+n_q}\); \(β=γ=0\)
Центроїдний	\(α_p=\frac{n_p}{n_p+n_q}\); \(α_p=\frac{n_q}{n_p+n_q}\); \(β=-\frac{n_p}{n_p+n_q}\cdot\frac{n_q}{n_p+n_q}\)
Медіанного зв’язку	\(α_p=α_q=0,5\); \(β=-0,25\); \(γ=0\)

Приклад 4.1. Метод «найближчого сусіда» (одиничного зв’язку)

Вхідні дані: аналізуються чотири об’єкти, які характеризуються двома показниками \(X_{i1},X_{i2}\) (табл. 2.2).

Табл. 2.2: Вхідні дані

Ознака	Об’єкт 1	Об’єкт 2	Об’єкт 3	Об’єкт 4
\(x_{i1}\)	5	6	5	10
\(x_{i2}\)	10	12	13	9

Розраховуємо матрицю відстаней між об’єктами за формулою 4.1 (табл. 2.3).

Табл. 2.3: Матриця відстаней \(D1\)

№ об’єкта	1	2	3	4
1	0	2,24	3,00	5,10
2	2,24	0	1,41	5,00
3	3,00	1,41	0	6,40
4	5,10	5,00	6,40	0

Знаходимо мінімальну відстань між об’єктами \(d_{23}=1,41\). Отже, необхідно об’єднати об’єкти 2 і 3 в один кластер, обираючи в якості нової відстані мінімальну між кластерами, що об’єднуються \(\min⁡(2,24;3,00)=2,24\) і т.д. Перераховуємо матрицю відстаней (табл 2.4).

Табл. 2.4: Матриця відстаней за методом «найближчого сусіда» \(D2\)

№ об’єкта	1	2, 3	3
1	0	2,24	5,10
2,3	2,24	0	5,00
4	5,10	5,00	0

Аналогічно знаходимо мінімальну відстань між об’єктами \(d_{1(23)}=2,24\). Отже, необхідно об’єднати об’єкти 1 і (2, 3) в один кластер, обираючи в якості нової відстані мінімальну між кластерами, що об’єднуються: \(\min⁡(5,10; \, 5,00)=5,00\). Перераховуємо матрицю відстаней (табл 2.5).

Табл. 2.5: Матриця відстаней за методом «найближчого сусіда» \(D3\)

№ об’єкта	1, 2, 3	4
1, 2, 3	0	5,00
4	5,00	0

Дендрограма класифікації методом «найближчого сусіда» наведена на рис. 4.8.

Рис. 4.8: Дендрограма класифікації методом «найближчого сусіда»

Приклад 4.2. Дивізимна кластеризація

Вхідні дані: аналізуються вісім об’єктів, які характеризуються двома показниками \(X_{i1},X_{i2}\) (табл. 3.1).

Табл. 3.1: Вхідні дані

№ об’єкта	1	2	3	4	5	6	7	8
\(x_{i1}\)	0,98	1,24	-1,12	0,12	0,39	-1,35	-0,91	0,66
\(x_{i2}\)	-0,35	0,21	-0,76	0,69	2,11	-0,32	-0,69	-0,88

Розраховуємо матрицю відстаней між об’єктами за формулою 4.1 (табл. 3.2).

Знаходимо максимальну відстань між об’єктами, це буде відстань між третім і п’ятим об’єктами \(d_{35}=2,54\).

Оцінимо відстані до третього та п’ятого об’єктів від усіх інших, що залишилися:

• \(d13 < d15\) — об’єкт \(n_1\) ближче до \(n_3\);
• \(d23 < d25\) — об’єкт \(n_2\) ближче до \(n_3\);
• \(d43 > d45\) — об’єкт \(n_4\) ближче до \(n_5\);
• \(d63 < d65\) — об’єкт \(n_6\) ближче до \(n_3\);
• \(d73 < d75\) — об’єкт \(n_7\) ближче до \(n_3\);
• \(d83 < d85\) — об’єкт \(n_8\) ближче до \(n_3\).

Табл. 3.2: Матриця відстаней \(D1\)

№ об’єкта	1	2	3	4	5	6	7	8
1	0	0,49	1,20	0,99	2,08	1,28	1,07	0,48
2	0,49	0	1,53	0,74	1,66	1,49	1,40	0,97
3	1,20	1,53	0	1,39	2,54	0,39	0,13	0,98
4	0,99	0,74	1,39	0	1,2	1,17	1,29	1,35
5	2,08	1,66	2,54	1,2	0	2,25	2,45	2,50
6	1,28	1,49	0,39	1,17	2,25	0	1,50	1,49
7	1,07	1,40	0,13	1,29	2,45	1,50	0	1,57
8	0,48	0,97	0,98	1,35	2,50	1,49	1,57	0

Отримано два кластери: \(S_1\left\{1,2,3,6,7,8\right\}\) і \(S_2\left\{4,5\right\}\).

Кластер \(S_2\left\{4,5\right\}\) розділяємо на два кластери на відстані \(d_{45}=1,2\).

Аналізуємо відстані між об’єктами в кластері \(S1\left\{1, 2, 3, 6, 7, 8\right\}\). Для цього треба створити нову матрицю відстаней, яка не містить об’єктів 4 і 5, уже розділених на окремі кластери (табл. 3.3).

Табл. 3.3: Матриця відстаней \(D2\)

№ об’єкта	1	2	3	6	7	8
1	0	0,49	1,20	1,28	1,07	0,48
2	0,49	0	1,53	1,49	1,40	0,97
3	1,20	1,53	0	0,39	0,13	0,98
6	1,28	1,49	0,39	0	1,50	1,49
7	1,07	1,40	0,13	1,50	0	1,57
8	0,48	0,97	0,98	1,49	1,57	0

Знаходимо максимальну відстань між об’єктами, це буде відстань між другим та третім об’єктами \(d_{35}=2,54\). Оцінимо відстані об’єктів, що залишилися до другого та третього об’єктів:

• \(d12 < d13\) — об’єкт \(n_1\) ближче до \(n_2\);
• \(d62 > d63\) — об’єкт \(n_6\) ближче до \(n_3\);
• \(d72 > d73\) — об’єкт \(n_7\) ближче до \(n_3\);
• \(d82 < d83\) — об’єкт \(n_8\) ближче до \(n_2\).

Кластер \(S_1\left\{1,2,3,6,7,8\right\}\) розділився на два: \(S_{11}\left\{1, 2, 8\right\}\) і \(S_{12}\left\{3, 6, 7\right\}\).

Аналізуємо відстані між об’єктами в отриманих кластерах.

Створимо нові матриці відстаней для кластерів \(S_{11}(D3)\) та \(S_{12}(D4)\) (табл. 3.4; 4.1).

Табл. 3.4: Матриця відстаней \(D3\)

№ об’єкта	1	2	8
1	0	0,49	0,48
2	0,49	0	0,97
8	0,48	0,97	0

\(\max \, \> d_{28} = 0,97\).

Оцінимо відстані від об’єкта \(n_1\) до \(n_2\) і \(n_8\): \(d_12 < d_18\) — об’єкт \(n_1\) ближче до \(n_2\). Тоді \(n_8\) від’єднується від кластера \(S_{11}\left\{1, 2, 8\right\}\) на відстані \(0,97\), а об’єкти \(n_1\) і \(n_2\) розділяються на відстані \(0,49\).

Табл. 4.1: Матриця відстаней \(D4\)

№ об’єкта	1	2	8
1	0	0,39	0,13
2	0,39	0	1,50
8	0,13	1,50	0

\(\max\) \(d_{67} = 1,5\).

Оцінимо відстані від об’єкта \(n_3\) до \(n_6\) і \(n_7: d_{36} > d37\) — об’єкт \(n_3\) ближче до \(n_7\). Тоді \(n_6\) від’єднується від кластера \(S12\left\{3, 6, 7\right\}\) на відстані \(1,5\), а об’єкти \(n_3\) і \(n_7\) розділяються на відстані \(0,13\).

Усі об’єкти розділені на окремі кластери, що свідчить про закінчення процедури розбиття.

Побудуємо дендрограму (рис. 4.9).

Рис. 4.9: Дендрограма класифікації дивізимним методом

Метод Уорда (Ward’s method, 1963)

Оптимізація мінімальної дисперсії всередині кластерів:

• цільова функція (сума квадратів відхилень (СКВ) → \(\min\));
• утворюються кластери, приблизно рівних розмірів, мають гіперсферичну форму.

Алгоритм метода Уорда:

1. Нормування вихідних даних.
2. Розрахунок матриці відстаней або матриці мір подібності.
3. Знаходиться пара найближчих кластерів, вони об’єднуються. Новому кластеру присвоюється менший з номерів об’єднувальних кластерів. Для утвореного кластера розраховується СКВ за формулою: \[ V_k=\sum_{i=1}^{n_k}\sum_{j=1}^{p}(x_{ij}-\bar{x}_{jk})^2. \tag{4.2} \]
4. Надалі на кожному кроці роботи алгоритму об’єднуються ті об’єкти або кластери, які дають найменший приріст величини \(V_k\).

Процедури 2, 3 і 4 повторюються до тих пір, поки всі об’єкти не будуть об’єднані в один кластер або до досягнення заданого «порогу».

Приклад 4.3. Метод Уорда

1. Вхідні дані: аналізуються пять об’єктів, які характеризуються двома показниками \(X_{i1},X_{i2}\) (табл. 3.6).

Табл. 3.6: Вхідні дані

№ об’єкта	1	2	3	4	5
\(x_{i1}\)	21	18	15	13	25
\(x_{i2}\)	0,3	0,8	0,6	0,7	0,9

2. Розраховуємо матрицю евклідових відстаней між об’єктами (табл. 3.7).

Табл. 3.7: Матриця евклідових відстаней \(D\)

№ об’єкта	1	2	3	4	5
1	0	3,04	6,01	8,01	4,04
2	3,04	0	3,01	5,00	7,00
3	6,01	3,01	0	2,00	10,00
4	8,01	5,00	2,00	0	12,00
5	4,04	7,00	10,00	12,00	0

Знаходимо мінімальну відстань між об’єктами, це буде відстань між третім і четвертим об’єктами \(d_{34}=2,00\).

3. Для кластера \(S_{3,4}\) визначаємо СКВ за формулою 4.2:

   \[ V_k=\sum_{i=1}^{2}\sum_{j=1}^{2}(x_{ij}-\bar{x}_{j3})^2, \]

   де \(\bar{x}_{j3}\) — середнє значення \(j\)-ї ознаки в кластері \(S_3;\)
   \(x_{sr(13)} = 14;\)
   \(x_{sr23} = 0,65;\)
   \(V_{3} =[(15-14)2 + (0,6-0,65)2 ]+[(13-14)2 +(0,7-0,65)2]=2,005.\)

4. Вирішуємо питання: який новий об’єкт може бути на наступному кроці приєднаний до третього кластеру або які кластери можна об’єднати?

   • якщо об’єднувати об’єкти, що залишилися (1, 2, 5):
     • для 1 і 2 об’єктів \(V_k=1,625\);
     • для 1 і 5 об’єктів \(V_k=8,0081\);
     • для 2 і 5 об’єктів \(V_k=12,25\);
   • якщо приєднувати до кластеру S3 почергово кожен з решти об’єктів (1, 2, 5):
     • для 1 об’єкта і \(S3\): \(V_k=34,75\);
     • для 2 об’єкта і \(S3\): \(V_k=12,69\);
     • для 5 об’єкта і \(S3\): \(V_k=82,71\);

5. Кластеризація спостережуваних об’єктів методом Уорда подана на рис. 4.10.

Рис. 4.10: Кластеризація спостережуваних об’єктів

6. Кроки 2, 3 і 4 повторюються, поки всі об’єкти не будуть об’єднані в один кластер або до досягнення заданого «порогу» подібності.

Види ітеративних (ітераційних) методів кластеризації схематизовані на рис. 4.11.

Рис. 4.11: Види ітеративних (ітераційних) методів кластеризації

Характеристика ітеративних методів кластеризації наведена на рис. 4.12.

Рис. 4.12: Особливості ітеративних методів кластеризації

Розглянемо детальніше особливості і основні етапи ітеративних методів кластеризації.

Метод \(K\)-середніх

Особливості: метод \(k\)-середніх зручний для обробки великих статистичних сукупностей. Необхідно попередньо задати кількість кластерів \(k\).

Алгоритм метода \(K\)-середніх:

1. Виділяємо початкові центри \(k\) кластерів: \(C^{(0)}_1, C^{(0)}_2, …, C^{(0)}_k\) (як зважене середнє за кожним показником). Кожному кластеру привласнюють одиничну вагу.
2. Знаходять відстані від точки \(x_{k+1}\) до центрів кластерів, побудованих на кроці 1. Точку \(x_{k+1}\) відносять до кластеру, відстань до якого мінімальна.
3. Розраховують новий центр ваги \(C^{(1)}_i\). Вагу кластера \(i\) збільшують на одиницю.
4. Повтор кроків 2 і 3 поки всі крапки разом не будуть віднесені до якогось з \(k\) кластерів.
5. Точки \(x_1, x_2, …, x_n\) знову приєднуються до \(k\) отриманих кластерів, вага продовжує збільшуватися.
6. Розбиття порівнюється з попереднім, поки \(C^{(m+1)}\) i \(<>C^{(m)}_i\).
7. Класифікація закінчена.

Приклад 4.4. Метод \(K\)-середніх

1. Вхідні дані: аналізуються шість об’єктів, які характеризуються двома показниками \(X_i, Y_i\) (табл. 3.8).

Табл. 3.8: Вхідні дані

№ об’єкта	1	2	3	4	5	6
\(X_{i}\)	5	6	5	10	11	10
\(Y_{i}\)	10	12	13	9	9	7

2. Розбиваємо вихідну сукупність на два кластери: \(S^{(0)}_1 (1, 2, 3, 4)\) і \(S^{(0)}_2 (5, 6)\).

3. Знаходимо центри тяжіння (точки еталона) для кожної зі сформованих груп \(S^{(0)}_1\) і \(S^{(0)}_2:\) \[ E^{(0)}_1 =(e^{(0)}_{x1}; e^{(0)}_{y1}), \, E^{(0)}_2=(e^{(0)}_{x2}; e^{(0)}_{y2}), \]

   де \(e^{(0)}_{x1}=(5+6+5+10)/4=6,5;\) \(e^{(0)}_{y1}=(10+12+13+9)/4=11;\)
   Таким чином \(E^{(0)}_1 =(6,5; 11)\) і \(E^{(0)}_2=(10,5; 8).\)

4. Знаходимо відстань від точки еталона до об’єкта (табл. 3.9).

Табл. 3.9: Відстань від точки еталона до об’єкта

Об’єкт	\(E_1\)	\(E_2\)	Клас
1	1,803	5,852	\(S_1\)
2	1,118	6,021	\(S_1\)
3	2,5	7,433	\(S_1\)
4	4,031	1,118	\(S_2\)
5	4,924	1,118	\(S_2\)
6	5,315	1,118	\(S_2\)

\(E^{(1)}_2<E^{(1)}_1;\) \(4=>S^{(1)}_2(4,5,6).\)

5. Знаходимо центри тяжіння нового розбиття елементів: \(S^{(1)}_1 (1, 2, 3): E^{(1)}_1=(5,33; 11,66);\) \(S^{(1)}_2 (5, 6, 4): E^{(1)}_2=(10,33; 8,33).\)

6. Крок 4 для нового розбиття (табл. 4.2).

Табл. 4.2: Відстань від точки еталона до об’єкта

Об’єкт	\(E_1\)	\(E_2\)	Клас
1	1,7	5,588	\(S_1\)
2	0,745	5,676	\(S_1\)
3	1,374	7,087	\(S_1\)
4	5,375	0,745	\(S_2\)
5	6,263	0,943	\(S_2\)
6	6,6	1,374	\(S_2\)

7. Оскільки два останні розбиття збігаються, обчислювальні процедури закінчуються: \(S^{(1)}_1(1, 2, 3)\) і \(S^{(1)}_2 (5, 6, 4).\)