Phát triển các giải thuật song song trong khai phá luật kết hợp

In this paper we present two parallel algorithms for mining association rules that are well suited for distributed memory parallel computers. The algorithms are developed based on FP-growth method. The first algorithm is a task parallel formulation using a static load balancing technique. The second algorithm improves upon the first algorithm by dynamically balancing the load when the static task assignment leads to load imbalance.
Nội dung trích xuất từ tài liệu:
Phát triển các giải thuật song song trong khai phá luật kết hợp’Tap ch´ Tin hoc v` Diˆu khiˆn hoc, T.23, S.2 (2007), 184–200ıee.. a `.’’´ˆ´ˆPHAT TRIEN CAC GIAI THUAT SONG SONG..´´ˆˆTRONG KHAI PHA LUAT KET HO P..˜ˆNGUYEN LONG GIANGViˆn Cˆng nghˆ thˆng tin, Viˆn Khoa hoc v` Cˆng nghˆ Viˆt Nameoe oee e.... a o..Abstract. In this paper we present two parallel algorithms for mining association rules that are wellsuited for distributed memory parallel computers. The algorithms are developed based on FP-growthmethod. The first algorithm is a task parallel formulation using a static load balancing technique.The second algorithm improves upon the first algorithm by dynamically balancing the load when thestatic task assignment leads to load imbalance. We use the count matrix technique to compute theweight of tasks and to distribute tasks to processors. This technique also helps to reduce the timeneeded to scan the trees and to reduce communication cost. We also use the hash tree techniqueto group similar prefix-paths extracted from the tree, and thus can greatly reduce the amount ofinformation exchanged among processors. Our experiments show that the algorithms are capable ofachieving very good speedups, and of substantially reducing the amount of time when finding frequentpatterns in very large databases.´´ .’’ .eaaa eeT´m t˘t. B`i b´o n`y gi´.i thiˆu hai giai thuˆt song song khai th´c luˆt kˆt ho.p su. dung trˆnoaa a ao...’’c´c m´y t´ song song c´ bˆ nh´. phˆn t´n. C´c giai thuˆt du.o.c ph´t triˆn trˆn phu.o.ng ph´paa ınho ooa aaaaeea...´’ .’ ınh.’e ınh aaya a `aFP-growth. Giai thuˆt th´. nhˆt thu.c hiˆn t´ to´n song song su. dung k˜ thuˆt cˆn b˘ ng tai t˜au..... hai du.o.c ph´t triˆn du.a trˆn giai thuˆt th´. nhˆt su. dung k˜ thuˆt cˆn b˘ ng tai dˆng’`´’’’ oGiai thuˆt th´auaeeau a ’ .ya a a......’´´´’ ’e ınh ao ’ ayaa ekhi mˆt cˆn b˘ ng tai xay ra. B`i b´o su. dung k˜ thuˆt ma trˆn dˆm dˆ t´ to´n trong sˆ cua c´ca a `aa a ’ ....’´’uo ’ yya aeoe at´c vu v` phˆn phˆi c´c t´c vu t´.i nh˜.ng bˆ xu. l´ . K˜ thuˆt n`y giam thiˆu th`.i gian duyˆt cˆya . a ao a a.... o’`’ .v` giam b´.t chi ph´ truyˆn thˆng gi˜.a c´c bˆ xu. l´ . B`i b´o c˜ ng su. dung k˜ thuˆt cˆy b˘m dˆa ’oea a uya a aıeou a o ’ y..’` n tˆ du.`.ng di giˆng nhau tr´ loc t`. cˆy, v` nhu. vˆy giam thiˆu lu.o.ng thˆng tin trao´ o´’aaeonh´m c´c tiˆ ooa eoıch . u a..’´ ´ ´ a´´’’’dˆ i gi˜.a c´c bˆ xu. l´ . Kˆt qua thu. nghiˆm cho thˆ y c´c giai thuˆt dat du.o.c dˆ t˘ng tˆc rˆ t tˆt, v`o u a o ’ y eo ao a oea aa ......’ ´’ a’˜´’ım eaao eaogiam thiˆu d´ng kˆ th`.i gian t` kiˆm c´c mˆ u phˆ biˆn trong c´c CSDL l´.n.ee o´.ˆ1. GIO I THIEU.B`i to´n khai th´c luˆt kˆt ho.p (Association Rule Mining - ARM) du.o.c Agrawal, Imielinskia aa a e ... ´.i thiˆu lˆn dˆu tiˆn. B`i to´n n`y tˆp trung t` kiˆm nh˜.ng mˆi quan hˆ c´ ´´´e ` `a aoe o ıchv` [1] gi´aoeaa a aım eu...’˜ u e´ .` m ˆ n gi˜.a c´c mˆu d˜. liˆu trong mˆt CSDL. C´c luˆt kˆt ho.p d˜ v` dang du.o.c su. dungaoaa etiˆ aeu aa a.... ’ .˜´´ ´´ e’u o .e .e erˆ t hiˆu qua trong mˆt loat c´c u.ng dung t`. hˆ tro. ra quyˆt dinh, du. b´o, y tˆ, tiˆp thi v`ao.. a. a... a ´’quan tri kinh doanh. . ..Cho I l` mˆt tˆp c´c muc trong CSDL giao dich. Mˆt giao dich T ⊆ I du.o.c dinh ngh˜a o a aoıa. ...... .`´ooa e .u aool` mˆt tˆp c´c muc du.o.c sinh ra dˆ ng th`.i trong mˆt giao dich. Mˆt luˆt kˆt ho.p gi˜.a tˆpa o a a....... ..˜`’’ a’ amuc X ⊆ I v` tˆp muc Y ⊆ I , biˆ u diˆn X → Y , chı ra r˘ ng kha n˘ng hiˆn diˆn cua c´ca ae’eaee.....``’ aphˆn tu. X trong giao dich c˜ng k´o theo kha n˘ng hiˆn diˆn cua phˆn tu. Y . Dˆ do du.o.c su.a ’oueee ’a ’..... ’.’’´´ˆ´ˆ´ˆˆPHAT TRIEN CAC GIAI THUA T SONG SONG TRONG KHAI PHA LUAT KET HO P...185’dung dˆ d´nh gi´ m´.c dˆ kˆt ho.p cua luˆt l` dˆ hˆ tro. (support ) v` dˆ tin cˆy (confidence ).a a o o .a oe’ aa u o e .a... ´. ˜... cua luˆt X → Y l` ty lˆ gi˜.a sˆ giao dich ch´.a ca X v` Y v´.i tˆ ng sˆ giao dich’˜´´aa ’ e u ou ’ao ooDˆ hˆ tro ’o o ....... so. d˜. liˆu. Dˆ tin cˆy cua luˆt X → Y l` ty lˆ gi˜.a sˆ giao dich ch´.a ca X v` Y´u ’aoa ’aa ’ e u otrong co ’ u e......`´uo aoav´.i sˆ giao dich ch´.a X . Mˆt tˆp ho.p gˆ m c´c muc (item) trong CSDL goi l` mˆt tˆp muco o.. .... a o a. ...i k muc goi l` mˆt tˆp k muc (k-itemset). B`i to´n khai th´c d˜.(itemset). Mˆt tˆp muc v´o aoa aa u. .... a o a. ..´´ a ’ a a´a e .aoou a ım eliˆu su. dung luˆt kˆt ho.p du.o.c chia th`nh hai bu.´.c. Bu.´.c th´. nhˆ t t` kiˆm tˆ t ca c´c tˆpe ’ .. ´...˜ . o˜ . o’ biˆn, l` tˆp muc xuˆ t hiˆn trong CSDL v´.i dˆ hˆ tro. l´.n ho.n ...