Алгоритми класифікації

🔬 Фундаментальні концепції класифікації

Що таке класифікація?

Класифікація — це тип задачі керованого навчання (supervised learning), де мета полягає в тому, щоб навчити модель призначати вхідні дані одному з попередньо визначених класів або категорій. На відміну від регресії, яка передбачає неперервні числові значення, класифікація працює з дискретними мітками.

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

Типи класифікації

Бінарна класифікація — найпростіший випадок, де є лише два можливі класи. Приклади включають виявлення спаму, медичну діагностику (хвороба/здоров'я), кредитний скоринг (схвалення/відмова). Бінарна класифікація є основою для багатьох складніших підходів.

Мультикласова класифікація передбачає більше двох класів. Наприклад, розпізнавання рукописних цифр (0-9), класифікація електронних листів за темами, розпізнавання об'єктів на зображеннях. Деякі алгоритми природно підтримують мультикласову класифікацію, тоді як інші використовують стратегії "один проти одного" (one-vs-one) або "один проти решти" (one-vs-rest).

Мультилейблна класифікація дозволяє призначати об'єкту кілька класів одночасно. Наприклад, документ може належати до категорій "наука", "технологія" та "новини" одночасно. Це ускладнює задачу, оскільки класи не є взаємовиключними.

Математична основа

Формально, класифікацію можна описати як задачу знаходження функції f: X → Y , де X — простір ознак (features), а Y — множина класів. Для бінарної класифікації Y = {0, 1} , для мультикласової Y = {1, 2, ..., k} .

Багато алгоритмів класифікації працюють з ймовірностями. Вони обчислюють P(y|x) — ймовірність того, що спостереження x належить до класу y . Остаточне передбачення робиться шляхом вибору класу з найвищою ймовірністю.

🎯 Основні алгоритми класифікації

1. Decision Trees (Дерева рішень)

Decision Trees — це один з найінтуїтивніших алгоритмів класифікації, який будує ієрархічну структуру правил для прийняття рішень. Дерево складається з вузлів (nodes), де кожен вузол представляє тест на значення ознаки, гілки (branches) відповідають результатам тесту, а листя (leaves) — класам.

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

Недоліки: Схильні до overfitting, нестабільні (малі зміни в даних можуть змінити структуру), можуть створювати складні дерева з поганим узагальненням.

Алгоритм навчання: Використовує метрики як Information Gain або Gini Impurity для вибору найкращих ознак для розділення. Рекурсивно ділить дані на підмножини, поки не досягне листків з однорідними класами або не вичерпає критеріїв зупинки.

Застосування: Медична діагностика, фінансовий аналіз, експертні системи, де важлива інтерпретація рішень.

2. Random Forest

Random Forest — це ансамблевий метод, який об'єднує багато Decision Trees для отримання більш точних та стабільних передбачень. Кожне дерево навчається на випадковій підмножині даних (bootstrap sampling) та враховує лише випадкову підмножину ознак при кожному розділенні.

Як працює: Під час навчання створюються сотні або тисячі дерев. Кожне дерево голосує за клас, і остаточна класифікація проводиться шляхом majority voting. Для регресії використовується середнє значення.

Переваги: Висока точність, зменшує overfitting порівняно з окремими деревами, може визначати важливі ознаки, добре працює з великими датасетами, обробляє missing values.

Недоліки: Менш інтерпретовані за окремі дерева, потребує більше обчислювальних ресурсів, може бути повільним для real-time передбачень.

Гіперпараметри: Кількість дерев (n_estimators), глибина дерев (max_depth), мінімальна кількість зразків у листі (min_samples_leaf), кількість ознак для розгляду (max_features).

3. Support Vector Machines (SVM)

SVM — потужний алгоритм класифікації, який знаходить оптимальну гіперплощину для розділення класів у просторі ознак. Основна ідея полягає в максимізації "маржі" (відстані) між гіперплощиною та найближчими точками різних класів (support vectors).

Kernel Trick: Для нелінійно роздільних даних SVM використовує kernel functions (RBF, polynomial, sigmoid), які неявно перетворюють дані у більш високий вимір, де вони стають лінійно роздільними.

Переваги: Ефективний у високовимірних просторах, добре працює з нелінійними даними через kernels, стійкий до overfitting завдяки margin максимізації, менш схильний до curse of dimensionality.

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

Застосування: Розпізнавання тексту, класифікація зображень, біоінформатика, фінансове прогнозування.

4. Naive Bayes

Naive Bayes заснований на теоремі Баєса з припущенням "наївності" про незалежність ознак. Незважаючи на це спрощене припущення, алгоритм часто показує відмінні результати та є дуже швидким.

Математика: Використовує формулу Баєса: P(y|x) = P(x|y) * P(y) / P(x) , де припущення незалежності дозволяє обчислити P(x|y) як добуток ймовірностей окремих ознак.

Варіанти: Gaussian Naive Bayes (для неперервних ознак), Multinomial Naive Bayes (для підрахунку даних), Bernoulli Naive Bayes (для бінарних ознак).

Переваги: Дуже швидкий навчання та передбачення, добре працює з малими датасетами, стійкий до шуму, ефективний для текстової класифікації (спам, sentiment analysis).

Недоліки: Припущення незалежності рідко виконується на практиці, гірша продуктивність на складних залежностях між ознаками.

5. K-Nearest Neighbors (KNN)

KNN — простий алгоритм "л treated learning" (lazy learning), який не будує модель під час навчання, а зберігає всі навчальні дані. Класифікація нового об'єкта базується на голосуванні K найближчих сусідів.

Як працює: Для нового спостереження знаходяться K найближчих точок у просторі ознак (зазвичай використовується Euclidean відстань), і клас визначається majority voting серед цих сусідів.

Вибір K: Маленьке K (1-3) → більш чутливе до шуму, велике K → більш гладке рішення, але може змивати межі класів. Часто використовується cross-validation для вибору оптимального K.

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

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

6. Logistic Regression

Logistic Regression, незважаючи на назву, є алгоритмом класифікації, а не регресії. Він використовує логістичну (сигмоїдну) функцію для моделювання ймовірності приналежності до класу.

Математика: Використовує логістичну функцію: P(y=1|x) = 1 / (1 + e^(-z)) , де z = w₀ + w₁x₁ + ... + wₙxₙ . Ця функція перетворює лінійну комбінацію ознак у ймовірність від 0 до 1.

Переваги: Швидкий та ефективний, надає ймовірності, легко інтерпретувати коефіцієнти, добре працює як baseline, менше схильний до overfitting при регуляризації.

Недоліки: Припускає лінійну залежність між ознаками та логарифмом odds, може потребувати feature engineering для нелінійних відносин, менш потужний за складніші алгоритми.

Мультикласова версія: Використовує multinomial logistic regression (softmax regression) або one-vs-rest підхід.

7. Gradient Boosting (XGBoost, LightGBM, CatBoost)

Gradient Boosting — потужний ансамблевий метод, який послідовно додає слабкі моделі (зазвичай дерева), кожна з яких виправляє помилки попередніх. XGBoost, LightGBM та CatBoost — оптимізовані реалізації цієї ідеї.

Як працює: Почнеться з простішої моделі, обчислюються залишки (помилки), наступна модель навчається передбачати ці залишки. Процес повторюється, і передбачення всіх моделей сумуються.

XGBoost: Додає regularization (L1, L2), обробляє missing values, паралельна обробка, рання зупинка для запобігання overfitting. Один з найпопулярніших алгоритмів для змагань з ML.

LightGBM: Швидший за XGBoost завдяки gradient-based one-side sampling та exclusive feature bundling, менше пам'яті.

CatBoost: Особливо ефективний для категоріальних ознак, автоматично обробляє categorical features, стійкий до overfitting.

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

Недоліки: Складніше налаштувати гіперпараметри, повільніше навчання порівняно з Random Forest, менш інтерпретований.

8. Нейронні мережі для класифікації

Глибокі нейронні мережі показали вражаючі результати в класифікації, особливо для складних даних як зображення, текст, аудіо. Вони можуть автоматично виявляти складні нелінійні патерни.

Архітектури: Feedforward networks для табличних даних, Convolutional Neural Networks (CNN) для зображень, Recurrent Neural Networks (RNN, LSTM) для послідовностей, Transformer для тексту.

Активізаційні функції: Sigmoid, tanh, ReLU та його варіанти для прихованих шарів, Softmax для вихідного шару при мультикласовій класифікації.

Переваги: Можуть моделювати складні нелінійні відносини, автоматичне feature extraction, чудова продуктивність на великих датасетах, гнучкість архітектури.

Недоліки: Потребують багато даних, обчислювально інтенсивні, "чорна скринька" (важко інтерпретувати), схильні до overfitting, потребують ретельного налаштування.

📊 Метрики оцінки класифікації

Confusion Matrix

Confusion Matrix — фундаментальний інструмент для оцінки продуктивності класифікації. Для бінарної класифікації це матриця 2x2, що показує:

True Positives (TP): Правильно передбачені позитивні

True Negatives (TN): Правильно передбачені негативні

False Positives (FP): Помилково передбачені позитивні (Type I error)

False Negatives (FN): Помилково передбачені негативні (Type II error)

Основні метрики

Accuracy: (TP + TN) / (TP + TN + FP + FN) — загальна частка правильних передбачень. Може бути оманливою при дисбалансі класів.

Precision: TP / (TP + FP) — частка правильно передбачених позитивів серед усіх передбачених позитивів. Відповідає на питання: "З усіх, що я передбачив як позитивні, скільки дійсно позитивні?"

Recall (Sensitivity): TP / (TP + FN) — частка правильно передбачених позитивів серед усіх реальних позитивів. Відповідає: "З усіх реальних позитивів, скільки я знайшов?"

F1-Score: 2 * (Precision * Recall) / (Precision + Recall) — гармонійне середнє precision та recall. Балансує обидві метрики.

Specificity: TN / (TN + FP) — здатність правильно ідентифікувати негативні випадки.

ROC Curve та AUC

ROC (Receiver Operating Characteristic) крива показує співвідношення True Positive Rate (Recall) та False Positive Rate при різних порогах класифікації. AUC (Area Under Curve) — площа під ROC кривою — скалярна метрика від 0 до 1, де 1 — ідеальна класифікація.

AUC незалежна від порогу класифікації та дає загальну оцінку якості моделі. Значення > 0.9 вважається відмінним, 0.8-0.9 — хорошим, < 0.7 — поганим для бінарної класифікації.

Precision-Recall Curve

Для дисбалансованих датасетів Precision-Recall крива часто інформативніша за ROC. Показує компроміс між precision та recall при різних порогах. PR-AUC також є корисною метрикою.

Метрики для мультикласової класифікації

Macro-averaging: Обчислює метрику для кожного класу окремо та бере середнє (не враховує дисбаланс).

Micro-averaging: Об'єднує всі TP, FP, FN з усіх класів та обчислює метрику (враховує розмір класів).

Weighted averaging: Середнє з урахуванням розміру кожного класу.

🎨 Візуалізація порівняння алгоритмів

Порівняльна таблиця алгоритмів

💡 Рекомендації щодо вибору алгоритму

Вибір на основі розміру датасету

Малі датасети (< 10,000): SVM, Naive Bayes, Decision Trees, Logistic Regression. Ці алгоритми добре працюють з обмеженими даними та не потребують багато обчислень.

Середні датасети (10,000 - 1,000,000): Random Forest, Gradient Boosting (XGBoost, LightGBM), Logistic Regression. Добрий баланс між точністю та швидкістю.

Великі датасети (> 1,000,000): Logistic Regression, LightGBM, Neural Networks з оптимізацією. Алгоритми, які можуть ефективно обробляти великі обсяги даних.

Вибір на основі інтерпретації

Якщо важлива інтерпретація моделі (медицина, фінанси, правові застосування): Decision Trees, Logistic Regression, Linear SVM. Ці алгоритми надають зрозумілі правила або коефіцієнти.

Якщо інтерпретація не критична, але важлива точність: Random Forest, XGBoost, Neural Networks. Можна використовувати feature importance для часткової інтерпретації.

Вибір на основі типу даних

Текст: Naive Bayes, Logistic Regression, SVM, Neural Networks (RNN, Transformer).

Зображення: CNN, Transfer Learning з попередньо навченими моделями.

Табличні дані: Random Forest, XGBoost, Logistic Regression, Neural Networks.

Послідовності: RNN, LSTM, GRU, Transformer.

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Hash Function Avalanche Visualizer і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.