Nội dung

 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