PCA és SVD esetén az új attribútumok a régiek lineáris kombinációi. A faktoranalízis célja az eredeti változók kisebb számú, úgynevezett rejtett változók (hidden, latent attributes) lineáris kombinációjaként való kifejezése. Emögött a törekvés mögött a következő megfigyelés áll. Gyakran vannak az adatobjektumoknak olyan jellemzői, melyeket nehéz közvetlenül mérni, ám ezek a nehezen mérhető attribútumok kapcsolatban állnak néhány könnyebben mérhető jellemzővel. Tipikus példa erre az intelligencia és ennek mérése különböző IQ-tesztekkel, vagy atléták versenyteljesítményének kapcsolata a gyorsasággal vagy az erővel. Ha sikerül mindössze néhány attribútum segítségével csoportosítani és összegezni az eredetieket, akkor elértük célunkat: csökkentettük a dimenziót és növeltük az adatok áttekinthetőségét.

A faktoranalízis lényegét gyakran a kovariancia- vagy korrelációs mátrix segítségével fogalmazzák meg. Tegyük fel, hogy attribútumok egy csoportja nem túl erősen korrelál egy másik csoporttal, de erősen korrelál egy harmadikkal. Ez esetleg azért lehet, mert ugyanazt a háttérben megbúvó mennyiséget mérik. Ilyen esetben kívánatosnak tűnhet olyan módszereket kifejleszteni, amelyek egy olyan önálló, háttérben lévő attribútumot tudnak találni, amely mindegyik ilyen csoportot összegez.

Példaképpen tekintsünk egy adathalmazt, mely atléták egy csoportjának teljesítményét méri a dekatlonban szereplő tíz versenyszámban. Azt várhatjuk, hogy az egyes atléták azokban a számokban mutatnak közel azonos teljesítményt, melyben például a sebesség alapvető fontosságú. Vagyis a lassabb atléták ,,következetesen'' lassabbak minden számban, a gyorsabbak pedig következetesen gyorsabbak. Hasonlóan megjósolható az is, hogy azok az atléták, akik egy versenyszámban erősebbnek bizonyultak, más, nagy fizikai erőnlétet kívánó számban is jobban teljesítenek. Mindent egybevetve, feltételezhetjük, hogy egy atléta egyes versenyszámokban elért teljesítménye az adott versenyszám természetétől és két tényezőtől -- a gyorsaságtól és az erőtől -- függ. A faktoranalízis célja éppen ezeknek a kapcsolatoknak a feltárása.

A formálisabb tárgyalás kedvéért legyenek f 1 , f 2 ,…, f p vektorok a látens faktorok, vagyis a rejtett változók. Megjegyezzük, hogy ezek új attribútumok és minden objektumra rendelkeznek értékkel. Ha az eredeti D adatmátrix egy m -szer n -es mátrix, akkor az új adatmátrix F=[ f 1 , f 2 ,…, f p ] , amely egy m -szer p -s mátrix. (Megjegyezzük, hogy f *j = f j .) Az F ij -edik eleme f ij , f i j -edik komponense.

Tegyük fel, hogy minden attribútum középértéke 0. Ha d i* az eredeti D mátrix i -edik sora, akkor f i* az új F adatmátrix megfelelő sora. A klasszikus faktoranalízis modellje feltételezi, hogy a régi és új adatobjektumok között a következő kapcsolat áll fenn:

d i* T =Λ f i* T +ε, (B.3)

vagy, ami ezzel egyenértékű,

d ij = λ j1 f i1 + λ j2 f i2 ,…, λ jp f ip + ε i . (B.4)

Λ , melynek elemei a λ kl számok, az ún. faktoregyüttható (factor loadings) n -szer p -s mátrix. Ez az eredeti változókra vonatkozóan azt jelzi, hogy ezek hogyan függenek a rejtett változóktól, azaz az új attribútumoktól. A dekatlon példán szemléltetve, két rejtett változónak kell lennie: sebesség és gyorsaság. Ezek F oszlopainak felelnek meg. Minden atlétának megfelel az F egy sora, amely elemei az atléta sebessége és gyorsasága. D oszlopai a dekatlon tíz versenyének felelnek meg és a sorok itt is az atlétát azonosítják. D ij -edik eleme az i -edik atléta j -edik versenyben nyújtott teljesítménye. Λ tehát egy 10-szer 2-es mátrix. Ha például D első oszlopában a sportolók 100 m-en nyújtott teljesítményei szerepelnek, akkor az i -edik atléta 100 m-en elért eredménye d i1 = λ 11 f i1 + λ 12 f i2 alakban írható, ahol f i1 az i -edik atléta sebessége f i2 pedig az általa kifejtett erő. λ 11 és λ 12 az a súly, amellyel rendre az atléta sebességét és erőnlétét figyelembe kell venni a 100 m-en nyújtott teljesítmény előrejelzéséhez. Emiatt azt várhatjuk, hogy λ 11 viszonylag nagy λ 12 -höz képest. A súlyok nyilván ugyanazok minden versenyzőre.

Mivel az összes látens faktort bevonjuk mindegyik eredeti attribútum értékének meghatározásához, ezeket közös faktoroknak nevezzük. Az ε egy hibatag, mely az attribútumok közös faktorok által nem magyarázott hányadának felel meg. ε koordinátái egyedi faktorok néven ismertek.

B.4. Példa

(Az írisz adatok faktoranalízise) Ez a példa az Írisz adatállományon alapszik. Ezekre az adatokra csak egyetlen faktort találunk. Az adathalmaz úgy áll össze, hogy az első 50 adat a nőszirom, a második 50 a foltos nőszirom, a harmadik 50 pedig a virginiai nőszirom adatait tartalmazza. Az egyetlen faktort (attribútumot) fig:factor_analysis_iris. ábrán tüntettük fel. Látható, hogy ez a faktor jól elkülöníti a három fajt.

Az LLE (locally linear embedding) egy olyan dimenziócsökkentési módszer, amely az átfedő lokális környezetek elemzésének ötletén alapul, melynek célja a lokális struktúra feltárása.

A második lépésben a w ij elemekből álló, súlymátrixnak nevezett W mátrixot a legkisebb négyzetek módszere segítségével kell megkeresni. (Ilyen problémát az A. függelékben tárgyaltunk.)

hiba(W)= ∑ i ( x i − ∑ j w ij x j ) 2 (B.5)

A harmadik lépés végzi el ténylegesen a dimenziócsökkentést. Adott W súlymátrix és a felhasználó által megadott p dimenzió paraméter mellett az algoritmus meghatározza az adatok alacsonyabb dimenziós térbe történő ,,szomszédság-megőrző beágyazását''. Ha y i az x i -nek megfelelő vektor az alacsonyabb dimenziós térben, és Y az az új adatmátrix, melynek i -edik sorában y i áll, akkor Y úgy kereshető meg, hogy a következő kifejezés minimumát vesszük:

hiba(Y)= ∑ i ( y i − ∑ j w ij y j ) 2 . (12.4)

B.5. Példa.

Az LLE dimenziócsökkentési módszert szemlélteti az íriszek adathalmazán a B.5. ábra. Itt az adatokat két dimenzióra vetítettük, és 30-ban határoztuk meg a szomszédos pontok számát. Az adatok egy dimenzióra is vetíthetőek, ekkor a helyzet hasonló, mint amit a B.4. ábrán láthattunk.

A többdimenziós skálázás (MDS -- Multidimensional Scaling) gyakori dimenziócsökkentési eljárás. Bár ennek a módszernek többféle variánsa létezik, a lényeg mindegyikben ugyanaz: az adatok olyan alacsonyabb dimenziós térbe történő vetítését kell megtalálni, mely a lehető legnagyobb mértékben megőrzi a páronkénti távolságot, amit egy célfüggvénnyel mérünk. A módszerből fakadóan az MDS egy különbözőségi mátrixból indul ki, emiatt olyan adatok, például stringek, esetén is használható, melynek eredetileg nincs is vektortér-reprezentációja.

Alapvető MDS módszerek

A klasszikus MDS módszerek bemutatását adatok p dimenziós térbe való vetítésével kezdjük. Tegyük fel, hogy megadtunk egy D távolságmátrixot, ahol a d ij elem az i -edik és j -edik objektum távolsága. Legyen továbbá d ij ' az objektumok transzformáció utáni távolsága. A klasszikus MDS célja az objektumokhoz egy p dimenziós pontot rendelni oly módon, hogy az ún. feszültség (stress) minimális legyen:

feszültség= ∑ ij ( d ij ' − d ij ) 2 ∑ ij d ij 2 . (B.7)

Az MDS klasszikus verziója példa metrikus MDS-re, mely megköveteli, hogy a különbözőségek folytonos (intervallum vagy hányados) változók legyenek. A nem-metrikus MDS módszerek alapja, hogy az adatok kategorikusak (legjobb ha sorrendiek). Nem tárgyaljuk részletesen ezeket az algoritmusokat, pusztán megjegyezzük, hogy a tipikus eljárás szerint az adatokhoz valamilyen módon hozzárendeljük a p dimenziós tér bizonyos pontjait, majd úgy módosítjuk ezeket a pontokat, hogy minimális legyen a feszültség.

Ha a klasszikus MDS-t vagy annak valamely más standard változatát használjuk az íriszek adathalmazára, majdnem ugyanazt az eredményt kapjuk, mint amit a B.2. ábra mutat. Ez azért van így, mert az euklideszi távolságon alapuló klasszikus MDS ekvivalens a PCA-val.

FastMap

Az MDS területén született egyik új algoritmus a FastMap. A cél itt is ugyanaz, mint a többi MDS módszernél, de két jelentős különbség mégis van:

A FastMap algoritmus objektumok egy párjának azonosításával kezdi, majd az összes többi objektum távolságát kiszámítja ebben az irányban. Ehhez elegendő mindössze páronkénti távolságokat használni, mert bizonyos geometriai tényeket is alkalmazhatunk, nevezetesen a koszinusztörvényt. Az első attribútum értékének ezt a távolságot választjuk. Ezután az objektumokat egy (n−1) -dimenziós térre vetítjük. Ezekhez a műveletekhez megint csak elég páronkénti távolságokat használni. A folyamat ezután megismételjük.

A FastMap algoritmust először a teljes adathalmazra alkalmazzuk. Ha azonban nyomon követjük azokat az objektumpárokat, melyeket az egyes lépések során választottunk ki, akkor növekményesen alkalmazhatjuk a FastMap algoritmust az új objektumra. Az egyetlen információ, melyre szükségünk van, az új objektum távolsága a kiválasztott adatpároktól.

ISOMAP

Az MDS és a PCA algoritmusok nem túl hatékonyak, ha a pontok között bonyolult, nemlineáris kapcsolat áll fenn. (Egy kivétel a magfüggvényes PCA -- lásd az irodalmi megjegyzéseket.) Az ISOMAP a tradicionális MDS kiterjesztéseként éppen az ilyen problémák orvoslására hivatott. A B.6. ábra -- az ún. ,,Swiss roll''^[9] -- olyan adatsorra példa, mely az ISOMAP-pel jól kezelhető. Az ilyen struktúrájú adatok háromdimenziós térbe ágyazottak, ám valójában kétdimenziósak. A PCA vagy az MDS nehezen kezelné, ám az ISOMAP sikeresen elemzi ezt az adathalmazt.

A B.2. algoritmus vázolja az alapvető ISOMAP módszert.

Egy pont legközelebbi szomszédjai definiálhatóak úgy, hogy vagy a k legközelebbi pontot vesszük, ahol k egy paraméter, vagy az összes pontot vesszük egy pont egy meghatározott sugarán belül. Az algoritmus második lépésének célja, hogy kiszámolja két pont geodetikus távolságát (az euklideszi helyett), azaz azt a távolságot, amely a felületen húzódó legrövidebb összekötő szakasz hossza. Például a Föld két átellenes pontján adott város hagyományos (ún. euklideszi) távolsága a Föld belsején át húzódó összekötő szakasz hossza, míg a geodetikus távolság a két várost összekötő legrövidebb ív a Föld felszínén.

B.6. Példa.

Az íriszek adatainak levetítése két dimenzióba az ISOMAP segítségével. Lásd a B7. ábrát. Az eredmény hasonló a korábbiakhoz.

Mint más adatelemzési módszereknél, számos szempont alapján tehetünk különbséget a dimenziócsökkentési módszerek között. Kulcsfontosságú szempont az eredmény minősége: képes-e egy módszer az adatok ésszerűen pontos reprezentációját adni egy alacsonyabb dimenziójú térben? Valóban kiemeli-e ez a reprezentáció az adatok adott vizsgálódás szempontjából lényeges jellemzőit (például ténylegesen elkülöníti-e a klasztereket)? Mindeközben figyelmen kívül hagyja-e a vizsgálódás szempontjából érdektelen vagy akár káros vonatkozásokat (például zajokat)?

A válasz nagyrészt az adatok típusától és eloszlásától függ, melyet dimenziócsökkentési megközelítéssel elemezhetünk. A PCA, SVD vagy a faktoranalízis feltételezi, hogy a régi és az új attribútumok között lineáris a kapcsolat. Noha ez közelítőleg teljesülhet sok esetben, gyakori, hogy nemlineáris megközelítés szükséges. Az olyan algoritmusokat, mint az ISOMAP és az LLE, elsősorban a nemlineáris kapcsolatok kezelésére dolgozták ki.

A dimenziócsökkentési algoritmusok idő- és tárbonyolultsága kulcsfontosságú szempont. A tárgyalt algoritmusok nagy része O( m 2 ) vagy nagyobb idő- és/vagy tárbonyolultságú, ahol m az objektumok számát jelöli. Ez korlátozhatja a nagyobb adathalmazokon való alkalmazhatóságukat, bár a mintavételezés néha egészen hatékonyan használható. A FastMap az egyetlen olyan általunk tárgyalt algoritmus, amely lineáris idő- és tárbonyolultságú.

Egy másik fontos szempont, hogy a dimenziócsökkentési algoritmusok az egyes futások alkalmával ugyanazt az eredményt adják-e. A PCA, SVD és LLE algoritmusoknál ez teljesül. A faktoranalízis és az MDS azonban már különböző eredményeket ad az egyes futások alkalmával. Sok más, általunk nem tárgyalt módszer is ezzel a tulajdonsággal bír, aminek az az oka, hogy megpróbálnak valamilyen célfüggvény szerint optimalizálni, és keresés közben csapdába eshetnek egy lokális minimum körül. A keresés alapú megközelítések szintén rossz időbonyolultsággal bírhatnak.

Végül az is lényeges megválaszolandó kérdés, hogy mennyi legyen a végső dimenziószám. Az áttekintett módszerek tipikusan jól működnek majdnem minden dimenziószám esetén. A csökkenés jósága mérhető néhány kirajzolható mennyiség révén, mint a kőtörmelék-ábrán. Néhány esetben egy ilyen ábra tisztán megmutatja a valódi dimenziót. Más esetekben viszont választanunk kell: kevesebb dimenziót akarunk, ám a hiba nagyobb lesz; vagy a kisebb hiba érdekében növeljük a dimenziót.