1 Linear Methods of ClassificationT. Hastie, R. Tibshirani, J. Friedman „The Element of Statistical Learning” Chapter 4 Linear Methods of Classification

2

3 Metody klasyfikacji liniowejWyznaczanie liniowej funkcji dyskryminacyjnej dla każdej z klas: Regresja liniowa Liniowa analiza dyskryminacyjna Regresja logistyczna Wyznaczanie liniowych hiperpłaszczyzn rozdzielających klasy: ‘Separating Hyperplanes’

4 Funkcja dyskryminacyjna k(x)Postać funkcji dyskryminacyjnej k(x): W zależności od modelu: regresja liniowa analiza dyskryminacyjna regresja logistyczna Hiperpłaszczyzna rozgraniczająca klasy k oraz l: Nowa obserwacja zaklasyfikowana do grupy o największej wartości k(x)

5

6 Regresja liniowa Estymacja modelu liniowego (MNK): (1) (2)Wartości funkcji dla nowej obserwacji (K wektor): (3) Reguła dyskryminacyjna: (4)

7 Maskowanie klas Gdy K > 2 istnieje niebezpieczeństwo maskowania klas.

8 Estymacja za pomocą funkcji kwadratowej, zamiast liniowej.Generalnie, dla k klas wymagany wielomian stopnia k-1. Duża złożoność obliczeniowa.

9 Liniowa analiza dyskryminacyjnaLiniowa i kwadratowa analiza dyskryminacyjna ‘Regularized discriminant analysis’ ‘Reduced-rank linear discriminant’

10 Reguła Bayesa Funkcja gęstości (wiarygodność): orazPrawdopodobieństwo a priori: oraz Prawdopodobieństwo a posteriori: (5)

11 Funkcja gęstości Zmienne mają łącznie wielowymiarowy rozkład normalny.(6) Wspólna macierz wariancji i kowariancji  dla wszystkich klas. (7)

12 Estymacja parametrów Prawdopodobieństwo a piori: (8)Wektor wartości średnich: (9) Macierz wariancji i kowariancji: (10)

13 Dyskryminacja liniowa a regresjaKlasyfikacja binarna: hiperpłaszczyzny są równoległe. Więcej niż dwie klasy: różnica pomiędzy rozwiązaniami. Nie występuje problem maskowania klas [Hastie et al, 1994].

14 Dyskryminacja kwadratowaDwa podejścia: Brak założenia o równości macierzy wariancji i kowariancji. Zwiększenie wymiaru przestrzeni cech: X1, X2  X1, X2, X1X2 , X12, X22 Podobne rezultaty.

15 ‘Regularized discriminant analysis’Kompromis pomiędzy dyskryminacją liniową a kwadratową [Friedman, 1989]. Postać macierzy kowariancji: (11)

16 ‘Reduced-rank linear discriminant’Redukcja wymiaru przestrzeni cech pozwala na lepszą identyfikację istotnych różnic między klasami. Redukcja ta jest możliwa dopóki liczba cech P  K-1. Analiza głównych składowych.

17 Regresja logistyczna Liniowe logarytmy ilorazów wiarygodności: (12)Rozwiązanie: (13) (14)

18 Estymacja parametrów Metoda największej wiarygodności Funkcja wiarygodności: (15) Logarytm funkcji wiarygodności (względy obliczeniowe): (16) Szukamy maksimum L().

19 Przykład: klasyfikacja binarnaWskaźnik y = 1 dla klasy 1 oraz y = 0 dla klasy 2 Prawdopodobieństwo a posteriori: p1(x; ) = p(x;) p2(x;) = 1-p(x;) Logarytm funkcji wiarygodności: (17)

20 Obliczanie  (18) P+1 równań nieliniowych względem Iteracyjna metoda wyznaczania  - algorytm Newton-Raphson: (19)

21 Dyskryminacja liniowa:(20) Regresja logistyczna: (21)

22 ‘Separating Hyperplanes’Metoda perceptronowa [Rosenblatt, 1958] ‘Optimal Separating Hyperplanes’

23 Metoda perceptronowa RosenblattaKryterium perceptronowe: Minimalizacja odległości pomiędzy źle sklasyfikowanymi obiektami a hiperpłaszczyzną. (22) Algorytm: metoda najszybszego spadku (23)

24 Wady Zadania liniowo separowalne: wiele rozwiązań w zależnościod punktu startowego. Algorytm może zbiegać w bardzo długim czasie. Zadania nieseparowalne liniowo: algorytm nie jest zbieżny.

25 ‘Optimal Separating Hyperplane’Kryterium: Maksymalizacja odległości pomiędzy hiperpłaszczyzną a najbliższymi obiektami. Jedno rozwiązanie. Lepsza klasyfikacja elementów zbioru testowego.

26 W skrócie... Regresja liniowa i problem maskowania klasDyskryminacja liniowa z założeniem normalnego rozkładu funkcji gęstości Regresja logistyczna ‘Separating Hyperplanes’