Zagadnienia

7. Klasyfikacja

Zadanie klasyfikacji polega na konstrukcji funkcji (klasyfikatora), która na podstawie zaobserwowanych cech będzie przydzielała obserwację do którejś z wcześniej zdefiniowanych grup. Do estymacji funkcji potrzebne są obserwacje, które już zostały sklasyfikowane, będziemy je nazywać próbą uczącą:

yi,Xii1,,n niezależne obserwacje, XiRpyi1,,K.

Dane Xi oznaczają zaobserwowane cechy, yi grupę, do której obserwacja została zaklasyfikowana.

Cj oznaczaja zbiór tych indeksów i, że yi=j; C1,,CK są rozłączne o licznościach odpowiednio n1,,nK.

Funkcja wiarygodności dla opisanych danych wyraża się wzorem:

Lπ1,,πK,θ1,,θK=i=1ngyi,Xi=i=1nπyifθyiXi
pod warunkiem: k=1Kπk=1.

Logwiarygodność to logarytm funkcji wiarygodności:

l=logL;
l=i=1nlogπyi+i=1nlogfθyiXi.

Zadanie klasyfikacji dzielimy na dwa kroki:

  1. Estymujemy parametry π1,,πK oraz θ1,,θK na podstawie zaobserwowanych par yi,Xi przy użyciu metody największej wiarygodności. Parametry πk możemy interpretować jako prawdopodobieństwa przynależności do danej grupy danych, a θk jako parametry rozkładu w danej grupie (na przykład dla wielowymiarowego rozkładu normalnego, byłyby to średnia μ i macierz kowariancji Σ).

  2. Obserwujemy nowe cechy Xn+1 i przyporządkowujemy im y^i+1 na podstawie zbudowanego przez nas klasyfikatora. Będziemy go także nazywać regułą decyzyjną.

Maksymalizujemy funkcję wiarygodności pod warunkiem k=1Kπk=1 przy użyciu metody mnożników Lagrange'a:

maxπ1,,πK,θ1,,θKFπ1,,πK,θ1,,θK=
maxπ1,,πK,θ1,,θKn1logπ1++nKlogπK-λk=1Kπk-1+
+iC1logfθ1Xi+iCKlogfθKXi.

Liczymy estymatory π^1,,π^K:

Fπk=nkπk-λ=0k=1,K; (7.1)
Fλ=k=1Kπk-1=0; (7.2)

Z równań 7.1 otrzymujemy:

k=1,Knkλ=πk.

Sumujemy po k korzystając z równania 7.2 :

nλ=1λ=nπ^k=nkn.

Estymację parametrów θk odłożymy do dalszej części wykładu.

7.1. Optymalna reguła decyzyjna

Zobaczmy teraz, jak można zdefiniować optymalny klasyfikator w zależności od funkcji straty karzącej za błędne sklasyfikowanie danych.

Definicja 7.1

Funkcja straty to funkcja przyporządkowująca nieujemną wielkość kary poprzez porównanie prawdy (założymy chwilowo, że ją znamy) do podjętej decyzji (wyliczonego estymatora):

L:Kprawda×KdecyzjaR+kara.

Przykładową funkcją kary dla ciągłego y jest Ly,y^=y-y^2.

Mając wyestymowaną regułę decyzyjną sensownym jest rozpatrywanie średniej straty dla naszego klasyfikatora:

Definicja 7.2

Ryzyko reguły decyzyjnej dla d:RpK:

Ryzyko=średnia strata reguły decyzyjnej d=
=R(d)=yKRpL(y,d(X))g(y,X)dX=

gdzie gy,X jest gęstością łącznego rozkładu danych. Z twierdzenia o prawdopodobieństwie całkowitym:

=k=1K[RpL(k,d(X))f(X|k)dX]πk.
Definicja 7.3

Optymalna reguła decyzyjna d* to taka reguła decyzyjna, że

dRd*Rd.
Definicja 7.4

Reguła bayesowska dBX to reguła decyzyjna, która lokalnie dla danego X spełnia warunek:

dBX=argmin1lKEy|XLy,l=
=argminlk=1KL(k,l)p(k|X)=

ze wzoru Bayesa:

=argminl[k=1KL(k,l)πkf(X|k)s=1Kπsf(X|s)]=
=argminl[k=1KL(k,l)πkf(X|k)].
Stwierdzenie 7.1
RdB=Rd*.

Reguła bayesowska jest optymalną regułą decyzyjną.

Dla dowolnej reguły decyzyjnej d zachodzi:

R(d)=k=1K[RpL(k,d(X))f(X|k)dX]πk=
=Rp[k=1KL(k,d(X))πkf(X|k)]dX
Rp[min1lkk=1KL(k,l)πkf(X|k)]dX=
=Rp[k=1KL(k,dB(X))πkf(X|k)]dX=R(dB).

7.2. Wielowymiarowy rozkład normalny

W dalszej części wykładu będziemy zakładać, że fθi mają rozkłady normalne. Dlatego przyjrzyjmy się bliżej własnościom wielowymiarowego rozkładu normalnego i estymacji jego parametrów metodą najwiękzej wiarygodności.

Definicja 7.5

Wektor losowy X=x1,,xp ma rozkład wielowymiarowy normalny w Rp jeśli uRp uTX ma rozkład normalny w R. Oznaczmy ten rozkład poprzez Nμ,Σ, gdzie μ=Ex, Σ=VarX.

Twierdzenie 7.1

Jeżeli X ma rokład normalny w Rp, to aRk i macierzy A wymiaru k×p, AX+a ma rozkład normalny w Rk.

 uRkuTAX+a=uTaX+uTa.
Wniosek 7.1

Rozkłady brzegowe wielowymiarowego rozkładu normalnego są normalne w odpowiednich podprzestrzeniach Rp.

Twierdzenie 7.2

Fcja charakterystyczna zmiennej losowej X o rozkładzie normalnym w Rp jest postaci:

φXt=eitTμ-12tTΣt. (7.3)

Także na odwrót: jeżeli Σ jest symetryczną macierzą dodatnio określoną o wymiarach p×p, to φX określona w równaniu 7.3 jest funkcją charakterystyczną wektora losowego o rozkładzie normalnym w Rp.

Wniosek 7.2

Dowolna macierz symetryczna dodatnio określona o wymiarach p×p jest macierzą kowariancji wektora losowego o rokładzie normalnym w Rp.

Twierdzenie 7.3

Gęstość wielowymiarowego rozkładu normalnego Nμ,Σ:

fX=12πp2detΣ=Σ12exp-12X-μTΣ-1X-μ.
Twierdzenie 7.4

Jeżeli X ma rozkład normalny w Rp: Nμ,Σ, to współrzędne wektora X są niezależne Σ jest diagonalna. Dla rozkładu normalnego brak korelacji oznacza niezależność.

Twierdzenie 7.5

Jeżeli XNμ,σ2I, C jest macierzą ortonormalną o wymiarach p×p, to:

CXNCμ,Cσ2ICT=NCμ,σ2CCT=I=NCμ,σ2I.

7.2.1. Estymatory największej wiarygodności dla rozkładu normalnego Nμ,Σ

Niech X1,,Xn będą niezależnymi wektorami losowymi z p-wymiarowego rozkładu Nμ,Σ. Znajdziemy estymatory dla parametrów μ i Σ. Łączna funkcja wiarygodności dla n wektorów losowych:

Lμ,Σ=i=1n12πp2Σ12exp-12Xi-μTΣ-1Xi-μ.

Najpierw szukamy estymatora μ^; w tym celu opuszczamy wszystkie wyrazy nie zalezeżące od μ, które by się wyzerowały po policzeniu pochodnej. Dla prostoty obliczeń maksymalizujemy podwojoną logwiarygodność:

2logLμ=2lμ=nμTΣ-1-2nμTΣ-1X¯,

gdzie X¯=1ni=1nXi.

Przypomnijmy fakt:

Lemat 7.1

Oznaczmy: a,b – wektory tej samej długości p, A macierz o wymiarach p×p.

aTba=bTaa=b.
bTAbb=A+ATb=2Ab jeśli A symetryczna.

Skorzystajmy z lematu 7.1 żeby obliczyć pochodną logwiarygodności:

1n2lμμ=2Σ-1μ-2Σ-1X¯=0,

stąd

μ^=X¯,

czyli estymatorem największej wiarygodności dla średniej rozkładu normalnego jest średnia arytmetyczna obserwacji.

Ponieważ optymalne μ^ nie zależy od Σ, przy obliczaniu Σ^ możemy wstawić X¯ za μ. Maksymalizujemy po Σ wyrażenie:

L(X¯,Σ)|Σ|-n2exp[-12i=1n(Xi-X¯)TΣ-1(Xi-X¯).]

Symbol oznacza proporcjonalność, możemy opuścić wszystkie stałe, które nie wpływają na wynik optymalizacji.

Ponieważ (Xi-X¯)TΣ-1(Xi-X¯) jest liczbą, a trliczba=liczba, oraz trAB=trBA, otrzymujemy:

LX¯,ΣΣ-n2exp-12i=1ntrXi-X¯Xi-X¯TΣ-1=

ślad macierzy jest funkcją liniową argumentu, więc zachodzi:

=|Σ|-n2exp[-12tr{Xi-X¯Xi-X¯T=SΣ-1}]=

pomnóżmy i podzielmy przez Sn2

=S-n2SΣ-1n2exp-12trSΣ-1.

Ponieważ S-n2 nie zależy od Σ, możemy to wyrażenie opuścić. Podstawmy B=SΣ-1:

LX¯,BBn2exp-12trB.
Lemat 7.2

Dla macierzy kwadratowej A o wymiarach p×p zachodzi:

detA=i=1pλi,
trA=i=1pλi,

gdzie λi to wartości własne macierzy.

Korzystając z lematu 7.2:

Bn2exp-12trB=j=1pλjn2e-12λj

Zmaksymalizujmy to wyrażenie po każdej wartości własnej λj, co sprowadza się do maksymalizacji po λ funkcji:

Fλ=λn2e-12λ;
logFλ=n2logλ-12λ;
logFλλ=n2λ-12=0;

skąd λ^=λ1^==λp^=n.

Macierzą o wszystkich wartościach własnych równych n jest nI:

B=SΣ-1=nI,

skąd:

Σ^=1nS=1nXi-X¯Xi-X¯T,

czyli estymatorem największej wiarygodności dla macierzy kowariancji rozkładu normalnego jest obciążony estymator próbkowy macierzy kowariancji.

7.3. Klasyfikacja w modelu normalnym

Zrobimy dwa założenia dotyczące rozważanego wcześniej klasyfikatora:

  1. Funkcja straty jest postaci:

    Lk,l=1kl.
  2. W każdej z grup dane pochodzą z rozkładu normalnego, czyli fθk to gęstość rozkładu normalnego, θk=μk,Σk.

Dal zadanej funkcji straty optymalna (bayesowska) reguła decyzyjna będzie miała postać:

dB(X)=argminl[k=1KL(k,l)πkf(X|k)]=argminl[k=1K1klπkf(X|k)]=
=argminl[k=1Kπkf(X|k)nie zależy od wyboru l-πlf(X|l)]=argmaxl[πlf(X|l)].

Znamy już postać szukanego klasyfikatora, potrzebujemy jeszcze estymatorów dla występujących w nim parametrów. Wiemy jak wyglądają estymatory π^k:

π^k=nkn,nk=i=1n1yi=k.

Estymatory największej wiarygodności dla parametrów θk przy założeniu normalności rozkładów w grupach są postaci:

μk^=1nkiCkXi=i=1nXi1yi=ki=1n1yi=k;
Σk^=1nkiCkXi-Xk¯Xi-Xk¯T,

gdzie Xk¯ oznacza wektor średnich obserwacji dla XiCk.

Dla X niezależnego od próby uczącej: y1,X1,,yn,Xn estymator reguły decyzyjnej ma postać:

d^X=argmax1lKπl^fμ^l,Σ^lX.

7.3.1. Kwadratowa (qda) i liniowa (lda) funkcja klasyfikacyjna

W zależności od założeń dotyczących parametrów, możemy otrzymać klasyfikator będący różną funkcją swojego argumentu X: albo kwadratową albo liniową.

Kwadratowa funkcja klasyfikacyjna (qda) nie wymaga dodatkowych założeń o parametrach:

dX=argmaxlπlfμl,Σl=
=argmaxl[πl2πp2Σl12exp{-12(X-μl)TΣl-1(X-μl)}]=

po opuszczeniu wyrażeń niezależnych od l i zlogarytmowaniu:

=argmaxllogπl-12logΣl-12X-μlTΣl-1X-μl,

czyli kwadratowa funkcja argumentu X.

Liniowa funkcja klasyfikacyjna (lda) wymaga założenia:

Σ1==ΣK=Σ.

Dzięki niemu mamy podwójny zysk obliczeniowy: o K-1 parametrów mniej do wyestymowania i liniową funkcję optymalizowaną:

dX=argmaxllogπl-12logΣl-12X-μlTΣl-1X-μl=

ponieważ logΣ oraz XTΣ-1X nie zależy od l,

=argmaxllogπl+XTΣ-1μl-12μlTΣ-1μl.

7.4. Metody porównywania klasyfikatorów

Chcemy znaleźć taką metodę porónywania, żeby każdą obserwację spośród y1,X1,,yn,Xn wykorzystać do uczenia i testu, ale tak żeby testować tylko na tych obserwacjach, które nie były brane pod uwagę przy uczeniu klasyfikatorów.

Kroswalidacja m-krotna (walidacja krzyżowa) polega na podziale danych na m części (popularnymi wyborami są m=5, m=10): m-1 będzie tworzyć próbę uczącą, ostatnia będzie próbą testową. Estymujemy klasyfikatory na próbie uczącej, porównujemy metody na próbie testowej. Powtarzamy procedurę m razy tak, żeby każda z części była próbą testową. Dokładniej:

  1. Permutujemy obserwacje. Jeżeli dane mają jakąś strukturę, na przykład można je podzielić na klasy, permutujemy obserwacje w klasach.

  2. Dzielimy próbę na m części tak, żeby w każdej z grup było po tyle samo obserwacji z każdej klasy.

  3. Uczymy klasyfikatory na próbie uczącej - estymujemy parametry.

  4. Porównujemy metody na próbie testowej (np. poprzez estymację prawdopodobieństwa poprawnej predykcji)

Definicja 7.6

Prawdopodobieństwo poprawnej predykcji to dla danego klasyfikatora PdX=y. Np. jeżeli funkcja straty wyraża się wzorem Lk,l=1kl, możemy estymować prawdopodobieństwo poprawnej predykcji dla konkretnej próby treningowej i testowej następująco:

ppp^i=ipróba testowa1dXi=yiipróba testowa1,

gdzie d jest klasyfikatorem wyestymowanym na podstawie próby uczącej. Uśrednione ppp^ jest dobrą metodą porównywania klasyfikatorów:

ppp^=i=1mppp^im.

7.5. Przykłady w programie R

Klasyfikacja:

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.