PCA LDA MDS, LLE, CCA. Adatbányászat. Dimenziócsökkentő eljárások. Szegedi Tudományegyetem. Adatbányászat

PCA LDA MDS, LLE, CCA

Adatbányászat Dimenziócsökkentő eljárások

Szegedi Tudományegyetem

Adatbányászat

PCA LDA MDS, LLE, CCA

Dimenziócsökkentés szerepe

Az adatpontok reprezentálására használt dimenziók számának csökkentésével spórolhatunk Többdimenziós adatpontok vizualizálása (pl. 2 vagy 3D-ben) Zajcsökkentés, jellemzőszelekció Ötlet: próbáljuk meg alacsonyabb dimenzióban ábrázolni a pontjainkat Az alacsonyabb dimenziós reprezentáció kapcsán miben mérjük az elégedettségünket? → PCA, LDA, SVD, . . .

Adatbányászat

PCA LDA MDS, LLE, CCA

Főkomponens analízis (Principal Component Analysis)

Transzformáljuk úgy alacsonyabb dimenzióba a több/sokdimenziós adatunkat, hogy a benne rejlő variancia minél kisebb részét veszítsük csak el Feltevés: az eredeti m-dimenziós adatpontok egy bizonyos m0 -dimenziós altéren (vagy legalábbis annak közelében) helyezkednek el → az adatpontokat az altér tengelyeire transzformálva jól reprezentálható az eredeti adat Mi lehet ez a m0 -dimenziós altér? Pn 0 2 i=1 k(xi − xi )k rekonstrukciós hibát szeretnénk minimálisnak látni, ahol xi0 az eredeti xi pont egy közelítése

Adatbányászat

PCA LDA MDS, LLE, CCA

Kovariancia

Emlékeztető Y és Z véletlen változók együttmozgását számszerűsíti cov (Y , Z ) = E[(Y − µY )(Z − µZ )] Ahol µY =

1 n

n P i=1

yi és µZ =

1 n

n P

zi

i=1

Az X adatmátrixunk i, j oszlopaira (X:,i , X:,j ) tekinthetünk véletlen változóként

Adatbányászat

PCA LDA MDS, LLE, CCA

Szóródási,- és kovarianciamátrixok

Szóródási mátrix: S =

n P

(xi − µ)(xi − µ)|

i=1

Torzított (torzítatlan) kovarianciamátrix: Σ = n1 S (Σ = 

1 n−1 S)



cov (X:,1 , X:,1 ) cov (X:,1 , X:,2 ) ... cov (X:,1 , X:,m )  cov (X:,2 , X:,1 ) cov (X:,2 , X:,2 ) ... cov (X:,2 , X:,m )      Σ= .. .. ..  . . cov (X , X ) . :,i :,j   cov (X:,m , X:,1 ) ... ... cov (X:,m , X:,m )

Σi,j tehát az i. és j. jellemzők kovarianciája (cov (X:,i , X:,j )) Milyen elemek állnak a főátlóban?

Adatbányászat

PCA LDA MDS, LLE, CCA

Szóródási,- és kovarianciamátrixok tulajdonságai Állítás: S és Σ mátrixok szimmetrikusak és pozitív definitek Bizonyítás. S=

n P

(xi − µ)(xi −

=

n P

!| (xi − µ)(xi −

µ)|

= S|

i=1

i=1

a| Sa =

µ)|

n P i=1

(a| (xi − µ))((xi − µ)| a) =

n P

(a| (xi − µ))2 ≥ 0

i=1

Következmény: S és Σ sajátértékeire λ1 ≥ λ2 ≥ . . . ≥ λm ≥ 0 Az adat varianciáját legjobban megőrző m0 -dimenziós projekciót úgy kapjuk, ha az adatpontokat S (vagy Σ) m0 legnagyobb sajátértékéhez tartozó sajátvektorából képzett mátrixszal szorozzuk (lásd: tábla) Adatbányászat

PCA LDA MDS, LLE, CCA

Lagrange szorzók Korlátozott/feltételes (nemlineáris) optimalizációs feladat f (x) → min/max f.h. gi (x) = 0∀i ∈ {1, . . . , n} Lagrange függvény: L(x, λ) = f(x) +

n X

λi gi (x)

i=1

Karush-Kuhn-Tucker (KKT) feltételek: az optimalitás szükséges feltételei ∇L(x, λ) = 0

(1)

λi gi (x) = 0∀i ∈ {1, . . . , n}

(2)

λi ≥ 0

(3)

Adatbányászat

PCA LDA MDS, LLE, CCA

Gyakorlati megfontolások Az adatpontokat érdemes egységes skálára hozni: normalizáció min-max normalizáció: xi,j = standardizálás: xi,j =

xi,j −min(x∗,j ) max(x∗,j )−min(x∗,j )

xi,j −µj σj

A redukált dimenziószámot (m0 ) minek válasszuk?  P m m P si2 λi = Hint : i=1

i=1

Pk λi m = arg min Pi=1 ≥ t küszöbérték m 1≤k≤m i=1 λi 0

m  1 X  λi > λj 1≤i≤m m

m0 = arg max

j=1

m0 = arg

max (λi − λi+1 )

1≤i≤m−1

Adatbányászat

PCA LDA MDS, LLE, CCA

PCA összegzés

Centralizáljuk és normalizáljuk az X adatmátrixot Számoljuk ki a (centralizált és normalizált) X adatmátrixot jellemző kovariancia/szóródási-mátrixot Számoljuk ki a mátrix sajátértékeit Az m0 legnagyobb sajátértékhez tartozó sajátvektorból képezzük P projekciós mátrixot X 0 = XP adja meg a transzformált adatmátrixot X 0 P | alakban kaphatjuk vissza az eredeti adatpontok egy közelítését PCA tutorial

Adatbányászat

PCA LDA MDS, LLE, CCA

Szinguláris érték felbontás

X

=

U

x

Sigma

x

V

t

rang P(X )

σi ui vi| i=1 s s rang m n P P P(X ) 2 xij2 = σi kX kF = X = UΣV | =

i=1 j=1

i=1

˜ | X alacsony(abb) rangú közelítése: X˜ = U ΣV X˜ előállítása során csupán Σ első m0 < m szinguláris értékére hagyatkozzunk Ha a közelítés eltérését Frobenius-normában mérjük, akkor X megadható legpontosabb m0 -dimenziós becslése X˜

Adatbányászat

PCA LDA MDS, LLE, CCA

SVD és a sajátérték dekompozíció viszonya Emlékeztető Egy szimmetrikus A mátrix felbontható A = X ΛX −1 alakban, ahol X = [x1 x2 . . . xm ] az A (ortogonális) sajátvekroraiból képzett mátrix, Λ = diag ([λ1 λ2 . . . λm ]) pedig az egyes sajátvektorokhoz tartozó sajátértékeből álló diagonális mátrix. Miért is? Tetszőleges n × m-es X mátrix előáll UΣV | szorzatként, ahol Un×n = [u1 u2 . . . un ] XX | ortonormált sajátvektoraiból álló mátrix √ √ √ Σn×m = diag ( λ1 , λ2 , . . . , λm ) Vm×m = [v1 v2 . . . vm ] X | X ortonormált sajátvektoraiból álló mátrix. Miért?

Ortogonális mátrix: M | M = I (szemléletesen: olyan forgatás, ami a vektorok hosszát nem változtatja meg) Miért? Adatbányászat

PCA LDA MDS, LLE, CCA

SVD és a Frobenius-norma viszonya PP

Tfh. M = P × Q × R, azaz mij =

k  −58 M = −32 −28



 87 6 48 = 2 42 3

  1 4  2 1 −2 0 2

3 4 2

pik qkl rlj

l

 3 ⇒ m32 = 3 ∗ 4 ∗ 3 + 2 ∗ 1 ∗ 3 + 0

2 PP PPPP pik qkl rlj Ekkor kMk2F = (mij )2 = i j i j k l PP 2 P P P P Továbbá pik qkl rlj = pik qkl rlj pin qnm rmj k l k P l m n P P P P P Ahonnan kMk2F = pik qkl rlj pin qnm rmj i

j

k

l

m n

Amennyiben P P, Q, R mátrixok az SVD P felbontásból jönnek, P kMk2F = pik qkk rkj pin qnn rnj = qkk rkj qkk rkj = (qkk )2 . i,j,k,n

j,k

k

Miért? ˜ | mátrixszal történő közelítésének hibája: X mátrix X˜ = U ΣV P 2 ˜ ˜ | k2 = (σkk − σ kX − X kF = kU(Σ − Σ)V ˜kk )2 F k

Adatbányászat

PCA LDA MDS, LLE, CCA

CUR

SVD hátránya, hogy egy jellemzően ritka mátrixot sűrű mátrixokat (U és V ) is tartalmazó szorzatként állítja elő Egy alternatíva az eredeti mátrix CUR formában történő előállítása Csak az U mátrix adódik sűrűnek, és az SVD felbontás egy közelítését adja C és R mátrixok az eredeti X mátrix soraiból, illetve oszlopaiból származnak, így azok megőrzik X ritkaságát Míg az SVD egyedi felbontást eredményez, addig a CUR nem

Adatbányászat

PCA LDA MDS, LLE, CCA

Lineáris Diszkriminancia Analízis (Linear Discriminant Analysis) Transzformáljuk úgy alacsonyabb dimenzióba a több/sokdimenziós címkézett adatunkat, hogy az új térben az eltérő osztályú pontok minél kevésbé keveredjenek Mi legyen w vetítés iránya? µ ~i = w| µi ⇒ |µ~1 − µ~2 | = |w| (µ1 − µ2 )| s˜i =

X

(w| x − ~ µi ) 2

x i címkéjű

w∗ = arg max J(w) = arg max w

w

Adatbányászat

|~ µ1 − ~ µ2 |2 2 s˜1 + s˜22

(1)

PCA LDA MDS, LLE, CCA

LDA – Belső,- és külső szóródási mátrixok i osztályú transzformált pontok belső szóródási mátrixa: X Si = (x − µi )(x − µi )| x i címkéjű

Aggregált belső szóródási mátrix: SW = S1 + S2 i osztályú transzformált pontok szóródása: X X s˜i 2 = (w| x−w| µi )2 = w| (x−µi )(x−µi )| w = w| Si w x i címkéjű

Eltérő osztályú transzformált pontok közötti szóródási mátrix: SB = (µ1 − µ2 )(µ1 − µ2 )| Eltérő osztályú transzformált pontok közötti szóródás: (˜ µ1 − µ ˜2 )2 = (w| µ1 − w| µ2 )2 = w| SB w Adatbányászat

PCA LDA MDS, LLE, CCA

LDA Azaz az eredeti (1)-ben foglalt célunk átfogalmazható | w∗ = arg maxw J(w) = arg maxw ww| SSWB ww alakra w | SB w w| SW w

az ún. általánosított Rayleigh-hányados |

J(w) maximális ⇒ ∇ ww| SSWB ww = 0 ⇔ SB w = λSW w ⇔ −1 −1 SW SB w = λw ⇔ w = SW (µ1 − µ2 ) (Lásd tábla) Emlékeztetőül  0 f (x) = g (x)

f 0 (x)g (x)−f (x)g 0 (x) g 2 (x)

∇x x| Ax = 2Ax, amennyiben A = A|  n  P | xx y = xi yi x (vagyis egy x irányába mutató vektor) i=1

Adatbányászat

PCA LDA MDS, LLE, CCA

LDA vs. PCA 4 b

3

4

PCA

3 b

b b

b b

2

b

b b

b

2

b

1 0

b b

b

b

LDA b

b b

b b

1

0

1

2

3

4

0

0

1

Adatbányászat

2

3

4

PCA LDA MDS, LLE, CCA

Multidimenziós skálázás (Multi-Dimensional Scaling)

Cél: adott ∆ pontpáronkénti költségeket/távolságokat tartalmazó mátrixhoz keressük meg az adatpontok azon pozícióit a térben, melyre kxi − xj k≈ δij Több/sokdimenziós adatpontok transzformációja alacsonyabb dimenzióba úgy, hogy a pontok közötti távolságok minél inkább megőrződjenek

Adatbányászat

PCA LDA MDS, LLE, CCA

Lokális lineáris beágyazás (Locally Linear Embedding) A PCA, SVD és LDA mind lineáris függést feltételeztek Nemlineáris dimenziócsökkentő eljárás Trükk: Minden ponthoz határozzuk meg a legközelebbi szomszédait, és írjuk fel őket azok lineáris kombinációiként n n n P P P J(W ) = kxi − Wij xj k2 , úgy, hogy Wij = 1, és i=1

j=1

j=1

wij > 0 ⇔ xj ∈ neighbors(xi )

Adatbányászat

PCA LDA MDS, LLE, CCA

Kanonikus korreláció analízis A pontjaink koordinátái két kordinátarendszer szerint ismertek Feladat: a két koordinátarendszer pontjainak egy (csökkentett dimenziójú) koordinátarendszerbe való összegyúrása, hogy a transzformált jellemzők korrelációja maximális legyen E [xy ] = E [x 2 ] E [y 2 ] | √ | wx Cxy w|y wx Cxx wx wy Cyy wy

ρ= √

√

E[wx| xy | wy ] | E[wx xx | wx| ] E [wy| yy | wy| ]

=

arg max ρ-t nem befolyásolja wx vagy wy hossza ⇒ arg max ρ = arg max wx| Cxy wy " # " # Σxx Σxy

x x | Σ= =E y y Σyx Σyy

Adatbányászat

PCA LDA MDS, LLE, CCA

Alternatív vizualizációs eljárások Ha nem (feltétlen) kérünk a dimenziócsökkentésből Chernoff arcok: egy arc egy adatpontnak feleltethető meg, az arc karakterisztikája pedig az az adatpontot leíró jellemzők által felvett értékekkel hozható összefüggésbe

Adatbányászat