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
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
-1-
Môc lôc
Néi dung Trang
PhÇn më ®Çu 3
Ch−¬ng 1. Bµi to¸n häc m¸y vµ mét sè thuËt to¸n 6
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
Ch−¬ng 2. Häc m¸y m« t¶ phøc 21
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¶
phøc
26
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
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
-2-
Ch−¬ng 3. Rót gän lçi trong häc m¸y m« t¶ phøc 49
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
Ch−¬ng 4. ThuËt to¸n t×m kiÕm vµ ph©n líp trong c¬ së d÷ liÖu
full-text
64
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
theo m« h×nh vector c¶i tiÕn 72
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
PhÇn kÕt luËn 90
Tµi liÖu tham kh¶o 92
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
-3-
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]).
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
-4-
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