Analiza discriminanta

Axe discriminante

Pentru precizarea ideiilor sa consideram o multime de date dintr-un spatiu bidimensional. Valorile caracteristicilor C1 si C2 ale datelor sunt date de proiectiile norului pe axele de coordonate x₁ si x₂. Structura de clusteri a lui X se poate in acest caz detecta prin simpla inspectie vizuala. Diferiti observatori pot indica diferite moduri de grupare a datelor in clasa. Acesta releva faptul ca puterea ca puterea de discriminare a caracteristicilor este slaba pentru datele considerate. Exista doua posibilitati:

fie nu s-au ales cele mai bune caracteristici ale datelor;

fie ca datele prin natura lor sunt foarte asemanatoare.

Este de dorit in acest caz sa determinam un nou sistem de coordonate fata de care structura de clusteri a norului sa fie mai evidenta decat in sistemul initial. Axele noului sistem au deci o putere de discriminare a claselor din superioara celei a axelor initiale. In unele situatii este suficient sa determinam o singura axa discriminanta, astfel incat proiectiile norului de obiecte pe acesta axa sa conste din clase compacte si bine separate.

Marimea puterii discriminante a axelor poate fi asadar reclamata de datele problemei, pentru a putea 'vedea' o anumita structura a datelor. Determinarea axelor discriminante poate servi si ca o tehnica de reducere a dimensiunii spatiului caracteristicilor, prin aceea ca cunt selectate cele mai relevante caracteristici. Reducerea dimensiunii poate fi impusa si de necesitatea vizualizarii claselor intr-un spatiu cu una sau doua dimensiuni. In acest caz cerinta fundamentala este ca prin proiectarea datelor intr-un spatiu de dimensiune redusa, la clasele compacte si bine separate din spatiul initial sa corespunda clase compacte si bine separate din noul spatiu. In acelasi timp informatiile legate de imprastierea datelor servesc si la construirea unor criterii de clasificare.

Ne propunem:

Fie multimea datelor ( este o forma care este definita printr-un numar de d caracteristici- atribute). Dorim sa determinam o dreapta care trece prin originea spatiului astfel incat proiectiile punctelor norului pe aceasta dreapta sa formeze clase bine separate. In plus cerem ca structura de clusteri a lui sa nu fie prea mult alterata prin proiectarea norului pe acesta dreapta.

Fie vectorul unitar al dreptei cautate. Proiectiile punctului pe dreapta de directie este:

(1)

Sa consideram ca in sunt prezente clasele si . Admitem ca proiectiile pe ale punctelor clasei formeaza o clasa B₁ iar punctele din se proiecteaza pe in clasa B₂. Fie p_i numarul de puncte din clasa A_i si

(2)

media (centrul de greutate) clasei . Media clasei este

(3)

care se mai poate scrie

(3a)

Se defineste imprastierea a clasei ca fiind data de

Se observa ca imprastierea clasei este proportionala cu dispersia clasei .

Imprastierea intra-clase a proiectiilor datelor se defineste ca fiind

(5)

Separarea a claselor si se poate masura prin patratul distantei 'centrilor' si ai acestor clase

(6)

Ne intereseaza determinarea directiei pentru care :

separarea claselor este cat mai mare ;

imprastierea fiecarei clase in directia este cat mai mica

Se impune deci sa cautam maximul functiei criteriu

(7)

Definitie

Directia care realizeaza maximul functiei J se numeste axa discriminanta. Rescriem J astfel ca aceasta sa apara ca o functie explicita de astfel:

de unde

(8)

Dar matricea de impastiere a clasei este

(9)

Ca urmare matricea de impastiere a clasei este

(10)

Utilizand (10) imprastierea intra-clase este:

(11)

sau

unde este matricea de impriastierea intra-clase

Momentan am rezolvat numitorul functiei criteriu (7).

Numaratorul se va putea scrie

Matricea

(12)

se numeste matricea de imprastiere inter-clase.

Cu aceasta notatie obtinem

(13)

si deci functia criteriu J poate fi scrisa sub forma:

(14)

Determinarea maximului functiei criteriu. Din conditia de extrem

se obtine ecuati:

de unde

rezulta ca:

(15)

Admitind ca matricea nu este singulara , obtinem ca

(16)

Asadar este un vector propriu al matricei corespunzator valorii proprii

In concluzie determinarea directiei se reduce la determinarea vectorului propiu a matricei

OBSERVATIE

Pentru determinarea maximului functiei J nu este necesar sa calculam vectorii si valorile proprii ale matricei .

Pentru aceasta sa observam ca:

vectorul propriu a lui se poate scrie

(17)

unde este un scalar

concluzia care apare imediat este ca si au intodeauna directia vectorului

din relatia (16)

rezulta ca

(18)

si deci ca

(19)

Deoarece raportul nu are importanta pentru directiea lui , rezulta ca maximul functiei criteriu este:

(20)

Directiei discriminanta serveste la definirea unei functii de decizie unde

(21)

numita functia de decizie a lui Fisher. Hiperplanul de separare a celor 2 clase determinat de aceasta functie este

pe axa discriminanta.

Matrici de imprastiere pentru n clase

Admitem acum ca in multimea a datelor sunt prezente clasele . Clasa are elemente. Daca este media clasei :

(22)

atunci vectorul medie total pentru toate obiectele din se va scrie:

(23)

Matricea de imprastiere a clasei in jurul centrului ei de greutate este data de:

(24)

si in aceste conditii putem defini:

1) Matricea de imprastiere intraclase ca fiind:

(25)

2) Matricea de imprastiere totala a obiectelor din X fata de centrul m , ca fiind:

(26)

3) Matricea de imprastiere interclase se noteaza cu si este prin definitie

(27)

Tinand cont de aceste definitii putem enunta urmatorul rezultat:

Propozitia 1. Matricea de imprastiere totala se poate scrie sub forma

(28)

Demonstratie

se scrie sub forma :

rezulta ca:

ultimele 2 sume sunt 0. Sa consideram spre exemplificare ultima suma unde calculam componenta a acestei matrici

Ca urmare matricea se poate scrie:

Axe discriminante pentru n clase

In cazul a n clase (n>2) sunt necesare n-1 axe discriminante. Problema gasirii acestora revine la determinarea unui spatiu n-1 dimensional, astfel incat proiectiile punctelor in noul spatiu sa prezinte o imprastiere cat mai mica.

Fie u¹, u², . . . ,u^n-1 directiile cautate. Proiectia y_i a punctului x pe directia uⁱ este:

y_i =u^iT x , i =1,,n-1 (29)

Sa notam cu U matricea formata din componentele vectorilor u¹,u², ,u^n-1. Avem:

U=( u¹,u², . . . ,u^n-1)= (30)

Proiectiile vectorului x pe directiile u¹,u², ,u^n-1 formeaza un vector y de forma:

y= (31)

care se poate scrie y=U^Tx (32)

Admitem ca punctele clasei A_i se proiecteaza in clasa B_i avand vectorul medie .

(33)

Vectorul mediu al proiectiilor este :

(34)

Cu aceste notatii se pot construi :

Matricea de imprastiere interclase a datelor proiectate

(35)

Matricea de imprastiere intraclase

(36)

Deoarece

rezulta ca

(38)

Avem deci

(39)

Se observa ca fiecare termen diagonal al matricii S_i este proportional cu dispersia datelor din clasa A_i in directia respectiva. Rezulta deci ca elementele diagonale ale matricii S_W de imprastiere intraclase reprezinta dispersiile multimii X a obiectelor in directiile axelor de coordonate.

Propozitie

Valoarea proprie l corespunzatoare vectorului propriu v a lui S_i reprezinta o masura a imprastierii punctelor clasei A_i in directia vectorului unitar v.

Demonstratie

Fie v un vector propriu unitar al matricei S_i corespunzator valorii proprii. Proiectia vectorului x in directia vectorului v este:

x =v^Tx

iar proiectia vectorului mⁱ este :

m^'i=v^Tmⁱ

Imprastierea proiectiilor clasei A_i in directia v este data de:

S_i^'=

Adica

Rezulta ca marimea imprastierii (dispersiei) obiectelor clasei A_i in directia v este data de:

v^TS_i v = v^Tlv v ²=l

Analiza componentelor principale

Cand datele nu se prezinta sub forma unor nori sferici in spatiul R^d cunoasterea directiilor de extindere a norilor constituie o informatie utila. Vom numi componentele principale ale unui nor directiile in care alungirea norului este cea mai marcata. Determinarea directiilor principale poate servi pentru scopuri de clasificare (detectarea substructurii norului), descrierea datelor cat si pentru selectarea preliminara a caracteristicilor. Caracteristicile cele relevante, adica realizand cea mai buna discriminare a datelor, vor corespunde directiilor pe care proiectiile punctelor au cea mai mare dispersie. Utilizand componentele principale putem obtine o descriere geometrica a norului, care poate fi utila in aplicatii.

Fie X= o multime de puncte formand un nor in spatiul R^d. Ne propunem sa detectam directiile u¹, u², de dispersie maxima a norului. Aceasta inseamna ca norul X este format din puncte ce adera strans la dreptele L₁, L₂, care trec prin centrul sau de greutate si au directiile u¹, u²,

Fie d_j distanta de la un punct x^j la o dreapta L. Problema noastra este de a gasi dreapta pentru care

(1)

Problema determinarii dreptelor care aproximeaza cel mai bine, norul este considerabil simplificata daca vom arata mai intai ca orice dreapta ce minimizeaza cantitatea Y trece prin centrul de greutate al norului de puncte. Pentru inceput vom stabilii acest rezultat in cazul cand X este o multime de puncte din plan, urmand apoi sa demonstram ca rezultatul este adevarat pentru orice dimensiune finita a spatiului.

Fie V-W un nou sistem de coordonate, astfel incat axa W este paralela cu dreapta L (vezi figura urmatoare)

Fig. 4.4‑ Reprezentarea intr-un nou sistem de coordonate.

In sistemul de coordonate (V,W) ecuatia dreptei L este

v = v₀ (2)

iar ale punctelor x^j sunt (v_j,w_j). Distanta de la x^j la L este

d_j = d(x^j, L)= |v_j-v₀ (3)

In acest caz minimizarea sumei patratelor distantelor revine la minimizarea functiei criteriu J: R R, data de:

J(v₀)=    (4)

de unde rezulta ca

J(v₀)= (5)

a carui minim este

v₀= (6)

S-a observa ca punctul v₀ care determina dreapta L este media aritmetica a proiectiilor punctelor pe axa V, adica proiectia centrului de greutate a norului pe aceasta axa. Deoarece L este paralela cu axa W, intersectia lui L cu axa V coincide cu proiectia v₀ a centrului de greutate daca si numai daca centrul de greutate se afla pe L. Am aratat deci ca dreapta optima L trece prin centrul de greutate al norului de puncte.

In continuare vom arata ca acest rezultat este valabil si pentru un nor dintr-un spatiu de dimensiune finita R^d, d > 2.

In acest scop consideram un hiperplan H perpendicular pe dreapta L. Fie s punctul de intersectie pe dreapta L cu hiperplanul H. Notam cu x^'j proiectia punctului x^j al norului pe hiperplanul H.

Fig. 4.4‑ Proiectia punctului x^j pe hiperplanul H

Deoarece d(x^j,L) = d(x^'j,s) functia criteriu devine o functie de variabila s si deci avem:

J(s) =    (7)

Deoarece suntem intr-un spatiu euclidian patratul distantei este

d²(x^j, s)= x^j - s ²=[x^j - s]^T[x^j - s] (8)

asa incat

J(s)=

Functia J admite un minim local, dat de solutia ecuatiei

ÑJ(s) = 0

de unde se obtine

-2

ceea ce implica ca

si deci avem s =     (10)

Consideram un sistem ortogonal de coordonate, avand axa K paralela cu dreapta L. Rezulta ca dreapta x^jx^'j (paralela cu L si cu axa K) este perpendiculara pe planul format de oricare doua dintre axele diferite de K. Asadar, in sitemul considerat x^j si x'^j vor avea aceleasi componente, cu exceptia celor corespunzatoare axei K.

Fig. 4.4‑ Sistemul ortogonal de coordonate.

Rezulta ca

s_i=     (11)

Am aratat asadar ca dreapta L trece prin punctul s, unde s_i i¹k este componenta i a centrului de greutate. Axa k fiind paralela cu L, rezulta ca centrul de greutate se afla pe L deoarece in caz contrar L nu ar putea trece prin componentele s_i, i¹k ale centrului de greutate.

Deoarece dreapta optima trece intotdeauna prin centrul de greutate al norului de puncte, putem considera ca datele sunt totdeauna normalizate astfel incat sa aiba media 0.

O astfel de normalizare revine la o translatie

x'=x-m    xIX (12)

unde m este valoarea medie a punctelor din X. Prin aceasta translatie centrul de greutate al norului este adus in originea sistemului de coordonate. Se va nota cu X' norul format din datele transformate.

Problema determinarii directiilor principale devine

Fiind data o multime X' de puncte din R^d, avand media 0, sa se gaseasca dreapta care trece prin origine si minimizeaza functia criteriu J.

Fie u vectorul care ne da directia dreptei cautate si fie . Patratul distantei de la punctul x^j la dreapta de directie u este:

d²(x^j, u) = - ( x^j, u)    (13)

Pentru simplitate am notat datele normalizate tot cu x^j, j = 1,.,p. Datele fiind normalizate, problema determinarii liniei realizand cea mai buna aproximare a norului revine la determinarea directiei u care minimizeaza functia J:R^d R data de:

J(u)=    (14)

inlocuind cu (13) avem:

J(u)=

Primul termen fiind constant, minimizarea lui J implica maximizarea celui de-al doilea termen

I(u)=    (15)

Cum , rezulta ca trebuie sa determinam pentru forma patratica

I(u)=    (16)

maximul pe vectorii sferei unitate.

Se poate observa ca matricea

[S]= (17)

este patratica de ordinul d, fiind matricea de imprastiere a norului pentru cazul cand media norului este 0 (datele au fost normalizate).

Valorile extreme ale formei patratice

I(u)=[u]^T[S][u]

pe vectorii sferei unitate corespund vectorilor proprii ai matricei S. Directia pentru care I(u) are valoare maxima, este data de vectorul propriu corespunzator celei mai mari valori proprii ale lui S.

Fie u¹,u²,,u^d, vectorii proprii ai lui S, luati in ordine descrescatoare a valorilor proprii corespunzatoare. Acesti vectorii proprii indica directiile de alungire ale norului si din acest motiv se numesc directiile principale sau componentele principale ale norului. Cea mai accentuata extindere a norului este in directia lui u¹ (vectorul propriu principal). Revenind la norul initial (datele nenormalizate), rezulta ca norul X este format din puncte grupate in jurul liniilor L₁, L₂, ,L_d, care trec prin centrul de greutate al norului si sunt paralele cu vectorii u¹, u², , u^d (deoarece vectorii proprii corespunzatori la valori proprii distincte sunt ortogonali, rezulta ca directiile principale sunt ortogonale).

Algoritm pentru determinarea componentelor pricipale

P1. Se standardizeaza datele efectuand transformarea

x'^j=x^j-m unde m=

P2. Se determina vectorii proprii ai matricei de imprastiere

[S]=

si se noteaza cu u¹,u², ,u^d

P3. Dreptele de cea mai buna aproximare a norului X sunt dreptele prin media m a lui X paralele cu directiile principale u¹, u²,, u^d.

Important

Fie [A] matricea schimbarii de baza care realizeaza diagonalizarea matricei [S] de imprastiere a datelor normalizate.

Avem

[A]^-1[S][A]=

In baza formata de vectorii proprii ai lui S punctele norului X devin

y^j=[A]^-1x^j, j=1,.,p

Aceasta transformare se numeste transformarea la axele principale. Vom nota Y norul de puncte raportat la axele principale, deci Y=. Componenta i a lui yⁱ se obtine proiectand x^j pe axa uⁱ adica

y_i^j=(uⁱ, x^j)=[uⁱ]^T[x^j]

Dispersia norului Y in directia axei uⁱ este , unde l_i este valoarea proprie corespunzatoare vectorului propriu uⁱ a matricei S.