Статистичні алгоритми

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

Статистичні алгоритми машинного навчання — це методи, що базуються на математичній статистиці та теорії ймовірностей. Вони спроможні виявляти закономірності в даних, робити передбачення та приймати рішення. Їхня головна ідея полягає в тому, щоб побудувати модель, яка найкраще описує залежність між вхідними даними (ознаками) та вихідними значеннями (мітками або цільовою змінною).

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

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

До статистичних алгоритмів також належать методи, що враховують варіації та розподіли даних, наприклад, метод k-середніх для кластеризації або метод опорних векторів (SVM), який шукає оптимальну межу між класами. Хоча деякі з цих алгоритмів не є суто ймовірнісними, вони використовують статистичні принципи для оцінки якості моделей.

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

Наївний Байєс для класифікації спаму

Наївний Байєс (Naive Bayes) — це популярний алгоритм контрольованого навчання, який використовується для завдань класифікації. Є особливо ефективним в обробці природної мови, аналізі текстів та фільтрації спаму. Алгоритм базується на теоремі Байєса і передбачає, що наявність конкретної ознаки в класі не залежить від наявності інших ознак. Алгоритм розглядає кожну ознаку як таку, що незалежно впливає на ймовірність певного результату.

Приклад Наївного Байєсівського класифікатора

Як працює алгоритм

• Токенізація, розділення тексту на окремі слова.
• Підрахунок частот, скільки разів кожне слово з'являється у спамі та не спамі.
• Згладжування Лапласа: P(слово|клас) = (кількість + 1) / (всього + розмір_словника).
• Теорема Байєса: P(клас|текст) ∝ P(клас) × ∏ P(слово|клас).
• Використання логарифму для уникнення антипереповнення.
• Математика: P(спам|текст) = P(спам) × P(слово1|спам) × P(слово2|спам) × ...

Рис.1. JS-демонстрація вирішення задачі класифікації за алгоритмом Наївного Байєсу (відкрити)

Cистема прийняття рішень на основі Дерева рішень

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

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

Приклад Дерева рішень для ухвалення видачі позики

В даному прикладі задіяно Числові пороги (дохід, вік, сума кредиту) та Категоріальні атрибути (історія, робота, застава). Кредитна історія - головний фактор

Рис.2. JS-демонстрація вирішення задачі класифікації за алгоритмом Дерева Рішень (відкрити)

Лінійна регресія

Проста лінійна регресія (Simple Linear Regression) моделює зв'язок між незалежною та залежною змінними у вигляді лінії. Залежна змінна повинна бути неперервною/реальною величиною, що є важливим аспектом аналізу. Незалежна змінна може бути обчислена з використанням безперервних або категоріальних значень.

Основними цілями алгоритму простої лінійної регресії є

• Створення моделі, яка відображає взаємозв'язок між двома змінними. Наприклад, співвідношення доходу до витрат, співвідношення метражу квартири до її ціни тощо.
• Передбачення нових результатів, наприклад, ціна квартири на основі її метражу, дохід компанії на основі річних витрат.

Інтерактивний графік на прикладі:

• Вісь X: Площа квартири (0-150 м²)
• Вісь Y: Ціна (0-3 млн.грн)

Лінійна регресія (метод найменших квадратів):

• Знаходження оптимальної прямої: y = mx + b
• m (slope) - наскільки зростає ціна при збільшенні площі на 1 м²
• b (intercept) - базова ціна
• R² - коефіцієнт детермінації (0-1), якість моделі

Математика:

• m = Σ[(x_i - x̄)(y_i - ȳ)] / Σ[(x_i - x̄)²]
• b = ȳ - m·x̄
• R² = 1 - (SS_res / SS_tot)

Рис.3. JS-демонстрація вирішення задачі передбачення за алгоритмом лінійної регресії (відкрити)

Алгоритм кластеризації K-Means

Алгоритм k-means використовують для групування об'єктів у набори (кластери) на основі їхньої схожості. В основу роботи k-means покладено принцип мінімізації відстані між об'єктами всередині одного кластеру.

Спочатку вибираються кілька центрів для груп (наприклад, для трьох груп – три центри). Далі алгоритм розподіляє всі об’єкти по групах, визначаючи, до якого центру вони ближче. Після цього він переобчислює центри нових груп і повторює процес, доки центри не перестануть сильно змінюватися. Це надає можливість створити групи з об’єктами, схожими між собою.

Алгоритм, показаний на прикладі:

• Ініціалізація K-Means. Розумний вибір початкових центроїдів.
• Кожна точка призначається найближчому центроїду.
• Центроїди переміщуються в центр мас своїх точок.
• Кроки до збіжності або досягнення ліміту ітерацій.

Рис.4. JS-демонстрація вирішення задачі кластеризації за методом k-means (відкрити)

Алгоритм кластеризації DBSCAN

DBSCAN (density-based spatial clustering of applications with noise) — алгоритм кластеризації даних, що засновано на щільності об’єктів. Для заданої множини об’єктів в деякому просторі алгоритм відносить до одної групи об’єкти, які розташовані найбільш щільно (об’єкти з багатьма сусідами) та помічає об’єкти, які знаходяться в областях з невеликою щільністю (чиї сусіди розташовані занадто далеко) як шум (викиди).

Приклад алгоритму DBSCAN

Алгоритм, показаний на прикладі:

• Для кожної точки шукає сусідів в радіусі epsilon.
• Epsilon (ε) - радіус околу для пошуку сусідів (10-100).
• Якщо знайдено >= minPoints сусідів - формує кластер.
• MinPoints - мінімальна кількість точок для формування кластера (2-10).
• Алгоритм рекурсивно розширює кластер, додаючи сусідів сусідів.
• Точки без достатньої кількості сусідів позначаються як шум.

Рис.5. JS-демонстрація вирішення задачі кластеризації за методом DBSCAN (відкрити)

Q-навчання

Ця демонстрація відповідає опису алгоритму глибокого навчання з підкріпленням Q-Learning.

• 2D-агент, в якого 9 очей спрямовані під різними кутами вперед.
• Кожне око сприймає 3 значення вздовж свого напрямку (до певної максимальної відстані видимості):
  • відстань до стіни
  • відстань до зеленого предмета
  • відстань до червоного предмета
• Агент орієнтується, використовуючи одну з 5 дій, які повертають його під різними кутами.
• Червоні предмети – це їжа, і агент отримує винагороду за їх з'їдання.
• Зелені предмети – це отрута, і агент отримує негативну винагороду за їх з'їдання.

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

Рис.6. JS-демонстрація навчання з підкріпленням Q-Learning (відкрити)

Реалізації статистичних алгоритмів у Python

Для реалізації статистичних алгоритмів у Python існує кілька спеціалізованих бібліотек.

• Основна бібліотека (№1 для статистичних алгоритмів) scikit-learn
• Наївний Байєс sklearn.naive_bayes
• Дерева рішень sklearn.tree
• Лінійна регресія sklearn.linear_model, statsmodels (для статистичного аналізу)
• K-найближчих сусідів sklearn.neighbors
• Метод опорних векторів sklearn.svm
• K-Means, DBSCAN sklearn.cluster
• Q-Learning NumPy