Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext

LINK DOWNLOAD MIỄN PHÍ TÀI LIỆU "Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext": http://123doc.vn/document/1040074-mot-so-giai-phap-cho-bai-toan-tim-kiem-trong-csdl-hypertext.htm

Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext

5
quan ó xut mt s phng phỏp biu din vn bn cho phộp thi hnh c nhng
khớa cnh ó cp trờn õy [2-4,8-14].
T vic tỡm hiu v phõn tớch u, nhc im ca cỏc phng phỏp tip cn khỏc
nhau, da trờn ý tng nõng cao hiu qu tỡm kim, lun vn cp vic s dng mụ
hỡnh vector biu din trang web trong cỏc mỏy tỡm kim cho phộp d dng b sung
trng s cho cỏc t khoỏ tỡm kim v tng cng c ng ngha ni dung vn bn vo
quỏ trỡnh tỡm kim.
Vi mc tiờu xut mt phng phỏp biu din vector cho cỏc trang web trong
cỏc mỏy tỡm kim nõng cao hiu qu tỡm kim, ni dung ca lun vn c nh
hng vo cỏc vn sau:
- Gii thiu, phõn tớch v ỏnh giỏ mt s phng phỏp biu din trang web in
hỡnh,
- Trờn c s mt s phng phỏp biu din vn bn trang web theo mụ hỡnh
vector, lun vn nghiờn cu vic ci tin cỏc phng phỏp biu din ú nhn c
mt phng phỏp mi biu din trang web,
- Nghiờn cu, xut vic b sung thờm biu din vector cho trang web trong cỏc
mỏy tỡm kim theo phng phỏp mi, ng thi b sung chc nng tỡm kim trang
Web "theo ni dung" cho h tỡm kim Vietseek.
Lun vn bao gm Phn m u, ba chng ni dung v Phn kt lun m ni
dung cỏc chng c trỡnh by nh di õy.
Chng 1 vi tiờu l Tng quan v web-mining gii thiu s b nhng ni
dung tng quan nht v c s d liu Fulltext, c s d liu Hypertext, c s d liu
trang web v phng phỏp biu din vector. Trong chng ny cỏch tip cn theo
website c trỡnh by khỏ chi tit v c khớa cnh biu din website ln gii phỏp cho
bi toỏn tỡm kim theo website. Lun vn cũn xut mt thut toỏn xõy dng cõy
website theo cỏch tip cn ny.


Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext

6
Tiờu ca chng 2 l Mt s phng phỏp biu din d liu web v gii phỏp
kt hp. Ni dung ca chng ny xem xột v ỏnh giỏ mt s phng phỏp biu din
trang web in hỡnh. u tiờn lun vn gii thiu v biu din trang web trong cỏc mỏy
tỡm kim, sau ú lun vn gii thiu cỏch tip cn theo mụ hỡnh vector biu din
trang web v mt xut v mt cỏch biu din trang web. Phn cui cựng ca chng
ny trỡnh by xut ca lun vn b sung cỏch biu din mi cho trang web vo mỏy
tỡm kim v s b v thut toỏn tỡm kim theo ni dung.
Chng 3 Mỏy tỡm kim VietSeek v th nghim thut toỏn tỡm kim theo ni
dung gii thiu chi tit v mỏy tỡm kim VietSeek, thit k lụgic v d liu theo biu
din vector v thut toỏn tỡm kim theo ni dung trờn c s do lun vn xut.
Phn kt lun tng hp nhng kt qu nghiờn cu chớnh ca lun vn, ch ra mt
s hn ch cha hon thin ci t thc s. ng thi lun vn cng xut mt s
hng nghiờn cu c th tip theo ca tỏc gi lun vn.


Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext

7
BNG CH GII MT S CM T VIT TT
CSDL: C s d liu (DataBase)
CNTT: Cụng ngh thụng tin (Information Technology)
kNN: k Nearest Neighbour
KPDL: Khai phỏ d liu (Data Mining)
KPTTCSDL: Khỏm phỏ tri thc trong CSDL (Knowledge Discovery in Databases)
SVM: Support Vector Machine
WWW: H thng trang Web (World Wide Web)

BNG CH GII MT S THUT NG TING VIT
Bayes t nhiờn: Naive Bayes
k ngi lỏng ging gn nht: k Nearest Neighbour
Mng nron: Neural Net
Mỏy tỡm kim: Search engine
B iu khin tỡm duyt: Crawl Control
B tỡm duyt: Crawler
B to ch mc: Indexer Module
B phõn tớch tp: Collection Analysis Modele
B truy vn: Query Engine
B xp hng: Ranking
B phõn tớch URL: URLresolver
Ch mc cu trỳc: Structure Index
Ch mc liờn kt ngc: Inverted Index
Ch mc ni dung: Text Index
Ch mc tin ớch: Utility Index
Hng hin th: Rank
Hng trang web (Hng): Page Rank
Kho trang web: Page Repository
Ti trang: Download


Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext

8
Mỏy vector tr giỳp: Support Vector Machine
Mụ hỡnh (khụng gian) vector: Vector (Space) Model
Siờu liờn kt: Hyperlink
Siờu vn bn: Hypertext
Tỡm kim theo ni dung: text-based retrieval
Trang web: web page, HTML page, HTML document





Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext

9
1 CHNG I. TNG QUAN V WEB-MINING
1.1 Gii thiu v c s d liu Fulltext v Hypertext
1.1.1 C s d liu Fulltext
Gii thiu chung
C s d liu Fulltext l c s d liu phi cu trỳc m d liu cha trong ú bao
gm cỏc ni dung text v cỏc thuc tớnh v ti liu vn bn vi ni dung ú. D liu
trong c s d liu Fulltext thng c t chc nh mt s kt hp gia hai phn:
phn c s d liu thụng thng qun lý thuc tớnh ca cỏc ti liu, v phn tp hp
ni dung cỏc ti liu c qun lý. Chỳng ta cú th hỡnh dung mt c s d liu
Fulltext c t chc nh sau:







Trong nhng trng hp ph bin, ni dung ti liu c lu gi giỏn tip trong
c s d liu theo ngha h thng ch qun lý cỏc con tr (a ch ) tr ti cỏc a ch
cha ni dung ti liu (mt vớ d d thy nht l mng Internet, cỏc trang web thng
lu gi cỏc a ch ch ti ni cú lu ni dung cỏc trang thụng tin c th m ngi s
dng mun xem). Cũn cỏc con tr (a ch) v cỏc thuc tớnh khỏc v nú thỡ c lu
trc tip trong c s d liu bng h qun tr cú cu trỳc.

Cơ sở dữ liệu Fulltext
CSDL về thuộc tính tài liệu

Tập hợp nội
dung các tài liệu

Hình 1.1
Mô hình tổ chức của cơ sở dữ liệu Fulltext




Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext

10
Tuy nhiờn, trong mt s trng hp (c bit l i vi cỏc mỏy tỡm kim trờn
Internet nh Yahoo, Google, AltaVista ), cung cp ni dung vn bn nhanh chúng,
ngi ta li t chc lu tr cỏc vn bn ngay trong h thng (di dng vựng cache).
Ni dung ca d liu Fulltext (vn bn) khụng cú cu trỳc ni ti, c coi nh
mt l dóy cỏc t, cỏc du ngn cỏch. Ng ngha vn bn da trờn ý ngha cỏc t mang
ngha (c gi l t khúa - term hoc keyword) cú trong vn bn v cỏch b trớ cỏc t
khúa trong vn bn ú. Do khụng cú cu trỳc nờn bi toỏn t chc theo cu trỳc hon
ton cỏc t khúa trong vn bn l khụng thớch hp do tớnh cht quỏ phc tp khi thc
hin iu ú. Do ú, ph bin hn ngi ta s dng cỏc phng phỏp biu din ng
ngha vn bn thụng qua tp cỏc t khoỏ cú trong vn bn ú.
Cỏc c s d liu Fulltext hin nay thng l cỏc tp hp sỏch, tp chớ, bi vit
c qun lý trong mt mng th vin in t, tp cỏc file v cỏc trang web (l cỏc
trang file) c lu tr bi cỏc h thng web nh h thng ca Yahoo, Google,
AltaVista
Nh ó núi, lm th no hiu c ni dung ca cỏc ti liu trong c s d
liu? Tn ti cỏc phng phỏp biu din c s dng nh phng phỏp túm tt,
phng phỏp vector, mng logic, lc cỳ phỏp. Nhng cỏc phng phỏp ú ch
cha ng c ni dung s si, túm tt ca ti liu. Hn na mi mt phng phỏp
li cú cỏc khú khn riờng, c bit l khi h thng cho phộp cp nht thờm d liu. Vỡ
vy m vic ci tin cỏc mụ hỡnh biu din ny luụn luụn c t ra
C s d liu Fulltext cú rt nhiu khớa cnh tim nng tt cho vic khai phỏ d
liu v KDD, vi cỏc mc tiờu l t ng tr giỳp ngi dựng h cú th s dng h
thng ti liu hiu qu hn (phõn lp ti liu, tỡm kim thụng tin v tỡm kim ti liu)
v mụ hỡnh vector l mụ hỡnh tt hn c trỡnh by ti liu Fulltext
Do ng ngha ca cỏc vn bn Fulltext thng c biu din thụng qua cỏc t
khoỏ ca nú nờn trong quỏ trỡnh x lý cỏc d liu Fulltext thng ny sinh cỏc vn
v t ng ngha v t a ngha. Nh chỳng ta ó bit thỡ trong ngụn ng t nhiờn luụn


Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext

11
cú cỏc t ng ngha (l trng hp cú nhiu t vit khỏc nhau u ch chung mt ý
ngha ging nhau) v cỏc t a ngha (l trng hp mt t nhng cú nhiu ngha khỏc
nhau). Trong thc t giao tip chỳng ta cng thng xuyờn gp phi cỏc tỡnh hung
hiu nhm ý ngha mun din t ca ngi núi khi gp phi cỏc t ng ngha v a
ngha. Vỡ vy trong x lý vn bn chc chn s khụng trỏnh khi nhng khú khn do
vn ny gõy ra. Do ú chỳng ta phi tỡm cỏch khc phc cỏc vn ny. ó cú mt
s hng nghiờn cu gii quyt vn t ng ngha v a ngha c tin hnh
[1,4,7] nh: liờn kt t ng ngha vi t khoỏ, dựng trng s th hin quan trng
cỏc t, chun hoỏ biu din vn bn, biu din ng cnh t khoỏ, biu din qua tp
m
Mụ hỡnh vector vi gii phỏp vn a ngụn ng v t ng ngha
Hin nay mụ hỡnh biu din d liu fulltext in hỡnh nht l mụ hỡnh. Theo mụ
hỡnh vector thỡ h thng c s d liu Fulltext qun lý cỏc ti liu thuc mt phm vi
hot ng ca con ngi c th hin qua mt tp t khoỏ V (cỏc t khoỏ ny cú
mang ý ngha ca ni dung cỏc ti liu). Nh vy l tp hp cỏc t khoỏ cú trong ti
liu biu din ni dung ca ti liu ú.
p dng bi toỏn tỡm kim trong c s d liu Fulltext thỡ quỏ trỡnh tỡm kim
gm hai giai on con l: quỏ trỡnh trỡnh by cõu hi (mó hoỏ cõu hi) v quỏ trỡnh x
lý trờn cỏc vector. Do s lng cỏc t trong cõu hi thng l nh nờn thi gian ca
quỏ trỡnh mó hoỏ cõu hi thng ngn. Ngc li, thi gian cho vic x lý trờn cỏc
vector thng khỏ ln, v ph thuc vo kớch thc ca cỏc vector v s lng cỏc
phộp tớnh gia cõu hi vi cỏc vector mó hoỏ ca ti liu. Trờn thc t thỡ s lng ln
nht cỏc phộp toỏn l A
*
n, vi A l s lng ti liu c lu tr trong c s d liu
v n l s lng cỏc t trong cõu hi c a ra. gim s lng cỏc phộp toỏn
trong giai on x lý trờn cỏc vector thỡ chỳng ta cú th xem xột gim kớch thc ca
vector trỡnh by ti liu, v kt qu l thay vỡ phi mó húa tt c cỏc t khoỏ xut hin


Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext

12
trong khụng gian c s d liu thỡ ta ch cn mó hoỏ cỏc t khoỏ xut hin trong ti
liu. Ngoi ra cú mt cỏch rt n gin cú th tng chớnh xỏc tỡm kim l tỏch riờng
phn tiờu ca ti liu ra thnh mt phn. Thụng thng, cỏc ti liu cú phn tiờu
th hin túm tt ni dung ca ti liu, chớnh vỡ vy m chỳng ta cú th tỏch phn tiờu
ra khi ni dung ca ti liu v biu din nú bng mt vector riờng, c lp vi phn
ni dung. Khi ú ngoi vic tỡm kim theo ni dung chỳng ta s a thờm la chn tỡm
kim theo tiờu . Vỡ phn tiờu bao gi cng ngn hn phn ni dung rt nhiu nờn
vic tỡm kim theo tiờu s din ra rt nhanh m li mang li cho chỳng ta chớnh
xỏc tỡm kim cao hn.
Vi bi toỏn tỡm kim thỡ vn t ng ngha nh ó nờu phn trờn cn phi
c trin khai nu khụng chỳng ta s ch tỡm c cỏc ti liu cha cỏc t cú trong
cõu hi, cũn cỏc ti liu cú cựng ni dung nhng cú cỏch th hin khỏc s b b qua.
gii quyt vn ny l chỳng ta xõy dng mt bng lit kờ danh sỏch cỏc t
ng ngha thuc nhiu ngụn ng cựng vi cỏc h s tng quan v mt ý ngha gia
chỳng. V trong mt nhúm cỏc t ng ngha mc dự cựng biu t mt ni dung
nhng vai trũ ca cỏc t cú th khỏc nhau do cỏc lý do sau: vi mt ni dung c th
ny thỡ t ny hay c s dng hn t kia, cũn vi mt ni dung c th khỏc thỡ cú
th li khỏc [3,9,12]. Vic thng kờ v n nh h s cho cỏc t ng ngha trong mt
nhúm cỏc t ng ngha l mt vic lm phc tp v rc ri, ũi hi phi cú tri thc v
ng ngha ca cỏc t trong nhiu ngụn ng khỏc nhau. Vỡ vy vic ny cn nhn c
s phi hp vi cỏc nh ngụn ng hc.
1.1.2 C s d liu Hypertext
Hypertext l thut ng c Theodore Nelson a ra ln u tiờn nm 1965 ti
hi tho ca Hi toỏn hc M ACM ln th 20. Theo Nelson thỡ Hypertext l cỏc ti
liu dng ch vit khụng liờn tc. Chỳng c phõn nhỏnh v cho phộp ngi c cú
th chn cỏch c theo ý mun ca mỡnh, tt nht l nờn c nú trờn cỏc mn hỡnh cú
kh nng tng tỏc.


Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext

13
Hiu theo ngha thụng thng thỡ Hypertext l mt tp cỏc trang ch vit c
kt ni vi nhau bi cỏc liờn kt, v nú cho phộp ngi c cú th c theo cỏc cỏch
khỏc nhau.
Hypertext cng cú th bao gm mt tp ch vit liờn tc, v õy cng chớnh l
dng ph bin nht ca ch vit. Do khụng b hn ch bi tớnh liờn tc nờn trong
Hypertext, chỳng ta cú th to ra cỏc dng trỡnh by mi, v nh ú m ti liu ca
chỳng ta s phn ỏnh tt hn ni dung m chỳng ta ang mun vit. V ngi c cú
th chn cho mỡnh mt cỏch c phự hp, vớ d h cú th i sõu vo mt vn m h
thớch thỳ, hoc cú th tip tc mch suy ngh hin ti ca h theo cỏch m t trc vn
c coi l khụng th.
Theo t in ca i hc Oxford (Oxford English Dictionary Additions Series)
thỡ Hypertext c nh ngha nh sau: l loi Text khụng phi c theo dng liờn tc
n, v nú cú th c c theo cỏc th t khỏc nhau; c bit l Text v nh ho
(Graphic) l cỏc dng cú mi liờn kt vi nhau theo cỏch m ngi c cú th khụng
cn c nú mt cỏch liờn tc. Vớ d khi c mt cun sỏch ngi c khụng cn c
ln lt t u n cui m cú th nhy cúc n cỏc on khỏc nhau tham kho cỏc
vn cú liờn quan.
Sỏng kin to ra mt tp cỏc vn bn cựng vi cỏc con tr tr ti cỏc vn bn
khỏc mt cỏch rừ rng liờn kt mt tp cỏc vn bn cú mi quan h vi nhau l mt
cỏch thc s hay v rt hu ớch t chc thụng tin. Vi ngi vit, cỏch ny cho phộp
h cú th thoi mỏi loi b nhng bn khon v th t trỡnh by nhng vn cú liờn
quan n nhau tp trung vo hon thnh cỏc vn nh, v sau ú h cú th s dng
cỏc kt ni ch ra cho ngi c thy c cỏc vn nh ú cú mi quan h vi
nhau nh th no. Ti õy, theo mt ngha no ú, chỳng ta gp li t tng mụ un
húa trong thit k thut toỏn v vit chng trỡnh. Vi ngi c, cỏch ny cho phộp h
cú th i tt trờn mng thụng tin v t quyt nh phn thụng tin no cú liờn quan n
vn h ang quan tõm tip tc tỡm hiu. So sỏnh vi cỏch c tuyn tớnh, tc l


Một số giải pháp cho bài toán tìm kiếm trong CSDL Hypertext

14
c ln lt, thỡ Hypertext ó cung cp cho chỳng ta mt giao din cú th tip xỳc
vi ni dung thụng tin hiu qu hn rt nhiu.
Theo khớa cnh ca thut toỏn hc mỏy thỡ Hypertext ó cung cp cho chỳng ta c
hi nhỡn ra ngoi phm vi mt ti liu phõn lp nú. Tt nhiờn khụng phi tt c cỏc
ti liu cú liờn kt n nú u cú ớch cho vic phõn lp, c bit l khi cỏc siờu liờn kt
cú th ch n rt nhiu loi khỏc nhau ca mi quan h gia cỏc ti liu. Tuy nhiờn
chc chn vn cũn tn ti cỏc tim nng m con ngi cn tip tc nghiờn cu v vic
s dng cỏc ti liu liờn kt n mt trang nõng cao chớnh xỏc phõn lp trang ú.
Ti liu Hypertext (Hypertext document): mt ti liu Text n nm trong mt
tp Hypertext. Nu chỳng ta tng tng tp Hypertext nh mt th thỡ mt ti liu
Text n l mt nỳt trong ú.
Siờu liờn kt (Hypertext link): l mt s tham kho/kt ni t mt ti liu
Hypertext ny n mt ti liu Hypertext khỏc. Cỏc siờu liờn kt úng vai trũ nh
nhng ng ni trong th núi trờn. Hỡnh 1.2 cho mt vớ d minh ho n gin v
ti liu Hypertext.












Hỡnh 1.2. th minh ho mi quan h gia cỏc ti liu
Hypertext trong mt tp ti liu Hypertext