Alapfogalmak az adatelemzésben

Alapfogalmak az adatelemzésben „Big Data” elemzési módszerek Kocsis Imre, Salánki Ágnes ikocsis@, salanki@ 2015

Budapesti Műszaki és Gazdaságtudományi Egyetem Méréstechnika és Információs Rendszerek Tanszék

Adatelemzés

Modell

Adatelemzés

Adat

Többletinformáció

Modell  Szakértői tudás o Elvárt összefüggések o Háttértudás a kísérletről o…

Modell  Szakértői tudás o Elvárt összefüggések o Háttértudás a kísérletről o…

Adatelemzés

Modell

Adatelemzés

Adat

Többletinformáció

Adat  Strukturált o Rögzített formátum o Általában 𝑛 × 𝑝-s táblázat Változó/ attribútum

 Nemstrukturált o Nincs előre rögzített tárolási/értelmezési modell

Rekord/ megfigyelés

Adat  Strukturált

 Nemstrukturált

o Rögzített formátum o Általában 𝑛 × 𝑝-s táblázat o „Tidy” • Sor: pontosan egy megfigyelés • Oszlop: pontosan egy változó

Széles

Hosszú

o Nincs előre rögzített tárolási/értelmezési modell

Adat  Strukturált o Rögzített formátum o Általában 𝑛 × 𝑝-s táblázat o „Tidy”

 Nemstrukturált o Nincs előre rögzített tárolási/értelmezési modell o Csak metaadat

• Sor: pontosan** egySzemistrukturált adat? megfigyelés o Pl. e-mail, audio anyagok pontosan egy változó • •⊂Oszlop: Strukturált

• Nem ábrázolható hatékonyan adattáblában o Transzformáció • Azonos típusú objektumok más attribútumokkal is strukturáltba? • Az attribútumok sorrendje nem számít • Pl. XML, JSON

Numerikus és kategorikus változók  Numerikus (numerical) o az alapvető aritmetikai műveletek értelmesek o Pl. átlaghőmérséklet, kor

Változók

Numerikus

 Kategorikus (categorical) o Csak megkülönböztetés miatt o Pl. telefonszám, nem

Kategorikus

Numerikus változók  Folytonos o Mért – tetszőleges értéket felvehet • adott tartományon belül • adott pontosság mellett

o Pl. a teremben ülők BigData jegyének átlaga

 Diszkrét

Folytonos

Változók

Numerikus

Diszkrét

o Számolt – véges sok értéket vehet fel adott tartományban o Pl. BigData előadáson ülők száma

Kategorikus

Kategorikus változók  Rendezett o Teljes rendezés az értékeken Változók

 Nem rendezett (reguláris) Numerikus

Rendezett

Kategorikus

Nem rendezett

Adatelemzés

Modell

Adatelemzés

Adat

Többletinformáció

Többletinformáció  „A kávét vásárlók gyakran vásárolnak tejet”  „A férfiak és nők előléptetési aránya különbözik”  „Az alkalmazás memóriaigénye a kiszolgálandó kérések számával exponenciálisan növekszik”  „A teljes populáció IQ-ja 𝑁(100, 15) eloszlást követ”  „Az Apple részvények vételi árának prediktált ingadozása a következő hónapban 2”  „A BME-s hallgatók tanulmányi átlaguk alapján 3 jól elkülöníthető csoportba tartoznak”

Adatelemzés Adatelemzés

Adat

Tisztítás

Modell

Felderítő Többletinformáció Megerősítő

Adatelemzés

Felderítő analízis

Megerősítő analízis

• Cél: hipotézisek megfogalmazása

• Cél: hipotézisek tesztelése

• Ismerkedés az adatokkal/doménnel • Erősen ad-hoc • Fő eszköz: leíró statisztika + adatbányászat, sok vizualizáció

• Előre megsejtett összefüggések ellenőrzése • Fő eszköz: statisztikai tesztek + következtető módszerek

Adatelemzés  Pl. eloszláselemzés Felderítő analízis Sejtés: az 𝑥 változó normális eloszlású

Megerősítő analízis Az 𝑥 változó hihetően 𝑁(12, 4) eloszlást követ

Adatelemzés  Pl. lineáris regresszió Felderítő analízis

Megerősítő analízis

Sejtés: az 𝑥 és 𝑦 változó között valamilyen lineáris kapcsolat van

Az 𝑥 és 𝑦 változó között az 𝑌 = 3.2 × 𝑥 – 1.2 írható fel, 𝑅2 = 0.1234

Adatelemzés Adatelemzés

Adat

Tisztítás

Modell

Felderítő Többletinformáció Megerősítő

Adattisztítás  Adattisztítás! o Meglepően hosszú tud lenni o Legtöbbször nem tökéletes o Big Data?

 Inkonzisztenciák o Beviteli/mérési hibák, „hibás join”, részleges megfigyelés, hamisítás, …

 Kieső értékek (outliers) o o o o

=/= „durva hiba” (gross error) Nem feltétlenül előnytelen, de klasszikusan az Magas dimenziószámnál nehéz lehet detektálni Alacsony dimenziós vizualizáció segíthet

Adattisztítás  Hiányzó adatok (missing data, „NA”, „null”) o Hol lehet probléma? o Mesterséges feltöltés („imputation”)

 Több változó, mint megfigyelés/minta o Génkifejeződési vizsgálatok o Műholdképek spektrális vizsgálata o…

Leíró statisztika

Leíró statisztika  Vizsgált adatok alapvető jellemzői o Kvantitatív o Erősen absztrahál, „összefoglal”

 Egyfajta ellentéte: következtető (inferential) stat. o Megfigyelt mintán túlmutató következtetések o Pl. populáció tulajdonságaira következtetés mintából

(Folytonos) megfigyelések jellemzése  Átlag, medián, módusz  Percentilis o Az 𝑛-edik percentilisnél az adatok 𝑛%-a kisebb

 Kvartilis o Q1, Q3: 25. és 75. percentilis o Q2: medián

 Inter-quartile range (IQR) o Q3 – Q1

Kvartilisek szerepe

„68–95–99.7 rule”

Boxplot (Box and whisker plot)

Ez már nem fog menni Excelben. (?)

Centrális tendencia és diszperzió  Centrális jelleg jellemzői: o Átlag, medián, multimodalitás (illetve módus)

 „Diszperzió” jellemzői o Percentilisek, szórás(ok), variancia

 Melyik mennyire érzékeny a kiugró értékekre?  Megj.: a mintaátlag vs. populáció-átlag jellegű kérdésekkel itt nem foglalkozunk o (Mi minek hogyan milyen becslője…)

Robusztus mérőszámok  Alaphalmaz o 1000 pont ~ U(1, 5) egyenletes eloszlás • átlag = medián = 3 ms 1 pont: 20 s

3ms ± 2 ms Válaszidő Új medián: sort(resp. times)[501] = 3.02 ms

Vál. medián

Robusztus

Vál. átlag

Nem rob. Új átlag: (2 * 10^4 + 3 * 10^3 )/ 1001 = 25 ms!

Minta-variancia; minta kovariancia-mátrix 𝑠

2

𝑁−1

1 = 𝑁−1

1 𝑐𝑜𝑣(𝑋, 𝑌) = 𝑁−1

𝑁

𝑥𝑖 − 𝑥

2

𝑖=1

𝑁

𝑋𝑖 − 𝑥 𝑌𝑖 − 𝑦 𝑖=1

Breakdown point (becslőé): „rossz” megfigyelések max. aránya, ami után már tetszőlegesen rossz eredményt ad

Mennyire robosztusak?

Példa - felvezetés  Fisher “Iris” adatkészlete o “The use of multiple measurements in taxonomic problems” (Fisher, 1936) o Cél: osztályozás folytonos jellemzők alapján o 50 minta, morfológiai jellemzők o 3 faj: setosa, versicolor, virginica

Példa - felvezetés  A csésze (kalyx; virágképletbeli jele: K) a kétnemű virágtakarójú virágok külső takaróköre, acsészelevelek (sepala) összessége. A csésze a pártát övezi.  A párta (corolla; virágképletbeli jele: C) a kétnemű virágtakarójú virágok belső takaróköre, asziromlevelek (petala) összessége. A pártát a csésze övezi.

Variancia, kovariancia: példa

Variancia, kovariancia: példa

(Minta) variancia, kovariancia: példa

Normalizálás (szórások szorzatával): Pearson-féle lineáris korrelációs koefficiens

1.5 1.0 0.5

iris$Petal.Width

2.0

2.5

Lineáris korrelációs koefficiens

1

2

3

4

iris$Petal.Length

5

6 7 most még Egyenest

nem illesztünk

Eloszlás jellemzése? Változók

Numerikus {RPT: 609, 613, 913, …}

Kategorikus {location: Peyton, Durham, …}

Oszlopdiagram (bar chart) • Ábrázolt összefüggés: • Kategorikus változó egyes értékeinek abszolút gyakorisága

• Adategység: • Oszlop – magassága: adott érték gyakorisága

• Tervezői döntés: • Értékkészlet darabolása?

Hisztogram • Ábrázolt összefüggés: • Folytonos változó egyes értékeinek abszolút gyakorisága

• Adategység: • Oszlop – magassága: adott érték gyakorisága

• Tervezői döntés: • Oszlopszélesség/kezdőpont?

Fontos percentilisek?

Problémák a hisztogrammal?  Általánosságban nem elfogulatlan  Akkor konzisztens, ha nem csökkentjük túl gyorsan a bin-méretet  (Ronda „zárt” alak)

 Érzékeny például az „origó” választására  A „query value” a határon „ugrik”  Az ismert algoritmusok ellenére a gyakorlatban jórészt manuálisan paraméterezzük  Vagy „darabos”, vagy „nem folytonos”

Bin-szélesség hatása Histogram of iris$Petal.Length

10 8 4

6

Frequency

20

2

10

0

0

Frequency

30

12

Histogram of iris$Petal.Length

1

2

3

4

5

iris$Petal.Length

6

7

1

2

3

4

5

6

iris$Petal.Length

A többváltozós hisztogramokkal itt nem foglalkoztunk

7

Sűrűségfüggvény  Ha mégis kevésbé akarunk absztrahálni  Problémák  1. Biztos, hogy normál eloszlású a populáció?  2. Paramétereket kell becsülnünk a mintából

Nemparametrikus sűrűségbecslés  Legyen X egy r komponensű val. vektorvált.  Bármely p, amire

𝑝 𝒙 ≥ 0,

𝑝 𝒙 𝑑𝒙 = 1, ℜ𝑟

 Ún. „bona fide sűrűségbecslő” (bona fide density est.)  NPDE: p parametrikus struktúra nélkül o Pl. elég nagy családba tartozik ahhoz, hogy esélytelen legyen véges paraméterkészlettel reprezentálni. o (Vagy csak nem akarunk ezzel foglalkozni…)

Nemparametrikus sűrűségbecslés  Egy 𝑝 becslő elfogulatlan (unbiased) 𝑝-re, ha minden 𝒙 ∈ ℜ𝑟 𝐸 𝑝 𝒙 =𝑝 𝒙  Véges adatkészleten nincs bona fide becslő, ami ezt minden folytonos sűrűségre teljesítené. o Aszimptotikus becslők vannak: mintaszámmal „egyre jobb” a megfelelés

 Konzisztencia-kritériumok o MSE(x)  0 minden x-re a mintaméret növelésével: „kvadratikus átlagban pontonként konzisztens becslő” o MSE: becslési hiba várhatóértékének négyzete

Kernel-módszerek  Megpróbálunk „folytonos vonalat húzni”  Legyen Xi egy ismeretlen f eloszlásból vett n elemű minta.  Egy „kernel density estimator” függvény ezt közelíti: 𝑛 1 𝑥 − 𝑋𝑖 𝑝ℎ 𝑥 = 𝐾 𝑛ℎ ℎ 𝑖=1

 h egy „ablakszélesség-paraméter”; K egy „magfüggvény”.

Magfüggvény-példák [4]  Négyszög (rectangular):

1 𝐼[ 𝑥 ≤1] 2

 Háromszög (triangular): 1 − 𝑥 𝐼[ 𝑥 ≤1]

 Bartlett-Epanechnikov:

3 4

1 − 𝑥 2 𝐼[ 𝑥 ≤1]

 Nem korlátos bázisú Gauss (Gaussian):

2𝜋

1 − 2

𝑒

𝑥2 − 2

,𝑥 ∈ ℜ

Histogram of iris$Petal.Length

0.15

0.20 1

2

3

4

5

6

0.00

0

0.05

0.10

Density

20 10

Frequency

30

0.25

density.default(x = iris$Petal.Length, kernel = "triangul

7

iris$Petal.Length

0

2

4

6

8

0

2

4

6

N = 150 Bandwidth = 0.5832

8

0.00 0.05 0.10 0.15 0.20 0.25

Density

0.15 0.20 0.10 0.05 0.00

Density

0.25

density.default(x =Niris$Petal.Length, kernel = "rectangu density.default(x = iris$Petal.Length, kernel = "gaussian") = 150 Bandwidth = 0.5832

0

2 N = 150

4

6

Bandwidth = 0.5832

8

Big Data és leíró statisztika?  A MapReduce programozási modellt láttuk. [5]

MapReduce és leíró statisztika?  MIN/MAX/AVG… o Folytonos esetben? o Diszkrét esetben?

 Oszlopdiagram?

 Hisztogram?  Kernel sűrűség-közelítés nagy adatra? o Tényleg nagy adatra drága „lekérdezni”: O(n) tag! o SIGMOD 2013: approximáció a minták csak egy mintáján számolással

Leíró statisztikák MapReduce becslése  Közelítő hisztogram újrahasznosítása o Kvantilisek becslése o Medián becslése o … De hogyan?

 Faktor/nominális változók: wordcount!   Variancia/szórás: pl. két menetben o Empirikus átlag kell hozzá

 Kovariancia, korreláció: két menetben, egy változópárra egyszerű

Hisztogram MapReduceban – nem ZH anyag

MapReduce és hisztogram (közelítés)  Tfh. Nem feltételezhetjük az ún. range partitioning-et a vizsgált változóra o Pl. óriási CSV-t dolgozunk fel – Hadoop + HDFS o Különben nem lenne problémánk

 Partition Incremental Discretization (PiD) [4] o Módosítva [5]

 Layer1 o Párhuzamosan több hisztogram építése o Azonos (igen kicsi) szélességű bin-ekkel kezdünk feltételezett intervallumon o Egy bin átlép egy thresholdot: split o N.B. adatfolyamra is működik

 Layer2: Layer1 hisztogramok összefűzése

Layer1 karbantartás [5]

Layer1 karbantartás [4]

Layer1 karbantartás [4]

Összefűzés - hibaforrások  Csak a Layer1 töréspontjai  Split  pontatlan számlálók  + „split” az összefűzés során

Következtető statisztika

Következtető statisztika

Következtető statisztika Teljes populáció Mintavételezés Reprezentatív minta Adatfelvétel Adatsor

EDA

Hipotézis Minta kiértékelés Val.ség, konf. int. stb.

Következtetés

Ökölszabályok  LLN (Law of Large Numbers) o Ha a kísérletek száma tart a végtelenhez, az előfordulási gyakoriság az elméleti valószínűséghez konvergál

Ökölszabályok  CLT (Central Limit Theorem) o A minták statisztikáinak átlaga normális eloszlást követ (bizonyos feltételek mellett).

o 𝑥 ~ 𝑁 𝑚𝑒𝑎𝑛 = 𝜇, 𝑆𝐸 = • • • •

𝑠 𝑛

𝑥 a mintaátlag 𝜇 a populáció várható értéke 𝑠 a populáció (empirikus) szórása 𝑛 a mintaméret

?

Magyarországi kamaszlányok

Békés

𝒙𝑩é𝒌é𝒔

Heves

𝒙𝑯𝒆𝒗𝒆𝒔

Vas 𝑿𝟏 + 𝑿𝟐 + … + 𝑿𝑵 𝝁= 𝑵

𝒙𝑽𝒂𝒔

𝝁 ≈ 𝒎𝒆𝒂𝒏(𝒙)

Következtető statisztika Teljes populáció Mintavételezés Reprezentatív minta Adatfelvétel Adatsor

EDA

Hipotézis Minta kiértékelés Val.ség, konf. int. stb.

Következtetés

Minta kiértékelés  EDA ~ nyomozás  Kiértékelés ~ a per maga o H0: alapfeltevés  a vádlott ártatlan o HA: alapfeltevés ellentéte  a vádlott bűnös o Kiértékelés: ha az alapfeltevés igaz, mennyire valószínű, hogy a kapott adatot tároltuk el?

Mit tesztelünk tipikusan?  Parametrikus tesztek o Egy minta eloszlás egy paraméterét próbáljuk kitalálni o Két minta eloszlásának a paramétere megegyezik-e?

 Nemparametrikus tesztek o Illeszkedésvizsgálat  adott eloszlású-e egy minta? o Függetlenségi vizsgálat  független-e két minta? o Homogenitásvizsgálat  két minta eloszlása megegyezik-e?

Következtető statisztika Teljes populáció Mintavételezés Reprezentatív minta Adatfelvétel Adatsor

EDA

Hipotézis Minta kiértékelés Val.ség, konf. int. stb.

Következtetés

Következtetés  Döntési bemenet o Valami küszöbérték

 Adatsor típusa o Megfigyelési tanulmány (observational study) o Kísérlet (experiment)

Különbség: a köztes változók eliminálása

Esettanulmány

„Girls who ate breakfast of any type had a lower average body mass index, a common obesity gauge, than those who said they didn't. The index was even lower for girls who said they ate cereal for breakfast.„

Forrás: http://usatoday30.usatoday.com/news/health/2005-09-08-cereal-slimming_x.htm

Esettanulmány 1. „Breakfast, cereal keep girls slim”

2. „Being slim causes girls to eat breakfast„ 3. „A confounding variable is responsible for both”

?

Forrás: http://usatoday30.usatoday.com/news/health/2005-09-08-cereal-slimming_x.htm

Következtetés  Döntési bemenet o Valami küszöbérték

 Adatsor típusa o Megfigyelési tanulmány (observational study) • A köztes változók kiléte bizonytalan • Csak korreláció, kauzális következtetések nem

o Kísérlet (experiment) • A köztes változókat kiszűrtük (mintavételezés!) • Kauzális következtetések is

Adatelemzési módszerek

Adatbányászati építőkövek Klaszterezés

Osztályozás

Asszociációs szabályok

Regresszió

Klaszterezés

Asszociációs szabályok

Osztályozás

Regresszió

Források  [1] Izenman, A. J. (2008). Modern Multivariate Statistical Techniques. New York, NY: Springer New York. doi:10.1007/978-0-387-78189-1  [2] Zheng, Y., Jestes, J., Phillips, J. M., & Li, F. (2013). Quality and efficiency for kernel density estimates in large data. In Proceedings of the 2013 international conference on Management of data - SIGMOD ’13 (p. 433). New York, New York, USA: ACM Press. doi:10.1145/2463676.2465319  [3] Rajaraman, A., & Ullman, J. D. (2011). Mining of Massive Datasets. Cambridge: Cambridge University Press. doi:10.1017/CBO9781139058452  [4] Gama, J., & Pinto, C. (2006). Discretization from data streams. In Proceedings of the 2006 ACM symposium on Applied computing - SAC ’06 (p. 662). New York, New York, USA: ACM Press. doi:10.1145/1141277.1141429  [5] http://www.slideshare.net/Hadoop_Summit/creating-histograms-from-datastream-via-map-reduce