Phương pháp biểu diễn ngữ nghĩa lân cận siêu liên kết cho máy tìm kiếm VietSeek
Môc lôc
PhÇn më ®Çu........................................................................................................................... 3
Ch−¬ng 1. Tæng quan vÒ t×m kiÕm th«ng tin trªn web.................................... 5
1.1
Giíi thiÖu vÒ t×m kiÕm th«ng tin............................................................... 5
1.2
Bµi to¸n t×m kiÕm th«ng tin ...................................................................... 5
1.2.1
Giai ®o¹n 1: Thu thËp vµ ph©n tÝch th«ng tin .................................... 9
1.2.2
Giai ®o¹n 2: Xö lý c©u hái vµ tr¶ lêi................................................10
1.3
M« h×nh biÓu diÔn th«ng tin cña v¨n b¶n ...............................................11
1.3.1
M« h×nh biÓu diÔn th«ng tin theo tõ kho¸ .......................................12
1.3.2
M« h×nh biÓu diÔn th«ng tin theo néi dung .....................................14
1.4
Ph©n tÝch có ph¸p vµ ng÷ nghÜa ..............................................................15
1.5
Ph©n líp v¨n b¶n.....................................................................................15
1.6
Ph©n côm v¨n b¶n...................................................................................15
1.7
Khai th¸c th«ng tin cÊu tróc web............................................................16
1.8
Khai th¸c th«ng tin sö dông web ............................................................16
Ch−¬ng 2. ph−¬ng ph¸p biÓu diÔn trang web theo ng÷ nghÜa l©n cËn
siªu liªn kÕt ......................................................................................................................... 18
2.1
Giíi thiÖu ................................................................................................18
2.2
Ph−¬ng ph¸p ®¸nh gi¸ chÊt l−îng ®é ®o t−¬ng tù ..................................19
2.2.1
Chän ph−¬ng ph¸p ®¸nh gi¸ ............................................................19
2.2.2
X¸c ®Þnh thø tù nÒn trong ODP .......................................................20
2.2.3
So s¸nh sù t−¬ng quan gi÷a c¸c tËp thø tù.......................................23
2.2.4
MiÒn cña tËp thø tù ..........................................................................24
2.3
§Þnh nghÜa m« h×nh vector biÓu diÔn th«ng tin v¨n b¶n ........................26
2.3.1
Vector biÓu diÔn th«ng tin v¨n b¶n..................................................27
2
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
2.3.2
Lùa chän tõ kho¸ biÓu diÔn .............................................................27
2.3.3
L−îc bít tõ kho¸ ..............................................................................28
2.3.4
X¸c ®Þnh träng sè cña tõ kho¸ .........................................................29
2.4
§Þnh nghÜa ®é ®o t−¬ng tù......................................................................30
2.5
§¸nh gi¸ chÊt l−îng xÕp h¹ng ®èi víi mçi ph−¬ng ph¸p x©y dùng vector
..............................................................................................................31
2.5.1
§¸nh gi¸ chÊt l−îng ®èi víi c¸ch chän tõ kho¸ ..............................32
2.5.2
§¸nh gi¸ chÊt l−îng ®èi víi c¸ch chuÈn ho¸ träng sè tõ kho¸........39
2.5.3
§¸nh gi¸ chÊt l−îng ®èi víi ph−¬ng ph¸p l−îc bít tõ kho¸............42
2.6
C¸c thuËt to¸n t×m kiÕm theo m« h×nh vector.........................................42
Ch−¬ng 3. m¸y t×m kiÕm vietseek vµ thö nghiÖm ThuËt to¸n t×m kiÕm
theo ng÷ nghÜa l©n cËn siªu liªn kÕt .................................................................... 45
3.1
M¸y t×m kiÕm VietSeek ..........................................................................45
3.1.1
C¸c ®Æc ®iÓm c¬ b¶n cña Vietseek ..................................................45
3.1.2
C¬ së d÷ liÖu cña Vietseek ..............................................................46
3.2
§Ò xuÊt thuËt to¸n t×m kiÕm míi cho m¸y t×m kiÕm VietSeek ..............49
3.2.1
Nh÷ng c¬ së ®Ó ®Ò xuÊt thuËt to¸n ..................................................49
3.2.2
C¸c thuËt to¸n ¸p dông cho m¸y t×m kiÕm VietSeek.......................53
3.2.3
KÕt qu¶ thùc hiÖn.............................................................................62
PhÇn kÕt luËn...................................................................................................................... 67
Tµi liÖu tham kh¶o........................................................................................................... 69
Phô lôc.................................................................................................................................... 72
§Æng TiÓu Hïng – LuËn v¨n cao häc
3
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
PhÇn më ®Çu
Cïng víi sù ph¸t triÓn m¹nh mÏ cña Internet lµ mét khèi l−îng khæng lå d÷ liÖu
®−îc ph¸t sinh, tuy nhiªn (theo th«ng tin tõ tËp ®oµn Oracle) kho¶ng 90% d÷ liÖu ë
d¹ng phi cÊu tróc hoÆc nöa cÊu tróc. Nhu cÇu khai th¸c, t×m kiÕm th«ng tin mét c¸ch
chÝnh x¸c trªn internet ®· ngµy cµng trë nªn bøc thiÕt h¬n, do ®ã xuÊt hiÖn c¸c hÖ t×m
kiÕm theo tõ kho¸ (côm tõ kho¸) nh− Yahoo, Google ... Tuy nhiªn viÖc t×m kiÕm theo
tõ kho¸ vÉn ch−a ®ñ ®Ó gióp ng−êi sö dông nhanh chãng t×m ®−îc trang Web cÇn thiÕt
v× sè l−îng kÕt qu¶ tr¶ l¹i rÊt lín vµ nhiÒu khi chØ lµ c¸c trang Web Ýt cã liªn quan. V×
vËy c¸c hÖ thèng t×m kiÕm cÇn ®−îc c¶i tiÕn ®Ó ngµy cµng th«ng minh h¬n. XuÊt hiÖn
nh÷ng hÖ h−íng tíi môc tiªu cô thÓ nh− tra cøu th«ng tin vÒ c¸c chñ ®Ò y tÕ, gi¸o dôc,
luËt ph¸p, ©m nh¹c ... Tuy vËy, viÖc nghiªn cøu c¸c gi¶i ph¸p t×m ®−îc c¸c trang th«ng
tin theo mét néi dung nµo ®ã s¸t víi yªu cÇu ng−êi sö dông vÉn cßn nhiÒu h¹n chÕ. §·
cã nhiÒu m« h×nh t×m kiÕm ®−îc ®Ò xuÊt, song nh÷ng m« h×nh lý t−ëng vÒ mÆt lý
thuyÕt th× l¹i ch−a cã tÝnh kh¶ thi khi cµi ®Æt. Do ®ã, trong c¸c hÖ t×m kiÕm, ng−êi ta
t×m c¸ch c¶i tiÕn c¸c ph−¬ng ph¸p cã s½n ®Ó ¸p dông trong thùc tÕ. LuËn v¨n nµy h−íng
tíi viÖc nghiªn cøu, ph©n tÝch, ®¸nh gi¸ mét sè thuËt to¸n t×m kiÕm theo néi dung, tõ
®ã ®Ò xuÊt ph−¬ng ¸n c¶i tiÕn ®Ó n©ng cao hiÖu qu¶ vÒ tÝnh chÝnh x¸c cña néi dung
còng nh− vÒ tèc ®é.
Tõ viÖc t×m hiÓu, ®¸nh gi¸ vµ ph©n tÝch −u, nh−îc ®iÓm cña c¸c ph−¬ng ph¸p tiÕp
cËn kh¸c nhau, dùa theo môc tiªu n©ng cao hiÖu qu¶ t×m kiÕm, luËn v¨n ®Ò xuÊt gi¶i
ph¸p thùc hiÖn “Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m
kiÕm VietSeek”.
Néi dung cña luËn v¨n ®−îc ®Þnh h−íng vµo c¸c vÊn ®Ò sau:
1. M« h×nh to¸n häc biÓu diÔn trang v¨n b¶n Web,
§Æng TiÓu Hïng – LuËn v¨n cao häc
4
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
2. Kh¸i qu¸t c¸c ph−¬ng ph¸p tiÕp cËn trong t×m kiÕm trang Web cã néi dung
t−¬ng tù. §¸nh gi¸ −u ®iÓm vµ nh−îc ®iÓm cña mçi ph−¬ng ph¸p ®−îc
kh¶o s¸t.
3. §Ò xuÊt ph−¬ng ph¸p kÕt hîp ®Ó n©ng cao hiÖu qu¶ trong t×m kiÕm trang
Web cã néi dung t−¬ng tù
LuËn v¨n bao gåm PhÇn më ®Çu, ba ch−¬ng néi dung vµ PhÇn kÕt luËn víi néi
dung c¸c ch−¬ng ®−îc tr×nh bµy nh− d−íi ®©y.
Ch−¬ng 1 víi tiªu ®Ò lµ Tæng quan vÒ c¸c ph−¬ng ph¸p biÓu diÔn vµ t×m kiÕm
th«ng tin trªn web giíi thiÖu kh¸i qu¸t vÒ c¸c ph−¬ng ph¸p biÓu diÔn vµ t×m kiÕm trªn
web.
Tiªu ®Ò cña ch−¬ng 2 lµ Ph−¬ng ph¸p biÓu diÔn trang web theo ng÷ nghÜa l©n
cËn siªu liªn kÕt. Ch−¬ng nµy tr×nh bµy c¬ së, néi dung cña ph−¬ng ph¸p ®−îc ®Ò xuÊt
vµ ®¸nh gi¸ ph−¬ng ph¸p ®−îc ®Ò xuÊt víi c¸c ph−¬ng ph¸p kh¸c. LuËn v¨n còng tr×nh
bµy chi tiÕt c¸c lùa chän ®−îc ®Ò xuÊt trong mçi b−íc cña ph−¬ng ph¸p, tõ ®ã chän ra
gi¶i ph¸p tèt nhÊt.
Ch−¬ng 3 M¸y t×m kiÕm VietSeek vµ thö nghiÖm ThuËt to¸n t×m kiÕm theo ng÷
nghÜa l©n cËn siªu liªn kÕt giíi thiÖu kiÕn tróc logic cña m¸y t×m kiÕm VietSeek, thiÕt
kÕ logic vÒ d÷ liÖu theo biÓu diÔn vector vµ thuËt to¸n t×m kiÕm theo néi dung trªn c¬ së
biÓu diÔn trang web do luËn v¨n ®Ò xuÊt. Ch−¬ng nµy còng ®Ò xuÊt nh÷ng c¶i tiÕn khi
¸p dông vµo thùc tÕ ®Ó n©ng cao hiÖu suÊt thùc hiÖn cña ph−¬ng ph¸p biÓu diÔn.
PhÇn kÕt luËn tæng hîp nh÷ng kÕt qu¶ nghiªn cøu chÝnh cña luËn v¨n vµ chØ ra
mét sè h¹n chÕ cña luËn v¨n. §ång thêi luËn v¨n ®Ò xuÊt mét sè h−íng nghiªn cøu cô
thÓ tiÕp theo cña luËn v¨n.
PhÇn phô lôc bæ sung mét sè th«ng tin chi tiÕt vÒ viÖc ¸p dông thuËt to¸n cho
m¸y t×m kiÕm VietSeek nh− s¬ ®å khèi mét sè module cÇn bæ sung chøc n¨ng, nh÷ng
lÖnh bæ sung vµo c¬ së d÷ liÖu cña VietSeek.
§Æng TiÓu Hïng – LuËn v¨n cao häc
5
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
1
Ch−¬ng 1. Tæng quan vÒ t×m kiÕm th«ng tin trªn web
1.1 Giíi thiÖu vÒ t×m kiÕm th«ng tin
Khai ph¸ d÷ liÖu trªn web (Web Mining) lµ qu¸ tr×nh kh¶o s¸t vµ ph©n tÝch d÷ liÖu
web mét c¸ch tù ®éng hoÆc b¸n tù ®éng ®Ó ph¸t hiÖn ra th«ng tin. Tõ th«ng tin ®−îc
khai ph¸, t×m kiÕm th«ng tin (Infomartion Retrieval) trªn web lµ ph−¬ng ph¸p ®Ó truy
cËp mét c¸ch hiÖu qu¶ nhÊt ®Õn th«ng tin mµ ng−êi dïng quan t©m, kú väng cung cÊp
mét tËp hîp nhá c¸c v¨n b¶n gÇn nhÊt ®Õn lÜnh vùc hoÆc chñ ®Ò mµ ng−êi dïng mong
muèn tiÕp cËn.
H×nh 1. T×m kiÕm th«ng tin
1.2 Bµi to¸n t×m kiÕm th«ng tin
Cã 2 bµi to¸n c¬ b¶n trong t×m kiÕm th«ng tin lµ t×m kiÕm theo tõ kho¸ vµ t×m
kiÕm theo néi dung. Bµi to¸n t×m kiÕm theo tõ kho¸ lµ bµi to¸n t×m kiÕm th«ng tin theo
§Æng TiÓu Hïng – LuËn v¨n cao häc
6
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
c¸c tõ khãa do ng−êi dïng cung cÊp [1][1]. HÖ t×m kiÕm sÏ tr¶ vÒ cho ng−êi dïng c¸c
trang web cã chøa nh÷ng tõ kho¸ trong c©u hái. Tuy vËy, víi sè l−îng khæng lå c¸c
trang web trªn internet nh− hiÖn nay th× sè l−îng kÕt qu¶ t×m ®−îc theo tõ kho¸ lµ qu¸
lín. VÝ dô nÕu t×m c¸c trang web cã tõ kho¸ find similar web page th× cho kÕt qu¶ 858
trang web.
H×nh 2. T×m kiÕm th«ng tin theo tõ kho¸
B»ng c¸ch t×m kiÕm theo côm tõ kho¸ th× sè l−îng kÕt qu¶ tr¶ vÒ chÝnh x¸c h¬n,
sè kÕt qu¶ tr¶ vÒ lµ 25 trang web.
§Æng TiÓu Hïng – LuËn v¨n cao häc
7
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
H×nh 3. T×m kiÕm th«ng tin theo côm tõ kho¸
NÕu t×m trang web t−¬ng tù víi mét trang web mÉu th× sè l−îng kÕt qu¶ chØ lµ 8
trang web.
§Æng TiÓu Hïng – LuËn v¨n cao häc
8
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
H×nh 4. T×m kiÕm th«ng tin theo néi dung mét trang web mÉu
Mét c¸ch tiÕp cËn kh¸c lµ t×m kiÕm theo c¸c site ®−îc ®Ò cËp trong luËn v¨n cña
Ph¹m Thanh Nam [1] v× sè l−îng c¸c site Ýt biÕn ®éng vµ Ýt h¬n rÊt nhiÒu so víi c¸c
trang web. Tuy vËy, do l−îng th«ng tin øng víi mçi lÜnh vùc ®Òu rÊt lín nªn vÉn qu¸
khã kh¨n ®Ó tiÕp cËn c¸c trang v¨n b¶n ®¸p øng mong muèn víi yªu cÇu ng−êi dïng.
ChÝnh v× lý do ®ã mµ c¸c ®Ò tµi nghiªn cøu nh÷ng n¨m gÇn ®©y ®i s©u vÒ lÜnh vùc t×m
kiÕm theo néi dung t−¬ng tù víi trang v¨n b¶n mÉu nh− luËn v¨n th¹c sÜ cña Ph¹m
Thanh Nam n¨m 2003 [1], luËn ¸n tiÕn sÜ cña Se¸n Slattery n¨m 2002 [13] hoÆc trong
mét sè b¸o c¸o vÒ WWW ®−îc tæ chøc n¨m 2002[12], n¨m 2003. §Ó ®¸p øng c¸c yªu
cÇu t×m kiÕm th«ng tin cña ng−êi dïng mét c¸ch nhanh nhÊt, tÊt c¶ c¸c gi¶i ph¸p t×m
kiÕm th«ng tin ®Òu chia thµnh 2 giai ®o¹n thùc hiÖn t−¬ng ®èi ®éc lËp víi nhau
§Æng TiÓu Hïng – LuËn v¨n cao häc
9
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
• Giai ®o¹n 1: Thu thËp vµ ph©n tÝch th«ng tin vÒ c¸c trang web.
• Giai ®o¹n 2: Xö lý c©u hái vµ tr¶ lêi
Giai ®o¹n 1
WWW
Giai ®o¹n 2
Index
database
index process
Client
web
repository
Webserver
searchd
daemon
H×nh 5: KiÕn tróc c¸c hÖ t×m kiÕm th«ng tin
Do giai ®o¹n 1 kh«ng t−¬ng t¸c trùc tiÕp víi ng−êi dïng nªn c¸c th«ng tin ®−îc
ph©n tÝch mét c¸ch ®Çy ®ñ nhÊt ®Ó gi¶m thiÓu c¸c ph©n tÝch ë giai ®o¹n sau. Sè l−îng
c¸c trang web ®−îc ph©n tÝch rÊt lín (hµng triÖu trang) nªn thêi gian thùc hiÖn giai
®o¹n 1 rÊt lín (tÝnh b»ng giê) cßn thêi gian thùc hiÖn giai ®o¹n 2 lµ rÊt nhá (tÝnh b»ng
phÇn tr¨m gi©y).
1.2.1 Giai ®o¹n 1: Thu thËp vµ ph©n tÝch th«ng tin
C¸c b−íc xö lý chÝnh:
• T×m duyÖt c¸c trang web. Tõ c¸c danh s¸ch ®Þa chØ ban ®Çu, bé phËn t×m
duyÖt sÏ t¶i trang web vµ chuyÓn cho bé phËn ph©n tÝch néi dung trang
web. C¸c trang web ban ®Çu cã ®é s©u lµ 0, c¸c liªn kÕt cã trong trang web
sÏ ®−îc bé phËn ph©n tÝch ghi nhËn l¹i víi ®é s©u lµ 1. Sau khi ®· ph©n tÝch
xong c¸c trang web cã ®é s©u lµ 0 th× bé t×m duyÖt tiÕp tôc t¶i néi dung c¸c
trang web cã ®é s©u lµ 1 ®Ó ph©n tÝch vµ t×m ra c¸c trang web cã ®é s©u lµ
§Æng TiÓu Hïng – LuËn v¨n cao häc
10
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
2. Qu¸ tr×nh t¶i trang web sÏ dõng l¹i khi ®¹t ®Õn mét ®é s©u nhÊt ®Þnh nµo
®ã do ng−êi dïng ®Æt tham sè nh− trong VietSeek lµ 256.
• Ph©n tÝch vµ l−u tr÷ th«ng tin biÓu diÔn trang web. §©y lµ b−íc c¬ b¶n
quyÕt ®Þnh ®Õn chÊt l−îng cña c¸c hÖ t×m kiÕm. C¸c trang web ®−îc ph©n
tÝch vÒ mÆt néi dung ®Ó x©y dùng thµnh vector biÓu diÔn trang web. C¸c
liªn kÕt cã trong trang web còng ®−îc ghi nhËn l¹i. C¸c trang web còng
®−îc ®¸nh gi¸ mèi t−¬ng quan víi c¸c trang kh¸c theo môc tiªu cña bµi
to¸n, vÝ dô nh− sù t−¬ng tù vÒ néi dung so víi c¸c trang web kh¸c hoÆc
ph©n vµo líp c¸c chñ ®Ò. Toµn bé thêi gian vµ tµi nguyªn cña c¸c hÖ t×m
kiÕm ®−îc sö dông trong b−íc nµy. Do ®ã b−íc nµy còng ®−îc chia thµnh
bµi to¸n nhá h¬n cÇn ph¶i gi¶i quyÕt lµ x©y dùng cÊu tróc biÓu diÔn th«ng
tin ®−îc cung cÊp tõ c¸c v¨n b¶n ®−îc ph©n tÝch, ph©n tÝch có ph¸p/ng÷
nghÜa, sinh vector biÓu diÔn, ph©n líp v¨n b¶n, ph©n côm v¨n b¶n, ph©n
tÝch kÕt qu¶. Nh÷ng néi dung nµy sÏ ®−îc tr×nh bµy trong môc 1.3, 1.4 vµ
1.5 cña ch−¬ng nµy.
• L−u tr÷ b¶n sao trang web. §Ó nhanh chãng truy xuÊt ®Õn néi dung trang
web t×m thÊy, th«ng th−êng c¸c hÖ t×m kiÕm th−êng l−u tr÷ s½n b¶n sao c¸c
trang web d−íi d¹ng nÐn cung cÊp cho ng−êi dïng. Ph−¬ng ph¸p nÐn
th−êng ®−îc dïng zip. ViÖc chän mét kü thuËt nÐn th−êng ®−îc c©n nh¾c
gi÷a tèc ®é vµ tû lÖ nÐn. Tû lÖ nÐn cña zip lµ 3/1 tuy cã nhá h¬n so víi c¸c
ph−¬ng ph¸p nÐn kh¸c nh−ng tèc ®é nÐn vµ gi¶i nÐn cña zip l¹i nhanh ®¸ng
kÓ.
1.2.2 Giai ®o¹n 2: Xö lý c©u hái vµ tr¶ lêi
C¸c b−íc xö lý chÝnh:
• Ph©n tÝch c©u hái cña ng−êi dïng. C¸c hÖ t×m kiÕm th«ng th−êng cho
phÐp ng−êi dïng t×m kiÕm c¸c trang web d−íi d¹ng biÓu thøc logic, ngoµi
ra ®Ó thuËn tiÖn vµ n©ng cao tÝnh chÝnh x¸c cña c©u hái, c¸c hÖ t×m kiÕm
§Æng TiÓu Hïng – LuËn v¨n cao häc
11
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
còng cho phÐp ng−êi dïng ®−a vµo c¸c ®iÒu kiÖn n©ng cao nh− t×m tõ trong
chñ ®Ò, t×m c¸c trang theo néi dung cña mét trang web, t×m theo thêi gian
xuÊt hiÖn, t×m theo ng«n ng÷ ..v.v. C©u hái cña ng−êi dïng sÏ ®−îc ph©n
tÝch thµnh c¸c ®iÒu kiÖn ®Ó hÖ t×m kiÕm cã nh÷ng øng xö phï hîp.
• §Þnh vÞ c¸c trang web kÕt qu¶ vµ xÕp h¹ng. Dùa trªn c¸c ®iÒu kiÖn cña
ng−êi dïng vµ c¸c trang web ®· ®−îc ph©n tÝch trong giai ®o¹n “thu thËp
vµ ph©n tÝch th«ng tin” hÖ t×m kiÕm nhanh chãng ®Þnh vÞ ra ®−îc c¸c
trang web kÕt qu¶, h¬n n÷a c¸c trang web còng ®−îc lÊy ra theo møc ®é
t−¬ng quan víi c©u hái cña ng−êi dïng theo mét sè tiªu chÝ s¾p xÕp, vÝ dô
nh− thø tù cã xuÊt hiÖn c¸c tõ kho¸ trong c©u hái, møc ®é gÇn víi néi dung
trang web mÉu. Møc ®é chÝnh x¸c cña trang web ®èi víi c©u hái cña ng−êi
dïng (h¹ng cña trang web) còng ®−îc tÝnh to¸n vµ cung cÊp cho ng−êi
dïng. Mét sè hÖ t×m kiÕm cßn bæ sung thªm tÝnh n¨ng xö lý c¸c ph¶n håi
cña ng−êi dïng víi kÕt qu¶ ®Ó n©ng cao ®é chÝnh x¸c cho c¸c lÇn tr¶ lêi
sau nh− ghi nhËn sè lÇn truy cËp cña trang web ®Ó t¨ng ®é −u tiªn vÒ h¹ng
cña trang web, thay ®æi ®é t−¬ng tù cña c¸c trang web ®· ph©n tÝch, chuyÓn
trang web vµo nhãm v¨n b¶n cã chñ ®Ò chÝnh x¸c h¬n.
• HiÓn thÞ néi dung trang web s½n cã. Ng−êi dïng cã thÓ lÊy trang web tõ
®Þa chØ ®−îc cung cÊp bëi hÖ t×m kiÕm hoÆc cã thÓ xem néi dung trang web
s½n cã trong kho l−u tr÷ cña hÖ t×m kiÕm. Thao t¸c nµy yªu cÇu hÖ t×m
kiÕm gi¶i nÐn trang web vµ hiÓn thÞ. Th«ng th−êng th× hÖ t×m kiÕm sÏ t«
s¸ng c¸c thµnh phÇn cã trong c©u hái cña ng−êi dïng b»ng c¸c mµu s¾c ®Ó
ng−êi dïng nhanh chãng nhËn ra vÞ trÝ cña chóng trong trang web kÕt qu¶.
1.3 M« h×nh biÓu diÔn th«ng tin cña v¨n b¶n
C¬ së d÷ liÖu Fulltext lµ c¬ së d÷ liÖu phi cÊu tróc biÓu diÔn th«ng tin cña v¨n b¶n
mµ d÷ liÖu chøa trong ®ã bao gåm c¸c néi dung v¨n b¶n vµ c¸c thuéc tÝnh cña c¸c néi
dung ®ã. D÷ liÖu trong c¬ së d÷ liÖu Fulltext th−êng ®−îc tæ chøc nh− mét sù kÕt hîp
§Æng TiÓu Hïng – LuËn v¨n cao häc
12
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
gi÷a hai phÇn: phÇn c¬ së d÷ liÖu th«ng th−êng qu¶n lý thuéc tÝnh cña c¸c v¨n b¶n, vµ
phÇn tËp hîp néi dung c¸c v¨n b¶n ®−îc qu¶n lý [3].
C¬ së d÷ liÖu Fulltext
C¬ së d÷ liÖu vÒ
thuéc tÝnh tµi liÖu
C¬ së d÷ liÖu vÒ
néi dung tµi liÖu
H×nh 6. M« h×nh tæ chøc cña c¬ së d÷ liÖu Fulltext
HiÖn nay cã ba m« h×nh c¬ së d÷ liÖu Fulltext ®iÓn h×nh lµ
1. M« h×nh logic
2. M« h×nh có ph¸p
3. M« h×nh vector
M« h×nh vector lµ m« h×nh ®−îc sö dông phæ biÕn nhÊt trong c¸c hÖ t×m kiÕm
hiÖn nay.
1.3.1 M« h×nh biÓu diÔn th«ng tin theo tõ kho¸
Mçi v¨n b¶n ®−îc biÓu diÔn nh− mét vector cã c¸c thµnh phÇn lµ thÓ hiÖn tõ kho¸
t−¬ng øng cã mÆt hoÆc kh«ng cã mÆt trong v¨n b¶n ®ã. Mçi tõ kho¸ l¹i cã mét träng sè
biÓu diÔn vÒ møc ®é quan träng cña nã trong v¨n b¶n. Qu¸ tr×nh g¸n c¸c gi¸ trÞ ®ã ®−îc
gäi lµ qu¸ tr×nh ®¸nh chØ sè (indexing). HiÖn nay cã nhiÒu ph−¬ng ph¸p ®¸nh chØ sè
nh− TF, IDF, TF*IDF, LSI [3]... trong ®ã chñ yÕu dùa vµo tÇn sè xuÊt hiÖn cña c¸c tõ
§Æng TiÓu Hïng – LuËn v¨n cao häc
13
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
hoÆc mèi quan hÖ gi÷a sù xuÊt hiÖn cña c¸c tõ trong v¨n b¶n. Nh− vËy th× sè chiÒu cña
kh«ng gian vector lµ lùc l−îng cña tËp c¸c tõ kho¸.
VÝ dô v¨n b¶n thø nhÊt cã néi dung “VietKey 32-Bit lµ ch−¬ng tr×nh hç trî gâ
tiÕng ViÖt trong c¸c m«i tr−êng Windows 32-Bit cña Microsoft”.
Vµ v¨n b¶n thø 2 “VietKey cã thÓ nhóng ®−îc tiÕng ViÖt trong hÇu hÕt c¸c øng
dông 16-bit vµ 32-bit trong m«i tr−êng Windows 32-bit”
Vector biÓu diÔn v¨n b¶n sÏ gåm c¸c thµnh (tõ kho¸, tÇn suÊt cña tõ trong v¨n
b¶n):
Tõ kho¸
Vector biÓu diÔn v¨n b¶n 1
Vector biÓu diÔn v¨n b¶n 2
16
0
1
32
2
2
bit
1
3
c¸c
1
1
cã
0
1
cña
1
0
ch−¬ng
1
0
dông
0
1
®−îc
0
1
gâ
1
0
hÇu
0
1
hÕt
0
1
hç
1
0
lµ
1
0
§Æng TiÓu Hïng – LuËn v¨n cao häc
14
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
m«i
1
1
microsoft
1
0
nhóng
0
1
thÓ
0
1
tiÕng
1
1
tr×nh
1
0
tr−êng
1
1
trî
1
0
trong
1
2
øng
0
1
vµ
0
1
vietkey
1
1
viÖt
1
1
windows
1
1
B¶ng 1. Vector biÓu diÔn v¨n b¶n
1.3.2 M« h×nh biÓu diÔn th«ng tin theo néi dung
§èi víi bµi to¸n t×m kiÕm theo néi dung, phÇn lín c¸c gi¶i ph¸p t×m kiÕm th«ng
tin ®Òu lùa chän m« h×nh vector. Cã ba ph−¬ng ph¸p tiÕp cËn trong viÖc x¸c ®Þnh tõ
kho¸ trong vector biÓu diÔn v¨n b¶n.
1. Ph−¬ng ph¸p biÓu diÔn theo néi dung v¨n b¶n: Tõ kho¸ trong vector biÓu
diÔn v¨n b¶n u lµ nh÷ng tõ cã mÆt trong v¨n b¶n u.
2. Ph−¬ng ph¸p tiÕp cËn theo liªn kÕt: Tõ kho¸ trong vector biÓu diÔn v¨n b¶n
u lµ nh÷ng tõ khãa cã trong ®Þnh danh cña nh÷ng v¨n b¶n v cã liªn kÕt ®Õn
v¨n b¶n u.
§Æng TiÓu Hïng – LuËn v¨n cao häc
15
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
3. Ph−¬ng ph¸p tiÕp cËn theo ng÷ nghÜa l©n cËn liªn kÕt: Tõ kho¸ trong vector
biÓu diÔn v¨n b¶n u lµ nh÷ng tõ xuÊt hiÖn trong cöa sæ ng÷ nghÜa l©n cËn
liªn kÕt tõ nh÷ng v¨n b¶n v ®Õn v¨n b¶n u.
LuËn v¨n ®Ò cËp tíi gi¶i ph¸p kÕt hîp c¸c ph−¬ng ph¸p tiÕp cËn trªn ®©y.
1.4 Ph©n tÝch có ph¸p vµ ng÷ nghÜa
Trong trang web kh«ng chØ cã th«ng tin thÓ hiÖn néi dung mµ cßn c¸c th«ng tin
phô trî nh− c¸c comment, c¸c ®o¹n m·, c¸c thÎ HTML. Do ®ã cÇn ph¶i t¸ch läc th«ng
tin mµ trang web biÓu diÔn, t¸ch th«ng tin vÒ c¸c liªn kÕt. CÇn ph¶i x¸c ®Þnh tõ gèc cña
tõ biÓu diÔn v¨n b¶n, x¸c ®Þnh vÞ trÝ cña tõ trong v¨n b¶n, x¸c ®Þnh c¸c biªn cña ®o¹n
v¨n theo có ph¸p c©u (dÊu ng¾t c©u) hoÆc biªn theo chñ ®Ò ®o¹n v¨n (ng¾t ®o¹n, ng¾t
b¶ng, ng¾t trang).
1.5 Ph©n líp v¨n b¶n
Ph©n líp v¨n b¶n ®−îc xem nh− lµ qu¸ tr×nh g¸n c¸c v¨n b¶n vµo mét hay nhiÒu
líp v¨n b¶n ®· ®−îc x¸c ®Þnh tr−íc. Sau khi ®−îc ph©n líp, c¸c v¨n b¶n sÏ ®−îc ®¸nh
chØ sè ®èi víi tõng líp t−¬ng øng. Ng−êi dïng cã thÓ yªu cÇu hÖ t×m kiÕm giíi h¹n sè
kÕt qu¶ trong mét chñ ®Ò hoÆc líp v¨n b¶n mong muèn. Ph©n líp v¨n b¶n cã thÓ thùc
hiÖn tù ®éng b»ng c¸c ph−¬ng ph¸p c©y quyÕt ®Þnh [3], m¹ng Bayer, m¸y vector trî
gióp. Ngoµi ra, c¸c trang web cã thÓ thÓ ®−îc ph©n líp b»ng thñ c«ng nhê sù t×nh
nguyÖn cña ng−êi dïng trªn internet nh− th− môc chñ ®Ò c¸c trang web ODP (Open
Directory Project) [17].
1.6 Ph©n côm v¨n b¶n
Ph©n côm v¨n b¶n lµ viÖc tù ®éng sinh ra c¸c líp v¨n b¶n dùa vµo sù t−¬ng tù cña
c¸c v¨n b¶n. C¸c líp v¨n b¶n ë ®©y lµ ch−a biÕt tr−íc, ng−êi dïng cã thÓ chØ yªu cÇu sè
l−îng c¸c líp cÇn ph©n lo¹i, hÖ sÏ ®−a ra c¸c v¨n b¶n theo tõng tËp hîp, tõng côm, mçi
tËp hîp chøa c¸c v¨n b¶n t−¬ng tù nhau.
§Æng TiÓu Hïng – LuËn v¨n cao häc
16
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
1.7 Khai th¸c th«ng tin cÊu tróc web
Trong t×m kiÕm th«ng tin trªn web, c¸c trang web ®· chøa ®ùng th«ng tin nöa cÊu
tróc, ®ã chÝnh lµ c¸c liªn kÕt gi÷a c¸c trang web. Th«ng th−êng, c¸c web ®em l¹i nhiÒu
th«ng tin sÏ ®−îc trÝch dÉn nhiÒu do ®ã cã thÓ khai th¸c th«ng tin liªn kÕt gi÷a c¸c
trang web ®Ó ®¸nh gi¸ träng sè cña trang web nh− Slattery ®· ®Ò xuÊt [13].
1.8 Khai th¸c th«ng tin sö dông web
Th«ng tin sö dông web ®−îc chøa trong mét tËp hîp c¸c file liªn quan ®−îc ®Þnh
s½n trªn nh÷ng m¸y chñ web. Môc ®Ých cña viÖc khai th¸c th«ng tin sö dông web ®Ó
ph¸t hiÖn ra nh÷ng mÉu d÷ liÖu cã ý nghÜa ®−îc sinh ra trong nh÷ng giao dÞch
kh¸ch/chñ. Th«ng th−êng c¸c d÷ liÖu ®ã ë phÝa m¸y chñ lµ access logs, referrer logs,
agent logs vµ phÝa m¸y tr¹m lµ cookies. Mét d¹ng th«ng tin vÒ ng−êi dïng web lµ c¸c
profile cña hä.
Trong t×m kiÕm th«ng tin, c¸c trang web ®em l¹i nhiÒu th«ng tin th−êng ®−îc truy
cËp nhiÒu h¬n c¸c trang web kh¸c trong cïng chñ ®Ó. Do ®ã tÇn suÊt truy cËp (th«ng tin
sö dông web) cña c¸c trang web còng lµ mét thµnh phÇn cÇn xem xÐt khi ®¸nh gi¸ träng
sè cña trang web.
Tuy nhiªn, víi mçi ng−êi dïng th× cã thÓ cã tËp hîp c¸c trang web ®−îc yªu thÝch
cña riªng m×nh. Ng−êi sö dông cã thÓ yªu cÇu mµ hÖ t×m kiÕm cho phÐp giíi h¹n c¸c
trang kÕt qu¶ trong mét tªn miÒn nµo ®ã nh− .com.vn vµ nh÷ng tham sè nh− vËy cã thÓ
®−îc ®Þnh nghÜa trong c¸c profile.
KÕt luËn ch−¬ng 1
Trong ch−¬ng nµy, luËn v¨n ®· giíi thiÖu tæng qu¸t bµi to¸n t×m kiÕm th«ng tin
trªn web vµ c¸c ph−¬ng ph¸p t×m kiÕm th«ng tin trªn web:
1. C¸c ph−¬ng ph¸p t×m kiÕm theo tõ kho¸ gåm m« h×nh có ph¸p, m« h×nh
logic vµ m« h×nh vector. C¸c ph−¬ng ph¸p nµy ®· ®−îc nghiªn cøu kh¸
kü l−ìng vµ tiªu biÓu nhÊt lµ m« h×nh vector.
§Æng TiÓu Hïng – LuËn v¨n cao häc
17
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
2. C¸c ph−¬ng ph¸p t×m kiÕm theo néi dung ®ang ®−îc nghiªn cøu hiÖn nay
lµ t×m kiÕm theo néi dung toµn v¨n, theo liªn kÕt vµ theo ng÷ nghÜa l©n
cËn liªn kÕt.
LuËn v¨n ®· ph©n tÝch nguyªn t¾c ho¹t ®éng còng nh− −u ®iÓm vµ nh−îc ®iÓm cña
mçi ph−¬ng ph¸p. Tõ nh÷ng ph©n tÝch trªn, luËn v¨n sÏ tr×nh bµy ph−¬ng ph¸p biÓu
diÔn v¨n b¶n míi trong ch−¬ng 2 vµ ®Ò xuÊt thuËt to¸n t×m kiÕm theo néi dung trong
ch−¬ng 3.
§Æng TiÓu Hïng – LuËn v¨n cao häc
18
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
2
Ch−¬ng 2. ph−¬ng ph¸p biÓu diÔn trang web theo ng÷
nghÜa l©n cËn siªu liªn kÕt
2.1 Giíi thiÖu
Môc tiªu cña viÖc t×m kiÕm trang Web t−¬ng tù lµ cho phÐp ng−êi sö dông t×m
nh÷ng trang Web t−¬ng tù víi trang Web mÉu. VÒ c¬ b¶n, khi ®−a ra mét v¨n b¶n, mét
thuËt to¸n t×m kiÕm t−¬ng tù ph¶i cung cÊp danh s¸ch thø tù cña c¸c v¨n b¶n t−¬ng tù
víi v¨n b¶n mÉu.
Trong ch−¬ng nµy, luËn v¨n sÏ tr×nh bµy mét sè ph−¬ng ph¸p tiÕp cËn cña gi¶i
ph¸p t×m kiÕm theo néi dung vµ ®¸nh gi¸ chÊt l−îng cña mçi ph−¬ng ph¸p. Trªn c¬ së
ph−¬ng ph¸p biÓu diÔn trang web theo ng÷ nghÜa l©n cËn siªu liªn kÕt [12], luËn v¨n ®Ò
xuÊt mét sè bæ sung, c¶i tiÕn thµnh gi¶i ph¸p t×m kiÕm theo néi dung. C¨n cø trªn
nh÷ng kÕt qu¶ ®¸nh gi¸ qua thö nghiÖm, gi¶i ph¸p t×m kiÕm theo néi dung do luËn v¨n
®Ò xuÊt ®−îc xem lµ cã chÊt l−îng tèt h¬n so víi c¸c ph−¬ng ph¸p ®· kh¶o s¸t kh¸c vµ
®−îc ¸p dông cho m¸y t×m kiÕm VietSeek.
ThuËt to¸n t×m kiÕm gåm hai b−íc:
1. TiÒn xö lý c¸c trang web: T¹o vector biÓu diÔn trang web. So s¸nh c¸c
trang web trong cïng chñ ®Ò cña ODP ®Ó tÝnh to¸n s½n ®é t−¬ng tù c¸c
trang web.
2. Thùc hiÖn t×m kiÕm th«ng tin, chØ ®¬n thuÇn lµ thao t¸c ®Þnh vÞ vµ ®äc d÷
liÖu s½n cã trong c¬ së d÷ liÖu.
Ph−¬ng ph¸p nµy ®· ®−îc thö nghiÖm b»ng tËp d÷ liÖu lín vµ chøng tá tÝnh kh¶
thi cña nã. C¸c vÊn ®Ò chÝnh cÇn ph¶i gi¶i quyÕt trong ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa
l©n cËn siªu liªn kÕt lµ:
1. X¸c ®Þnh ph−¬ng ph¸p ®¸nh gi¸ chÊt l−îng cho ®é ®o t−¬ng tù.
2. X¸c ®Þnh m« h×nh vector biÓu diÔn trang web.
3. X¸c ®Þnh nghÜa ®é ®o t−¬ng tù víi m« h×nh biÓu diÔn ®· chän
§Æng TiÓu Hïng – LuËn v¨n cao häc
19
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
4. Kh¶o s¸t c¸c thµnh phÇn cña vector biÓu diÔn trang web
5. X©y dùng c¸c thuËt to¸n:
- ThuËt to¸n t¹o vector biÓu diÔn trang web
- ThuËt to¸n tÝnh ®é t−¬ng tù gi÷a c¸c trang web
- ThuËt to¸n t×m kiÕm trang web t−¬ng tù
C¸c vÊn ®Ò 1, 2, 3 vµ 4 sÏ ®−îc tr×nh bµy trong ch−¬ng 3 cña luËn v¨n. VÊn ®Ò 5
cã trong ®Ò xuÊt ph−¬ng ¸n thùc hiÖn cho m¸y t×m kiÕm VietSeek trong ch−¬ng 4.
2.2 Ph−¬ng ph¸p ®¸nh gi¸ chÊt l−îng ®é ®o t−¬ng tù
2.2.1 Chän ph−¬ng ph¸p ®¸nh gi¸
Khi kh¶o s¸t c¸c c¸ch tiÕp cËn ®Ó t×m ra ®−îc mét gi¶i ph¸p t×m kiÕm th«ng tin tèt
nhÊt th× cÇn thiÕt ph¶i cã mét ph−¬ng ph¸p ®¸nh gi¸ chÊt l−îng cho c¸c mçi ph−¬ng ¸n.
ChÊt l−îng xÕp h¹ng trang web cña m¸y t×m kiÕm th−êng ®−îc ®¸nh gi¸ bëi ng−êi
dïng dùa trªn c¸c ®é ®o vÒ kho¶ng c¸ch vµ ®Æc tr−ng cña v¨n b¶n. Tuy nhiªn, sö dông
trùc tiÕp sù ®¸nh gi¸ cña ng−êi dïng th−êng tèn thêi gian vµ c«ng søc, nªn ®iÒu ®ã
kh«ng thÝch hîp cho nh÷ng nghiªn cøu mµ ®ßi hái sù so s¸nh ®¸nh gi¸ cña nhiÒu tham
sè.
Trong v¨n b¶n vÒ ph©n côm, nhiÒu ph−¬ng ph¸p ®¸nh gi¸ chÊt l−îng tù ®éng ®·
®−îc ®Ò xuÊt [20]. Steinback [20] chia nh÷ng ph−¬ng ph¸p nµy thµnh 2 líp tæng qu¸t.
Ph−¬ng ph¸p ®¸nh gi¸ sö dông c¸c ®é ®o chÊt l−îng néi t¹i, nh− ®é t−¬ng tù trung b×nh,
chØ ra chÊt l−îng cña mét côm v¨n b¶n ®−îc ®Ò xuÊt dùa hoµn toµn trªn néi t¹i h×nh häc
vµ thèng kª, kh«ng dùa trªn mét tËp ch©n lý nÒn cã s½n. Ph−¬ng ph¸p ®¸nh gi¸ dùa trªn
c¸c ®é ®o chÊt l−îng ngoµi, nh− ®é ®o entropy, kiÓm tra sù t−¬ng quan cña mét côm
víi mét tËp ch©n lý nÒn cã s½n. §©y còng lµ ph−¬ng ph¸p ®¸nh gi¸ ®−îc sö dông ®Ó ®o
chÊt l−îng cña mét ph−¬ng ¸n.
C©y ph©n lo¹i chñ ®Ò c¸c trang web ODP [17] ®−îc x©y dùng vµ phæ dông trªn
Internet. Trong ODP, c¸c trang web ®−îc s¾p ph©n líp theo c¸c chñ ®Ò vµ thø tù cña nã
§Æng TiÓu Hïng – LuËn v¨n cao häc
20
Ph−¬ng ph¸p biÓu diÔn ng÷ nghÜa l©n cËn siªu liªn kÕt cho m¸y t×m kiÕm VietSeek
trong chñ ®Ò cã thÓ coi lµ h¹ng cña trang web trong chñ ®Ò t−¬ng øng. §é ®o t−¬ng tù
cña c¸c v¨n b¶n t−¬ng øng víi mét ph−¬ng ¸n biÓu diÔn th«ng tin vÒ v¨n b¶n cung cÊp
mét tËp thø tù. Do ®ã, cã thÓ dïng ODP lµm tËp thø tù nÒn ®Ó kiÓm tra chÊt l−îng xÕp
h¹ng cña mét ®é ®o t−¬ng tù. C¸c ®é ®o ®¸nh gi¸ ®é t−¬ng quan gi÷a h¹ng cña trang
web trong ODP vµ h¹ng cña trang web t−¬ng øng víi ®é ®o t−¬ng tù ®−îc x©y dùng
®−îc coi nh− lµ sù ®¸nh gi¸ gi¸n tiÕp cña ng−êi dïng vÒ chÊt l−îng xÕp h¹ng. TÊt nhiªn
lµ kh«ng thÓ sö dông trùc tiÕp ODP lµm thø tù cho gi¶i ph¸p t×m kiÕm v× nã chØ chøa
mét bé phËn c¸c trang web cã mÆt trªn Internet.
2.2.2 X¸c ®Þnh thø tù nÒn trong ODP
Dùa theo viÖc ph©n líp s½n cã c¸c v¨n b¶n cña ODP, dÔ thÊy r»ng c¸c v¨n b¶n
cïng mét líp (cïng chñ ®Ò) sÏ gÇn nhau vÒ néi dung h¬n so víi c¸c v¨n b¶n ë líp kh¸c
(chñ ®Ò kh¸c). VÝ dô, mét v¨n b¶n trong líp recreation/aviation/un-powered th−êng cã
néi dung gÇn víi c¸c v¨n b¶n kh¸c cïng líp so víi c¸c v¨n b¶n kh«ng thuéc líp ®ã.
H¬n n÷a, v¨n b¶n nµy l¹i "gÇn" víi c¸c v¨n b¶n kh¸c cña líp recreation/aviation h¬n lµ
c¸c v¨n b¶n ë khu vùc kh¸c cña c©y.
TÊt nhiªn lµ vÞ trÝ cña v¨n b¶n trong c©y ph©n lo¹i chñ ®Ò kh«ng thÓ mang l¹i sù
chÝnh x¸c vÒ néi dung mét c¸ch tuyÖt ®èi. VÝ dô trong chñ ®Ò recreation/autos, hÇu hÕt
gÇn víi c¸c v¨n b¶n ë shopping/autos h¬n lµ c¸c v¨n b¶n ë recreation/smoking. Tuy vËy
cã thÓ c¨n cø vµo ®ã ®Ó x©y dùng mét tiªu chuÈn cho ®é ®o t−¬ng tù v× c¸c c©y ph©n
lo¹i chñ ®Ò ®· cã sù s¾p xÕp ®é t−¬ng tù vÒ mÆt néi dung.
§Ó chuÈn ho¸ kh¸i niÖm kho¶ng c¸ch tõ mét v¨n b¶n nµy ®Õn mét v¨n b¶n kh¸c
trong c©y, kho¶ng c¸ch t−¬ng quan ®· ®−îc x¸c ®Þnh nh− d−íi ®©y.
Kho¶ng c¸ch t−¬ng quan
Kho¶ng c¸ch t−¬ng quan df(s,d) tõ mét v¨n b¶n mÉu s ®Õn mét v¨n b¶n d kh¸c
trong mét c©y ph©n líp lµ kho¶ng c¸ch tõ líp chøa s ®Õn líp cã kho¶ng c¸ch gÇn nhÊt
chøa c¶ s vµ d.
§Æng TiÓu Hïng – LuËn v¨n cao häc
- Xem thêm -