Principal Component Analysis

Autor: Ladislav Miženko


Popis metódy

Principal Component Analysis, čiže analýza hlavných komponentov patrí medzi metódy analýzy skrytých komponentov, medzi ktoré sa zaraďuje tiež napríklad Faktorová analýza. Takéto metódy používame, keď:

  • premenné nemožno logicky rozdeliť do dvoch skupín na závislé a nezávislé
  • cieľom je zistiť prečo a ako sú premenné vzájomne korelované, čiže ako sa navzájom ovplyvňujú
  • ak sú premenné navzájom korelované, možno rovnaký objem informácií vystihnúť menším počtom premenných – zníženie dimenzie
  • metóda analýzy hlavných komponentov vychádza  z an alýzy kovariačnej, resp. korelačnej matice pôvodných premenných a pokúša sa nájsť skryté – nemerateľné - latent prememnné. Tieto premenné sa nedajú merať, ale majú schopnosť vecnej interpretácie.

Charakteristika

  • predmetom analýzy je skupina kvantitatívnych premenných
  • metóda umožňuje vytvárať nové premenné, ktoré sú lineárnou kombináciou pôvodných premenných
  • nové premenné sa nazývajú hlavné komponenty (Principal Components)

Cieľ

  • Identifikácia odľahlých pozorovaní (outliers)
  • Zníženie dimenzie (premenných) viacrozmernej analýzy
  • Odstránenie závislosti medzi premennými, následné použitie hlavných komponentov v zhlukovej analýze, pri tvorbe regresných modelov na odstránenie multikolinearity

Matematické prepoklady

Aby sme lepšie pochopili, čo sa deje "vo vnútri" metódy, je dobre si vysvetliť niekoľko základných pojmov, ktoré budeme potrebovať.

 

Smerodajná odchýlka (Standard deviation)

Smerodajná odchýlka alebo štandardná odchýlka hovorí o tom, ako široko sú rozložené hodnoty v množine. Je druhou odmocninou rozptylu

Majme postupnosť reálnych čísiel x1, ..., xN. Aritmetický priemer (stredná aritmetická hodnota) tohto radu čísiel je definovaný ako:

 

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

Smerodajná odchýlka je definovaná ako "Priemerná vzdialenosť jednotlivých dát od ich priemernej hodnoty":

\sigma = \sqrt{\frac{\sum_{i = 1}^{N} {(X_i - \bar{X})^2}}{N}}

Pri PCA sa používa výberová smerodajná odchýlka, ktorá má tvar: 

s = \sqrt{\frac{\sum_{i = 1}^{N} {(X_i - \bar{X})^2}}{N - 1}}

 

Rozptyl (Variance)

Rozptyl je ďalší spôsob merania rozloženia hodnôt v množine. V podstate zápis je skoro rovnaký ako zápis smerodajnej odchýlky:

s^2 = \frac{\sum_{i = 1}^{N} {(X_i - \bar{X})^2}}{N - 1}

 

Kovariancia (Covariance)

Smerodajná odchýlka a rozptyl sú merania, ktoré uskutočňujeme nad jednou dimenziou našich dát, napr. výška ľudí v miestnosti. Lenže väčšina dát, ktoré získame vo svete má viac ako jeden rozmer. Napr. môžme mať databázu výšky žiakov a známku z telesnej, ktorú dostali. Potom môžeme vykonávať štatistické operácie nad týmito údajmi a zisťovať, či je medzi nimi nejaký súvis.

Na takéto operácie nám slúži napríklad práve kovariancia. Koviariancia sa vždy počíta medzi 2 dimenziami. Ak by sme počítali kovarianciu medzi jednou dimenziu a jej samou, dostali by sme rozptyl. Čiže, ak by sme mali 3-dimenzionálne dáta (x, y, z), mohli by sme merať kovarianciu medzi x a y, x a z a medzi y a z. Kovariancia medzi x a x, alebo y a y, alebo z a z by nám dala rozptyl daných dimenzií.

Vzorec na kovarianciu je veľmi podobný so vzorcom na rozptyl, ktorý by sa dal zapísať aj takto: 

var(X) = \frac{\sum_{i = 1}^{N} {(X_i - \bar{X})(X_i - \bar{X})}}{N - 1}

Kovariancia je potom:

cov(X, Y) = \frac{\sum_{i = 1}^{N} {(X_i - \bar{X})(Y_i - \bar{Y})}}{N - 1} 

Teraz si vysvetlíme, čo to vlastne znamená. Povedzme, že máme zozbierané nejaké dáta od študentov o tom, koľko času strávili pripravovaním sa na skúšku a výsledné hodnotenie zo skúšky. Čiže máme 2-dimenzionálne dáta, kde prvá dimenzia je H, čiže hodiny, ktoré strávil študent učením a druhá dimenzia B, teda počet bodov, ktoré získal študent na skúške. 

Hodiny (H)

Body (B)

Dáta 9 39
15 56
25 93
14 61
10 50
18 75
0 32
16 85
5 42
19 70
16 66
20 80
Spolu 167 749
Priemer 13,92 62,42

 

Kovariancia:

 

H B (H_i - \bar{H}) (B_i - \bar{B}) (H_i - \bar{H})(B_i - \bar{B})
9 39 -4,92 -23,42 115,23
15 56 1,08 -6,42 -6,93
25 93 11,08 30,58 338,83
14 61 0,08 -1,42 -0,11
10 50 -3,92 -12,42 48,69
18 75 4,08 12,58 51,33
0 32 -13,92 -30,42 423,45
16 85 2,08 22,58 46,97
5 42 -8,92 -20,42 182,15
19 70 5,08 7,58 38,51
16 66 2,08 3,58 7,45
20 80 6,08 17,58 106,89
Spolu 1149,89
Priemer 104,54

 

 

Takže čo nám to vlastne táto tabuľka hovorí? Presná hodnota kovariancie nie je až tak dôležitá, ako jej znamienko. Ak hodnota je kladná (tá naša je), tak to značí, že obe dimenzie vzrastajú súčasne, čiže v našom prípade s počtom narastajúcich hodín narastal aj počet bodov zo skúšky.

Ak by bola hodnota záporná, tak v tom prípade jedna dimenzia narastá a druhá klesá. Čiže ak by sme dostali kovarianciu zápornú, znamenalo by to že so zvyšujúcim sa počtom hodín učenia na skúšku by počet bodov klesal.

V prípade, že by kovariancia bola nulová, znamenalo by to, že dimenzie sú na sebe nezávislé.

Ešte jedna vec. Vzhľadom k tomu, že násobenie je komutatívna operácia, tak cov(x, y) a cov(y, x) sú rovnaké.

 

Kovariančná matica (The covariance matrix)

Ako sme si už povedali v predošlej sekcii, kovariancia sa počíta vždy medzi dvoma veličinami. Ak máme viacrozmerné dáta, budeme potrebovať vypočítať viac kovariancií. Napríklad pre dáta o troch veličinách (x, y, z) môžeme vypočítať cov(x, y), cov(x, z) a cov(y, z). Pre n-rozmerné dáta môžme vypočítať \frac{n!}{(n-2)! * 2} rôznych kovariancií.

Spôsob, akým môžme zapísať všetky kovariancie, je zapísať ich do matice. Všeobecný zápis kovariančnej matice pre n veličín vyzerá takto:

C^{n \times n} = \left ( c_{i,j}, c_{i, j} = cov(Dim_{i}, Dim_{j}) \right ),

 kde C^{n \times n} je matica o n riadkoch a n stĺpcoch a Dim_{x} je x-tá veličina. Kovariančná matica pre 3 veličiny (x, y, z) vyzerá takto: 

C = \begin{pmatrix}  cov(x, x) & cov(x, y) & cov(x, z) \\  cov(y, x) & cov(y, y) & cov(y, z) \\  cov(z, x) & cov(z, y) & cov(z, z) \end{pmatrix}

Poznámka: Všimnite si, že po diagonále sa počíta kovariancia napr. pre veličinu x a ňu samú, čiže je to rozptyl. Ďalšia zaujímavá vec je, že matica je symetrická pozdĺž diagonály.

 

Vlastné čísla, vlastné vektory matice (Eigenvalues, eigenvectors)

Predpokladám, že všetci vieme čo sú to vlastné čísla a vlastné vektory matice, ale pre istotu uvediem ich stručný popis na zopakovanie.

Štvorcová matica A rádu n má vlastné čísla \lambda_{1}, \lambda_{2}, ..., \lambda_{i} a tie sú koreňmi rovnice:

det(A - \lambda I) = 0,

kde A je štvorcová matica, λ je vlastné číslo a  I je jednotková matica. (3x3 matica, t.j. matica rádu 3 bude mať 3 alebo menej vlastných čísel)
Ku každému vlastnému číslu λ i existuje aspoň jedno nenulové riešenie sústavy rovníc

Ax = \lambda_{i} x,

kde riešenie x je pravým vlastným vektorom matice A. Ľavý vlastný vektor matice A je vlastným vektorom transponovanej matice AT a je riešením rovnice

y^T = \lambda_{i} y^T.

 

Výpočet vlastných čísel matice:

A = \begin{vmatrix}0 & -2 & 2\\ 0 & 2 & -3\\ 0 & 0 & 2\end{vmatrix}

Dosadením do vzorca získame

det (\begin{vmatrix}0 & -2 & 2\\ 0 & 2 & -3\\ 0 & 0 & 2\end{vmatrix} - \begin{vmatrix}\lambda & 0 & 0\\ 0 & \lambda & 0\\ 0 & 0 & \lambda\end{vmatrix}) = 0

Po vypočítaní determinantu dostaneme vzorec:

-\lambda * (2 - \lambda) * (2 - \lambda) = 0,

z ktorého získame tieto vlastné čísla:

\lambda_{1} = 0
\lambda_{2,3} = 2

 

Výpočet vlastných vektorov:

Máme zadané tieto hodnoty:

A = \begin{vmatrix}
 0 & -2 & 2\\ 
 0 & 2 & -3\\ 
 0 & 0 & 2
 \end{vmatrix}

\lambda_{1} = 0
\lambda_{2,3} = 2

x = \begin{vmatrix}
 x_1\\ 
 x_2\\
 x_3
 \end{vmatrix}

Riešenie rovnice pre \lambda_1 = 0:

\begin{vmatrix}
 0 & -2 & 2\\ 
 0 & 2 & -3\\ 
 0 & 0 & 2
 \end{vmatrix} * \begin{vmatrix}
 x_1\\ 
 x_2\\
 x_3
 \end{vmatrix} = 0 * \begin{vmatrix}
 x_1\\ 
 x_2\\
 x_3
 \end{vmatrix}

Prvý vlastný vektor matice je teda nulový.

Riešenie rovnice pre \lambda_{2,3} = 2:

\begin{vmatrix}
 0 & -2 & 2\\ 
 0 & 2 & -3\\ 
 0 & 0 & 2
 \end{vmatrix} * \begin{vmatrix}
 x_1\\ 
 x_2\\
 x_3
 \end{vmatrix} = 2 * \begin{vmatrix}
 x_1\\ 
 x_2\\
 x_3
 \end{vmatrix}

\begin{vmatrix}
 0 & -2x_2 & 2x_3\\ 
 0 & 2x_2 & -3x_3\\ 
 0 & 0 & 2x_3
 \end{vmatrix} = \begin{vmatrix}
 2x_1\\ 
 2x_2\\
 2x_3
 \end{vmatrix}

Po vyriešení sústavy lineárnych rovníc zistíme, že vlastný vektor matice má nekonečne veľa riešení:

x = \begin{vmatrix}
 x_1\\ 
 x_2\\
 x_3
 \end{vmatrix} = \begin{vmatrix}
 - x_2\\ 
 x_2\\
 0
 \end{vmatrix}, napr \begin{vmatrix}
 - 1\\ 
 1\\
 0
 \end{vmatrix} , \begin{vmatrix}
 - 2\\ 
 2\\
 0
 \end{vmatrix}, ...

 

Takže, teraz keď sme si ako tak zopakovali, ako sa vlastné vektory počítajú, môžeme si o nich čo to povedať.

Aké vlastnosti teda vlastné vektory maju? 

  • Vlastné vektory sa dajú počítať iba zo štvorcových matíc, aj to nie z každej,
  • ak máme maticu n x n, ktorá má vlastné vektory, tak ich je presne n,
  • zmenšením / zväčšaním vektora o nejaký pomer nezmením smer vektora, iba jeho veľkosť,
  • vlastné vektory matice sú ortogonálne, teda kolmé na seba.

Ďalšou dôležitou vecou je, že pri PCA sa používa pri vektoroch štandardná dĺžka rovná 1, čiže všetky vlastné vektory sú rovnakej dĺžky. To sa robí takto: 

\begin{pmatrix}
3\\ 
2
\end{pmatrix}

je vlastný vektor, ktorého dĺžka je

\sqrt{(3^2 + 2^2)} = \sqrt{13}

takže stačí ňou podeliť pôvodný vektor, aby sme ho upravili na dĺžku 1

\begin{pmatrix}
3\\ 
2
\end{pmatrix} \div \sqrt{13} = \begin{pmatrix}
3/\sqrt{13}\\ 
2/\sqrt{13}
\end{pmatrix}

 

Analýza hlavných komponentov

Teraz sa môžeme pustiť do popisu toho, ako funguje táto metóda. Pre jednoduchosť si to ukážeme na dátach o 2 rozmeroch, čiže s dvoma veličinami.

Krok 1: Odčítať priemer z dát

V prvom kroku získame priemernú hodnotu každej veličiny a odčítamu ju od všetkých hodnôt danej veličiny. Týmto získame množinu dát, ktorých priemer je rovný 0.

 

x y
2,5 2,4
0,5 0,7
2,2 2,9
1,9 2,2
Dáta =  3,1 3,0
2,3 2,7
2 1,6
1 1,1
1,5 1,6
1,1 0,9

 

x y
0,69 0,49
-1,31 -1,21
0,39 0,99
0,09 0,29
Upravené dáta =  1,29 1,09
0,49 0,79
0,19 -0,31
-0,81 -0,81
-0,31 -0,31
-0,71 -1,01

Original data

Krok 2: Vypočítanie kovariančnej matice

Postup výpočtu je presne taký istý, aký som uviedol v sekcii o kovariančnej matici. Keďže máme 2-rozmerné dáta, kovariančná matica bude 2x2:

cov = \begin{pmatrix}
0,616555556 & 0,615444444\\ 
0,615444444 & 0,716555556
\end{pmatrix}

Keďže nediagonálne prvky matice sú kladné, môžeme očakávať, že x aj y stúpajú súčasne.

 

Krok 3: Výpočet vlastných vektorov a a vlastných čísel kovariančnej matice

 vlastné\ čísla = \begin{pmatrix}
0,0490833989\\ 
1,28402771
\end{pmatrix}

vlastné\ vektory = \begin{pmatrix}
-0,735178656 & -0,677873399\\ 
0,677873399 & -0,735178656
\end{pmatrix} 

Je dôležité poznamenať, že vlastné vektory majú dĺžku 1, ktorú dostaneme rovnakým spôsobom, ako sme si ukázali v sekcii o vlastných vektoroch

Vlastné vektory som vykreslil na nasledujúcom grafe ako diagonálne čiarkované čiary. Ako som spomínal vyššie, sú kolmé na seba. Ale čo je dôležitejšie, opisujú nám dáta. Všimnite si ako jeden vektor prechádza cez stred dát a jednotlivé body sú umiestnené pozdĺž neho. Druhý vektor, menej dôležitejší nám ukazuje, akým smerom sa body rozptyľujú.

eigenvectors 

Takže týmto spôsobom sme získali informáciu o rozvrhnutí dát v priestore. 

Krok 4: Vybratie komponentov a vytvorenie opisného vektora (feature vector)

V tomto kroku dochádza ku kompresii dát a redukcii dimenzií (zníženie počtu veličín). Takže máme vlastné čísla a vlastné vektory kovariančnej matice. Teraz potrebujeme vybrať hlvný komponent. Hlavný komponent je vlastný vektor s najvyčším vlastným číslom.

Vo všeobecnosti, akonáhle máme nájdene vlastné vektory, ďalší krok je usporiadať ich podľa veľkosti vlasných čísel od najväčšieho po najmenšie. Takto ich usporiadame podľa dôležitosti. Teraz môžeme niektoré komponenty ignorovať. Stratíme tým síce nejakú informáciu, lenže ak je vlastné číslo komponentu malé, nestratíme veľa. Ak to trochu zovšeobecníme zistíme, že ak máme n-rozmerné dáta a získame z nich n vlastných vektorov a čísel, z ktorých vyberieme len prvých p vlastných vektorov, zredukujeme dáta len na p dimenzií.  

Ďalší krok je vytvorenie opisného vektora (feature vector), čo je vlastne len sci-fi názov pre maticu vektorov. Zoberieme vlastné vektory, ktoré si chceme nechať a vložíme ich do stĺpcov matice.

opisný\ vektor = (eig_1\ eig_2\ eig_3\ ...\ eig_n)

My máme 2 vlastné vektory, z ktorých môžme vytvoriť opisný vektor

\begin{pmatrix}
-0,735178656 & -0,677873399\\ 
0,677873399 & -0,735178656
\end{pmatrix}

alebo môžme ten mene doležitý vynechať: 

\begin{pmatrix}
-0,735178656 & -0,677873399\\ 
\end{pmatrix}

Krok 5: Vytvorenie novej množiny dát

Tento krok je posledným krokom algoritmu PCA. Po tom, ako si vyberieme hlavné komponenty a vytvoríme z nich opisný vektor, si tento opisný vektor transponujeme a prenásobíme ním povodnú množinu dát zľava, ktorá je tak isto transponovaná:

nové\ dáta = OpisnýVektor^T\ \ast\ UpravenéDáta^T

V transponovanom opisnom vektore sú uložené naše vybrané vlastné vektory v riadkoch, čiže v každom riadku je jeden vektor a v prvom riadku je uložený vektor s najväčeou dôležitosťou. V transponovaných  upravených dátach sú dáta zoradené takým spôsobom, že v každom riadku je jedna veličina (jeden rozmer).

Takže čo sme to teraz dostali? Naše pôvodné dáta mali 2 osy, x a y. Dáta je možné vyjadriť v koľkých osiach len chceme. Najefektívnejšie je, ak sú osi na seba kolmé. Preto je dôležité, že vlastné vektory sú vždy na seba kolmé. Teraz sme zmenili zobrazenie naších údajov z ôs x a y na na osi 2 vlastných vektorov. Ak by sme sa rozhodli použiť len jeden vlastný vektor, zredukovali by sme tým 1 rozmer a dáta by sme zobrazili len v 1-rozmernom priestore.

V nasledujúcej tabuľke a obrázku sú znázornené nové dáta, ktoré sú tiež zobrazené v grafe, kde môžme vidieť, že dáta sú vlastne otočené pôvodné dáta tak, aby vlastné vektory boli osi. 

 

x y
-0,827970186 -0,175115307
1,77758033 0,142857227
-0,992197494 0,384374989
-0,274210416 0,130417207
Nové dáta =  -1,67580142 -0,209498461
-0,912949103 0,1752082444
0,0991094375 -0,349824698
1,14457216 0,0464172582
0,438046137 0,0177646297
1,22382056 -0,162675287
noveData

 

Ďalšiu transformáciu by sme mohli spraviť takú, že by sme zobrali iba jeden vlastný vektor a vytvorili pomocou ňeho nové dáta. V tom prípade by sme mali iba 1-rozmerné dáta, čiže v tabuľká dát by vyzerala tak isto ako teraz, len by nemala druhý stĺpček. Na grafe by zase bola iba 1 os a po nej rozmiestnené dáta.

Ale vrátme sa späť k našej pôvodnej transformácii s dvoma vektormi. Čo nám vlasne zobrazuje náš graf s dátami? Dáta máme teraz rozdelené tak, aby sme vyjadrili v nich určitý vzor. Tým vzorom sú naše osi, ktoré nám dáta rozdeľujú. Teraz môžme povedať, kde naše dáta ležia v zmysle trendových osí, teda či ležia nad alebo pod osou.

Ako dostať pôvodné dáta späť

Ak by sme chceli dostať dáta späť v pôvodnom tvare, museli by sme pre transformáciu vybrať všetky vlastné vektory. Ak sme všetky nevzali, stratíme tým nejakú informáciu. Takže náš vzorec pre získanie dát späť je:

 

PôvodnéDáta^T = (TransOpisnýVektor^T\ \ast\ NovéDáta) + PôvodnýPriemer

V nasledujúcom obrázku je znázornená obnova dát iba s jedným vlastným vektorom. Vidíme že došlo k určitej strate informácie.

obnoveneData

 

Ukážka aplikácie v RapidMineri

 

Údaje

Pre vzorový príklad som použil voľne dostupnú databázu s nutričnými hodnotami informáciami pre 77 rôznych komerčne predávaných cereálií. Táto databáza obsahuje 15 rôznych premenných, z ktorých je 13 numerických. Týchto 13 veličín použijeme pri aplikovaní PCA a pokúsime sa zredukovať ich počet.

Údaje je možné stiahnuť na adrese http://lib.stat.cmu.edu/DASL/Datafiles/Cereals.html .

 

Popis operátora

operator

 

Dimensionality reduction

Aký typ redukcie dimenzionality sa má použiť.

  • žiadny
  • podľa kumulácie rozptylu
  • fixný počet komponentov

Variance threshold

Túto možnosť dostaneme, ak vyberieme typ redukcie dimenzie podľa rozptylu. Nastavuje sa tu, po akú hodnotu kululatívneho rozptylu si chceme komponenty ponechať.

Number of components

Nastavíme presný počet komponentov, ktoré chceme ponechať. Komponenty sú zoradené tak, ako je to popísané v sekcii o Vyberaní komponent.

 

Proces

Krok 1: Načítanie údajov

Jednoduché načítanie údajov z excelovského súboru, ktoré myslím netreba viac komentovať.

Krok 2: Normalizácia dát

Načítané dáta musíme znormalizovať pomocou operátora Normalize. Tieto dáta byť normalizované musia, pretože nie sú v jednotnej mierke a tým pádom môže dôjsť ku skresleniu výpočtov a tak nám môže vyjsť, že pre našu potrebuje budú postačovať 3 vlastné vektory namiesto 5. Tým by sme prišli o značnú stratu informácie.

Krok 3: Aplikovanie operátoru PCA

Operátor PCA sa nachádza pod Data Transformation -> Attribute Set Reduction and Transformation -> Transformation , alebo stačí jednoducho zadať do vyhľadávača PCA. Pretiahneme operátor do okna s procesom a prepojíme ho s našími znormalizovanými dátami.

Krok 4: Aplikovanie modelu

Teraz použijeme operátor Apply Model a prepojíme ho nasledovne:

  • z operátoru PCA prepojíme "ori"ginal port s portom "unl"abled data v operátore Apply Model
  • z operátoru PCA prepojíme "pre"processing port s portom "mod"el v operátore Apply Model
  • z operátoru Apply Model prepojíme porty "lab" a "mod" na výstup "res"
rapidminer example

Krok 5: Vysvetlenie výsledkov

Po spustení procesu sa nam v perspektíve výsledkov zobrazí záložka "PCA", kde si môžme prepínať medzi 3 prepínačmi: "Eigenvalues", "Eigenvectors" a "Cumulative Variance Plot".

vysledky

V "Eigenvalues" máme informácie o rozptyloch a štandardnej odchýlke pre jednotlivé komponenty. Ak napr. si povieme, že prah našich rozptylov bude 90%, tak nám bude stačiť len prvých 7 vlastných vektorov.

V "Eigenvectors" máme zobrazené jednotlivé vlastné vektory a v "cumulative Variance Plot" máme vývoj rozptylu vzhľadom ku každému vlastnému vektoru.

 

Súbory

Vzorový príklad v RapidMineri - stiahnuť icon


Zdroje

  1. Analýza hlavných komponentov, Matejková - www.fem.uniag.sk/cvicenia/ksov/matejkova/VSA/PCA_11.pptx
  2. RapidMiner Wiki - Principal Component Analysis - http://rapid-i.com/wiki/index.php?title=Principal_Component_Analysis
  3. How to run Principal Component Analysis with RapidMiner - http://www.simafore.com/blog/bid/62910/How-to-run-Principal-Component-Analysis-with-RapidMiner-Part-1
  4. A tutorial on Principal Components Analysis, Lindsay I Smith, 2002 - http://www.cs.otago.ac.nz/cosc453/student_tutorials/principal_components.pdf
  5. Analýza hlavních komponent - Příručka použití pro inženýry, Ing. Jakub Šťastný, Ph.D., 2007 - http://amber.feld.cvut.cz/fpga/prednasky/asi/pca.pdf
  6. Numerická matematika - http://www.math.chytrak.cz/math/matice/cisla.php