Leggyakrabban használt adatbányászási technikák. Vezetői információs rendszerek

Leggyakrabban használt adatbányászási technikák

Vezetői információs rendszerek ADATBÁNYÁSZÁS II.

1. A társításelemzés társítási szabályok (asszociációs szabályok) feltárását jelenti. Azt vizsgájuk, hogy az adatbázis elemei között létezik-e összefüggés. → A gyakori elemhalmazok és a köztük lévő összefüggések keresése a feladat. Ha létezik kapcsolat, akkor ez adatbányászási eszközökkel feltárható és a kapcsolat erőssége is jellemezhető. Széles körben alkalmazzák a kereskedelemben, a bevásárlókosár típusú elemzéseknél.

Vezetői információs rendszerek


1

PL.: Egy adatbányászási elemzés során a következő társítási szabályt tárták fel: életkor( XY, 18-23 év) és lakhely (XY, Észak Dunántúl)  egyetemre jelentkezik (XY, SZE), (gyakoriság= 25%, bizonyosság=60%), ahol XY a személy azonosítója. Ez a szabály azt fejezi ki, hogy a vizsgált személyek (az adatbázisban levő rekordoknak) 25%-ára érvényes az életkorra és lakhelyre vonatkozó feltétel és 60 % a valószínűsége, hogy az életkorra és a lakhelyre megfogalmazott feltételeknek eleget tevő személyek a SZE-re jelentkeznek továbbtanulni. Vezetői információs rendszerek

Társítási szabályok meghatározása A vásárlói kosár elemzésénél kérdés: A vásárlók mely árukat vásárolják együtt? Stratégia árucikkek egymás melletti elhelyezésére: Ha A termék vásárlása esetén B terméket is vásárolják 1. A és B termék egymás mellé helyezésével növelhető a B termék eladása. 2. A és B termék egymástól távoli elhelyezésével egyéb termékek vásárlása ösztönözhető. Vezetői információs rendszerek

2

Vásárlói kosarak, tranzakciók TID transaction Identifier

Vásárolt termékek

1.

tej, kenyér, csoki, bor

2.

tej, csoki, vaj

3.

kenyér, bor

4.

kenyér, csoki, bor

5.

tej, bor

Termékek kódja tej → a kenyér → b csoki → c vaj → d bor → e

Vásárolt termékek kódosan a,b,c,e a,c,d b,e b,c,e a,e


Alapfogalmak

1.

tej, kenyér, csoki,bor

2.

tej, csoki, vaj

3.

kenyér, bor

4.

kenyér, csoki, bor

5.

tej, bor

tej → a kenyér → b csoki → c vaj → d bor → e

Legyen T a tranzakciók (az adatbázis rekordok) halmaza, E pedig az adatbázisban előforduló elemek halmaza. (Példánkban T öt elemű, az E pedig E={a,b,c,d,e}.) Az E részhalmazait elemhalmazoknak, ha k elemet tartalmaz, akkor k-elemhalmaznak nevezzük. Az elemhalmaz előfordulási gyakorisága azoknak a tranzakcióknak a száma, amelyek tartalmazzák az elemhalmazt. Vezetői információs rendszerek

3

Tekintsük az A={b,e}={kenyér,bor} 2-elemhalmazt. 1.

tej, kenyér, csoki,bor

2.

tej, csoki, vaj

3.

kenyér, bor

4.

kenyér, csoki, bor

5.

tej, bor

tej → a kenyér → b csoki → c vaj → d bor → e

A gyakorisága ?

A gyakorisága 3 (60%), mert az első, harmadik és negyedik tranzakció is tartalmazza a kenyér és bor elemeket. Gyakran százalékos formában használják a gyakoriságot, azaz az előfordulás és a tranzakciók számának hányadosaként. → A gyakoriság tehát az A elemhalmaz előfordulásának P(A) valószínűsége. Vezetői információs rendszerek

Az A elemhalmazt gyakorinak nevezzük, ha egy előre adott σ értékre fennáll, hogy

gyakoriság(A)   Az A és B halmazok közötti társítási szabály egy A B implikáció, ahol AE, BE és A∩B=. Társítási szabályok keresésekor arra vagyunk kíváncsiak, hogy a B elemhalmazt a tranzakciók hány százaléka tartalmazza úgy, hogy az A elemhalmazt is tartalmazza. Vezetői információs rendszerek

4

A keresett érték a P(BA) feltételes valószínűség, amelyet a társítási szabály bizonyosságának neveznek és a következőképpen számítható: bizonyosság ( A  B) 

gyakoriság ( A B) gyakoriság ( A)

gyakoriság ( A B )  

A társítási szabályokra előírt  küszöbértéket minimátej, kenyér, csoki,bor lis bizonyosságnak nevezik. tej, csoki, vaj Pl. a „tej  kenyér” szabály bizonyossága: kenyér, bor kenyér, csoki, bor tej, bor

P(tej kenyér ) 1 bizonyoság (tej  kenyér )    0.33(33%) P(tej ) 3 Vezetői információs rendszerek

Egy szabály akkor érvényes társítási szabály, ha egyszerre teljesíti a minimális gyakoriság és a minimális bizonyosság követelményét: és

bizonyosság ( A  B)   A társítási eljárások meghatározásának két (3) lépése: 1. a gyakori elemhalmazok megkeresése, 2. ezekből az érvényes társítási szabályok előállítása, (3.) lehet a szabályok rangsorolása érdekességi mutatók alapján (érdektelenek, redundánsak kiszűrése). Vezetői információs rendszerek

5

1. Gyakori elemhalmazok keresése Gyakori elemhalmaz keresés: az asszociációs szabálykeresés hatékonyságát legjobban befolyásoló lépés. Az adatbázis elemeiből jelölteket állítunk: Pl. az adatbázis elemei legyenek: a,b,c,d. Jelöltek lehetnek: a,b,c,d, ab,ac,ad,bc,bd,cd, abc,abd,acd,bcd, abcd. Jelöltekről el kell dönteni gyakoriak-e? Lehetőség: minden jelölt vizsgálata → nagy elemszám esetén nem járható út → n elem esetén 2n-1 jelölt van! Vezetői információs rendszerek

Kérdés: hogyan lehet minél kevesebb jelöltet megvizsgálni úgy, hogy közben minden gyakorit megtaláljunk? A kereső algoritmusok az alábbiakat használják: -Ha egy elemhalmaz nem gyakori, akkor egy elemmel bővítve ismét nem gyakori elemhalmaz adódik – anti-monoton tulajdonság. -Fordítva is igaz: egy gyakori elemhalmaz minden rész elemhalmaza is gyakori. → ez az állítás az Apriori-elv. (A-priori → előzetes, tapasztalat előtti) Vezetői információs rendszerek

6

{} {a} {a,b}

{a,c}

{b}

{c}

{a,d}

{a,b,c} {a,b,d}

{b,c}

{a,c,d}

Elemhalmazokat feltáró algoritmusok jellemzői:

{d} {b,d}

{c,d}

{b,c,d}

{a,b,c,d} Az {a},{b},{c},{d} elemek keresési tere. Apriori-elv: Ha {b,c,d} gyakori, akkor az összes részelemhalmaza is gyakori. Vezetői információs rendszerek

Keresési módszer szerint (milyen a jelöltek keresési terének bejárási módja) : -szintenként haladó (breadth-first search):szintről szintre (a legkisebb méretű elemhalmaztól kiindulva) állítják elő az elemhalmazokat és határozzák meg azok gyakoriságát. {a},{b},{c},{d}→{a,b},…,{c,d} -mélységben haladó(depth-first search): mélységben mindig egy elemet az előzőhöz adva haladnak. {a},{a,b},{a,b,c},{a,b,c,d},{a,b,d},{a,c},{a,c,d},{a,d} ,{b}, {b,c} {b,c,d},{b,d},{c,d},{d} Vezetői információs rendszerek

7

Apriori- algoritmus: Szintenként haladó módszer. (a kisebb méretű elemhalmaztól a legnagyobb méretűig haladva határozza meg a gyakori elemhalmazokat.) - először a gyakori 1-elemhalmazokat kell megkeresni (L1 halmaz), - L1-t használva következik L2 (gyakori 2-elemhalmazok összessége) meghatározása, - L2 segítségével L3 meghatározása, - és így tovább, amíg már nem található újabb gyakori k-elemhalmaz. Vezetői információs rendszerek

Minden lépésben két feladat van: a jelölt generálás és a gyakoriság ellenőrzése. A gyakoriságot nem teljesítő elemhalmazokat nem vizsgáljuk tovább. Tranzakció

Jelöltek

Gyak.

a,b,c,e

{a}

0,60

{b}

0,60

b,e

{c}

0,60

b,c,e

{d}

0,20

a,e

{e}

0,80

a,c,d





Gyakori

Gyak.

{a}

0,60

{b}

0,60

{c}

0,60

{e}

0,80

Az algoritmus 30 %-os gyakorisági küszöbbel Vezetői információs rendszerek

8

Gyakori elemhalmazokból jelölt állítás: A gyakori k-elemhalmazokból a jelölt k+1-elemhalmazok illesztéssel határozhatók meg. Két gyakori k-elemhalmaz összeilleszthető, ha lexikografikusan rendezett első k-1 elemük megegyezik és az utolsó különbözik. Pl. ha {b,c,e} és {b,c,d} gyakori elemhalmazok lennének, mivel összeilleszthetők, az összeillesztés után az új jelölt a {b,c,d,e} 4-elemhalmaz lenne. Az algoritmus véget ér, ha nem lehet új jelöltet állítani, vagy a vizsgált jelöltek közül egyik sem éri el az adott gyakorisági küszöböt. Vezetői információs rendszerek

Minden lépésben két feladat van: a jelölt generálás és a gyakoriság ellenőrzése. A gyakoriságot nem teljesítő elemhalmazokat nem vizsgáljuk tovább. Gyak.

Jelöltek

Gyak.

Gyakori

Gyak.

0,60

{a,b}

0,20

{a,c}

0,40

{b}

0,60

{a,c}

0,40

{a,e}

0,40

{c}

0,60

{e}

0,80

Gyakori

{a}

termékek kódosan a,b,c,e a,c,d





{a,e}

0,40

{b,c}

0,40

{b,c}

0,40

{b,e}

0,60

{b,e}

0,60

{c,e}

0,40

{c,e}

0,40

30 %-os gyakorisági küszöbbel

b,e b,c,e


a,e

9

Minden lépésben két feladat van: a jelölt generálás és a gyakoriság ellenőrzése. A gyakoriságot nem teljesítő elemhalmazokat nem vizsgáljuk tovább. Gyakori

Gyak.

{a,c}

0,40

{a,e}

0,40

{b,c}

0,40

{b,e}

0,60

{c,e}

0,40

termékek kódosan a,b,c,e a,c,d b,e b,c,e



Jelöltek

Gyak.

{a,c,e}

0,20

{b,c,e}

0,40



Gyakori

Gyak.

{b,c,e}

0,40

30 %-os gyakorisági küszöbbel Vége az algoritmusnak: nem állítható újabb jelölt! Vezetői információs rendszerek

2. Társítási szabályok generálása gyakori elemhalmazokból Az érvényes társítási szabályok előállítása két lépésben történik. a. Minden gyakori Z elemhalmazt fel kell bontani az összes lehetséges X,Y , két diszjunkt és nem üres halmaz párjára, ahol X  Z (a szabályfeltétele), Y = Z \ X ( a szabály következménye). Minden gyakori k-elemhalmazt 2k-2 diszjunkt, nem üres párra lehet bontani. Vezetői információs rendszerek

a,e

10

bizonyosság ( A  B) 

b. A kapott X,Y halmaz párok közül azok lesznek érvényesek, amelyek teljesítik a minimális bizonyossági követelményt.

(Már csak ezt kell vizsgálni, mert a gyakori elemhalmazokra fenn áll a gyakorisági követelmény.) Példánkban Z= {b,c,e}. Lehetséges asszociációs szabályok száma:

{b,c}{e}

bizonyosság: 2/2 →100%

{b,e}{c}

bizonyosság: 2/3 → 66%

{c,e}{b}

bizonyosság: 2/2 →100%

{b}{c,e}


{c}{b,e}


{e}{b,c}


gyakoriság ( A B) gyakoriság ( A)

termékek kódosan a,b,c,e a,c,d b,e b,c,e a,e

23-2=6. Ha 70% a bizonyossági küszöb, akkor csak az első és a harmadik szabály érvényes, azaz {kenyér, csoki}  {bor} és {csoki,bor}{kenyér}.



11

{a,b,c,d}

Ha a vizsgált elemhalmaz elég nagy → az eljárás nehézkes. 100 elemű halmaz esetén 2100-2 szabály bizonyosságát kell kiszámítani. Anti-monoton tulajdonság felhasználása Csökkenti a vizsgálandó szabályok számát. Legyen a Z gyakori elemhalmazból generált két szabály X  Z \ X és x  Z \ x , ahol x  X. Ha az X  Z \ X szabály nem teljesíti a bizonyosság követelményét, akkor a x  Z \ x szabály sem. Vezetői információs rendszerek

{a,b,c,}=>{d} {a,b,d}=>{c} {a,c,d}=>{b} {b,c,d}=>{a}

{a,b}=>{c,d} {a,c}=>{b,d}{b,c} =>{a,d}

{a}=>{b,c,d} {b}=>{a,c,d}

…

…

{c,d}=>{a,b}

{c}=>{a,b,d} {d}=>{a,b,c,}

Szabályok generálása az anti-monoton tulajdoság alapján:Ha az {a,b,c}=>{d} szabály nem érvényes, akkor a bekeretezetek sem érvényesek. Vezetői információs rendszerek

12

Érdekességi mutatók – asszociációs szabályok kiválasztása Érdekességi mutatók szükségessége: a fenti szabály állítás (gyakoriság és bizonyosság alapján történő felállítás) korlátokkal, hibákkal rendelkezhet. 1. Túl sok asszociációs szabály esetén az érvényes szabályok többsége érdektelen. -a két küszöb szám alacsony →sok érvényes,de nem érdekes szabály adódik, az érdekesek ezek között rejtve maradhatnak. -redundáns szabályok adódhatnak → tej=>csoki :gyak.=6%, biz.=59% zsíros tej=>csoki :gyak.=3%, biz.=60% felesleges! Vezetői információs rendszerek

2. Gyakoriság és bizonyossági mutatók alapján előállított szabályok félrevezetők lehetnek: bizonyosságot feltételes valószínűséggel adunk meg → következmény gyakorisága nincs figyelembe véve. Pl. 1000 ember bor, tömény alkohol fogyasztási adatai: rendszeresen iszik bort 20%, töményt 80%, mindkettőt 15%. bor => tömény szabály bizonyossága: 75% → bort fogyasztók 75 %-a rendszeres tömény fogyasztó. Vegyük észre: 80 % a töményt részesíti előnyben, tehát a bor fogyasztása csökkenti a tömény fogyasztását (80%-ról 75 %-ra). 75 % félrevezető! Vezetői információs rendszerek

13

Lift mutató – asszociációs szabály függetlenségének vizsgálata (objektív mutató) Az asszociációs szabályok következményének gyakoriságát is figyelembe veszi: Lift ( A  B) 

bizonyosság ( A  B) gyakoriság ( B)

Példánkban a bor=>tömény szabály Lift mutatója: Lift (bor  tömény ) 

bizonyosság (bor  tömény ) 0.75   0.9375 gyakoriság (tömény ) 0.8

A kapott érték mutatja a negatív korrelációt→bor fogyasztása negatívan befolyásolja a tömény fogyasztását. Vezetői információs rendszerek

Leggyakrabban használt adatbányászási technikák 2. Csoportosítás (klaszterezés) segítségével az adatoknak csoportokba (klaszterekbe) sorolása történik úgy, hogy az egyes csoportokba egymáshoz hasonló elemek kerüljenek, az egyes csoportok viszont jelentősen különbözzenek egymástól. Az egy csoporthoz tartozó elemek esetén maximalizáljuk, a különböző csoportokhoz tartozó elemek esetében viszont minimalizáljuk a hasonlóságot. A feltárt csoportok lehetnek egymást kizáróak, de akár egymással átfedők is. Vezetői információs rendszerek

14

A klaszterezés tipikus példája: a piackutatás. Vásárlási szokások alapján lehetőleg homogén vásárlói csoportokat határoznak meg→ csoportok kereskedelmi célcsoportok → jól használhatók a marketing tevékenység optimalizálása érdekében → bizonyos reklám anyagot csak a megfelelő célcsoporthoz juttatnak el. Első tudományos alkalmazás: 1854-ben londoni kolera járványnál→megbetegedéseket térképen bejelölve az előfordulások jó része a Broad Street kútjai köré estek →vizsgálattal kimutatták a víz milyen baktériumot tartalmaz, mi okozza a fertőzést. Vezetői információs rendszerek

Csoportosítási algoritmusokkal szembeni követelmények 1.Különböző adattípusok esetén is alkalmazhatók legyenek. Az algoritmusok egy része numerikus adattípusok klaszterezésére alkalmas. A megoldandó feladatok gyakran megkívánják egyéb adattípus (bináris, felsorolás típusú, ezek valamilyen keveréke) feldolgozását is. 2.Az algoritmus ugyanazokat a csoportokat hozza létre, ha más sorrendben kapja az adatrekordokat, és a zajos, hibás adatokat is kezelni tudja. Vezetői információs rendszerek

15

3. Nagy adathalmazokon is hatékonyan lehessen alkalmazni. 4. Dimenzionalitás: objektumokat jellemző nagy számú tulajdonság esetén is el tudják végezni a csoportosítást. 5. Korlátozások érvényesíthetősége:lehetőség legyen az előzetes ismeretek alapján adódott korlátozó feltételek megadására. 6. Az algoritmus minimális felhasználói közreműködést igényeljen: ne kelljen olyan paramétereket megadni, amelyeket csak becsülni lehet. 7. A végeredmény értelmezhető, áttekinthető és felhasználható formában legyen előállítva. Vezetői információs rendszerek

Adatok hasonlósága, különbözősége A csoportokat, klasztereket úgy kell létrehozni, hogy a hasonló adatelemek, objektumok kerüljenek egy csoportba → ezért szükség van az adatok hasonlóságát, vagy különbözőségét valamilyen mértékkel meghatározni. Legyen N a csoportosítandó objektumok száma, n az egyes objektumokat jellemző tulajdonság (attribútummal) száma. Ekkor N objektum esetén a teljes objektum halmaz megadható az N x n méretű adatmátrix segítségével: Vezetői információs rendszerek

16

 x11 x  21     xN 1

x12 x22  xN 2

 x1n   x2 n       xNn 

Az adatmátrix (mintamátrix) sorai az egyes objektumokat (adatmintákat) jelölik, tehát xi= [xi1,xi2,…,xin] i-edik objektumot jellemző vektor. Az adatmátrix oszlopai az objektumokra jellemző tulajdonságokat tartalmazzák. Vezetői információs rendszerek

Különbözőségi mátrix (az algoritmusok jó része ezt használja a számítások során): N objektum esetén egy NxN méretű mátrix, amelyben az objektumok egymáshoz való viszonyára jellemző relatív érték (különbözőség) van tárolva → d(i,j) ≥0 adja meg az i és j objektumok közötti különbözőséget. Ha i és j objektum nagyon hasonló, akkor d(i,j) közel van 0-hoz, és annál nagyobb lesz d(i,j) értéke minél jobban különböznek egymástól i és j . Mivel d(i,j)=d(j,i) és d(i,i)=0, ezért a különbözőségi mátrix a következő felépítésű lesz: Vezetői információs rendszerek

17

 0   d (2,1)  0    d (3,1) d (3,2) 0          d ( N ,1) d ( N ,2)  d ( N , N  1), 0

Hasonlósági mátrix - ha a hasonlósági értékekre van szükség→ azt is egy hasonló felépítésű mátrixban lehet megadni, de ott 1 áll a főátlóban, és minél kisebb d(i,j)értéke, annál jobban különböznek egymástól i és j objektumok. Vezetői információs rendszerek

Hasonlóság(közelség)/különbözőség számítása Különböző típusú attribútum értékek esetén más és más elvek alapján történik. Folytonos értékek esetén a közelséget leggyakrabban valamilyen távolsággal szokás megadni. (A távolság egy különbözőségi mérték.) Objektumokat n-dimenziós adatvektornak tekintve, az n-dimenziós térben legelterjedtebb távolság mértéket, az Euklideszi távolságot alkalmazzák. Standardizálás: Ha az egyes tulajdonságok értéke nem azonos skálán mozog a többivel, akkor ezek domináns szerepet játszhatnak → célszerű azonos intervallum-skálára leképezni őket még a távolság számítása előtt. Vezetői információs rendszerek

18

Particionáló algoritmusok fő kérdései: 1. A k csoport szám meghatározása: általában a felhasználó feladata. Ha nem áll rendelkezésre megbízható érték, akkor szokás k különböző értékeire elvégezni a csoportosítást és a leginkább hasznosíthatónak látszó eredményt elfogadni. 2. Milyen kezdeti particióból induljon ki az algoritmus? Kezdeti csoport választás történhet véletlenszerűen, korábbi ismeret alapján, korábbi klaszterezés alapján. (szokás több kiindulási particióra futtatni az algoritmust, ésa legjobb eredményt választani) Vezetői információs rendszerek

Particionáló algoritmusok fő kérdései: 3. Az objektumok csoportba sorolása milyen mutató alapján történjen: Mutató választásának elve:egymástól jól elkülönülő csoportok keletkezzenek és a csoporton belül a hasonlóság nagy mértékű legyen → csoportok közötti szeparáció és a csoportok homogenitásának vizsgálata. Leggyakrabban használt minőségi kritérium az ún. négyzetes hiba → egy objektumnak a csoport középpontjától való távolságának a négyzete.


19

A k-átlag módszer 1. A k darab elem véletlenszerű kiválasztása, ezek lesznek kezdetben a k darab csoport középpontjai (átlagai). 2. A fennmaradó elemek mindegyikének hozzárendelése ahhoz a csoporthoz, amelyiknek a középpontjához a legközelebb van. (A négyzetes hiba a legkisebb.) 3. Meg kell határozni a kialakult klaszterek új középpontját (átlagát). 4. A 2. és 3. lépés ismétlése mindaddig, amíg a 2. lépésben már egyetlen elem sem kerül új csoportba. Vezetői információs rendszerek

Más megállási kritérium is létezik:Gyakran akkor fejeződik be az iteráció, ha a csoportosítás teljes négyzetes hibája (az egyes elemek négyzetes hibáinak összege) egy előírt értéknél kisebb változást mutat két egymás utáni lépésben. Az algoritmus hátránya: -érzékeny a kiindulási adatokra, -akkor ad jó eredményt, ha tömör, jól elkülönülő csoportokat kell meghatározni. -csak vektortérben jellemezhető adatok esetén használható. k-medoid algoritmus: már képes tetszőleges tulajdonságokkal rendelkező adatokat használni Vezetői információs rendszerek

20

Példa: Legyenek a,b,c,d,e,f és g csoportosítandó objektumok, melyeket V1 ésV2 folytonos értékű változóval jellemezhetünk. Obj.

V1

V2

a

1

1

b

1.4

1.8

c

2.1

2

d

4.3

5

e

3.8

4.1

f

3.3

4.5

g

5

6

Lépések: • k=2 legyen. 1. Két objektum választása csoport központnak. Ne véletlenül → egy mástól legtávolabbi pontokat → ezek a és g. 2. A fent maradó objektumok a és g objektumtól való távolságának számítása. Vezetői információs rendszerek

Objektumok távolsága a kezdő centrumoktól:

Obj. Táv. a- Táv. tól g-tól b

0.89

5.53

c

1.49

4.94

d

5.19

1.22

e

4.18

2.25

f

4.19

2.27

Lépések: 4. Minden elemet a hozzá legközelebbi centroidhoz rendelünk → C1={A={a,b,c},B={d,e,f,g}} 5. Az A és B csoportok új középpontjának számolása: cA1=((1+1.4+2.1)/3 ; (1+1.8+2)/3)=(1.5 ;1.6) cB1=((4.3+3.8+3.3+5)/4;(5+4.1+4.5+6)/4)=(4.1;4.9)

6. Esetleges átsoroláshoz újra számolni az objektumok cA1-től és cB1-től való távolságát. Vezetői információs rendszerek

21

Objektumok távolsága a C1 csoportosítás középpontjaitól. Obj.

Táv. Táv. cA1-től cB1-től

a

0.78

4.98

b

0.22

4.11

c

0.72

3.52

d

4.4

0.22

e

3.4

0.85

f

3.41

0.89

g

5.62

1.42

Nem kellett egyik objekumot sem másik csoportba áttenni → vége az algoritmusnak ! Csoportosítás teljes négyzetes hibája (az egyes adatpontok négyzetes hibáinak összege): E(C)= 14.69; E(C1)=4.78.


Jobb eredmény keresése: - algoritmus lefuttatása véletlenszerűen választott kiinduló csoportokkal, -minden futtatásnál kiszámítjuk a csoportosítás teljes négyzetes hibáját, -a legkisebb négyzetes hibaösszeget szolgáltató eredményt fogadjuk el optimálisnak.


22

Hierarchikus módszerek Típusai: az egyesítő és a felosztó módszerek. Az egyesítő módszerek általános elve az, hogy kezdetben minden objektumot külön csoportban helyeznek el, majd lépésenként egyesítik az egymáshoz legközelebbi csoportokat (minden lépésben csak egy egyesítés történik). Addig folytatódik az egyesítés, amíg minden objektum egy csoportba kerül. A felosztó módszer ennek a fordítottja, ott kezdetben minden objektum egy csoportban van, amelyet lépésenként újabb csoportokra bontunk mindaddig, amíg minden elem külön csoportba nem kerül. Vezetői információs rendszerek

Algoritmus megállítása: Általában a felhasználót nem a teljes hierarchia érdekli, hanem annak csak egy szelete → az algoritmus futása tetszőleges szinten megállítható. Klaszterek száma alapján történő megállítás: erős felhasználói behatás érvényesül, nem feltétlenül optimális az eredmény. Távolsági érték alapján történő megállítás:akkor ér véget az algoritmus, amikor a távolság az egyes csoportok között adott d értéknél nem kisebb. Ezek az algoritmusok általában hasonlósági mátrixok alapján dolgoznak. Előnyük, hogy tetszőleges attribútumok esetén használhatók. Vezetői információs rendszerek

23

Leggyakrabban használt adatbányászási technikák

5 4

Hierarchikus csoportosítás dendogramja.

3 2 1 a

b

c

d

e


3. Az osztályozás jellemzője, hogy egy adott (kiválasztott) ismérv (osztálycimke) alapján akarjuk az adatbázis elemeit (rekordjait) megkülönböztetni, osztályokba sorolni. Osztálycímke csak olyan ismérv lehet, ami véges számú különböző értéket vehet fel → ez azt jelenti, hogy ismert hány osztály létezik. Osztályozás jelenségek leírására és előrejelzésre is használható. Vezetői információs rendszerek

24

Cél minden esetben olyan szabály felállítása, amelynek segítségével a legpontosabban lehet szeparálni az adatokat a megfelelő osztályba. Az osztályozást gyakran alkalmazzák pl. pénzintézeti vizsgálatoknál (ügyfelek hitelképességének megadása, biztosítási kockázatbecslés), orvosi alkalmazásoknál. Például egy pénzintézet ügyfeleit hitelképessége szerint szeretné osztályozni jó, közepes és gyenge minősítésű osztályokba. Az osztályba sorolás alapján jellemezni lehet az egyes csoportokba tartozó ügyfeleket, és ezek alapján a pénzintézet egy új ügyfél hitelkérelméből azt is el tudja dönteni (előrejelzés), hogy hitel visszafizetés szempontjából jó ügyfél lesz-e. Vezetői információs rendszerek

Az osztályozás lépései Az osztályozási módszerek alapvetően a következő két lépésből állnak: •Első lépés: az osztályozási szabály generálása (modellkészítés) és a modell pontosságának ellenőrzése. •Második lépés: a modell felhasználása új adatminta ismeretlen osztálycímkéjének meghatározására. Vezetői információs rendszerek

25

1. Első lépés részei: - Osztálycímke meghatározása: kiválasztunk egy attribútumot, amelynek értékei szerint osztályozni akarjuk adatainkat. Alapvető feltételezés: a többi attribútum függ az osztálycímke attribútumtól- ha nem így lenne, akkor az új minta ismeretlen osztálycímkéjét nem tudnánk előrejelezni. - A modell elkészítéséhez tanuló minta felhasználása: a rendelkezésre álló adatok olyan részhalmazát vesszük, ahol minden rekord esetén ismert az osztálycímke értéke. Vezetői információs rendszerek

1. Első lépés részei: - Osztályozási algoritmus választás, amely segítségével a tanuló minták függvényében osztályozási modellt készítése következik. - A kapott modell alapján osztályozási szabályok adódnak. Osztályozási szabály: ha –akkor típusú szabályok. Osztályozási címke értékét határozzuk meg a többi attribútum függvényében. Pl. ha valaki 40 éven felüli és magas a jövedelme, akkor valószínű nem lesz adócsaló.


26

1. Első lépés részei: - A modell ellenőrzése: teszt minták – ismert osztálycímke értékkel rendelkező rekordok - segítségével ellenőrizzük a modell pontosságát. ( Az osztályozási modell az egyes mintákat jó osztályba sorolja-e, ill. milyen arányban tudja jó osztályba sorolni.) -Behangolt modell elkészítése: iterációs folyamat, amikor cél lépésről – lépésre növeljük a modell pontosságát. Ismert módszerek vannak a tanuló és teszt minták kiválasztására. Vezetői információs rendszerek

Osztálycímke, tanuló minták választása

Algoritmus-választás

nem Osztályozási szabály meghatározása

Az első lépés folyamata

Ellenőrző minta Pontosság megfelelő? igen Helyes szabály(ok), behangolt modell


27

2. Második lépés részei: A második lépés a kapott modell, osztályozási szabály előrejelzésre való használata. Ez új adatminták esetén a minta ismeretlen osztálycímkéjének meghatározását jelenti a többi, ismert attribútum értékének függvényében. Osztályozás segítségével csak diszkrét érték előrejelzése lehetséges (az osztálycímke diszkrét értéke miatt), ezért folytonos érték előrebecslésére más módszert, valamilyen regressziós módszert kell használni.


Osztályozás döntési fa segítségével A döntési fa egy fa formájú folyamatábra, az osztályozási feladatok esetében a leggyakrabban alkalmazott eszköz. Felépítése: fa gyökerétől csomópontokon keresztül jutunk el a fa leveléig. Minden csomóponthoz egy attribútumra vonatkozó kérdés tartozik. A kérdésekre adott válaszok segítségével a fa valamelyik leveléhez jutunk, amelyek az egyes osztályok címkéit tartalmazzák. Vezetői információs rendszerek

28

A döntési fa egy szabálybázis (döntési fából kinyerhető szabályok összessége). Használata: A fa mindegyik szabályát a fa gyökeréből indulva, egy levél felé haladó útvonal alapján lehet előállítani. A „ha-akkor” típusú szabály feltételi részét az útvonalba eső csomópontokhoz tartozó feltételek ÉS művelettel való összekapcsolásával kapjuk. A szabály kimenetelét az útvonal végén levő levél adja meg. Vezetői információs rendszerek

életkor?

≥45

≥20 és <30 ≥30 és <45

tanuló? igen IGEN

nem NEM

IGEN

városban lakik? igen

nem

IGEN

NEM

A fenti döntési fa egy kereskedelmi cég eladásai alapján azt tudja megbecsülni, hogy egy vásárló vesz, vagy nem vesz számítógépet → a döntési fáról öt szabály olvasható le (öt levél található rajta). Vezetői információs rendszerek

29

életkor? ≥20 és <30 ≥30 és <45

tanuló? igen

nem

IGEN

NEM

IGEN

≥45 városban lakik? igen IGEN

nem NEM

Leolvasható szabályok pl. •Aki 30 év alatti és még tanul, az vesz számítógépet (szüksége van rá). •aki idősebb 45 évesnél és nem városban lakik, nem vesz számítógépet (nem fogékony az új dolgokra). Előny:könnyű az osztályozási szabályok kiolvasása és alkalmazása. Vezetői információs rendszerek

Döntési fák elkészítése: • A fa konstruálása: -Kezdetben minden minta a fa gyökeréhez tartozik. -Minden lépésben egy kiválasztott attribútum alapján elágazásokat (csomópontokat) készítünk→ annyit, ahány diszkrét értéke van az attribútumnak. Olyan kérdéseket teszünk fel a csomópontokban, hogy a csomóponthoz tartozó adatokat úgy ossza fel, hogy a következő szinten az adatok homogenitása növekedjen. -A mintákat ezek szerint szétosztjuk diszjunkt részhalmazokra. Vezetői információs rendszerek

30

A rekurziv felosztás befejeződik, ha -az egy csomóponthoz tartozó összes minta azonos osztályból való, -már nincs olyan attribútum ami alapján további bontás készíthető, -az összes adatpontot osztályba soroltuk, -a döntési fa mélysége elért egy előre megadott értéket . 2. Döntési fák tisztítása: döntési fák tükrözhetik a tanuló minták hibáit, „zajait”.Nem megbízható ágak eltávolítása: előmetszés hamarabb leállítják a fa felépítését, utómetszésnél pedig a kész döntési fáról távolítják el a nem kívánatos részeket.

Az is az algoritmus végét jelentheti, ha már az öszszes mintát figyelembe vettük. Ezekben az esetekben a csomópontból levélcsúcs lesz. A felosztás alapjául szolgáló attribútumnak kiválasztása: egyik lehetőség az információnyereség vizsgálata. Az ezt használó algoritmusok a döntési fa egyes csomópontjaiban minden lehetséges attribútumra meghatározzák az információnyereség értékét, és a maximális információnyereséggel rendelkezőt választják az adott csomóponthoz tartozónak



31

További lehetőségek: Különféle Bayes–osztályozók, amelyek a valószínűségszámításból ismert Bayes-tételen alapulnak. A naiv Bayes-osztályozó segítségével megbecsülhető, hogy egy adott minta milyen valószínűséggel tartozik valamelyik osztályba. (A naiv jelző arra a naiv feltételezésre utal, hogy az attribútumok függetlenek egymástól.) Jól használható a minták és az attribútumok nagy számú eseténél, de még hiányos adatoknál is.


k-legközelebbi szomszéd technika k-NN algoritmus (k-nearest neighbours) Egyszerű módszer, nem készít előre modellt a minták osztályozásához, eset alapú következtetést használ. A k-legközelebbi szomszéd technika feltételezi, hogy az adatok numerikusak, így minden tanuló mintát egy n dimenziós tér egy pontjának lehet tekinteni. Az alapötlet az, hogy meg kell keresni a k darab legközelebbi szomszédot, és az ismeretlen minta abba az osztályba fog tartozni, amely a k szomszéd között a leggyakoribb. Vezetői információs rendszerek

32

Legközelebbi k szomszéd megkeresése: N dimenziós térpontjai közötti távolság meghatározása → Euklideszi- távolsággal Ha n>1, azaz több ismérv is van, akkor az értékeket normalizálni kell. Így elérhető, hogy az egyes attribútumok azonos súllyal számítsanak a távolságok kiszámításakor.

Kor (év)

Jövedelem Vásárol (eFt)

22

125

nem

27

92

nem

36

130

nem

43

87

igen

46

132

igen

52

115

nem

Egy kereskedelmi egység adatai egy adott termék vásárlására vonatkozóan. Vezetői információs rendszerek

Új ügyfél adatai: Kor : 45 év Jövedelem : 122 000Ft. Előrejelzést szeretnénk adni, hogy az ügyfél megvásárolja-e a kérdéses terméket. k-NN technika segítségével végezzük az előrejelzést.


33

Kor

Jövedelem

norm.

(eFt)

Jöv. norm.

Vásárol

22

0

125

0.84

nem

f(x)kor=(x-22)/(52-22)

27

0.17

92

0.11

nem

f(x)jövedelem=(x-87)/(132-87)

Kor (év) Jövedelem Vásárol Kor (év) (eFt) 22

125

nem

27

92

nem

36

0.47

130

0.96

nem

36

130

nem

43

0.7

87

0

igen

43

87

igen

46

0.8

132

1

igen

46

132

igen

52

1

115

0.62

nem

52

115

nem

f(x)kor=(x-22)/(52-22) → f(27)kor= (27-22)/(52-22) = 0.17 Adatokat normalizálni kell →

f(x)jövedelem=(x-87)/(132-87) → f(92)jövedelem= (92-87)/(132-87) = 0.11

[0,1] intervallumba hozni

Új ügyfél adatai normalizálva: 45 év → 0.77, 122 000 jövedelem → 0.78.



34

Kor (év)

Kor norm.

Jövedele m (eFt)

Jöv. norm.

Kor (év)

Kor norm.

Jövedele m (eFt)

Jöv. norm.

22

0

125

0.84

0.77

nem

22

0

125

0.84

0.77

nem

27

0.17

92

0.11

0.897

nem

27

0.17

92

0.11

0.897

nem

36

0.47

130

0.96

0.348

nem

36

0.47

130

0.96

0.348

nem

43

0.7

87

0

0.781

igen

43

0.7

87

0

0.781

igen

46

0.8

132

1

0.224

igen

46

0.8

132

1

0.224

igen

52

1

115

0.62

0.280

nem

52

1

115

0.62

0.280

nem

Távolság Vásárol

Távolság Vásárol

Új ügyfél adatai (norm): 45 év → 0.77, 122 000 jövedelem → 0.78.

Új ügyfél adatai (norm): 45 év → 0.77, 122 000 jövedelem → 0.78.

K=1 esetén dmin=d5 → új minta osztálycímkéje az 5. minta osztálycímkéje lesz → új ügyfél is meg fogja venni a terméket.

K=3 esetén d3,d5,d6 a legkisebbek → 2 nem vásárol és egy vásárol → új minta osztálycímkéje a nem lesz → új ügyfél nem fogja megvenni a terméket.



35

Adatbányászási szoftverek Termék

Magyarországi forgalmazó

URL

Clementine

SPSS Hungary

www.spss.hu

Enterprise Miner

SAS Institute

www.sas.com/hung ary

Intelligent Miner

IBM Magyarország

www.ibm.hu

Darwin

Oracle

www.oracla.hu

Datascope

Cygron

www.cygron.hu

MineSet

Silicon Computers Kft.

www.silicon.hu

Scenario

Axis

www.axis.hu


Leggyakrabban használt adatbányászási technikák 4. A fejlődésanalízis az időben változó adatok időben változó viselkedési szabályosságait modellezi. A regresszió-vizsgálat célja egy előrejelzésre alkalmas függvény megadása, amelynek segítségével ismert értékekből más numerikus érték(ek)re lehet következtetni. Pl. jó példa erre, amikor értékpapír befektetési döntésekhez az értékpapírárak alakulásának előrejelzéséhez az értékpapírt kibocsátó társaságok gazdasági fejlődésének jövőbeli szabályszerűségeit tárják fel adatbányászási módszerekkel. Vezetői információs rendszerek

36

Az idősorok elemzése akkor kerül be az adatbányászási feladatok közé, amikor a hagyományos statisztikai idősor elemzési eszközök már nem alkalmazhatók a feladat bonyolultsága (túl sok változó) miatt.


Döntéselőkészítő rendszerek

37


38

Leggyakrabban használt adatbányászási technikák. Vezetői információs rendszerek

Recommend Documents