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

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

Історія

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

У 1948 метод був узагальнений індійським математиком ^[en] для довільної кількості класів.

Алгоритм

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

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}}$ в такому випадку — відстань від гіперплощини розділяючої класи до точки даних.

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

Дискримінантний аналіз Фішера

Приклад бінарної класифікації за допомогою класифікатора Фішера. Точковий графік двох класів та гістограма розподілів при проєкції на прямі різної напрямленості

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

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

Нехай ${\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, його можна визначити виходячи з того, що: ${\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})}$

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

При використанні класифікаторів один-проти-всіх жовта область не буде віднесена до жодного класу, а сині — до більш ніж одного класу

При використанні попарних класифікаторів, у жовтій області утвориться цикл 1>2>3>1

Підхід може бути застосований і до більше ніж двох класів. У такому випадку, матриця проєкції ${\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), або через те, що жоден з класифікаторів один-проти-всіх не визначає точку як належну до "свого" класу.

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

Баєсів класифікатор

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

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

Згідно з теоремою Баєса, ймовірність того, що деяке спостереження ${\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}}$

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

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

${\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 дані очікуються нормалізовані, з варіацією всіх ознак рівною одиниці. Для баєсівського класифікатора також важливо щоб усі класи мали багатовимірний гаусів розподіл а матриця коваріації була однаковою в усіх класах.

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

Варіації алгоритму

Квадратичний дискримінантний аналіз

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

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

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

${\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). Її перевага полягає в значно меншій кількості параметрів моделі.

Література

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

Примітки

1. The Use of Multiple Measurements in Taxonomic Problems(англ.)
2. What is Linear Discriminant Analysis ?|Assumptions of Linear Discriminant Analysis | How LDA makes predictions ?|Advantages and Disadvantages of LDA(англ.)
3. Linear Discriminat Analysis(рос.)
4. Linear Discriminant Functions(англ.)
5. Дуда,Харт, 1976, с. 146.
6. A Tutorial on Data Reduction. Linear Discriminant Analysis(англ.)
7. Fisher’s Linear Discriminant: Intuitively Explained(англ.)
8. Threshold Selection Study on Fisher Discriminant Analysis Used in Exon Prediction for Unbalanced Data Sets(англ.)
9. Classification(англ.)
10. Дуда,Харт, 1976, с. 148.
11. Хасті,Тібширані,Фрідман, 2020, с. 132.
12. Хасті,Тібширані,Фрідман, 2020, с. 133.
13. Linear Discriminant Analysis for Machine Learning(англ.)
14. Хасті,Тібширані,Фрідман, 2020, с. 134.
15. Differences between LDA, QDA and Gaussian Naive Bayes classifiers(англ.)