Tài liệu 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 Néi dung Trang PhÇn më ®Çu 3 Ch−¬ng 1. tæng quan vÒ khai ph¸ d÷ liÖu vµ 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 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 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÷ liÖu 1.2. Khai ph¸ d÷ liÖu song song 17 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 KÕt luËn ch−¬ng 1 Ch−¬ng 2. LuËt kÕt hîp theo c¸ch tiÕp cËn cña lý thuyÕt tËp th« 2.1. Kh¸i niÖm luËt kÕt hîp vµ mét sè c«ng nghÖ ph¸t hiÖn 31 32 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 KÕt luËn ch−¬ng 2 Ch−¬ng 3. Ph¸t hiÖn song song luËt kÕt hîp 3.1. Kh«ng gian thiÕt kÕ song song 51 52 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 KÕt luËn ch−¬ng 3 74 PhÇn kÕt luËn 75 Tµi liÖu tham kh¶o 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.