intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Luận văn:Học máy, học máy mô tả phức;thuật toán và vấn đề rút gọn lỗi

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

Thêm vào BST
Báo xấu
113
lượt xem 43
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong phạm vi Tin học, ta có thể quan niệm bài toán là việc nào đó ta muốn máy tính thực hiện. Viết một dòng chữ ra màn hình, giải phương trình bậc hai, quản lí điểm trong trường học v.v… Khi dùng máy tính giải bài toán, ta cần quan tâm đến hai yếu tố: đưa vào máy thông tin gì (Input) và cần lấy ra thông tin gì (Output). Do đó để phát biểu một bài toán ta cần phải chỉ rõ Input và Output của bài toán đó....

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:Học máy, học máy mô tả phức;thuật toán và vấn đề rút gọn lỗi

  1. bé gi¸o dôc vµ ®µo t¹o ®¹i häc quèc gia hµ néi tr−êng ®¹i häc khoa häc tù nhiªn ****** l−¬ng song v©n Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi luËn ¸n th¹c sü khoa häc chuyªn ngµnh tin häc ng−êi h−íng dÉn khoa häc: PTS. Hµ Quang Thôy hµ néi - 1999
  2. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n Môc lôc Néi dung Trang 3 PhÇn më ®Çu 6 Ch−¬ng 1. Bµi to¸n häc m¸y vµ mét sè thuËt to¸n I.1. Bµi to¸n häc m¸y 6 I.1.1. Bµi to¸n häc m¸y 6 I.1.2. Mét sè ®Æc tr−ng trong häc m¸y 7 I.1.3. Ph−¬ng ph¸p ®iÓn h×nh biÓu diÔn tri thøc trong häc m¸y 9 I.2. ThuËt to¸n ®iÓn h×nh trong häc m¸y 10 I.2.1. ThuËt to¸n t¸ch nhãm 10 I.2.2. ThuËt to¸n ph©n líp Bayes 14 I.2.3. ThuËt to¸n ph©n líp k-ng−êi l¸ng giÒng gÇn nhÊt 18 I.2.4. ThuËt to¸n c©y quyÕt ®Þnh 20 21 Ch−¬ng 2. Häc m¸y m« t¶ phøc II.1. M« h×nh häc m¸y m« t¶ phøc 21 II.1.1. S¬ bé vÒ m« h×nh häc m¸y m« t¶ phøc 21 II.1.2. Mét sè néi dung cña häc m¸y m« t¶ phøc 23 II.2. Mét sè kh¸i niÖm vµ tr×nh bµy tri thøc trong häc m¸y m« t¶ 26 phøc II.2.1 Mét sè kh¸i niÖm 26 II.2.2 Tr×nh bµy tri thøc trong häc m¸y m« t¶ phøc 27 II.3. Mét sè m« h×nh häc m¸y m« t¶ phøc 33 II.3.1. M« h×nh POIL 33 II.3.2. M« h×nh POCL 37 II.3.3. M« h×nh HYDRA 42 II.3.4. M« h×nh HYDRA-MM 45 -1-
  3. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n 49 Ch−¬ng 3. Rót gän lçi trong häc m¸y m« t¶ phøc III.1. S¬ bé vÒ rót gän lçi trong häc m¸y m« t¶ phøc 49 III.1.1. Mét sè kh¸i niÖm 49 III.1.2. S¬ bé vÒ rót gän lçi trong häc m¸y m« t¶ phøc 49 III.2. Mét sè néi dung vÒ rót gän lçi trong häc m¸y m« t¶ phøc 55 III.2.1. Sö dông tËp luËt phøc cho lçi thÊp h¬n 55 III.2.2. Mèi quan hÖ gi÷a gi¶m lçi vµ c¸c lçi t−¬ng quan 57 III.2.3. Thu thËp c¸c mèi quan hÖ vµ rót gän lçi 58 III.2.4. T¸c ®éng cña nhiÔu 59 III.2.5. T¸c ®éng cña thuéc tÝnh kh«ng thÝch hîp 60 III.2.6. T¸c ®éng cña viÖc ®a d¹ng ho¸ 62 64 Ch−¬ng 4. ThuËt to¸n t×m kiÕm vµ ph©n líp trong c¬ së d÷ liÖu full-text IV.1. C¬ së d÷ liÖu full-text 64 IV.1.1. Kh¸i niÖm vÒ c¬ së d÷ liÖu full-text 64 IV.1.2. C¸c néi dung c¬ b¶n cña mét c¬ së d÷ liÖu full-text 66 IV.1.3. C¸c m« h×nh qu¶n lý vµ l−u tr÷ th«ng tin v¨n b¶n 69 IV.2. ThuËt to¸n t×m kiÕm vµ ph©n líp trong c¬ së d÷ liÖu full-text 72 theo m« h×nh vector c¶i tiÕn IV.2.1. M« h×nh vector c¶i tiÕn vµ thuËt to¸n t×m kiÕm 73 IV.2.2. ThuËt to¸n ph©n líp Bayes thø nhÊt 79 IV.2.3. ThuËt to¸n ph©n líp Bayes thø hai 83 IV.2.4. ThuËt to¸n ph©n líp k-ng−êi l¸ng giÒng gÇn nhÊt 86 90 PhÇn kÕt luËn 92 Tµi liÖu tham kh¶o -2-
  4. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n PhÇn më ®Çu Häc m¸y (häc tù ®éng) lµ mét lÜnh vùc quan träng trong Tin häc, ®Æc biÖt ®èi víi lÜnh vùc c«ng nghÖ tri thøc. Môc tiªu chÝnh cña häc m¸y lµ t¹o ra c¸c ph−¬ng ph¸p vµ ch−¬ng tr×nh lµm cho m¸y tÝnh cã thÓ häc ®−îc nh− ng−êi. RÊt nhiÒu c«ng tr×nh nghiªn cøu vÒ lý thuyÕt vµ triÓn khai ®· ®−îc c«ng bè trong lÜnh vùc häc m¸y mµ phÇn lín ®−îc tËp hîp trong t¹p chÝ kh¸ næi tiÕng "Machine Learning" do nhµ xuÊt b¶n Kluwer Ên hµnh. LÜnh vùc häc m¸y cã quan hÖ mËt thiÕt víi lÜnh vùc ph¸t hiÖn tri thøc ([1, 3, 11]) vµ v× vËy hiÖn nay, sè l−îng c¸c nghiªn cøu vÒ häc m¸y vÉn ®ang ngµy cµng ph¸t triÓn víi tèc ®é cao. ë ViÖt nam, ®· cã nhiÒu nhµ khoa häc quan t©m ®Õn lÜnh vùc nãi trªn vµ nhiÒu c«ng tr×nh nghiªn cøu cã gi¸ trÞ ®· ®−îc c«ng bè ([1]). LÜnh vùc häc m¸y cã liªn quan mËt thiÕt víi nhiÒu lÜnh vùc kh¸c nhau cña To¸n häc vµ Tin häc. NhiÒu m« h×nh, nhiÒu ph−¬ng ph¸p trong häc m¸y cã quan hÖ mËt thiÕt víi c¸c m« h×nh To¸n häc nh− dµn Galois [2], lý thuyÕt Bayes [6, 7, 8, 13, 14] v.v. LuËn v¨n "Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi" cã néi dung ®Ò cËp tíi mét sè m« h×nh, thuËt to¸n ®iÓn h×nh trong häc m¸y. Hai néi dung c¬ b¶n ®−îc tr×nh bµy trong luËn v¨n lµ c¸c thuËt to¸n ®iÓn h×nh vµ vÊn ®Ò rót gän lçi trong häc m¸y. Häc m¸y m« t¶ phøc lµ mét m« h×nh häc m¸y nh»m gi¶m thiÓu lçi trong häc m¸y cã gi¸m s¸t ®ang ®−îc nghiªn cøu réng r·i trªn thÕ giíi hiÖn nay ([2, 6, 7, 8, 13, 14]) còng ®−îc tr×nh bµy trong luËn v¨n. Néi dung cña luËn v¨n bao gåm bèn ch−¬ng ®−îc tr×nh bµy nh− d−íi ®©y. Ch−¬ng 1 víi tiªu ®Ò "Bµi to¸n häc m¸y vµ mét sè thuËt to¸n" ®Ò cËp tíi nh÷ng vÊn ®Ò chung nhÊt cña bµi to¸n häc m¸y: häc m¸y kh«ng gi¸m s¸t vµ häc m¸y cã gi¸m s¸t, c¸c thuËt to¸n ®iÓn h×nh trong t¸ch nhãm (häc kh«ng gi¸m s¸t) vµ ph©n líp (häc cã gi¸m s¸t). C¸c thuËt to¸n Bayes, k-ng−êi l¸ng giÒng gÇn nhÊt, thuËt to¸n c©y quyÕt ®Þnh v.v. ®−îc giíi thiÖu. C¸c néi dung nãi trªn ®−îc tæng hîp tõ c¸c tµi liÖu ([1, 2, 6, 7, 11, 14]). -3-
  5. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n Ch−¬ng 2 víi tiªu ®Ò "Häc m¸y m« t¶ phøc" giíi thiÖu mét sè m« h×nh häc m¸y m« t¶ phøc ®−îc ®Ò x−íng vµ ph¸t triÓn t¹i tr−êng §¹i häc Tæng hîp California, Ivrin. LuËn v¨n tr×nh bµy néi dung c¬ b¶n vÒ c¸c m« h×nh häc m¸y m« t¶ phøc, c¸c thuËt to¸n ph©n líp ¸p dông trong c¸c m« h×nh häc m¸y m« t¶ phøc tõ FOIL ®Õn HYDRA-MM. C¸c chiÕn l−îc "chia nhá ®Ó chÕ ngù", "leo ®åi ngÉu nhiªn" v.v., c¸c thuËt to¸n Bayes, k-ng−êi l¸ng giÒng gÇn nhÊt ®−îc m« t¶ trong mçi m« h×nh häc. LuËn v¨n còng giíi thiÖu sù tiÕn bé cña m« h×nh míi so víi m« h×nh s½n cã. C¸c néi dung nãi trªn ®−îc tæng hîp tõ c¸c tµi liÖu ([6, 7, 8, 14]). Ch−¬ng 3 víi tiªu ®Ò "Rót gän lçi trong häc m¸y" ®Ò cËp tíi mét sè néi dung liªn quan ®Õn lçi vµ rót gän lçi trong häc m¸y vµ häc m¸y m« t¶ phøc. C¸c kh¸i niÖm vÒ lçi tuyÖt ®èi, lçi t−¬ng ®èi, lçi t−¬ng quan ®−îc tr×nh bµy. M« h×nh häc m¸y m« t¶ phøc lµ mét gi¶i ph¸p hiÖu qu¶ trong viÖc rót gän lçi. Mét sè gi¶i ph¸p vÒ thuéc tÝnh kh«ng t−¬ng øng, ®a d¹ng ho¸ d÷ liÖu, tæ hîp chøng cø v.v. ®−îc giíi thiÖu vµ ph©n tÝch vÒ kh¶ n¨ng rót gän lçi cña mçi gi¶i ph¸p. Mét sè ®¸nh gi¸ thùc nghiÖm cña c¸c t¸c gi¶ m« h×nh còng ®−îc nªu ra nh»m minh häa tÝnh hiÖu qu¶ cña c¸c gi¶i ph¸p. C¸c néi dung trong ch−¬ng nµy ®−îc rót ra tõ c¸c tµi liÖu [5-11] vµ ®Æc biÖt lµ tõ c«ng tr×nh cña Ali. K. & Pazzani M. [5]. Ch−¬ng 4 víi tiªu ®Ò "ThuËt to¸n t×m kiÕm vµ ph©n líp trong c¬ së d÷ liÖu full-text" tr×nh bµy c¸c néi dung liªn quan ®Õn hai bµi to¸n ®iÓn h×nh trong c¬ së d÷ liÖu full-text, ®ã lµ t×m kiÕm vµ ph©n líp. Néi dung cña ch−¬ng nµy lµ sù ph¸t triÓn mét sè néi dung ®· ®−îc tr×nh bµy trong [4, 11]. Sö dông m« h×nh vector trong thuËt to¸n ph©n líp lµ mét thÓ hiÖn cô thÓ c¸c néi dung t−¬ng øng trong [11] vµ cho phÐp thuËt to¸n ho¹t ®éng víi tèc ®é nhanh. LuËn v¨n ®Ò xuÊt mét sè c¶i tiÕn trong m« h×nh vector trong vÊn ®Ò tõ ®ång nghÜa vµ sè l−îng xuÊt hiÖn tõ khãa víi hai môc ®Ých: thÓ hiÖn tèt h¬n néi dung v¨n b¶n vµ t¨ng tèc ®é thùc hiÖn c¸c thuËt to¸n. Do sù h¹n chÕ vÒ tr×nh ®é vµ thêi gian nªn luËn v¨n míi -4-
  6. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n ph¸c ho¹ ý t−ëng vÒ mét hÖ qu¶n trÞ c¬ së full-text cã cµi ®Æt c¸c thuËt to¸n trªn ®©y. Em xin ch©n thµnh bµy tá lßng biÕt ¬n s©u s¾c tíi thÇy gi¸o - PTS. Hµ Quang Thuþ, ng−êi ®· tËn t×nh h−íng dÉn, t¹o ®iÒu kiÖn gióp ®ì vµ bæ sung cho em nhiÒu kiÕn thøc quý b¸u trong suèt qu¸ tr×nh em lµm luËn v¨n. Em còng xin c¶m ¬n thÇy PGS. TS. NguyÔn Xu©n Huy vµ thÇy PTS. NguyÔn TuÖ ®· ®ãng gãp nhiÒu ý kiÕn gióp em hoµn chØnh h¬n luËn v¨n cña m×nh. Cuèi cïng, em xin ch©n thµnh c¶m ¬n tÊt c¶ c¸c thÇy c« gi¸o trong khoa C«ng NghÖ Th«ng Tin (tr−íc ®©y) vµ khoa C«ng NghÖ (hiÖn nay), còng nh− phßng Khoa häc vµ ®µo t¹o sau ®¹i häc, tr−êng §¹i häc Khoa häc Tù nhiªn ®· t¹o ®iÒu kiÖn gióp ®ì vÒ c¸c ph−¬ng tiÖn nghiªn cøu, gióp em hoµn thµnh mäi thñ tôc ®Ó em ®−îc b¶o vÖ luËn v¨n nµy. Häc viªn L−¬ng Song V©n -5-
  7. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n Ch−¬ng 1. bµi to¸n Häc m¸y vµ mét sè thuËt to¸n I.1. Bµi to¸n häc m¸y I.1.1. Bµi to¸n häc m¸y Häc m¸y (machine learning) ®−îc hiÓu nh− mét qu¸ tr×nh gåm hai giai ®o¹n: giai ®o¹n häc vµ giai ®o¹n ¸p dông nh»m tù ®éng nhËn râ ®Æc tr−ng vÒ ®èi t−îng. Mçi lÜnh vùc ®−îc con ng−êi quan t©m lu«n lu«n liªn quan ®Õn tËp hîp c¸c kh¸i niÖm. Tõ nh÷ng kinh nghiÖm ®· häc theo mét sè mÉu cho tr−íc, cÇn ph¸t hiÖn ®Æc tr−ng cña mét ®èi t−îng míi. Häc m¸y cßn ®−îc quan niÖm nh− lµ mét qu¸ tr×nh thùc hiÖn c¸c kü x¶o, mµ nhê ®ã, tri thøc ®−îc thu nhËn th«ng qua kinh nghiÖm. Môc tiªu chÝnh cña häc m¸y lµ t¹o ra c¸c ph−¬ng ph¸p vµ ch−¬ng tr×nh lµm cho m¸y tÝnh "cã thÓ häc ®−îc" nh− ng−êi. Tuy nhiªn, trong mét sè ph¹m vi nghiªn cøu hÑp h¬n, bµi to¸n häc m¸y ®−îc quan niÖm mét c¸ch ®¬n gi¶n d−íi d¹ng bµi to¸n "ph©n líp": xÕp mét ®èi t−îng nµo ®ã vµo mét trong nh÷ng líp ®−îc coi lµ ®· biÕt. Bµi to¸n häc m¸y cã thÓ ®−îc tr×nh bµy mét c¸ch h×nh thøc nh− d−íi ®©y. Gi¶ sö tån t¹i mét tËp c¸c kh¸i niÖm nÒn Ko (tËp kh¸i niÖm nÒn Ko cã thÓ ch−a biÕt) t−¬ng øng víi mét ph©n ho¹ch d÷ liÖu ®èi víi mét miÒn D nµo ®ã. Tån t¹i ¸nh x¹ ®a trÞ M tõ Ko vµo 2D theo ®ã øng víi mçi kh¸i niÖm nÒn x thuéc Ko tíi mét tËp d÷ liÖu (®−îc gäi lµ c¸c vÝ dô mÉu øng víi kh¸i niÖm x) thuéc miÒn D. Mét kh¸i niÖm nÒn ®Æc tr−ng cho mét líp ®èi t−îng. Më réng tËp kh¸i niÖm nÒn Ko tíi tËp kh¸i niÖm K (Ko ⊆ K) ®−îc gäi lµ tËp c¸c kh¸i niÖm. Cho biÕt tån t¹i ¸nh x¹ nµo ®ã tõ Ko tíi K \ Ko (¸nh x¹ nãi trªn cã thÓ ch−a biÕt) cho phÐp b»ng c¸ch nµo ®ã nhËn biÕt mét kh¸i niÖm th«ng qua mèi quan hÖ víi c¸c kh¸i niÖm nÒn. -6-
  8. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n Qu¸ tr×nh häc m¸y ®−îc ph©n chia thµnh hai giai ®o¹n vµ t−¬ng øng víi hai giai ®o¹n ®ã, kÕt qu¶ cña häc m¸y cã hai d¹ng nh− tr×nh bµy d−íi ®©y. - KÕt qu¶ cña viÖc häc m¸y cho ra tËp kh¸i niÖm K, tËp kh¸i niÖm nÒn Ko vµ ¸nh x¹ L tõ Ko tíi mét tËp c¸c luËt suy diÔn liªn quan tíi mçi kh¸i niÖm nÒn (Tr−êng hîp ®Æc biÖt, tËp kh¸i niÖm K vµ tËp kh¸i niÖm nÒn Ko lµ ®· biÕt). Theo ¸nh x¹ nµy, mçi kh¸i niÖm nÒn ®−îc t−¬ng øng víi mét sè luËt suy diÔn d¹ng Horn - cÊp 1. KiÓu häc nµy ®−îc gäi lµ "häc kh«ng gi¸m s¸t" theo nghÜa kh«ng cã mét ¸p ®Æt tõ tr−íc ®èi víi qu¸ tr×nh häc do th«ng tin vÒ m« h×nh lµ rÊt Ýt. Mét d¹ng ®Æc biÖt cña häc m¸y kh«ng gi¸m s¸t lµ t¸ch (ph©n ho¹ch) mét tËp ®èi t−îng thµnh mét sè nhãm (®o¹n) ®èi t−îng víi mét sè ®Æc tr−ng nµo ®ã. Bµi to¸n häc d¹ng nµy ®−îc gäi lµ bµi to¸n t¸ch nhãm (t¸ch ®o¹n). - Gi¶ sö ®· cã ¸nh x¹ L nãi trªn (tõ mçi kh¸i niÖm nÒn thuéc Ko tíi c¸c m« t¶ t−¬ng øng) vµ phÐp biÓu diÔn mét kh¸i niÖm th«ng qua c¸c kh¸i niÖm nÒn. Bµi to¸n ®Æt ra lµ cÇn t×m ra kh¸i niÖm t−¬ng øng víi vÝ dô ®−îc hÖ thèng tiÕp nhËn. Häc m¸y kiÓu nµy cßn ®−îc gäi lµ "häc cã gi¸m s¸t" theo nghÜa ®· h−íng ®Ých tíi tËp kh¸i niÖm K. Cã thÓ sö dông mét sè c¸ch thøc ®o¸n nhËn tr−íc ®èi víi c¸c kh¸i niÖm ®Ó nhanh chãng ph¸t hiÖn kh¸i niÖm t−¬ng øng víi vÝ dô. Mét d¹ng ®Æc biÖt cña häc cã gi¸m s¸t lµ ph©n mét ®èi t−îng vµo líp thÝch hîp trong mét tËp c¸c líp cho tr−íc. Bµi to¸n häc kiÓu nµy ®−îc gäi lµ "bµi to¸n ph©n líp". I.1.2. Mét sè ®Æc tr−ng trong häc m¸y C¸c ph−¬ng ph¸p häc m¸y th−êng ®−îc ph©n lo¹i theo b¶n chÊt cña d÷ liÖu ®−îc sö dông cho qu¸ tr×nh häc. T−¬ng øng víi ph−¬ng ph¸p häc kh«ng gi¸m s¸t lµ qu¸ tr×nh m¸y cÇn ph¸t hiÖn ra c¸c kh¸i niÖm dùa trªn mét tËp thÓ hiÖn ch−a biÕt thuéc vÒ kh¸i niÖm nµo. T−¬ng øng víi ph−¬ng ph¸p häc cã gi¸m s¸t lµ qu¸ tr×nh m¸y tÝnh cÇn t×m ra ®Æc tr−ng cña c¸c kh¸i niÖm dùa trªn tËp c¸c thÓ hiÖn (instances) ®· biÕt vÒ kh¸i niÖm nµy. -7-
  9. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n Häc m¸y kh«ng gi¸m s¸t (bµi to¸n t¸ch nhãm) cÇn ®¹t ®−îc mét sè môc tiªu nh− sau [2]: - Ph©n r· tËp ®èi t−îng thµnh c¸c tËp con, mçi tËp con ®ã t−¬ng øng víi mét kh¸i niÖm (t¸ch nhãm). ChÝnh b¶n th©n kh¸i niÖm còng ®−îc ph¸t hiÖn trong qu¸ tr×nh häc m¸y. Trong mét sè tr−êng hîp riªng, qu¸ tr×nh t¸ch nhãm cßn ®−îc thÓ hiÖn d−íi d¹ng c©y nªn qu¸ tr×nh häc m¸y d¹ng nµy ®−îc gäi lµ ph©n lo¹i ph©n cÊp (hierarchical clustering). - T×m ra ®Æc tr−ng cña c¸c tËp con ®· ®−îc ph©n ho¹ch trong qu¸ tr×nh ph©n r·. Nh÷ng ®Æc tr−ng nµy ®−îc dïng cho viÖc ph©n líp mét ®èi t−îng vµo mét tËp con. Qu¸ tr×nh nµy cßn ®−îc gäi lµ ®Æc tr−ng ho¸ c¸c kh¸i niÖm. LuËt suy diÔn d¹ng Horn-cÊp 1 lµ mét trong nh÷ng d¹ng biÓu diÔn ®iÓn h×nh vÒ ®Æc tr−ng ho¸ c¸c kh¸i niÖm ([6, 7, 8]). Tuy nhiªn, trong nhiÒu tr−êng hîp m« h×nh sö dông mét tËp mÉu thay cho mét kh¸i niÖm do ch−a thÓ t×m ra ®−îc biÓu diÔn ®èi víi c¸c kh¸i niÖm t−¬ng øng. Nh− ®· ®−îc tr×nh bµy, do bµi to¸n häc m¸y kh«ng gi¸m s¸t tiÕp nhËn rÊt Ýt th«ng tin ®Çu vµo vµ v× vËy, ch−a cã ®−îc nhiÒu kÕt qu¶ nghiªn cøu vµ c«ng nghÖ gi¶i quyÕt bµi to¸n ([2]). PhÇn sau cña luËn v¨n sÏ tr×nh bµy mét sè gi¶i ph¸p chung nhÊt ®èi víi bµi to¸n häc m¸y kh«ng gi¸m s¸t. Mét d¹ng ®¬n gi¶n cña thuËt to¸n häc m¸y kh«ng gi¸m s¸t ®−îc tr×nh bµy trong [2], trong ®ã nghiªn cøu sù thay ®æi cña hÖ thèng kh¸i niÖm cïng c¸c ®Æc tr−ng cña chóng khi d÷ liÖu ®−îc thay ®æi. NhiÒu d¹ng kh¸c nhau cña häc m¸y kh«ng gi¸m s¸t ®¨ ®−îc kh¶o s¸t mµ viÖc nghiªn cøu vÒ sù phô thuéc th« lµ mét trong nh÷ng d¹ng ®iÓn h×nh ([03]). Kh¸c víi häc m¸y kh«ng gi¸m s¸t, häc m¸y cã gi¸m s¸t thu nhËn ®−îc nhiÒu thµnh tùu c¶ vÒ lý luËn lÉn triÓn khai øng dông. D−íi ®©y lµ mét sè néi dung ®Æc tr−ng cña häc m¸y cã gi¸m s¸t: - Trong mét sè m« h×nh häc m¸y cã gi¸m s¸t, viÖc ®Æc tr−ng ho¸ mçi kh¸i niÖm (mçi nhãm d÷ liÖu) ®−îc thÓ hiÖn th«ng qua viÖc m« t¶ mét tËp vÝ dô ®iÓn -8-
  10. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n h×nh t−¬ng øng víi kh¸i niÖm ®ã. Th«ng qua mét kho¶ng c¸ch gi÷a c¸c ®èi t−îng ®−îc x¸c ®Þnh mét c¸ch thÝch hîp, nhiÒu thuËt to¸n ®· ®−îc sö dông ®Ó kiÓm nghiÖm sù t−¬ng øng mét ®èi t−îng ®èi víi mét kh¸i niÖm. - Trong nhiÒu m« h×nh häc m¸y kh¸c, mçi kh¸i niÖm ®−îc biÓu diÔn nhê mét d·y c¸c luËt Horn-cÊp 1 d¹ng: class-a(X,Y) ←b(X),c(Y) bao gåm phÇn ®Çu (class-a(X,Y)) liªn quan ®Õn kh¸i niÖm vµ phÇn th©n liªn quan ®Õn c¸c literal (b(X),c(Y)). Th«ng qua qu¸ tr×nh suy diÔn t−¬ng øng víi c¸c luËt nãi trªn cã thÓ kiÓm nghiÖm ®−îc kh¸i niÖm phï hîp víi ®èi t−îng.. Ch¼ng h¹n, luËt sau ®©y tham gia biÓu diÔn kh¸i niÖm ung_th−_vó: ung_th−_vó (Tuæi,..., Møc ®é) ← >(Tuæi, 50), >(Møc ®é, 3) Theo luËt nµy, ng−êi phô n÷ ®−îc biÓu thÞ th«ng qua mét tËp hîp c¸c gi¸ trÞ cña c¸c biÕn (Tuæi,..., Møc ®é) cã bÖnh ung th− vó nÕu bµ ta ®· h¬n 50 tuæi vµ møc ®é trÇm träng cña bÖnh lín h¬n 3 ®é. - Mét ®Æc tr−ng quan träng cÇn ®−îc kh¶o s¸t lµ sai sãt trong häc m¸y cã gi¸m s¸t. §Ó ®¸nh gi¸ møc ®é tèt cña mét m« h×nh häc m¸y, ng−êi ta th−êng ®−a ra mét bé c¸c vÝ dô kiÓm tra (vÝ dô test). Mét sai sãt ®−îc ph¸t hiÖn khi vÝ dô ®· biÕt thuéc vµo kh¸i niÖm x song l¹i ®−îc hÖ thèng xÕp vµo kh¸i niÖm y mµ x ≠ y. HiÓn nhiªn, mét m« h×nh ®−îc coi lµ tèt khi sè l−îng sai sãt kiÓm tra lµ Ýt hoÆc kh«ng cã. Cã rÊt nhiÒu c«ng tr×nh khoa häc nghiªn cøu vÒ häc m¸y cã gi¸m s¸t. Mét trong nh÷ng néi dung cèt lâi cña lÜnh vùc nµy lµ gi¶m bít sai sãt häc m¸y. Mét trong nh÷ng h−íng ®Ó gi¶m thiÓu sai sãt ®ang ®−îc ph¸t triÓn lµ häc m¸y m« t¶ phøc ([6, 7, 8, 13, 14]). Trong ch−¬ng 2 vµ ch−¬ng 3, mét sè m« h×nh ®iÓn h×nh vµ mét sè néi dung chÝnh yÕu vÒ häc m¸y m« t¶ phøc ®−îc tr×nh bµy. I.1.3. Ph−¬ng ph¸p ®iÓn h×nh biÓu diÔn tri thøc trong häc m¸y Nh− ®· tr×nh bµy, biÓu diÔn tri thøc ®i liÒn víi bµi to¸n häc m¸y ([4]). NhiÒu m« h×nh hÖ thèng liªn quan ®Õn viÖc kÕt hîp viÖc häc tù ®éng víi thu -9-
  11. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n nhËn tri thøc ([2]) ®· ®−îc ®Ò xuÊt vµ ®¸nh gi¸. Nh÷ng ph−¬ng ph¸p ®iÓn h×nh nhÊt biÓu diÔn tri thøc trong häc m¸y cã thÓ kÓ ®Õn lµ: Ph−¬ng ph¸p biÓu diÔn l«gic, ph−¬ng ph¸p biÓu diÔn theo x¸c suÊt vµ ph−¬ng ph¸p biÓu diÔn theo ®èi t−îng. Theo ph−¬ng ph¸p biÓu diÔn l«gic, mçi kh¸i niÖm ®−îc nh− mét cÆp (thÓ hiÖn, ®Æc tr−ng). LuËt Horn-cÊp 1 lµ mét vÝ dô vÒ viÖc sö dông ph−¬ng ph¸p biÓu diÔn nµy. Theo ph−¬ng ph¸p biÓu diÔn theo x¸c suÊt, mçi kh¸i niÖm ®−îc biÓu diÔn nh− mét h×nh mÉu ph¶n ¸nh c¸c ®Æc tr−ng chung vµ tiªu biÓu nhÊt cña c¸c thÓ hiÖn. Khi ®· x¸c ®Þnh ®−îc c¸c x¸c suÊt tiªn nghiÖm cã thÓ nhËn ®−îc mét x¸c suÊt hËu nghiÖm kÕt qu¶. C¸c m« h×nh häc m¸y Bayes sö dông ph−¬ng ph¸p biÓu diÔn theo x¸c suÊt. Theo ph−¬ng ph¸p biÓu diÔn theo ®èi t−îng, mçi kh¸i niÖm ®−îc hiÓu vµ biÓu diÔn th«ng qua mét tËp c¸c thÓ hiÖn tiªu biÓu. D¹ng qu¸ ®¬n gi¶n vÒ tËp c¸c thÓ hiÖn lµ cho biÕt mét tËp ®èi t−îng t−¬ng thÝch víi kh¸i niÖm t−¬ng øng. M« h×nh t−¬ng øng thuËt to¸n ng−êi l¸ng giÒng gÇn nhÊt (k-ng−êi l¸ng giÒng gÇn nhÊt) sö dông ph−¬ng ph¸p biÓu diÔn theo ®èi t−îng. Trong mçi ng÷ c¶nh ¸p dông, thuËt to¸n häc m¸y sÏ chän mét trong ba ph−¬ng ph¸p biÓu diÔn nãi trªn. I.2. ThuËt to¸n ®iÓn h×nh trong häc m¸y I.2.1. ThuËt to¸n t¸ch nhãm C¸c ph−¬ng ph¸p t¸ch nhãm (t¸ch ®o¹n - clustering) tiÕp cËn tíi nh÷ng vÊn ®Ò t¸ch nhãm ®Þnh ®Þa chØ. C¸ch tiÕp cËn nµy g¸n c¸c b¶n ghi víi mét sè l−îng lín c¸c thuéc tÝnh vµo mét tËp nhá cã quan hÖ gi÷a c¸c nhãm hoÆc c¸c ®o¹n. Qu¸ tr×nh nµy ®−îc thùc hiÖn mét c¸ch tù ®éng bëi c¸c thuËt to¸n t¸ch nhãm nhËn d¹ng c¸c tÝnh chÊt kh¸c biÖt cña tËp d÷ liÖu vµ sau ®ã ph©n ho¹ch vïng kh«ng gian n_chiÒu ®−îc ®Þnh nghÜa bëi c¸c thuéc tÝnh tËp d÷ liÖu phô thuéc vµo c¸c biªn chia mét c¸ch tù nhiªn. -10-
  12. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n a/ ThuËt to¸n t¸ch nhãm ®iÓn h×nh T¸ch nhãm thùc hiÖn viÖc nhËn d¹ng nhãm c¸c b¶n ghi cã quan hÖ víi nhau, c¸c b¶n ghi nµy l¹i cã thÓ ®−îc sö dông nh− lµ ®iÓm xuÊt ph¸t cho viÖc khai th¸c c¸c mèi quan hÖ xa h¬n. Kü thuËt nµy hç trî cho viÖc ph¸t triÓn c¸c m« h×nh t¸ch nhãm mét quÇn thÓ t−¬ng tù viÖc t¸ch nhãm c¸c kh¸ch hµng dùa trªn c¸c tiªu chuÈn cña nh©n khÈu häc. Cã thÓ tõ kÕt qu¶ mong muèn vµ dùa trªn kü thuËt ph©n tÝch chuÈn ®Ó x¸c ®Þnh ®−îc ®Æc tÝnh cña c¸c nhãm. Ch¼ng h¹n, thãi quen mua s¾m cña nhiÒu nhãm d©n c− cã thÓ ®−îc so s¸nh ®Ó x¸c ®Þnh nhãm nµo lµ môc tiªu cña chiÕn dÞch bu«n b¸n míi trong tiÕp thÞ ®Þnh h−íng. T¸ch nhãm lµ ph−¬ng ph¸p nhãm nh÷ng hµng cña d÷ liÖu (b¶n ghi) theo nh÷ng h−íng gièng nhau vµ vµo c¸c mÉu. Trong t¸ch nhãm kh«ng cã biÕn phô thuéc, kh«ng cã sù m« t¶ s¬ l−îc vÒ mét h−íng ®Æc ®iÓm riªng. T¸ch nhãm còng cã thÓ dùa vµo mÉu qu¸ khø ([2]), cã nghÜa lµ, tõ c¸c kÕt qu¶ t¸ch nhãm tr−íc ®©y ®Ó h×nh thµnh viÖc t¸ch nhãm míi. Kü thuËt t¸ch nhãm cè g¾ng t×m sù kh¸c nhau vµ gièng nhau trong tËp d÷ liÖu vµ ph©n nhãm nh÷ng b¶n ghi gièng nhau vµo nh÷ng ®o¹n hoÆc nh÷ng nhãm. Nh− vËy, trong tËp d÷ liÖu cµng cã nhiÒu sù gièng nhau hoÆc kh¸c nhau th× tËp d÷ liÖu ®ã cµng ®−îc chia nhá thµnh nhiÒu nhãm. Sau khi d÷ liÖu ®· ®−îc t¸ch nhãm, ng−êi ph©n tÝch sÏ khai th¸c th«ng tin vµ rót ra c¸c tri thøc cÇn thiÕt th«ng qua sù gièng nhau vµ sù kh¸c nhau trong c¸c nhãm d÷ liÖu ®ã. Ch¼ng h¹n, ®èi t−îng con ng−êi th−êng ®−îc ph©n mét c¸ch tù nhiªn theo nh©n khÈu häc thµnh nh÷ng nhãm ph©n biÖt theo ®é tuæi nh−: trÎ míi sinh, nhi ®ång, thanh thiÕu niªn, ng−êi tr−ëng thµnh vµ ng−êi cã tuæi. TÝnh "gièng nhau" hoÆc "kh¸c nhau" ®Ó t¸ch nhãm võa lµ kÕt qu¶ cña qu¸ tr×nh t¸ch nhãm võa lµ thµnh tè tham gia vµo viÖc t¸ch nhãm. VÝ dô 1.1 -11-
  13. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n Mét tËp d÷ liÖu chøa c¸c th«ng tin vÒ kh¸ch hµng cã c¸c thuéc tÝnh {“thu nhËp”, “sè con”, “Lo¹i «t« së h÷u”}. Ng−êi b¸n lÎ muèn biÕt nh÷ng nÐt gièng nhau tån t¹i trong tËp kh¸ch hµng c¬ b¶n cña hä, vµ nh− vËy, hä cã thÓ t¸ch ra ®Ó hiÓu ®−îc nh÷ng nhãm kh¸c nhau vÒ nh÷ng mÆt hµng ®· ®−îc mua vµ b¸n trªn thÞ tr−êng. Ng−êi b¸n hµng sö dông c¬ së d÷ liÖu víi nh÷ng b¶n ghi th«ng tin vÒ kh¸ch hµng vµ cè g¾ng t¸ch nh÷ng nhãm kh¸ch hµng. Ch¼ng h¹n, tËp d÷ liÖu cã thÓ chøa ®ùng rÊt nhiÒu kh¸ch hµng giÇu cã mµ l¹i kh«ng cã con vµ nh÷ng kh¸ch hµng thu nhËp thÊp mµ cã bè mÑ ë cïng. Qu¸ tr×nh kh¸m ph¸ nµy sÏ t×m ra sù kh¸c nhau cã thÓ ®−îc sö dông ®Ó ph©n chia d÷ liÖu vµo hai nhãm tù nhiªn. NÕu tån t¹i rÊt nhiÒu ®iÓm gièng nhau còng nh− kh¸c nhau th× tËp d÷ liÖu cã thÓ ®−îc chia nhá thªm n÷a. Ch¼ng h¹n, sau khi ph©n tÝch, tËp kh¸ch hµng ®−îc ph©n thµnh c¸c nhãm nh− trong h×nh 1. H×nh 1. T¸ch nhãm kh¸ch hµng L−îc ®å trong h×nh 1 chØ ra mét c¸ch thøc nghiªn cøu ®o¹n mÉu: ®−a ra nh÷ng d÷ liÖu kh¸ch hµng vµ chia vµo c¸c nhãm kh¸c nhau. L−îc ®å thÓ hiÖn sù cè g¾ng thu ®−îc tri thøc vÒ nh÷ng nhãm d÷ liÖu trong tËp d÷ liÖu. Tõ nh÷ng nhãm ®· ®−îc nhËn d¹ng s¬ bé tr−íc ®©y, mét ng−êi ph©n tÝch cã thÓ hiÓu ®Ó biÓu diÔn ®−îc sù kh¸c nhau vµ gièng nhau trong nh÷ng nhãm. -12-
  14. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n H×nh 1 cho thÊy cã 4 nhãm kh¸ch hµng ®−îc nhËn d¹ng víi tªn gäi lµ Nhãm 1, Nhãm 2, Nhãm 3 vµ Nhãm 4. Lý do ®Ó t¸ch thµnh nh÷ng nhãm kh¸c nhau: Nhãm 1 bao gåm nh÷ng ng−êi së h÷u « t« Luxery, Nhãm 2 bao gåm nh÷ng ng−êi së h÷u « t« Compact, hai Nhãm 3 vµ Nhãm 4 bao gåm nh÷ng ng−êi së h÷u « t« Sedan hoÆc Truck. D÷ liÖu trong hai nhãm cã thÓ giao nhau, ch¼ng h¹n, trong tr−êng hîp nµy hai nhãm 3 vµ 4 cã nh÷ng ®iÓm gièng nhau còng nh− nhiÒu ®iÓm kh¸c nhau. b/ Kü thuËt hiÓn thÞ b»ng h×nh ¶nh (Visualization) Kü thuËt hiÓn thÞ b»ng h×nh ¶nh lµ mét ph−¬ng ph¸p ®¬n gi¶n, dÔ hiÓu nh−ng l¹i rÊt h÷u Ých trong viÖc nhËn biÕt nh÷ng nhãm d÷ liÖu kh¸c nhau th«ng qua viÖc nhËn biÕt nh÷ng mÉu Èn trong d÷ liÖu. Kü thuËt nµy cã thÓ ®−îc sö dông t¹i thêi ®iÓm tr−íc khi tiÕn hµnh qu¸ tr×nh khai th¸c vµ gióp cho ng−êi ph©n tÝch thÊy s¬ bé vÒ chÊt l−îng cña d÷ liÖu vµ c¸c mÉu sÏ ®−îc t×m thÊy trong kho¶ng nµo. Ph−¬ng ph¸p hiÓn thÞ mét c¸ch ®¬n gi¶n chØ hiÓn thÞ c¸c thuéc tÝnh cña d÷ liÖu lªn mÆt ph¼ng theo mét c¸ch nµo ®ã. C¸c kü thuËt hiÓn thÞ ®ang ®−îc ph¸t triÓn m¹nh mÏ vµ nhanh chãng ®−îc c¶i tiÕn nh»m cho phÐp ng−êi ph©n tÝch l−ít qua d÷ liÖu th«ng qua kh«ng gian d÷ liÖu nh©n t¹o. Mét kü thuËt s¬ cÊp nh−ng l¹i cã gi¸ trÞ lµ l−îc ®å ph©n bè, trong kü thuËt nµy th«ng tin ®−îc hiÓn thÞ qua hai thuéc tÝnh trªn mét hÖ trôc to¹ ®é hai chiÒu. C¸c ph−¬ng ph¸p ®¬n gi¶n nµy cã thÓ cho ta rÊt nhiÒu th«ng tin. L−îc ®å ph©n bè cã thÓ ®−îc sö dông ®Ó t×m ra c¸c tËp d÷ liÖu con h÷u Ých trong toµn bé tËp d÷ liÖu vµ tõ ®ã ta sÏ tËp trung vµo ph©n tÝch trªn c¸c tËp con ®ã trong phÇn cßn l¹i cña qu¸ tr×nh khai th¸c d÷ liÖu. Tuy nhiªn, c¸c c«ng cô khai ph¸ d÷ liÖu (Data Mining) cßn ®−îc c¶i tiÕn ®Ó hiÓn thÞ d÷ liÖu th«ng qua m«i tr−êng giao tiÕp ba chiÒu, mçi chiÒu t−¬ng øng víi mét thuéc tÝnh. H×nh 2 m« t¶ mét c¸ch hiÓn thÞ ®¬n gi¶n vµ cã thÓ th«ng qua ph©n bè trªn mÆt ph¼ng hiÖn thÞ ®Ó nhËn ra ®−îc c¸c nhãm d÷ liÖu. -13-
  15. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n H×nh 2. Mét vÝ dô vÒ c¸ch hiÓn thÞ d÷ liÖu. c/ T¸ch nhãm tèi −u Mét vÊn ®Ò ®Æt ra trong thuËt to¸n t¸ch nhãm lµ “Nªn ph©n d÷ liÖu ®· cho thµnh bao nhiªu nhãm th× tèi −u?”. Tån t¹i c¸c c«ng cô kh¸c nhau víi c¸c c¸ch gi¶i quyÕt kh¸c nhau gi¶i quyÕt c©u hái nµy. Ch¼ng h¹n, cã c«ng cô cho phÐp ng−êi dïng tuú chän, c«ng cô kh¸c th× tù ®éng quyÕt ®Þnh tuú vµo tõng lo¹i d÷ liÖu ®−îc ®−a vµo... Cã thÓ t¸ch thµnh 2, 3 hay nhiÒu nhãm. Sau khi t¸ch nhãm s¬ bé nh− vËy, mçi nhãm nµy cã thÓ trë thµnh vïng t×m kiÕm tiÕp tôc. Ngµy nay, tån t¹i nhiÒu c¸ch tiÕp cËn ph©n nhãm cho phÐp ng−êi sö dông quyÕt ®Þnh sè nhãm trong tËp d÷ liÖu, trong khi ®ã, còng tån t¹i nhiÒu c¸ch tiÕp cËn kh¸c cè g¾ng ®i tíi quyÕt ®Þnh nhê viÖc sö dông mét hoÆc nhiÒu thuËt to¸n. I.2.2. ThuËt to¸n ph©n líp Bayes a) ThuËt to¸n ph©n líp (Classification Algorithm) Ph©n líp lµ kü thuËt häc cã gi¸m s¸t ®−îc øng dông phæ biÕn nhÊt, sö dông mét tËp c¸c mÉu ®· ®−îc ph©n lo¹i tõ tr−íc ®Ó ph¸t triÓn mét m« h×nh cho phÐp ph©n lo¹i thuéc tÝnh cña mét sè l−îng lín c¸c b¶n ghi. -14-
  16. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n Theo c¸ch tù nhiªn, con ng−êi th−êng cã ý t−ëng ph©n chia sù vËt thµnh c¸c líp kh¸c nhau. Mét vÝ dô dÔ thÊy lµ ®èi t−îng con ng−êi th−êng ®−îc ph©n chia theo ®é tuæi thµnh nhãm kh¸c nhau nh−: TrÎ s¬ sinh, nhi ®ång, thiÕu niªn, thanh niªn vµ ng−êi giµ. Nh− ®· biÕt, bµi to¸n t¸ch tËp ®èi t−îng thµnh c¸c nhãm kh¸c nhau ®· ®−îc thuËt to¸n t¸ch nhãm gi¶i quyÕt. ThuËt to¸n ph©n líp ®¬n gi¶n chØ lµ mét phÐp ¸nh x¹ tõ mét thuéc tÝnh, hoÆc mét tËp hîp c¸c thuéc tÝnh nµo ®ã cña d÷ liÖu sang mét miÒn gi¸ trÞ cô thÓ nµo ®ã. Nh− trong vÝ dô trªn, thuéc tÝnh tuæi ®−îc ¸nh x¹ sang miÒn gi¸ trÞ {“trÎ s¬ sinh”, “nhi ®ång”, “thiÕu niªn”, “thanh niªn”,...}. Cã thÓ lÊy vÝ dô trong c¸c øng dông nh»m ph¸t hiÖn sù gian lËn vµ sù rñi ro vÒ mua b¸n tÝn phiÕu. C¸ch tiÕp cËn nµy th−êng xuyªn sö dông thuËt to¸n ph©n líp c©y quyÕt ®Þnh hoÆc thuËt to¸n ph©n líp dùa trªn m¹ng thÇn kinh (neural network). Sö dông thuËt to¸n ph©n líp b¾t ®Çu víi mét tËp c¸c cuéc mua b¸n tËp d−ît mÉu ®· ®−îc ph©n líp tõ tr−íc. Víi mét øng dông ph¸t hiÖn sù gian lËn bao gåm c¸c hå s¬ hoµn chØnh vÒ c¶ ho¹t ®éng gian lËn vµ hîp lÖ, x¸c ®Þnh trªn c¬ së tõng b¶n ghi mét. §Çu tiªn, thuËt to¸n s¬ bé ph©n líp sö dông c¸c mÉu ®· ®−îc ph©n líp tr−íc ®Ó x¸c ®Þnh tËp c¸c tham sè cÇn thiÕt cho viÖc ph©n biÖt chÝnh x¸c. TiÕp theo, thuËt to¸n sÏ m· ho¸ c¸c tham sè vµo mét m« h×nh ®−îc gäi lµ bé ph©n líp. C¸ch tiÕp cËn nµy ch−a t−êng minh vÒ n¨ng lùc cña mét hÖ thèng. Ngay sau khi bé ph©n líp cã hiÖu qu¶ ®−îc ph¸t triÓn, nã ®−îc sö dông trong chÕ ®é cã thÓ ®o¸n tr−íc ®−îc ®Ó ph©n líp c¸c hå s¬ míi vµo cïng c¸c líp ®· ®−îc ®Þnh nghÜa s½n. Ch¼ng h¹n, mét bé ph©n líp cã kh¶ n¨ng x¸c ®Þnh c¸c kho¶n cho vay cã tÝnh rñi ro, cã thÓ ®−îc dïng ®Ó trî gióp c¸c quyÕt ®Þnh cho c¸c c¸ nh©n vay. Mét vÝ dô kh¸c, mét c¸ch tiÕp cËn phæ biÕn trong doanh nghiÖp cã môc ®Ých lµ ”T«i muèn hiÓu ®iÒu g× thu hót kh¸ch hµng cña c«ng ty t«i g¾n bã nhiÒu h¬n víi c«ng ty“. §Ó ®¹t ®−îc môc ®Ých ®ã, gi¶ sö cã s½n hai líp kh¸ch hµng "g¾n bã" vµ "®i khái" vµ víi nh÷ng th«ng tin cã s½n vÒ kh¸ch hµng, cÇn nhËn ra -15-
  17. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n ®−îc ®Æc tr−ng tõng lo¹i nãi trªn ®Ó cã ®−îc chÝnh s¸ch tiÕp thÞ tèt h¬n. Tõ c¸c b¶ng d÷ liÖu qu¸ khø cã thÓ dù ®o¸n vÒ hai líp ®èi t−îng "g¾n bã" vµ "®i khái" nÕu vÉn theo chÝnh s¸ch tiÕp thÞ tr−íc ®©y. Cét tªn KiÓu d÷ KiÓu gi¸ trÞ M« t¶ tr−êng liÖu Sè_hiÖu_kh¸c Sè C¸c gi¸ trÞ duy nhÊt Tr−êng m· ph©n biÖt mçi h_hµng kh¸ch hµng Thêi_gian_mu Sè C¸c gi¸ trÞ nguyªn Nh÷ng ngµy mét kh¸ch a_b¸n hµng ®Õn víi c«ng ty Sö_dông_trùc_Ký tù RÊt cao, Cao, Võa, Sè phót ®−îc kh¸ch hµng tuyÕn ThÊp,RÊt_thÊp sö dông trong th¸ng tr−íc Xu_h−íng Ký tù T¨ng, T¨ng_®a_møc, Møc ®é t¨ng gi¶m kh¸ch Nh−_tr−íc, hµng th−êng xuyªn d−íi 6 Gi¶m_®a_møc th¸ng Tr¹ng_th¸i Ký tù Cao, §−îc, ThÊp, KÕt qu¶ ®iÒu tra thèng kª Ch−a_râ kh¸ch hµng KiÓu_kh¸ch_h Ký tù G¾n_bã, §i_khái Kh¸ch hµng trung thµnh µng víi c«ng ty hay ®Õn víi c«ng ty c¹nh tranh. B¶ng 1. M« t¶ ®Æc tr−ng cña tËp d÷ liÖu kh¸ch hµng B¶ng 1 trªn ®©y cho biÕt tËp d÷ liÖu qu¸ khø vÒ kh¸ch hµng, cã c¸c tr−êng víi gi¸ trÞ vµ kiÓu cña nã. Ch¼ng h¹n, cét KiÓu_kh¸ch_hµng lµ cét gåm nh÷ng b¶n ghi biÓu thÞ nh÷ng kh¸ch hµng trong qu¸ khø lµ trung thµnh hay nghiªng vÒ c«ng ty c¹nh tranh (®Þnh râ tõng hµng trong b¶ng víi gi¸ trÞ G¾n_bã hoÆc §i_khái). Chó ý, x©y dùng m« h×nh kh¸ch hµng ®ßi hái mét sù hiÓu biÕt tr−íc vÒ ng−êi kh¸ch hµng nµo lµ trung thµnh (G¾n_bã) vµ ng−êi nµo lµ kh«ng trung thµnh (§i_khái). KiÓu khai th¸c nµy ®−îc gäi lµ “häc cã gi¸m s¸t” bëi v× mÉu ®µo t¹o ®−îc g¾n nh·n víi c¸c líp thùc sù (G¾n_bã hoÆc §i_khái). Cét KiÓu_kh¸ch_hµng ®−îc x¸c ®Þnh nh− lµ mét kÕt qu¶ ra hoÆc nh− lµ biÕn phô thuéc nÕu nã ®−îc sö dông nh− mét phÇn c¬ b¶n cña nghiªn cøu vÒ b¶ng d÷ liÖu kh¸ch hµng. -16-
  18. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n b) ThuËt to¸n ph©n líp Bayes Theo ph−¬ng ph¸p Bayes, ®Ó cùc ®¹i ho¸ hµm tiÖn Ých U nµo ®ã phô thuéc vµo t¸c ®éng A vµ mét tr¹ng th¸i ®· biÕt song ch−a ®Çy ®ñ cña thÕ giíi H, chóng ta ®−a ra t¸c ®éng mµ hy väng t¸c ®éng ®ã sÏ lµm cùc ®¹i hµm tiÖn Ých U nãi trªn khi tÝnh ®Õn mäi kh¶ n¨ng cña thÕ giíi H. ¸p dông trong bµi to¸n ph©n líp: T¹o ra sù ph©n líp A ®−a ®Õn ®é chÝnh x¸c hy väng U lµ cùc ®¹i víi ®iÒu kiÖn ®· xem xÐt trªn mäi gi¶ thiÕt cã thÓ cã trong kh«ng gian gi¶ thiÕt cña thuËt to¸n häc. Trong thùc tÕ, thuËt to¸n chØ tÝnh ®−îc trong mét tËp con ®−îc gäi lµ “tèt” cña kh«ng gian gi¶ thiÕt. Gi¶ sö c lµ mét líp, τ lµ tËp c¸c gi¶ thiÕt sinh ra cña thuËt to¸n häc, x lµ vÝ dô test, x lµ vÝ dô cÇn d¹y. Ta cÇn g¸n c cho x ®Ó cùc ®¹i biÓu thøc: p (c x,τ ) = ∑ p (c x, T ) p (T x) (1.1) T in τ §iÒu nµy cã nghÜa lµ chóng ta ph¶i dù ®o¸n x¸c xuÊt hËu nghiÖm p(T x ) cña mçi m« h×nh häc vµ ph¶i −íc l−îng mét c¸ch chÝnh x¸c p(c x , T ) . Chóng ta xem xÐt tËp con cña c¸c luËt trong tËp c¸c luËt cña líp i mµ ®· tho¶ m·n vÝ dô test x. §é chÝnh x¸c cña luËt chÝnh x¸c nhÊt trong ®ã tËp con ®−îc sö dông cho p( c x , T ) . C¸c h¹ng thøc kh¸c trong ph−¬ng tr×nh (1.1) lµ x¸c suÊt hËu nghiÖm cña c©y p(T x ) cã thÓ ®−îc tÝnh to¸n khi sö dông: B(n1k + α 1 , n 2 k + α 2 ) V p (T x)α p(T )× ∏ (1.2) B (α 1 , α 2 ) k =1 ë ®©y p(T ) lµ −u tiªn cña c©y, B lµ hµm Beta*, V lµ sè l¸ cña c©y, α1 vµ α2 lµ tham biÕn vµ ni,j lµ kÝ kiÖu sè vÝ dô cÇn d¹y cña líp i ë l¸ thø j cña c©y. Bªn c¹nh ®ã nã cßn ®−îc sö dông ®Ó ph©n líp. -17-
  19. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n Trong mçi bµi to¸n øng dông cô thÓ, viÖc x¸c ®Þnh c¸c c«ng thøc tÝnh to¸n x¸c suÊt tiªn nghiÖm vµ x¸c suÊt hËu nghiÖm ®èi víi (1.1) vµ (1.2) lµ mét trong nh÷ng néi dung c¬ b¶n nhÊt cña viÖc øng dông ph©n líp Bayes. Trong ch−¬ng 4 cña luËn v¨n sÏ tr×nh bµy qu¸ tr×nh gi¶i quyÕt mét lo¹i bµi to¸n ph©n líp trong mét c¬ së d÷ liÖu full-text. C¸c x¸c suÊt trong m« h×nh nµy th−êng ®−îc biÓu diÔn d−íi d¹ng tû sè c¸c tÇn suÊt. I.2.3. ThuËt to¸n ph©n líp "k_ng−êi l¸ng giÒng gÇn nhÊt" (k-nearest neighbour) Cho tËp hîp ®èi t−îng Ω, trªn Ω cã mét hµm kho¶ng c¸ch µ nµo ®ã. Cho tËp hîp c¸c mÉu Ωo ®· biÕt tr−íc vµ mét ph©n ho¹ch trªn Ωo trong ®ã mçi líp ®−îc ®Æc tr−ng bëi mét tËp con cña Ωo theo ph©n ho¹ch nãi trªn. Bµi to¸n ph©n líp ®èi víi ®èi t−îng w cã thÓ ®−îc gi¶i quyÕt nhê thuËt to¸n ng−êi l¸ng giÒng gÇn nhÊt. Theo thuËt to¸n nµy, t×m phÇn tö wo cña Ωo tháa m·n ®iÒu kiÖn: µ(w, wo) = min {µ(w, u): u ∈ Ωo} Líp ®−îc g¸n cho ®èi t−îng w chÝnh lµ líp mµ wo ®· thuéc vµo. T×nh huèng sau ®©y ®−îc ®Æt ra víi thuËt to¸n ng−êi l¸ng giÒng gÇn nhÊt lµ khi tÝnh kho¶ng c¸ch nhËn ®−îc nhiÒu h¬n mét ®èi t−îng cïng gÇn w nhÊt vµ chóng l¹i thuéc c¸c líp kh¸c nhau. ThuËt to¸n k-ng−êi l¸ng giÒng gÇn nhÊt lµ sù c¶i tiÕn cña thuËt to¸n ng−êi l¸ng giÒng gÇn nhÊt ®−îc m« t¶ nh− sau ®©y. Víi mét sè k ®· chän tr−íc. T×m k ®èi t−îng thuéc Ωo gÇn víi w nhÊt. §èi víi mçi líp ®· cho, líp nµo cã nhiÒu ®èi t−îng tham gia vµo k ®èi t−îng ®· tÝnh th× kh¼ng ®Þnh ®ã lµ líp cÇn ph©n w vµo. Mét sè néi dung sau ®©y cÇn ®−îc ®Æt ra víi thuËt to¸n k-ng−êi l¸ng giÒng gÇn nhÊt: -18-
  20. Häc m¸y, häc m¸y m« t¶ phøc: thuËt to¸n vµ vÊn ®Ò rót gän lçi L−¬ng Song V©n - ViÖc x¸c ®Þnh kho¶ng c¸ch µ. Kho¶ng c¸ch nãi trªn ®−îc chän tïy thuéc vµo néi dung cña bµi to¸n ph©n líp. Ch¼ng h¹n, trong bµi to¸n häc m« t¶ phøc HYDRA (®−îc tr×nh bµy cô thÓ trong ch−¬ng 2), kho¶ng c¸ch Ls ®−îc chän theo c«ng thøc: ( p + 1) / ( p + 2) lsi j=ls(p,n,p0,n0) ≈ 0 (n + 1) / (n0 + 2) ë ®©y p0 vµ n0 t−¬ng øng kÝ hiÖu sè c¸c vÝ dô d¹y tÝch cùc vµ ®èi ngÉu (cña líp i) trong toµn bé tËp d÷ liÖu cßn p vµ n lµ c¸c ký hiÖu t−¬ng øng víi p0 vµ n0 song liªn quan ®Õn luËt. - Cì cña sè k còng cã ¶nh h−ëng ®Õn chÊt l−îng cña thuËt to¸n: k qu¸ bÐ th× ¶nh h−ëng ®Õn ®é tin cËy cña thuËt to¸n, cßn khi k qu¸ lín sÏ t¹o ra ®é phøc t¹p tÝnh to¸n cao mµ ®é tin cËy l¹i kh«ng t¨ng mét sè ®¸ng kÓ. Mét sè ph−¬ng ph¸p thèng kª cã thÓ ®−îc sö dông ®Ó x¸c ®Þnh gi¸ trÞ k thÝch hîp. Trong nhiÒu tr−êng hîp, thuËt to¸n k-ng−êi l¸ng giÒng gÇn nhÊt cho mét ph−¬ng ph¸p kh¶ thi, hiÖu qu¶ tèt mµ kh«ng qu¸ phøc t¹p. MÆt kh¸c, khi ¸p dông thuËt to¸n ng−êi ta th−êng xem xÐt "®é gÇn nhau" gi÷a c¸c ®èi t−îng thay cho viÖc xem xÐt "kho¶ng c¸ch" gi÷a chóng. Mét biÕn d¹ng cña thuËt to¸n k-ng−êi l¸ng giÒng gÇn nhÊt th−êng ®−îc sö dông trong bµi to¸n ph©n líp ®−îc diÔn t¶ theo tiÕn tr×nh nh− sau: - LÊy mét sè d−¬ng g¸n t−¬ng øng cho mçi líp, ®−îc gäi lµ ng−ìng cña líp, - LÊy ngÉu nhiªn k ®èi t−îng trong tËp c¸c ®èi t−îng mÉu, - TÝnh ®é thuéc cña ®èi t−îng cÇn ph©n líp t−¬ng øng víi mçi líp ®· cho, - Víi tõng líp ®èi t−îng, so s¸nh gi¸ trÞ kÕt qu¶ tÝnh to¸n ®é thuéc víi ng−ìng: nÕu v−ît qu¸ ng−ìng th× kÕt qu¶ ®èi t−îng ®−îc ph©n vµo líp ®ã; trong tr−êng hîp ng−îc l¹i th× xem xÐt víi líp tiÕp theo. BiÕn d¹ng nh− trªn cña thuËt to¸n k-ng−êi l¸ng giÒng gÇn nhÊt th−êng ®¹t ®é chÝnh x¸c kh«ng cao song l¹i ®−a ®Õn tèc ®é tÝnh to¸n nhanh. Tèc ®é hoµn -19-
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Tài Chính Ngân Hàng
172 tài liệu
841 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
3=>0