B. függelék - Dimenziócsökkentés

Tartalom

PCA és SVD
Főkomponens analízis (PCA)
SVD
További dimenziócsökkentési módszerek
Faktoranalízis
Lokális lineáris beágyazás (LLE)
Többdimenziós skálázás (MDS), FastMap és ISOMAP
Közös szempontok
Irodalmi megjegyzések

Ez a függelék a dimenziócsökkentés különféle módszereit mutatja be. A célunk az, hogy ismertessük az Olvasóval az ezzel a témával kapcsolatos kérdéseket és leírjunk néhány általános megközelítést. A főkomponens analízissel (PCA -- Principal Component Analysis) és szinguláris érték felbontással (SVD -- Singular Value Decomposition) kezdjük. Ezeket a módszereket részletesen tárgyaljuk, mivel ezek a leggyakrabban alkalmazottak, és a hozzájuk szükséges lineáris algebrai ismereteket az A. függelékből már megtanultuk. Egyéb módszerek is léteznek azonban a dimenziócsökkentésre, melyek közül a fontosabbakat a szakasz végén ismertetjük röviden. A függeléket a fontosabb szempontok áttekintésével zárjuk.

PCA és SVD

A PCA és az SVD két közeli rokonságban álló módszer. A PCA-nál eltávolítjuk az adatok átlagát, ezzel szemben az SVD-nél ezt nem tesszük. Ezeket a módszereket évtizedek óta használják számos területen. A következőkben feltesszük, hogy az Olvasó -- legalábbis az A. függelék szintjén -- járatos a lineáris algebrában.

Főkomponens analízis (PCA)

A főkomponens analízis célja dimenziók (attribútumok) olyan új halmazának a keresése, mely jobban tükrözi az adatok variabilitását. Az első dimenziót úgy választjuk meg, hogy a maximálisan lehetséges mértékű variabilitást hordozza. A második dimenzió merőleges az elsőre és ezen kényszerfeltétel mellett a fennmaradó variabilitásból a lehető legtöbbet hordozza, és így tovább.

A PCA-nak számos vonzó előnye van. Először is, segítségével könnyebb megtalálni az adatokat legjobban jellemző mintázatokat. Ezért a PCA mintázat-kereső módszerként is használható. Másfelől gyakori, hogy az adatok nagyon nagy mértékben tömöríthetők az információtartalom lényeges csökkenése nélkül. Utóbbi miatt a PCA-n alapuló dimenziócsökkentés relatíve alacsony dimenziót eredményez, mely már olyan eszközökkel is kezelhető, ami a kiinduló adatokon nem használható. Harmadik előny, hogy mivel az adatokban található zaj (reményeink szerint) gyengébb, mint a mintázatok, a dimenziócsökkentés a zajok nagy részét képes kiküszöbölni. Ez hasznos az adatbányászatban, de más adatelemző algoritmusok esetén is.

Most röviden felvázoljuk a PCA matematikai alapjait, és egy példát is bemutatunk.

Matematikai részletek

A statisztikusok egy többváltozós -- azaz több, folytonos attribútummal rendelkező -- adatsor variabilitását többek között az S kovarianciamátrixszal jellemzik.

B.1. Definíció

Ha adott egy m -szer n -es D adatmátrix, melynek m sora az adatokat azonosítja, n oszlopa pedig a jellemzőket, akkor D kovarianciamátrixa az az S mátrix, melynek s ij eleme

s ij =kovariancia( d *i , d *j ). (B.1)

Szavakkal, s ij az i -edik és j -edik attribútum (oszlop) kovarianciája. Két attribútum kovarianciáját a C. függelékben definiáljuk, és azt méri, hogy a két mennyiség mennyire erősen függ egymástól. Ha i=j , vagyis a két mennyiség ugyanaz, akkor a kovariancia a varianciát adja vissza. Ha az adatmátrix előzetes feldolgozásával azt olyan alakúra hoztuk, hogy az egyes attribútumok középértéke 0, akkor S= D T D .

A PCA célja olyan transzformáció megkeresése, mellyel az adatok a következő tulajdonságúra hozhatók:

  1. Minden új (különböző elemekből álló) attribútumpár kovarianciája 0.

  2. Az attribútumok aszerint vannak rendezve, hogy milyen mértékben járulnak hozzá a szóráshoz.

  3. Az első attribútum járul hozzá a szóráshoz a legnagyobb mértékben.

  4. Az ortogonalitási feltétel miatt minden egyes bevont attribútum olyan mértékben járul hozzá a szóráshoz, amennyire csak lehetséges.

Az adatoknak az a transzformációja, mely ezeket a tulajdonságokat eredményezi, megkapható a kovarianciamátrix sajátértékeinek elemzésével. Legyenek e célból λ 1 ,, λ n az S sajátértékei. A sajátértékek mindegyike nemnegatív, és rendezhető úgy, hogy λ 1 λ 2 λ m1 λ m teljesüljön. (A kovarianciamátrix példa úgynevezett pozitív szemidefinit mátrixra, mely egyéb tulajdonságai mellett például nemnegatív sajátértékekkel bír.) Legyen U=[ u 1 ,, u n ] az S sajátvektoraiból álló mátrix. A sajátvektorok legyenek úgy rendezve, ahogy a sajátértékeik: az i -edik sajátvektor tartozzon az i -edik legnagyobb sajátértékhez. Tegyük fel végül, hogy a D adatmátrix az előfeldolgozás során úgy lett átalakítva, hogy minden attribútum (oszlop) középértéke 0. A következőket állíthatjuk.

  • A D ' =DU adatmátrix a transzformált adatok olyan halmaza, mely már teljesíti a fentebbi feltételeket.

  • Minden új attribútum az eredetiek lineáris kombinációja. Konkrétabban, az i -edik attribútumot előállító lineáris kombináció súlyai az i -edik sajátvektor komponensei. Ez az (A.12) mátrixszorzási szabályból és abból a tényből jön, hogy D ' j -edik oszlopát D u j adja meg.

  • Az i -edik új attribútum varianciája λ i .

  • A régi és az új attribútumok varianciáinak összege megegyezik.

  • Az új jellemzőket főkomponenseknek nevezzük, így például az első új attribútum az első főkomponens, és így tovább.

A legnagyobb sajátértékhez tartozó sajátvektor jelzi azt az irányt, amely irányban a legnagyobb az adatok varianciája. Ezt szemléletesebben úgy is kifejezhetjük, hogy ha az összes adatvektort rávetítenénk ezen sajátvektor által megadott egyenesre, akkor a keletkező értékeknek így lenne a legnagyobb a varianciájuk minden lehetséges irány közül. A második legnagyobb sajátértékhez tartozó sajátvektor azt az irányt adja meg, mely egyfelől merőleges az előzőre, és melyre nézve az adatoknak a legnagyobb a megmaradó varianciája.

S sajátvektorai új tengelyeket definiálnak. A PCA tehát úgyis tekinthető, mint a koordinátatengelyek olyan irányú forgatása, melyet az adatok variabilitása határoz meg. A teljes szóródás a transzformáció során megmarad, de az új attribútumok már korrelálatlanok lesznek.

B.1. Példa.

(Kétdimenziós adatok) A PCA használatát szemléltetjük azzal, hogy a koordinátatengelyeket a maximális szórás irányába ,,állítjuk''. A B.1. ábra 1000 darab kétdimenziós adatpontot mutat a PCA előtt és után. A teljes szórás az x és y attribútumok szórásainak összege: 2,84+2,95=5,79 . Transzformáció után a szórás 4,81+0,98=5,79 .

B.1. ábra - PCA használata adattranszformációhoz

PCA használata adattranszformációhoz

B.2. Példa.

(Írisz adatok) Ez a példa az íriszek (nőszirom) korábban már tárgyalt adatsorán mutatja be a dimenziócsökkentést. Ez az adatsor 150 adat objektumot (virágok) tartalmaz. 50 virág van, három különböző fajból: nőszirom (Setosa), foltos nőszirom (Versicolor) és virginiai nőszirom (Virginica). Minden növény négy jellemzőjét tároljuk: csészelevél hossza és szélessége, sziromlevél hossza és szélessége. Részletesebb információ található a 3. fejezetben.

A B.2. (a) ábra bemutatja, hogy a kovarianciamátrix egyes sajátértékei (a főkomponensek) milyen mértékben magyarázzák a teljes szórást. Ezt a típusú ábrát kőtörmelék ábrának[8] (scree plot) nevezzük, és a megtartandó főkomponensek számának meghatározására használjuk azért, hogy megőrizzük az adatok ingadozásának a legnagyobb részét. A nőszirom adatai esetében az első főkomponens magyarázza a szórás legnagyobb részét (92,5%), a második csak 5,3%-ot magyaráz, az utolsó kettő pedig csak 2,2%-ot. Így ha csak az első két főkomponenst tartjuk meg, akkor az adatsor variabilitásának nagy részét megőrizzük. A B.2. (b) ábra az első két főkomponens alapulvételével készült pontdiagramot szemléltet. Érdekes megjegyezni, hogy a nőszirom első faja jól elkülönül a másik kettőtől. Bár a másik kettő sokkal közelebb van, még ezek is jól elválnak egymástól.

B.2. ábra - PCA a nőszirom adathalmazára alkalmazva

PCA a nőszirom adathalmazára alkalmazva

SVD

Ha a változókat már normalizáltuk, akkor a PCA és az SVD ekvivalens módszerek. Ennek ellenére érdemes a dimenziócsökkentésre az SVD oldaláról is rátekinteni, ugyanis nem mindig kívánatos a középérték eltávolítása. Különösen igaz ez ritka adatok esetén.

Matematikai részletek

Az A. függelékből tudjuk, hogy egy m -szer n -es A mátrix az

A= i=1 rang(A) σ i u i v i T =UΣ V T (B2)

formában is írható, ahol σ i az i -edik szinguláris értéke A -nak ( Σ i -edik diagonális eleme), u i az A i -edik bal szinguláris vektora ( U i -edik oszlopa) és v i az A i -edik jobb szinguláris vektora ( V i -edik oszlopa). (Lásd az A.5. szakaszt.) Az adatmátrix SVD-felbontása a következő tulajdonságokkal rendelkezik.

  • Az attribútumok közötti mintázatokat a jobb szinguláris vektorok ( V oszlopai) tárolják.

  • Az objektumok menti mintázatokat a bal szinguláris vektorok ( U oszlopai) tárolják.

  • Az A mátrix fokozatosan és optimálisan közelíthető a (B.2) egyenletbeli összeg egyes tagjaival. Itt nem fejtjük ki bővebben, hogy mit értünk ,,optimális'' alatt, ehelyett az irodalomi megjegyzésekre hivatkozunk. Informálisan, minél nagyobb egy szinguláris érték, a mátrix annál nagyobb hányadát magyarázza a hozzátartozó szinguláris vektorokkal együtt.

  • Új, k darab attribútumot tartalmazó adatmátrixhoz úgy jutunk, hogy kiszámoljuk a D ' =D*[ v 1 , v 2 ,, v k ] mátrixot. Az előző fejtegetésekből következően látható, hogy az (A.12) egyenlet első k tagjából előálló mátrixot kell vennünk. Habár az így létrejövő mátrix n oszloppal (attribútummal) rendelkezik, a rangja mégis k .

B.3. Példa.

(Dokumentum adatok) Az SVD felbontás alkalmas dokumentum-jellegű adatok elemzésére is. Ebben a példában az adatok a Los Angeles Times 3204 cikkét tartalmazzák. A cikkek hat területre esnek: szórakozás, pénzügyi, külügyi, belföldi, közlekedés, sport. Az adatmátrix most egy olyan dokumentum-kifejezés mátrix, amelyben a sorok dokumentumokat, az oszlopok kifejezéseket (szavakat) tartalmaznak. Az ij -edik elem annak a száma, ahányszor a j -edik szó az i -edik dokumentumban előfordul. A szinonimák kiszűrése, illetve az egyes szavak gyakoriságának és a dokumentumok különböző méretének figyelembevétele érdekében az adatok előzetes feldolgozáson estek át. (A részletekért lásd a 2.3.7. szakaszt.)

Az SVD analízist abból a célból végeztük el, hogy az első 100 szinguláris értéket és vektort kiszűrjük. (Sok adathalmaz esetében túl költséges vagy akár felesleges is a teljes SVD vagy PCA felbontást megkeresni, hiszen viszonylag kevés szinguláris érték vagy sajátérték elegendő a mátrix struktúrájának feltárásához.) A legnagyobb szinguláris érték a leggyakoribb -- előzetes feldolgozás által meghagyott -- közös kifejezésekhez tartozik. (Megtörténhet, hogy a legerősebb mintázat zajt vagy érdektelen mintázatot takar.)

A többi szinguláris értékhez tartozó mintázat már érdekesebb. Például a következő kifejezések fordultak elő leggyakrabban a második jobb szinguláris vektor legerősebb koordinátáihoz rendelve:

game, score, lead, team, play, rebound, season, coach, league, goal

Mindegyik szó a sporttal kapcsolatos. Nem meglepő, hogy a második bal szinguláris érték legerősebb koordinátáihoz rendelt dokumentumok (újságcikkek) túlnyomó többségben a Sport rovatból származnak.

A harmadik jobb szinguláris vektor legerősebb koordinátáihoz tartozó 10 leggyakoribb kifejezés:

earn, million, quarter, bank, rose, billion, stock, company, corporation, revenue

Mindegyik szó pénzügyekkel kapcsolatos, és így nem meglepő, hogy a harmadik bal szinguláris érték legerősebb komponenseihez rendelt dokumentumok túlnyomó többségben az üzleti rovatból származnak.

Az adatok dimenzióját a második és harmadik szinguláris vektor segítségével csökkentettük: D ' =D*[ v 2 , v 3 ] . Más szavakkal, minden dokumentumot két attribútum szerint fejeztünk ki, az egyik a sportra, a másik a pénzügyre vonatkozott. A dokumentumok pontdiagramját a B.3. ábra mutatja. A jobb áttekinthetőség kedvéért a nem sporttal vagy pénzüggyel kapcsolatos cikkeket elhagytuk az ábráról. A sportrovat cikkeit világosabb, az üzleti rovat cikkeit sötétebb szürkével jelöltük. A két kategória jól elkülönül. Valóban, a sport rovat cikkei nem változnak nagyon az üzleti rovat változójának (harmadik koordináta) függvényében, és az üzleti rovat cikkei sem változnak nagyon a sport rovat változójának (második koordináta) függvényében.

B.3.. ábra - A Los Angeles Times sport- és üzleti rovata cikkeinek pontábrája a második és harmadik szinguláris érték figyelembevételével

A Los Angeles Times sport- és üzleti rovata cikkeinek pontábrája a második és harmadik szinguláris érték figyelembevételével



[8] A fordító megjegyzése: A kőtörmelék ábra olyan, mint egy hegy oldala. A hegytetőről lehulló törmelékdarabok a hegy oldalvonalának töréspontjain állnak meg. Az elnevezés innen származik.