Нечітка кластеризація: алгоритм fuzzy c-means і точки між кластерами

K-means і його чітке віднесення, fuzzy c-means з належностями до всіх кластерів, фазифікатор m, коефіцієнт розбиття та індекс Се — Бені для вибору кількості кластерів — і чому викидні точки дістають високі належності.

13 хвилин Matěj Žalmánek 2026-10-15

Серія Основи ШІ Частина 36 з 52

1. Мапа штучного інтелекту: що є що і як усе це пов’язано
2. Коротка історія штучного інтелекту: від Тюрінга до мовних моделей
3. Дані, модель, тренування, інференс: основні поняття на одному прикладі
4. Як читати математичний запис: символи, індекси, суми та квантори
5. Множини й відношення: конструктор, з якого складаються означення в ШІ
6. Функції й відображення: чому кожна модель у ШІ — це функція
7. Логіка й доведення: правила, за якими міркують у ШІ
8. Графи й дерева: структура, на якій тримаються пошук і нейронні мережі
9. Лінійна алгебра для машинного навчання: вектори, матриці й чому ШІ передусім множить
10. Похідні, градієнт і правило ланцюжка: як модель дізнається, у якому напрямку вчитися
11. Градієнтний спуск: як навчається модель
12. Що таке ймовірність: від кидка кубика до аксіом Колмогорова
13. Умовна ймовірність і теорема Баєса: як змінити оцінку, коли дізнаєтеся щось нове
14. Випадкова величина і функція розподілу: одна функція, яка каже про розподіл усе
15. Функція щільності та функція маси ймовірності: чому неперервна величина має в точці ймовірність нуль
16. Математичне сподівання, дисперсія і коваріація: де лежить розподіл, наскільки він широкий і що з чим пов’язано
17. Огляд розподілів ймовірностей: Бернуллі, біноміальний, Пуассона, рівномірний, нормальний і експоненційний
18. Закон великих чисел і центральна гранична теорема: чому середні поводяться так передбачувано
19. Статистика й оцінювання параметрів: максимальна правдоподібність, MAP і довірчі інтервали
20. Теорія інформації: ентропія, перехресна ентропія і KL-дивергенція — звідки беруться функції втрат
21. Пошук у просторі станів: BFS, DFS, UCS і A* з анімаціями
22. Ігри та суперник: мінімакс, альфа-бета відсікання і Monte Carlo tree search
23. Задоволення обмежень: бектрекінг, поширення обмежень і AC-3 на судоку та мапі чеських країв
24. Логіка й системи, засновані на знаннях: пряме і зворотне виведення, резолюція та експертні системи
25. Планування: STRIPS, світ кубиків, евристики з релаксації та планування в AI-агентах
26. Локальний пошук та імітація відпалу: комівояжер через обласні центри Чехії
27. Генетичні алгоритми: популяція, схрещування, мутація і добір на рюкзаку для походу
28. Еволюційні стратегії і генетичне програмування: від правила однієї п’ятої до закону Кеплера
29. Оптимізація мурашиною колонією: як феромоновий слід знаходить короткий шлях
30. Оптимізація роєм частинок: інерція, власний досвід і досвід рою
31. Нейроеволюція: еволюція ваг і форми нейронних мереж та алгоритм NEAT
32. Нечіткі множини й функції належності: як записати «трохи тепло»
33. Нечітка логіка та ймовірність: чому «трохи тепло» не означає «імовірно тепло»
34. Нечітка логіка: t-норми, імплікації та правила ЯКЩО–ТО
35. Нечітке керування: Мамдані та Суґено від вентилятора до маятника на візку
36. Нечітка кластеризація: алгоритм fuzzy c-means і точки між кластерами
37. Нейро-нечіткі системи (ANFIS): нечіткі правила, які навчаються з даних
38. Марковські ланцюги: матриця переходів, стаціонарний розподіл і PageRank
39. Приховані марковські моделі: алгоритм Вітербі й нечесне казино
40. Байєсівські мережі: чому трава мокра і що з цього випливає для дощувача
41. Фільтр Калмана: як за неточними вимірюваннями оцінити, де авто і як швидко воно їде
42. Види машинного навчання: з учителем, без учителя, з частковим залученням учителя та інші
43. Промпти, контекст і RAG: як дати моделі правильну інформацію
44. Варіаційні автокодувальники (VAE): нові зображення з неперервного латентного простору
45. Генеративні змагальні мережі (GAN): фальшувальник проти детектива
46. Дифузійні моделі: як із чистого шуму постає зображення
47. Марковські процеси ухвалення рішень: стани, дії, винагороди й рівняння Беллмана
48. Q-навчання і DQN: як навчитися цінності дій — від таблиці до нейронної мережі
49. Policy gradient і PPO: навчання безпосередньо політики
50. Як працює ШІ-агент: мовна модель у циклі з інструментами
51. Програмування з AI-агентами: завдання, тести й перевірка
52. Оцінювання і безпека систем ШІ: як вимірювати і як стежити

Повна програма серії Готово: 52 з 83 тем

Кластеризація шукає в даних групи, про які заздалегідь нічого не відомо: покупців зі схожою купівельною поведінкою, ділянки однієї тканини на знімку магнітно-резонансної томографії, документи на схожу тему. Класичний алгоритм k-means відносить кожну точку рівно до однієї групи. Проте справжні дані мають точки на межі — покупця, який купує трохи як студент і трохи як батько, піксель, у якому сходяться сіра й біла речовина мозку. Нечітка кластеризація дозволяє точці належати до кількох груп водночас, до кожної з них трохи.

Продовжує частини Нечіткі множини й функції належності і Види машинного навчання, де кластеризація з’явилася як типова задача навчання без учителя.

1. Чітка кластеризація: k-means

Означення — задача k-means

Для точок x₁, …, x_n ∈ ℝ^d і кількості кластерів c шукаємо центри v₁, …, v_c і віднесення точок до кластерів, які мінімізують

J = ∑_i=1ⁿ ‖x_i − v_shluk(i)‖².

Алгоритм Ллойда чергує два кроки: віднеси кожну точку до найближчого центру; перерахуй кожен центр як середнє його точок. Повторюй, поки віднесення змінюється.

Означення — евклідова відстань

Для точок x, v ∈ ℝ^d маємо ‖x − v‖ = √( ∑_r=1^d (x_r − v_r)² ). На площині це звичайна довжина відрізка, наприклад від точки M1 = (4,5; 2,5) до центру кластера A (1,73; 2,31), який нижче знайде fuzzy c-means: √(2,77² + 0,19²) ≈ 2,78. Кластеризація працює з квадратом ‖·‖² — відпадає корінь, а віддалені точки штрафуються сильніше.

def kmeans(X, c):
    V = c випадково вибраних точок з X            # початкові центри
    while True:
        shluk = [argmin_j ‖x − V[j]‖² for x in X]  # крок віднесення
        if shluk не змінився: return V, shluk
        for j in range(c):                         # крок центрів
            V[j] = середнє точок x, для яких shluk(x) = j

Теорема — алгоритм Ллойда зупиняється

Жоден крок не збільшує J, тому алгоритм зупиняється після скінченної кількості кроків.

Доведення: Віднесення: кожен доданок ‖x_i − v_shluk(i)‖² замінюється найменшим з усіх ‖x_i − v_j‖², тож не збільшується. Центри: для точок S одного кластера із середнім x̄ справджується розклад

∑_i∈S ‖x_i − v‖² = ∑_i∈S ‖x_i − x̄‖² + |S| · ‖x̄ − v‖²

(мішаний доданок 2 ∑ (x_i − x̄) · (x̄ − v) дорівнює нулю, бо ∑ (x_i − x̄) = 0). Отже, сума найменша при v = x̄. Розбиттів n точок на c кластерів скінченно багато, а J за кожної зміни віднесення строго спадає (за однакової відстані лишаємо точку в її кластері), тож жодне розбиття не повториться. ∎

Теорема нічого не каже про те, чи знайдене розбиття має найменше J, — лише що алгоритм не зациклиться.

Наші дані: три групи по 40 точок — A ліворуч унизу, B праворуч і C угорі, — чотири точки на межі (M1–M4) і дві викидні точки далеко від усього (O1, O2). K-means усталився після чотирьох ітерацій:

Кластери він знайшов добре, але точки на межі мусив розподілити: M1, M3 і M4 відніс до B, M2 — до A. Точка M3 при цьому лежить майже точно між B і C — k-means про це нічого не скаже. А обидві викидні точки потрапили до кластера C, ніби належать до нього так само, як його ядро.

2. Fuzzy c-means

Означення — fuzzy c-means (Данн 1973, Бездек 1981)

Замість віднесення шукаємо матрицю належностей U = (u_ij), u_ij ∈ [0, 1], де для кожної точки ∑_j u_ij = 1, і центри v_j, які мінімізують

J_m = ∑_i ∑_j u_ij^m ‖x_i − v_j‖²,

де m > 1 — фазифікатор. Алгоритм чергує два кроки, що випливають з умов оптимальності:

v_j = ∑_i u_ij^m x_i / ∑_i u_ij^m,    u_ij = 1 / ∑_k (d_ij / d_ik)^2/(m−1),

де d_ij = ‖x_i − v_j‖.

J_m = ∑_i=1ⁿ ∑_j=1^c u_ij^m ‖x_i − v_j‖²,    ∑_j u_ij = 1

J_m

загальна «ціна» розбиття — алгоритм її мінімізує; вона мала, коли точки належать переважно до близьких до них центрів

∑_i ∑_j

кожна точка рахується до кожного кластера — на відміну від k-means, де на точку брався лише один кластер

u_ij

належність точки i до кластера j — вага, з якою відстань входить у ціну

^m

фазифікатор — без степеня (m = 1) вигідно було б віддати всю одиницю найближчому центру, і знову вийшов би k-means; при m > 1 ділитися вигідно: точка, однаково віддалена від двох центрів, при m = 2 і поділі навпіл заплатить лише (½² + ½²) · d² = ½d² замість d²

‖x_i − v_j‖²

квадрат відстані — скільки коштує мати точку «біля» цього центру; далекий центр обійдеться дорого

∑_j u_ij = 1

умова — без неї мінімум був би тривіальним: усі u_ij = 0 і нульова ціна

u_ij = 1 / ∑_k=1^c ( d_ij / d_ik )^2/(m−1)

u_ij

нова належність точки i до кластера j за фіксованих центрів

d_ij / d_ik

відношення відстаней — у скільки разів центр j далі, ніж центр k; відношення (а не різниця) робить результат незалежним від масштабу даних

^2/(m−1)

наскільки різко вирішує відношення — для m = 2 це 2, тож удвічі ближчий центр дістає вчетверо більше; для m → 1 показник необмежено зростає і все дістає найближчий центр

∑_k

порівняння з усіма центрами, зокрема із самим j (доданок k = j дорівнює 1), — завдяки цьому належності точки дають у сумі рівно 1

Теорема — звідки беруться обидва кроки

Належності за фіксованих центрів. Для однієї точки i мінімізуємо ∑_j u_ij^m d_ij² за умови ∑_j u_ij = 1. Функція Лагранжа: L = ∑_j u_ij^m d_ij² − λ (∑_j u_ij − 1). З ∂L/∂u_ij = m u_ij^m−1 d_ij² − λ = 0 випливає u_ij = (λ/m)^1/(m−1) · d_ij^−2/(m−1). Після підстановки в умову суми невідома λ скорочується і лишається

u_ij = d_ij^−2/(m−1) / ∑_k d_ik^−2/(m−1) = 1 / ∑_k (d_ij / d_ik)^2/(m−1).

Вийшли додатні числа, тож умову u_ij ≥ 0 окремо стежити не треба. (Якщо точка лежить точно в центрі, d_ij = 0, вона дістає до цього кластера належність 1; наша реалізація розв’язує це так, що відстань ніколи не падає нижче 10⁻¹².)

Центри за фіксованих належностей. J_m — опукла квадратична функція від v_j, і ∂J_m/∂v_j = −2 ∑_i u_ij^m (x_i − v_j) = 0 дає v_j = ∑_i u_ij^m x_i / ∑_i u_ij^m.

Отже, кожен крок мінімізує J_m за фіксованої другої групи змінних і не може його збільшити — той самий аргумент, що й для k-means. Бездек та ін. (1987, виправлення початкової теореми Бездека 1980 року) показали, що послідовність має граничні точки в стаціонарних точках J_m (не обов’язково в глобальному мінімумі).

import numpy as np

def fcm(X, c, m=2.0, iteraci=100, eps=1e-5):
    U = np.random.dirichlet(np.ones(c), size=len(X))        # випадкові належності, рядок = 1
    for _ in range(iteraci):
        W = U ** m
        V = (W.T @ X) / W.sum(axis=0)[:, None]             # центри як зважені середні
        D = np.linalg.norm(X[:, None, :] - V[None, :, :], axis=2) + 1e-12
        nove = 1 / ((D[:, :, None] / D[:, None, :]) ** (2 / (m - 1))).sum(axis=2)
        if np.abs(nove - U).max() < eps:
            return V, nove
        U = nove
    return V, U

3. Fuzzy c-means на наших даних

Колір точки тепер — суміш кольорів кластерів відповідно до належностей: чисто зелена точка належить лише до A, точка «між» зеленим і помаранчевим — частково до A і частково до B. Пунктирні лінії показують, як переміщувалися центри, — алгоритм усталився після дев’яти ітерацій:

Тепер видно, що k-means замовчав. M1 майже навпіл між A і B; M3 насправді на волосинку більше в C, ніж у B, хоча k-means відніс її до B; а M4 посередині трикутника трохи належить до всіх трьох. Точки в ядрах кластерів мають належність до свого кластера, близьку до одиниці. Центри вийшли практично такі самі, як у k-means, — fuzzy c-means не змінює, де кластери, але додає до них інформацію, наскільки впевнено до них належить кожна точка.

Приклад — належності точки M1 = (4,5; 2,5)

Центри після дев’яти ітерацій: A ≈ (1,73; 2,31), B ≈ (7,12; 2,87), C ≈ (4,51; 7,11). Для m = 2 досить обернених квадратів відстаней:

Кластер	d2	1/d2	u = (1/d2) / 0,3190
A	2,772 + 0,192 ≈ 7,72	0,1296	0,41
B	2,622 + 0,372 ≈ 7,03	0,1423	0,45
C	0,012 + 4,612 ≈ 21,25	0,0471	0,15
сума		0,3190	1,00

M1 майже однаково віддалена від центрів A і B (7,72 проти 7,03), тому ділиться між ними майже навпіл; C утричі далі (у квадраті), тож дістає лише решту.

4. Фазифікатор m

Означення — коефіцієнт розбиття

Коефіцієнт розбиття (partition coefficient) — це PC = (1/n) ∑_i ∑_j u_ij². Він дорівнює 1 для чіткого розбиття і 1/c, коли кожна точка однаково належить до всіх кластерів.

PC = (1/n) ∑_i ∑_j u_ij²

PC

чіткість усього розбиття, число з [1/c; 1]

(1/n) ∑_i

середнє за точками — щоб можна було порівнювати набори даних різного розміру

∑_j u_ij²

чіткість однієї точки — квадрат «винагороджує» зосереджену належність: (1, 0, 0) дає 1, (⅓, ⅓, ⅓) лише ⅓; за фіксованої суми 1 сума квадратів найменша, коли всі частки однакові

Для m, близького до 1, fuzzy c-means наближається до k-means: коефіцієнт розбиття дорівнює 0,98, а точка M4 належить до B на 0,79. Для m = 2 коефіцієнт становить 0,84, а для m = 5 лише 0,42 — кольори зливаються, і навіть точка з ядра кластера A має до A належність лише 0,45. Для m → ∞ усі належності прямували б до 1/3. Найчастіше використовують m = 2: досить м’яко, щоб точки на межі було видно, і досить чітко, щоб кластери лишалися виразними.

Приклад — точка вдвічі ближча до одного з двох центрів

Точка має до центру 1 відстань 1, а до центру 2 відстань 2. За формулою u₁ = 1 / (1 + (1/2)^2/(m−1)):

• m = 1,2: показник 10, u₁ = 1 / (1 + 1/1 024) ≈ 0,999 — практично чітке віднесення,
• m = 2: показник 2, u₁ = 1 / (1 + 1/4) = 0,8,
• m = 5: показник 0,5, u₁ = 1 / (1 + 0,707) ≈ 0,586,
• m → ∞: показник → 0, (1/2)⁰ = 1 і u₁ → 1/2.

Загалом: для m → 1⁺ показник 2/(m − 1) прямує до нескінченності, відношення d_ij/d_ik < 1 прямують до нуля, а ті, що > 1, — до нескінченності, тож найближчий центр дістає 1, а решта 0 (k-means). Для m → ∞ показник прямує до нуля, усі c доданків суми прямують до 1 і u_ij → 1/c.

5. Скільки кластерів?

Кількість кластерів алгоритму треба задати. Коли ми її не знаємо, запускаємо його для різних c і порівнюємо якість розбиттів. Для цього придатні коефіцієнт розбиття та індекс Се — Бені (Xie–Beni).

Означення — індекс Се — Бені

XB = ∑_i ∑_j u_ij^m ‖x_i − v_j‖² / (n · min_{j ≠ k} ‖v_j − v_k‖²) — що менший, то краще.

XB = ∑_i ∑_j u_ij^m ‖x_i − v_j‖² / ( n · min_{j ≠ k} ‖v_j − v_k‖² )

XB

відношення «розкид усередині кластерів / відстань між ними» — менше краще

∑ ∑ u_ij^m ‖x_i − v_j‖²

компактність — саме значення J_m, яке алгоритм мінімізував

n

кількість точок — робить із чисельника середнє на точку, щоб індекс не зростав із розміром даних

min_{j ≠ k} ‖v_j − v_k‖²

відокремленість — вирішує найближча пара центрів; саме J_m з додаванням кластерів лише спадає, а цей доданок штрафує розбиття, яке розколює один справжній кластер на два близькі

Приклад — індекс Се — Бені для c = 3

Після завершення алгоритму J₂ ≈ 166,73. Квадрати відстаней між центрами: A–B ≈ 29,4, A–C ≈ 30,8, B–C ≈ 24,79 (найближчі B і C). Для n = 126 точок:

XB = 166,73 / (126 · 24,79) = 166,73 / 3 124 ≈ 0,053.

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

6. Де fuzzy c-means дає збій

Погляньте на викидні точки: O1 праворуч угорі має до C належність 0,45, а до B — 0,39; O2 ліворуч угорі — навіть 0,58 до C. Проте жодному кластеру вони не належать. Винна умова ∑_j u_ij = 1: точка мусить комусь роздати свою одиницю, навіть коли вона далеко від усіх. Належність тут означає радше «до кого найближче», ніж «наскільки добре сюди пасує».

Приклад — чому O2 = (0,2; 9,5) «належить» до C

Квадрати відстаней до центрів: A ≈ 54,07, B ≈ 91,88, C ≈ 24,29. Навіть від найближчого центру C точка, отже, віддалена на 4,9 — понад шість стандартних відхилень 0,8, з якими точки кластерів розкидані навколо центрів. Обернені значення 0,0185, 0,0109 і 0,0412 дають суму 0,0706 і належності 0,26, 0,15 і 0,58. Формула бачить лише відношення відстаней, а не їхню величину: що далі лежала б точка, то ближче відношення були б до 1, а належності — до ⅓, але до нуля вони не прямували б ніколи.

Означення — посибілістичні c-means (Крішнапурам і Келлер, 1993)

Умову суми відкидають, а до ціни додають доданок, який не допускає тривіального розв’язку u = 0:

J = ∑_i ∑_j u_ij^m d_ij² + ∑_j η_j ∑_i (1 − u_ij)^m,    звідки u_ij = 1 / (1 + (d_ij² / η_j)^1/(m−1)).

η_j — це «радіус» кластера j: точка на відстані d² = η_j має належність ½, а при m = 2 точка з d² = 9η_j — лише 0,1. Належність тепер залежить від відстані до одного-єдиного центру, а не від відношення до інших, — викидна точка дістає малі значення скрізь.

• Посибілістичні c-means (Крішнапурам і Келлер, 1993) скасовують умову суми — викидна точка тоді дістає малі належності до всіх кластерів.
• Форма кластерів. Евклідова відстань дає круглі кластери. Алгоритм Густафсона — Кесселя (1979) дає кожному кластеру власну матрицю відстані і знаходить навіть видовжені еліпси.
• Початкове положення. Так само, як k-means, алгоритм може зупинитися в гіршому локальному мінімумі — на практиці його запускають кілька разів з різних стартів.

7. Нечітка кластеризація на практиці

• Медичні знімки. Сегментація МРТ-знімків мозку на сіру речовину, білу речовину та спинномозкову рідину — класичне застосування: піксель на межі тканин справді містить обидві.
• Сегментація покупців. Покупець може частково належати до кількох груп, і маркетинг може це враховувати.
• Імовірнісний родич. Гаусові суміші, навчені алгоритмом EM, теж відносять точки до кластерів «м’яко» — але ймовірностями, а не належностями. Результати бувають схожі, а тлумачення відрізняється саме так, як описала частина про нечітку логіку та ймовірність.
• Ембединги. Тексти, перетворені мовною моделлю на вектори, можна кластеризувати так само; м’яке віднесення тоді покаже документи, що лежать між темами.

8. Підсумок

• K-means відносить кожну точку рівно до одного кластера і нічого не каже про точки на межі.
• Fuzzy c-means шукає належності u_ij із сумою 1 і центри як зважені середні; чергує два прості кроки.
• На наших даних він знайшов ті самі центри, що й k-means, і до того ж показав, що точки M1–M4 належать до двох чи трьох кластерів водночас.
• Фазифікатор m керує тим, наскільки м’яке розбиття; коефіцієнт розбиття та індекс Се — Бені допомагають вибрати кількість кластерів.
• Умова суми 1 дає викидним точкам високі належності; посибілістичні варіанти це розв’язують.

Хочете спробувати самі? Попросіть ШІ-агента запустити fuzzy c-means на кольорах пікселів вашої власної фотографії й розфарбувати її за кластерами — і погляньте, які пікселі лежать «між» кольорами.

Маєте іншу думку? Напишіть на support@coden-app.com.