Gyakori elemhalmazok


1 Gyakori elemhalmazok Bankó Tibor June 9, 2010 Bankó Tibor (BME) Gyakori elemhalmazok June 9, / 262 Tartalom 1 Bevezetés 2 Az al...
Author:  Ignác Halász

0 downloads 2 Views 286KB Size

Recommend Documents


OkmányApp Gyakori kérdések
1 OkmányApp Gyakori kérdések 1. Az alkalmazás használatával kapcsolatos általános kérd&...

Gyakori kérdések (EGAA-rendelet, )
1 Gyakori kérdések (EGAA-rendelet, ) március március2 Európai Globalizációs Alkalmazkodási Ala...

Gyakori kérdések és válaszok - Részvétel
1 Gyakori kérdések és válaszok - Részvétel Meddig küldhetek be képet? Egészen augusztus 3...

Cyanosissal járó gyakori veleszületett szívhibák
1 Cyanosissal járó gyakori veleszületett szívhibák Dr. Horváth Zsóka SE I.sz. Gyermekklinika Kötel...

Napközbeni átutalás: Gyakori kérdések és definíciók
1 2 Napközbeni átutalás: Gyakori kérdések és definíciók Tartalom 1. A napközbeni átu...

Wikipédia:Válaszok a gyakori kritikákra A Wikipédiából, a szabad lexikonból
1 Wikipédia:Válaszok a gyakori kritikákra A Wikipédiából, a szabad lexikonból. Néhány e...

Nemzeti Agrárgazdasági Kamara Együtt az élelmiszeriparért. Üzemi ellenőrzések tapasztalatai, gyakori hibák. Varga Tamás osztályvezető
1 Nemzeti Agrárgazdasági Kamara Együtt az élelmiszeriparért Üzemi ellenőrzések tapasztalatai, gyakori hib...

- 1 - DIREKTNET FELHASZNÁLÓI KÉZIKÖNYV. Gyakori kérdések és válaszok a. Raiffeisen DirektNet, internetbankról november
1 - 1 - DIREKTNET FELHASZNÁLÓI KÉZIKÖNYV Gyakori kérdések és válaszok a Raiffeisen DirektNet, in...

I GYAKORI MÓDSZERNEK. iî '''v *. fí *» i A - ' U i RÉSZ .{; ( 3 ' i i 3 ^ 6 ZSEB$ZÖ TÁR UNSUA KIÁSÁS
1 I GYAKORI MÓDSZERNEK iî '''v *. fí *» i A - ' U i r A t e g j t o r - N RÉSZ.{; ( 3 ' i i 3 ^ 6 8 II?! ZSEB$ZÖ...

EGY GYAKORI VÁD ÉS EGY JÓL ISMERT VÁDLOTT A KR. E. IV. SZÁZADI ATHÉNBAN: NEAIRA, A HETÉRA GRAPHÉ XENIAS-PERE (PSEUDO-DÉMOSTHENÉS OR. LIX
1 Publicationes Universitatis Miskolcinensis Sectio Juridica et Politica, Tomus XXXV (2017), pp EGY GYAKORI VÁD ÉS EGY JÓL ISMERT...



Gyakori elemhalmazok Bank´ o Tibor

June 9, 2010

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

1 / 26

Tartalom

1

Bevezet´es

2

Az algoritmusok Egy speci´alis eset Apriori Eclat FP-Growth

3

Az algoritmusok ´ert´ekel´ese

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

2 / 26

A kiindul´asi probl´ema

A gazdas´agnak a legnagyobb profitot ´altal´aban az egy¨ utt v´as´arolt term´ekek jelentik (p´eld´aul a s¨ or ´es a pelenka). ´Igy nagyon fontos ezen term´ekhalmazok megkeres´ese.

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

3 / 26

A gyakori elemhalmaz fogalma Legyen adott: term´ekek egy halmaza: A = {a1 , a2 , ...am } tranzakci´ok egy halmaza: T = {t1 , t2 , ...tm }, ahol tj ⊆ A. Ezt a T-t bemeneti sorozatnak elemeit pedig tranzakci´ oknak h´ıvjuk. A tranzakci´o felfoghat´o egy v´as´arl´as sor´an megvett term´eekeknek. Egy α ⊆ A halmaz fed´ese azon tranzakci´ ok halmaza, melyek azt tartalmazz´ak. Ekkor α t´amogatotts´aga (supp(α)) a fed´es´enek sz´amoss´aga. Azok a fontos halmazok, melyek sok tranzakci´ oban el˝ ofordulnak, hiszen ezeket gyakran v´as´arolt´ak egy¨ utt. Emiatt defini´alva van egy min supp (t´amogatotts´agi k¨ usz¨ob), ´es csak az enn´el nagyobb t´amogatotts´ag´ u halmazokkal kell foglalkozni. Ezeket h´ıvjuk gyakori elemhalmazoknak.

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

4 / 26

A gyakori elemhalmaz fogalma (folyt.)

Az A elemein defini´alva van egy rendez´es. A tranzakci´ok elemeit ennek megfelel˝oen tartjuk rendezve. Ritka elemeknek nevezz¨ uk azokat az elemeket, melyek egyetlen gyakori elemhalmaznak sem elemei. Sz˝ urt tranzakci´okhoz u ´gy juthatunk, hogy elhagyjuk a tranzakci´okb´ol a ritka elemeket. Ezek u ´gy sem sz´am´ıtanak, ´es ´ıgy kisebb tranzakci´okhoz jutunk, amelyek meggyors´ıtj´ak az algoritmusok fut´as´at. Nagyon fontos, hogy gyakori elemhalmaz minden r´eszhalmaza is gyakori, hiszen azok legal´abb annyi tranzakci´oban megtal´alhat´ oak.

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

5 / 26

Tranzakci´ok t´arol´asi m´odjai

A tranzakci´okat ´es elemeket id-val l´atjuk el. Horizont´alis adatb´azis: Minden tranzakci´ ohoz t´aroljuk az elemeinek list´aj´at. Vertik´alis adatb´azis: Minden elemhez t´aroljuk egy list´aban a tranzakci´okat, melyek ˝ ot tartalmazz´ak. Rel´aci´os adatb´azis: A t´abla minden sora egyetlen elem - tranzakci´o p´art tartalmaz.

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

6 / 26

Tartalom

1

Bevezet´es

2

Az algoritmusok Egy speci´alis eset Apriori Eclat FP-Growth

3

Az algoritmusok ´ert´ekel´ese

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

7 / 26

Tartalom

1

Bevezet´es

2

Az algoritmusok Egy speci´alis eset Apriori Eclat FP-Growth

3

Az algoritmusok ´ert´ekel´ese

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

8 / 26

Gyakori elemhalmazok egy speci´alis esetben

A k¨ ovetkez˝o sql lek´erdez´essel a k´etelem˝ u gyakori elemhalmazok kereshet˝oek meg, amennyiben azokat rel´aci´ os adatb´azisban t´aroljuk. SELECT I.elem, J.elem, COUNT(I.tranzakci´ o) FROM tranzakci´ ok I,tranzakci´ ok J WHERE I.tranzakci´ o = J.tranzakci´ o AND I.elem < J.elem GROUP BY I.elem, J.elem HAVING COUNT(I.tranzakci´ o) >= min supp

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

9 / 26

Az ´altl´anos esetet megold´o algoritmusok Egy algoritmust teljesnek nevez¨ unk, ha minden gyakori elemhalmazt megtatl´al. Helyesnek akkor nevezz¨ uk, ha csak a gyakori elemhalmazokat tal´alja meg. Ilyen ´ertelemben az el˝ oz˝ o sql lek´erdez´es se nem helyes se nem teljes. Az gyakori elemhalmazokat kinyer˝ o algoritmusok(GYEK) ´altal´aban 3 l´ep´est ism´etelgetnek. Jel¨olteket ´all´ıtanak el˝ o. Meghat´arozz´ak a jel¨oltek t´amogatotts´ag´at. Kiv´alogatj´ak a gyakoriakat. A k¨ ul¨onbs´eg a keres´esi t´er bej´ar´as´aban (a jel¨ oltek el˝ o´all´ıt´as´aban) ´es a t´amogatotts´ag meghat´aroz´as´aban van.

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

10 / 26

Tartalom

1

Bevezet´es

2

Az algoritmusok Egy speci´alis eset Apriori Eclat FP-Growth

3

Az algoritmusok ´ert´ekel´ese

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

11 / 26

Az Apriori algoritmus l =0 Jl = {0} while |Jl | = 6 0 do t´ amogatotts´ ag meghat´ aroz´ as(T , Jl ) alogat´ asa(Jl , min supp) Gyl = gyakoriak kiv´ Jl+1 =jel¨ olt elo´ all´ ıt´ as(Gyl ) l =l +1 end while return GY Egy sz´eless´egi bej´ar´ast val´ os´ıt meg a lehets´eges elemhalmazokat reprezent´al´o f´aban, hiszen minden iter´aci´ oban pr´ ob´al egyre nagyobb m´eret˝ u gyakori elemhalmazokat keresni.

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

12 / 26

Jel¨oltek el˝o´all´ıt´asa

K´et n elem˝ u halmazb´ol( Legyenek ezek: I1 , I2 . Ezeket genenr´atoroknak h´ıvjuk) egy n + 1 m´eret˝ u lesz el˝ o´all´ıtva. A k¨ ovetkez˝ o tulajdons´agok figylemebev´etel´evel: I1 a deini´alt rendez´esnek megfelel˝ oen megele˝ ozi a I2 -t I1 ´es I2 l − 1 elem˝ u prefixei megegyeznek. Az ´ıgy kapott n + 1 elem˝ u halmazr´ ol kell eld¨ onteni, hogy gyakori-e. Ennek sz¨ uks´eges felt´etele, hogy mind az n + 1 db n elem˝ u r´eszhalmaza gyakori legyen. Ezt le kell ellen˝orizni miel˝ ott gyakorinak jel¨ olj¨ uk.

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

13 / 26

A jel¨oltek t´amogatotts´ag´anak meghat´aroz´asa A jel¨oltek elemsz´ama alapj´an k¨ ul¨ onb¨ oz˝ o elj´ar´asokat kell haszn´alni: 1 elem eset´ en: minden elemhez hozz´arendel¨ unk egy int v´altoz´ot kezdetben 0 ´ert´ekkel. A tranzakci´ okat v´egigolvassuk ´es minden eleme eset´en n¨ovelj¨ uk az ahhoz tartoz´ o sz´aml´al´ ot. 2 elem eset´ en: Tfh. n gyakori elem¨ unk van elem¨ unk van. Ekkor ´erdemes felvenni egy n ∗ n m´eret˝ u kezdetben csupa 0 elemet ´ ir´any´ tartalmaz´o t¨omb¨ot, melynek csak a DNY-EK u ´atl´o felett lev˝o elemeit vessz¨ uk figyelembe. Ekkor az < l, k > (l < k) p´arhoz tartoz´o ´ert´eket a t¨omb [l][k-l] eleme tartalmazza. Az egyes tranzakci´ok v´egigolvas´asa folyam´an minden el˝ o´all´ıthat´ o p´arra meg kell n¨ovelni a t¨omb megfelel˝o elem´et.

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

14 / 26

A jel¨oltek t´amogatotts´ag´anak meghat´aroz´asa ´ 2-n´ el t¨ obb elem eset´ en: Erdemes a jel¨ olteket tartalmaz´o f´at egy sz´of´av´a alak´ıtani. A sz´ ofa ´elei a megfelel˝ o elemek. A pontjai pedig az egyedhalmazoknak felelnek meg. A gy¨ ok´er az u ¨res halmaznak. A t¨obbi elem, pedig annak a rendezett halmaznak, amely elemek azokon az ´eleken vannak, melyeken ´at az ponthoz el lehet jutni a gy¨ok´erb˝ol. Egy csom´opont egyes gyerekei balr´ ol jobbra oly sorrendben vannak, ahogy a csom´opontot b˝ ov´ıt˝ o elem lexiografikus rendez´ese adja vagy ennek ford´ıtottja vagy pedig valamilyen m´as szempont szerint van rendezve (lsd. r´eszletetesebben a k´es˝ obbiekben). Az algoritmus: A tranzakci´okon bel¨ ul az elemek is a lexiogafikus rendez´esnek megfelel˝oen vannak. Egy tranzakci´ on´al v´egig kell l´epkedni a f´aban oly m´odon, hogy minden olyan jel¨ olt t´amogatotts´ag´at n¨ovelj¨ uk, melyet a 2 tranzakci´o tartalmaz. Ha a tranzakci´ o hossza t, akkor t2 pontot kell bej´arni a f´aban. Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

15 / 26

Apriori sz´of´aval A sz´ of´at nem csak a t´amogatotts´ag meghat´aroz´as´ahoz haszn´alhatjuk fel, hanem a jel¨olt el˝o´all´ıt´asn´al is. Ugyanis a sz´ ofa olyan levelei, melyek testv´erek is megfelelnek a jel¨ olt el˝ o´all´ıt´as sor´an eml´ıtett genenr´atoroknak. Az u ´j jel¨oltet csak a bal oldalibb al´a kell felvenni. ´Igy elker¨ ulve, hogy az algoritmusban egy elem k´etszer is megjelenjen. Teh´at az algoritmus a fut´asa sor´an egyetlen sz´ of´at ´ep´ıt. A sz´ofa kezdetben az u ¨res halmazt jelent˝o jelent˝ o egyetlen cs´ ucsb´ ol ´all, melynek gyerekei a gyakori elemhalmazok. Ezek gyerekei a k´etelem˝ u gyakoriak. Ezek ut´an ´erdemes a 3 elem˝ u jel¨olteket az el˝ obb eml´ıtett m´ odon el˝o´all´ıtani. Teh´at a fa levelei a jel¨olteknek felelnek meg. Ezek t´amogatotts´ag´at meg kell hat´arozni. A ritka halmazoknak megfelel˝ o leveleket (vagyis amelyek or¨ olni... t´amogatotts´aga nem ´eri el amin supp-ot) le kell t¨

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

16 / 26

A rendez´es hat´asa a sz´ofa m´eret´ere T¨ orekedni kell a min´el kisebb f´ara, mert rengeteg (ak´ar exponenci´alisan sok) gyakori elemhalmaz is lehet. A minim´alis sz´ ofa megtal´al´asa neh´az feladat.

T´etel A minim´alis sz´ofa megkeres´ese NP-neh´ez probl´ema. A tapasztalatok szerint a gyakoris´ag szerint cs¨ okken˝ o sorrend adja a legkedvez˝obbe m´eretet. De m´egsem ezt ´erdemes haszn´alni, hanem a gyakoris´ag szerinti n¨ovekv˝ o sorrendet. Ennek az el˝ onyei: Egy csom´opontb´ol kevesebb ´el indul ki. Valamint a gy¨ok´er k¨ozel´eben vannak a ritka elemek. A fenti tulajdons´agok az´ert el˝ ony¨ osek, mert ´ıgy a tranzakci´ok nem jutnak olyan m´elyre a f´aban ´es nem ´erintenek annyi levelet.

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

17 / 26

Tov´abbi optimaliz´aci´ok

Ritka jel¨ oltek t¨ orl´ ese: A ritka jel¨ oltek t¨ orl´es´ehez nem kell m´eg egyszer bej´arni a sz´of´at, hanem az u ´j jel¨ oltek el˝ o´all´ıt´as´an´al is r´a´er¨ unk megtenni. Zs´ akutca nyes´ es: Felesleges t´arolni azokat a cs´ ucsokat, melyek egyik gyereke sem gyakori egyedhalmaz, hiszen ezek csak a mem´ori´at foglalj´ak. Persze vigy´azni kell, nehogy t´ ul kor´an t¨or¨olj¨ uk. Addig nem sznad, ameddig nem ´allt el˝ o az ¨ osszes olyan jel¨ olt, aminek r´eszhalmaza lehet.

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

18 / 26

Tranzakci´ok sz˝ur´ese Fontos, hogy a tranzakci´okb´ ol sz˝ urj¨ uk a nem relev´ans elemeket vagyis azokat, amik m´ar nem lehetnek elemei az aktu´alis m´eret˝ u jel¨olteknek. Hiszen ez lass´ıtja a t´amogatotts´ag meghat´aroz´ast. Az o¨tletek: Minden tranzakci´ob´ol t¨ or¨ olj¨ uk a ritka elemeket. Az algoritmus l. iter´aci´ oj´aban (ekkor a jel¨ oltek l m´eret˝ uek) t¨or¨olni kell azokat a t tranzakci´okat, melyek elemsz´ama nem nagyobb, mint l. Hiszen ekkor ez a tranzakci´ o m´ar nem tartalmaz olyan elemet, ami a k¨ovetkez˝o iter´aci´oban jel¨ olt lesz. T¨or¨olj¨ uk azt a tranzakci´ ot, mely nem tartalmaz jel¨oltet. Ez u ´gysem adhat m´ar nagyobb m´eret˝ u gyakori elemhalmazt, hiszen, akkor kellett volna jel¨oltet tartalmaznia.

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

19 / 26

Tranzakci´ok sz˝ur´ese (folyt.)

T¨or¨olj¨ uk a tranzakci´o azon elemeit, melyek nem elemei egyetlen olyan jel¨oltnek sem, amit a tranzakci´ o tartalmaz. Ugyanis, ezek az elemek nagyobb m´eret˝ u gyakori elemhalmazoknak sem lehetnek elemei. Ha ´ıgy a tranzakci´o sz´amoss´aga kisebb egyenl˝ o l-lel, akkor t¨or¨olj¨ uk a tranzakci´ot is. T¨or¨olj¨ uk a tranzakci´o azon elemeit, melyek nem elemei legal´abb l db olyan jel¨oltnek, amit tartalmaz a tranzakci´ o. Hiszen ekkor ezek az elemek megintcsak nem lehetnek l + 1 m´eret˝ u gyakori elemhalmazok elemei. Az elemek elt´avol´ıt´asa ut´an haszn´alhatjuk a m´asodik ¨otletet.

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

20 / 26

Tartalom

1

Bevezet´es

2

Az algoritmusok Egy speci´alis eset Apriori Eclat FP-Growth

3

Az algoritmusok ´ert´ekel´ese

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

21 / 26

Az Eclat algoritmus

Az Eclat algoritmus az u ¨res mint´ab´ ol kiindulva egy m´elys´egi keres´est hajt v´egre, ellent´etben az Apriori sz´eless´egi keres´es´evel. Mindig egyetlen jel¨oltet ´all´ıt el˝o, melynek meg is hat´arozza a t´amogatotts´ag´at. Egy l sz´amoss´ag´ u jel¨ olt el˝o´all´ıt´asa sor´an kett˝ o l − 1 sz´amoss´ag´ ut haszn´al fel, hasonl´oan az Apriorihoz. A t´amogatotts´ag meghat´aroz´asa azonban m´ashogy t¨ort´enik. Ehhez be kell vezetni az u ´n. TID-halmazokat. A TID-halmazt elemek egy halmaz´ahoz rendelj¨ uk hozz´a. A TID-halmaz megadja azokat a tranzakci´o azonos´ıt´okat, amelyekben az adott halmaz minden eleme megtal´alhat´o. ´Igy a jel¨olt t´amogatotts´aga gener´atorainak TID-halmazainak metszet´enek sz´amoss´ag´aval egyezik meg.

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

22 / 26

Tartalom

1

Bevezet´es

2

Az algoritmusok Egy speci´alis eset Apriori Eclat FP-Growth

3

Az algoritmusok ´ert´ekel´ese

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

23 / 26

FP-Growth algoritmus

A keres´esi t´er bej´ar´as´a megegyezik az Eclat algoritmus´eval. De a t´amogatotts´agok meghat´aroz´asa elt´er. Ehhez az algoritmus felhaszn´alja az elemhalmazok vet´ıt´es´et. A T tranzakci´ ohalmaz P elemhalmazra val´o vet´ıt´es´et(T | P) u ´gy kapjuk, hogy a vessz¨ uk T P-t tartalmaz´o elemeit, ´es t¨ or¨ olj¨ uk bel˝ol¨ uk P-t. Az algoritmus egy rekurzi´ os l´ep´es´eben h´arom dolgot ism´etel. A gyakori elemek megkeres´ese ut´an el˝ o´all´ıtja azokb´ol a sz˝ urt tranzakci´okat. Majd a sz˝ urt tranzakci´ okat vet´ıti az egyes gyakori elemekre ´es mindegyik ´ıgy el˝o´allt sz˝ urt tranzakci´ ora u ´j rekurz´ıv h´ıv´ast ind´ıt. A rekurz´ıv h´ıv´asn´al ´atadja az eddigi gyakori elemeket is ´ıgy b˝ov´ıti a gyakori elemhalmazokat.

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

24 / 26

Tartalom

1

Bevezet´es

2

Az algoritmusok Egy speci´alis eset Apriori Eclat FP-Growth

3

Az algoritmusok ´ert´ekel´ese

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

25 / 26

A teljes´ıtm´enyek elemz´ese

2004-ben rendeztek egy versenyt az GYEK algoritmusok ¨osszehasol´ıt´as´ara. Sebess´eg tekintet´eben az Eclat ´es FP-growth m´ odos´ıt´asai vitt´ek a p´alm´at. Mem´orihaszn´alatban az Apriori volt a nyer˝ o.

Bank´ o Tibor (BME)

Gyakori elemhalmazok

June 9, 2010

26 / 26

Life Enjoy

" Life is not a problem to be solved but a reality to be experienced! "

Get in touch

Social

© Copyright 2013 - 2019 TIXPDF.COM - All rights reserved.