Főkomponens-analízis

Mai bejegyzésünkben egy nagyon elterjedt dimenziócsökkentő eljárást fogunk megismerni, a Főkomponens-analízist (angolul: Principal component analysis). A bejegyzés Lantos Gábor közreműködésével született. Gábor írt a főkomponens analízis felhasználói oldaláról a saját oldalán, én pedig a háttérben levő matematikai alapokat tárgyalom itt.


Miért?

Mint a bevezetőben említettem, a főkomponens analízis célja általában a dimenziócsökkentés. Jogos a kérdés, miért tegyük ezt? Ennek általában két oka van: ábrázolni szeretnénk az adatainkat, vagy olyan statisztikai, gépi tanulási módszert szeretnénk alkalmazni, ami megbízhatóbb és/vagy gyorsabb kevesebb dimenzió esetén. Igazából minden alkalmazás gyorsabb kevesebb dimenzió esetén, tehát akkor mindig alkalmazzunk főkomponens analízist? A válasz erre a kérdésre: Nem. Ennek a legfőbb oka, hogy az adatokat átalakítjuk, és az eredmény magyarázata nehezebbé válik.

Hogyan?

Értelemszerűen a dimenzió csökkentésnek csak akkor van haszna, ha egy időben nem vesztünk túl sok információt. Rendben, de mi az információ, és hogyan mérjük? A főkomponens analízis a varianciát használja az információ mérésére. Feltételezi, hogy minél nagyobb egy megfigyelt tulajdonság szórása, annál több információt tartalmaz. Nézzünk egy egyszerű példát:

Független tulajdonságok
Független tulajdonságok

Könnyű belátni, hogy az 1.tulajdonság lényegében semmiféle hasznos információt nem hordoz. Értéke minden esetben 2, és nyugodtan el is hagyhatnánk. Azt is könnyű belátni, hogy a fenti példában a tulajdonság varianciájának vizsgálata alapján is ugyanerre a következtetésre jutottunk volna. Egy kicsit összetettebb a helyzet, amikor a változóink nem függetlenek egymástól:

Egymással kapcsolatban lévő tulajdonságok
Egymással kapcsolatban lévő tulajdonságok

A fenti ábrán egyértelmű, hogy az 1. és a 2. tulajdonság között lineáris kapcsolat van. Mit tegyünk ilyenkor, ha dimenziót szeretnénk csökkenteni? Melyik tulajdonság a fontosabb? Ugye ebben az esetben is megvizsgálhatjuk a tulajdonságok varianciáját. A helyzet az, hogy a fenti példa esetén mindkét tulajdonság varianciája ugyanaz lesz.[1] Tehát melyiket hagyjuk el? A főkomponens analízis válasza erre a kérdésre: egyiket se. Inkább készítsünk egy új dimenziót, aminek maximális a szórása. Ez az új dimenzió pedig a lentebb látható tengely lesz:

Maximális szórás
Maximális szórás

Könnyű belátni, hogy erre a tengelyre vetítve lesz a legmagasabb a pontok varianciája. Ami, kiindulva abból az axiómából, hogy a variancia = információ, kedvezőbb számunkra, mintha egyszerűen elhagytuk volna az egyik vagy másik tulajdonságot. Ez tulajdonképpen a főkomponens analízis alapötlete: az adatokat egy olyan tengelyre vetítjük, ami maximalizálja a varianciát, és ezzel minimalizálja az információvesztést a dimenziócsökkentés során. Sajnos ennek a vetítésnek van egy hátulütője: ez az új tulajdonság nehezen elmagyarázható.

A főkomponens analízis lépései

A magyar Wikipédia elég jól pontokba szedi ezeket a lépéseket, így most mi is ezt a felosztást fogjuk használni:

  1. létrehozzuk az adathalmazt.
  2. kiszámítjuk az átlagot minden dimenzióra
  3. elkészítjük a kovarianciamátrixot
  4. kiszámoljuk a kovarianciamátrixhoz tartozó sajátvektorokat és sajátértékeket
  5. származtatjuk az új adathalmazt

Most nézzük ezeket a lépéseket kicsit részletesebben:

Létrehozzuk az adathalmazt

Tegyük fel, hogy van négy (n) darab két dimenziós (d) megfigyelésünk:


x_1= \begin{pmatrix}  8 \\ 4  \end{pmatrix},\,  x_2= \begin{pmatrix}  2 \\ 8  \end{pmatrix},\,  x_3= \begin{pmatrix}  3 \\ 1 \\ \end{pmatrix},\,  x_4= \begin{pmatrix}  9 \\ 7 \\ \end{pmatrix}.

Kezdetnek írjuk fel az összes megfigyelést egyetlen egy mátrix segítségével, legyen ez mondjuk \mathbb{X}, egy olyan mátrix, aminek a sorai az egyes megfigyelések (összesen n darab) és az oszlopai pedig az egyes tulajdonságok (d darab).


\mathbb {X} = \begin{pmatrix}  8 &  2 &  3 &  9 \\ 4 &  8 &  1 &  7 \\  \end{pmatrix}^ T = \begin{pmatrix} 8 & 4\\ 2&8\\ 3&1\\ 9&7\end{pmatrix}

Minta átlag dimenzióként

Ez nagyon egyszerű, csak kiszámítjuk minden egyes dimenzióra egyesével az átlagot. Vagyis:


\bar{X} = \frac{1}{n} \sum_{i=0}^n X_i

Mivel korábban egyetlen mátrix segítségével is felírtuk a megfigyeléseinket, ezt érdemes mátrix formában átfogalmazni:


\bar{X} = \frac{1}{n} \mathbb {X}^T \cdot \mathbf{1}

Ahol:

  • \mathbf{1} – pedig egy n hosszúságú egység vektor, jelen esetben:

 
\mathbf{1} = \begin{pmatrix}  1 &  1 &  1 &  1 \end{pmatrix}^T

Ami jelen példánk esetén:


\bar{X} = \begin{pmatrix}  5,5 \\ 5 \\ \end{pmatrix}

Mire volt ez jó? Ez abban fog segíteni nekünk, hogy minden dimenzió központja ugyanaz legyen. Nevezetesen az origó. Ehhez csak ki kellene vonunk a megfigyelésekből az átlagokat.

Minta kovarianciája

Ez már egy kicsit bonyolultabb. Maga a vektor formájú definíciója a következő:[2]


 \mathbf{S}\triangleq \frac{1}{n} \sum _{i=1}^{n} \left(\mathbf X_ i \mathbf X_ i^ T \right) - \overline{\mathbf X}~ \overline{\mathbf X}^ T

Ahol:

  • \mathbf{S} – a megfigyelés Kovarianciája, egy d   \times d dimenziójú mátrix
  • ii-edik megfigyelés
  • \overline{\mathbf X} – az átlag

Ezt két módon lehet kiszámítani. Egyrészt behelyettesíthetjük az értékeket:


\mathbf{S}= \frac{1}{4} \Bigg( \left(\begin{pmatrix}  8 \\ 4 \\  \end{pmatrix} - \begin{pmatrix}  5.5 \\ 5.0  \\ \end{pmatrix} \right) \left(\begin{pmatrix}  8 \\ 4 \\ \end{pmatrix} - \begin{pmatrix}  5.5 \\ 5.0  \\ \end{pmatrix} \right)^ T + \dots + \left(\begin{pmatrix}  9 \\ 7 \\  \end{pmatrix} - \begin{pmatrix}  5.5 \\ 5.0 \\ \end{pmatrix} \right) \left(\begin{pmatrix}  9 \\ 7 \\ \end{pmatrix} - \begin{pmatrix}  5.5 \\ 5.0 \\ \end{pmatrix} \right)^ T \Bigg) \\

Lássuk be, ez elég ronda. Szerencsére van egy szebb megoldás is. A (3) egyenletet átírhatjuk. Az átlagszámítás során megismert logika alapján az első fele:


\sum _{i=1}^{n} \left(\mathbf X_ i \mathbf X_ i^ T \right) =  \mathbb {X}^ T \mathbb {X}

A második rész az (2) segítségével:


\overline{\mathbf X}~ \overline{\mathbf X}^ T = \left( \frac{1}{n} \mathbb {X}^T \cdot \mathbf{1} \right) \cdot \left(\frac{1}{n} \mathbb {X} \cdot \mathbf{1}^T \right)

Ami egyszerűsítés után:


\overline{\mathbf X}~ \overline{\mathbf X}^ T = \frac{1}{n^2} \mathbb {X}^ T \mathbf{1} \mathbf{1}^ T \mathbb {X}

Rakjuk összes:


\mathbf{S}= \frac{1}{n} \mathbb {X}^ T \mathbb {X} - \frac{1}{n^2} \mathbb {X}^ T \mathbf{1} \mathbf{1}^ T \mathbb {X}

Amit így is felírhatnánk:


\mathbf{S}= \frac{1}{n} \mathbb {X}^ T ( I_ n - \frac{1}{n} \mathbf{1} \mathbf{1}^ T ) \mathbb {X}

Ahol:

Ez talán nem tűnik elsőre egyszerűbbnek, de a középső elem egy olyan állandó, ami csak az n értékétől függ, a megfigyelések értékétől nem.

A példában szereplő minták esetén az eredmény:


\mathbf{S} = \begin{pmatrix}  9,25 &  1 \\ 1 &  7,5  \end{pmatrix}

Mi a Variancia ebből? Természetesen az átló, tehát:


\text{Var}(X) = \begin{pmatrix} 9,25 \\ 7,5 \end{pmatrix}

A kovarianciamátrixhoz tartozó sajátvektorok és sajátértékek

Sajátvektor és sajátérték

Mielőtt továbbmennék álljunk meg egy kicsit és nézzük meg mi is a sajátérték és a sajátvektor: A sajátvektor egy olyan vektor amire igaz, hogy


Ax = \lambda x

Ahol:

  • A – egy négyzetes mátrix
  • \lambda – a sajátérték
  • x – a sajátvektor

A példa kedvért nézzük meg a következőt mátrixot:


A = \begin{bmatrix}1&0\\0&1\end{bmatrix}

Ennek a mátrixnak az egyik sajátvektora:


x_1 = \begin{bmatrix}1\\1\end{bmatrix} \\

Mi lesz ebben az esetben a sajátérték? 1. Mert igaz, hogy:


\begin{bmatrix}1&0\\0&1\end{bmatrix}   \begin{bmatrix}1\\1\end{bmatrix} = \begin{bmatrix}1\\1\end{bmatrix}  1

Van egy másik sajátvektor és sajátértéke is ennek a mátrixnak:


x_2 = \begin{bmatrix}-1\\1\end{bmatrix}


\lambda_2 = 1

Vegyük észre, hogy ez a két sajátvektor merőleges egymásra. Ez igaz lesz más hasonló mátrixokra is, és azzal az érdekes ténnyel függ össze, hogy a sajátértékek összege megegyezik az A mátrix átlójának összegével.[3] Ez érdekes, mert ennek segítségével lehet meghatározni a sajátvektorokat és sajátértékeket. Most ne részreteszük a sajátvektorok konkrét számítását, inkább térjünk vissza a kovarianciamátrixunkhoz.

A kovarianciamátrix dekompozíciója

Ha jól megnézzük a kovarianciamátrixunkat akkor a fentiek alapján egyértelmű, hogy lehet az esetében saját vektorokat számítani. A kovariancia mátrix szimmetrikus és pozitív, pont úgy mint az A az előző részben. Igazából a fenti példa lehetne egy kovarianciamátrix szintén, méghozzá két egymástól független tulajdonság esetén.

Rendben, mint kiderült ennek a tudásnak a felhasználásával képesek vagyunk a kovarianciamátrixot sajátvektorok és sajátértékek segítségével is felírni, ezt konkrétan spectral dekompozíciónak nevezik:


\mathbf{S} = P D P^ T

Ahol:

  • P – egy mátrix ahol a sajátvektorok az oszlopokban helyezkednek el.
  • D – egy ortogonális mátrix, az átlón lévő értékek pedig a sajátértékek

Ami érdekes itt, hogy az új tengelyek mentén a tulajdonságok függetlenek egymástól. Persze ezek nem az eredeti tulajdonságok, hanem az újonnan kalkuláltak. Ez értelemszerűen maximalizálja a megfigyelések szórását, és mivel a varianciát információnak tekintjük ennek őrölünk.

Rendben, az egyetlen megválaszolatlan kérdés az maradt, hogy mik lesznek ezek az új varianciák. Ezek a sajátértékek. Nagyon szerencsések vagyunk, a dekompozíció megválaszolja ezt a kérdést számunka. Innen már már gyerekjáték a dimenziócsökkentés. Egyszerűen azokat a dimenziókat őrizzük meg, amelyeknek legnagyobb a sajátértéke.

Az egész nagyszerűsége abban rejlik, hogy bonyolult keresés, és sokszoros iteráció nélkül, egy lépésben a dekompozíció segítségével megkapjuk az optimális dimenziókat. Ez a tény teszi a főkomponens analízist hihetetlenül hatékonnyá.

A fenti példa esetén az eredmény a következő:


D =  \begin{bmatrix}9,70376823 &0\\     
0 &        7,04623177\\
\end{bmatrix}


P =  \begin{bmatrix}
0,91063291 &-0,41321628\\
0,41321628 & 0,91063291\\
\end{bmatrix}

Származtatjuk az új adathalmazt

Most, hogy megvannak a tengelyek, amikre vetíteni fogjuk a pontokat, végezzük el a vetítést:


X_{PCA} = P^T (X-\bar{X})

Ami az esetünkben:


X_{PCA} =  \begin{bmatrix}
1,863366  & -1,94367362\\
-1,94756635 & 4,17815573\\
-3,92944741 &-2,60949095\\
4,01364776 & 0,37500884\\
\end{bmatrix}

Ezzel készen is van az adatok feldolgozása. Lényegében előállítottunk egy teret, ahol a tulajdonságok függetlenek egymástól.

Amennyiben még dimenziócsökkentést is szeretnénk végezni, akkor már csak arról kell döntenünk melyik koordinátákat őrizzük meg. Ebben lesz segítségünkre a sajátértékek. A konkrét példánál maradva látjuk, hogy az első sajátvektor sajátértéke 9,7 míg a másodiké 7. Vagyis ha egy dimenziósra szeretnénk csökkenteni az adatainkat, akkor az első dimenziót érdemes megőrizni, vagyis a példa egy dimenziós eredménye:


X_{PCA\_1D} =  \begin{bmatrix}
1,863366\\
-1,94756635 \\
-3,92944741 \\
4,01364776 \\
\end{bmatrix}

Az egyetlen kérdés, amit még a mai bejegyzésben szeretnék tárgyalni: Mi alapján döntjük el, mennyi dimenziót örzünk meg? Ha a főkomponens analízist vizualizációs célokból végezzük, eléggé behatároltak a lehetőségeink. Amennyiben nem ez a cél, csak dimenziócsökkentés, akkor az egyik lehetőségünk, hogy ábrázoljuk a sajátértékeket, és ha valahol törést észlelünk benne, ott érdemes elvágni. Például ha a sajátértékek 10,9,8,7,1,0, akkor én az első 4 dimenziót őrizném meg. A másik lehetőség, hogy ábrázoljuk az információ veszteséget, és eldöntjük mekkora veszteséget engedhetünk meg magunknak. Például azt mondjuk 90%-át a varianciának szeretném megőrizni. Ezt a kérdést Lantos Gábor a saját bejegyzésében részretesebben tárgyalja, érdemes elolvasni az írását.

Végszó

A fenti számítások Pythonban elvégzett megfelelői megtalálhatók a blog git oldalán.

A cikk szintén letölthető PDF és ePuB változatban hála a μr² szerkesztőnek. Ez egy nyílt forráskódú online Markdown szerkesztő amit én fejlesztek, kifejezetten összetettebb írások készítésére.

[@fmitx]{ style=„opacity:0” }
[@strang]{ style=„opacity:0” }
[@smith]

Végjegyzetek

  1. Vegyük észre, hogy az 2. tulajdonság=1. tulajdonság-2. ↩︎
  2. Ez egy biasos számítás lesz, n-1-el kellene osztanunk, hogy ne az legyen. De mivel mi itt nem a varianciát keressük, és a bias nem érdekel minket, ettől most eltekintünk, mert egyszerűbb így számolni. ↩︎
  3. Ez nem mindig lesz igaz, vannak olyan mátrixok amik „degeneráltak” és bizonyos sajátvektoraik hiányoznak. A legegyszerűbb példa erre a háromszögmátrix. De szerencsére mi csak szimetrikus mátrixok esetén fogunk sajátvektort számítani, tehát ezt most ugorjuk. ↩︎

Vélemény, hozzászólás?

Adatok megadása vagy bejelentkezés valamelyik ikonnal:

WordPress.com Logo

Hozzászólhat a WordPress.com felhasználói fiók használatával. Kilépés /  Módosítás )

Twitter kép

Hozzászólhat a Twitter felhasználói fiók használatával. Kilépés /  Módosítás )

Facebook kép

Hozzászólhat a Facebook felhasználói fiók használatával. Kilépés /  Módosítás )

Kapcsolódás: %s