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

Chia sẻ: Bluesky_12 Bluesky_12 | Ngày: | Loại File: PDF | Số trang:82

Thêm vào BST

Báo xấu

159
lượt xem 57
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tính toán song song là một hình thức tính toán trong đó nhiều phép tính được thực hiện đồng thời,[1] hoạt động trên nguyên tắc là những vấn đề lớn đều có thể chia thành nhiều phần nhỏ hơn, sau đó được giải quyết tương tranh ("trong lĩnh vực tính toán"). Có nhiều hình thức khác nhau của tính toán song song: song song cấp bit, song song cấp lệnh, song song dữ liệu, và song song tác vụ.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 Néi dung Trang 3 PhÇn më ®Çu 8 Ch−¬ng 1. tæng quan vÒ khai ph¸ d÷ liÖu vµ khai ph¸ d÷ liÖu song song 8 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 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 20 1.2. Khai ph¸ d÷ liÖu song song 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 31 KÕt luËn ch−¬ng 1 32 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 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 51 52 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 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 75 PhÇn kÕt luËn 77 Tµi liÖu tham kh¶o
-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.