4.2 Нечіткі методи класифікації

Окремим видом методів кластерного аналізу є нечіткі методи класифікації.

Чітка (непересічна) кластеризація: кластеризація, в якій кожен об’єкт належить тільки до одного кластера.

Нечітка кластеризація: кластеризація, за якої для кожного об’єкта визначається дійсне значення, що показує ступінь приналежності до кластера — функція приналежності (ФП). Ступінь приналежності визначається відстанню від об’єкта до відповідних кластерних центрів. Даний алгоритм ітераційно обчислює центри кластерів і нові ступені приналежності об’єктів.

Нечітка кластеризація методом \(k\)-середніх здійснюється за допомогою певних алгоритмів (рис. 4.13).

Рис. 4.13: Алгоритми нечіткої клатеризації методом \(k\)-середніх

Розглянемо детальніше основні етапи реалізації алгоритмів нечітких \(k\)-середніх.

Базовий алгоритм нечітких \(k\)-середніх. Fuzzy \(c\)-means (Бездек)

Алгоритм знаходить компактні кластери сферичної форми.

Дано: множина \(K\) вхідних векторів \(x_k\), \(N\) виділяючих кластерів \(с_j\).

Кожний вхідний вектор \((х_k)\) належить будь-якому кластеру \((c_j)\) з ФП \(\mu_{jk}\), що приймає будь-яке значення з інтервалу \([0;1]\), де \(j\) — номер кластера, а \(k\) — номер вхідного вектора.

Умови нормування для \(\mu jk\):

\[ \sum_{j=1}^N \mu_{jk}=1, \forall \, k=1,...,K. \tag{4.3} \]

Мета кластеризації — мінімізація суми всіх зважених евклідових відстаней:

\[ \sum_{j=1}^N = \sum_{k=1}^K ((\mu_{jk})^q|| x_k-c_j||^2)\rightarrow \min, \tag{4.4} \]

де \(q\) — фіксований параметр, що задається перед ітераціями.

Для цього треба знайти перші похідні по \(\mu_{jk}\) і по \(c_j\), прирівняти їх до 0 і розв’язати систему рівнянь. Отримуємо:

формула центра кластера (зважений центр гравітації): \[ c_j=\frac{\sum_{j=1}^N(\mu_{jk})^q \cdot x_k}{\sum_{j=1}^N(\mu_{jk})^q}; \tag{4.5} \]
ФП (елементи матриці нечіткого розбиття): \[ c_j=\frac{1}{(d^2_{jk} \cdot \sum_{j=1}^N \frac{1}{d^2_{jk}})^\frac{1}{q-1}}. \tag{4.6} \]

Базовий алгоритм нечітких \(k\)-середніх – FCM

Ініціалізація (встановлення параметрів):

кількість кластерів \(N,\, 2 < N < K;\)
міра відстаней \(d\) (евклідова);
фіксований параметр \(q (\sim1,5)\);
\(ε\) — параметр зупинки алгоритма;
початкова (на нульовій ітерації) матриця приналежності об’єктів \(x_k\) до \(c_jU^{(0)} = (\mu_{jk})^{(0)}\) — випадково генерується.

Розрахунок центрів кластерів за формулою (4.5).
Розрахунок відстані між об’єктами та центрами кластерів: \[ d_{jk}=\sqrt{||x_k-c_j||^2}. \tag{4.7} \]
Перерахунок елементів матриці нечіткого розбиття, якщо \[ d_{jk}>0\rightarrow \mu_{jk}=\frac{1}{(d^2_{jk} \cdot \sum_{j=1}^N \frac{1}{d^2_{jk}}) ^\frac{1}{q-1}}, \\ якщо \> d_{jk}>0\rightarrow \mu_{jk}=\begin{cases}1, \> j = k\\0, \> j\neq k \end{cases}. \tag{4.8} \] Перевіряємо умову \(‖U^{(t)}-U^{(t-1)}‖^2<ε\): якщо «так», то алгоритм закінчений; якщо «ні» — перейти до кроку 2.

Метод пошуку згущень «форель»

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

Обчислення матриці відстаней (або матриці мір подібності) між об’єктами.
Вибір об’єкта (на основі попереднього аналізу точок та їх околів), який є первинним центром першого кластера — гіперсфери заданого радіуса \(R: \min \>\> d_{ij}≤R≤\max \>\> d_{ij}\).
Визначення сукупності точок, що потрапили всередину цієї сфери та обчислення для них координат нового центра (вектор середніх значень ознак).
Крок 3 повторюється до тих пір, поки черговий перерахунок координат центра сфери приводить до такого ж результату, як і на попередньому кроці.
Переміщення сфери припиняється, а точки, що потрапили в неї, утворюють кластер і з подальшого процесу кластеризації виключаються.
Для всіх точок, що залишилися, повторюють кроки 2–5.

Метод дендритів

Дендрит: ламана лінія, яка може розгалужуватися; вона з’єднує кожні дві точки досліджуваної сукупності, проте не може містити замкнутих ламаних ліній (контурів).

Критерій оптимальності дендрита: \(\min\) суми відстаней, це забезпечує більшу схожість сусідніх елементів.

Алгоритм побудови дендритів (нелінійне впорядкування):

Нормування вихідних даних.
Розрахунок матриці відстаней або матриці мір подібності.
Аналіз рядків матриці відстаней і вибір пари елементів з мінімальною відстанню між собою.
З’єднання спільних елементів (об’єднання) і отримання груп, які називають об’єднаннями першого роду.
Процес об’єднання відбувається до тих пір, поки не будуть об’єднані всі пари елементів досліджуваної сукупності.

Приклад 4.5. Метод дендритів

Вхідні дані: аналізуються шість об’єктів, які характеризуються двома показниками \(x_{i1}, x_{i2}\) (табл. 4.3).
Розраховуємо матрицю евклідових відстаней між об’єктами (табл. 4.4).

Табл. 4.3: Вхідні дані
№ об’єкта	1	2	3	4	5	6
\(x_{i1}\)	5	6	5	10	11	10
\(x_{i2}\)	10	12	13	9	9	7

Табл. 4.4: Матриця евклідових відстаней \(D\)
№ об’єкта	1	2	3	4	5	6
1	0,00	2,24	3,00	5,10	6,08	5,83
2	2,24	0,00	1,41	5,00	5,83	6,40
3	3,00	1,41	0,00	6,40	7,21	7,81
4	5,10	5,00	6,40	0,00	1,00	2,00
5	6,08	5,83	7,21	1,00	0,00	2,24
6	5,83	6,40	7,81	2,00	2,24	0,00

У матриці \(D\) вибираємо елементи з \(\min\) відстанню між собою:

1-2	2,24
2-3	1,41
3-2	1,41
4-5	1,0
5-4	1,0
6-4	2,0

Отримуємо дві групи із загальними елементами: (1 – 2 – 3) і (4 – 5 – 6).
За відповідними зв’язками будуємо дендрит (рис. 4.14).

Рис. 4.14: Дендрит

Метод куль

Алгоритм методу куль:

Нормування вихідних даних.
Розрахунок матриці відстаней або матриці мір подібності.
Визначення радіуса кулі \(ρ=\max_S \min_U (d_{SU})\), де \(d_{SU}\) — відстань між \(S\)-м і \(U\)-м об’єктами.
Для кожного багатовимірного об’єкта утворюється куля з радіусом \((R)\) і визначається кількість точок, що потрапили в кожну кулю.
Визначається куля з максимальним числом елементів. Якщо є кілька таких куль, то розглядається куля, що розташована найближче до осі координат.
З матриці виключаються елементи, що потрапили в першу виділену групу.

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

Приклад 4.6. Метод куль

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

Табл. 4.5: Вхідні дані
№ об’єкта	1	2	3	4	5	6
\(x_{i1}\)	5	6	5	10	11	10
\(x_{i2}\)	10	12	13	9	9	7

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

Рис. 4.15: Визначення радіуса кулі

Виходячи з умови \((d_{US}<ρ)\) елемент 1 становитиме одноелементну кулю.

Знаходимо відстань об’єктів до точки початку координат (рис. 4.16).

Рис. 4.16: Відстань об’єктів до точки початку координат

Отримали три кластери: \(S_1 (п4, п5, п6); S_2 (п2, п3); S_3 (п1).\)