Klasifikavimas

Klasifikacijos uždavinys yra specifinis atpažinimo uždavinys, kurio esmė pagal pateiktus objekto (vaizdo, proceso) skaitmeninius duomenis priskirti jį kokiai nors klasei. Laikysime, kad objektas yra aprašomas D-mačiu vektoriumi

S_D= [ s₁ , s₂ , ... , s_D ]^' ,

o w₁ , w₂ , ... , w_L žymi visas klases, kurioms gali priklausyti objektas. Čia ir toliau ^' žymi transponavimo operaciją.
Klasifikacijos uždavinys yra sukurti duomenų žymėjimo algoritmą. Matematine prasme klasifikatoriumi vadinamas bet koks S_D vektorių atvaizdis į L žymių (kategorijų) aibę. Kadangi praktiškai žymių skaičius nebūna labai didelis, dažniausiai yra apskaičiuojamos L funkcijų reikšmės o₁ , o₂ , ... , o_L , kurios yra interpretuojamos panašumo į atitinkamos kategorijos objektą ir išsirenkamas indeksas su didžiausia panašumo reikšme.

Klasifikavimo uždavinys yra skaidomas į dvi dalis. Pirma yra surandamos objekto savybės (angl. features). Pažymėkime objekto savybių skaičių n. Savybės yra apskaičiuojamos remiantis pradiniu objektą aprašančiu vektoriumi S_D. Parenkant objekto savybes yra ieškoma kompromiso tarp

• Mažo savybių skaičiaus n (n<<D).
• Kuo didesnio savybių informatyvumo. Idealiu atveju iš savybių yra galima rekonstruoti pradinius objekto duomenis S_D.

Antrajame etape remiantis požymių vektoriumi

X= [ x₁ , x₂ , ... , x_n ]^'

yra atliekama klasifikacija.

1 pvz. Tarkime S_D= [ s₁ , s₂ , ... , s_D ]^' žymi stacionaraus akustinio signalo garso slėgio reikšmes. Tuomet geru požymių rinkiniu yra S_D duomenų tiesinės prognozės koeficientai X= [ x₁ , x₂ , ... , x_n ]^' .

Toliau paprastumo dėlei laikysime, kad yra tik dvi kategorijos, t.y., L=2. Tai nėra esminis apribojimas, kadangi pradžioje gali apjungti visas kategorijas į dvi grupes. Atlikę pirmąją klasifikaciją, rasime kuriai grupei priklauso tiriamas objektas. Toliau rasta grupė skirstoma vėl į dvi dalis, atliekama klasifikacija, kad surasti kuriam pogrupiui priklauso objektas ir t.t.

Kad sukurti klasifikatorių, pradžioje yra pasirenkama aibė duomenų vektorių S_D su žinomom kategorijų reikšmėm. Ši aibė yra pagrindas kuriant klasifikatorių. Kadangi iš pradinių duomenų galima išskirti įvairius požymių rinkinius, dažnai neapsiribojama vienu klasifikatoriumi, o kuriama skirtingiems rinkiniams skirtingi klasifikatoriai. Taip natūraliai iškyla klausimas - kuris klasifikavimo algoritmas yra geriausias? Todėl bendra pradinių duomenų grupė skaidoma į dvi dalis

1. apmokymo imtis (angl. training set)
2. verifikacijos imtis (angl. validation set)

Yra naudojamos įvairios strategijos kuriant ir įvertinant klasifikavimo algoritmus. Dažnai apmokymo ir verifikacijos imtys yra sukeičiamos vietom ir žiūrima kaip keičiasi rezultatai. Taip pat naudinga turėti dar vieną klasifikuotų duomenų grupę, kuri naudojama tikrinti algoritmus tik vieną kartą. Taip išvengiama algoritmo adaptacijos prie turimų duomenų. Vieną kartą naudojam tikrinimo imtis vadinama testine.

Dažnai laikoma, kad požymiai X yra pasiskirstę pagal kokį nors daugiamatį skirstinį. Tokia matematinė abstrakcija suteikia galimybę įvertinti klasifikavimo algoritmą vienareikšmiais skaičiais, kurie gaunami naudojant statistikinę informaciją apie populiaciją. Šiuo atveju geru požymiu dažnai yra skirtingų kategorijų požymių vidurkiai M₁ , M₂ , ... , M_L .

Konkretaus požymių vektoriaus X euklidiniai atstumai iki kategorijų vidurkių, kurių kvadratai apskaičiuojami pagal formules

||X-M_l||² = ( X-M_l )^'( X-M_l ),

yra vienas galimų panašumo į kategorijas matų. Tokių atstumų pagrindu atlikta klasifikacija vadinama euklidinio atstumo klasifikatoriumi (angl. Euclidean distance clasifier EDC). Kartais EDC dar vadinami artimiausiojo vidurkio klasifikatoriumi.

Dvi pirmąsias kategorijas skirianti riba randama iš lygybės

||X-M₁||² - ||X-M₂||² = 0.

Nesunku pastebėti, kad ši riba X atžvilgiu yra tiesinė. Taigi arčiausiojo vidurkio dviejų kategorijų klasifikatorius apibrėžiamas tiesine diskriminantine funkcija

h(X) = X^' V + c,

kur

V = M₁ - M₂ ir c = - (M₁ + M₂ ) ^' V / 2.

Klasifikavimas atliekamas pagal diskriminantinės funkcijos ženklą - jei jis yra '+', tai X požymius atitinkantis vektorius priskiriamas 1-ai klasei, priešingu atveju - 2-ai klasei. Žemiau pateikta iliustracija dviejų grupių klasifikavimas naudojant artimiausiojo vidurkio metodą.

Dviejų grupių artimiausiojo vidurkio klasifikatorius.
Grupių centrai: M₁ = (1,-2) ir M₁ = (-1,2)

Paprastas euklidinio atstumo pagrindu sukurtas klasifikatorius yra asimptotiškai (kai apmokymo duomenų skaičius artėja į begalybę) optimalus, jei duomenys pasiskirstę pagal sferinį Gauso dėsnį N_X(M_l , s²I). Čia I žymi vienetinę matricą, o s² I - kovariacijos matricą.

Jei požymių kovariacinė matrica S nėra įstrižaininė, klasifikavimas pagal artimiausiąjį kategorijų vidurkį nėra optimalus. Šiuo atveju geriau tinka Fišerio dar 1936 m. pasiūlytas klasifikatorius.

2 pvz. Žemiau pateiktame pavyzdyje palygintos klasifikavimo tiesės gautos taikant Euklidinį atstumą (E) ir Fišerio metodą. Naudojant klasifikavimui pateiktus N₁ ir N₂ duomenis, tiesinio klasifikavimo taisyklė h(X) = X^' V^F + c, gaunama tokiu būdu:

V^F = S^-1 (M₁ - M₂) ir c = - (M₁ + M₂ ) ^' V^F / 2,

o empirinė kovariacijos matrica apskaičiuojama pagal formulę

S = 1/(N₁ + N₂ - 2) S_i=1² S_j=1^N_i ( X_jⁱ - M_i ) ( X_jⁱ - M_i )^'.

Dviejų grupių taškų atpažinimas
artimiausiojo vidurkio ir Fišerio tiesiniais klasifikatoriais.

Jei grupių požymių vektoriai pasiskirstę pagal daugiamatį Gauso dėsnį su ta pačia kovariacine matrica ir skirtingais vidurkiais, tai standartinis Fišerio klasifikatorius yra optimalus. Naudojant vektorių V^F ir konstantą c Fišerio tiesinis klasifikatorius išreiškiamas formule

h(X) = X^' V^F + c.

Ir vienu ir kitu atveju išvesdami klasifikavimo taisyklę mes darėme prielaidą apie duomenų pasiskirstymą, įvertindavome pasiskirstymo parametrus ir po to gaudavome klasifikavimo taisyklę. Silpna vieta čia yra daroma prielaida apie parametrinį pasiskirstymo dėsnį. Daugelis autorių teigia, kad vietoje prielaidos apie pasiskirstymo dėsnį geriau fiksuoti kokiai klasei turi priklausyti klasifikavimo taisyklė ir toje klasėje ieškoti optimaliai atskiriančio grupes klasifikatoriaus. Pavyzdžiui, galima fiksuoti, kad mūsų klasifikatoriaus funkcija tiesiškai priklausys nuo požymių vektoriaus ir tarpe visų tiesinių išraiškų ieškosime skiriamosios tiesės geriausiai skiriančios apmokymo duomenimis. Panašios klasifikavimo paradigmos laikosi dirbtinių neuroninių tinklų pagrindu sukurti klasifikatoriai.

Susipažinsime su MEE (angl. minimum empirical error) klasifikatoriumi, kuris priklauso tiesinių klasifikatorių aibei ir randamas tiesiogiai minimizuojant klasifikavimo paklaidą.

3 pvz. Žemiau pateiktame brėžinyje palygintos klasifikavimo tiesės gautos taikant Euklidinį atstumą (E), Fišerio (F) ir minimalios empirinės paklaidos (MEE) metodą. Klasifikavimui pateiktos dvi plokštumos taškų grupės, kurios skiriasi vidurkiais: M₁ = -M₂ = 0.5. Prie abiejų grupių taškai pasiskirstę pagal normalųjį dėsnį su ta pačia kovariacine matrica, kurios kvadratinės formos vieną lygio liniją iliustruoja elipsė.

Dviejų grupių taškų atpažinimas
artimiausiojo vidurkio (E), Fišerio (F) ir
optimizuojančiu pateiktos imties atpažinimą (MEE)
tiesiniais klasifikatoriais.

Iš brėžinio matyti, kad tiesiogiai duomenų imčiai adaptuotas tiesinis klasifikatorius (MEE) geriausiai atlieka skirtingų grupių taškų atpažinimą. Tačiau nebūtinai šis klasifikatorius yra geriausias. Neuroniniuose tinkluose susiduriama su reiškiniu, vadinamu tinklo pertreniravimu (angl. overtraining. Jo esmė yra per didelė parametrų adaptacija prie pateiktos duomenų specifikos. Pertreniravimas reiškia, kad tinklo mokymo eigoje buvo pereitas etapas, kuriame einamosios parametrų reikšmės būtų davusios geresnius verifikacinius rezultatus.

Vienasluoksniai ir daugiasluoksniai perceptronai

Vienasluoksnis perceptronas yra grupė paprastųjų perceptronų, naudojančių bendrą požymių vektorių. Pas žmogų yra milijardai tarpusavyje sujungtų neuronų. Laikoma, kad gyvuose organizmuose neuronai grupuojasi sluoksniais, o šie savo ruožtu taip pat jungiasi tarpusavyje. Taip susidaro sudėtinga struktūra skirta apdoroti informacijai. Tuo atveju kai sluoksninė neuronų struktūra yra imituojama jos matematiniu modeliu, kompiuteriu ar elektrinėm schemom, vartojamas dirbtinių neuroninių tinklų terminas (angl. Artifical Neural Networks (ANN) ).

Paprastasis perceptronas sudarytas iš

• n įvesties (įėjimo) parametrų: x₁, x₂, ... , x_n.
• Perdavimo funkcijos f=f(x).
• Vieno išvesties (išvedimo) parametro o, apskaičiuojamo formule

  o = f ( V^'X + c ).

Dirbtiniuose neuroniniuose tinkluose perceptronų perdavimo funkcijos yra vienodos ir vienas nuo kito perceptronai skiriasi tik svorių V^' = w₁, w₂, ... , w_p ir poslinkio c reikšmėm. Klasikiniu atveju perdavimo funkcija yra sigmoidinė, t.y.,

f(x) = 1/(1+e^-x).

Paprastasis perceptronas yra specifinės struktūros diskriminantinė funkcija, x₁, x₂, ... , x_n yra požymiai, o o svoriai ir poslinkis apibrėžia konkrečią diskriminantinės funkcijos išraišką.

Net vienu perceptronu galima atlikti požymių vektoriaus X klasifikaciją. Kadangi perdavimo funkcija turi tik dvi stabilias reikšmes - 0 ir 1, klasifikavimo kategorijų (grupių) skaičius lygus 2, o sprendimo taisyklė yra tokia: jei o viršija slenkstinę reikšmę 0.5, X priskiriamas vienai grupei, priešingu atveju - kitai. Iš čia ir f argumento išraiškos V^'X + c gauname, kad perceptrono sprendimo skiriamoji riba yra tiesinė. Perceptrono svoriai surandami minimizuojant baudos funkciją apibrėžtą apmokymo aibėje. Paprasčiausia ir populiariausia yra kvadratinė baudos funkcija: bauda = 1/(N₁+N₂) S_i=1² S_j=1^N_i ( t_jⁱ - f ( V^'X_jⁱ + c ) ) ²,

kur t_jⁱ yra tikslo reikšmė duotajam mokymo požymių vektoriui X_jⁱ . Mūsų atveju galima pasirinkti t_j¹ = 1 , t_j² = 0 arba t_j¹ = 0.95 , t_j² = 0.05 . Bendru atveju pasirenkamos tikslo reikšmės turi tenkinti nelygybę 0 < t_jⁱ <1 .

Aprašytas perceptronas kiek pasikeistų, jei būtų naudojama kita populiari perdavimo funkcijos išraiška

f ^tanh(x) = ( e^x - e^-x ) / ( e^x + e^-x ) = 2f ^sigmoid(2x) - 1.

Šiuo atveju geriau būtų t_j¹ = 1 , t_j² = -1.

Slenkstinei perdavimo funkcijai

f ^hard(x) = 1 kai x > 0 , f ^hard(x) = 0 kai x < 0

vėl tinka t_j¹ = 1 , t_j² = 0.

Klasikiniu atveju perceptrono svoriai randami gradientiniu metodu minimizuojant baudos funkciją. Tuo tikslu skaičiuojamos baudos funkcijos dalinės išvestinės atžvilgiu ieškomų parametrų ir svoriai keičiami tokiu iteraciniu būdu:

V_t+1 = V_t - h bauda_V^',     c_t+1 = c_t - h bauda_c^'.

Čia baudos išvestinė atžvilgiu vektoriaus žymi gradientą.
Slenksčio funkcijai šis gradientinis metodas netinka. Kad pradėti iteracinį procesą, reikia apibrėžti pradinius svorius V₀ ir laisvąjį narį c₀. Literatūroje rekomenduojama pradines svorių reikšmes imti nedidelius atsitiktinius skaičius. Mes kiek vėliau susipažinsime su trim skirtingais pradinių svorių parinkimo variantais, su kuriais galima gauti visus tris anksčiau nagrinėtus tiesinius klasifikatorius.

Grupė parastųjų perceptronų, naudojanti tuos pačius įvesties parametrus, sudaro vienasluoksnį perceptroną. Kelių vienasluoksnių perceptronų struktūra vadinama daugiasluoksniu perceptronu arba dirbtiniu neuroniniu tinklu. Daugiasluoksnio perceptrono įvestį sudaro požymių vektoriaus X = ( x₁ , x₂ , ... , x_n )^' komponentės x₁ , ... , x_n. Vieno sluoksnio perceptrono išėjimai (angl. output) sudaro kito sluoksnio įėjimą (angl. input). Perceptronų sluoksniai tarp įėjimo ir paskutinio vadinami paslėptais (angl. hidden). Pateiktas brėžinys iliustruoja dvisluoksnį perceptroną su vienu paslėptuoju sluoksniu, požymių vektorius yra septinmatis, paslėptąjį sluoksnį sudaro trys perceptronai, išvesties (antrąjį) sluoksnį taip pat trys perceptronai.

Dviejų sluoksnių perceptronas.

Paskutiniojo sluoksnio perceptronai naudojami skirtingom klasėm žymėti. Tipiniu atveju paskutinio sluoksnio perceptronų skaičius yra lygus skaičiui skirtingų klasių (kategorijų), kurias reikia atpažinti. Tarkime, jei reikėtų atpažinti skaitmenis, tai atpažinimui tikslinga būtų pasirinkti daugiasluoksnį perceptroną, turintį 10 išeities perceptronų.

Daugiasluoksnio perceptrono svoriai taip pat surandami iteraciniu būdu minimizuojant baudos funkciją. Kadangi paslėptųjų sluoksnių perceptronams tiesiogiai nėra kaip parinkti tikslo reikšmes, skaičiuojant gradientą atsiranda tam tikros rekurencijos, vadinamos t_jⁱ - f ( V^'X_jⁱ + c ) paklaidų atgaliniu sklidimu (angl. Back Propagation).
Apie atgalinio sklidimo algoritmą, skirtą daugiasluoksnių perceptronų mokymui, galite paskaityti http://scitec.uwichill.edu.bb/cmp/online/p21h/Lecture9/lect9.htm.

Naudojant slenkstines funkcijas požymių plokštumoje grupes skiriančios ribos sudaro laužtę (laužtė - tolydi kreivė sudaryta iš tiesės atkarpų). Jei perdavimo funkcija f yra diferencijuojama, skiriamoji riba neturi aštrių kampų.

Dviejų sluoksnių perceptronų skiriamosios ribos.
Punktyrinė linija - naudojama slenkstinė perdavimo funkcija,
ištisinė kreivė - glodi perdavimo funkcija

Bendru atveju dvisluoksniu perceptronu su vienu paslėptu sluoksniu naudojant pakankamai daug perceptronų galima gauti kiek norima sudėtingą dvi grupes skiriančią ribą. Esminio skirtumo tarp naudojamų perdavimo funkcijų nėra. Pavyzdžiui, pasirenkant mastelį galima pasiekti, kad sigmoidinė perdavimo funkcija duotų skiriamąsias ribas panašias į ribas gaunamas su slenksčio funkcija.

Ryšys tarp paprastojo perceptrono ir euklidinio ir Fišerio klasifikatorių

Paprastumo dėlei tarkime, kad yra tik dvi grupės (kategorijos), abiejų grupių apmokymo imtys yra vienodo dydžio (N₁ = N₂ = N = N/2) ir duomenys yra centruoti, t.y.,
M = ( M₁ + M₂ ) / 2 = 0.
Toliau laikysime, kad perdavimo funkcija yra tiesė
f(x) = x , baudos funkcija apibrėžiama

bauda = 1/N S_i=1² S_j=1^N ( t_jⁱ - ( V^'X_jⁱ + c ) ) ²

su simetrinėm tikslo reikšmėm t_j¹ = 1 ir t_j² = -1 .

Parodysime, kad prie šių sąlygų startuojant nuo nulinių svorių V₀ = 0 ir nulinės poslinkio konstantos c₀ = 0 jau po pirmojo gradientinio vieno perceptrono treniravimo žingsnio gauname naują svorio vektorių ir poslinkio konstantą, su kuriais apskaičiuojamas perdavimo funkcijos argumentas daugiklio tikslumu sutampa su artimiausiojo vidurkio (euklidinio atstumo) metode naudojama klasifikavimui išraiška.

Apskaičiavę baudos funkcijos išvestinę atžvilgiu kintamojo c ir gradientą atžvilgiu svorio vektoriaus V, gausime

d bauda / dc = -2/N S_i=1² S_j=1^N ( t_jⁱ - ( V^'X_jⁱ + c ) ) = 2 c + 2 V^' M,

d bauda / dV = -2/N S_i=1² S_j=1^N X_jⁱ ( t_jⁱ - ( (X_jⁱ)^' V + c ) ) = -D M + 2 K V,

kur

D M = M₁ - M₂ ir

2 K V = 1/N S_i=1² S_j=1^N X_jⁱ ( X_jⁱ )^'.

Įstatę šiose formulėse pradines nulines svorių ir poslinkio reikšmes, gauname tokias atnaujintas po pirmosios iteracijos reikšmes:

V₁ = V₀ - h d bauda / d _V = h D M ,

c₁ = c₀ - 0 = 0.

h bauda_c^'.

Taigi daugiklio tikslumu išraiškos naudojamos klasifikuoti arčiausiojo vidurkio ir perceptrono, gaunamos po pirmosios iteracijos, yra vienodos. Kadangi klasifikuojama pagal diskriminantinės funkcijos ženklą, tai daugiklis nekeičia klasifikavimo rezultatų.
Aprašytas rezultatas teisingas bet kokiai nelyginiai diferencijuojamai perdavimo funkcijai.

Taigi, jei

1. apmokymo imtis yra centruota ta prasme, kad požymių vidurkio vektorius M = 0;
2. apmokymas pradedamas su nuliniais svoriais ir poslinkio konstanta;
3. dviejų grupių apmokymo imtys vienodos ir tikslo reikšmės simetrinės, t.y, N₁ = N₂ = N ir t₁ = -t₂.
4. naudojamas pilnojo gradiento metodas (angliškai sakoma, kad iteracinis procesas atliekamas su batch mode .)

Fišerio klasifikatorius gaunamas minimizuojant baudos funkciją antrosios eilės metodu. Prilyginę baudos funkcijos gradientą nuliniam vektoriui, randame svorio vektoriaus išraišką V = 1/2 K^-1 DM. Centruotiems duomenims (M = 0) matricą K galime išreikšti

K = (N-1)/N S + 1/4DM DM^',

S = 1/(N₁ + N₂ - 2) S_i=1² S_j=1^N_i ( X_jⁱ - M_i ) ( X_jⁱ - M_i )^'.

Naudodami Bartleto teigiamos simetrinės matricos apgrąžos formulę

(A + VV^')^-1 = A^-1 - ( A^-1VV^'A^-1 ) / ( 1 + V^'A^-1V ) ,

svorio vektorių išreikšime

V = k S^-1DM,

kur k = 2 / ( D² + 4(N-1)/N ) ir D² = DM^' S^-1 DM .

Taigi vėl iš paprasto perceptrono vienu antrosios eilės baudos minimizavimo būdu gauta svorio išraiška duoda daugiklio tikslumu tą pačią išraišką kaip ir Fišerio tiesinis klasifikatorius.

1. Šarūnas Raudys, Statistical and Neural Classifiers, An Integrated Approach to design, Springer, 2001.
2. J. Sodha, Neural Networks, http://scitec.uwichill.edu.bb/cmp/online/p21h/p21h.htm
3. Wikipedia, Support vector machine
4. Wikipedia, Nearest Neighbour algorithm
5. Wikipedia, Unsupervized learning
6. Wikipedia, Logistic regression
7. Wikipedia, AdaBoost
8. Wikipedia, Naive Byes classifier