Лінійний розділювальний аналіз

Частина з циклу
Машинне навчання та добування даних
Парадигми Кероване навчання Некероване навчання Інтерактивне навчання Пакетне навчання Метанавчання Напівкероване навчання Самокероване навчання Навчання з підкріпленням Навчання на основі правил Квантове машинне навчання
Задачі Класифікація Породжувальна модель Регресія Кластерування Знижування розмірності Оцінювання густини Виявляння аномалій Очищування даних[en] АвтоМН Асоціативні правила Семантичний аналіз[en] Структурове передбачування Конструювання ознак Навчання ознак Навчання ранжуванню Виведення граматик[en] Навчання онтологій[en] Мультимодальне навчання[en]
Кероване навчання (класифікація • регресія) Ансамблі Випадковий ліс Бутстрепова агрегація Підсилювання Градієнтне підсилювання[en] AdaBoost[en] Дерева рішень MARS[en] CART Доречно-векторна машина k-сусідів Лінійна регресія Логістична регресія Лінійний розділювальний аналіз Наївний баєсів класифікатор Перцептрон Підмайстрове навчання Опорно-векторна машина Штучні нейронні мережі
Кластерування BIRCH[en] CURE Ієрархічне k-середніх Нечітке Очікування-максимізація DBSCAN OPTICS Спектральне Зсув середнього[en]
Знижування розмірності Факторний аналіз Метод незалежних компонент[en] Канонічна кореляція Дискримінантний аналіз Метод головних компонент Власний узагальнений розклад[en] Розклад невід'ємних матриць t-розподілене вкладення стохастичної близькості Навчання розріджених словників[en]
Структурове передбачування Графові моделі Баєсова мережа Прихована марковська модель Умовне випадкове поле
Виявляння аномалій RANSAC k-НС Коефіцієнт локального відхилення Відстань Кука Ізоляційний ліс[en]
Штучна нейронна мережа Автокодувальник Когнітивні обчислення[en] Глибоке навчання DeepDream Нейронна мережа прямого поширення Рекурентна нейронна мережа ДКЧП ВРВ МВС Резервуарне обчислення Обмежена машина Больцмана ГЗМ Дифузійна модель Самоорганізаційна карта Згорткова нейронна мережа U-Net Трансформер Зоровий Спайкова нейронна мережа[en] Мемтранзистор Електрохімічна ПДД[en] (ECRAM)
Навчання з підкріпленням Q-навчання SARSA Метод часових різниць Багатоагентне навчання з підкріпленням Гра проти себе[en]
Навчання з людьми Активне навчання (машинне навчання)[en] Краудсорсинг Людина-в-циклі
Діагностування моделей Крива спроможності навчатися[en]
Математичні засади Ядрові машини Компроміс зсуву та дисперсії Ймовірнісно приблизно коректне навчання Мінімізація емпіричного ризику Оккамове навчання[en] Регуляризація LASSO[en] Тихонова Еластично-сіткова[en] Статистичне навчання Теорія Вапника — Червоненкіса Теорія обчислювального навчання[en]
Місця машинного навчання ECML PKDD[en] NeurIPS[en] ICML[en] ICLR IJCAI ML JMLR
Пов'язані статті Глосарій штучного інтелекту[en] Список наборів даних для досліджень з машинного навчання Перелік понять машинного навчання[en]
п о р

Лінійний дискримінантний аналіз (англ. Linear discriminant analysis, LDA) — статистичний метод для розв'язку задачі класифікації. З його допомогою будуються лінійні комбінації предикторів, що відділяють області одного класу від іншого. LDA працює для будь-якої кількості класів, на відміну від таких методів як логістична регресія, що в першу чергу використовуються для бінарної класифікації.

Лінійний дискримінативний аналіз базується на використанні критерія Фішера, який був описаний британським статистиком і біологом Рональдом Фішером у задачі бінарної класифікації, розділення ірисів за розмірами частин квітки^[1].

У 1948 метод був узагальнений індійським математиком Кальямпуді Радхакришною Рао^[en] для довільної кількості класів^[2].

LDA шукає проєкцію даних у деякий підпростір розмірності ${\displaystyle min(K-1,p)}$ або менше (де ${\displaystyle K}$ — кількість класів, ${\displaystyle p}$ — кількість ознак). Підпростір обирається так, щоб проєкції розподілів, що відносяться до різних класів, були розділені у ньому якомога сильніше. Таким чином класи розділюються за правилом^[3][4]:

1. Кожному класу ставиться у відповідність деяка функція вигляду ${\displaystyle f_{i}(X)=w^{T}X+w_{0}}$. Ці функції називаються дискримінантними функціями. Матриця ${\displaystyle w}$ є матрицею проєкції, ${\displaystyle ||w||=1}$.
2. Кожна точка простору ознак класифікується відповідно до того, яка саме з дискримінантних функцій має найвище значення у ній.

Через те що всі функції є лінійними по Х, границі між областями простору, що відповідають різним класам (decision surface) завжди є гіперплощинами.

У найпростішому випадку двох класів підпростір є одномірним — прямою, і розділення відбувається за правилом :

• ${\displaystyle Class1:w^{T}x+w_{0}>0}$
• ${\displaystyle Class2:w^{T}x+w_{0}<0}$

Геометричний сенс функції ${\displaystyle w^{T}x+w_{0}}$ в такому випадку — відстань від гіперплощини розділяючої класи до точки даних^[5].

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

Історично першою спробою побудувати лінійну дискримінантну модель була модель запропонована Фішером.

Нехай є два класи. Тоді підпростором найкращого розділення буде такий, що при проєктуванні на нього даних максимальним є відношення відстані між середнім значенням класів і розкидом всередині класу^[6].

Нехай ${\displaystyle g_{i}(i=1,2)}$ — елементи класу ${\displaystyle i}$, а ${\displaystyle N_{i}}$ — кількість елементів у цьому класі. Тоді середнє значення по класу дорівнює

${\displaystyle \mu _{i}={\frac {\sum \limits _{x\in g_{i}}x}{N}}}$

${\displaystyle \mu }$ в цьому записі — p-вимірний вектор

середнє проєкції класу (скаляр)

${\displaystyle {\tilde {\mu _{i}}}={\frac {\sum \limits _{x\in g_{i}}w^{T}x}{N}}=w^{T}\mu _{i}}$

розкид всередині класу

${\displaystyle S_{wi}=\sum _{x\in g_{i}}(x-\mu _{i})^{2}=\sum _{x\in g_{i}}(x-\mu _{i})(x-\mu _{i})^{T}}$

розкид всередині проєкції елементів класу

${\displaystyle {\tilde {S}}_{wi}=\sum _{x\in g_{i}}(w^{T}x-{\tilde {\mu _{i}}})^{2}=}$

${\displaystyle =\sum _{x\in g_{i}}(w^{T}x-w^{T}\mu _{i})(w^{T}x-w^{T}\mu _{i})^{T}=}$

${\displaystyle =\sum _{x\in g_{i}}w^{T}(x-\mu _{i})(x-\mu _{i})^{T}w=w^{T}S_{wi}w}$

Тоді функція, максимум якої необхідно знайти:

${\displaystyle J(w)={\frac {({\tilde {\mu _{1}}}-{\tilde {\mu _{2}}})^{2}}{{\tilde {S}}_{w1}+{\tilde {S}}_{w2}}}={\frac {w^{T}S_{b}w}{w^{T}S_{w}w}}}$

Величину ${\displaystyle {\tilde {S}}_{B}=({\tilde {\mu _{1}}}-{\tilde {\mu _{2}}})^{2}=w^{T}S_{b}w}$ називають також міжкласовим розкидом(between-class scatter), тоді як ${\displaystyle {\tilde {S_{w}}}={\tilde {S}}_{w1}+{\tilde {S}}_{w2}=w^{T}S_{w}w}$ — внутрішньокласовим розкидом (within-class scatter matrix).

Продиференціювавши ${\displaystyle J(w)}$ по ${\displaystyle w}$ і прирівнявши результат до нуля отримуємо:

${\displaystyle (w^{T}S_{w}w)2S_{b}w-(w^{T}S_{b}w)2S_{w}w=0}$

ділимо на ${\displaystyle 2w^{T}S_{w}w}$:

${\displaystyle {\frac {w^{T}S_{w}w}{w^{T}S_{w}w}}S_{b}w-{\frac {w^{T}S_{b}w}{w^{T}S_{w}w}}S_{w}w=0}$

тоді

${\displaystyle S_{b}w-J(w)S_{w}w=0}$

${\displaystyle S_{w}^{-1}S_{b}w=J(w)w}$

оскільки ${\displaystyle J(w)}$ — скаляр, задача зводиться до пошуку власних векторів. Найкраще розділення буде досягнуто при проєкції на вектор, що відповідає найбільшому власному значенню.

У випадку двох класів також є більш простий спосіб оцінки w: через те що важливий лише напрямок вектору w, його можна визначити виходячи з того, що^[7]: ${\displaystyle S_{w}^{-1}S_{b}w=S_{w}^{-1}(\mu _{1}-\mu _{2})(\mu _{1}-\mu _{2})^{T}w=S_{w}^{-1}(\mu _{1}-\mu _{2})a}$, де а — скаляр. Таким чином: ${\displaystyle w\propto S_{w}^{-1}(\mu _{1}-\mu _{2})}$

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

Підхід може бути застосований і до більше ніж двох класів. У такому випадку, матриця проєкції ${\displaystyle w}$ має розміри ${\displaystyle K-1\times p}$, а матриця міжкласового розкиду визначається як

${\displaystyle S_{b}=\sum _{j=1}^{K}(\mu _{j}-\mu )(\mu _{j}-\mu )^{T}}$,

де μ — загальне середнє по всіх класах.

У цьому випадку, w складається з ${\displaystyle K-1}$ стовпчиків, що відповідають найбільшим власним векторам матриці ${\displaystyle S_{w}^{-1}S_{b}}$.

Головним чином такий алгоритм для великої кількості класів використовується як спосіб зниження розмірності (дані проєціюються на гіперплощину нижчої розмірності проте класифікатор не будується).

Щоб все ж побудувати модель багатокласової класифікації за цим підходом можна створити ${\displaystyle (K-1)K/2}$ окремих класифікаторів, які будуть попарно порівнювати класи, або ж ${\displaystyle K}$ класифікаторів, кожен з яких робить класифікацію один-проти-решти. Недоліком цього підходу є те, що при ньому деякі зони можуть мати невизначений клас — або через те що створюються цикли класифікацій (клас 2 більш ймовірний ніж клас 1, клас 3 більш ймовірний ніж клас 2, клас 1 більш ймовірний ніж клас 3), або через те, що жоден з класифікаторів один-проти-всіх не визначає точку як належну до "свого" класу^[9][10].

Тому для класифікації у викпадку 3 і більше класів зазвичай використовують описаний нижче баєсів класифікатор.

Баєсів класифікатор застосовується до більш вузького випадку: якщо в усіх класах точки мають однаковий (багатовимірний нормальний) розподіл, що відрізняється лише середнім, тобто, матриці коваріації точок всередині кожного класу однакові^[11].

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

Згідно з теоремою Баєса, ймовірність того, що деяке спостереження ${\displaystyle x}$ належить до класу K, можна оцінити, знаючи розподіл значень всередині класів і ймовірності самих класів ${\displaystyle \pi _{k}}$:

${\displaystyle Pr(G=k|X=x)={\frac {f_{k}(x)\pi _{k}}{\sum \limits _{l=1}^{K}f_{l}(x)\pi _{l}}}}$

Багатовимірний нормальний розподіл точок що відносяться до класу ${\displaystyle k}$ задається як:

${\displaystyle f_{K}(x)={\frac {1}{(2\pi )^{p/2}\left|\Sigma _{k}\right|^{1/2}}}e^{-{\frac {1}{2}}(x-\mu _{k})^{T}\Sigma _{k}^{-1}(x-\mu _{k})}}$

де ${\displaystyle \mathbf {x} \in \mathbb {R} ^{p}}$, а ${\displaystyle \Sigma _{K}}$ — матриця коваріації.

Виразимо тоді логарифм співвідношення ймовірностей того, що спостереження x відноситься до класу ${\displaystyle k}$ і ${\displaystyle l}$, припускаючи що матриці коваріації ${\displaystyle \Sigma }$ однакові для всіх класів (через що члени з ${\displaystyle x^{2}}$ скорочуються:

${\displaystyle log{\frac {Pr(G=k|X=x)}{Pr(G=l|X=x)}}=\log {\frac {f_{k}(x)}{f_{l}(x)}}+\log {\frac {\pi _{k}}{pi_{l}}}=\log {\frac {\pi _{k}}{pi_{l}}}-{\frac {1}{2}}(\mu _{k}+\mu _{l})^{T}\Sigma ^{-1}(\mu _{k}-\mu _{l})+x^{T}\Sigma ^{-1}(\mu _{k}-\mu _{l})}$

Тоді функції

${\displaystyle \delta _{k}=\log \pi _{k}+x^{T}\Sigma ^{-1}\mu _{k}-{\frac {1}{2}}\mu _{k}^{T}\Sigma ^{-1}\mu _{k}}$

і будуть питомими дискримінантними функціями. Спостереження належить до того класу, який має максимальну дискримінантну функцію у відповідній точці.

Параметри функції визначаються з вибіркових даних^[12]:

${\displaystyle {\hat {\pi }}_{k}=N_{k}/N}$

${\displaystyle {\hat {\mu }}_{k}=\sum _{x\in g_{k}}x/N_{k}}$

${\displaystyle {\hat {\Sigma }}=\sum _{k=1}^{K}\sum _{x\in g_{k}}(x-{\hat {\mu }}_{k})(x-{\hat {\mu }}_{k})^{T}/(N-K)}$

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

Аналіз чутливий до викидів тому бажано перевірити дані і видалити їх до початку роботи^[13].

Якщо матриці коваріації не рівні, то скорочення квадратичних членів не відбувається. Відповідно, границі між класами будуть описуватися кривими другого порядку а не гіперплощинами, а кількість параметрів можелі сильно зросте. Така модель називається квадратичним дискримінантним аналізом (QDA).

Схожі результати можна отримати, додаючи в модель складні предиктори, наприклад, якщо до моделі з двома предикторами ${\displaystyle x_{1}}$ і ${\displaystyle x_{2}}$ додати ще три, які дорівнюють ${\displaystyle x_{1}^{2},x_{1}x_{2},x_{2}^{2}}$, отримане лінійне рівняння відносно п'яти параметрів буде квадратичним відносно ${\displaystyle x_{1}}$ і ${\displaystyle x_{2}}$. Проте, ці два підходи не є ідентичними, і отримані поверхні розділення класів різні, хоча часто різниця є невеликою^[14].

Можливі проміжні варіанти, де в якості матриці коваріації класу використовується матриця

${\displaystyle \Sigma (a)_{k}=(1-a)\Sigma _{k}+a\Sigma ^{*}}$

де ${\displaystyle a}$ — деякий параметр від 0 до 1, а ${\displaystyle \Sigma ^{*}}$ — середня матриця коваріації по всіх класах (така як використовується в LDA)

Матрицю коваріації в LDA можна замінити на

${\displaystyle \Sigma (\gamma )=(1-\gamma )\Sigma +\gamma I\sigma ^{2}}$,

де I — одинична матриця, ${\displaystyle \gamma }$ — параметр від 0 до 1, ${\displaystyle \sigma }$ — вектор стандартного відхилення кожного параметру всередині класу. Таким чином матриця стає ближчою до діагональної і вплив коваріацій зменшується. У крайньому випадку ${\displaystyle \gamma =1}$ всі змінні вважаються незалежними. Така модель називається наївною гаусівською баєсовою (англ. Gaussian Naive Bayes)^[15]. Її перевага полягає в значно меншій кількості параметрів моделі.

• Багатовимірне шкалювання
• Добування даних
• Квадратичний класифікатор(інші мови)
• Лінійна регресія
• Логіт (щодо логістичної регресії)
• Навчання дерев рішень
• Розпізнавання образів
• Статистична класифікація
• Факторний аналіз
• Ядровий фішерів розділювальний аналіз(інші мови)

• Хасті Т., Тібширані Р., Фрідман Дж. Основы статистического обучения. — 2. — Київ : «Діалектика», 2020. — 768 с. — ISBN 978-617-7812-91-2.
• Дуда Р.,Харт П. Распознавание образов и анализ сцен. — М. : «Мир», 1976. — 507 с.