Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Systemy decyzyjne – 3. Metody oceny klasyfikatorów – MIM UW

Zagadnienia

3. Metody oceny klasyfikatorów

3.1. Metody oceny klasyfikatorów

3.1.1. Skuteczność predykcji

\block

Błąd klasyfikacji

\textit{Błąd klasyfikacji}=\frac{\textit{liczba błędów}}{\textit{liczba obiektów testowych}}

gdzie:

  • Sukces: gdy obiekt jest prawidłowo klasyfikowany

  • Błąd: gdy obiekt jest źle klasyfikowany

  • Błąd klasyfikacji (lub odsetka błędów podczas klasyfikacji) powinien być wyznaczony na losowych i nieznanych danych.

  • Są dwa rodzaje błędu:

  • W “systemach uczących się”: minimalizujemy FP+FN lub miarę skuteczności (ang. Accuracy) (ACC):

    ACC=(TP+TN)/(TP+FP+TN+FN)
  • W marketingu: maksymalizujemy TP.

  • Podział zbioru danych na część treningową i testową;

  • Uczenie lub poszukiwanie modelu

  • Ocena klasyfikatora

  • Niektóre metody uczenia działają w dwóch etapach:

  • Etap 1: Buduje strukturę

  • Etap 2: Optymalizuje parametry

\block

Uwaga: Nie używaj danych testowych do budowy klasyfikatorów!

  • Właściwa procedura powinna zawierać 3 zbiory: treningowe, walidacyjne i testowe

  • Dane walidacyjne używane są do optymalizacji parametrów

3.1.2. Przedział ufności miar ocen

  • Przykład: S=750 sukcesów w N=1000 próbach

    • Estymowana skuteczność: 75\%

    • Jak bliska jest ta estymacja do prawdziwej skuteczności p?

    • Odp: z 80\% pewności możemy twierdzić, że p\in[73.2,76.7]

  • Inny przykład: S=75 i N=100

    • Estymowana skuteczność: 75\%;

    • p\in[69.1,80.1] z 80\% pewności.

  • Rozpatrujemy rozkład Bernoulliego: p,p(1-p)

  • Oczekiwany odsetek sukcesu w N próbach: f=S/N

  • Wartość oczekiwana i wariancja dla f:

    p,p(1-p)/N
  • Dla dużych N, zm.l. f ma rozkład zbliżony do rozkładu normalnego;

  • [–z\leq X\leq z] nazywamy przedziałem ufności na poziomie c\% dla zm.l. X o zerowej wartości oczekiwanej wtw:

    P[-z\leq X\leq z]=c
  • Dla rozkładu symetrycznego mamy:

    P[-z\leq X\leq z]=1-2P[X\geq z]
  • Wartość oczekiwana i wariancję dla f: p,p(1-p)/N

  • Normalizacja zm. f:

    \frac{f-p}{\sqrt{p(1-p)/N}}
  • Mamy równanie na p:

    Pr\left(-z\leq\frac{f-p}{\sqrt{p(1-p)/N}}\leq z\right)=c
  • Rozwiązanie dla p: p\in[p_{1},p_{2}], gdzie

    p_{{1,2}}=\frac{f+\frac{z^{2}}{2N}\pm z\sqrt{\frac{f}{N}-\frac{f^{2}}{N}+\frac{z^{2}}{4N^{2}}}}{1+\frac{z^{2}}{N}}

3.1.3. Metody walidacji danych

Ogólna zasada:

  • Im większy zbiór treningowy, tym lepszy jest klasyfikator

  • Im większy jest zbiór testowy, tym lepiej można aproksymować błąd klasyfikacji.

\block

Praktyczna rada: Kiedy proces oceniania się zakończy, wszystkie dane mogą być wykorzystywane do skonstruowania ostatecznego klasyfikatora

  • Walidacja krzyżowa nie pozwala na wielokrotne testowanie tego samego obiektu

    • Krok 1: Podział zbioru danych na k równych podzbiorów

    • Krok 2: Testowanie każdego podzbioru używając pozostałych jako zbiór treningowy

  • To się nazywa k-CV = k-fold cross-validation

  • Zwykle obiekty są przetasowane przed dokonaniem podziału.

  • Błędy wszystkich iteracji są uśrednione, aby otrzymać błąd globalny.

  • Standardowa metoda ocena klasyfikatorów: 10-krotna walidacja krzyżowa

  • Liczba 10 została wyznaczona w wyniku wielu doświadczeń.

  • Walidacja pozwala na zmniejszenie długości przedziału ufności

  • Jeszcze lepsza metoda oszacowania parametrów:

    Walidacja z powtórzeniami!

  • Leave-one-out: przypadek szczególny walidacji krzyżowej Liczba grup = liczba przykładów

    • Dla n obiektów budujemy klasyfikator n razy

    • Najlepiej ocenia klasyfikatora

    • Obliczeniowo kosztowna metoda (wyjątek: kNN)

  • Bootstraping: próbkuje ze zwracaniem, żeby stworzyć różne zbiory treningowe i testowe

    • Próbkuje ze zwracaniem n razy

    • Wybrane obiekty tworzą zbiór treningowy

    • Reszta – zbiór testowy.

3.1.4. Krzywy Lift i ROC

  • Miara “sensitivity” lub “true positive rate” (TPR)

    TPR=TP/(TP+FN)

    czasem nazywa się też “recall” lub “hit rate”.

  • Specificity (SPC) lub True Negative Rate SPC=TN/(FP+TN)

  • false positive rate (FPR): FPR=FP/(FP+TN)=1-FPC

  • positive predictive value (PPV) lub precision: PPV=TP/(TP+FP)

  • negative predictive value (NPV): NPV=TN/(TN+FN)

  • false discovery rate (FDR): FDR=FP/(FP+TP)

  • Matthew's correlation coefficient (MCC)

    MCC=\frac{TP\times TN-FP\times FN}{\sqrt{(TP+FN)(TP+FP)(FN+TN)(FP+TN)}}
  • F1 score: F1=2TP/[(TP+FN)+(TP+FP)] lub

    \frac{1}{F1}=\frac{\frac{1}{recall}+\frac{1}{precision}}{2}
\block

Funkcje

  • p - parametr określający początek listy rankingowej

  • CPH - (ang. Cumulative Percentage Hit)

    CPH(p) = część klasy docelowej znajdująca się wsród p\% pierwszych obiektów z listy rankingowej.

  • zysk (ang. lift): Lift(p)=CPH(p)/p

  • Trafienie lub true positive rate: TPR(p)=TP/(TP+FN)

  • Odsetek fałszywych alarmów FPR(p)=FP/(FP+TN)

\block

Wyróżnione krzywy

  • Gain chart:

    Ox:p

    Oy:CPH(p)

  • Lift chart:

    Ox:p

    Oy:Lift(p)

  • ROC (receiver operating characteristic):

    Ox:FPR(p)

    Oy:TPR(p)

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.