Adatok el˝ofeldolgoz´asa Kulcs´ar G´eza
Budapest, 2012. febru´ar 23.
Mi´ert van sz¨uks´eg el˝ofeldolgoz´asra? Az adatb´any´aszat a nagy mennyis´eg˝ u adatokban rejl˝o inform´aci´ok felt´ar´asa. Milyen form´aban ´all az adat rendelkez´esre? ´ aban: Altal´
Mi´ert van sz¨uks´eg el˝ofeldolgoz´asra? Az adatb´any´aszat a nagy mennyis´eg˝ u adatokban rejl˝o inform´aci´ok felt´ar´asa. Milyen form´aban ´all az adat rendelkez´esre? ´ aban: Altal´ I
Hi´anyos
Mi´ert van sz¨uks´eg el˝ofeldolgoz´asra? Az adatb´any´aszat a nagy mennyis´eg˝ u adatokban rejl˝o inform´aci´ok felt´ar´asa. Milyen form´aban ´all az adat rendelkez´esre? ´ aban: Altal´ I
Hi´anyos
I
Zajos
Mi´ert van sz¨uks´eg el˝ofeldolgoz´asra? Az adatb´any´aszat a nagy mennyis´eg˝ u adatokban rejl˝o inform´aci´ok felt´ar´asa. Milyen form´aban ´all az adat rendelkez´esre? ´ aban: Altal´ I
Hi´anyos
I
Zajos
I
Inkonzisztens
Hogyan el˝ofeldolgozzunk? I
Milyen az adat? → le´ır´as, statisztika
I
Hi´anyos, zajos, inkonzisztens → adattiszt´ıt´as
I
T¨obb adatforr´as → integr´aci´ o
I
Nagy adatmennyis´eg → redukci´ o
Az adat le´ır´asa, jellemz˝oi Attrib´ utum t´ıpusok I
I. Kateg´oria t´ıpus´ u attrib´ utumok: csak az egyenl˝os´eg vizsg´alhat´o
I
II. Sorrend t´ıpus´ u attrib´ utumok: >, <, = eld¨ onthet˝o, azaz van teljes rendez´es
I
III. Intervallum t´ıpus´ u attrib´ utumok: az elemek csoportot alkotnak
I
IV. Ar´any sk´al´aj´ u attrib´ utum: van z´erus elem is
Az adat le´ır´asa, jellemz˝oi Attrib´ utum t´ıpusok I
I. Kateg´oria t´ıpus´ u attrib´ utumok: csak az egyenl˝os´eg vizsg´alhat´o
I
II. Sorrend t´ıpus´ u attrib´ utumok: >, <, = eld¨ onthet˝o, azaz van teljes rendez´es
I
III. Intervallum t´ıpus´ u attrib´ utumok: az elemek csoportot alkotnak
I
IV. Ar´any sk´al´aj´ u attrib´ utum: van z´erus elem is
Az adat le´ır´asa, jellemz˝oi K¨oz´ep´ert´ekek I
´ Atlag (s´ ulyozott ´atlag)
I
Medi´an Nehezen sz´amolhat´ o (nem lehet darabolni a feladatot, holisztikus m´ert´ek.) De ismert intervallumsz´amoss´agokn´al j´ ol becs¨ ulhet˝o! Hogyan?
I
M´odusz Lehet t¨obb is
I
Ferdes´eg (skewness): γ1 =
E [(X −m)3 ] 3
(E [(X −m)2 ]) 2
P´elda negat´ıv ferdes´eg˝u adatra
Az adat le´ır´asa, jellemz˝oi Az ´ert´ekek eloszl´asa T¨obbet tudhatunk meg az adathalmazr´ ol, ha nem csak a centralit´as´ar´ol t´aj´ekoz´odunk. I
Negyedel˝opontok (sz´amoss´ag szerint): Q1 : 25%-hoz, Q3 : 75%-hoz legk¨ ozelebb es˝ o adatpont a rendezett sorban
I
IQR = Q3 − Q1 Mit nem tudunk m´eg?
Az adat le´ır´asa, jellemz˝oi Az ´ert´ekek eloszl´asa T¨obbet tudhatunk meg az adathalmazr´ ol, ha nem csak a centralit´as´ar´ol t´aj´ekoz´odunk. I
Negyedel˝opontok (sz´amoss´ag szerint): Q1 : 25%-hoz, Q3 : 75%-hoz legk¨ ozelebb es˝ o adatpont a rendezett sorban
I
IQR = Q3 − Q1 Mit nem tudunk m´eg?
I
¨ amos jellemz´es: Minimum, Q1 , Medi´an, Q3 , Maximum Otsz´
I
Egyszer˝ u lehet˝os´eg outlierek (k¨ ul¨ onc¨ ok) azonos´ıt´as´ara: d(x, Q) > 1, 5IQR
Az adat le´ır´asa, jellemz˝oi Sz´or´as
σ2 =
1 N
PN
i=1 (xi
− x)2
I
σ 2 : sz´or´asn´egyzet, variancia (tkp. m´asodik centr´alis momentum)
I
σ: sz´or´as
I
K¨onnyen, elosztottan sz´am´ıthat´ o, u ´j adat ´erkez´esekor felhaszn´alhatjuk az eddigi ´ert´eket
Az adat le´ır´asa, jellemz˝oi Hasonl´os´agi m´ert´ekek Mennyire hasonl´ıt egym´asra k´et elem? Mekkora a t´avols´aguk? I
Legegyszer˝ ubben (ha azonos t´ıpus´ uak az attrib´ utumaink): nemegyez´esek ar´anya az ¨ osszes attrib´ utum sz´am´ahoz
I
Intervallum t´ıpus´ u attrib´ utumok eset´en sokkal jobb: 1 Minkowski-norma: Lp (z) = (|z1 |p + ... + |zm |p ) p
Az adat le´ır´asa, jellemz˝oi Hasonl´os´agi m´ert´ekek Mennyire hasonl´ıt egym´asra k´et elem? Mekkora a t´avols´aguk? I
Legegyszer˝ ubben (ha azonos t´ıpus´ uak az attrib´ utumaink): nemegyez´esek ar´anya az ¨ osszes attrib´ utum sz´am´ahoz
I
Intervallum t´ıpus´ u attrib´ utumok eset´en sokkal jobb: 1 Minkowski-norma: Lp (z) = (|z1 |p + ... + |zm |p ) p
I
p = 2? p = 1?
Az adat le´ır´asa, jellemz˝oi Hasonl´os´agi m´ert´ekek Mennyire hasonl´ıt egym´asra k´et elem? Mekkora a t´avols´aguk? I
Legegyszer˝ ubben (ha azonos t´ıpus´ uak az attrib´ utumaink): nemegyez´esek ar´anya az ¨ osszes attrib´ utum sz´am´ahoz
I
Intervallum t´ıpus´ u attrib´ utumok eset´en sokkal jobb: 1 Minkowski-norma: Lp (z) = (|z1 |p + ... + |zm |p ) p
I
p = 2? p = 1?
I
p = 2: euklideszi norma, p = 1: Manhattan-norma
Az adat le´ır´asa, jellemz˝oi Hasonl´os´agi m´ert´ekek Mennyire hasonl´ıt egym´asra k´et elem? Mekkora a t´avols´aguk? I
Legegyszer˝ ubben (ha azonos t´ıpus´ uak az attrib´ utumaink): nemegyez´esek ar´anya az ¨ osszes attrib´ utum sz´am´ahoz
I
Intervallum t´ıpus´ u attrib´ utumok eset´en sokkal jobb: 1 Minkowski-norma: Lp (z) = (|z1 |p + ... + |zm |p ) p
I
p = 2? p = 1?
I
p = 2: euklideszi norma, p = 1: Manhattan-norma
I
Vegyes attrib´ utumok: csoportos´ıt´as, majd s´ ulyozott t´avols´ag´atlag
I
Speci´alis esetek pl.: szerkeszt´esi t´avols´ag, bez´art sz¨og alap´ u hasonl´os´ag
K¨ul¨onb¨oz˝o p ´ert´ekek hat´asa a szomsz´eds´agokra
Adattiszt´ıt´as Mit kezdj¨ unk a hi´anyz´ o adattal? I
Elhagyjuk a rekordot, vagy k´ezzel t¨ omj¨ uk be a lyukakat: nem t´ ul hat´ekony
I
Dedik´alt konstans a hi´any jelz´es´ere: f´elrevezetheti az adatb´any´asz alkalmaz´ast
I
A teljes attrib´ utum, vagy az adott oszt´aly ´atlag´anak, m´odusz´anak behelyettes´ıt´ese
I
K¨ovetkeztet´es a hi´anyz´ o ´ert´ekre (regresszi´ o, d¨ont´esi fa...)
Adattiszt´ıt´as Mit kezdj¨ unk a zajos adattal? Egy ´ert´ekhalmaz eset´en zajon v´eletlenszer˝ u hib´ab´ ol fakad´o hib´as ´ert´ekeket ´ert¨ unk. I
Binning: r¨ogz´ıtett sz´amoss´ag´ u vagy sz´eless´eg˝ u ”v¨odr¨ok” ´ert´ekeit ´atlagukkal, medi´anjukkal vagy a legk¨ ozelebbi sz´els˝o´ert´ekkel helyettes´ıtj¨ uk T´ ul egyszer˝ unek l´atszik, de gyakorlatban is haszn´alhat´o, pl. MS, NMR k´ıs´erletek
I
Regresszi´o: az adat illeszt´ese egy f¨ uggv´enyhez
I
Klaszterez´es: hasonl´ os´ag alap´ u csoportos´ıt´as
I
Ezek a technik´ak m´ar t¨ obb c´elra haszn´alhat´ ok, egyben redukci´os ´es diszkretiz´aci´ os elj´ar´asok is
Toluol ioniz´aci´os t¨omegspektruma
Adatintegr´aci´o K¨ ul¨onb¨oz˝o forr´asok egyes´ıt´ese I
Azonos´ıt´asi probl´ema, redundancia → korrel´aci´oanal´ızis
I
Pearson-f´ele korrel´aci´ os egy¨ utthat´ o: rA,B = Nem jelent implik´aci´ ot Milyen ´ert´ekeket vehet fel?
PN
i=1 (ai −A)(bi −B) NσA σB
Adatintegr´aci´o K¨ ul¨onb¨oz˝o forr´asok egyes´ıt´ese I
Azonos´ıt´asi probl´ema, redundancia → korrel´aci´oanal´ızis
I
Pearson-f´ele korrel´aci´ os egy¨ utthat´ o: rA,B = Nem jelent implik´aci´ ot Milyen ´ert´ekeket vehet fel?
I
Kateg´oria t´ıpus´ u attrib´ utumokra: χ2 statisztika (Pearson) A c-f´ele, B r -f´ele ´ert´eket vehet fel. Egy c x r -es t´abl´azatot t¨olt¨ unk ki az esem´enyp´arok egy¨ uttes el˝ ofordul´as´aval. Pc Pr (oij −eij )2 2 χ = i=1 j=1 eij , ahol oij a megfigyelt, eij pedig a v´art egy¨ uttes el˝ofordul´as #(A=ai )#(B=bi ) ei j = N
PN
i=1 (ai −A)(bi −B) NσA σB
Adattranszform´aci´o Rengeteg diverz technik´aval k´esz´ıthetj¨ uk el˝ o az adatokat az adatb´any´aszathoz. I
Zajsz˝ ur´es (m´ar l´attuk)
I
Aggreg´aci´o (pl. havi adatokb´ ol ´eves kimutat´as)
I
´ anos´ıt´as (fogalmi, numerikus hierarchi´ak) Altal´
I
Normaliz´al´as
I
´ attrib´ Uj utum l´etrehoz´asa
Adattranszform´aci´o Normaliz´al´as v −min max−min (maxn
− minn ) + minn
I
Min-max: vn =
I
z-score: vn =
I
Decim´alis sk´al´az´as a c´eltartom´anyhoz igaz´ıtva
I
A min-max normaliz´al´as ´es a decim´alis sk´al´az´as nem robusztus az ´erkez˝ ou ´j ´ert´ekekre
v −A σA
Adatredukci´o Ez tulajdonk´eppen a feldolgozand´ o adat m´eret´enek cs¨okkent´ese ´erdek´eben v´egzett transzform´aci´ o. I
Aggreg´aci´o
I
Attrib´ utum-r´eszhalmaz v´alaszt´asa(inkrement´alisan, dekrement´alisan, d¨ ont´esi f´akkal)
I
M´eretcs¨okkent´es (alternat´ıv ´abr´azol´as, modellez´es)
I
Dimenzi´ocs¨okkent´es (ez is u ´j reprezent´aci´ o, de valamilyen k´odol´as, lek´epez´es, ”t¨ om¨ or´ıt´es”) Hasznos, ha nagyon nagy az attrib´ utumhalmaz sz´amoss´aga (pl. sz´op´arok gyakoris´aga az interneten: n ≈ 109 )
Adatredukci´o Dimenzi´ocs¨okkent´es: DWT (Discrete Wavelet Transform) I
Az adatrekordra vektork´ent tekint¨ unk, a DWT ezt egy azonos hossz´ us´ag´ u vektorr´a transzform´alja. De akkor mire j´o?
Adatredukci´o Dimenzi´ocs¨okkent´es: DWT (Discrete Wavelet Transform) I
Az adatrekordra vektork´ent tekint¨ unk, a DWT ezt egy azonos hossz´ us´ag´ u vektorr´a transzform´alja. De akkor mire j´o?
I
Az u ´j vektornak n´ eh´ any egy¨ utthat´ oj´ ab´ ol is j´ ol k¨ ozel´ıthet˝ o az eredeti adat.
I
A kiindul´o vektor m´erete 2 hatv´anya legyen (padding sz¨ uks´eges lehet). Egy transzform´aci´ o sor´an k´et f¨ uggv´enyt alkalmazunk szomsz´edos adatp´arokra, iterat´ıvan, minden ciklusban felezve ezzel az adathalmaz m´eret´et. Az egyik f¨ uggv´eny jellemz˝oen sim´ıtja az adatot, a m´asik pedig a k¨ ul¨onbs´egeket er˝os´ıti.
I
A fut´as sor´an el˝o´all´ o, kijel¨ olt ´ert´ekek lesznek a transzform´alt vektor egy¨ utthat´oi. A transzform´aci´ o inverz´et v´egrehajtva az adat vissza´all´ıthat´ o.
De mi az a wavelet (”hull´amocska”)?
I
A k´epen a legegyszer˝ ubb diszkr´et wavelet, a Haar-wavelet l´athat´o. (Haar Alfr´ed, 1909)
I
A waveletek egy ortonorm´alt b´azisban t¨ ort´en˝ o le´ır´ast tesznek lehetov´e. (K´et f¨ uggv´eny: wavelet f¨ uggv´eny az ortogonalit´ashoz, ´es egy sk´al´az´ o f¨ uggv´eny az ortonormalit´ashoz.
I
A Haar-wavelet rekurz´ıvan p´aronk´enti k¨ ul¨ onbs´egeket ad meg, illetve a teljes adatsor ¨ osszeg´et.
I
A DWT elonye a DFT-vel szemben, hogy nem csak a frekvenci´at ´abr´azolja, hanem a lokalit´ast is.
Vannak ¨osszetettebb waveletek is! (Ingrid Daubechies, 1988)
Vannak ¨osszetettebb waveletek is! (Ingrid Daubechies, 1988)
DWT vs. DFT az egys´egimpulzus p´eld´aj´an
DWT a gyakorlatban - JPEG2000
JPEG JFIF vs. JPEG2000
Adatredukci´o Dimenzi´ocs¨okkent´es: PCA (Principal Component Analysis f˝ okomponens-anal´ızis, szingul´aris felbont´as, Karhunen-Loeve m´odszer) El˝osz¨or: intuit´ıven I
A PCA-val egy u ´j ortogon´alis b´azist tal´alhatunk az eredeti adathalmazhoz.
I
Ezeket a vektorokat, amiket f˝ okomponenseknek nevez¨ unk, szignifikancia szerint sorba rendezhetj¨ uk, kezdve a leger˝osebb sz´or´as ir´any´aba mutat´ oval.
I
A leggyeng´ebb komponensek elhagy´as´aval is az eredeti adat j´o k¨ozel´ıt´es´et kapjuk.
I
(Bizonyos ´ertelemben a leheto legjobb k¨ ozel´ıt´est, mint azt l´atni fogjuk.)
PCA Gauss-eloszl´asra
Adatredukci´o Dimenzi´ocs¨okkent´es: PCA (Principal Component Analysis f˝ okomponens-anal´ızis, szingul´aris felbont´as, Karhunen-Loeve m´odszer) M´asodszor: alapos(abb)an - PCA SVD haszn´alat´aval I
Defin´ıci´ o Ortogon´alis m´atrix: Az U n´egyzetes m´atrix ortogon´alis, ha l´etezik U −1 inverze ´es U −1 = U T
Adatredukci´o Dimenzi´ocs¨okkent´es: PCA (Principal Component Analysis f˝ okomponens-anal´ızis, szingul´aris felbont´as, Karhunen-Loeve m´odszer) M´asodszor: alapos(abb)an - PCA SVD haszn´alat´aval I
Defin´ıci´ o Ortogon´alis m´atrix: Az U n´egyzetes m´atrix ortogon´alis, ha l´etezik U −1 inverze ´es U −1 = U T
I
Ortogon´alis m´atrix ´altal reprezent´alt line´aris transzform´aci´o nem v´altoztatja a vektorok hossz´at.
I
T´ etel Minden M ∈ Rm×n m´atrixnak l´etezik szingul´aris ´ert´ek felbont´asa (SVD): M = UΣV T , ahol U ∈ Rm×m , V ∈ Rn×n , Σ ∈ Rm×n , ´es Σ bal fels˝ o r´eszm´atrixa egy r × r diagon´alis m´atrix, a f˝o´atl´oj´aban cs¨ okken˝ o sorrendben pozit´ıv elemekkel, mindenhol m´ashol pedig 0 elemekkel.
Adatredukci´o Dimenzi´ocs¨okkent´es: PCA (Principal Component Analysis f˝ okomponens-anal´ızis, szingul´aris felbont´as, Karhunen-Loeve m´odszer) Mi´ert j´o ez nek¨ unk a dimenzi´ ocs¨ okkent´esn´el? P r T I M = UΣV T = i=1 σi ui vi
Adatredukci´o Dimenzi´ocs¨okkent´es: PCA (Principal Component Analysis f˝ okomponens-anal´ızis, szingul´aris felbont´as, Karhunen-Loeve m´odszer) Mi´ert j´o ez nek¨ unk a dimenzi´ ocs¨ okkent´esn´el? P r T I M = UΣV T = i=1 σi ui vi I
Vegy¨ uk csak a k legnagyobb s´ uly´ u diadikus szorzatot! T Mk = Uk Σk Vk , Mk rangja k
I
T´ etel qP r 2 ||M − Mk ||F = min||M − N||F = i=k+1 σi , ahol a minimumot a k rang´ u m´atrixok N halmaz´an vessz¨ uk.
I
Az M m´atrix Uk Σk -val k¨ ozel´ıtheto, ahol VkT sorai alkotj´ak a b´azist.
Adatredukci´o M´eretcs¨okkent´es I
Parametrikus m´odszerek: nem kell elt´arolni az adatot, csak n´eh´any param´etert P´elda: regresszi´o
I
Nemparametrikus m´ odszerek: klaszterez´es, mintav´etelez´es I
I
SRSWOR, SRSWR (Simple Random Sample WithOut/With Replacement): s rekordot ”h´ uzunk”, az ut´ obbin´al ugyanaz t¨ obbsz¨ or is h´ uzhat´ o Ha van klaszter- vagy oszt´alyinform´aci´ o, azt felhaszn´alhatjuk
Adatredukci´o Mintav´etelez´es hib´aja a m´eret f¨ uggv´eny´eben I
Els˝o k¨ozel´ıt´es: hiba(m) = P(| Ymx − px | ≥ ), ahol m a minta m´erete, Yx az x elem elofordul´asainak sz´ama a mint´aban, px pedig x el˝ofordul´as´anak val´ osz´ın˝ us´ege
I
Csernov-korl´ atb´ ol: m ≥
I
Pl. ha 0,01 vagy nagyobb elt´er´es es´ely´et 0,01 al´a akarjuk cs¨okkenteni, 27000 mint´at kell venn¨ unk
I
Ez a megk¨ozel´ıt´es nem szerencs´es, mert kisebb p val´osz´ınus´eg mellett kisebb hib´at ad
I
Yx Yx Jobb: hiba(m) = P( mp ≥ 1 + ) + P( mp ≤
1 22
ln σ2 , ahol σ a k´ıv´ant hibakorl´at
1 1+ )
Diszkretiz´al´as ´es hierarchi´ak Cs¨okkenti, egyszer˝ us´ıti, ugyanakkor megfoghat´ obb´a teszi az adatot. I
Lehet top-down, illetve bottom-up megk¨ ozel´ıt´es˝ u (splitting ill. merging), aszerint, hogy az oszt´ opontok kezdeti halmaz´ahoz tov´abbiakat vesz¨ unk, vagy kezdetben minden pont oszt´opont, ´es ezt cs¨okkentj¨ uk
I
Lehet fel¨ ugyelt, ha a diszkretiz´al´ashoz haszn´alunk oszt´alyinform´aci´ot
I
L´etrehozhatunk t¨ obb szint˝ u hierarchi´at is rekurz´ıv diszkretiz´al´assal
Diszkretiz´al´as ´es hierarchi´ak M´odszerek numerikus adatokon I
Binning (m´ar l´attuk)
I
Az 1R algoritmus diszkretiz´al´ o elj´ar´asa
I
Entr´opia alap´ u diszkretiz´al´as
I
ChiMerge
I
Klaszterez´es
I
Intuit´ıv feldarabol´as (k´ıv´anatos lehet a term´eszetesebb hat´arok ´erdek´eben)
Diszkretiz´al´as ´es hierarchi´ak Entr´opia alap´ u diszkretiz´al´as I
Fel¨ ugyelt, top-down
I
P Entr´opia: H(D) = − Ci ∈C pi log2 pi , ahol pi a Ci oszt´aly´ u elemek relat´ıv gyakoris´aga D-ben
I
´ v´alasztunk v´ag´ Ugy opontot, hogy minim´alis legyen
I
Ez annak az inform´aci´ onak a m´ert´eke, amennyi hozz´aad´as´aval t¨ok´eletess´e tehet˝o lenne a v´ag´as oszt´alyoz´asi k´epess´ege
I
Rekurz´ıvan, am´ıg el nem ´er¨ unk valamilyen k´ıv´ant hat´art (hi´anyz´o inform´aci´ oban, intervallumok sz´amoss´ag´aban)
|D1 | |D| H(D1 )
+
|D2 | |D| H(D2 )
Diszkretiz´al´as ´es hierarchi´ak ChiMerge I
Fel¨ ugyelt, bottom-up diszkretiz´al´as a m´ar megismert χ2 teszt haszn´alat´aval
I
A t´abl´azat oszlopai azok a szomsz´edos intervallumok, amiknek k´ıv´ancsi vagyunk az ¨ osszevonhat´ os´ag´ara, sorai pedig az oszt´alyok
I
Alacsony χ2 ´ert´ekek eset´en az intervallumok oszt´alyf¨ uggetlenek ´es ¨ osszevonhat´ ok
I
Meg´all´asi krit´eriumok: χ2 , intervallumok sz´ama
Diszkretiz´al´as ´es hierarchi´ak ¨ olszab´aly az intuit´ıv diszkretiz´al´ashoz Ok¨ I
3-4-5 szab´ aly
I
A decim´alis ´ert´ekek MSD-je alapj´an hat´arozzuk meg a k¨ovetkez˝o szint˝ u intervallumok sz´am´at 3, 6, 7 ´es 9 k¨ ul¨onb¨ ozo ´ert´ek eset´en: 3 r´eszre 2, 4 ´es 8 k¨ ul¨onb¨ozo ´ert´ek eset´en: 4 r´eszre 1, 5 ´es 10 k¨ ul¨on¨ozo ´ert´ek eset´en: 5 r´eszre osztunk
I
El˝otte megfontolhat´ o az extr´emumok kihagy´asa (pl. 5%-95%), de ut´ana sz¨ uks´eg lehet u ´j intervallumokat l´etrehozni nekik
K¨ osz¨ on¨ om a figyelmet!
