Luận văn: Luật kết hợp theo tiếp cận lý thuyết tập thô và khai phá dữ liệu song song



Luận văn tốt nghiệp Luật kết hợp theo tiếp cận lý thuyết tập thô và khai phá dữ liệu song song

-1-

môc lôc

PhÇn më ®Çu

Néi dung Trang

Ch−¬ng 1. tæng quan vÒ khai ph¸ d÷ liÖu vµ

3

8

khai ph¸ d÷ liÖu song song 1.1. Khai ph¸ d÷ liÖu vµ ph¸t hiÖn tri thøc trong C¬ së d÷ liÖu

8

1.1.1. S¬ bé vÒ khai ph¸ d÷ liÖu vµ ph¸t hiÖn tri thøc trong c¬ së d÷ liÖu 8

1.1.2. Néi dung cña khai ph¸ d÷ liÖu 11

1.1.3. C¸c ph−¬ng ph¸p khai ph¸ d÷ liÖu phæ biÕn vµ lùa chän ph−¬ng ph¸p 13

1.1.4. ¦u thÕ cña khai ph¸ d÷ liÖu 15

1.1.5. Mét sè th¸ch thøc trong øng dông vµ nghiªn cøu kü thuËt khai ph¸ d÷ 17 liÖu

1.2. Khai ph¸ d÷ liÖu song song 20

1.2.1. C¸c hÖ thèng tÝnh to¸n song song 21

1.2.2. C¸c chiÕn l−îc khai ph¸ d÷ liÖu song song 26

1.2.3. C¸c m« h×nh chi phÝ 28

Ch−¬ng 2. LuËt kÕt hîp theo c¸ch tiÕp cËn cña

KÕt luËn ch−¬ng 1 31

lý thuyÕt tËp th«

32

2.1. Kh¸i niÖm luËt kÕt hîp vµ mét sè c«ng nghÖ ph¸t hiÖn 32

2.1.1. LuËt kÕt hîp 32

2.1.2. Mét sè c«ng nghÖ ph¸t hiÖn luËt kÕt hîp tuÇn tù 35

-2-

2.2. LuËt kÕt hîp theo c¸ch tiÕp cËn cña lý thuyÕt tËp th« 40

2.2.1. TËp th« 40

2.1.2. LuËt kÕt hîp theo c¸ch tiÕp cËn lý thuyÕt tËp th« 42

Ch−¬ng 3. Ph¸t hiÖn song song luËt kÕt hîp

KÕt luËn ch−¬ng 2 51

52

3.1. Kh«ng gian thiÕt kÕ song song 52

3.1.1. NÒn phÇn cøng 52

3.1.2. M« h×nh song song hãa 53

3.1.3. C¸ch thøc c©n b»ng t¶i 54

3.2. Mét sè m« h×nh ph¸t hiÖn song song luËt kÕt hîp 55

3.2.1. C¸c hÖ ph©n t¸n bé nhí 55

3.2.2. C¸c hÖ chia sÎ bé nhí 65

3.2.3. C¸c hÖ ph©n cÊp 67

3.3. M« h×nh tËp th« ph¸t hiÖn song song luËt kÕt hîp 70

3.3.1. ThuËt to¸n cho m« h×nh tËp trung 72

3.3.2. ThuËt to¸n cho m« h×nh ph©n t¸n 73

PhÇn kÕt luËn

KÕt luËn ch−¬ng 3 74

Tµi liÖu tham kh¶o

75

77

-3-

phÇn Më ®Çu

Sù ph¸t triÓn m¹nh mÏ cña c«ng nghÖ phÇn cøng ®· t¹o nªn c¸c m¸y tÝnh cã

bé xö lý tèc ®é cao, bé nhí dung l−îng lín vµ cïng víi ®iÒu ®ã, lµ sù ph¸t triÓn

kh«ng ngõng c¸c hÖ thèng m¹ng viÔn th«ng. Tõ c¸c kÕt qu¶ ®ã, nhiÒu hÖ thèng

th«ng tin phôc vô viÖc tù ®éng hãa mäi ho¹t ®éng kinh doanh còng nh− qu¶n lý ®·

®−îc triÓn khai víi tèc ®é t¨ng tr−ëng v−ît bËc. §iÒu nµy ®· t¹o ra nh÷ng dßng d÷

liÖu khæng lå trë thµnh hiÖn t−îng "bïng næ th«ng tin" nh− nhiÒu ng−êi quan niÖm.

NhiÒu hÖ qu¶n trÞ c¬ së d÷ liÖu m¹nh víi c¸c c«ng cô phong phó vµ thuËn tiÖn ®·

gióp con ng−êi khai th¸c cã hiÖu qu¶ c¸c nguån tµi nguyªn d÷ liÖu lín nãi trªn.

Cïng víi viÖc khèi l−îng d÷ liÖu ®−îc qu¶n lý t¨ng kh«ng ngõng, c¸c hÖ thèng

th«ng tin còng ®−îc chuyªn m«n hãa theo c¸c lÜnh vùc øng dông nh− s¶n xuÊt, tµi

chÝnh, kinh doanh, y häc,... Nh− vËy, bªn c¹nh chøc n¨ng khai th¸c d÷ liÖu cã tÝnh

chÊt t¸c nghiÖp, sù thµnh c«ng trong kinh doanh kh«ng chØ lµ n¨ng suÊt cña c¸c hÖ

th«ng tin mµ cßn lµ tÝnh linh ho¹t vµ s½n sµng ®¸p l¹i nh÷ng nhu cÇu trong thùc tÕ,

hay nãi kh¸c ®i, ng−êi ta cßn mong muèn c¸c c¬ së d÷ liÖu cÇn ®em l¹i tri thøc tõ

d÷ liÖu h¬n lµ chÝnh b¶n th©n d÷ liÖu. §Ó lÊy ®−îc c¸c th«ng tin mang tÝnh tri thøc

trong khèi d÷ liÖu khæng lå nh− ®· nãi, cÇn thiÕt ph¶i ph¸t triÓn c¸c kü thuËt cã kh¶

n¨ng hîp nhÊt c¸c d÷ liÖu tõ c¸c hÖ thèng giao dÞch kh¸c nhau, chuyÓn ®æi chóng

thµnh mét tËp hîp c¸c c¬ së d÷ liÖu æn ®Þnh, cã chÊt l−îng ®Ó sö dông theo mét sè

môc ®Ých nµo ®ã. C¸c kü thuËt nh− vËy ®−îc gäi chung lµ c¸c kü thuËt t¹o kho d÷

liÖu vµ m«i tr−êng c¸c d÷ liÖu nhËn ®−îc sau khi ¸p dông c¸c kü thuËt nãi trªn ®−îc

gäi lµ c¸c kho d÷ liÖu.

C¸c kho d÷ liÖu cã thÓ gióp khai th¸c th«ng tin b»ng c¸c c«ng cô truy vÊn vµ

b¸o c¸o, còng nh− ®−îc sö dông ®Ó hç trî viÖc ph©n tÝch trùc tuyÕn, kiÓm ®Þnh c¸c

gi¶ thuyÕt. Tuy nhiªn, nÕu chØ cã c¸c kho d÷ liÖu th× ch−a thÓ cã ®−îc tri thøc.

-4-

Chóng kh«ng cã kh¶ n¨ng ®−a ra c¸c gi¶ thuyÕt. NÕu d÷ liÖu ®−îc ph©n tÝch mét

c¸ch th«ng minh th× chóng sÏ lµ nguån tµi nguyªn v« cïng quý gi¸. Tõ c¸c d÷ liÖu

s½n cã, nhu cÇu t×m ra nh÷ng th«ng tin tiÒm Èn cã gi¸ trÞ (nh÷ng tµi nguyªn quý gi¸)

ch−a ®−îc ph¸t hiÖn, nh÷ng xu h−íng ph¸t triÓn vµ nh÷ng yÕu tè t¸c ®éng lªn chóng

lµ mét ®iÒu hÕt søc cÇn thiÕt. TiÕn hµnh c«ng viÖc nh− vËy chÝnh lµ thùc hiÖn qu¸

tr×nh ph¸t hiÖn tri thøc trong c¬ së d÷ liÖu (Knowledge Discovery in Databases -

KDD) mµ trong ®ã kü thuËt khai ph¸ d÷ liÖu (data mining) cho phÐp ph¸t hiÖn ®−îc

c¸c tri thøc tiÒm Èn.

NÕu ph¸t hiÖn tri thøc lµ toµn bé qu¸ tr×nh rót ra tri thøc h÷u Ých tõ c¬ së d÷

liÖu th× khai ph¸ d÷ liÖu lµ giai ®o¹n chÝnh cña qu¸ tr×nh nµy [7]. Giai ®o¹n khai ph¸

d÷ liÖu ®−îc thùc hiÖn sau c¸c kh©u tinh läc vµ tiÒn xö lý d÷ liÖu, nh»m t×m ra c¸c

mÉu, c¸c xu h−íng cã ý nghÜa tõ c¸c tËp d÷ liÖu ®−îc hi väng lµ sÏ thÝch hîp víi

nhiÖm vô khai ph¸. ChØ c¸c mÉu, c¸c xu h−íng ®−îc xem lµ ®¸ng quan t©m (xÐt

theo mét ph−¬ng diÖn nµo ®ã) míi ®−îc coi lµ tri thøc, vµ tri thøc lµ cã Ých khi nã cã

thÓ gióp ®¹t ®−îc môc ®Ých cña hÖ thèng hoÆc ng−êi dïng. Ng−êi ta ®· sö dông c¸c

kü thuËt vµ c¸c kh¸i niÖm cña c¸c lÜnh vùc ®· ®−îc nghiªn cøu tõ tr−íc nh− häc

m¸y, nhËn d¹ng, thèng kª, håi quy, xÕp lo¹i, ph©n nhãm, c¸c m« h×nh ®å thÞ, m¹ng

Bayes... ®Ó khai ph¸ c¸c khèi d÷ liÖu cña kho d÷ liÖu nh»m ph¸t hiÖn ra c¸c mÉu

míi, c¸c t−¬ng quan míi, c¸c xu h−íng cã ý nghÜa.

Mét trong c¸c néi dung c¬ b¶n nhÊt trong khai ph¸ d÷ liÖu vµ rÊt phæ biÕn lµ

ph¸t hiÖn c¸c luËt kÕt hîp. Ph−¬ng ph¸p nµy nh»m t×m ra c¸c tËp thuéc tÝnh th−êng

xuÊt hiÖn ®ång thêi trong c¬ së d÷ liÖu, vµ rót ra c¸c luËt vÒ ¶nh h−ëng cña mét tËp

thuéc tÝnh ®Õn sù xuÊt hiÖn cña mét (hoÆc mét tËp) thuéc tÝnh kh¸c nh− thÕ nµo.

§iÒu ®ã cã thÓ ®−îc diÔn gi¶i nh− sau. Cho mét l−îc ®å R = {A1, A2,..., Ap} c¸c

thuéc tÝnh víi miÒn gi¸ trÞ {0, 1} vµ mét quan hÖ r trªn R, mét luËt kÕt hîp trªn r

®−îc m« t¶ d−íi d¹ng X → Y víi X ⊆ R vµ Y ∈ R \ X. VÒ mÆt trùc gi¸c, cã thÓ ph¸t

-5-

biÓu ý nghÜa cña luËt lµ: nÕu mét b¶n ghi cña b¶ng r cã gi¸ trÞ 1 t¹i mçi thuéc tÝnh

thuéc X th× gi¸ trÞ cña thuéc tÝnh Y còng lµ 1 trong b¶n ghi ®ã.

Cho W ⊆ R, ®Æt s(W, r) lµ tÇn sè xuÊt hiÖn cña W trong r ®−îc tÝnh b»ng tØ lÖ

cña c¸c hµng trong r cã gi¸ trÞ 1 t¹i mçi cét thuéc W. TÇn sè xuÊt hiÖn, cßn gäi lµ ®é

hç trî cña luËt X → Y trong r ®−îc ®Þnh nghÜa lµ s(X ∪ {Y}, r), ®é tin cËy cña luËt lµ

s(X∪ {Y}, r)/s(X, r). ë ®©y X cã thÓ gåm nhiÒu thuéc tÝnh, B lµ gi¸ trÞ kh«ng cè ®Þnh,

vµ ta thÊy kh«ng gian t×m kiÕm cã kÝch th−íc t¨ng theo hµm mò cña sè c¸c thuéc

tÝnh ë ®Çu vµo. NhiÖm vô cña viÖc ph¸t hiÖn c¸c luËt kÕt hîp lµ ph¶i t×m tÊt c¶ c¸c

luËt X → Y sao cho ®é hç trî cña luËt kh«ng nhá h¬n ng−ìng σ cho tr−íc vµ ®é tin

cËy cña luËt kh«ng nhá h¬n ng−ìng α cho tr−íc. Tõ mét c¬ së d÷ liÖu ta cã thÓ t×m

ra hµng ngh×n, thËm chÝ hµng tr¨m ngh×n c¸c luËt kÕt hîp.

Do viÖc ph¸t hiÖn luËt kÕt hîp ®ßi hái l−îng tÝnh to¸n vµ truy xuÊt d÷ liÖu

lín, cïng víi sù ph©n t¸n cña d÷ liÖu, ®Æc biÖt trªn c¸c c¬ së d÷ liÖu trùc tuyÕn, mét

gi¶i ph¸p tù nhiªn ®−îc nghÜ ®Õn lµ ¸p dông tÝnh to¸n song song, bëi c¸c m¸y tÝnh

song song vèn cã kh¶ n¨ng thùc hiÖn nhanh l−îng tÝnh to¸n lín vµ xö lý tèt l−îng

d÷ liÖu lín [4, 10, 15, 17]. C¸c thuËt to¸n ph¸t hiÖn luËt kÕt hîp cã thÓ ®−îc song

song hãa theo nhiÒu c¸ch kh¸c nhau: chóng ta cã thÓ t×m kiÕm ®éc lËp, song song

hãa hoÆc lÆp l¹i mét thuËt to¸n tuÇn tù. §Ó chän ®−îc chiÕn l−îc phï hîp, chóng ta

cÇn dùa trªn c¸c ®é ®o vÒ tÝnh phøc t¹p vµ chi phÝ cho lËp tr×nh song song víi mçi

chiÕn l−îc.

VÊn ®Ò d− thõa d÷ liÖu hoÆc d÷ liÖu kh«ng ®Çy ®ñ trong hÖ th«ng tin cã thÓ

®−îc kh¾c phôc b»ng c¸ch sö dông kh¸i niÖm tËp th« do Pawlak ®−a ra [14, 1]. TËp

th« cho phÐp chia b¶ng quyÕt ®Þnh thµnh c¸c thuéc tÝnh ®iÒu kiÖn vµ thuéc tÝnh

quyÕt ®Þnh, trong ®ã th«ng tin t−¬ng øng víi c¸c thuéc tÝnh quyÕt ®Þnh tuú thuéc

vµo th«ng tin t−¬ng øng víi c¸c thuéc tÝnh ®iÒu kiÖn, phï hîp víi c¸ch biÓu diÔn c¸c

luËt kÕt hîp. ViÖc nghiªn cøu luËt kÕt hîp th«ng qua c¸ch tiÕp c©n tËp th« ®· ®−îc

-6-

Tetsuya Murai, Yoshiharu Sato ®Ò xuÊt trong [12]. HÖ th«ng tin ®−îc ph©n ho¹ch

thµnh tËp c¸c tËp c¬ b¶n, mµ gi¸ trÞ cña tËp th« trong mçi tËp c¬ b¶n lµ gièng nhau,

tõ ®ã phÇn tö ®¹i diÖn cho mçi tËp c¬ b¶n ®−îc chän ra, ta cã ®−îc rót gän cña b¶ng

quyÕt ®Þnh ®Ó gi¶m bít khèi l−îng th«ng tin ®iÒu kiÖn d− thõa cã trong b¶ng quyÕt

®Þnh. Mèi quan hÖ cña luËt kÕt hîp trong c¸c hÖ th«ng tin con Si víi luËt kÕt hîp

trong hÖ th«ng tin hîp thµnh S = ∪ {Si} ®−îc t×m hiÓu ®Ó t×m ra ®iÒu kiÖn cho tÝnh

kh¶ t¸ch cña hÖ th«ng tin, tõ ®ã cã thÓ ph¸t hiÖn song song luËt kÕt hîp dùa trªn

ph©n t¸n theo d÷ liÖu.

LuËn v¨n víi ®Ò tµi "LuËt kÕt hîp theo tiÕp cËn lý thuyÕt tËp th« vµ khai ph¸ d÷

liÖu song song" kh¶o s¸t lÜnh vùc ph¸t hiÖn tri thøc trong c¬ së d÷ liÖu, trong ®ã tËp

trung vµo c¸c néi dung ph¸t hiÖn luËt kÕt hîp theo c¸ch tiÕp cËn cña tËp th«. M«

h×nh song song ph¸t hiÖn luËt kÕt hîp còng ®−îc xem xÐt víi viÖc ph©n tÝch mét sè

thuËt to¸n song song ph¸t hiÖn luËt kÕt hîp.

Ph−¬ng ph¸p nghiªn cøu chÝnh yÕu cña luËn v¨n lµ kh¶o s¸t c¸c bµi b¸o khoa

häc ®−îc xuÊt b¶n trong mét vµi n¨m gÇn ®©y tõ ®ã ®−a ra ®−îc mét sè ý t−ëng

nh»m c¶i tiÕn thuËt to¸n.

Néi dung cña b¶n luËn v¨n nµy gåm cã PhÇn më ®Çu, ba ch−¬ng vµ PhÇn kÕt

luËn. Cuèi mçi ch−¬ng cña b¶n luËn v¨n cã phÇn kÕt luËn ch−¬ng tr×nh bµy tãm t¾t

nh÷ng néi dung chÝnh yÕu trong néi dung cña ch−¬ng.

Ch−¬ng mét giíi thiÖu mét sè néi dung c¬ b¶n vÒ khai ph¸ d÷ liÖu vµ ph¸t

hiÖn tri thøc trong c¬ së d÷ liÖu (môc 1.1), c¸c hÖ thèng ®a xö lý vµ tÝnh to¸n song

song (môc 1.2.1); vµ c¸c chiÕn l−îc vµ m« h×nh chi phÝ cña khai ph¸ d÷ liÖu song

song (môc 1.2.2, 1.2.3). Mét sè néi dung trong ch−¬ng nµy ®−îc trÝch dÉn tõ c¸c tµi

liÖu [2], [7], [9]. §©y lµ nh÷ng kiÕn thøc nÒn t¶ng lµm c¬ së ®Ó cho néi dung c¸c

ch−¬ng sau vµ viÖc thiÕt lËp c¸c thuËt to¸n.

-7-

Ch−¬ng hai cña b¶n luËn v¨n tr×nh bµy vÒ kh¸i niÖm vµ mét sè c«ng nghÖ

ph¸t hiÖn luËt kÕt hîp (môc 2.1); lý thuyÕt tËp th« vµ vÊn ®Ò khai ph¸ d÷ liÖu theo

c¸ch tiÕp cËn tËp th« (môc 2.1). Mét thuËt to¸n t×m tËp tèi −u c¸c luËt vµ thuËt to¸n

c¶i tiÕn cña nã ®−îc tr×nh bµy (môc 2.2.2, thuËt to¸n 2.1, 2.2) cïng víi ®é phøc t¹p

vÒ thêi gian tÝnh to¸n. Hai thuËt to¸n nµy ®−îc dïng lµm c¬ së ®Ò xuÊt ra m« h×nh

song song t−¬ng øng trong ch−¬ng 3.

Ch−¬ng thø ba tr×nh bµy tãm t¾t mét sè thuËt to¸n ph¸t hiÖn song song luËt

kÕt hîp trªn c¸c nÒn phÇn cøng kh¸c nhau vµ so s¸nh chóng (môc 3.2). Qua kh¶o s¸t

mét bµi to¸n hÖ th«ng tin cña Së Y tÕ Hµ Néi [3], luËn v¨n còng ®Ò xuÊt mét m«

h×nh ph¸t hiÖn song song luËt kÕt hîp theo c¸ch tiÕp cËn tËp th«, trong ®ã c¬ së d÷

liÖu ®−îc tr×nh bµy d−íi d¹ng mét b¶ng quyÕt ®Þnh, vµ viÖc song song hãa ®−îc thùc

hiÖn trªn c¸c b−íc d÷ liÖu (môc 3.3).

PhÇn kÕt luËn ®−a ra mét sè néi dung liªn quan ®Õn ph−¬ng h−íng nghiªn

cøu ph¸t triÓn néi dung cña luËn v¨n nµy: ph¸t triÓn m« h×nh ph¸t hiÖn luËt kÕt hîp

vµ thö nghiÖm trªn hÖ thèng tÝnh to¸n song song thùc sù.

Néi dung c¬ b¶n cña b¶n luËn v¨n ®· ®−îc tr×nh bµy t¹i xª-mi-na khoa häc

t¹i bé m«n C¸c HÖ thèng Th«ng tin, Khoa C«ng nghÖ, §¹i häc Quèc gia Hµ Néi.

LuËn v¨n nµy ®−îc thùc hiÖn d−íi sù h−íng dÉn khoa häc cña TS. Hµ Quang

Thôy. T«i xin bµy tá lßng biÕt ¬n s©u s¾c tíi ThÇy ®· cã nh÷ng chØ dÉn tËn t×nh quý

b¸u gióp t«i cã thÓ hoµn thµnh b¶n luËn v¨n. T«i xin ch©n thµnh c¶m ¬n c¸c thÇy

gi¸o vµ b¹n bÌ trong bé m«n C¸c HÖ thèng Th«ng tin ®· cã nh÷ng gãp ý h÷u Ých

trong qu¸ tr×nh thùc hiÖn b¶n luËn v¨n. T«i còng xin c¶m ¬n c¸c thÇy c« gi¸o trong

khoa, c¸n bé thuéc phßng Khoa häc vµ §µo t¹o, Khoa C«ng nghÖ, ®· t¹o ®iÒu kiÖn

thuËn lîi gióp ®ì t«i trong qu¸ tr×nh häc tËp vµ nghiªn cøu t¹i Khoa. T«i v« cïng

c¶m ¬n nh÷ng ng−êi th©n trong gia ®×nh vµ b¹n bÌ ®· lu«n ®éng viªn khÝch lÖ ®Ó t«i

cã thÓ hoµn thµnh b¶n luËn v¨n nµy.

-8-

Ch−¬ng I. Tæng quan vÒ khai ph¸ d÷ liÖu vµ

khai ph¸ d÷ liÖu song song

I.1. Khai ph¸ d÷ liÖu vµ ph¸t hiÖn tri thøc trong c¬ së d÷ liÖu

I.1.1. S¬ bé vÒ khai ph¸ d÷ liÖu vµ ph¸t hiÖn tri thøc trong c¬ së d÷ liÖu

Ph¸t hiÖn tri thøc trong c¬ së d÷ liÖu lµ qu¸ tr×nh kh¸m ph¸ nh÷ng tri thøc cã

Ých tõ mét l−îng lín d÷ liÖu ®−îc l−u trong c¸c c¬ së d÷ liÖu. Do c¸c d÷ kiÖn d¹ng

®iÖn tö ®−îc thu thËp vµ tÝch lòy ngµy cµng nhiÒu, do nhu cÇu chuyÓn c¸c d÷ liÖu ®ã

thµnh c¸c th«ng tin vµ tri thøc cã Ých cho c¸c øng dông réng r·i nh− ph©n tÝch thÞ

tr−êng, qu¶n trÞ doanh nghiÖp, hç trî quyÕt ®Þnh ngµy cµng t¨ng, cho nªn lÜnh vùc

ph¸t hiÖn tri thøc ®· ngµy cµng ®−îc quan t©m trong ngµnh c«ng nghiÖp th«ng tin

trong nh÷ng n¨m gÇn ®©y [7].

C¸c c¬ së d÷ liÖu ®−îc x©y dùng víi môc ®Ých qu¶n lý, tËp hîp c¸c d÷ liÖu cã

tæ chøc vµ theo ®ã, mét kÕt qu¶ tù nhiªn lµ con ng−êi cã ®−îc mét khèi l−îng d÷

liÖu rÊt lín. NhiÒu d÷ liÖu nghÜa lµ cã thÓ cã nhiÒu th«ng tin. C¸c chuyªn gia ®−îc

®µo t¹o vÒ ph©n tÝch hç trî quyÕt ®Þnh ®· ph©n tÝch nh÷ng d÷ liÖu ®ã vµ ph¸t hiÖn ra

th«ng tin d−íi d¹ng c¸c mÉu vµ c¸c quy luËt tiÒm Èn sau quan hÖ gi÷a c¸c thuéc tÝnh

kh¸c nhau trong d÷ liÖu. ViÖc nµy gióp cho c¸c doanh nghiÖp thÊy ®−îc kÕt qu¶ cña

c¸c ho¹t ®éng tr−íc ®©y vµ ®Þnh h−íng cho c¸c ho¹t ®éng s¾p tíi. Tuy nhiªn, l−îng

d÷ liÖu s½n cã ®· trë nªn qu¸ lín ®Ó cã thÓ dÔ dµng ph¸t hiÖn ®−îc c¸c th«ng tin nh−

vËy.

Mét øng dông kh¸c cña ph¸t hiÖn tri thøc lµ cung cÊp c¸c hç trî quyÕt ®Þnh

t¸c nghiÖp [9]. Kh«ng nh− c¸ch tiÕp cËn hç trî quyÕt ®Þnh theo chu kú, trong ®ã thêi

gian tõ thêi ®iÓm ph¸t hiÖn ra th«ng tin tíi thêi ®iÓm dïng c¸c th«ng tin ®ã trong

qu¸ tr×nh ra quyÕt ®Þnh cã thÓ mÊt nhiÒu tuÇn hoÆc nhiÒu th¸ng (chóng th−êng ®−îc

dïng ®Ó hç trî quyÕt ®Þnh dµi h¹n cho doanh nghiÖp), hç trî quyÕt ®Þnh t¸c nghiÖp

-9-

cña ph¸t hiÖn tri thøc cã thÓ diÔn ra trong vµi phót vµ ®−îc dïng ®Ó cung cÊp hç trî

quyÕt ®Þnh ng¾n h¹n hoÆc tøc th× trong mét tËp rÊt Ýt c¸c tr−êng hîp, thËm chÝ trong

mét tr−êng hîp. Cã ®−îc c¸c hç trî nh− vËy do ph¸t hiÖn tri thøc ®· cung cÊp c¸c

kü thuËt, c«ng cô ®Æc thï thao t¸c tíi d÷ liÖu.

Trong qu¸ tr×nh ph¸t hiÖn tri thøc, mét sè kiÓu ph©n tÝch kh¸c nhau cã thÓ

®−îc dïng ®Ó ph¸t hiÖn ®−îc c¸c mÉu vµ quy luËt tõ d÷ liÖu ®· cã s½n, trong mét

t×nh huèng ®−îc ®Æt ra cña doanh nghiÖp, sau ®ã th«ng tin cã thÓ ®−îc l−u l¹i nh−

mét m« h×nh to¸n häc trõu t−îng cña d÷ liÖu vèn cã, ®−îc coi nh− mét m« h×nh ph¸t

hiÖn tri thøc. Sau khi ®· t¹o ®−îc m« h×nh ph¸t hiÖn tri thøc, d÷ liÖu míi cã thÓ ®−îc

kiÓm tra trong m« h×nh ®Ó xem liÖu nã cã phï hîp víi mÉu vµ quy luËt mong muèn

kh«ng. Tõ th«ng tin nµy, cã thÓ cã c¸c hµnh ®éng ®Ó c¶i thiÖn kÕt qu¶ trong mét

t×nh huèng ®−îc doanh nghiÖp ®Æt ra.

Mét ®Þnh nghÜa kh¸c vÒ ph¸t hiÖn tri thøc lµ qu¸ tr×nh nh»m x¸c ®Þnh ra c¸c mÉu

cã gi¸ trÞ, míi, cã tiÒm n¨ng sö dông vµ dÔ hiÓu tõ d÷ liÖu [7]. C¸c néi dung sau ®©y

h×nh thøc hãa ®Þnh nghÜa nµy. NÕu coi d÷ liÖu lµ mét tËp c¸c sù kiÖn F th× mÉu lµ

mét biÓu thøc E trong ng«n ng÷ L m« t¶ c¸c sù kiÖn trong mét tËp con FE cña F,

biÓu thøc nµy ph¶i ®¬n gi¶n h¬n lµ viÖc liÖt kª tÊt c¶ c¸c sù kiÖn trong F. C¸c tÝnh

chÊt cã gi¸ trÞ, cã tiÒm n¨ng sö dông, dÔ hiÓu cña mÉu lÇn l−ît ®−îc ®o b»ng c¸c

hµm C, U, S; c¸c hµm nµy ¸nh x¹ c¸c biÓu thøc trong ng«n ng÷ L vµo c¸c kh«ng

gian ®o cã thø tù toµn phÇn hay thø tù bé phËn MC, MU, MS.

C¸c mÉu thu ®−îc lµ míi nÕu cã c¸c thay ®æi trong d÷ liÖu khi so s¸nh gi¸ trÞ

hiÖn t¹i víi gi¸ trÞ cò hoÆc gi¸ trÞ dù ®o¸n, hoÆc cho thÊy c¸c gi¸ trÞ míi t×m ®−îc

liªn quan thÕ nµo víi c¸c gi¸ trÞ cò, ký hiÖu tÝnh míi mÎ cña mÉu lµ N(E, F), nã cã

thÓ lµ mét hµm logic hoÆc mét phÐp ®o vÒ møc ®é míi hoÆc kh«ng ngê tíi cña mÉu.

Mét kh¸i niÖm quan träng kh¸c lµ tÝnh thó vÞ, th−êng ®−îc coi lµ ®é ®o tæng thÓ gi¸

trÞ cña mÉu, tÝnh thó vÞ cã thÓ ®−îc ®o b»ng mét hµm I trong kh«ng gian ®é ®o

-10-

MI: i = I(E, F, C, N, U, S). MÉu E ∈ L ®−îc gäi lµ tri thøc nÕu víi ng−ìng i do ng−êi

dïng ®Þnh nghÜa, ta cã I(E, F, C, N, U, S) > i.

Nh×n chung, qu¸ tr×nh ph¸t hiÖn tri thøc lµ mét chuçi nèi tiÕp vµ lÆp l¹i c¸c

b−íc sau:

- lµm s¹ch d÷ liÖu: xö lý c¸c d÷ liÖu cã lçi, bÞ nhiÔu, thiÕu d÷ liÖu hoÆc d÷ liÖu

kh«ng thÝch hîp;

- tÝch hîp d÷ liÖu: c¸c nguån d÷ liÖu bÞ lÆp l¹i, kh«ng ®ång nhÊt cã thÓ ®−îc

tÝch hîp lµm mét;

- lùa chän d÷ liÖu: lÊy ra c¸c d÷ liÖu liªn quan tíi c«ng viÖc ph©n tÝch;

- biÕn ®æi d÷ liÖu: d÷ liÖu ®−îc biÕn ®æi hoÆc cñng cè d−íi c¸c d¹ng thÝch hîp

®Ó khai ph¸ b»ng c¸ch thùc hiÖn c¸c thao t¸c tãm t¾t hay tËp hîp.

- khai ph¸ d÷ liÖu: qu¸ tr×nh cèt yÕu ®Ó ¸p dông c¸c ph−¬ng ph¸p th«ng minh

nh»m t¸ch ra c¸c mÉu d÷ liÖu;

- ®¸nh gi¸ mÉu: x¸c ®Þnh c¸c mÉu thùc sù thó vÞ biÓu diÔn tri thøc dùa trªn mét

sè ®é ®o tÝnh thó vÞ;

- biÓu diÔn tri thøc: dïng c¸c kü thuËt biÓu diÔn tri thøc vµ trùc quan hãa ®Ó

®−a ra tri thøc míi khai ph¸ ®−îc cho ng−êi dïng.

Tõ viÖc s½n cã c¸c hÖ c¬ së d÷ liÖu quan hÖ vµ c¸c kho d÷ liÖu, bèn b−íc ®Çu

tiªn: lµm s¹ch d÷ liÖu, tÝch hîp d÷ liÖu, lùa chän d÷ liÖu vµ biÕn ®æi d÷ liÖu cã thÓ

®−îc thùc hiÖn b»ng c¸ch x©y dùng c¸c kho d÷ liÖu vµ thùc hiÖn mét sè phÐp xö lý

ph©n tÝch trùc tuyÕn (OLAP) trªn kho d÷ liÖu ®ã. §«i khi c¸c b−íc khai ph¸ d÷ liÖu,

®¸nh gi¸ mÉu vµ biÓu diÔn tri thøc ®−îc kÕt hîp vµo lµm mét qu¸ tr×nh (th−êng lµ

lÆp l¹i), ®−îc gäi lµ khai ph¸ d÷ liÖu. ViÖc khai ph¸ d÷ liÖu nµy ®−îc tiÕn hµnh trªn

tËp d÷ liÖu cã hi väng lµ sÏ thÝch hîp víi nhiÖm vô khai ph¸ ®Ó cã ®−îc c¸c mÉu thó

vÞ, chø kh«ng ph¶i trªn toµn bé d÷ liÖu trong thêi gian ®ñ dµi ®Ó cã c¸c mÉu kh«ng

thùc sù cã Ých nh− kh¸i niÖm trong thèng kª tr−íc ®©y.

-11-

I.1.2. Néi dung cña khai ph¸ d÷ liÖu

I.1.2.1 C¸c nhiÖm vô chÝnh cña khai ph¸ d÷ liÖu

C«ng viÖc khai ph¸ d÷ liÖu cã thÓ chia lµm hai lo¹i: khai ph¸ d÷ liÖu m« t¶ vµ

khai ph¸ d÷ liÖu dù ®o¸n [2, 7]. Lo¹i thø nhÊt m« t¶ d÷ liÖu mét c¸ch ng¾n gän, tãm

t¾t vµ tr×nh bµy c¸c tÝnh chÊt chung ®¸ng quan t©m cña d÷ liÖu. Lo¹i thø hai x©y

dùng mét hoÆc mét tËp c¸c m« h×nh, thùc hiÖn c¸c phÐp suy luËn trªn d÷ liÖu s½n cã

vµ dù ®o¸n hµnh vi cña c¸c tËp d÷ liÖu míi.

C¸c môc tiªu m« t¶ vµ dù ®o¸n ®¹t ®−îc th«ng qua c¸c c«ng viÖc khai ph¸ d÷

liÖu chÝnh sau ®©y:

- Ph©n líp lµ viÖc häc mét hµm ¸nh x¹ mét mÉu d÷ liÖu vµo mét trong sè c¸c

líp ®· x¸c ®Þnh. Qu¸ tr×nh nµy ph©n tÝch mét tËp d÷ liÖu huÊn luyÖn (tøc lµ mét tËp

c¸c ®èi t−îng mµ ta ®· biÕt tªn líp cña nã) vµ x©y dùng mét m« h×nh cho mçi líp

dùa trªn c¸c ®Æc tÝnh trong d÷ liÖu. Mét c©y quyÕt ®Þnh hoÆc mét tËp c¸c luËt ph©n

líp ®−îc t¹o ra tõ qu¸ tr×nh ph©n líp ®ã, nã cã thÓ ®−îc dïng ®Ó hiÓu râ h¬n mçi líp

trong c¬ së d÷ liÖu vµ ®Ó ph©n lo¹i d÷ liÖu trong t−¬ng lai.

VÝ dô, ng−êi ta cã thÓ ph©n lo¹i c¸c bÖnh vµ gióp dù ®o¸n bÖnh dùa trªn c¸c

triÖu chøng cña bÖnh nh©n. Ph©n líp ®−îc dïng trong viÖc ph©n nhãm kh¸ch hµng,

m« h×nh hãa doanh nghiÖp vµ ph©n tÝch tÝn dông...

- Håi quy lµ viÖc häc mét hµm ¸nh x¹ tõ mét mÉu d÷ liÖu sang mét biÕn dù

®o¸n cã gi¸ trÞ thùc. Cã rÊt nhiÒu c¸c øng dông khai ph¸ d÷ liÖu víi nhiÖm vô håi

quy, vÝ dô nh− ®¸nh gi¸ kh¶ n¨ng tö vong cña bÖnh nh©n dùa trªn c¸c kÕt qu¶ xÐt

nghiÖm chÈn ®o¸n, dù ®o¸n nhu cÇu tiªu thô mét s¶n phÈm míi b»ng mét hµm chi

tiªu qu¶ng c¸o.

- Ph©n nhãm (®o¹n) lµ viÖc m« t¶ chung ®Ó t×m ra c¸c tËp x¸c ®Þnh c¸c nhãm

®Ó m« t¶ d÷ liÖu. C¸c nhãm cã thÓ t¸ch rêi hoÆc ph©n cÊp hoÆc gèi lªn nhau, tøc lµ

-12-

mét d÷ liÖu cã thÓ võa thuéc nhãm nµy, võa thuéc nhãm kh¸c. C¸c øng dông khai

ph¸ d÷ liÖu cã nhiÖm vô ph©n nhãm nh− ph¸t hiÖn tËp kh¸ch hµng cã ph¶n øng

gièng nhau trong c¬ së d÷ liÖu tiÕp thÞ, x¸c ®Þnh c¸c lo¹i quang phæ tõ c¸c ph−¬ng

ph¸p ®o tia hång ngo¹i.

- Tãm t¾t lµ ph−¬ng ph¸p t×m kiÕm mét m« t¶ c« ®äng cho mét tËp con d÷

liÖu. VÝ dô nh− viÖc lËp b¶ng c¸c ®é lÖch chuÈn vµ trung b×nh cho tÊt c¶ c¸c tr−êng.

C¸c kü thuËt tãm t¾t th−êng ®−îc ¸p dông cho c¸c ph©n tÝch d÷ liÖu t−¬ng t¸c cã

tÝnh th¨m dß vµ t¹o b¸o c¸o tù ®éng.

- M« h×nh ho¸ phô thuéc bao gåm viÖc t×m kiÕm mét m« h×nh m« t¶ sù phô

thuéc ®¸ng kÓ gi÷a c¸c biÕn. C¸c m« h×nh phô thuéc tån t¹i d−íi hai møc: møc cÊu

tróc cña m« h×nh x¸c ®Þnh nh÷ng biÕn nµo lµ phô thuéc côc bé víi nhau, vµ møc

®Þnh l−îng cña mét m« h×nh x¸c ®Þnh ®é m¹nh cña sù phô thuéc theo mét th−íc ®o

nµo ®ã.

- Ph¸t hiÖn sù thay ®æi vµ chÖch h−íng khai th¸c nh÷ng thay ®æi ®¸ng kÓ

nhÊt trong d÷ liÖu tõ c¸c gi¸ trÞ chuÈn hoÆc ®−îc ®o tr−íc ®ã.

C¸c nhiÖm vô kh¸c nhau nµy ®ßi hái sè l−îng vµ d¹ng th«ng tin kh¸c nhau

nªn chóng th−êng ¶nh h−ëng ®Õn viÖc thiÕt kÕ vµ chän thuËt to¸n khai ph¸ d÷ liÖu

kh¸c nhau.

I.1.2.2 C¸c thµnh phÇn cña thuËt to¸n khai ph¸ d÷ liÖu

Ba thµnh phÇn chñ yÕu trong mét thuËt to¸n khai ph¸ d÷ liÖu lµ biÓu diÔn m«

h×nh, ®¸nh gi¸ m« h×nh vµ ph−¬ng ph¸p t×m kiÕm.

BiÓu diÔn m« h×nh lµ viÖc x©y dùng ng«n ng÷ L ®Ó miªu t¶ c¸c mÉu cã thÓ

ph¸t hiÖn ®−îc. NÕu sù m« t¶ nµy bÞ giíi h¹n qu¸ th× sÏ kh«ng x©y dùng ®−îc m«

h×nh chÝnh x¸c cho d÷ liÖu, v× thÕ ng−êi ph©n tÝch d÷ liÖu ph¶i hiÓu ®Çy ®ñ c¸c kh¶

n¨ng tiªu biÓu cña ph−¬ng ph¸p ®−îc dïng. Ngoµi ra ng−êi thiÕt kÕ thuËt to¸n còng

-13-

cÇn chØ râ gi¶ thiÕt m« t¶ nµo ®−îc t¹o bëi thuËt to¸n nµo. M« h×nh cã kh¶ n¨ng

miªu t¶ qu¸ m¹nh sÏ lµm t¨ng nguy c¬ d÷ liÖu huÊn luyÖn qu¸ phï hîp, dÉn ®Õn

viÖc gi¶m ®é chÝnh x¸c dù ®o¸n c¸c d÷ liÖu ch−a biÕt, thªm vµo ®ã nã cßn lµm cho

viÖc t×m kiÕm trë nªn phøc t¹p vµ viÖc gi¶i thÝch m« h×nh khã h¬n.

§¸nh gi¸ m« h×nh xem xÐt mét mÉu cã ®¸p øng ®−îc c¸c tiªu chuÈn cña qu¸

tr×nh ph¸t hiÖn tri thøc hay kh«ng. ViÖc ®¸nh gi¸ ®é chÝnh x¸c dù ®o¸n dùa trªn

®¸nh gi¸ chÐo, ®¸nh gi¸ chÊt l−îng m« t¶ liªn quan ®Õn ®é chÝnh x¸c dù ®o¸n, tÝnh

míi mÎ, tÝnh h÷u Ých vµ dÔ hiÓu cña m« h×nh. C¶ hai tiªu chuÈn thèng kª vµ logic cã

thÓ ®−îc dïng ®Ó ®¸nh gi¸ m« h×nh.

Ph−¬ng ph¸p t×m kiÕm bao gåm hai thµnh phÇn lµ t×m kiÕm tham sè vµ t×m

kiÕm m« h×nh. ThuËt to¸n ph¶i t×m ra c¸c tham sè ®Ó tèi −u ho¸ c¸c tiªu chuÈn ®¸nh

gi¸ m« h×nh víi c¸c d÷ liÖu quan s¸t ®−îc vµ mét c¸ch miªu t¶ m« h×nh ®· ®Þnh.

Trong t×m kiÕm m« h×nh, miªu t¶ m« h×nh ®−îc thay ®æi ®Ó xÐt mét hä c¸c m« h×nh

míi. Víi mçi c¸ch biÓu diÔn m« h×nh, ph−¬ng ph¸p t×m kiÕm tham sè ®−îc ¸p dông

®Ó ®Ó ®¸nh gi¸ chÊt l−îng m« h×nh. C¸c ph−¬ng ph¸p t×m kiÕm m« h×nh th−êng sö

dông c¸c kü thuËt t×m kiÕm pháng ®o¸n do kÝch th−íc lín cña kh«ng gian c¸c m«

h×nh th−êng c¶n trë viÖc t×m kiÕm toµn diÖn.

I.1.3. C¸c ph−¬ng ph¸p khai ph¸ d÷ liÖu phæ biÕn vµ viÖc lùa chän ph−¬ng ph¸p

Cã rÊt nhiÒu c¸c ph−¬ng ph¸p khai ph¸ d÷ liÖu, mçi ph−¬ng ph¸p cã ®Æc

®iÓm riªng vÒ biÓu diÔn m« h×nh, ®¸nh gi¸ m« h×nh vµ c¸ch t×m kiÕm, phï hîp víi

víi mét líp c¸c bµi to¸n víi c¸c d¹ng d÷ liÖu vµ miÒn d÷ liÖu nhÊt ®Þnh. D−íi ®©y lµ

mét sè ph−¬ng ph¸p phæ biÕn th−êng ®−îc dïng [9]:

- Ph−¬ng ph¸p quy n¹p

- C©y quyÕt ®Þnh vµ luËt

- Ph¸t hiÖn luËt kÕt hîp

- C¸c ph−¬ng ph¸p ph©n líp vµ quy håi phi tuyÕn

-14-

- Ph©n nhãm vµ ph©n ®o¹n

- C¸c ph−¬ng ph¸p dùa trªn mÉu

- Khai ph¸ d÷ liÖu v¨n b¶n

- M¹ng n¬-ron

- ThuËt to¸n di truyÒn.

- M« h×nh phô thuéc dùa trªn ®å thÞ x¸c suÊt.

- M« h×nh häc quan hÖ

C¸c thuËt to¸n khai ph¸ d÷ liÖu tù ®éng vÉn míi chØ ë giai ®o¹n ph¸t triÓn ban ®Çu. Ng−êi ta vÉn ch−a ®−a ra ®−îc mét tiªu chuÈn nµo trong viÖc quyÕt ®Þnh sö dông ph−¬ng ph¸p nµo vµ trong tr−êng hîp nµo th× cã hiÖu qu¶.

HÇu hÕt c¸c kü thuËt khai ph¸ d÷ liÖu ®Òu míi ®èi víi lÜnh vùc kinh doanh. H¬n n÷a l¹i cã rÊt nhiÒu kü thuËt, mçi kü thuËt ®−îc sö dông cho nhiÒu bµi to¸n kh¸c nhau. Mçi ph−¬ng ph¸p ®Òu cã ®iÓm m¹nh vµ ®iÓm yÕu cña nã, nh−ng hÇu hÕt c¸c ®iÓm yÕu ®Òu cã thÓ kh¾c phôc ®−îc, v× vËy cÇn t×m c¸ch ¸p dông mçi kü thuËt mét c¸ch thËt ®¬n gi¶n, dÔ sö dông ®Ó kh«ng c¶m thÊy nh÷ng phøc t¹p vèn cã cña kü thuËt ®ã.

§Ó so s¸nh c¸c kü thuËt cÇn ph¶i cã mét tËp lín c¸c quy t¾c vµ c¸c ph−¬ng ph¸p thùc nghiÖm tèt. Th−êng th× quy t¾c nµy kh«ng ®−îc sö dông khi ®¸nh gi¸ c¸c kü thuËt míi nhÊt. V× vËy mµ nh÷ng yªu cÇu c¶i thiÖn ®é chÝnh x¸c kh«ng ph¶i lóc nµo còng thùc hiÖn ®−îc.

NhiÒu c«ng ty ®· ®−a ra nh÷ng s¶n phÈm sö dông kÕt hîp nhiÒu kü thuËt khai ph¸ d÷ liÖu kh¸c nhau víi hy väng nhiÒu kü thuËt th× sÏ tèt h¬n. Nh−ng thùc tÕ cho thÊy nhiÒu kü thuËt chØ thªm nhiÒu r¾c rèi vµ g©y khã kh¨n cho viÖc so s¸nh gi÷a c¸c ph−¬ng ph¸p vµ c¸c s¶n phÈm. Theo nhiÒu ®¸nh gi¸ cho thÊy khi ®· hiÓu ®−îc c¸c kü thuËt vµ nghiªn cøu tÝnh gièng nhau gi÷a chóng, ng−êi ta thÊy r»ng nhiÒu kü thuËt lóc ®Çu th× cã vÎ kh¸c nhau nh−ng thùc chÊt khi hiÓu ra ®−îc c¸c kü thuËt nµy th× thÊy chóng hoµn toµn gièng nhau. Tuy nhiªn, ®¸nh gi¸ nµy còng chØ ®Ó tham kh¶o v× cho ®Õn nay, khai ph¸ d÷ liÖu vÉn cßn lµ kü thuËt míi chøa nhiÒu tiÒm n¨ng mµ ng−êi ta vÉn ch−a khai th¸c hÕt.

-15-

I.1.4 ¦u thÕ cña khai ph¸ d÷ liÖu

Khai ph¸ d÷ liÖu thùc chÊt kh«ng cã g× míi mµ hoµn toµn dùa trªn c¸c ph−¬ng ph¸p c¬ b¶n ®· biÕt. VËy khai ph¸ d÷ liÖu cã g× kh¸c so víi c¸c ph−¬ng ph¸p ®ã vµ t¹i sao khai ph¸ d÷ liÖu l¹i cã −u thÕ h¬n h¼n chóng? C¸c ph©n tÝch sau ®©y sÏ gi¶i ®¸p nh÷ng c©u hái nµy [2].

Häc m¸y (Machine Learning)

Tuy ph−¬ng ph¸p häc m¸y ®· ®−îc c¶i tiÕn ®Ó nã cã thÓ phï hîp víi môc ®Ých khai ph¸ d÷ liÖu nh−ng sù kh¸c biÖt gi÷a thiÕt kÕ, c¸c ®Æc ®iÓm cña c¬ së d÷ liÖu ®· lµm nã trë nªn kh«ng phï hîp víi môc ®Ých nµy mÆc dï cho ®Õn nay phÇn lín c¸c ph−¬ng ph¸p khai ph¸ d÷ liÖu vÉn dùa trªn nÒn t¶ng c¬ së cña ph−¬ng ph¸p häc m¸y.

Trong c¸c hÖ qu¶n trÞ c¬ së d÷ liÖu, mét c¬ së d÷ liÖu lµ mét tËp hîp d÷ liÖu ®−îc tÝch hîp mét c¸ch logic, ®−îc l−u trong mét hay nhiÒu tÖp vµ ®−îc tæ chøc ®Ó l−u tr÷, söa ®æi vµ lÊy th«ng tin mét c¸ch hiÖu qu¶ vµ dÔ dµng. Trong häc m¸y, thuËt ng÷ c¬ së d÷ liÖu chñ yÕu ®Ò cËp tíi mét tËp c¸c mÉu (instance hay example) ®−îc l−u trong mét tÖp. C¸c mÉu th−êng lµ c¸c vector thuéc tÝnh cã ®é dµi cè ®Þnh, th«ng tin vÒ tªn thuéc tÝnh vµ d·y gi¸ trÞ cña chóng ®«i khi còng ®−îc l−u l¹i nh− trong tõ ®iÓn d÷ liÖu. Mét thuËt to¸n häc cßn sö dông tËp d÷ liÖu vµ c¸c th«ng tin kÌm theo tËp d÷ liÖu ®ã lµm ®Çu vµo vµ ®Çu ra biÓu thÞ kÕt qu¶ cu¶ viÖc häc.

Víi so s¸nh c¬ së d÷ liÖu th«ng th−êng vµ c¬ së d÷ liÖu trong häc m¸y nh− trªn, cã thÓ thÊy lµ häc m¸y cã kh¶ n¨ng ®−îc ¸p dông cho c¬ së d÷ liÖu, bëi v× kh«ng ph¶i häc trªn tËp c¸c mÉu mµ häc trªn tÖp c¸c b¶n ghi cña c¬ së d÷ liÖu. Tuy nhiªn, ph¸t hiÖn tri thøc trong c¬ së d÷ liÖu lµm t¨ng thªm c¸c khã kh¨n vèn ®· lµ ®iÓn h×nh trong häc m¸y vµ ®¨ v−ît qu¸ kh¶ n¨ng cña häc m¸y. Trong thùc tÕ, c¬ së d÷ liÖu th−êng ®éng, kh«ng ®Çy ®ñ, bÞ nhiÔu vµ lín h¬n nhiÒu so víi c¸c tËp d÷ liÖu häc m¸y ®iÓn h×nh. C¸c yÕu tè nµy lµm cho hÇu hÕt c¸c thuËt to¸n häc m¸y trë nªn kh«ng hiÖu qu¶ trong hÇu hÕt c¸c tr−êng hîp. V× vËy trong khai ph¸ d÷ liÖu, cÇn tËp trung rÊt nhiÒu c«ng søc vµo viÖc v−ît qua nh÷ng vÊn ®Ò nµy trong CSDL.

-16-

Ph−¬ng ph¸p hÖ chuyªn gia

C¸c hÖ chuyªn gia cè g¾ng n¾m b¾t c¸c tri thøc thÝch hîp víi mét bµi to¸n nµo ®ã. C¸c kü thuËt thu thËp gióp cho viÖc lÊy tri thøc tõ c¸c chuyªn gia con ng−êi. Mçi ph−¬ng ph¸p ®ã lµ mét c¸ch suy diÔn c¸c luËt tõ c¸c vÝ dô vµ gi¶i ph¸p ®èi víi bµi to¸n chuyªn gia ®−a ra. Ph−¬ng ph¸p nµy kh¸c víi khai ph¸ d÷ liÖu ë chç c¸c vÝ dô cña chuyªn gia th−êng ë møc chÊt l−îng cao h¬n rÊt nhiÒu so víi c¸c d÷ liÖu trong c¬ së d÷ liÖu, vµ chóng th−êng chØ bao qu¸t ®−îc c¸c tr−êng hîp quan träng. H¬n n÷a, c¸c chuyªn gia sÏ x¸c nhËn tÝnh gi¸ trÞ vµ h÷u dông cña c¸c mÉu ph¸t hiÖn ®−îc. Còng nh− víi c¸c c«ng cô qu¶n trÞ c¬ së d÷ liÖu, ë c¸c ph−¬ng ph¸p nµy ®ßi hái cã sù tham gia cña con ng−êi trong viÖc ph¸t hiÖn tri thøc.

Ph¸t kiÕn khoa häc

Khai ph¸ d÷ liÖu rÊt kh¸c víi ph¸t kiÕn khoa häc ë chç nh÷ng khai ph¸ trong c¬ së d÷ liÖu Ýt cã chñ t©m vµ cã ®iÒu khiÓn h¬n. C¸c d÷ liÖu khoa häc cã tõ thùc nghiÖm nh»m lo¹i bá mét sè t¸c ®éng cña c¸c tham sè ®Ó nhÊn m¹nh ®é biÕn thiªn cña mét hay mét sè tham sè ®Ých. Tuy nhiªn, c¸c c¬ së d÷ liÖu th−¬ng m¹i th−êng ghi l¹i mét sè l−îng thõa th«ng tin vÒ c¸c dù ¸n cña hä ®Ó ®¹t ®−îc mét sè môc ®Ých vÒ mÆt tæ chøc. Sù d− thõa nµy cã thÓ lµ hiÓn hiÖn hay Èn chøa trong c¸c mèi quan hÖ d÷ liÖu. H¬n n÷a, c¸c nhµ khoa häc cã thÓ t¹o l¹i c¸c thÝ nghiÖm vµ cã thÓ t×m ra r»ng c¸c thiÕt kÕ ban ®Çu kh«ng thÝch hîp. Trong khi ®ã, c¸c nhµ qu¶n lý c¬ së d÷ liÖu hÇu nh− kh«ng thÓ xa xØ ®i thiÕt kÕ l¹i c¸c tr−êng d÷ liÖu vµ thu thËp l¹i d÷ liÖu.

Ph−¬ng ph¸p thèng kª

MÆc dï c¸c ph−¬ng ph¸p thèng kª cung cÊp mét nÒn t¶ng lý thuyÕt v÷ng ch¾c cho c¸c bµi to¸n ph©n tÝch d÷ liÖu nh−ng chØ cã tiÕp cËn thèng kª thuÇn tuý th«i ch−a ®ñ. Thø nhÊt, c¸c ph−¬ng ph¸p thèng kª chuÈn kh«ng phï hîp ®èi víi c¸c kiÓu d÷ liÖu cã cÊu tróc trong rÊt nhiÒu c¬ së d÷ liÖu. Thø hai, c¸c ph−¬ng ph¸p thèng kª hoµn toµn bÞ d÷ liÖu ®iÒu khiÓn, nã kh«ng sö dông tri thøc s½n cã vÒ lÜnh vùc. Thø ba, c¸c kÕt qu¶ cña ph©n tÝch thèng kª cã thÓ sÏ rÊt nhiÒu vµ khã cã thÓ lµm râ ®−îc. Cuèi cïng, c¸c ph−¬ng ph¸p thèng kª cÇn cã sù h−íng dÉn cña ng−êi dïng ®Ó x¸c ®Þnh ph©n tÝch d÷ liÖu nh− thÕ nµo vµ ë ®©u.

-17-

Sù kh¸c nhau c¬ b¶n gi÷a khai ph¸ d÷ liÖu vµ thèng kª lµ ë chç khai ph¸ d÷ liÖu lµ mét ph−¬ng tiÖn ®−îc dïng bëi ng−êi dïng cuèi chø kh«ng ph¶i lµ c¸c nhµ thèng kª. Khai ph¸ d÷ liÖu tù ®éng hãa qu¸ tr×nh thèng kª mét c¸ch hiÖu qu¶, v× vËy lµm nhÑ bít c«ng viÖc cña ng−êi dïng cuèi, t¹o ra mét c«ng cô dÔ sö dông h¬n. Nh− vËy, nhê cã khai ph¸ d÷ liÖu, viÖc dù ®o¸n vµ kiÓm tra rÊt vÊt v¶ tr−íc ®©y cã thÓ ®−îc ®−a lªn m¸y tÝnh, ®−îc tÝnh, dù ®o¸n vµ kiÓm tra mét c¸ch tù ®éng.

I.1.5. Mét sè th¸ch thøc trong øng dông vµ nghiªn cøu kü thuËt khai ph¸ d÷ liÖu

ViÖc nghiªn cøu vµ øng dông c¸c kü thuËt khai ph¸ d÷ liÖu cßn gÆp nhiÒu khã kh¨n, c¸c khã kh¨n nµy kh«ng ph¶i lµ kh«ng thÓ gi¶i quyÕt, song chóng cÇn ®−îc t×m hiÓu ®Ó cã thÓ ph¸t triÓn tèt h¬n. Nh÷ng khã kh¨n ®iÓn h×nh ®−îc tr×nh bµy d−íi ®©y.

C¸c vÊn ®Ò vÒ c¬ së d÷ liÖu

§Çu vµo chñ yÕu cña mét hÖ thèng ph¸t hiÖn tri thøc lµ c¸c d÷ liÖu th« trong

c¬ së d÷ liÖu. Nh÷ng vÊn ®Ò khã kh¨n ph¸t sinh trong khai ph¸ d÷ liÖu chÝnh tõ

nguyªn nh©n lµ d÷ liÖu trong thùc tÕ th−êng ®éng, kh«ng ®Çy ®ñ, lín vµ bÞ nhiÔu.

Trong nh÷ng tr−êng hîp kh¸c, ng−êi ta kh«ng biÕt c¬ së d÷ liÖu cã chøa c¸c th«ng

tin cÇn thiÕt cho viÖc khai th¸c hay kh«ng vµ lµm thÕ nµo ®Ó gi¶i quyÕt sù d− thõa

th«ng tin kh«ng thÝch hîp nµy.

- D÷ liÖu lín: Cho ®Õn nay, c¸c c¬ së d÷ liÖu víi hµng tr¨m tr−êng vµ b¶ng, hµng triÖu b¶n ghi vµ víi kÝch th−íc gigabyte ®· lµ chuyÖn b×nh th−êng. HiÖn nay ®· b¾t ®Çu xuÊt hiÖn c¸c c¬ së d÷ liÖu cã kÝch th−íc tíi tetrabyte. C¸c ph−¬ng ph¸p gi¶i quyÕt hiÖn nay lµ ®−a ra mét ng−ìng cho c¬ së d÷ liÖu, lÊy mÉu, c¸c ph−¬ng ph¸p xÊp xØ, xö lý song song.

- KÝch th−íc lín: Kh«ng chØ cã sè l−îng b¶n ghi mµ sè c¸c tr−êng trong c¬ së d÷ liÖu còng nhiÒu, v× vËy mµ kÝch th−íc cña bµi to¸n trë nªn lín h¬n. Mét tËp d÷ liÖu cã kÝch th−íc lín sÏ lµm t¨ng kh«ng gian t×m kiÕm. H¬n n÷a, nã còng lµm t¨ng kh¶ n¨ng mét thuËt to¸n khai ph¸ d÷ liÖu cã thÓ t×m thÊy c¸c

-18-

mÉu gi¶. BiÖn ph¸p kh¾c phôc lµ lµm gi¶m kÝch th−íc t¸c ®éng cña bµi to¸n vµ sö dông c¸c tri thøc biÕt tr−íc ®Ó x¸c ®Þnh c¸c biÕn kh«ng phï hîp.

- D÷ liÖu ®éng: §Æc ®iÓm c¬ b¶n cña hÇu hÕt c¸c c¬ së d÷ liÖu lµ néi dung cña chóng thay ®æi liªn tôc, d÷ liÖu cã thÓ thay ®æi theo thêi gian vµ viÖc khai ph¸ d÷ liÖu bÞ ¶nh h−ëng bëi thêi ®iÓm quan s¸t d÷ liÖu. ViÖc thay ®æi d÷ liÖu nhanh chãng cã thÓ lµm cho c¸c mÉu khai th¸c ®−îc tr−íc ®ã mÊt gi¸ trÞ. H¬n n÷a, c¸c biÕn trong c¬ së d÷ liÖu cña øng dông ®· cho còng cã thÓ bÞ thay ®æi, bÞ xãa hoÆc lµ t¨ng lªn theo thêi gian. VÊn ®Ò nµy ®−îc gi¶i quyÕt b»ng c¸c gi¶i ph¸p n©ng cÊp c¸c mÉu vµ coi nh÷ng thay ®æi nh− lµ c¬ héi ®Ó khai th¸c b»ng c¸ch sö dông nã ®Ó t×m kiÕm c¸c mÉu bÞ thay ®æi.

- C¸c tr−êng hîp kh«ng phï hîp: Mét ®Æc ®iÓm quan träng kh¸c lµ tÝnh kh«ng thÝch hîp cña d÷ liÖu, nghÜa lµ môc d÷ liÖu trë thµnh kh«ng thÝch hîp víi träng t©m hiÖn t¹i cña viÖc khai th¸c. Mét khÝa c¹nh kh¸c ®«i khi còng liªn quan ®Õn tÝnh phï hîp lµ sù cã gi¸ trÞ cña mét thuéc tÝnh ®èi víi mét tËp con cña c¬ së d÷ liÖu.

- C¸c gi¸ trÞ bÞ thiÕu: Sù cã mÆt hay v¾ng mÆt cña gi¸ trÞ c¸c thuéc tÝnh d÷ liÖu phï hîp cã thÓ ¶nh h−ëng ®Õn viÖc khai ph¸ d÷ liÖu. Trong hÖ thèng t−¬ng t¸c, sù thiÕu v¾ng d÷ liÖu quan träng cã thÓ dÉn tíi yªu cÇu cho gi¸ trÞ cña nã hoÆc kiÓm tra ®Ó x¸c ®Þnh gi¸ trÞ cña nã. HoÆc còng cã thÓ sù v¾ng mÆt cña d÷ liÖu ®−îc coi nh− mét ®iÒu kiÖn, thuéc tÝnh bÞ mÊt cã thÓ ®−îc coi nh− mét gi¸ trÞ trung gian vµ lµ gi¸ trÞ kh«ng biÕt.

- C¸c tr−êng bÞ thiÕu: Mét quan s¸t kh«ng ®Çy ®ñ c¬ së d÷ liÖu cã thÓ lµm cho d÷ liÖu cã c¸c gi¸ trÞ bÞ xem nh− cã lçi. ViÖc quan s¸t c¬ së d÷ liÖu ph¶i ph¸t hiÖn ®−îc toµn bé c¸c thuéc tÝnh cã thÓ dïng ®Ó thuËt to¸n khai ph¸ d÷ liÖu cã thÓ ¸p dông ®Ó gi¶i quyÕt bµi to¸n. Gi¶ sö ta cã c¸c thuéc tÝnh ®Ó ph©n biÖt c¸c t×nh huèng ®¸ng quan t©m. NÕu chóng kh«ng lµm ®−îc ®iÒu ®ã th× cã nghÜa lµ ®· cã lçi trong d÷ liÖu. §©y còng lµ vÊn ®Ò th−êng x¶y ra trong c¬ së d÷ liÖu kinh doanh. C¸c thuéc tÝnh quan träng cã thÓ sÏ bÞ thiÕu d÷ liÖu kh«ng ®−îc chuÈn bÞ cho viÖc khai ph¸ d÷ liÖu.

-19-

- §é nhiÔu vµ kh«ng ch¾c ch¾n: §èi víi c¸c thuéc tÝnh ®· thÝch hîp, ®é nghiªm träng cña lçi phô thuéc vµo kiÓu d÷ liÖu cña c¸c gi¸ trÞ ®−îc phÐp. C¸c gi¸ trÞ cña c¸c thuéc tÝnh kh¸c nhau cã thÓ lµ c¸c sè thùc, sè nguyªn, chuçi, vµ cã thÓ thuéc vµo tËp c¸c gi¸ trÞ ®Þnh danh. C¸c gi¸ trÞ ®Þnh danh nµy cã thÓ s¾p xÕp theo thø tù bé phËn hoÆc ®Çy ®ñ, thËm chÝ cã thÓ cã cÊu tróc ng÷ nghÜa.

Mét yÕu tè kh¸c cña ®é kh«ng ch¾c ch¾n lµ tÝnh kÕ thõa hoÆc ®é chÝnh x¸c

mµ d÷ liÖu cÇn cã, nãi c¸ch kh¸c lµ ®é nhiÔu cña d÷ liÖu. Dùa trªn viÖc tÝnh

to¸n trªn c¸c phÐp ®o vµ ph©n tÝch cã −u tiªn, m« h×nh thèng kª m« t¶ tÝnh

ngÉu nhiªn ®−îc t¹o ra vµ ®−îc sö dông ®Ó ®Þnh nghÜa ®é mong muèn vµ ®é

dung sai cña d÷ liÖu. Th−êng th× c¸c m« h×nh thèng kª ®−îc ¸p dông theo

c¸ch ®Æc biÖt ®Ó x¸c ®Þnh mét c¸ch chñ quan c¸c thuéc tÝnh ®Ó ®¹t ®−îc c¸c

thèng kª vµ ®¸nh gi¸ kh¶ n¨ng chÊp nhËn cña c¸c gi¸ trÞ thuéc tÝnh. §Æc biÖt

lµ víi c¸c kiÓu d÷ liÖu sè, sù ®óng ®¾n cña d÷ liÖu cã thÓ lµ mét yÕu tè trong

viÖc khai ph¸. VÝ dô nh− trong viÖc ®o nhiÖt ®é c¬ thÓ, ta th−êng cho phÐp

chªnh lÖch 0.1 ®é. Nh−ng viÖc ph©n tÝch theo xu h−íng nh¹y c¶m nhiÖt ®é

cña c¬ thÓ l¹i yªu cÇu ®é chÝnh x¸c cao h¬n. §Ó mét hÖ thèng khai th¸c cã

thÓ liªn hÖ ®Õn xu h−íng nµy ®Ó chuÈn ®o¸n th× l¹i cÇn cã mét ®é nhiÔu trong

d÷ liÖu ®Çu vµo.

- Mèi quan hÖ phøc t¹p gi÷a c¸c tr−êng: C¸c thuéc tÝnh hoÆc c¸c gi¸ trÞ cã

cÊu tróc ph©n cÊp, c¸c mèi quan hÖ gi÷a c¸c thuéc tÝnh vµ c¸c ph−¬ng tiÖn

phøc t¹p ®Ó diÔn t¶ tri thøc vÒ néi dung cña c¬ së d÷ liÖu yªu cÇu c¸c thuËt

to¸n ph¶i cã kh¶ n¨ng sö dông mét c¸ch hiÖu qu¶ c¸c th«ng tin nµy. Ban ®Çu,

kü thuËt khai ph¸ d÷ liÖu chØ ®−îc ph¸t triÓn cho c¸c b¶n ghi cã gi¸ trÞ thuéc

tÝnh ®¬n gi¶n. Tuy nhiªn, ngµy nay ng−êi ta ®ang t×m c¸ch ph¸t triÓn c¸c kü

thuËt nh»m rót ra mèi quan hÖ gi÷a c¸c biÕn nµy.

-20-

Mét sè vÊn ®Ò kh¸c

- "Qu¸ phï hîp": Khi mét thuËt to¸n t×m kiÕm c¸c tham sè tèt nhÊt cho mét m« h×nh nµo ®ã sö dông mét tËp d÷ liÖu h÷u h¹n, nã cã thÓ sÏ bÞ t×nh tr¹ng “qu¸ ®é” d÷ liÖu (nghÜa lµ t×m kiÕm qu¸ møc cÇn thiÕt g©y ra hiÖn t−îng chØ phï hîp víi c¸c d÷ liÖu ®ã mµ kh«ng cã kh¶ n¨ng ®¸p øng cho c¸c d÷ liÖu l¹), lµm cho m« h×nh ho¹t ®éng rÊt kÐm ®èi víi c¸c d÷ liÖu thö. C¸c gi¶i ph¸p kh¾c phôc bao gåm ®¸nh gi¸ chÐo (cross-validation), thùc hiÖn theo nguyªn t¾c nµo ®ã hoÆc sö dông c¸c biÖn ph¸p thèng kª kh¸c.

- Kh¶ n¨ng biÓu ®¹t cña mÉu: Trong rÊt nhiÒu øng dông, ®iÒu quan träng lµ nh÷ng ®iÒu khai th¸c ®−îc ph¶i cµng dÔ hiÓu víi con ng−êi cµng tèt. V× vËy, c¸c gi¶i ph¸p th−êng bao gåm viÖc diÔn t¶ d−íi d¹ng ®å häa, x©y dùng cÊu tróc luËt víi c¸c ®å thÞ cã h−íng, biÓu diÔn b»ng ng«n ng÷ tù nhiªn vµ c¸c kü thuËt kh¸c nh»m biÓu diÔn c¸c tri thøc vµ d÷ liÖu.

- Sù t−¬ng t¸c víi ng−êi sö dông vµ c¸c tri thøc s½n cã: RÊt nhiÒu c«ng cô vµ ph−¬ng ph¸p khai ph¸ d÷ liÖu kh«ng thùc sù t−¬ng t¸c víi ng−êi dïng vµ kh«ng dÔ dµng kÕt hîp cïng víi c¸c tri thøc ®· biÕt tr−íc ®ã. ViÖc sö dông tri thøc miÒn lµ rÊt quan träng trong khai ph¸ d÷ liÖu. §· cã nhiÒu biÖn ph¸p nh»m kh¾c phôc vÊn ®Ò nµy nh− sö dông c¬ së d÷ liÖu suy diÔn ®Ó ph¸t hiÖn tri thøc, nh÷ng tri thøc nµy sau ®ã ®−îc sö dông ®Ó h−íng dÉn cho viÖc t×m kiÕm khai ph¸ d÷ liÖu hoÆc sö dông ph©n bè vµ x¸c suÊt d÷ liÖu tr−íc ®ã nh− mét d¹ng m· hãa tri thøc cã s½n.

I.2. Khai ph¸ d÷ liÖu song song

HÇu hÕt c¸c thuËt to¸n khai ph¸ d÷ liÖu ®Òu ®ßi hái sè l−îng tÝnh to¸n lín,

chóng cÇn cã kh¶ n¨ng më réng ®−îc ®Ó xö lý l−îng d÷ liÖu lín h¬n vµ phøc t¹p

h¬n [7]. Mét sè c¬ së d÷ liÖu vèn liªn quan tíi Internet vµ do ®ã ®· s½n cã tÝnh ph©n

t¸n. TÝnh to¸n song song vèn cã thÓ xö lý tèt l−îng tÝnh to¸n lín trªn l−îng lín d÷

liÖu, v× thÕ nã lµ mét c«ng cô tèt ®Ó khai ph¸ d÷ liÖu [8].

-21-

I.2.1. C¸c hÖ thèng tÝnh to¸n song song

Cã hai c¸ch t¨ng tèc ®é phÇn cøng m¸y tÝnh: vÒ mÆt c«ng nghÖ cã thÓ sö

dông c¸c thiÕt bÞ tèc ®é cao, vÒ mÆt cÊu tróc cã thÓ t¹o c¸c cÊu tróc míi hoÆc ghÐp

c¸c hÖ s½n cã víi nhau theo nh÷ng c¸ch s¸ng t¹o. C¸c bé ®a xö lý cung cÊp mét lùa

chän tèt ®Ó n©ng cao hiÖu suÊt c¸c hÖ thèng m¸y tÝnh b»ng c¸ch ghÐp nèi mét sè bé

xö lý cã gi¸ thµnh thÊp. Mét hÖ thèng ®a xö lý gåm c¸c bé vi xö lý chuÈn s½n cã thÓ

®¹t tØ lÖ chi phÝ/hiÖu suÊt tèt h¬n mét bé ®¬n xö lý tèc ®é cao dùa trªn c«ng nghÖ

lai. Gi¸ t−¬ng ®èi cao cña c¸c hÖ ®a xö lý cã thÓ ®−îc bï ®¾p b»ng c¸ch khai th¸c

chóng nh− c¸c m¸y chñ tÝnh to¸n trong c¸c hÖ ph©n t¸n. §a xö lý ®−îc dïng ®Ó t¨ng

l−u l−îng hÖ thèng b»ng c¸ch thùc hiÖn song song mét sè tiÕn tr×nh kh¸c nhau cña

ng−êi sö dông trªn c¸c bé xö lý kh¸c nhau, vµ t¨ng tèc øng dông b»ng c¸ch thùc

hiÖn song song mét sè phÇn cña øng dông. C¸c phÇn cña øng dông ®−îc song song

hãa cÇn ®−îc ®ång bé hãa vµ trao ®æi d÷ liÖu sau khi hoµn thµnh mçi b−íc tÝnh

to¸n. Sù ®ång bé hãa vµ truyÒn th«ng gi÷a c¸c bé xö lý nãi chung sÏ lµm gi¶m mét

phÇn tèc ®é do nã t¹m dõng mét sè tÝnh to¸n vµ sö dông b¨ng th«ng kÕt nèi hÖ

thèng. Mét trong nh÷ng th¸ch thøc vÒ thiÕt kÕ hÖ ®a xö lý lµ lµm sao gi¶m thiÓu c¸c

t−¬ng t¸c gi÷a c¸c bé xö lý vµ cã mét c¬ chÕ hiÖu qu¶ ®Ó thùc hiÖn viÖc nµy khi cÇn

thiÕt.

I.2.1.1. TÝnh chÊt vµ ph©n lo¹i c¸c hÖ ®a xö lý

C¸c hÖ ®a xö lý cã c¸c −u ®iÓm chÝnh nh−: kh¶ n¨ng tÝnh to¸n vµ hiÖu suÊt

cao, kh¶ n¨ng kh¸ng lçi, kh¶ n¨ng thÝch nghi, cã thÓ ph¸t triÓn theo m«-®un, chuyªn

m«n ho¸ c¸c chøc n¨ng vµ cã tØ lÖ chi phÝ/ hiÖu suÊt thÊp. Víi c¸c −u ®iÓm nµy, c¸c

hÖ ®a xö lý cã thÓ ®−îc thiÕt kÕ theo m«-®un vµ tù ®iÒu chØnh mét c¸ch linh ho¹t

nh»m cã ®−îc hÖ thèng tèi −u cho c¸c môc ®Ých cô thÓ [10].

C¸c hÖ thèng tÝnh to¸n song song gåm bèn lo¹i chÝnh: xö lý ®¬n lÖnh ®¬n d÷

liÖu (SISD), xö lý ®¬n lÖnh ®a d÷ liÖu (SIMD), xö lý ®a lÖnh ®¬n d÷ liÖu (MISD) vµ

-22-

xö lý ®a lÖnh ®a d÷ liÖu (MIMD). C¸c bé ®a xö lý thuéc vÒ lo¹i cuèi cïng, chóng l¹i

cã thÓ ®−îc chia thµnh c¸c bé ®a xö lý ghÐp chÆt, trong ®ã tÊt c¶ c¸c bé xö lý ®Òu

®−îc truy cËp tíi bé nhí chia sÎ toµn côc, vµ c¸c bé ®a xö lý ghÐp láng, trong ®ã c¸c

bé xö lý cã bé nhí riªng, kh«ng cã bé nhí toµn côc ®−îc chia sÎ. Còng tån t¹i c¸c

hÖ lai trong ®ã c¸c bé xö lý cã bé nhí riªng nh−ng vÉn ®−îc truy cËp vµo bé nhí

chung, thËm chÝ c¶ vµo bé nhí riªng cña c¸c bé xö lý kh¸c. Trong c¸c hÖ ghÐp chÆt

th× bé nhí toµn côc chÝnh lµ c¬ së truyÒn th«ng vµ ®ång bé hãa gi÷a c¸c bé xö lý;

trong c¸c hÖ ghÐp láng, sù truyÒn th«ng nµy ®−îc thùc hiÖn bëi c¬ chÕ truyÒn th«ng

b¸o. §é trÔ lín trong c¸c ®−êng truyÒn th«ng ngµy nay ®· ®−îc gi¶m bít nhê sù

ph¸t triÓn cña sîi quang häc vµ c¸c c«ng nghÖ m¹ng tèc ®é cao.

I.2.1.2. C¸c c¸ch kÕt nèi trong hÖ ®a xö lý

C¸c kiÓu cÊu tróc c¬ b¶n th−êng gÆp cña c¸c hÖ ®a xö lý gåm c¸c hÖ h−íng

®−êng truyÒn, c¸c hÖ kÕt nèi chÐo, cÊu tróc siªu khèi, vµ c¸c hÖ dùa trªn chuyÓn

m¹ch nhiÒu tÇng [11].

- C¸c hÖ h−íng ®−êng truyÒn lµ mét trong nh÷ng c¸ch t¹o hÖ ®a xö lý ®¬n gi¶n

nhÊt b»ng c¸ch dïng mét ®−êng truyÒn chung ®Ó nèi c¸c bé xö lý vµ c¸c bé nhí.

Trong s¬ ®å, nµy c¸c bé xö lý cã thÓ cã hoÆc kh«ng cã c¸c bé nhí riªng, c¸c thiÕt bÞ

nhËp/xuÊt cã thÓ ®−îc g¾n víi c¸c bé xö lý hoÆc víi ®−êng truyÒn chung, vµ b¶n

th©n bé nhí chia sÎ còng th−êng ®−îc t¹o d−íi d¹ng mét sè vïng nhí g¾n liÒn víi

®−êng truyÒn chung. §−êng truyÒn chia sÎ vµ bé nhí chia sÎ lµ hai yÕu tè chÝnh cña

hÖ h−íng ®−êng truyÒn. Cã thÓ dïng c¸c bé nhí truy cËp nhanh (cache) ®Ó gi¶m t¶i

cho ®−êng truyÒn chung, chóng cã thÓ ®−îc g¾n víi bé nhí chung hoÆc víi mçi bé

xö lý. C¸ch thø hai th−êng ®−îc dïng h¬n, tuy nhiªn viÖc duy tr× tÝnh nhÊt qu¸n

gi÷a c¸c b¶n sao vËt lý cña d÷ liÖu ®−îc l−u trong cache th−êng lµm t¨ng l−u l−îng

®−êng truyÒn, lµm gi¶m Ých lîi cña viÖc sö dông cache riªng cho mçi bé xö lý. Khã

kh¨n nµy sÏ ®−îc gi¶m bít nÕu dïng ®−êng truyÒn réng hoÆc dïng giao thøc ph©n

-23-

t¸ch yªu cÇu/®¸p øng ®Ó c¸c yªu cÇu vµ ®¸p øng vÒ bé nhí ®−îc xö lý nh− nh÷ng

nhiÖm vô kh¸c nhau, sau khi mét bé xö lý yªu cÇu mét vïng nhí, ®−êng truyÒn cã

thÓ ®−îc dµnh cho c¸c bé xö lý kh¸c dïng trong thêi gian bé nhí t×m vµ tËp hîp ®ñ

c¸c thµnh phÇn liªn quan. Tuy kh¶ n¨ng më réng cña c¸c hÖ ®a xö lý h−íng ®−êng

truyÒn bÞ h¹n chÕ do sù c¹nh tranh cña ®−êng truyÒn chia sÎ vµ bé nhí chia sÎ, c¸ch

tiÕp cËn nµy vÉn ®−îc sö dông réng r·i trong nhiÒu øng dông th−¬ng m¹i do c¸ch

thùc hiÖn ®¬n gi¶n cña nã.

CÊu tróc hÖ ®a xö lý h−íng ®−êng truyÒn

- C¸c hÖ kÕt nèi chÐo cho phÐp N bé xö lý ®ång thêi truy cËp vµo N bé nhí víi

®iÒu kiÖn t¹i mçi thêi ®iÓm, mçi bé xö lý truy cËp vµo mét bé nhí kh¸c nhau, b¶n

th©n hÖ nµy kh«ng cã tÝnh c¹nh tranh vµ lµ c¸ch ®èi lËp víi hÖ thèng h−íng ®−êng

truyÒn. Sù chËm trÔ gi÷a mét bé xö lý vµ mét bé nhí chØ x¶y ra ë ®iÓm kÕt nèi,

trong tr−êng hîp c¸c bé xö lý kh«ng cã bé nhí riªng th× ®©y lµ hÖ thèng ®a xö lý

truy cËp bé nhí kh«ng ®æi. Sù xÕp ®Æt d÷ liÖu mét c¸ch hîp lý sÏ tr¸nh ®−îc tranh

chÊp cã thÓ x¶y ra khi nhiÒu h¬n mét bé xö lý cïng cè truy cËp mét bé nhí, song nã

còng kh«ng tr¸nh ®−îc tranh chÊp khi cã nhiÒu bé xö lý cïng cè truy cËp mét vÞ trÝ

trong cïng mét bé nhí. V× thÕ s¬ ®å nµy cho phÐp song song hãa møc cao gi÷a c¸c

c«ng viÖc kh«ng liªn quan, tuy nhiªn sù ®ång bé hãa gi÷a c¸c tiÕn tr×nh hoÆc c¸c bé

xö lý trªn bé nhí chia sÎ sÏ dÔ g©y ra tranh chÊp vÒ bé nhí. Do m« h×nh nµy cÇn N2

-24-

®iÓm kÕt nèi ®Ó nèi N bé nhí víi N bé xö lý, ®é phøc t¹p sÏ t¨ng gÊp 4 theo sè phÇn

tö, lµm h¹n chÕ kh¶ n¨ng më réng cña s¬ ®å nµy.

KÕt nèi chÐo

- HÖ thèng siªu khèi gi¶i quyÕt ®−îc bµi to¸n vÒ kh¶ n¨ng më réng vµ gi¸

thµnh b»ng c¸c liªn kÕt cã ®é phøc t¹p t¨ng theo hµm l«-ga-rit cña sè nót N vµ

kho¶ng c¸ch tèi ®a gi÷a c¸c nót lµ log2N. CÊu tróc nµy lµ ®Ö quy theo nghÜa c¸c siªu

khèi nhiÒu chiÒu chøa c¸c siªu khèi Ýt chiÒu h¬n nh− nh÷ng tËp con cña m×nh. HÖ

thèng nµy sö dông c¸c bé nhí riªng cho mçi bé xö lý vµ truyÒn th«ng b¸o ®Ó truyÒn

th«ng vµ ®ång bé hãa gi÷a c¸c bé xö lý. Ngoµi chøc n¨ng xö lý, mçi nót cßn thùc

hiÖn c¸c giao thøc truyÒn th«ng, nã còng ®Þnh tuyÕn vµ chuyÓn tiÕp c¸c th«ng b¸o

®Ó t¹o ®−êng truyÒn th«ng gi¸n tiÕp gi÷a c¸c nót tõ xa kÕt nèi trùc tiÕp víi nã. C¸c

thiÕt bÞ nhËp/xuÊt cã thÓ ®−îc g¾n côc bé vµo mçi nót, ®Ó t¨ng b¨ng th«ng

nhËp/xuÊt ng−êi ta cã thÓ dïng mét sè nót nhËp/xuÊt chuyªn dông nh− c¸c luång vµ

kho chøa d÷ liÖu nhËp/xuÊt cho mét nhãm c¸c nót.

-25-

Siªu khèi 8 nót: (a) m« h×nh 3 chiÒu (b) c¸c kÕt nèi gi÷a c¸c bé xö lý

- C¸c hÖ thèng dùa trªn bé chuyÓn m¹ch nhiÒu tÇng ®Ó kÕt nèi c¸c bé xö lý vµ

c¸c bé nhí. KiÓu tæng qu¸t nhÊt cña c¸ch tiÕp cËn nµy cung cÊp c¸c liªn kÕt gi÷a N

®Çu vµo vµ N ®Çu ra, nã cã log2N tÇng, mçi tÇng gåm N liªn kÕt tíi N/2 hép trao

®æi. M¹ng chuyÓn m¹ch cã thÓ nèi bÊt kú ®Çu vµo víi ®Çu ra nµo b»ng c¸ch t¹o c¸c

kÕt nèi thÝch hîp t¹i mçi tÇng. ViÖc ®Þnh tuyÕn trong m¹ng nµy th−êng lµ cè ®Þnh vµ

®−îc thùc hiÖn nhê c¸c thÎ ®Þa chØ ®Ých mµ bªn göi göi kÌm víi yªu cÇu kÕt nèi.

ChuyÓn m¹ch nhiÒu tÇng cã thÓ ®ång thêi kÕt nèi tÊt c¶ c¸c ®Çu vµo vµ tÊt c¶ c¸c

®Çu ra víi ®iÒu kiÖn kh«ng cã hai bé xö lý nµo ®ång thêi cè truy cËp cïng mét m«-

®un bé nhí; nÕu kh«ng th× tranh chÊp t¹i c¶ m«-®un bé nhí vµ trong m¹ng chuyÓn

m¹ch sÏ x¶y ra vµ g©y t¾c nghÏn. §Ó tr¸nh ®iÒu nµy x¶y ra, ng−êi ta thªm phÇn cøng

phô trî vµo b¶n th©n hÖ thèng chuyÓn m¹ch; hÖ thèng cã thªm kh¶ n¨ng xö lý t¹i

c¸c ®iÓm chuyÓn m¹ch ®−îc gäi lµ m¹ng kÕt hîp.

-26-

M¹ng chuyÓn m¹ch nhiÒu tÇng vµ ®−êng nèi P2-M4

I.2.2. C¸c chiÕn l−îc khai ph¸ d÷ liÖu song song

Khai ph¸ d÷ liÖu song song ®ßi hái ph©n chia c«ng viÖc ®Ó c¸c bé xö lý cã

thÓ thùc hiÖn phÇn c«ng viÖc cña m×nh, nh»m ®¹t kÕt qu¶ cuèi cïng mét c¸ch nhanh

nhÊt. VÊn ®Ò lµ ë chç ph©n chia c«ng viÖc nh− thÕ nµo, ta cã thÓ ph©n chia viÖc tÝnh

to¸n, còng cã thÓ ph©n chia viÖc truy cËp tíi d÷ liÖu, vµ gi¶m thiÓu sù truyÒn th«ng

gi÷a c¸c bé xö lý trong khi thùc hiÖn. Trong c¸c øng dông khai ph¸ d÷ liÖu, ta cÇn

gi¶m thiÓu nguån tµi nguyªn ®−îc dïng ®Ó sinh c¸c kh¸i niÖm cã vÎ cã gi¸ trÞ ®Þa

ph−¬ng, dùa trªn l−îng h¹n chÕ d÷ liÖu cã s½n t¹i mçi bé xö lý, nh−ng kh«ng cã gi¸

trÞ toµn phÇn. Cã ba chiÕn l−îc ®Ó song song hãa c¸c thuËt to¸n khai ph¸ d÷ liÖu [13,

15], ®ã lµ:

- T×m kiÕm ®éc lËp: Mçi bé xö lý ®−îc truy cËp tíi toµn bé tËp d÷ liÖu, nh−ng

chØ tËp trung vµo mét phÇn kh«ng gian t×m kiÕm, b¾t ®Çu tõ mét ®iÓm ®−îc chän

ngÉu nhiªn.

-27-

C¸ch nµy phï hîp víi c¸c bµi to¸n mµ kÕt qu¶ cÇn t×m lµ mét gi¶i ph¸p tèi

−u, tuy nhiªn nã ®ßi hái mçi bé xö lý ph¶i truy cËp toµn bé tËp d÷ liÖu, khiÕn tèc ®é

bÞ chËm l¹i.

- Song song hãa mét thuËt to¸n khai ph¸ d÷ liÖu tuÇn tù: TËp c¸c kh¸i niÖm

®−îc ph©n chia gi÷a c¸c bé xö lý, mçi bé xö lý kiÓm tra toµn bé tËp d÷ liÖu ®Ó kiÓm

tra xem c¸c kh¸i niÖm côc bé cña nã cã ®óng trªn ph¹m vi toµn côc kh«ng. Do viÖc

t¹o kh¸i niÖm míi th−êng ®ßi hái ph¶i biÕt c¸c kh¸i niÖm nhá h¬n hay ®¬n gi¶n h¬n

nµo lµ ®óng, c¸c bé xö lý ph¶i th−êng xuyªn trao ®æi th«ng tin vÒ c¸c kh¸i niÖm cña

chóng. Mét c¸ch kh¸c lµ tËp d÷ liÖu ®−îc ph©n chia theo c¸c cét, mçi bé xö lý t×m

ra c¸c kh¸i niÖm trªn c¸c cét mµ chóng gi÷.

Theo c¸ch nµy còng cÇn th−êng xuyªn trao ®æi th«ng tin ®Ó x¸c ®Þnh xem c¸c

kh¸i niÖm côc bé nµo cã thÓ ghÐp l¹i thµnh kh¸i niÖm ®óng trªn toµn côc.

- LÆp l¹i mét thuËt to¸n khai ph¸ d÷ liÖu tuÇn tù: Mçi bé xö lý lµm viÖc trªn

mét phÇn cña tËp d÷ liÖu (theo hµng), vµ thùc hiÖn thuËt to¸n tuÇn tù. Do chØ cã mét

phÇn th«ng tin, nã t¹o nªn c¸c kh¸i niÖm ®óng côc bé, nh−ng cã thÓ kh«ng ®óng

trªn toµn côc - c¸c kh¸i niÖm xÊp xØ. C¸c bé xö lý trao ®æi c¸c kh¸i niÖm xÊp xØ nµy,

hoÆc c¸c sè liÖu vÒ chóng, ®Ó kiÓm tra xem chóng cã ®óng trªn toµn côc kh«ng. Khi

lµm nh− vËy mçi bé xö lý häc ®−îc vÒ nh÷ng phÇn d÷ liÖu mµ chóng kh«ng nh×n

thÊy.

C¸ch nµy cã hai −u ®iÓm ®¸ng chó ý: tËp d÷ liÖu ®−îc ph©n chia gióp cho chi

phÝ truy cËp ®−îc chia ®Òu cho c¸c bé xö lý, vµ d÷ liÖu cÇn ®−îc trao ®æi gi÷a c¸c

pha th−êng nhá h¬n rÊt nhiÒu so víi b¶n th©n c¸c kh¸i niÖm, v× thÕ kh«ng tèn nhiÒu

chi phÝ cho truyÒn th«ng.

-28-

I.2.3. C¸c m« h×nh chi phÝ

§Ó xem mét kü thuËt khai ph¸ d÷ liÖu cã nªn ®−îc thùc hiÖn song song hay

kh«ng, ta cÇn x¸c ®Þnh ®é phøc t¹p cña nã, dùa trªn m« h×nh chi phÝ thùc tÕ. Chi phÝ

cho mét ch−¬ng tr×nh song song gåm hai phÇn: l−îng tÝnh to¸n mµ nã thùc hiÖn vµ

C

=

+

i

i

lý

xö

wMax bécc xö ¸

ghMax bécc lý ¸

truyÒn th«ng gi÷a c¸c bé xö lý. Chi phÝ nµy cã thÓ ®−îc tÝnh chÝnh x¸c bëi [15]:

víi hµm Max ®−îc tÝnh trªn tËp toµn bé c¸c bé xö lý; wi lµ sè c¸c lÖnh ®−îc thùc

hiÖn bëi bé xö lý i; hi lµ sè byte ®−îc göi hoÆc nhËn bëi bé xö lý i; vµ g lµ kh¶ n¨ng

truyÒn cña m¹ng, tÝnh b»ng sè ®¬n vÞ thêi gian ®Ó truyÒn mçi byte.

XÐt mét thuËt to¸n khai ph¸ d÷ liÖu tuÇn tù: gi¶ sö tËp d÷ liÖu gåm n hµng cã

kÝch th−íc m vµ c¸c thuËt to¸n t¹o ra s kh¸i niÖm. Mçi thuËt to¸n gåm mét sè k_s

lÇn lÆp ®Ó t¹o ra c¸c kh¸i niÖm lín h¬n tõ c¸c kh¸i niÖm nhá h¬n. §é phøc t¹p ®−îc

t

s

=

k

s

s

+

ACCESS

cos

_

_

,

( nm

)

( nm

[ STEP

] )

cho bëi c«ng thøc:

víi STEP lµ chi phÝ cho mét b−íc lÆp, ACCESS lµ chi phÝ xö lý d÷ liÖu.

D−íi ®©y tr×nh bµy c¸c chiÕn l−îc song song ho¸ c¸c thuËt to¸n tuÇn tù nªu

trªn [15].

I.2.3.1. XÊp xØ c¸c kh¸i niÖm

- Chia d÷ liÖu lµm p tËp con, mçi tËp trªn mét bé xö lý.

- Thùc hiÖn thuËt to¸n tuÇn tù (hoÆc c¶i biªn cña thuËt to¸n trªn mçi tËp con).

- Trao ®æi th«ng tin mçi bé xö lý häc ®−îc víi c¸c bé xö lý kh¸c.

- LÆp l¹i.

Gi¸ cña thuËt to¸n xÊp xØ kh¸i niÖm cã d¹ng:

-29-

+

ak

r

ACCESS

=

rpg

RES

cos

at _

*_

,

( rp

nm p

nm p

⎞ +⎟⎟ ⎠

⎛ ⎜⎜ ⎝

⎞ +⎟⎟ ⎠

⎛ ⎜⎜ ⎝

⎡ STEP ⎢ ⎣

⎤ )⎥ ⎦

trong ®ã r lµ kÝch th−íc cña c¸c kh¸i niÖm xÊp xØ ®−îc t¹o bëi mçi bé xö lý; rpg lµ

tæng chi phÝ cña viÖc trao ®æi c¸c kh¸i niÖm xÊp xØ nµy gi÷a c¸c bé xö lý; RES(rp) lµ

chi phÝ tÝnh to¸n cña viÖc s¾p xÕp c¸c kh¸i niÖm xÊp xØ nµy ®Ó tÝnh ®−îc c¸c xÊp xØ

STEP

r

r

,

,

)

( nm

)

STEP

r

ACCESS

r

,

,

tèt h¬n cho lÇn lÆp sau. Cã thÓ gi¶ thiÕt r»ng:

nm p

( nm p

nm p

ACCESS p

⎛ ⎜⎜ ⎝

⎛ ⎜⎜ ⎝

⎞ =⎟⎟ ⎠

⎞ =⎟⎟ ⎠

s

_

=

+

+

RES

cos

at _

ak _

vµ

( rpg

( rp

) )

t cos p

⇒

Nh− vËy, ta t¨ng tèc ®−îc p lÇn, kh«ng kÓ tæng chi phÝ, víi ®iÒu kiÖn k_s vµ k_a cã

kÝch th−íc cã thÓ so s¸nh ®−îc. Trao ®æi kÕt qu¶ th−êng xuyªn cã thÓ c¶i thiÖn ®é

chÝnh x¸c nhanh h¬n víi mét sè thuËt to¸n, vÝ thÕ k_a << k_s. §iÒu nµy cho ta sù

s

_

=

+

chi

phÝ

cos

at _

*

_

_

( tæng

)

t cos p

ak _ k s _

t¨ng tèc gÊp ®«i:

I.2.3.2. Ph©n chia c¸c kh¸i niÖm

- Chia tËp d÷ liÖu lµm p tËp con dùa trªn c¸c thuéc tÝnh

- Thùc hiÖn mét biÕn ®æi cô thÓ cña mét thuËt to¸n khai ph¸ d÷ liÖu trªn tËp con

nµy ®Ó lÊy ra c¸c kh¸i niÖm hoÆc c¸c tham sè m« h×nh chØ øng víi tËp con c¸c

thuéc tÝnh nµy.

- LÆp l¹i.

- KÕt hîp c¸c kh¸i niÖm côc bé hîp lý víi nhau ®Ó t¹o ra c¸c kh¸i niÖm m« t¶

toµn bé tËp d÷ liÖu.

Gi¸ cña thuËt to¸n kh¸i niÖm bé phËn cã d¹ng:

-30-

+

t

p

k

p

n

r

ACCESS

n

=

EXCH

g

RES

cos

_

_

,

,

,

,

,

*

,

,

( prmn ,

)

( prmn ,

m p

m p

⎞ +⎟⎟ ⎠

⎛ ⎜⎜ ⎝

⎞ +⎟⎟ ⎠

⎛ ⎜⎜ ⎝

⎡ SPECIAL ⎢ ⎣

⎤ )⎥ ⎦

víi hµm SPECIAL tÝnh ®é phøc t¹p cña mét b−íc cña thuËt to¸n; EXCH lµ chi phÝ

trao ®æi c¸c kh¸i niÖm côc bé.

I.2.3.3. C¸c chiÕn l−îc t×m kiÕm ®éc lËp

Kh«ng ph©n chia d÷ liÖu. Thay v× thùc hiÖn cïng mét thuËt to¸n p lÇn, sö

dông mét sè kü thuËt ngÉu nhiªn ®Ó h−íng thuËt to¸n sang mét phÇn kh¸c cña

kh«ng gian t×m kiÕm c¸c kh¸i niÖm.

t

i

=

k

s

+

ACCESS

+

s

g

+

s

cos

_

i *_

,

*

( nm

)

( nm

[ STEP

] )

k

s

k

_ = i

Gi¸ cña mét thuËt to¸n t×m kiÕm ®éc lËp cã d¹ng:

_ p

. Râ rµng c¸ch tiÕp cËn nµy chØ cã ý nghÜa nÕu ta cã lý do ®Ó gi¶ sö r»ng

I.2.3.4. So s¸nh c¸c chiÕn l−îc

Gi¸ cña c¸c chiÕn l−îc thùc hiÖn kh¸c nhau ë trªn phô thuéc vµo gi¸ trÞ cña

c¸c gi¸ trÞ k_a, k_p, k_i. Tuy nhiªn, gi¶ sö r»ng chóng kh«ng tåi h¬n k_s th× ta cã

thÓ xÕp h¹ng c¸c c¸ch song song hãa nh− sau:

ThuËt to¸n kh¸i niÖm xÊp xØ tèt h¬n thuËt to¸n kh¸i niÖm côc bé, tèt h¬n

thuËt to¸n t×m kiÕm ®éc lËp. C¸c kü thuËt kÕt hîp tõng phÇn t¹o nhiÒu kh¸i niÖm mµ

chóng kh«ng thÓ lµ mét bé phËn cña tËp kh¸i niÖm lín h¬n. V× thÕ c¸c tËp t¹o bëi

mçi thuËt to¸n ®éc lËp lµ lín h¬n nhiÒu so víi c¸c tËp cã ®−îc sau khi gi¶i quyÕt, cã

nghÜa lµ mçi thuËt to¸n ®· lµm mét viÖc v« Ých. Còng vËy, t×m kiÕm ®éc lËp kh«ng

lîi dông ®−îc mét thùc tÕ lµ c¸c bé xö lý kh¸c còng ®· cã thÓ ph¸t hiÖn ra c¸c tri

thøc cã Ých mµ cã thÓ tØa bít sù t×m kiÕm ë bé xö lý nµy, vµ nã l¹i thùc hiÖn c«ng

viÖc v« Ých.

-31-

KÕt luËn ch−¬ng 1

Ch−¬ng nµy ®· tr×nh bµy nh÷ng néi dung chÝnh yÕu vÒ khai ph¸ d÷ liÖu, hÖ

thèng tÝnh to¸n song song vµ ¸p dông trong khai ph¸ d÷ liÖu song song. ViÖc ph¸t

hiÖn tri thøc (nh÷ng mÉu, nh÷ng xu h−íng tiÒm Èn vµ h÷u Ých) trong c¬ së d÷ liÖu lµ

rÊt cÇn thiÕt vµ lµ mét qu¸ tr×nh gåm nhiÒu giai ®o¹n, trong ®ã giai ®o¹n khai ph¸ d÷

liÖu lµ mét giai ®o¹n chÝnh yÕu nhÊt (môc 1.1.1). Trong c¸c c¬ së d÷ liÖu ®å sé, c¸c

ph−¬ng ph¸p khai ph¸ d÷ liÖu (®iÓn h×nh lµ ph©n líp, ph©n côm) cho phÐp ph¸t hiÖn

®−îc c¸c mÉu tiÒm Èn vµ ®¸nh gi¸ gi¸ trÞ cña chóng mét c¸ch tù ®éng trong mét

kho¶ng thêi gian nhanh nhÊt ®Ó hç trî cho ng−êi sö dông.

Thùc hiÖn khai ph¸ d÷ liÖu trªn c¸c hÖ thèng víi d÷ liÖu lín, trªn c¸c hÖ

thèng ph©n t¸n, viÖc nghiªn cøu vµ ®Ò xuÊt c¸c thuËt to¸n khai ph¸ d÷ liÖu song

song trong c¸c m« h×nh song song lµ rÊt cã ý nghÜa. Tïy thuéc vµo c¬ së d÷ liÖu

thùc tÕ, viÖc lùa chän c¸ch thøc song song ®Ó song song hãa thuËt to¸n khai ph¸ d÷

liÖu tuÇn tù lµ rÊt quan träng (môc 1.2.2), nã ¶nh h−ëng trùc tiÕp tíi gi¸ thµnh thùc

hiÖn viÖc khai ph¸ d÷ liÖu. Mét sè m« h×nh chi phÝ h×nh thøc cho khai ph¸ d÷ liÖu

song song ®· ®−îc tæng kÕt (môc 1.2.3).

-32-

Ch−¬ng II. LuËt kÕt hîp theo tiÕp cËn lý thuyÕt tËp th«

II.1. kh¸i niÖm LuËt kÕt hîp vµ mét sè c«ng nghÖ ph¸t hiÖn

II.1.1. LuËt kÕt hîp

Ph¸t hiÖn luËt kÕt hîp lµ sù khai ph¸ d÷ liÖu kh«ng ®−îc ®Þnh h−íng hoÆc

kh«ng cã gi¸m s¸t trªn d÷ liÖu cã ®é dµi thay ®æi, nã cho ra c¸c kÕt qu¶ râ rµng vµ

dÔ hiÓu. Môc ®Ých cña khai ph¸ luËt kÕt hîp lµ t×m tÊt c¶ c¸c tËp con c¸c ®èi t−îng

hoÆc thuéc tÝnh xuÊt hiÖn th−êng xuyªn trong nhiÒu giao dÞch hoÆc b¶n ghi trong c¬

së d÷ liÖu, thªm vµo ®ã lµ rót ra c¸c luËt vÒ mét tËp con ®èi t−îng cã ¶nh h−íng tíi

sù xuÊt hiÖn cña tËp con c¸c ®èi t−îng kh¸c nh− thÕ nµo [15].

MÆc dï ph¸t hiÖn luËt kÕt hîp cã c¸ch ®Æt bµi to¸n ®¬n gi¶n, nã ®ßi hái l−îng

tÝnh to¸n vµ truy xuÊt d÷ liÖu rÊt lín. Khi d÷ liÖu t¨ng lªn c¶ vÒ sè h−íng (sè c¸c

thuéc tÝnh) vµ kÝch th−íc (sè giao dÞch), mét trong nh÷ng tÝnh chÊt cÇn thiÕt cña

ph¸t hiÖn luËt kÕt hîp lµ kh¶ n¨ng më réng ®−îc: kh¶ n¨ng xö lý kho d÷ liÖu rÊt lín.

C¸c thuËt to¸n tuÇn tù kh«ng thÓ cho kh¶ n¨ng nµy trong c¸c c¬ së d÷ liÖu lín. V×

vËy ta ph¶i dùa vµo tÝnh to¸n song song vµ ph©n t¸n hiÖu suÊt cao.

TËp phæ biÕn lµ c¬ së ®Ó t¹o c¸c luËt kÕt hîp [4]. Chóng ta xem xÐt mét vÝ dô

khai ph¸ luËt kÕt hîp. Cho mét tËp c¸c thuéc tÝnh I = {I1, I2,..., Im}, mét giao dÞch T

®−îc ®Þnh nghÜa lµ mét tËp con bÊt kú c¸c thuéc tÝnh trong I. Gi¶ sö c¬ së d÷ liÖu D

lµ mét tËp n giao dÞch, mçi giao dÞch ®−îc g¸n mét ®Þnh danh giao dÞch duy nhÊt

TID. Giao dÞch T lµ hç trî mét tËp X ⊆ I nÕu nã chøa tÊt c¶ c¸c thuéc tÝnh trong X,

tøc lµ X ⊆ T. §é hç trî cña mét tËp thuéc tÝnh X, ký hiÖu σ(X), lµ tØ lÖ cña tÊt c¶ c¸c

giao dÞch trong D hç trî X.

-33-

§Þnh nghÜa 2.1 (TËp phæ biÕn)

TËp X ⊆ I ®−îc gäi lµ tËp phæ biÕn nÕu cã σ(X) ≥ smin víi smin lµ ®é hç trî

tèi thiÓu cho tr−íc.

Mét tËp X cã lùc l−îng k = |X| ®−îc gäi lµ k-itemset. Cã ba tÝnh chÊt quan

träng cña c¸c tËp phæ biÕn, ®ã lµ:

- NÕu A ⊆ B víi A, B lµ c¸c tËp thuéc tÝnh th× σ(A) > σ(B), bëi tÊt c¶ c¸c giao

dÞch trong D hç trî B th× ®Òu ph¶i hç trî A.

- TËp cha cña mét tËp kh«ng phæ biÕn lµ tËp kh«ng phæ biÕn: NÕu tËp thuéc

tÝnh A kh«ng ®ñ ®é hç trî, tøc lµ σ(A) ≤ smin th× mäi tËp B chøa A còng sÏ

kh«ng phæ biÕn, bëi v× σ(B) ≤ σ(A) ≤ smin.

- TËp con cña tËp phæ biÕn lµ tËp phæ biÕn: NÕu tËp thuéc tÝnh B lµ phæ biÕn

trong D, tøc lµ σ(B) ≥ smin, th× mäi tËp con A cña B còng sÏ lµ phæ biÕn, bëi

σ(A) ≥ σ(B) ≥ smin.

Mét tËp phæ biÕn lµ cùc ®¹i nÕu nã kh«ng lµ tËp con cña bÊt kú tËp phæ biÕn nµo

kh¸c. Víi kh¸i niÖm vµ c¸c tÝnh chÊt nªu trªn cña tËp phæ biÕn, ng−êi ta ®−a ra kh¸i

niÖm luËt kÕt hîp nh− sau ®©y.

§Þnh nghÜa 2.2 (LuËt kÕt hîp)

Mét luËt kÕt hîp lµ mét biÓu thøc R: X → Y, víi X vµ Y lµ c¸c tËp thuéc

tÝnh kh«ng giao nhau X ∩ Y = ∅ vµ Y ≠ ∅.

§Þnh nghÜa 2.3 (§é hç trî vµ ®é tin cËy cña luËt)

§ç hç trî cña luËt lµ x¸c suÊt cña mét giao dÞch chøa c¶ X vµ Y: σ(X∪Y).

§é tin cËy cña mét luËt lµ x¸c suÊt cã ®iÒu kiÖn ®Ó mét giao dÞch chøa Y,

nÕu nã ®· chøa X, vµ ®−îc tÝnh bëi:

-34-

T

( Yp

)

)

=

⊆

⊆

T

=

=

XT |

( α R

)

( Yp

)

⊆∧⊆ X T ( ) Xp ⊆ T

( ∪ σ X Y )X ( σ

§é hç trî cña mét luËt lµ tÇn suÊt nã cã thÓ x¶y ra, trong khi ®é tin cËy cña

luËt cho biÕt luËt ®ã ®¸ng tin ra sao. Mét luËt lµ thÝch hîp nÕu nã cã ®ñ ®é hç trî vµ

®é tin cËy: σ(R) ≥ smin (luËt phæ biÕn) vµ α(R) ≥ cmin (luËt m¹nh), ®iÒu nµy chØ x¶y ra

nÕu c¶ vÕ tr¸i vµ vÕ ph¶i cña luËt ®ã lµ c¸c tËp phæ biÕn.

Ph¸t hiÖn luËt kÕt hîp liªn quan tíi viÖc t×m ra tÊt c¶ c¸c luËt kÕt hîp trong c¬

së d÷ liÖu cã ®é hç trî > smin vµ cã ®é tin cËy > cmin (c¸c luËt phæ biÕn vµ m¹nh).

C«ng viÖc nµy gåm hai b−íc:

1. T×m tÊt c¶ c¸c tËp thuéc tÝnh phæ biÕn cã ®é hç trî tèi thiÓu. Kh«ng gian t×m

kiÕm ®Ó liÖt kª tÊt c¶ c¸c tËp thuéc tÝnh phæ biÕn lµ 2m, víi m lµ sè thuéc tÝnh.

Tuy nhiªn, nÕu ta gi¶ sö chiÒu dµi giao dÞch lµ cã giíi h¹n, th× cã thÓ chØ ra

r»ng ph¸t hiÖn luËt kÕt hîp vÒ c¬ b¶n lµ tuyÕn tÝnh víi kÝch th−íc cña c¬ së

d÷ liÖu.

2. T¹o c¸c luËt m¹nh cã ®é tin cËy tèi thiÓu tõ c¸c tËp thuéc tÝnh phæ biÕn. Ta

t¹o vµ thö ®é tin cËy cña tÊt c¶ c¸c luËt cã d¹ng X\Y → Y, víi Y ⊂ X vµ X phæ

biÕn. V× ta ph¶i xÐt mçi tËp con cña X nh− lµ vÕ ph¶i cña luËt, ®é phøc t¹p cña

b−íc t¹o luËt lµ O(r.2l), víi r lµ sè tËp thuéc tÝnh phæ biÕn, l lµ kÝch th−íc cña

tËp phæ biÕn lín nhÊt.

C¸c tÝnh chÊt cña luËt kÕt hîp:

- Kh«ng cã phÐp hîp c¸c luËt: NÕu X → Z vµ Y → Z, kh«ng cã nghÜa lµ X ∪ Y

→ Z. XÐt tr−êng hîp X ∩ Y = ∅, mét giao dÞch trong D hç trî Z khi vµ chØ

khi nã hç trî hoÆc X, hoÆc Y. §é hç trî cña X ∪ Y lµ b»ng 0, vµ do ®ã ®é tin

cËy cña X ∪ Y → Z lµ b»ng 0%.

-35-

- PhÐp t¸ch c¸c luËt: NÕu X ∪ Y → Z thÝch hîp, c¸c luËt X → Z vµ Y → Z cã

thÓ kh«ng thÝch hîp. VÝ dô trong tr−êng hîp Z chØ xuÊt hiÖn khi c¶ X vµ Y

xuÊt hiÖn, tøc lµ σ(X∪Y) = σ(Z), nÕu X vµ Y cã ®é hç trî kh¸ lín so víi X∪Y

th× hai luËt t¹o thµnh sÏ kh«ng cã ®ñ ®é tin cËy. Tr−êng hîp ng−îc l¹i: X →

Y∪Z ⇒ X → Y ∧ X → Z l¹i ®óng, bëi σ(XY) ≥ σ(XYZ) vµ σ(XZ) ≥ σ(XYZ), do

®ã ®é hç trî vµ ®é tin cËy cña luËt nhá h¬n ®Òu t¨ng so víi luËt ban ®Çu.

- Kh«ng cã tÝnh chÊt b¾c cÇu: NÕu X → Y vµ Y → Z, ta kh«ng thÓ suy ra X →

Z. VÝ dô trong tr−êng hîp T(X) ⊂ T(Y) ⊂ T(Z), víi T(X) lµ tËp c¸c giao dÞch

hç trî X, ... vµ ®é tin cËy tèi thiÓu lµ cmin. Gi¶ sö α(X → Y) = α(Y → Z) = cmin,

min

< cmin (v× cmin <

dùa trªn c¸c gi¸ trÞ ®é hç trî t−¬ng ®èi ta cã α(X → Z) = c2

1), nh− thÕ X → Z kh«ng cã ®ñ ®é tin cËy vµ do ®ã kh«ng thÝch hîp.

II.1.2. Mét sè c«ng nghÖ ph¸t hiÖn luËt kÕt hîp tuÇn tù [16]

Kh«ng gian t×m kiÕm luËt kÕt hîp tuÇn tù cã thÓ ®−îc thiÕt ®Æt theo nh÷ng

c¸ch d−íi ®©y [17].

(cid:131) T×m kiÕm tõ d−íi lªn/ T×m kiÕm lai

Trong ph¸t hiÖn luËt kÕt hîp cã sö dông quan hÖ tËp con ⊆ ®Þnh nghÜa mét

thø tù bé phËn trªn tËp c¸c itemset. Quan hÖ nµy lµ ®¬n ®iÖu so víi ®é hç trî σ(X).

ThuËt to¸n ph¸t hiÖn luËt kÕt hîp kh¸c víi c¸ch t×m kiÕm trong m¹ng c¸c itemset

kÕt nèi bëi quan hÖ tËp con. HÇu hÕt c¸c tiÕp cËn sö dông c¸ch t×m kiÕm theo møc

hoÆc t×m-tõ-d−íi-lªn trong m¹ng ®Ó liÖt kª c¸c itemset phæ biÕn. NÕu dù ®o¸n lµ cã

itemset dµi, c¸ch tiÕp cËn trªn-xuèng nguyªn thñy cã thÓ ®−îc −a dïng h¬n. Ng−êi

ta còng dïng c¸ch t×m kiÕm lai, kÕt hîp c¶ t×m-tõ-trªn-xuèng vµ t×m-tõ-d−íi-lªn.

-36-

(cid:131) T¹o øng viªn theo c¸ch ngÉu nhiªn/ T¹o øng viªn ®Çy ®ñ

C¸c thuËt to¸n ph¸t hiÖn luËt kÕt hîp cã thÓ kh¸c nhau trong c¸ch t¹o øng

viªn míi. Mét t×m kiÕm ®Çy ®ñ ®¶m b¶o r»ng ta cã thÓ t¹o vµ thö tÊt c¶ c¸c tËp con

phæ biÕn. ë ®©y, ®Çy ®ñ kh«ng cã nghÜa lµ t×m ®Õn kiÖt søc, ta cã thÓ tØa bít ®Ó h¹n

chÕ c¸c nh¸nh v« Ých trong kh«ng gian t×m kiÕm. Trong c¸ch t¹o pháng ®o¸n, tÝnh

®Çy ®ñ bÞ mÊt ®i cho môc ®Ých t¨ng tèc. T¹i mçi b−íc, nã chØ kiÓm tra mét sè h¹n

chÕ c¸c "nh¸nh tèt". Còng cã thÓ t×m kiÕm ngÉu nhiªn ®Ó ®Þnh vÞ itemset phæ biÕn

cùc ®¹i.

(cid:131) LiÖt kª tÊt c¶ c¸c itemset/ LiÖt kª c¸c itemset phæ biÕn cùc ®¹i

C¸c thuËt to¸n ph¸t hiÖn luËt kÕt hîp kh¸c nhau phô thuéc vµo viÖc chóng t¹o

ra tÊt c¶ c¸c tËp con phæ biÕn hay chØ mét sè tËp con phæ biÕn cùc ®¹i. X¸c ®Þnh c¸c

tËp con cùc ®¹i lµ nhiÖm vô cèt lâi, v× viÖc rµ quÐt l¹i c¬ së d÷ liÖu cã thÓ t¹o ra tÊt

c¶ c¸c tËp con kh¸c. Tuy nhiªn, ®a sè c¸c thuËt to¸n ®Òu liÖt kª tÊt c¶ c¸c tËp con

phæ biÕn.

(cid:131) Tr×nh bµy d÷ liÖu theo hµng/theo cét

HÇu hÕt c¸c thuËt to¸n ph¸t hiÖn luËt kÕt hîp ®Òu sö dông c¸ch tr×nh bµy d÷

liÖu theo hµng ngang, l−u mçi ®Þnh danh giao dÞch cña kh¸ch cïng c¸c môc cã trong

giao dÞch ®ã. Mét sè ph−¬ng ph¸p còng dïng c¸ch thÓ hiÖn d÷ liÖu theo chiÒu däc,

kÕt hîp víi mçi môc X mét danh s¸ch c¸c ®Þnh danh giao dÞch chøa nã.

i. ThuËt to¸n Apriori - do Rakesh Agrawal vµ céng sù ®Ò xuÊt

§©y lµ mét trong c¸c thuËt to¸n ph¸t hiÖn luËt kÕt hîp tèt nhÊt. Nã còng lµ

nÒn t¶ng cho hÇu hÕt c¸c thuËt to¸n song song. Apriori sö dông c¸ch t×m kiÕm ®Çy

®ñ tõ d−íi lªn trong d÷ liÖu tr×nh bµy theo chiÒu ngang vµ liÖt kª tÊt c¶ c¸c itemset

phæ biÕn. Lµ mét thuËt to¸n lÆp, Apriori ®Õm c¸c itemset cã chiÒu dµi cô thÓ trong

c¬ së d÷ liÖu. Qu¸ tr×nh b¾t ®Çu víi viÖc duyÖt tÊt c¶ c¸c giao dÞch trong c¬ së d÷

-37-

liÖu vµ tÝnh c¸c itemset phæ biÕn. TiÕp theo, t¹o mét tËp c¸c øng viªn 2-itemset phæ

biÕn tõ c¸c itemset phæ biÕn. Mét lÇn duyÖt c¬ së d÷ liÖu n÷a ®Ó tÝnh ®é hç trî cña

chóng. C¸c 2-itemset phæ biÕn ®−îc duy tr× cho lÇn sau. Qu¸ tr×nh lÆp l¹i tíi khi liÖt

kª hÕt c¸c itemset phæ biÕn. ThuËt to¸n cã 3 b−íc chÝnh:

- T¹o c¸c øng viªn cã ®é dµi k tõ c¸c (k-1)-ietmset phæ biÕn b»ng c¸ch tù

kÕt hîp trªn Fk-1

- TØa bít c¸c øng viªn cã Ýt nhÊt mét tËp con kh«ng phæ biÕn

- DuyÖt tÊt c¶ c¸c giao dÞch ®Ó cã ®é hç trî cña c¸c øng viªn. Apriori l−u

c¸c øng viªn trong mét c©y b¨m (hash tree) ®Ó ®Õm nhanh ®é hç trî.

Trong mét c©y b¨m, c¸c itemset ®−îc l−u t¹i c¸c l¸, c¸c nót trong chøa

c¸c b¶ng b¨m (trén bëi c¸c môc) ®Î ®Þnh h−íng t×m kiÕm c¸c øng viªn.

ii. ThuËt to¸n tØa vµ b¨m ®éng (Dynamic Hashing & Pruning - DHP) - do Jong

Soo Park vµ céng sù ®Ò xuÊt

ThuËt to¸n DHP më réng c¸ch tiÕp cËn Apriori b»ng c¸ch dïng b¶ng trén ®Ó

tÝnh tr−íc ®é hç trî xÊp xØ cho c¸c 2-itemset trong qu¸ tr×nh lÆp. LÇn lÆp thø hai chØ

cÇn tÝnh c¸c øng viªn trong c¸c phÇn tö b¨m cã ®é hç trî tèi thiÓu. Kü thuËt dïng

hµm b¨m nµy cã thÓ lo¹i ®i rÊt tèt nh÷ng cÆp øng viªn mµ cuèi cïng sÏ lµ kh«ng phæ

biÕn.

iii. ThuËt to¸n ph©n ho¹ch (Partition) - do Ashok vµ céng sù ®Ò xuÊt

ThuËt to¸n nµy ph©n chia hîp lý c¬ së d÷ liÖu theo chiÒu ngang thµnh c¸c

phÇn kh«ng giao nhau. Mçi phÇn ®−îc ®äc vµ t¹o ra cho mçi item c¸c danh s¸ch

theo hµng däc c¸c ®Þnh danh giao dÞch cã chøa item ®ã (tidlist). Sau ®ã t×m c¸c

itemset phæ biÕn ®Þa ph−¬ng qua phÇn giao cña c¸c tidlist. C¸c itemset phæ biÕn t¹i

mçi phÇn sÏ tËp hîp l¹i ®Ó t¹o mét tËp c¸c øng viªn toµn phÇn. ThuËt to¸n duyÖt lÇn

thø hai qua tÊt c¶ c¸c phÇn vµ cã ®−îc con sè toµn côc cña mäi øng viªn qua phÇn

giao cña c¸c tidlist.

-38-

iv. C¸c thuËt to¸n SEAR & SPEAR - do Andreas Muller ®Ò xuÊt

ThuËt to¸n SEAR (Sequential Efficial Association Rules - Ph¸t hiÖn tuÇn tù

luËt kÕt hîp mét c¸ch hiÖu qu¶) gièng hÖt Apriori, ngo¹i trõ viÖc nã l−u c¸c øng

viªn trong mét c©y tiÒn tè thay v× mét c©y b¨m. Trong mét c©y tiÒn tè, mçi c¹nh

®−îc g¸n nh·n bëi c¸c tªn thuéc tÝnh, c¸c tiÒn tè phæ biÕn ®−îc biÓu diÔn bëi c¸c

nh¸nh c©y, vµ c¸c hËu tè duy nhÊt ®−îc l−u t¹i c¸c l¸. Ngoµi ra, SEAR dïng mét

c¸ch tèi −u hãa gép nhiÒu lÇn duyÖt, trong ®ã nã t×m øng viªn cho nhiÒu l−ît nÕu

c¸c øng viªn ®ã võa trong bé nhí.

ThuËt to¸n SPEAR (SEAR with Partition technique) t−¬ng tù víi SEAR

nh−ng nã dïng kü thuËt ph©n ho¹ch, nã lµ b¶n sao cña SEAR nh−ng kh«ng dïng

®Þnh danh giao dÞch. SPEAR dïng d÷ liÖu ®Þnh d¹ng theo hµng ngang, nã duyÖt hai

lÇn: tr−íc hÕt tËp trung vµo c¸c itemset phæ biÕn tiÒm n¨ng, sau ®ã tÝnh ®é hç trî

toµn phÇn cña chóng.

Môc tiªu cña Muller lµ ®¸nh gi¸ nh÷ng lîi Ých néi t¹i cña viÖc ph©n ho¹ch,

bÊt kÓ ®Þnh ®Þnh d¹ng d÷ liÖu ®−îc dïng. ¤ng kÕt luËn r»ng ph©n ho¹ch kh«ng gióp

®−îc g× do ph¶i xø lý thªm nhiÒu ph©n ho¹ch vµ do ph©n ho¹ch t×m ra nhiÒu itemset

phæ biÕn ®Þa ph−¬ng nh−ng kh«ng phæ biÕn toµn phÇn. SEAR −u viÖt h¬n do nã thùc

hiÖn c¶ viÖc gép c¸c lÇn duyÖt.

v. ThuËt to¸n ®Õm itemset ®éng (Dynamic Itemset Counting - DIC) do Sergey

Brin vµ céng sù ®Ò xuÊt

§©y lµ sù tæng qu¸t hãa cña thuËt to¸n Apriori. D÷ liÖu ®−îc chia lµm p phÇn

cã kÝch th−íc b»ng nhau ®Ó mçi phÇn võa trong bé nhí. Víi phÇn 1, DIC tËp hîp ®é

hç trî cña tõng item. C¸c item phæ biÕn ®Þa ph−¬ng (chØ trong phÇn nµy) t¹o nªn c¸c

øng viªn øng viªn 2-itemset. Sau ®ã DIC ®äc phÇn 2, cã ®é hç trî cña tÊt c¶ c¸c øng

viªn hiÖn t¹i - tøc lµ c¸c item ®¬n lÎ vµ c¸c øng viªn 2-itemset. Qu¸ tr×nh nµy lÆp l¹i

-39-

cho c¸c phÇn cßn l¹i. DIC b¾t ®Çu ®Õm sè øng viªn k-itemset trong khi xö lý phÇn k

trong lÇn duyÖt c¬ së d÷ liÖu lÇn ®Çu tiªn. Sau khi xö lý hÕt phÇn cuèi cïng p, DIC

quay trë l¹i phÇn 1. §é hç trî toµn phÇn cña øng viªn ®−îc tÝnh mçi khi qu¸ tr×nh

quay l¹i vµ ®¹t ®Õn phÇn n¬i nã ®−îc tÝnh lÇn ®Çu. DIC cã hiÖu qu¶ trong viÖc gi¶m

sè lÇn quÐt c¬ së d÷ liÖu nÕu hÇu hÕt c¸c phÇn lµ ®ång nhÊt (cã sù ph©n bè c¸c

itemset phæ biÕn gièng nhau). NÕu d÷ liÖu kh«ng ®ång nhÊt, DIC cã thÓ t¹o ra nhiÒu

sè liÖu sai - tøc c¸c itemset phæ biÕn ®Þa ph−¬ng nh−ng kh«ng phæ biÕn toµn phÇn -

vµ duyÖt c¬ së d÷ liÖu nhiÒu h¬n Apriori. DIC ®−a ra mét kü thuËt ph©n ho¹ch ngÉu

nhiªn ®Ó gi¶m ®é lÖch cña c¸c phÇn d÷ liÖu.

vi. C¸c thuËt to¸n Eclat, MaxEclat, Clique, MaxClique - do Mohammed J.

Zaki vµ céng sù ®Ò xuÊt

§©y lµ mét c¸ch thiÕt kÕ hoµn toµn kh¸c m« t¶ c¸c thuËt to¸n dùa trªn c¸c líp

t−¬ng ®−¬ng. C¸c ph−¬ng ph¸p nµy sö dông ®Þnh d¹ng d÷ liÖut theo cét däc, t×m

kiÕm ®Çy ®ñ vµ kÕt hîp gi÷a c¸ch t×m kiÕm lai vµ t×m kiÕm tõ d−íi lªn, chóng t¹o ra

mét hçn hîp c¸c itemset phæ biÕn cùc ®¹i vµ kh«ng cùc ®¹i. Lîi thÕ chÝnh cña viÖc

dïng ®Þnh d¹ng d÷ liÖu theo cét däc lµ ta cã thÓ x¸c ®Þnh ®é hç trî cña bÊt kú k-

itemset nµo, ®¬n gi¶n b»ng c¸ch giao c¸c danh s¸ch ®Þnh danh giao dÞch tidlist cña

hai tËp con kÝch th−íc (k-1) ®Çu tiªn cã chung phÇn tiÒn tè (c¸c itemset ph¸t sinh).

C¸c ph−¬ng ph¸p nµy chia kh«ng gian t×m kiÕm lín thµnh c¸c phÇn nhá, ®éc lËp vµ

cã thÓ qu¶n lý ®−îc. C¸c phÇn nµy cã thÓ ®−îc xö lý trong bé nhí qua c¸c líp t−¬ng

®−¬ng dùa trªn c¸c nhãm hoÆc tiÒn tè; c¸ch tiÕp cËn dùa trªn nhãm t¹o ra nhiÒu líp

nhá h¬n. Mçi líp lµ ®éc lËp theo nghÜa chóng cã ®Çy ®ñ th«ng tin ®Ó t¹o tÊt c¶ c¸c

itemset phæ biÕn cã cïng tiÒn tè.

Trong bèn thuËt to¸n nµy, Eclat sö dông c¸c líp dùa trªn tiÒn tè vµ t×m kiÕm

tõ d−íi lªn, MaxEclat sö dông c¸c líp dùa trªn tiÒn tè vµ t×m kiÕm lai, Clique dïng

c¸c líp dùa trªn nhãm vµ t×m kiÕm tõ d−íi lªn, MaxClique dïng c¸c líp dùa trªn

-40-

nhãm vµ t×m kiÕm lai. C¸ch tiÕp cËn tèt nhÊt lµ MaxClique, nã tèt h¬n c¶ Apriori vµ

Eclat.

II.2. LuËt kÕt hîp theo tiÕp cËn lý thuyÕt tËp th«

II.2.1. TËp th« [14]

Lý thuyÕt tËp th« ®−îc ph¸t triÓn bëi Zdzislaw Pawlak vµo ®Çu nh÷ng n¨m

1980. Môc ®Ých chÝnh cña ph©n tÝch tËp th« lµ suy dÉn ra c¸c xÊp xØ cña c¸c kh¸i

niÖm, nã cung cÊp c¸c c«ng cô to¸n häc cho viÖc ph¸t hiÖn c¸c mÉu Èn chøa trong

d÷ liÖu vµ ®−îc dïng ®Ó lùa chän thuéc tÝnh, rót gän d÷ liÖu, sinh luËt quyÕt ®Þnh vµ

rót ra c¸c mÉu.

Gäi cÆp A= (U, R) lµ mét kh«ng gian xÊp xØ, víi U lµ mét tËp h÷u h¹n, vµ R

lµ tËp c¸c líp t−¬ng ®−¬ng trªn U. Mçi phÇn tö cña tËp R ®−îc gäi lµ mét tËp c¬ së

(hay tËp nguyªn tö). Mét tËp cã thÓ ®Þnh nghÜa trong A lµ thu ®−îc nhê ¸p dông mét

sè h÷u h¹n c¸c phÐp hîp (∪) trªn R. Gäi R* lµ hä c¸c tËp con cña R. Khi ®ã, R* t¹o

mét kh«ng gian t«p« TA = (U, R*). Ta gäi mçi phÇn tö cña U lµ mét ®èi t−îng. Mét

kh¸i niÖm ®¸ng quan t©m X lµ mét tËp con cña U. Mét tËp cã thÓ ®Þnh nghÜa trong A

chøa X, ClA(X) ®−îc gäi lµ tËp ®ãng (cßn gäi lµ tËp trªn) cña X trong A. T−¬ng tù, tËp

cã thÓ ®Þnh nghÜa lín nhÊt trong A ®−îc chøa bëi X, IntA(X), ®−îc gäi lµ tËp trong

U

ClA(X) - X

U/R

IntA(X)

tËp X

(hay cßn gäi lµ tËp d−íi) cña X trong A.

-41-

§Þnh nghÜa 2.4 (TËp m« t¶ ®−îc vµ tËp th«)

TËp X lµ m« t¶ ®−îc trong A nÕu víi mét sè tËp Y ∈ R*, X b»ng hîp cña tÊt

c¶ c¸c tËp trong Y. Ng−îc l¹i, X ®−îc gäi lµ tËp th« hay tËp kh«ng m« t¶

®−îc.

Ta muèn t¹o mét thuËt to¸n quyÕt ®Þnh trong A, ký hiÖu lµ DA(X), sao cho víi

mçi x ∈ U nã cho mét trong 3 c©u tr¶ lêi: (a) x n»m trong X, (b) x kh«ng n»m trong

X, (c) kh«ng biÕt. Ta ®Þnh nghÜa c¸c tËp cña X trong A t−¬ng øng víi mçi c©u tr¶ lêi:

- POSA(X) lµ tËp c¸c ®èi t−îng ®−îc DA(X) coi lµ mét phÇn tö cña kh¸i niÖm X;

- BNDA(X) lµ tËp c¸c ®èi t−îng mµ DA(X) cho c©u tr¶ lêi "kh«ng biÕt";

- NEGA(X) lµ tËp c¸c ®èi t−îng kh«ng ®−îc DA(X) coi lµ phÇn tuwr cña X;

Theo ®Þnh nghÜa trªn, dÔ thÊy NEGA(X) = U - (POSA(X) ∪ BNDA(X)). Nãi c¸ch kh¸c,

thuËt to¸n quyÕt ®Þnh dïng c¸c luËt sau ®Ó tr¶ lêi c©u hái x ∈ X hay kh«ng:

i. x ∈ POSA(X) ⇒ x ∈ X,

ii. x ∈ BNDA(X) ⇒ kh«ng biÕt,

iii. x ∈ NEGA(X) ⇒ x ∉ X

Cã hai ph−¬ng ph¸p xÊp xØ ®−îc ®Þnh nghÜa trong kh«ng gian xÊp xØ ®¹i sè:

A(X) = IntA(X) vµ

- XÊp xØ d−íi: POSl

A(X) = ClA(X)

- XÊp xØ trªn: POSu

=

Trong c¶ hai ph−¬ng ph¸p, vïng biªn cña kh¸i niÖm X b»ng ClA(X) - POSA(X). §é

( X

)

µ A

| |

) | ) |

( Int A A ( XCl A

m¬ hå ®−îc biÓu diÔn bëi ®é ®o chÝnh x¸c:

§Æt F = {X1, X2,..., Xk}, víi Xi ∈U, lµ mét ph©n lo¹i cña U. C¸c tËp trong vµ tËp

®ãng cña F trong A ®−îc ®Þnh nghÜa t−¬ng øng lµ c¸c hä:

IntA(F) = {IntA(X1), IntA(X2),..., IntA(Xn)}

-42-

vµ ClA(F) = {ClA(X1), ClA(X2),..., ClA(Xn)}

Mét bµi to¸n ph©n líp ®−îc m« t¶ nh− viÖc t¹o mét thuËt to¸n quyÕt ®Þnh

DA(R, F) ®Ó liªn kÕt c¸c tËp cã thÓ ®Þnh nghÜa víi c¸c kh¸i niÖm. NÕu DA(R, F) lµ

mét quan hÖ th× nã ®−îc gäi lµ mét thuËt to¸n quyÕt ®Þnh kh«ng nhÊt qu¸n, ng−îc

l¹i nã lµ mét thuËt to¸n quyÕt ®Þnh nhÊt qu¸n. Do POSA(R, F) = ∪x∈FPOSA(R, X) nªn

sù më réng mét ph−¬ng ph¸p xÊp xØ cho bµi to¸n ph©n líp lµ dÔ hiÓu. T−¬ng tù, ®é

k

Int

|

|

( X

)

A

i

1

i

( F

)

β A

|

|

)

( XCl A

i

∑ == k ∑

i

1 =

chÝnh x¸c ph©n líp b»ng:

Trong bµi to¸n ph©n líp, mét ®é ®o thø hai th−êng ®−îc nãi tíi, ®ã lµ chÊt

k

Int

|

|

( x

)

A

i

∑ 1 i ==

( F

)

η A

k

U

|

|

∑

i

1 =

l−îng cña ph©n lo¹i F trong A, ®ùoc cho bëi c«ng thøc:

NÕu ηA(F) = βA(F) th× ph©n lo¹i nµy®−îc gäi lµ cã thÓ ®Þnh nghÜa, ng−îc l¹i

nã ®−îc gäi lµ ph©n lo¹i cã thÓ ®Þnh nghÜa th«.

II.2.2 LuËt kÕt hîp theo tiÕp cËn lý thuyÕt tËp th«

C¸c c¬ së d÷ liÖu lu«n chøa rÊt nhiÒu thuéc tÝnh, mét sè thuéc tÝnh cã thÓ lµ

d− thõa vµ kh«ng cÇn thiÕt cho qu¸ tr×nh ph¸t hiÖn luËt. NÕu c¸c thuéc tÝnh d− thõa

nµy kh«ng bÞ lo¹i bít th× kh«ng chØ thêi gian ph¸t hiÖn luËt t¨ng lªn, mµ chÊt l−îng

cña c¸c luËt t×m ®−îc còng kh«ng cao.

§Ó sö dông lý thuyÕt tËp th«, ta coi c¬ së d÷ liÖu lµ mét hÖ quyÕt ®Þnh [16]:

T = (U, A ∪ {d}), trong ®ã

-43-

U lµ tËp h÷u h¹n kh¸c rçng c¸c ®èi t−îng.

A lµ tËp h÷u h¹n kh¸c rçng c¸c thuéc tÝnh sao cho a: U → Va víi ∀a ∈A,

Va ®−îc gäi lµ tËp gi¸ trÞ cña a, c¸c phÇn tö cña A ®−îc gäi lµ c¸c thuéc

tÝnh ®iÒu kiÖn.

d ∉ A lµ thuéc tÝnh quyÕt ®Þnh.

VÝ dô: HÖ quyÕt ®Þnh:

B×nh th−êng

u2 Cã

Cao

Cã

Cã

u3 Cã

B×nh th−êng

Cã

Cã

u4 Kh«ng

Cao

Cã

Kh«ng

u5 Kh«ng

B×nh th−êng Kh«ng

Kh«ng

u6 Cã

RÊt cao

Cã

Cã

u7 Kh«ng

Cao

Cã

Cã

U §au ®Çu NhiÖt ®é u1 Cã Mái c¬ Cã BÞ cóm Kh«ng

C¸c thuéc tÝnh ®iÒu kiÖn lµ §au ®Çu, NhiÖt ®é, Mái c¬ víi

V®au ®Çu={Kh«ng (0), Cã (1)},

VnhiÖt ®é={B×nh th−êng(0), Cao (1), RÊt cao (2)},

Vmái c¬= {Kh«ng (0), Cã (1)}

vµ thuéc tÝnh quyÕt ®Þnh lµ BÞ cóm víi VbÞ cóm ={ Kh«ng (0), Cã (1)}.

F(x) *-0-0 *-0-1 *-1-0 *-1-1 *-2-0 *-2-1 0-*-0 .....

0-0-0 1/2 1/3 .....

0-0-1 1/2

... ...

1-0-0 1/2

... ..... ..... ..... ..... ..... ..... ..... .....

1-2-1 1/2

B¶ng quyÕt ®Þnh t−¬ng øng cña nã lµ:

-44-

1-1-* 1-2-* ..... *-*-0 ..... 0-*-* 1-*-*

1/6 ..... 1/6

1/6

1/6 1/6

..... ..... ..... ..... ..... ..... .....

1/2 1/6

Gäi F(x) lµ c¸c ®èi t−îng cã thÓ (PI)

G(x) lµ c¸c bé sinh cã thÓ (PG)

if

PG

nÕu PIj ∈ PGi PI ∈

j

i

1 N

(

|

)

p

PI

PG

=

PG i

i

j

trong c¸c tr−êng hîp cßn l¹i

otherwise

⎧ ⎪ ⎨ ⎪ ⎩

N

=

lµ sè PI tháa m·n trong PGi

PG

i

k

k *

}

0 ∏ n [ ] { lPGl ∈ = |

−

→

=

G(x) → F(x) lµ quan hÖ x¸c suÊt gi÷a PI vµ PG:

)

( XS

) =→ Y

( Xs

( ) 1

( Xr

)Y )

)kPGs (

§é m¹nh cña luËt: víi ( Xs

N

PG

(

)

ins

k

=

=

=

p

PG

|

( Xs

)

( PGs

)

( PI

)

k

l

k

∑

rel _ N

l

PG

k

Nins_rel(PGk) lµ sè ®èi t−îng quan s¸t ®−îc lµ tháa m·n trong lÇn thø i

NÕu kh«ng sö dông tri thøc kinh nghiÖm:

BKF

PG

|

( PI

)

l

k

∑

l

p

PG

=

=

=

|

( Xs

)

( PGs

)

( PI

)

k

bk

l

k

∑

N

l

ins

rel

_

(

)X

−

N

N

( X

)

( YX ,

)

ins

rel

ins

class

_

_

NÕu sö dông tri thøc kinh nghiÖm:

( Xr

) =→ Y

N

)X (

ins

rel

_

Nins_class(X,Y) lµ sè ®èi t−îng thuéc líp Y trong sè c¸c ®èi t−îng tháa m·n X

§é nhiÔu ®−îc tÝnh b»ng:

-45-

Qu¸ tr×nh khai ph¸ trong b¶ng quyÕt ®Þnh cã thÓ ph¸t hiÖn ra c¸c ®èi t−îng

ch−a biÕt vµ nã dïng ®é m¹nh cña luËt ®Ó biÓu diÔn t−êng minh tÝnh kh«ng ch¾c

ch¾n cña luËt, bao gåm c¶ kh¶ n¨ng luËt dù ®o¸n c¸c ®èi t−îng cã thÓ.

§Ó chän ra c¸c luËt trong b¶ng quyÕt ®Þnh, ta dùa trªn c¸c tiªu chuÈn nh−:

- Chän c¸c luËt phñ cµng nhiÒu ®èi t−îng cµng tèt

- Chän c¸c luËt chøa cµng Ýt thuéc tÝnh cµng tèt, nÕu chóng phñ cïng sè ®èi

t−îng

- Chän c¸c luËt m¹nh h¬n, nÕu chóng cã cïng sè thuéc tÝnh ®iÒu kiÖn vµ

phñ cïng sè ®èi t−îng

C¸c thuéc tÝnh tham gia trong luËt cÇn ®−îc chän sao cho sè ®èi t−îng t¨ng

nhanh h¬n, nh»m cã tËp con c¸c thuéc tÝnh cµng nhá cµng tèt, vµ chóng nªn cã sè

gi¸ trÞ Ýt h¬n, ®Ó ®¶m b¶o sè ®èi t−îng do luËt nµy bao phñ cµng lín cµng tèt.

XÐt b¶ng c¬ së d÷ liÖu nªu trªn:

U

U §au ®Çu

§au ®Çu

NhiÖt ®é

Mái c¬

BÞ cóm ⊥ Cã Ko Ko Cã

u1 Cã u2 Cã u3 Cã u4 Ko u5 Cã u6 Cã u7 Ko

NhiÖt ®é Mái c¬ Cã BT Cã Cao Cã BT Ko Cao BT Cã RÊt cao Cã Cã Cao

u1’ Cã u2 Cã u4 Ko u6 Cã u7 Ko

Cã BT Cã Cao Ko Cao RÊt cao Cã Cã Cao

BÞ cóm Cã ⇒ Cã Cã Ko Ko Ko Cã

r(cã)(u1') = 1 - 2/3 = 0,33

r(kh«ng)(u1') = 1 - 1/3 = 0,67

§Æt TnhiÔu = 0 ⇒ r(cã)(u1') > TnhiÔu; r(kh«ng) (u1') > TnhiÔu vµ BÞ cóm(u1') = ⊥

u1’

u4

u6

u7

u2 NhiÖt ®é

u2 λ §au ®Çu, Mái c¬ NhiÖt ®é

λ

T¹o vÐct¬ ph©n biÖt cho u2:

T×m rót gän cho u2:

-46-

fT(u2) = (NhiÖt ®é) ∧ T ∧ (§au ®Çu ∨ Mái c¬) ∧ (NhiÖt ®é) ∧ T

= (NhiÖt ®é) ∧ (§au ®Çu ∨ Mái c¬)

= (§au ®Çu ∧ NhiÖt ®é) ∨ (NhiÖt ®é ∧ Mái c¬)

fT(u2) = (§au ®Çu ∧ NhiÖt ®é) ∨ (NhiÖt ®é ∧ Mái c¬)

{Cã ®au ®Çu, NhiÖt ®é cao} {NhiÖt ®é cao, Cã mái c¬}

({Cã ®au ®Çu, NhiÖt ®é cao} → BÞ cóm) cã

s({Cã ®au ®Çu, NhiÖt ®é cao}) = 0.5 vµ

r({Cã ®au ®Çu, NhiÖt ®é cao} → BÞ cóm) = 0 ⇒

S({Cã ®au ®Çu, NhiÖt ®é cao} → BÞ cóm) = (1 x 1/2) x (1-0) = 0.5

({NhiÖt ®é cao,Cã mái c¬} → BÞ cóm) cã

s({NhiÖt ®é cao, Cã mái c¬}) = 1 vµ

r({NhiÖt ®é cao,Cã mái c¬} → BÞ cóm) = 0 ⇒

S({NhiÖt ®é cao, Cã mái c¬} → BÞ cóm) = (2 x 1/2) x (1-0) = 1

T¹o luËt tõ u2:

u1’

u2

u7

u4 §au ®Çu, NhiÖt ®é, Mái c¬ §au ®Çu, Mái c¬

u4 u6 λ

λ Mái c¬

fT(u4) = (§au ®Çu ∨ NhiÖt ®é ∨ Mái c¬) ∧ (§au ®Çu ∨ Mái c¬) ∧ T ∧ T ∧ (Mái c¬)

= (Mái c¬)

T¹o vÐct¬ ph©n biÖt cho u4:

fT(u4) = (Mái c¬) {Kh«ng mái c¬}

({Kh«ng mái c¬} → Kh«ng bÞ cóm) cã

s(Kh«ng mái c¬) = 1/6 vµ

r({Kh«ng mái c¬} → Kh«ng bÞ cóm) = 0 ⇒

S({Kh«ng mái c¬} → Kh«ng bÞ cóm) = (1 x 1/6) x (1-0) = 0,167

T¹o luËt tõ u4:

-47-

u2:

{Cã ®au ®Çu, NhiÖt ®é cao} → BÞ cóm,

S = 0.5

S = 1

{NhiÖt ®é cao, Cã mái c¬} → BÞ cóm,

S = 0,167

u4:

{Kh«ng mái c¬} → Kh«ng bÞ cóm,

S = 0.25

u6:

{NhiÖt ®é rÊt cao} → Kh«ng bÞ cóm,

u7:

{Kh«ng ®au ®Çu, Cã mái c¬ } → BÞ cóm, S = 0.5

S = 1

{NhiÖt ®é cao, Cã mái c¬ } → BÞ cóm,

Sau khi t¹o luËt tõ tÊt c¶ c¸c ®èi t−îng ta cã:

u7

u2

§au ®Çu, NhiÖt ®é cao, Mái c¬

Kh«ng ®au ®Çu, NhiÖt ®é cao, Mái c¬

*, NhiÖt ®é cao, Mái c¬ Kh«ng ®au ®Çu, *, Mái c¬ Cã ®au ®Çu, NhiÖt ®é cao, *

1/2 1/3

1/2 1/2

{NhiÖt ®é cao, Cã mái c¬ } → BÞ cóm víi S = 1

{Kh«ng ®au ®Çu, Cã mái c¬} → BÞ cóm víi S = 1/2 phñ u7

{Cã ®au ®Çu, NhiÖt ®é cao} → BÞ cóm víi S = 1/2 phñ u2

Bé sinh thuéc líp BÞ cóm:

u7

u2

Cã ®au ®Çu, NhiÖt ®é rÊt cao, Cã mái c¬

Kh«ng ®au ®Çu, NhiÖt ®é cao, Kh«ng mái c¬

1/6

1/4

*, *, Kh«ng mái c¬ *, NhiÖt ®é rÊt cao, *

Kh«ng mái c¬ → Kh«ng bÞ cóm víi S = 1/6 phñ u4

NhiÖt ®é rÊt cao → Kh«ng bÞ cóm víi S = 1/4 phñ u6

Bé sinh thuéc líp Kh«ng bÞ cóm:

Nh− vËy víi ®é nhiÔu b»ng 0, tõ c¬ së d÷ liÖu trªn ta cã:

C¸c luËt ch¾c ch¾n:

Phñ c¸c ®èi t−îng

u4

Kh«ng mái c¬ → Kh«ng bÞ cóm víi S = 1/6

-48-

u6

NhiÖt ®é rÊt cao → Kh«ng bÞ cóm víi S = 1/4

u2, u7

{NhiÖt ®é cao, Cã mái c¬ } → BÞ cóm víi S = 1

C¸c luËt cã thÓ:

NhiÖt ®é b×nh th−êng → BÞ cóm víi S = (1/4)*(2/3)

Cã ®au ®Çu & NhiÖt ®é B×nh th−êng → BÞ cóm víi S = (1/2)*(2/3)

Cã ®au ®Çu & Cã mái c¬ → BÞ cóm víi S = (1/3)*(2/3)

NhiÖt ®é b×nh th−êng & Cã mái c¬ → BÞ cóm víi S = (1/2)*(2/3)

NÕu ®é nhiÔu kh¸c 0, gi¶ sö TnhiÔu = 0,5:

U

BÞ cóm

U

§au ®Çu

NhiÖt ®é

§au ®Çu

NhiÖt ®é

Mái c¬

BÞ cóm ⊥ Cã Ko Ko Cã

u1 Cã u1’ u3 Cã u5 Cã Cã Ko Cã Ko

u2 u4 u6 u7

Mái c¬ Cã BT Cã BT Cã BT Cã Cao Cao Ko RÊt cao Cã Cã Cao

Cã ⇒ u1’ Cã u2 Cã Cã u4 Ko Ko u6 Cã Cã u7 Ko Ko Ko Cã

Cã BT Cã Cao Ko Cao RÊt cao Cã Cã Cao

r(cã)(u1') = 1 - 2/3 = 0,33 < TnhiÔu vµ r(kh«ng)(u1’) = 1 - 1/3 = 0,67 > TnhiÔu ⇒ d(u1’) = Cã

u1’:

{NhiÖt ®é b×nh th−êng} → BÞ cóm,

S = 0,5

S = 0,5

u2:

{Cã ®au ®Çu, NhiÖt ®é cao} → BÞ cóm

S = 1

{NhiÖt ®é cao, Cã mái c¬} → BÞ cóm

S = 0,167

u4:

{Kh«ng mái c¬} → Kh«ng bÞ cóm

S = 0,25

u6:

{NhiÖt ®é rÊt cao} → Kh«ng bÞ cóm

S = 0,5

u7:

{Kh«ng ®au ®Çu, Cã mái c¬} → BÞ cóm

Khi ®ã c¸c luËt cã ®−îc tõ tÊt c¶ c¸c ®èi t−îng lµ:

-49-

{NhiÖt ®é cao, Cã mái c¬} → BÞ cóm

S = 1

...

1-2-1

0-0-* 0-1-* 0-*-1 0-*-*

0-0-0 1/2 1/6

0-0-1 1/2 1/3 1/6

0-1-0 1/2 1/6

0-1-1 1/2 1/3 1/6

0-2-0 1/6

0-2-1 1/3 1/6

NÕu sö dông tri thøc kinh nghiÖm, tõ b¶ng

víi tri thøc lµ Cã ®au ®Çu → Cã mái c¬, ch¾c ch¾n 100% ta sÏ cã ®é m¹nh cña c¸c

0-0-0

0-0-1

0-1-0

0-1-1

0-2-0

0-2-1

...

1-2-1

0-0-*

0

1

0-1-*

0

1

0-*-1

1/3

1/3

1/3

0-*-*

0

1/3

0

1/3

0

1/3

luËt thay ®æi nh− sau:

Trong [16], c¸c t¸c gi¶ ®· ®−a ra thuËt to¸n rót ra c¸c luËt tõ c¬ së d÷ liÖu cã

d¹ng b¶ng quyÕt ®Þnh.

ThuËt to¸n 2.1: T×m tËp tèi −u c¸c luËt [16]

Input: B¶ng quyÕt ®Þnh U gåm n ®èi t−îng, mèi ®èi t−îng u cã thÓ cã m

thuéc tÝnh.

Output: TËp tèi −u c¸c luËt cïng ®é m¹nh cña mçi luËt

Néi dung thuËt to¸n

B−íc 1: Coi c¸c ®èi t−îng víi cïng gi¸ trÞ cña c¸c thuéc tÝnh ®iÒu kiÖn nh−

mét ®èi t−îng, gäi lµ ®èi t−îng kÐp

B−íc 2: TÝnh ®é nhiÔu r cho mäi ®èi t−îng kÐp

B−íc 3: Chän mét ®èi t−îng u tõ U vµ tÝnh vec-t¬ kh«ng ph©n biÖt ®−îc cho u

-50-

B−íc 4: TÝnh tÊt c¶ c¸c rót gän cho ®èi t−îng u, sö dông hµm kh«ng ph©n biÖt

®−îc

B−íc 5: Rót ra c¸c luËt tõ c¸c rót gän cña ®èi t−îng u, tÝnh l¹i ®é m¹nh cña

mÉu cho mçi luËt

B−íc 6: Chän ra c¸c luËt tèt h¬n tõ c¸c luËt tÝnh ®−îc ë b−íc 5 b»ng c¸ch

chän ngÉu nhiªn

B−íc 7: U = U \ {u}. NÕu U ≠ ∅ th× quay l¹i b−íc 3, nÕu kh«ng chuyÓn sang

b−íc 8

B−íc 8: KÕt thóc nÕu sè luËt trong b−íc 6 cho mçi ®èi t−îng b»ng 1, ng−îc

l¹i t×m tËp luËt tèi thiÓu, chøa tÊt c¶ c¸c ®èi t−îng trong b¶ng quyÕt

2

3 +

®Þnh.

( mnO

)TGNmn ) (

§é phøc t¹p vÒ thêi gian cña thuËt to¸n nµy lµ víi

)12 −mO (

)TGN (

lµ sè lÇn sinh vµ nhá h¬n .

ThuËt to¸n nµy lµ kh«ng phï hîp cho c¸c c¬ së d÷ liÖu cã sè thuéc tÝnh lín,

®Ó gi¶i quyÕt vÊn ®Ò nµy, ta sÏ t×m mét rót gän cña c¸c thuéc tÝnh ®iÒu kiÖn trong

giai ®o¹n tiÒn xö lý vµ t×m mét gi¶i ph¸p gÇn tèi −u, sö dông mét sè phÐp pháng

®o¸n hiÖu qu¶.

ThuËt to¸n 2.2: Gi¶i ph¸p gÇn tèi −u {16]

B−íc 1: §Æt R = {}, COVER = {}, SS ={®Þnh danh cña tÊt c¶ c¸c ®èi t−îng}.

Víi mçi líp Dc, chia b¶ng quyÕt ®Þnh T lµm 2 phÇn: líp hiÖn t¹i T+

vµ c¸c líp cßn l¹i T-

B−íc 2: Tõ c¸c gi¸ trÞ vij cña c¸c ®èi t−îng Ik (vij lµ gi¸ trÞ thø j cña thuéc tÝnh

thø i, Ik ∈ T+, Ik ∈ SS) chän mét gi¸ trÞ v cã sè lÇn xuÊt hiÖn nhiÒu

nhÊt trong c¸c ®èi t−îng chøa trong T- .

B−íc 3: Thªm v vµo R

-51-

B−íc 4: Xãa ®Þnh danh cña ®èi t−îng khái SS nÕu ®èi t−îng ®ã kh«ng chøa v.

B−íc 5: Quay l¹i b−íc 2 tíi khi ®é nhiÔu nhá h¬n gi¸ trÞ ng−ìng

B−íc 6: T×m mét tËp con tèi thiÓu R’ cña R tuú theo ®é m¹nh cña nã. Thªm

luËt (R’ → Dc) vµo RS. §Æt R = {}, sao chÐp ®Þnh danh cña c¸c ®èi

t−îng tõ SS vµo COVERED vµ ®Æt SS ={mäi ®Þnh danh cña c¸c ®èi

t−îng }\ COVERED

B−íc 7: Quay l¹i b−íc 2 tíi khi mäi ®èi t−îng cña T+ ®Òu ë trong COVERED

B−íc 8: Quay l¹i b−íc 1 tíi khi mäi líp ®−îc xö lý xong.

( 2nmO

)2

. §é phøc t¹p vÒ thêi gian cña thuËt to¸n nµy lµ:

KÕt luËn ch−¬ng II

Ph¸t hiÖn luËt kÕt hîp lµ mét trong c¸c kü thuËt ®¬n gi¶n vµ hiÖu qu¶ cña khai ph¸

d÷ liÖu. Theo c¸ch nµy, tri thøc ®−îc ph¸t biÓu d−íi d¹ng c¸c luËt biÓu diÔn sù phô

thuéc gi÷a c¸c tËp con thuéc tÝnh xuÊt hiÖn th−êng xuyªn trong c¬ së d÷ liÖu (môc

2.1.1). ViÖc ph¸t hiÖn ra c¸c luËt kÕt hîp tõ c¬ së d÷ liÖu ®ßi hái l−îng tÝnh to¸n vµ

truy xuÊt d÷ liÖu v« cïng lín. NhiÒu thuËt to¸n tuÇn tù ®· ®−îc ph¸t triÓn cho c¸c

m« h×nh kh¸c nhau (môc 2.1.2). Trªn thùc tÕ, hiÖn t−îng d÷ liÖu kh«ng ®Çy ®ñ hoÆc

kh«ng chÝnh x¸c lµ cã thÓ x¶y ra, nã ¶nh h−ëng kh«ng tèt tíi qu¸ tr×nh nh»m ph¸t

hiÖn ra tri thøc chÝnh x¸c tõ d÷ liÖu. Lý thuyÕt tËp th« ®· ®−îc ph¸t triÓn bëi Pawlak

[14] cho phÐp suy dÉn ra c¸c xÊp xØ cña c¸c kh¸i niÖm, gióp rót gän d÷ liÖu trong

qu¸ tr×nh t×m kiÕm mÉu vµ sinh luËt (môc 2.2.1). Lý thuyÕt nµy ®−îc sö dông trong

viÖc ph¸t hiÖn luËt kÕt hîp tõ c¬ së d÷ liÖu d¹ng b¶ng quyÕt ®Þnh (môc 2.2.2). ViÖc

sö dông tri thøc kinh nghiÖm trong chän luËt còng gióp gi¶m bít ®−îc sè thuéc tÝnh

cÇn xem xÐt ®Ó t¹o luËt. Hai t¸c gi¶ A. Skowron & N. Zhong [16] ®· ®−a ra mét

-52-

thuËt to¸n tuÇn tù t×m tËp tèi −u c¸c luËt tõ b¶ng quyÕt ®Þnh cïng víi c¶i tiÕn cña nã

nh»m gi¶m bít ®é phøc t¹p tÝnh to¸n.

-53-

Ch−¬ng III. ph¸t hiÖn song song luËt kÕt hîp

III.1. kh«ng gian thiÕt kÕ song song

Ng−êi ta hi väng song song hãa sÏ lµm gi¶m ®−îc khã kh¨n cho c¸c ph−¬ng

ph¸p ph¸t hiÖn luËt kÕt hîp tuÇn tù, cung cÊp kh¶ n¨ng më réng cho c¸c tËp d÷ liÖu

lín vµ c¶i thiÖn ®−îc tèc ®é thùc hiÖn. Cã ®−îc hiÖu suÊt cao tõ c¸c hÖ ®a xö lý hiÖn

thêi kh«ng ph¶i lµ mét chuyªn dÔ. C¸c th¸ch thøc chÝnh bao gåm viÖc gi¶m thiÓu sù

truyÒn th«ng vµ ®ång bé hãa, c©n b»ng khèi l−îng c«ng viÖc, t×m ®−îc c¸ch tèt ®Ó

tr×nh bµy d÷ liÖu, ph©n tÝch d÷ liÖu vµ gi¶m thiÓu viÖc truy/xuÊt ®Üa (®©y lµ ®iÒu rÊt

quan träng cho viÖc ph¸t hiÖn luËt kÕt hîp). Kh«ng gian thiÕt kÕ song song gåm 3

phÇn chÝnh: nÒn phÇn cøng, kiÓu song song hãa, vµ chiÕn l−îc c©n b»ng t¶i c«ng

viÖc.

III.1.1. NÒn phÇn cøng: C¸c hÖ thèng ph©n t¸n bé nhí/ C¸c hÖ thèng chia sÎ bé nhí

Trong mét kiÕn tróc cã bé nhí chia sÎ, mçi bé xö lý cã quyÒn truy nhËp

ngang b»ng vµ trùc tiÕp tíi tÊt c¶ bé nhí cña hÖ thèng. C¸c ch−¬ng tr×nh song song

dÔ thùc hiÖn trªn hÖ thèng nh− vËy. Mét c¸ch tiÕp cËn ®a xö lý kh¸c lµ x©y dùng

mét hÖ thèng tõ nhiÒu bé phËn, mçi bé phËn chøa mét bé xö lý vµ bé nhí. Trong

kiÕn tróc bé nhí ph©n t¸n, mçi bé xö lý cã riªng bé nhí côc bé mµ chØ m×nh nã cã

quyÒn truy nhËp. NÕu mét bé xö lý muèn truy cËp d÷ liÖu trªn bé nhí côc bé cña bé

xö lý kh¸c, mét b¶n sao cña d÷ liÖu cÇn dïng ph¶i ®−îc göi gi÷a hai bé xö lý. MÆc

dï kiÕn tróc chia sÎ bé nhí cho phÐp lËp tr×nh ®¬n gi¶n h¬n, nh−ng b¨ng th«ng h÷u

h¹n cña ®−êng truyÒn sÏ h¹n chÕ kh¶ n¨ng më réng. KiÕn tróc dïng bé nhí ph©n t¸n

vµ truyÒn th«ng b¸o gi¶i quyÕt vÊn ®Ò ph¸t triÓn hÖ thèng, nh−ng lËp tr×nh kh«ng

®¬n gi¶n.

-54-

Mét m« h×nh thø ba rÊt phæ biÕn, kÕt hîp nh÷ng −u ®iÓm cña c¸c c¸ch tiÕp

cËn dïng bé nhí chia sÎ vµ bé nhí ph©n t¸n. M« h×nh nµy bao gåm c¸c hÖ thèng

chia sÎ bé nhí víi phÇn cøng hoÆc phÇn mÒm ph©n t¸n. C¸c hÖ thèng nµy ph©n chia

bé nhí vËt lý gi÷a c¸c nót nh−ng cung cÊp mét kh«ng gian ®Þa chØ toµn côc ®−îc

chia sÎ trªn mçi bé xö lý. PhÇn cøng vµ phÇn mÒm ®¶m b¶o sù m¹ch l¹c trong bé

l−u tr÷, gióp d÷ liÖu ®−îc l−u tr÷ côc bé lu«n ph¶n chiÕu c¸c thay ®æi lªn mäi bé xö

lý. Nhãm c¸c m¸y tr¹m chia sÎ bé nhí (clump) còng lµ mét phÇn cña m« h×nh nµy.

C¸c clump ®ßi hái ph¶i cã c¸ch tiÕp cËn song song cã ph©n cÊp, víi bé nhí chia sÎ

nguyªn thñy ®−îc dïng trong mét nót vµ c¸c th«ng b¸o ®−îc truyÒn gi÷a c¸c nót

chia sÎ bé nhí.

Môc ®Ých tèi −u hãa hiÖu suÊt cho c¸c m¸y cã bé nhí ph©n t¸n so víi c¸c hÖ

thèng chia sÎ bé nhí phô thuéc vµo kiÕn tróc c¬ së. Trong hÖ thèng ph©n t¸n bé

nhí, sù ®ång bé hãa n»m Èn trong viÖc truyÒn th«ng b¸o, vÝ thÕ môc tiªu trë thµnh

tèi −u hãa sù truyÒn th«ng. Víi c¸c hÖ chia sÎ bé nhí, sù ®ång bé hãa xuÊt ph¸t tõ

c¸c khãa vµ c¸c hµng rµo ng¨n c¸ch, vµ môc tiªu lµ ph¶i tèi −u hãa nh÷ng ®iÓm nµy.

Sù ph©n r· d÷ liÖu lµ rÊt quan träng trong c¸c hÖ ph©n t¸n, song l¹i kh«ng quan

träng trong c¸c hÖ chia sÎ bé nhí. Trong khi viÖc nhËp/xuÊt song song lµ ®¬n gi¶n

víi c¸c hÖ cã bé ph©n t¸n, nã l¹i lµ vÊn ®Ò khã ®èi víi c¸c hÖ chia sÎ bé nhí, n¬i mµ

viÖc nhËp/xuÊt th−êng ®−îc tuÇn tù hãa. Th¸ch thøc chñ yÕu ®Ó ®¹t hiÖu suÊt cao

cho c¸c hÖ cã bé nhí ph©n t¸n lµ ph¶i t×m ®−îc mét sù ph©n r· tèt d÷ liÖu gi÷a c¸c

nót vµ gi¶m thiÓu sù truyÒn th«ng.

Víi c¸c hÖ chia sÎ bé nhí, môc ®Ých lµ cã ®−îc vÞ trÝ tèt cho d÷ liÖu, nghÜa lµ

ta ph¶i tèi ®a sù truy nhËp tíi bé nhí ®Þa ph−¬ng vµ tr¸nh/ gi¶m lçi chia sÎ bé nhí.

Nh− vËy ta cÇn gi¶m hiÖu øng "bãng bµn" - nhiÒu bé xö lý cïng cè thay ®æi c¸c

biÕn kh¸c nhau cïng n»m trïng khíp t¹i mét hµng trong bé nhí. Víi c¸c m¸y ph©n

cÊp lai truy nhËp bé nhí kh«ng ®ång bé, c¸c tham sè tèi −u ®−îc lÊy tõ c¶ hai m«

h×nh bé nhí ph©n t¸n vµ bé nhí chia sÎ.

-55-

III.1.2. Song song hãa d÷ liÖu vµ song song hãa c«ng viÖc

Song song hãa d÷ liÖu vµ song song hãa c«ng viÖc lµ hai m« h×nh chÝnh ®Ó

khai th¸c c¸c thuËt to¸n song song. Víi viÖc ph¸t hiÖn luËt kÕt hîp, song song hãa

d÷ liÖu øng víi viÖc c¬ së d÷ liÖu ®−îc chia ra trªn p bé xö lý - ph©n chia vÒ mÆt

logic cho bé nhí chia sÎ, ph©n chia vÒ mÆt vËt lý cho c¸c hÖ ph©n t¸n bé nhí. Mçi

bé xö lý lµm viÖc trªn phÇn c¬ së d÷ liÖu cña nã nh−ng thùc hiÖn cïng mét phÐp

®Õm ®é hç trî cho c¸c itemset øng viªn toµn côc. Song song hãa c«ng viÖc øng víi

viÖc c¸c bé xö lý thùc hiÖn c¸c phÐp tÝnh kh¸c nhau mét c¸ch ®éc lËp, nh− lµ ®Õm

mét tËp kh«ng giao nhau c¸c øng viªn, nh−ng kh«ng cÇn truy nhËp tíi toµn bé c¬ së

d÷ liÖu. C¸c hÖ chia sÎ bé nhí cã truy nhËp tíi toµn bé d÷ liÖu, nh−ng víi c¸c hÖ

ph©n t¸n bé nhí, qu¸ tr×nh truy nhËp c¬ së d÷ liÖu cã thÓ liªn quan tíi viÖc t¸i t¹o

mét c¸ch cã chän lùa hoÆc truyÒn th«ng gi÷a c¸c phÇn côc bé. Còng cã thÓ kÕt hîp

c¶ song song hãa d÷ liÖu vµ song song hãa c«ng viÖc, ®©y lµ c¸ch ®−îc −a dïng ®Ó

khai th¸c hÕt ®−îc c¸c c¸ch song song hãa cã s½n cho c¸c thuËt to¸n ph¸t hiÖn luËt

kÕt hîp.

III.1.3. C©n b»ng t¶i tÜnh vµ c©n b»ng t¶i ®éng

C©n b»ng t¶i tÜnh ban ®Çu ph©n chia c«ng viÖc gi÷a c¸c bé xö lý dïng hµm

chi phÝ theo kinh nghiÖm, kh«ng cã thay ®æi nµo trªn d÷ liÖu hoÆc trong tÝnh to¸n

nµo cã thÓ ®iÒu chØnh sù mÊt c©n b»ng vÒ t¶i do b¶n chÊt ®éng cña c¸c thuËt to¸n

ph¸t hiÖn luËt kÕt hîp. ViÖc c©n b»ng t¶i ®éng gi¶i quyÕt vÊn ®Ò nµy b»ng c¸ch lÊy

c«ng viÖc tõ c¸c bé xö lý ph¶i chÞu t¶i nÆng vµ g¸n sang c¸c bé xö lý cã l−îng c«ng

viÖc Ýt h¬n. C¸c thay ®æi trong tÝnh to¸n còng dÉn tíi c¸c thay ®æi trªn d÷ liÖu, do bé

xö lý chÞu tr¸ch nhiÖm cho nhiÖm vô tÝnh to¸n cÇn c¸c d÷ liÖu kÕt hîp víi nhiÖm vô

nµy. V× thÕ c©n b»ng t¶i ®éng ph¶i chÞu thªm chi phÝ dÞch chuyÓn d÷ liÖu vµ c«ng

viÖc, vµ cho c¶ c¬ chÕ x¸c ®Þnh sù mÊt c©n b»ng. Tuy nhiªn c©n b»ng t¶i ®éng lµ cÇn

thiÕt nÕu cã sù mÊt c©n b»ng lín vÒ t¶i hoÆc t¶i thay ®æi theo thêi gian.

-56-

C©n b»ng t¶i ®éng ®Æc biÖt quan träng trong m«i tr−êng nhiÒu ng−êi sö dông

víi c¸c t¶i t¹m thêi vµ trªn nÒn kh«ng ®ång nhÊt cã bé xö lý vµ m¹ng víi tèc ®é

kh¸c nhau. C¸c kiÓu m«i tr−êng nµy bao gåm c¸c m¸y chñ song song vµ c¸c cluster,

metacluster vµ supercluster kh«ng ®ång nhÊt. TÊt c¶ c¸c thuËt to¸n ph¸t hiÖn luËt

kÕt hîp më réng chØ dïng c¸ch c©n b»ng t¶i tÜnh cã s½n nhê sù ph©n chia c¬ së d÷

liÖu s½n cã gi÷a c¸c nót. §iÒu nµy lµ do gi¶ thiÕt cã mét m«i tr−êng ®ång nhÊt vµ

chuyªn dông.

VÊn ®Ò thiÕt kÕ chÝnh trong c¸c hÖ ph©n t¸n bé nhí lµ viÖc gi¶m thiÓu sù

truyÒn th«ng vµ thËm chÝ c¶ ph©n t¸n d÷ liÖu ®Ó cã sù c©n b»ng t¶i. C¸c thuËt to¸n

ph¸t hiÖn luËt kÕt hîp d−íi ®©y gi¶ sö r»ng c¬ së d÷ liÖu ®−îc chia thµnh c¸c phÇn

cã kÝch th−íc nh− nhau trªn æ ®Üa côc bé cña c¸c bé xö lý.

III.2. Mét sè m« h×nh ph¸t hiÖn song song luËt kÕt hîp

Tån t¹i nhiÒu thuËt to¸n thùc hiÖn viÖc ph¸t hiÖn song song c¸c luËt kÕt hîp.

D−íi ®©y lµ nh÷ng thuËt to¸n ®iÓn h×nh nhÊt [15, 17].

III.2.1. C¸c hÖ ph©n t¸n bé nhí

(cid:131) ThuËt to¸n PEAR - dùa trªn SEAR vµ SPEAR

Andrea Muller ®−a ra mét sè ph−¬ng ph¸p ph¸t hiÖn song song luËt kÕt hîp

trªn nÒn c¸c ph−¬ng ph¸p tuÇn tù dùa trªn c¸c thuËt to¸n Partition vµ Apriori. PEAR

lµ b¶n song song cña SEAR, trong mçi lÇn lÆp, mçi bé xö lý t¹o mét c©y tiÒn tè c¸c

øng viªn tõ c¸c itemset phæ biÕn toµn phÇn cña lÇn duyÖt tr−íc. Mçi bé xö lý cã

toµn bé b¶n sao cña tËp øng viªn ®ã. TiÕp theo mçi nót tËp hîp c¸c ®é hç trî ®Þa

ph−¬ng, cïng víi mét rót gän cña tæng ®Ó cã ®−îc ®é hç trî toµn phÇn trªn mçi bé

xö lý.

C¸ch ph©n chia song song c¸c luËt kÕt hîp (PPAR) lµ dùa trªn SPEAR,

nh−ng PPAR dïng ®Þnh d¹ng d÷ liÖu theo hµng ngang. ThuËt to¸n nµy ho¹t ®éng

-57-

nh− sau: Mçi bé xö lý tËp hîp c¸c itemset phæ biÕn ®Þa ph−¬ng víi mäi kÝch th−íc

trªn c¬ së d÷ liÖu ®Þa ph−¬ng cña nã trong mét lÇn duyÖt. PPAR th«ng b¸o c¸c

itemset phæ biÕn tiÒm n¨ng tíi tÊt c¶ c¸c bé xö lý kh¸c. Trong lÇn duyÖt côc bé thø

hai, mçi bé xö lý tËp hîp con sè c¸c øng viªn toµn phÇn. Cuèi cïng, mét th«ng b¸o

vÒ tËp itemset phæ biÕn toµn phÇn ®−îc ph¸t ra. C¸c thö nghiÖm cho thÊy PEAR

lu«n tèt h¬n PPAR, bëi v× PEAR dïng c¸c gép nhiÒu lÇn duyÖt trong khi PPAR cã

thÓ t¹o nªn mét c¸ch kh«ng cÇn thiÕt nhiÒu øng viªn mµ rèt côc lµ kh«ng phæ biÕn.

(cid:131) ThuËt to¸n PDM - dùa trªn DHP

Trong thuËt to¸n PDM, mçi bé xö lý t¹o c¸c ®é hç trî ®Þa ph−¬ng cña c¸c 1-

itemset vµ tÝnh xÊp xØ sè c¸c 2-itemset víi mét b¶ng b¨m. Th«ng b¸o tõ mçi nót tíi

tÊt c¶ c¸c nót kh¸c vÒ sè ®Õm côc bé sÏ gióp tÝnh ®−îc sè c¸c 1-itemset toµn phÇn.

Do b¶ng b¨m chøa c¸c 2-itemset cã thÓ rÊt lín, sù trao ®æi trùc tiÕp c¸c con sè qua

th«ng b¸o gi÷a tÊt c¶ c¸c nót sÏ rÊt tèn kÐm. C¸c t¸c gi¶ ®· dïng c¸ch tèi −u hãa lµ

chØ trao ®æi c¸c phÇn tö ®−îc ®¶m b¶o lµ sÏ phæ biÕn. Tuy nhiªn, ph−¬ng ph¸p nµy

®ßi hái hai lÇn truyÒn th«ng. Víi lÇn duyÖt thø hai, PDM t¹o c¸c øng viªn ®Þa

ph−¬ng dïng b¶ng b¨m c¸c 2-itemset toµn phÇn. ChØ lÇn duyÖt thø hai dïng b¶ng

b¨m, c¸c lÇn duyÖt sau t¹o c¸c øng viªn trùc tiÕp tõ Fk-1 (nh− trong thuËt to¸n

Apriori).

C¸c øng viªn ®−îc t¹o mét c¸ch song song. Mçi bé xö lý t¹o tËp øng viªn cña

riªng nã, sau ®ã sÏ trao ®æi qua th«ng b¸o gi÷a tÊt c¶ c¸c bé xö lý ®Ó cã ®−îc tËp

øng viªn toµn phÇn. TiÕp ®ã, PDM cã sè c¸c øng viªn ®Þa ph−¬ng vµ trao ®æi chóng

gi÷a c¸c bé xö lý ®Ó cã c¸c itemset phæ biÕn toµn phÇn. C«ng viÖc ®−îc chuyÓn

sang b−íc tiÕp theo. PDM cã mét sè h¹n chÕ: Tr−íc hÕt, nã song song hãa viÖc t¹o

c¸c øng viªn vµ ®ßi hái c¸c th«ng b¸o ph¶i ®−îc truyÒn gi÷a tÊt c¶ c¸c bé xö lý ®Ó

t¹o mét tËp øng viªn toµn phÇn. Chi phÝ truyÒn th«ng nµy cã thÓ lµm gi¶m hiÖu qu¶

cña song song hãa.

-58-

(cid:131) C¸c thuËt to¸n dùa trªn Apriori

NhiÒu thuËt to¸n song song sö dông Apriori nh− lµ ph−¬ng ph¸p c¬ b¶n bëi

sù thµnh c«ng cña nã trong thiÕt ®Æt tuÇn tù.

- Ph©n phèi sè ®Õm, d÷ liÖu vµ øng viªn:

ThuËt to¸n ph©n phèi sè ®Õm lµ mét c¸ch song song hãa ®¬n gi¶n cña

Apriori. TÊt c¶ c¸c bé xö lý t¹o mét c©y b¨m c¸c øng viªn toµn phÇn tõ Fk-1. Mçi bé

xö lý khi ®ã cã ®−îc mét c¸ch ®éc lËp ®é hç trî ®Þa ph−¬ng tõ phÇn c¬ së d÷ liÖu bé

phËn cña nã. TiÕp theo, thuËt to¸n lµm mét phÐp céng gi¶n −íc ®Ó cã sè ®Õm toµn

phÇn b»ng c¸ch trao ®æi c¸c sè ®Õm ®Þa ph−¬ng víi c¸c bé xö lý kh¸c. Thay v× trén

c¸c c©y b¨m kh¸c nhau, thuËt to¸n chØ cÇn trao ®æi c¸c sè ®Õm ®Þa ph−¬ng, v× tÊt c¶

c¸c bé xö lý ®· cã b¶n sao cña toµn bé c©y b¨m. Mçi khi x¸c ®Þnh ®−îc Fk toµn

phÇn, mçi bé xö lý x©y dùng song song toµn bé øng viªn Ck-1, vµ lÆp l¹i qu¸ tr×nh tíi

khi t×m ®−îc tÊt c¶ c¸c itemset phæ biÕn. ThuËt to¸n nµy gi¶m thiÓu viÖc truyÒn

th«ng, tuy nhiªn, do nã sao toµn bé c©y b¨m trªn mçi bé xö lý, nã kh«ng sö dông

ThuËt to¸n ph©n phèi sè ®Õm

hiÖu qu¶ toµn bé bé nhí hÖ thèng.

Rót gän sè ®Õm toµn côc

-59-

ThuËt to¸n ph©n phèi d÷ liÖu dïng toµn bé bé nhí hÖ thèng b»ng c¸ch t¹o c¸c

tËp øng viªn rêi nhau trªn mçi bé xö lý. Tuy nhiªn, ®Ó tÝnh ®é hç trî toµn phÇn, mçi

bé xö lý ph¶i duyÖt toµn bé c¬ së d÷ liÖu trong tÊt c¶ c¸c lÇn lÆp. Do ®ã, thuËt to¸n

nµy ph¶i chÞu g¸nh nÆng lín vÒ truyÒn th«ng vµ hiÖu qu¶ kh«ng cao so víi thuËt

ThuËt to¸n ph©n phèi d÷ liÖu

to¸n ph©n phèi sè ®Õm.

Th«ng b¸o vÒ d÷ liÖu

Th«ng b¸o vÒ c¸c øng viªn gi÷a c¸c bé xö lý

ThuËt to¸n ph©n phèi øng viªn ph©n chia c¸c øng viªn trong lÇn lÆp l ®Ó mçi

bé xö lý cã thÓ t¹o c¸c øng viªn kh«ng giao nhau ®éc lËp víi c¸c bé xö lý kh¸c.

ViÖc ph©n chia sö dông kinh nghiÖm dùa trªn ®é hç trî, khiÕn mçi bé xö lý cã

l−îng c«ng viÖc nh− nhau. §ång thêi, c¬ së d÷ liÖu còng ®−îc sao chÐp mét c¸ch cã

chän lùa ®Ó mçi bé xö lý cã thÓ tÝnh sè ®Õm toµn phÇn mét c¸ch ®éc lËp. Sù lùa

chän pha ph©n phèi l¹i liªn quan tíi sù tháa hiÖp gi÷a viÖc t¸ch riªng c¸c bé xö lý

®éc lËp cµng sím cµng tèt vµ viÖc ®îi tíi khi cã ®ñ sù c©n b»ng t¶i. Trong c¸c thÝ

nghiÖm cña Agrawal vµ Shafer, sù ph©n chia l¹i ®−îc thùc hiÖn trong bèn lÇn. Sau

®ã, chØ bé xö lý ®éc lËp víi c¸c bé xö lý kh¸c lµ bÞ c¾t bít c¸c øng viªn. Mçi bé xö

lý th«ng b¸o kh«ng ®ång bé tËp phæ biÕn ®Þa ph−¬ng cña m×nh tíi c¸c bé xö lý kh¸c

trong mçi lÇn lÆp. NÕu sù c¾t xÐn th«ng tin nµy x¶y ra ®óng lóc, nã ®−îc dïng, nÕu

-60-

kh«ng nã sÏ ®−îc l−u l¹i dïng cho lÇn lÆp sau. Mçi bé xö lý vÉn ph¶i duyÖt d÷ liÖu

côc bé cña nã trong mçi lÇn lÆp. ThËm chÝ khi cã th«ng tin ®Æc tr−ng cho bµi to¸n,

thuËt to¸n ph©n phèi øng viªn vÉn thùc hiÖn tåi h¬n thuËt to¸n ph©n phèi sè ®Õm, do

nã ph¶i tr¶ gi¸ cho viÖc ph©n phèi l¹i c¬ së d÷ liÖu khi lÆp l¹i viÖc duyÖt phÇn d÷

liÖu côc bé.

- C¸c thuËt to¸n Apriori kh«ng ph©n chia, ph©n chia ®¬n gi¶n vµ ph©n chia b¨m

Apriori kh«ng ph©n chia (NPA) vÒ c¬ b¶n gièng víi thuËt to¸n ph©n phèi sè

®Õm, ngo¹i trõ viÖc rót gän tæng ®−îc thùc hiÖn trªn bé xö lý chÝnh. ThuËt to¸n

Apriori ph©n chia ®¬n gi¶n (SPA) gièng hÖt thuËt to¸n ph©n phèi d÷ liÖu.

ThuËt to¸n Apriori ph©n chia b¨m (HPA) t−¬ng tù thuËt to¸n ph©n phèi øng

viªn. Mçi bé xö lý t¹o c¸c øng viªn tõ tËp phæ biÕn t¹o ë møc tr−íc vµ ¸p dông hµm

b¨m ®Ó x¸c ®Þnh bé xö lý chñ cho mét øng viªn. NÕu mét bé xö lý lµ chñ cña mét

øng viªn, nã sÏ thªm øng viªn ®ã vµo c©y b¨m t¹i chç, nÕu kh«ng, nã bá qua øng

viªn. §Ó ®Õm, thuËt to¸n nµy kh«ng lÆp l¹i c¬ së d÷ liÖu mét c¸ch cã chän lùa nh−

thuËt to¸n ph©n phèi øng viªn, mçi bé xö lý t¹o mét tËp con k ph©n tö cho mçi giao

dÞch ®Þa ph−¬ng, t×m bé xö lý ®Ých, vµ göi tËp con ®ã ®Õn bé xö lý. Bé xö lý chñ cã

tr¸ch nhiÖm t¨ng sè ®Õm sö dông c¬ së d÷ liÖu ®Þa ph−¬ng vµ bÊt kú th«ng b¸o nµo

tõ c¸c bé xö lý kh¸c.

Shitani vµ Kitsuregawa còng ®Ò xuÊt mét biÕn ®æi cho thuËt to¸n Apriori

ph©n chia b¨m, gäi lµ Apriori ph©n chia b¨m víi sù nh©n ®«i c¸c tËp d÷ liÖu cùc lín

(HPA-ELD). §éng c¬ cña thuËt to¸n nµy lµ dï ta cã ph©n chia c¸c øng viªn mét

c¸ch ®ång ®Òu trªn c¸c bé xö lý, vÉn cã øng viªn phæ biÕn h¬n c¸c øng viªn kh¸c.

V× thÕ, bé xö lý chñ cña nã sÏ cã t¶i nÆng h¬n, trong khi c¸c bé xö lý kh¸c cã t¶i

nhÑ. HPA-ELD gi¶i quyÕt chuyÖn nµy b»ng c¸ch sao chÐp c¸c itemset rÊt phæ biÕn

trªn tÊt c¶ c¸c bé xö lý vµ xö lý chóng b»ng s¬ ®å NPA. Do ®ã, kh«ng cÇn truyÒn

-61-

tËp con cho c¸c øng viªn nµy. Khi ®· tÝnh ®−îc c¸c sè ®Õm côc bé, tiÕp theo lµ phÐp

tÝnh rót gän tæng ®Ó cã ®é hç trî toµn phÇn.

Shitani vµ Kitsuregawa ®· kh¼ng ®Þnh b»ng c¸c thÝ nghiÖm r»ng HPA-ELD

thùc hiÖn tèt h¬n c¸c c¸ch tiÕp cËn kh¸c. Tuy nhiªn, hä chØ dïng SPA, HPA vµ

HPA-ELD cho lÇn lÆp thø hai, vµ víi c¸c lÇn lÆp sau, hä dïng apriori kh«ng ph©n

chia. §iÒu nµy cho thÊy c¸ch tiÕp cËn tèt nhÊt lµ c¸ch lai: dïng HPA-ELD chõng

nµo c¸c øng viªn cßn ch−a võa trong bé nhí, sau ®ã chuyÓn sang dïng Apriori

kh«ng ph©n chia (NPA). §iÒu nµy rÊt cã ý nghÜa bëi Apriori kh«ng ph©n chia vµ

ph©n phèi sè ®Õm lµ c¸c thuËt to¸n ®ßi hái l−îng truyÒn th«ng Ýt nhÊt.

- Ph©n phèi d÷ liÖu th«ng minh vµ Ph©n phèi lai

Eui-Hong Han vµ c¸c céng sù ®· ®Ò xuÊt hai ph−¬ng ph¸p ph¸t hiÖn luËt kÕt

hîp dùa trªn ph©n phèi d÷ liÖu. Hä quan s¸t thÊy thuËt to¸n ph©n phèi d÷ liÖu sö

dông c¸ch truyÒn th«ng b¸o gi÷a tÊt c¶ c¸c bé xö lý rÊt tèn kÐm ®Ó göi c¸c phÇn d÷

liÖu côc bé tíi mäi bé xö lý kh¸c. H¬n n÷a, mÆc dï ph©n phèi d÷ liÖu chia c¸c øng

viªn ®ång ®Òu trªn gi÷a c¸c bé xö lý, nã kh«ng ph©n chia ®−îc c«ng viÖc trong mçi

giao dÞch. Tøc lµ nã vÉn t¹o mét tËp con cña giao dÞch vµ x¸c ®Þnh xem liÖu c©y

b¨m cã chøa tËp con ®ã kh«ng.

Trong c¸ch ph©n phèi d÷ liÖu th«ng minh, Han vµ céng sù ®· dïng c¸ch

truyÒn th«ng gi÷a c¸c bé xö lý theo vßng trßn, tuyÕn tÝnh vÒ thêi gian. Hä chuyÓn

sang c¸ch ph©n phèi sè ®Õm mçi khi c¸c øng viªn võa trong bé nhí. Thay v× ph©n

chia øng viªn theo vßng trßn, hä dïng c¸ch ph©n chia dùa trªn tiÒn tè, cho tõng

thuéc tÝnh mét. Tr−íc khi xö lý mét giao dÞch, hä ®¶m b¶o r»ng nã chøa c¸c tiÒn tè

t−¬ng øng. NÕu kh«ng, giao dÞch nµy cã thÓ bÞ bá qua. Toµn bé c¬ së d÷ liÖu vÉn

giao tiÕp víi nhau, nh−ng mét giao dÞch cã thÓ kh«ng ®−îc xö lý nÕu nã kh«ng chøa

c¸c thuéc tÝnh t−¬ng øng.

-62-

ThuËt to¸n ph©n phèi d÷ liÖu th«ng minh

DÞch chuyÓn d÷ liÖu

Th«ng b¸o vÒ c¸c øng viªn gi÷a c¸c bé xö lý

ThuËt to¸n ph©n phèi lai kÕt hîp c¶ ph©n phèi sè ®Õm vµ ph©n phèi d÷ liÖu

th«ng minh. Nã ph©n chia P bé xö lý thµnh G nhãm kÝch th−íc b»ng nhau, mçi

nhãm ®−îc coi lµ mét bé siªu xö lý. Ph©n phèi sè ®Õm ®−îc dïng gi÷a G bé siªu xö

lý, vµ P/G bé xö lý trong mçi nhãm dïng c¸ch ph©n phèi d÷ liÖu th«ng minh. C¬ së

d÷ liÖu ®−îc ph©n chia theo hµng ngang gi÷a G bé siªu xö lý, c¸c øng viªn ®−îc

ph©n chia gi÷a P/G bé xö lý trong mçi nhãm. Thªm vµo ®ã, ph©n phèi lai ®iÒu chØnh

sè c¸c nhãm mét c¸ch linh ho¹t trong mçi lÇn lÆp. C¸c −u ®iÓm cña c¸ch ph©n phèi

lai lµ nã gi¶m ®−îc chi phÝ truyÒn th«ng trªn c¬ së d÷ liÖu cßn 1/G lÇn, vµ nã lu«n

gi÷ cho c¸c bé xö lý bËn rén, ®Æc biÖt trong c¸c lÇn lÆp sau. C¸c thÝ nghiÖm cho thÊy

lµ, trong khi ph©n phèi lai cã cïng hiÖu suÊt víi ph©n phèi sè ®Õm, nã cã thÓ xö lý

l−îng d÷ liÖu lín h¬n rÊt nhiÒu.

-63-

ThuËt to¸n ph©n phèi lai

P/G bé xö lý trªn mçi nhãm

Ph©n phèi sè ®Õm theo c¸c hµng

ý l

t é c c ¸ c o e h t h n i m g n « h t u Ö i l

÷ d

ö x é b c ¸ c m ã h n G

ý l ö x é b c ¸ c a ÷ i g n ª i v g n ø Ò v o ¸ b g n « h T

i è h p n © h P

- Ph¸t hiÖn ph©n t¸n nhanh (FDM)

David Cheung vµ céng sù ®Ò xuÊt thuËt to¸n ph©n t¸n nhanh ®Ó ph¸t hiÖn luËt

kÕt hîp. Sù kh¸c biÖt chÝnh gi÷a khai ph¸ d÷ liÖu song song vµ ph©n t¸n lµ b¨ng

th«ng vµ ®é trÔ trªn m¹ng, ngoµi ra, c¸c kh¸c biÖt kh¸c lµ kh«ng râ nÐt. Víi mét

m¹ng chËm, bÊt cø biÓn ®æi nµo cña c¸ch ph©n phèi d÷ liÖu ®Òu kh«ng cã gi¸ trÞ

thùc tÕ do chóng ph¶i truyÒn th«ng toµn bé c¬ së d÷ liÖu trong mçi lÇn lÆp. Do thuËt

to¸n ph©n phèi sè ®Õm kh«ng tèn nhiÒu chi phÝ cho truyÒn th«ng, nã lµ c¸ch lý

t−ëng ®Ó lµm c¬ së cho c¸c ph−¬ng ph¸p kh¸c trong m«i tr−êng ph©n t¸n.

Khai ph¸ ph©n t¸n nhanh dùa trªn ph©n phèi sè ®Õm vµ ®−a ra c¸c kü thuËt

míi ®Ó gi¶m sè c¸c øng viªn cÇn xem xÐt khi ®Õm, theo c¸ch ®ã nã gi¶m thiÓu sù

truyÒn th«ng. ThuËt to¸n nµy gi¶ sö r»ng c¬ së d÷ liÖu ®−îc ph©n chia theo chiÒu

ngang gi÷a c¸c tr¹m ph©n t¸n. V× tÊt c¶ c¸c itemset phæ biÕn toµn phÇn ®Òu ph¶i lµ

itemset phæ biÕn ®Þa ph−¬ng t¹i mçi tr¹m, c¸c øng viªn duy nhÊt mµ c¸c tr¹m ph¶i

xem xÐt ph¶i ®−îc t¹o nªn tõ c¶ c¸c øng viªn phæ biÕn ®Þa ph−¬ng vµ phæ biÕn toµn

-64-

phÇn (ký hiÖu lµ GLi cho tr¹m thø i). VÝ dô, trªn tÊt c¶ c¸c thuéc tÝnh phæ biÕn Fi =

{A, B, C, D, E}, ®Æt GL1 = {A, B, C} vµ GL2 = {C, D, E}. Khi ®ã tr¹m ®Çu tiªn chØ

xÐt c¸c øng viªn CG1 = {AB, AC, BC} vµ CG2 = {CD, CE, DE}. Thay v× s¸u øng

viªn nµy, thuËt to¸n ph©n phèi sè ®Õm sÏ t¹o ra 5 x 2 = 10 øng viªn. Khai ph¸ ph©n

t¸n nhanh còng ®Ò nghÞ ba c¸ch tèi −u hãa: tØa côc bé, tØa toµn phÇn vµ kiÓm sè ®Õm.

Trong khai ph¸ ph©n t¸n nhanh dïng c¸ch tØa côc bé vµ kiÓm sè ®Õm. Mçi

tr¹m t¹o c¸c øng viªn sö dông GLi tõ tÊt c¶ c¸c tr¹m vµ g¸n mét tr¹m chñ cho mçi

øng viªn. Sau ®ã, mçi tr¹m tÝnh ®é hç trî ®Þa ph−¬ng cho c¸c øng viªn. TiÕp theo lµ

b−íc tØa: lo¹i bÊt cø itemset X nµo kh«ng phæ biÕn ®Þa ph−¬ng t¹i tr¹m hiÖn t¹i, v×

nÕu X lµ phæ biÕn toµn phÇn, th× nã sÏ ph¶i xuÊt hiÖn t¹i mét sè tr¹m kh¸c.

B−íc tiÕp theo lµ sù tèi −u hãa viÖc kiÓm sè ®Õm. Mçi tr¹m chñ yªu cÇu tÊt c¶

c¸c øng viªn ®−îc g¸n cho nã sè ®Õm côc bé tõ tÊt c¶ c¸c tr¹m kh¸c vµ tÝnh ®é hç

trî toµn phÇn cña chóng. Tr¹m chñ sÏ th«ng b¸o ®é hç trî toµn phÇn tíi tÊt c¶ c¸c

tr¹m kh¸c. Cuèi cïng, mçi tr¹m cã tËp phæ biÕn toµn phÇn vµ b¾t ®Çu mét vßng lÆp

míi. ThuËt to¸n ph©n phèi sè ®Õm th«ng b¸o c¸c sè ®Õm ®Þa ph−¬ng cña tÊt c¶ c¸c

øng viªn tíi tÊt c¶ c¸c tr¹m kh¸c, trong khi khai ph¸ ph©n t¸n nhanh chØ göi chóng

tíi mét tr¹m chñ cña mçi øng viªn. V× thÕ, ph−¬ng ph¸p nµy gi¶m l−îng truyÒn

th«ng rÊt nhiÒu, vµ viÖc c¾t tØa ®Þa ph−¬ng thËm chÝ cßn gi¶m nã thÊp h¬n.

Mét c¸ch tèi −u hãa kh¸c ®−îc ®Ò xuÊt lµ tØa toµn bé. Ngoµi viÖc göi ®é hç

trî toµn phÇn cña c¸c itemset phæ biÕn, c¸ch nµy göi c¶ ®é hç trî ®Þa ph−¬ng t¹i mçi

phÇn vµo cuèi vßng lÆp thø (k-1). Víi vßng lÆp tiÕp theo, nÕu X lµ mét øng viªn th×

®é hç trî ®Þa ph−¬ng cña tÊt c¶ c¸c tËp con (k-1) ph©n tö cña nã ®· cã s½n. Ta cã thÓ

thay thÕ cËn trªn cña ®é hç trî cña X t¹i tr¹m i b»ng:

j=1, j≠i ubj(X)

UB(X) = X.supi + Σs

víi s lµ sè tr¹m, ubj(X) lµ ®é hç trî ®Þa ph−¬ng tèi thiÕu cña tËp con (k-1) phÇn tö bÊt

kú cña X t¹i tr¹m j (cËn trªn cña ®é hç trî ®Þa ph−¬ng cña X t¹i tr¹m j). NÕu UB(X)

-65-

nhá h¬n ®é hç trî tèi thiÓu, ta cã thÓ lo¹i X. C¸c t¸c gi¶ ®¸nh gi¸ thuËt to¸n nµy trªn

mét nhãm 6 m¸y tr¹m kÕt nèi b»ng Ethernet LAN 10-Mbyte, c¸c thÝ nghiÖm chØ

kiÓm tra viÖc c¾t tØa ®Þa ph−¬ng víi viÖc kiÓm tra sè ®Õm, ®· cho thÊy r»ng cã thÓ

gi¶m ®−îc 75%-90% kÝch th−íc cña tËp c¸c øng viªn trªn mçi tr¹m, vµ gi¶m ®−îc

85%-90% kÝch th−íc c¸c th«ng b¸o.

- Ph¸t hiÖn song song nhanh (FPM)

VÊn ®Ò trong c¬ chÕ ®Õm cña bµi to¸n ph¸t hiÖn ph©n t¸n nhanh lµ nã cÇn 2

lÇn göi th«ng b¸o trong mçi vßng lÆp: mét lÇn ®Ó tÝnh ®é hç trî toµn phÇn, mét lÇn

®Ó th«ng b¸o c¸c itemset phæ biÕn. S¬ ®å hai vßng nµy cã thÓ lµm gi¶m hiÖu suÊt

trong thiÕt lËp song song. Ph¸t hiÖn song song nhanh t¹o Ýt øng viªn h¬n vµ gi÷ l¹i

c¸c b−íc c¾t tØa toµn phÇn vµ c¾t tØa bé phËn. Nh−ng thay v× kiÓm tra c¸c sè ®Õm vµ

sau ®ã th«ng b¸o c¸c itemset phæ biÕn, nã chØ th«ng b¸o ®é hç trî ®Þa ph−¬ng tíi tÊt

c¶ c¸c bé xö lý.

Mét khÝa c¹nh thó vÞ h¬n cña c¸ch tiÕp cËn nµy lµ c¸c t¸c gi¶ dïng mét ma

trËn ®Ó l−u ®é nghiªng cña d÷ liÖu (sù ph©n bè c¸c itemset trªn c¸c phÇn kh¸c

n

−=

pX

pX

log

nhau). Víi itemset X, ký hiÖu pX(i) lµ x¸c suÊt X xuÊt hiÖn trong phÇn i, khi ®ã

( XH

)

( ) i

(

( ) ) i

∑

1 =

i

entropy cña X ®−îc cho bëi:

Sè entropy ®o ®é ph©n bè cña c¸c sè ®Õm ®é hç trî ®Þa ph−¬ng cña X trong

H

( XH

)

max

=

( XS

)

− H

max

tÊt c¶ c¸c phÇn. §é nghiªng cña mét itemset X ®−îc cho bëi:

víi Hmax = log(n) víi n phÇn. S(X) = 0 nÕu X cã ®é hç trî nh− nhau trong tÊt c¶ c¸c

phÇn, b»ng 1 nÕu X chØ xuÊt hiÖn trong mét phÇn. §é nghiªng d÷ liÖu toµn phÇn cña

c¬ së d÷ liÖu lµ tæng ®é nghiªng cña tÊt c¶ c¸c itemset tÝnh b»ng ®é hç trî cña

chóng. Trªn thùc tÕ, ta chØ cÇn xem xÐt ®é nghiªng cña c¸c itemset phæ biÕn. ThÝ

-66-

nghiÖm cña c¸c t¸c gi¶ trªn 32-nodes IBM SP2 cho thÊy r»ng ph¸t hiÖn song song

nhanh cã thÓ tèt h¬n thuËt to¸n ph©n phèi sè ®Õm 3 lÇn víi c¸c tËp d÷ liÖu cã ®é

nghiªng rÊt lín, vµ gÊp 1.5 lÇn víi c¸c tËp d÷ liÖu cã ®é nghiªng nhá.

III.2.2. C¸c hÖ chia sÎ bé nhí

Bµi to¸n thiÕt kÕ chÝnh trong c¸c hÖ thèng chia sÎ bé nhí liªn quan tíi viÖc

gi¶m thiÓu c¸c lçi chia sÎ vµ duy tr× sù tèt sù ®Þnh h−íng d÷ liÖu. C¸c nÒn hÖ thèng

chia sÎ bé nhí th−êng kh«ng ®−îc chó ý nhiÒu trong lÜnh vùc ph¸t hiÖn luËt kÕt hîp.

Tuy nhiªn, víi sù ph¸t triÓn cña c¸c m¸y tÝnh ®a xö lý vµ c¸c clump, c¸c nÒn hÖ

thèng chia sÎ bé nhí ®ang trë nªn ngµy cµng quan träng.

(cid:131) ThuËt to¸n dùa trªn Apriori

Mét trong c¸c thuËt to¸n cho c¸c hÖ chia sÎ bé nhí lµ øng viªn chung-c¬ së

d÷ liÖu ®−îc ph©n chia (CCPD). CCPD sö dông c¸ch tiÕp cËn d÷ liÖu song song. C¬

së d÷ liÖu ®−îc ph©n chia mét c¸ch hîp lý thµnh c¸c ®o¹n b»ng nhau, vµ tÊt c¶ c¸c

bé xö lý ®ång thêi xö lý mét c©y b¨m toµn phÇn hoÆc c©y b¨m c¸c øng viªn phæ

biÕn. CCPD song song hãa qu¸ tr×nh t¹o øng viªn. Mçi bé xö lý t¹o mét tËp con rêi

nhau c¸c øng viªn, dÉn tíi sù ph©n chia tèt vÒ mÆt tÝnh to¸n. §Ó x©y dùng song song

mét c©y b¨m. CCPD kÕt hîp mét khãa víi mçi nót l¸. Khi mét bé xö lý muèn thªm

mét øng viªn vµo c©y, nã b¾t ®Çu tõ gèc vµ liªn tiÕp b¨m trªn c¸c øng viªn cho tíi

khi ®¹t tíi l¸. Sau ®ã nã cã ®−îc khãa vµ chÌn øng viªn ®ã. Víi c¬ chÕ khãa nµy,

mçi bé xö lý cã thÓ chÌn c¸c itemset trong c¸c phÇn kh¸c nhau cña c©y b¨m mét

c¸ch song song. §Ó ®Õm ®é hç trî, mçi bé xö lý tÝnh tÇn sè tõ phÇn logic cña nã.

C¸c t¸c gi¶ còng ®Ò xuÊt kh¶ n¨ng tèi −u hãa, nh− lµ kÕt hîp vßng ng¾n vµ

c©n b»ng c©y b¨m. KÕt hîp vßng ng¾n sö dông phÐp ®¸nh dÊu bit trªn c©y b¨m ®Ó

tr¸nh viÖc xö lý c©y con ®· ®−îc xö lý tõ tr−íc. Hä dïng mét hµm b¨m míi ®Ó c©n

b»ng c©y b¨m, bëi v× mét hµm mod ®¬n gi¶n cã thÓ dÉn tíi c¸c c©y bÞ nghiªng. Mét

c©y c©n b»ng sÏ t¨ng tèc c¸c tiÕn tr×nh, v× nã cã cã chiÒu cao ng¾n h¬n. ThuËt to¸n

-67-

CCPD cã ®−îc sù t¨ng tèc ®¸ng kÓ nh−ng qu¸ tr×nh nhËp/xuÊt l¹i kh«ng cã lîi cho

hiÖu suÊt.

ThuËt to¸n øng viªn ®−îc ph©n chia-c¬ së d÷ liÖu chung còng ®−îc thùc hiÖn,

trong ®ã c¸c bé xö lý t¹o nªn c¸c c©y øng viªn rêi nhau vµ duyÖt toµn bé c¬ së d÷

liÖu ®Ó tÝnh ®é hç trî. Tuy nhiªn, g¸nh nÆng nhËp/xuÊt vµ sù tranh chÊp vÒ kh«ng

gian lµ kh«ng thÓ chÊp nhËn ®−îc, nã khiÕn nhiÒu bé xö lý bÞ chËm l¹i. Do b¶n chÊt

cña phÐp b¨m, c¸c c©y b¨m c¸c øng viªn ®Þnh vÞ d÷ liÖu rÊt kÐm. H¬n n÷a, mét c©y

dïng chung cã thÓ dÉn tíi chia sÎ sai trong pha tÝnh ®é hç trî. NhiÒu c¬ chÕ vµ

chÝnh s¸ch ®−îc ®Ò xuÊt ®Ó ®iÒu chØnh c¸ch bè trÝ bé nhí cña hµm b¨m dùa trªn

viÖn truy nhËp c¸c mÉu ®Ó tÝnh ®é hç trî. S¬ ®å nµy ®¶m b¶o r»ng c¸c nót cã kh¶

n¨ng ®−îc truy cËp kÕ tiÕp nhau sÏ ®−îc ®Æt gÇn nhau vÒ mÆt vËt lý, ®iÒu nµy gióp

®Þnh vÞ tèt d÷ liÖu. Ngoµi ra cßn c¬ chÕ t− nh©n hãa, mçi bé xö lý tËp hîp c¸c sè

®Õm tõ mét m¶ng ®Þa ph−¬ng, tiÕp theo lµ rót gän tæng ®Ó gi¶m lçi chia sÎ.

(cid:131) ThuËt to¸n dùa trªn DIC

Cheung vµ céng sù ®Ò xuÊt thuËt to¸n ph¸t hiÖn song song kh«ng ®ång bé

(APM) dùa trªn DIC. ThuËt to¸n nµy sö dông kü thuËt tØa toµn phÇn cña thuËt to¸n

ph¸t hiÖn ph©n t¸n nhanh ®Ó gi¶m kÝch th−íc c¸c øng viªn 2-itemset. ViÖc c¾t tØa

nµy hiÖu qu¶ nhÊt khi gi÷a c¸c phÇn cã ®é lÖch d÷ liÖu lín. Tuy nhiªn, DIC ®ßi hái

r»ng c¸c phÇn ph¶i ®ång nhÊt. Ph¸t hiÖn song song kh«ng ®ång nhÊt chia c¬ së d÷

liÖu mét c¸ch hîp lý thµnh c¸c phÇn ¶o nhá, kÝch th−íc b»ng nhau. Sè c¸c phÇn ¶o l

®éc lËp víi sè bé xö lý p, th−êng th× l ≥ p. Gäi m lµ sè c¸c thuéc tÝnh, APM tËp hîp

c¸c sè ®Õm ®Þa ph−¬ng cña c¸c m thuéc tÝnh trong mçi phÇn. Nã t¹o ra tËp d÷ liÖu

lxm, víi l vÐct¬ ®é hç trî c¸c thuéc tÝnh vµ kh«ng gian m chiÒu. APM chia l vÐct¬

vµo k cluster, tèi ®a hãa kho¶ng c¸ch gi÷a c¸c cluster vµ gi¶m thiÓu kho¶ng c¸ch

trong mçi cluster. V× thÕ, k cluster cã ®é lÖch tèi ®a vµ chóng ®−îc dïng ®Ó t¹o c¸c

tËp øng viªn 2-itemset nhá.

-68-

TiÕp theo APM ¸p dông song song DIC, ý t−ëng lµ chia c¬ së d÷ liÖu thµnh p

phÇn ®ång nhÊt. Mçi bé xö lý ¸p dông ®éc lËp thuËt to¸n DIC trªn phÇn côc bé cña

m×nh. Tuy nhiªn, cã mét c©y tiÒn tè ®−îc x©y dùng kh«ng ®ång bé ®−îc chia sÎ

gi÷a c¸c bé xö lý. APM dõng khi tÊt c¶ c¸c bé xö lý ®· ®· xö lý hÕt c¸c øng viªn t¹o

bëi nã hay bëi bé xö lý kh¸c, vµ khi kh«ng cã øng viªn míi ®−îc t¹o thªm. §Ó ¸p

dông DIC trªn mçi phÇn, mçi bé xö lý ph¶i chia phÇn côc bé cña nã thµnh r phÇn

con. H¬n n÷a, DIC ®ßi hái r»ng c¶ p phÇn gi÷a c¸c bé xö lý vµ r phÇn trong mçi bé

xö lý ph¶i cµng ®ång nhÊt cµng tèt. APM ®¶m b¶o r»ng p phÇn lµ ®ång nhÊt b»ng

c¸ch g¸n c¸c phÇn ¶o tõ mçi cluster trong k cluster cña vßng lÆp ®Çu tiªn theo kiÓu

quay vßng gi÷a p bé xö lý. Do ®ã, mçi bé xö lý cã sù kÕt hîp c¸c phÇn ¶o nh− nhau

tõ c¸c cluster riªng biÖt, cho ra sù ph©n chia c¸c bé xö lý ®ång nhÊt.

§Ó cã tÝnh ®ång nhÊt gi÷a c¸c phÇn trong mçi bé xö lý, APM thùc hiÖn ph©n

k nhãm lÇn thø hai. Chóng nhãm r phÇn vµo k cluster, vµ l¹i g¸n c¸c phÇn tö tõ mçi

cluster vµo r phÇn theo c¸ch quay vßng. C¸c thÝ nghiÖm trªn 12-node Sun Enterprise

4000 chia sÎ bé nhí cho thÊy APM thùc hiÖn tèt h¬n c¸c thuËt to¸n Ph©n phèi sè

®Õm/CCPD tõ 4-5 lÇn. Mét sù tháa hiÖp thó vÞ trong APM lµ mÆc dï ®é lÖch d÷ liÖu

lµ tèt cho ®Ó c¾t tØa toµn phÇn, nã l¹i kh«ng tèt ®Ó c©n b»ng t¶i.

III.2.3. C¸c hÖ ph©n cÊp

Mét hÖ thèng ph©n cÊp cã c¶ c¸c phÇn víi bé nhí ph©n t¸n vµ bé nhí ®−îc

chia sÎ. C¸c hÖ thèng ph©n cÊp ®ang trë nªn ngµy cµng phæ biÕn, ®Æc biÖt víi sù

ph¸t triÓn cña c¸c m¸y tÝnh ®Ó bµn ®a xö lý vµ cña c¸c m¹ng tèc ®é cao. C¸c nhãm

nµy cung cÊp kh¶ n¨ng më réng vµ cã hiÖu suÊt ngang víi c¸c m¸y ®¾t tiÒn, nh−ng

víi gi¸ thµnh rÎ. Trong mét hÖ thèng ph©n cÊp, ta ph¶i tèi −u hãa truyÒn th«ng gi÷a

c¸c nót vµ ph©n t¸ch d÷ liÖu vµ tèi −u hãa sù ®Þnh vÞ d÷ liÖu trong mçi nót vµ tr¸nh

lçi chia sÎ cho mçi nót chia sÎ bé nhí.

-69-

(cid:131) ThuËt to¸n dùa trªn Eclat

Bèn thuËt to¸n ParEclat, ParMaxEclat, ParClique va ParMaxClique ®−îc ph¸t

triÓn dùa trªn bèn thuËt to¸n tuÇn tù t−¬ng øng. ThuËt to¸n ®ang xÐt gi¶ sö r»ng hÖ

thèng cã n m¸y chñ, mçi m¸y chñ gåm p nót chia sÎ bé nhí, c¬ së d÷ liÖu ®−îc

®Þnh d¹ng theo chiÒu däc vµ ®−îc ph©n chia gi÷a c¸c m¸y chñ sao cho mçi m¸y chñ

cã toµn bé danh s¸ch ®Þnh danh tidlist cña tÊt c¶ c¸c thuéc tÝnh ®¬n lÎ. Tæng chiÒu

dµi cña c¸c tidlist côc bé lµ xÊp xØ b»ng nhau trªn tÊt c¶ c¸c m¸y chñ.

C¶ 4 thuËt to¸n ®Òu cã c¸ch song song hãa t−¬ng tù vµ chØ kh¸c nhau ë chiÕn

l−îc t×m kiÕm, cã ký thu©th ph©n líp gièng nhau. Mçi thuËt to¸n ®Òu cã 3 pha

chÝnh:

- Pha n¹p gi¸ trÞ: thùc hiÖn tÝnh to¸n vµ ph©n chia d÷ liÖu

- Pha kh«ng ®ång bé: mçi bé xö lý ®éc lËp t¹o c¸c itemset phæ biÕn

- Pha rót gän: kÕt hîp c¸c kÕt qu¶ cuèi cïng.

Trong pha ®Çu tiªn, m¸y chñ t¹o tiÒn tè hoÆc c¸c líp c©n b»ng dùa trªn

clique, dïng c¸c 2-itemset phæ biÕn. TiÕp ®ã mét thuËt to¸n xÕp c¸c líp nµy vµo c¸c

bé xö lý s½n cã. Mçi líp cã mét ®é ®o dùa trªn sè c¸c phÇn tö cña nã. Sau ®ã thuËt

to¸n xÕp lÞch sÏ s¾p xÕp c¸c líp theo ®é ®o vµ g¸n líp cã ®é ®o lín nhÊt cho bé xö

lý cã tæng ®é ®o nhá nhÊt, vµ lÆp l¹i qu¸ tr×nh nµy cho c¸c líp theo thø tù ®−îc s¾p.

Sau khi s¾p xÕp xong líp cha, c¸c danh s¸ch ®Þnh danh ®èi t−îng tidlist ®−îc sao

chÐp mét c¸ch chän läc trªn mçi m¸y chñ, nhê thÕ tÊt c¶ c¸c tidlist lµ mét phÇn cña

líp ®−îc g¸n trªn mét bé xö lý sÏ cã s½n trªn æ ®Üa côc bé cña c¸c m¸y chñ. ChØ cã

c¸c m¸y chñ tham gia vµo qua tr×nh truyÒn th«ng nµy.

Trong pha thø hai, mçi bé xö lý cã s½n c¸c líp ®−îc g¸n cho nã, cïng danh

s¸ch ®Þnh danh cña tÊt c¶ c¸c thuéc tÝnh. V× thÕ, mçi bé xö lý cã thÓ ®éc lËp t¹o tÊt

c¶ c¸c itemset phæ biÕn tõ c¸c líp cña m×nh. Trong pha nµy kh«ng cÇn ®Õn sù truyÒn

th«ng vµ ®ång bé hãa. H¬n n÷a, toµn bé bé nhí hÖ thèng lµ s½n cã ®Ó sö dông,

-70-

kh«ng cÇn l−u trong bé nhí c©y tiÒn tè hoÆc c©y b¨m. ChØ cÇn ®Õn c¸c thao t¸c ®¬n

gi¶n ®Ó ®Õm c¸c itemset.

Bèn thuËt to¸n kh¸c nhau phô thuéc vµo chiÕn l−îc ph©n t¸ch vµ t×m kiÕm

®−îc dïng. ParEclat vµ ParMaxEclat dïng c¸c líp dùa trªn tiÒn tè, vµ dïng chiÕn

thuËt t×m kiÕm tõ d−íi lªn vµ t×m kiÕm lai. ParClique vµ ParMaxClique th× dïng c¸c

líp nhá dùa trªn clique, còng t−¬ng øng dïng c¸ch t×m kiÕm tõ d−íi lªn vµ t×m kiÕm

lai.

B¶ng d−íi ®©y cho thÊy sù kh¸c biÖt c¬ b¶n gi÷a c¸c ph−¬ng ph¸p kh¸c nhau

vµ nhãm c¸c thuËt to¸n cã liªn quan víi nhau. Ta còng thÊy lµ chØ cã mét sè Ýt c¸c

m« h×nh kh¸c nhau. NhiÒu thuËt to¸n ®Ò xuÊt sù tèi −u hãa cho c¸c thuËt to¸n kh¸c.

V× thÕ, c¸c ph−¬ng ph¸p song song nµy cã cïng ®é phøc t¹p vµ c¸c tÝnh chÊt cña c¸c

thuËt to¸n tuÇn tù c¬ së cña nã.

ThuËt to¸n Ph©n phèi sè ®Õm PEAR PDM NPA FDM FPM CCPD Ph©n phèi d÷ liÖu SPA IDD PCCD Ph©n phèi lai Ph©n phèi øng viªn HPA HPA-ELD ParEclat ParMaxEclat ParClique ParMaxClique

§Æc ®iÓm Dùa trªn Apriori C©y tiÒn tè c¸c øng viªn B¶ng b¨m cho c¸c 2-itemset, t¹o øng viªn song song ChØ c¸c m¸y chñ thùc hiÖn viÖc rót gän sè ®Õm C¾t tØa côc bé vµ toµn côc, kiÓm sè ®Õm C¾t tØa côc bé vµ toµn côc, xö lý ®é nghiªng cña d÷ liÖu Chia sÎ bé nhí Trao ®æi toµn bé c¬ së d÷ liÖu trong mçi lÇn lÆp Gièng nh− ph©n phèi d÷ liÖu TruyÒn th«ng b¸o theo vßng trßn, ph©n ®o¹n øng viªn dùa trªn thuéc tÝnh Chia sÎ bé nhí (trao ®æi c¬ së d÷ liÖu logic) KÕt hîp ph©n phèi sè ®Õm vµ ph©n phèi d÷ liÖu LÆp l¹i c¬ së d÷ liÖu mét c¸ch chän läc, kh«ng ®ång bé Kh«ng lÆp l¹i c¬ së d÷ liÖu, trao ®æi c¸c itemset LÆp l¹i c¸c itemset phæ biÕn Dùa trªn Eclat, kh«ng ®ång bé, cÊu tróc ph©n cÊp Dùa trªn MaxEclat, kh«ng ®ång bé, cÊu tróc ph©n cÊp Dùa trªn Clique, kh«ng ®ång bé, cÊu tróc ph©n cÊp Dùa trªn MaxClique, kh«ng ®ång bé, cÊu tróc ph©n cÊp

-71-

Dùa trªn DIC, chia sÎ bé nhí, kh«ng ®ång bé Dùa trªn ph©n ®o¹n, c¬ së d÷ liÖu theo chiÒu ngang

APM PPAR

III.3. m« h×nh tËp th« ph¸t hiÖn song song luËt kÕt hîp

Ch−¬ng 2 ®· ®Ò cËp tíi hai thuËt to¸n ph¸t hiÖn luËt kÕt hîp theo c¸ch tiÕp

cËn cña lý thuyÕt tËp th«. C¸c t¸c gi¶ [16] cã nhËn xÐt r»ng thuËt to¸n 2.1 kh«ng

thÝch hîp ®èi víi c¸c c¬ së d÷ liÖu (b¶ng quyÕt ®Þnh) víi sè l−îng thuéc tÝnh lín.

Trong thùc tÕ gi¶ thiÕt nµy lµ rÊt khã chÊp nhËn v× vËy c¸c t¸c gi¶ cho r»ng cÇn cã

giai ®o¹n tiÒn xö lý tr−íc khi ¸p dông c¸c thuËt to¸n. ThuËt to¸n 2.2 víi môc tiªu

t×m tËp tèi −u luËt kÕt hîp lµ mét trong c¸c gi¶i ph¸p ®−îc ®Ò xuÊt. Trong phÇn nµy,

ph¸t triÓn c¸c ý t−ëng tõ [16], chóng t«i x©y dùng mét m« h×nh ph¸t hiÖn song song

luËt kÕt hîp theo c¸ch tiÕp cËn tËp th«. M« h×nh nµy dùa trªn mét sè vÊn ®Ò liªn

quan ®Õn m« h×nh ph¸t hiÖn luËt kÕt hîp. Tr−íc hÕt chóng t«i xin ®Ò cËp tíi mét vÝ

dô xuÊt ph¸t tõ thùc tÕ t¹i Së Y tÕ Hµ Néi.

B¾t ®Çu tõ n¨m 2001, Së Y tÕ Hµ Néi cã kÕ ho¹ch x©y dùng hÖ thèng th«ng

tin cña toµn ngµnh vµ cña c¸c bÖnh viÖn do Së qu¶n lý bao gåm c¸c th«ng tin qu¶n

lý vµ c¸c th«ng tin chuyªn m«n [3]. Së Y tÕ Hµ Néi qu¶n lý hÖ thèng gåm 42 bÖnh

viÖn trªn ®Þa bµn Hµ Néi, bao gåm c¶ c¸c bÖnh viÖn ®a khoa vµ chuyªn khoa mµ

theo chøc n¨ng mçi bÖnh viÖn ch÷a trÞ mét chuyªn khoa hoÆc ®a khoa, vµ cßn ®−îc

ph©n bè theo l·nh thæ (c¸c bÖnh viÖn quËn, huyÖn). C¬ së d÷ liÖu kh¸m vµ ®iÒu trÞ

bÖnh cña hÖ thèng toµn Së ®−îc ph©n t¸n theo hÖ thèng 42 bÖnh viÖn nãi trªn. Mét

trong nh÷ng yªu cÇu ®−îc ®Æt ra ë ®©y lµ sö dông ®−îc c¸c d÷ liÖu bÖnh ¸n s½n cã

®Ó ®−a ra c¸c luËt cho thÊy mèi liªn hÖ gi÷a c¸c triÖu chøng cña bÖnh nh©n vµ kh¶

n¨ng bÞ bÖnh nµo ®ã cña hä. C¸c luËt nµy bao gåm c¸c luËt côc bé (cho mçi bÖnh

viÖn) vµ luËt toµn bé, kh«ng chØ ¸p dông cho mét bÖnh viÖn nµo ®ã mµ cßn ph¶i

®óng ®Ó ¸p dông cho toµn bé Thñ ®« Hµ Néi. LuËt côc bé (hy väng nhËn ®−îc) liªn

quan ®Õn ®Æc thï cña tõng lo¹i bÖnh (®èi víi c¸c bÖnh viÖn chuyªn khoa) hoÆc liªn

-72-

quan ®Õn ®Æc thï cña tõng vïng l·nh thæ (quËn - thµnh thÞ vµ huyÖn - n«ng th«ng,

møc sèng cao vµ møc sèng thÊp ...). LuËt toµn côc (hy väng nhËn ®−îc) liªn quan

®Õn ch−¬ng tr×nh chung trong toµn Hµ Néi ®Ó ®−a ra c¸c chÝnh s¸ch dù phßng, ch¨m

sãc søc khoÎ ban ®Çu ... còng nh− c¸c phßng chèng chung ®èi víi mçi lo¹i bÖnh.

Bµi to¸n trªn ®−îc ph¸t biÓu d−íi d¹ng tËp th« trong b¶ng quyÕt ®Þnh theo quan

®iÓm cña Pawlak nh− d−íi ®©y.

Trong tr−êng hîp d÷ liÖu côc bé ®−îc tr×nh bµy d−íi d¹ng mét hÖ th«ng tin

theo quan ®iÓm cña Pawlak vµ sö dông c¸c thuËt to¸n trong ch−¬ng 2 [16], chóng ta

cÇn t×m m« h×nh cho phÐp m« t¶ vÊn ®Ò ph¸t hiÖn tËp phæ biÕn toµn côc vµ tËp phæ

biÕn côc bé. D−íi ®©y lµ nh÷ng nÐt s¬ bé nhÊt vÒ m« h×nh nh− vËy.

Ph¸t biÓu c¸c néi dung trªn ®©y theo c¸ch diÔn ®¹t trong hÖ th«ng tin nh−

sau: Cho c¸c hÖ th«ng tin Si = (Oi, Ai, V, σi) trong ®ã víi i≠j th× Oi ∩ Oj = ∅, cho

phÐp Ai ∩ Aj ≠ ∅ vµ h¹n chÕ xÐt V={0, 1} (Gi¶ thiÕt V h¹n chÕ kh«ng ¶nh h−ëng

®Õn ho¹t ®éng cña m« h×nh vµ thuËt to¸n - xem thuËt to¸n 2.1 vµ 2.2; ë ®©y, cã gi¶

thiÕt nh− vËy cho ®¬n gi¶n). Nh− vËy mçi hÖ th«ng tin Si lµ mét hÖ th«ng tin côc bé,

chøa d÷ liÖu vÒ c¸c bÖnh ¸n t¹i bÖnh viÖn thø i, mçi ®èi t−îng o ∈ Oi lµ mét phiÕu

kh¸m bÖnh. §Æt O = ∪Oi, A = ∪Ai, x©y dùng hÖ th«ng tin S = (O, A, V, σ), trong

)

,

∈

∈

)

,( ao

=

σ

,( ao 0

AaOokhi i i ≠

σ ⎛ i ⎜⎜ ⎝

®ã σ ®−îc x¸c ®Þnh nh− sau:

Theo quan ®iÓm cña hÖ ph©n t¸n, hÖ th«ng tin Si (hÖ th«ng tin t¹i bÖnh viÖn do Së Y

tÕ Hµ Néi qu¶n lý) nhËn ®−îc tõ hÖ th«ng tin S (hÖ th«ng tin toµn bé Së Y tÕ Hµ

Néi) theo ph©n ®o¹n võa ngang võa däc (®Æc biÖt khi mäi Ai = A th× chóng ta cã

ph©n ®o¹n ngang, mäi Oi = O th× chóng ta cã ph©n ®o¹n däc). Gi¶ sö, chóng ta sö

-73-

dông thuËt to¸n ph¸t hiÖn luËt kÕt hîp ®èi víi mçi hÖ th«ng tin Si. Mét vÊn ®Ò ®−îc

quan t©m lµ mèi quan hÖ gi÷a luËt kÕt hîp trong S víi c¸c luËt ®· ph¸t hiÖn tõ tr−íc

trong c¸c Si.

Cã thÓ xem xÐt hai m« h×nh xö lý song song ®èi víi :

- M« h×nh tËp trung: Ph¸t hiÖn luËt kÕt hîp mµ d÷ liÖu ®· tËp trung t¹i

mét hÖ th«ng tin thèng nhÊt. Theo m« h×nh nµy chó ý ®Õn viÖc chia xÎ bé

nhí, nhiÒu bé d÷ liÖu cïng ®−îc ®−a vµo bé nhí ®Ó xö lý. Trong tr−êng hîp

nµy, c¸c hÖ th«ng tin con thùc chÊt ®−îc t¸ch ra tõ mét hÖ th«ng tin tËp trung.

- M« h×nh ph©n t¸n: D÷ liÖu t¹i c¸c hÖ thèng con Si lµ ph©n t¸n thùc sù.

ViÖc ph¸t hiÖn luËt kÕt hîp song song kh«ng chØ thùc hiÖn ®èi víi mçi hÖ con

mµ cßn cÇn ph¸t hiÖn luËt kÕt hîp cho toµn bé hÖ tæng thÓ.

C¸c phÇn tr×nh bµy d−íi ®©y giíi thiÖu c¸c gi¶i ph¸p ë møc ®é s¬ l−îc nhÊt

liªn quan ®Õn c¸c néi dung trªn.

III.2.1. ThuËt to¸n 3.1. (M« h×nh tËp trung)

KÕt hîp c¸c gîi ý cña [16] khi xem xÐt thuËt to¸n 1 ch−¬ng 2, vµ kh¶o s¸t hÖ

thèng Data Surveyor trong [8], chóng ta ®−a ra thuËt to¸n sau ®©y nh»m ph¸t hiÖn

song song luËt kÕt hîp. Trõ b−íc tiÒn xö lý, b−íc t¸ch hÖ th«ng tin vµ b−íc hîp nhÊt

kÕt qu¶, néi dung c¸c b−íc cßn l¹i t−¬ng øng nh− m« t¶ trong thuËt to¸n 2.1.

ThuËt to¸n 3.1: T×m tËp tèi −u c¸c luËt

Input: HÖ th«ng tin S gåm n ®èi t−îng trong mét tËp ®èi t−îng O, mèi ®èi

t−îng u cã thÓ cã m thuéc tÝnh.

Output: TËp tèi −u c¸c luËt cïng ®é m¹nh cña mçi luËt

-74-

Néi dung thuËt to¸n

B−íc 1: Ph©n nhãm ®èi t−îng thµnh c¸c nhãm dùa theo chØ tiªu cña c¸c

thuéc tÝnh b»ng c¸ch thùc hiÖn mét thuËt to¸n ph©n nhãm: O = ∪Oi,

A = ∪Ai víi chó ý lµ tËp ®èi t−îng còng nh− tËp thuéc tÝnh trong mçi

hÖ th«ng tin thµnh phÇn kh«ng nhÊt thiÕt rêi nhau. Ghi nhËn th«ng

tin träng sè cña mçi hÖ th«ng tin thµnh phÇn (cã thÓ chän lµ sè ®èi

t−îng cã trong Oi).

B−íc 2: Thùc hiÖn song song thuËt to¸n 2.1 víi d÷ liÖu ®Çu vµo lµ c¸c hÖ

th«ng tin thµnh phÇn Si. KÕt qu¶ nhËn ®−îc qua b−íc nµy lµ c¸c luËt

kÕt hîp côc bé trong mçi hÖ th«ng tin thµnh phÇn.

Qu¸ tr×nh thùc hiÖn b−íc 2 ®−îc tiÕn hµnh lµ viÖc kÕt hîp c¸c néi

dung trong thuËt to¸n 2.1 vµ m« h×nh tÝnh to¸n song song trong [8].

B−íc 3: Hîp nhÊt kÕt qu¶ thùc hiÖn ®−îc trong b−íc 2 víi c¸c träng sè ®èi

víi mçi hÖ th«ng tin thµnh phÇn.

III.2.2. ThuËt to¸n 3.2 (M« h×nh ph©n t¸n)

Trong tr−êng hîp d÷ liÖu trong hÖ thèng ®−îc ph©n t¸n trong c¸c hÖ th«ng tin

®Þa ph−¬ng thùc sù (kh«ng cã b−íc t¸ch hÖ th«ng tin) th× thuËt to¸n ph©n t¸n ®−îc

tr×nh bµy nh− sau.

ThuËt to¸n 3.2: T×m tËp tèi −u c¸c luËt

Input: TËp hîp c¸c hÖ th«ng tin Si = (Oi, Ai, V, σi), mçi Si gåm ni ®èi t−îng

trong tËp ®èi t−îng con Oi, Ai lµ tËp con cña A (TËp hîp thuéc tÝnh ®−îc

thèng nhÊt trong toµn bé hÖ th«ng tin S; ch¼ng h¹n, Së Y tÕ Hµ Néi

thèng nhÊt b¶ng m· vµ tªn c¸c thuéc tÝnh nµy trong toµn bé Së).

Output: TËp tèi −u c¸c luËt cïng ®é m¹nh cña mçi luËt côc bé còng nh− c¸c luËt

toµn côc.

-75-

Néi dung thuËt to¸n

B−íc 1: ¸p dông thuËt to¸n 2.1. cho c¸c hÖ th«ng tin thµnh phÇn Si, KÕt qu¶

nhËn ®−îc luËt kÕt hîp cña mçi b¶ng hÖ th«ng tin thµnh phÇn cïng

mét ®¹i l−îng lµ träng sè cña mçi hÖ th«ng tin thµnh phÇn ®ã.

B−íc 2: Hîp nhÊt luËt kÕt hîp tõ c¸c hÖ th«ng tin thµnh phÇn theo träng sè ®·

cã ®Ó nhËn ®−îc c¸c luËt kÕt hîp toµn côc.

KÕt qu¶ cña b−íc nµy bao gåm hai lo¹i luËt kÕt hîp:

- C¸c luËt kÕt hîp toµn côc sau khi hîp nhÊt ë b−íc 2,

- Líp c¸c luËt kÕt hîp côc bé lµ kÕt qu¶ cña b−íc 1.

Chóng t«i ®Ò xuÊt ý nghÜa cña c¸c kh¸i niÖm "träng sè" trong kÕt qu¶ b−íc 1

vµ kh¸i niÖm "hîp nhÊt" khi thùc hiÖn b−íc 2 nh− tr×nh bµy d−íi d©y.

KÕt qu¶ ¸p dông b−íc 1 ®èi víi Si lµ (coi hai thµnh phÇn ®Çu tiªn lµ träng sè):

• TËp Si c¸c thuéc tÝnh trong Si,

• Sè ni sè l−îng c¸c ®èi t−îng cã trong Si,

• {c¸c luËt ph¸t hiÖn ®−îc qua b−íc 1 ®èi víi Si}. Chóng t«i quan niÖm r»ng

mçi luËt ë ®©y bao gåm c¸c thµnh phÇn:

- LuËt víi ®é hç trî, ®é tin cËy t×m ®−îc,

- TËp c¸c thuéc tÝnh A*i xuÊt hiÖn trong luËt,

- Sè l−îng ni ®èi t−îng trong Si,

Chó ý r»ng, mét luËt cã thÓ ®−îc ph¸t hiÖn trong nhiÒu hÖ th«ng tin thµnh

phÇn víi c¸c ®é ®o hç trî vµ tin cËy kh¸c nhau.

BiÓu thøc sau ®©y tr×nh bµy néi dung hîp nhÊt ®Ó nhËn ®−îc c¸c luËt kÕt hîp

toµn côc (µ ¸p dông tÝnh to¸n cho mçi ®¹i l−îng hoÆc ®é hç trî hoÆc ®é tin cËy) tõ

c¸c luËt kÕt hîp côc bé X→Y:

-76-

*

(

))

X

Y

→

µ S

i

(

∑ ( n i ) YX A ⊆∪ i

)

X

( µ

Y =→

(

(3.1)

∑ n i ) YX A ⊆∪ i

C«ng thøc trªn ®−îc gi¶i thÝch nh− sau: Víi mét luËt X→Y nµo ®ã ph¸t hiÖn ë b−íc

1, ®Ó hîp nhÊt chóng ta xem xÐt:

- C¸c hÖ th«ng tin thµnh phÇn Si mµ Ai chøa X∪Y. ViÖc hîp nhÊt chØ liªn quan

®Õn c¸c hÖ th«ng tin thµnh phÇn nµy,

- Víi mçi hÖ th«ng tin thµnh phÇn trªn ®©y, luËt X→Y cã ®¹i l−îng µ cã gi¸ trÞ

®−îc ký hiÖu lµ µSi(X→Y) ®−îc cho bëi kÕt qu¶ b−íc 1 hoÆc b»ng 0 nÕu nh− kh«ng lµ kÕt

qu¶ cña b−íc 1.

- TÝnh to¸n µ(X→Y) toµn côc nh− c«ng thøc ®· cho.

- So s¸nh ®é hç trî vµ ®é tin cËy víi ng−ìng ®Ó quyÕt ®Þnh vÒ viÖc cã kÕt luËn

X→Y lµ luËt toµn côc hay kh«ng.

NhËn xÐt: 1. Víi ®Ò xuÊt trªn ®©y, cã thÓ ®Ó xÈy ra t×nh huèng "bá sãt" luËt kÕt hîp

toµn côc, xuÊt ph¸t tõ lý do b−íc 1 ®· lo¹i bá mét sè luËt côc bé d−íi ng−ìng v× vËy

chóng kh«ng ®−îc tÝnh to¸n trong c«ng thøc 3.1. §iÒu nµy cã thÓ kh¾c phôc b»ng

c¸ch gi¶m ng−ìng mét c¸ch thÝch hîp khi khai ph¸ luËt kÕt hîp t¹i c¸c hÖ th«ng tin

thµnh phÇn trong b−íc 1 ®Ó hîp nhÊt trong b−íc 2 vµ chó ý r»ng bæ sung ng−ìng

míi cho luËt kÕt hîp côc bé.

2. ThuËt to¸n 3.1 vµ 3.2. kh«ng chØ thùc hiÖn song song ®èi víi c¸c b¶ng

quyÕt ®Þnh thµnh phÇn mµ trong nhiÒu tr−êng hîp, do viÖc ph©n nhãm, sè thuéc tÝnh

-77-

trong c¸c b¶ng quyÕt ®Þnh thµnh phÇn ®· gi¶m ®i nhiÒu so víi b¶ng quyÕt ®Þnh

chung cho nªn ®é phøc t¹p tÝnh to¸n tæng céng ®−îc gi¶m ®i ®¸ng kÓ.

KÕt luËn ch−¬ng 3

L−îng d÷ liÖu bïng næ trong c¸c hÖ th«ng tin cïng víi sù ph¸t triÓn cña c¸c c¬ së

d÷ liÖu trùc tuyÕn ®· thóc ®Èy nhu cÇu vÒ khai ph¸ d÷ liÖu song song vµ ph©n t¸n.

TÝnh to¸n song song sÏ gãp phÇn gi¶m bít thêi gian vµ chi phÝ xö lý, cho hÖ thèng

kh¶ n¨ng ph¸t triÓn. NhiÒu thuËt to¸n ph¸t hiÖn song song luËt kÕt hîp ®−îc ph¸t

triÓn dùa trªn c¸c thuËt to¸n tuÇn tù cho c¸c nÒn phÇn cøng kh¸c nhau. C¸c thuËt

to¸n nµy ®−îc tæng kÕt vµ so s¸nh bëi Zaki [17], cung cÊp mét c¸i nh×n kh¸i qu¸t vÒ

sù ph¸t triÓn cña c¸c m« h×nh ph¸t hiÖn song song luËt kÕt hîp (môc 3.2). Trªn c¬ së

c¸c thuËt to¸n t×m hiÓu ®−îc ®· nªu ë ch−¬ng 2, chóng t«i ®Ò xuÊt m« h×nh ph¸t

hiÖn song song luËt kÕt hîp theo c¸ch tiÕp cËn tËp th« cho hÖ th«ng tin, víi viÖc

song song hãa ®−îc thùc hiÖn trªn c¸c b−íc d÷ liÖu cho c¸c m« h×nh tËp trung vµ

ph©n t¸n. Theo c¸ch tiÕp cËn nµy, c¸c luËt t×m ®−îc trong c¸c hÖ th«ng tin con ®−îc

sö dông ®Ó t×m ra c¸c luËt cã gi¸ trÞ trªn toµn hÖ thèng tæng thÓ, cã sö dông gi¸ trÞ

träng sè cho mçi hÖ con. Chóng t«i còng ®−a ra mét c«ng thøc ®Ó hîp nhÊt c¸c luËt

kÕt hîp côc bé ®Ó nhËn ®−îc luËt kÕt hîp toµn côc (c«ng thøc 3.1).

-78-

PhÇn kÕt luËn

Sau mét thêi gian thu thËp tµi liÖu, kh¶o s¸t vµ ph©n tÝch néi dung vÒ viÖc

ph¸t hiÖn song song luËt kÕt hîp theo c¸ch tiÕp cËn tËp th«, luËn v¨n ®· ®¹t ®−îc

nh÷ng kÕt qu¶ nh− sau:

- Tr×nh bµy ®−îc nh÷ng néi dung c¬ b¶n nhÊt cña mét trong nh÷ng lÜnh vùc

nghiªn cøu vµ triÓn khai thêi sù hiÖn nay lµ khai ph¸ d÷ liÖu vµ ph¸t hiÖn tri thøc

trong c¸c c¬ së d÷ liÖu mµ luËt kÕt hîp lµ mét trong nh÷ng tri thøc ®iÓn h×nh,

- Cïng víi viÖc tr×nh bµy c¸c ph−¬ng ph¸p khai ph¸ d÷ liÖu ®iÓn h×nh, luËn

v¨n còng ®Þnh h−íng vµo néi dung biÓu diÔn vµ khai ph¸ luËt kÕt hîp theo c¸ch tiÕp

cËn tËp th«. Nh÷ng kÕt qu¶ gÇn ®©y nhÊt vÒ néi dung nµy ®· ®−îc giíi thiÖu, ph©n

tÝch trong luËn v¨n.

- Ph¸t hiÖn luËt kÕt hîp nãi riªng còng nh− khai ph¸ d÷ liÖu nãi chung

trong nh÷ng c¬ së d÷ liÖu lín lµ mét c«ng viÖc ®ßi hái thêi gian tÝnh to¸n lín, v× vËy

luËn v¨n ®· tr×nh bµy mét sè m« h×nh, thuËt to¸n liªn quan ®Õn viÖc ph¸t hiÖn song

song luËt kÕt hîp, trong ®ã ®¸ng chó ý lµ c¸c thuËt to¸n 2.1 vµ 2.2.

- LuËn v¨n ®· ®Ò xuÊt s¬ bé mét m« h×nh ph¸t hiÖn luËt kÕt hîp song song

theo h−íng tiÕp cËn tËp th« trong hÖ th«ng tin vµ b¶ng quyÕt ®Þnh, trong ®ã quan

niÖm r»ng mét hÖ th«ng tin tæng qu¸t ®−îc tÝch hîp tõ c¸c hÖ th«ng tin thµnh phÇn.

Th«ng qua viÖc ®Þnh nghÜa tÝnh chÊt kÕt hîp luËt kÕt hîp trong m« h×nh nµy, luËn

v¨n còng giíi thiÖu mét thuËt to¸n s¬ bé vÒ ph¸t hiÖn song song luËt kÕt hîp trong

m« h×nh nh− vËy. LuËn v¨n còng ®Ò xuÊt ®−îc c«ng thøc tÝnh to¸n c¸c ®Æc tr−ng cña

luËt kÕt hîp toµn côc tõ c¸c luËt kÕt hîp côc bé (c«ng thøc 3.1) nh»m hoµn chØnh

thuËt to¸n 3.2. LuËn v¨n còng ®−a ra nhËn xÐt vÒ tÝnh hîp lý cña c«ng thøc tÝnh to¸n

®ã.

-79-

Trong qu¸ tr×nh nghiªn cøu ®Ó hoµn thµnh luËn v¨n th«ng qua viÖc tæng hîp

vµ ph©n tÝch néi dung chÝnh yÕu vÒ mét lÜnh vùc hÕt søc thêi sù lµ ph¸t hiÖn tri thøc

mµ cô thÓ lµ ph¸t hiÖn luËt kÕt hîp, thö nghiÖm ®Ò xuÊt s¬ bé mét m« h×nh ph¸t hiÖn

luËt kÕt hîp, chóng t«i nhËn thÊy h−íng nghiªn cøu vÒ khai ph¸ d÷ liÖu song song

nãi chung vµ ph¸t hiÖn luËt kÕt hîp song song nãi riªng lµ mét h−íng nghiªn cøu

cßn rÊt réng lín vµ lu«n lµ vÊn ®Ò thêi sù. Chóng t«i tiÕp tôc c«ng viÖc nghiªn cøu

theo c¸c néi dung sau ®©y:

- Ph¸t triÓn m« h×nh ph¸t hiÖn luËt kÕt hîp nh− ®· tr×nh bµy trong môc 3.3.

- Thö nghiÖm thuËt to¸n trong mét hÖ thèng tÝnh to¸n song song thùc sù,

tr−íc m¾t dùa trªn nÒn cña hÖ thèng PC-cluster t¹i Bé m«n c¸c HÖ thèng Th«ng tin,

khoa C«ng nghÖ, §¹i häc Quèc gia Hµ Néi.

-80-

Tµi liÖu tham kh¶o

Tµi liÖu tiÕng ViÖt

1. Hµ Quang Thôy. Mét sè vÊn ®Ò vÒ kh«ng gian xÊp xØ, tËp th« ®èi víi hÖ th«ng tin.

LuËn ¸n Phã TiÕn sÜ Khoa häc To¸n Lý, 1996

2. NguyÔn Thanh Thñy. Khai ph¸ d÷ liÖu: Kü thuËt vµ øng dông. Tr−êng thu "HÖ mê

vµ øng dông", 2001

3. Së Y tÕ Hµ Néi. §Ò c−¬ng chi tiÕt c¸c h¹ng môc ®Çu t− c«ng nghÖ th«ng tin t¹i Së

Tµi liÖu tiÕng Anh

Y tÕ Hµ Néi n¨m 2001.

4. Rakesh Agrawal, John Shafer. Parallel Mining of Association Rules. IBM Almaden

Research Center, 1996

5. Rakesh Agrawal, Heikki Mannila, Ramakrishaman Skikant, Hannu Toivonen, A.

Inkeri Verkamo. Fast Discovery of Association Rules. Advances Knowledge

Discovery and Data Mining. AAAI Press/ MIT Press, 1996.

6. Ho Tu Bao, Nguyen Duc Dung. Integration of Rule Induction and Association Rule

Mining. The 1st Workshop of International Joint Research "Parallel Computing,

Data Mining and Optical Networks", 2001

7. Usama M. Fayyad, Gregory Piatetsky-Shapiro, Padhraic Smyth. From Dataming to

Knowledge Discovery: An Overview. Advances Knowledge Discovery and Data

Mining. AAAI Press/ MIT Press, 1996.

-81-

8. Marcel Holsheimer, Martin L. Kersten, Arno P.J.M. Siebes. Data Surveyor:

Searching the Nuggets in Parallel. Advances Knowledge Discovery and Data

Mining. AAAI Press/ MIT Press, 1996.

9. Boris Kovalerchuk, Evgenii Vityaev. Data Mining in Finance: Advances in

Relational and Hybrid Methods. Kluwer Academic Publishers, 2001

10. Vipin Kumar, Mohammed Zaki. High Performance Data Mining.

11. Milan Milenkovic. Operating Systems: Concepts and Design. McGraw-Hill Inc.,

1992.

12. Tetsuya Murai, Yoshiharu Sato. Association Rules from the Point of View of Modal

Logic and Rough Set. The 4th Asian Fuzzy Systems Symposium, 2000

13. S. Parthasarathy, S. Dwarkadas, M. Ogihara. Active Mining in a Distributed

Setting. SIGKDD Workshop on Large-Scale Parallel KDD Systems, 1999

14. Zdzislaw Pawlak. Rough Sets: Theoretical Aspects of Reasoning about Data.

Kluwer Academic Publishers, 1991.

15. D.B. Skilicorn. Strategies for Parallel Data Mining. External Technical Report, 1999

16. Andrzej Skowron, Ning Zong. Rough Sets in KDD. Tutorial Notes, 2000

17. Mohammed J. Zaki. Parallel and Distributed Association Mining: A Survey. IEEE

Concurrency, 1999.