Measuring indeks Quality Measuring indeks Quality using Random Walks on the using Random Walks on the

WebWeb

Disediakan oleh:Disediakan oleh:Ang Pek Ling A97105Ang Pek Ling A97105Beh Jin Hong A97110Beh Jin Hong A97110Chung Yee Mun A97155Chung Yee Mun A97155Emilee Tan Su-Chin A97158Emilee Tan Su-Chin A97158Lau Woan Yun A97208Lau Woan Yun A97208

PengenalanPengenalan Saiz, kuantiti dan kualiti adalah suatu ukuran Saiz, kuantiti dan kualiti adalah suatu ukuran

yang penting bagi sesuatu enjin gelintar.yang penting bagi sesuatu enjin gelintar. Enjin gelintar yang mengindekskan laman yang Enjin gelintar yang mengindekskan laman yang

banyak perlu mencari metodologi yang sesuai banyak perlu mencari metodologi yang sesuai untuk menempatkan laman tersebut.untuk menempatkan laman tersebut.

Enjin gelintar yang mempunyai kualiti indeks Enjin gelintar yang mempunyai kualiti indeks yang tinggi akan memberi maklumat yang lebih yang tinggi akan memberi maklumat yang lebih relevan kepada pengguna akhir.relevan kepada pengguna akhir.

Enjin gelintar yang bersaiz kecil dengan kualiti Enjin gelintar yang bersaiz kecil dengan kualiti indeks yang tinggi akan memastikan keperluan indeks yang tinggi akan memastikan keperluan kueri pengguna dengan lengkap.kueri pengguna dengan lengkap.

Random WalksRandom Walks

Bersifat Markovian. Bersifat Markovian. Digunakan untuk menganggar kualiti Digunakan untuk menganggar kualiti

indeks di mana setiap laman di laman indeks di mana setiap laman di laman mewakili satu situasi.mewakili satu situasi.

Tidak ada natural stopping point (tanpa Tidak ada natural stopping point (tanpa henti).henti).

'PageRank' Measure'PageRank' Measure

Dikira berdasarkan nombor laman.Dikira berdasarkan nombor laman.Suatu 'PageRank' untuk satu laman Suatu 'PageRank' untuk satu laman

adalah tinggi jika ia boleh link ke banyak adalah tinggi jika ia boleh link ke banyak laman yang berpangkat tinggi.laman yang berpangkat tinggi.

Boleh digunakan sebagai panduan kepada Boleh digunakan sebagai panduan kepada crawler untuk mengindeks laman yang crawler untuk mengindeks laman yang lebih penting.lebih penting.

Menganggar Kualiti IndeksMenganggar Kualiti Indeks

(i)(i) Persampelan Laman Menurut Persampelan Laman Menurut kepada 'PageRank'nya.kepada 'PageRank'nya.

Pendekatan pertama :Pendekatan pertama :

cari bahagian Web yang penting.cari bahagian Web yang penting.

tentukan 'PageRank' untuk laman tentukan 'PageRank' untuk laman yang telah dicari dengan kaedah yang telah dicari dengan kaedah berulang.berulang.

Masalah :Masalah :

i) ukuran pemberat yang diperolehi i) ukuran pemberat yang diperolehi mungkin tidak benar-benar menjadi mungkin tidak benar-benar menjadi ukuran 'PageRank' .ukuran 'PageRank' .

ii) perlukan carian bahagian Web yang ii) perlukan carian bahagian Web yang besar, simpan maklumat link yang besar, simpan maklumat link yang berkaitan dan hitung nilai 'PageRank’ .berkaitan dan hitung nilai 'PageRank’ .

(ii) Pendekatan Persampelan(ii) Pendekatan Persampelan ‘‘Random walk’ dilaksanakan dengan Random walk’ dilaksanakan dengan

pengagihan keseimbangan yang sepadan pengagihan keseimbangan yang sepadan dengan ukuran ‘PageRank’.dengan ukuran ‘PageRank’.

‘‘Walk’ lompat ke satu laman yang rawak Walk’ lompat ke satu laman yang rawak dengan kebarangkalian d atau ikut satu dengan kebarangkalian d atau ikut satu link yang rawak dengan kebarangkalian 1-link yang rawak dengan kebarangkalian 1-d. d.

Dengan laksanakan ‘walk’ dalam suatu Dengan laksanakan ‘walk’ dalam suatu tempoh masa panjang yang sesuai,satu tempoh masa panjang yang sesuai,satu turutan sampel dijana.turutan sampel dijana.

Tidak perlu simpan bahagian graf Web Tidak perlu simpan bahagian graf Web yang besar.yang besar.

kekalkan landasan laman web semasa kekalkan landasan laman web semasa ‘walk’ dan turutan sampel.‘walk’ dan turutan sampel.

Masalah laksanakan ‘random walk’ secara Masalah laksanakan ‘random walk’ secara langsung :langsung :

i) tiada kaedah diperkenalkan untuk i) tiada kaedah diperkenalkan untuk memilih laman Web dengan seragam memilih laman Web dengan seragam secara rawak.secara rawak.

Penyelesaian :Penyelesaian : ‘ ‘walk’ pilih satu ‘host’ dengan seragam walk’ pilih satu ‘host’ dengan seragam

secara rawak daripada set ‘hosts’ pada secara rawak daripada set ‘hosts’ pada ‘walk’ begitu jauh.‘walk’ begitu jauh.

Simulasi : tingkatkan penyebaran, Simulasi : tingkatkan penyebaran, kurangkan ‘bias’ terhadap ‘hosts’ dengan kurangkan ‘bias’ terhadap ‘hosts’ dengan banyak laman yang saling bersambung.banyak laman yang saling bersambung.

Kekalkan landasan URL semua laman Kekalkan landasan URL semua laman yang dilayari.yang dilayari.

ii) tidak jelas berapa langkah dilaksanakan ii) tidak jelas berapa langkah dilaksanakan untuk mengalih ‘bias’ keadaan permulaanuntuk mengalih ‘bias’ keadaan permulaan

- anggar taburan keseimbangan. - anggar taburan keseimbangan. Tindakan ‘random walk’ pada suatu sub-Tindakan ‘random walk’ pada suatu sub-

graf Web yang kecil cukup menangani graf Web yang kecil cukup menangani ‘bias’ permulaan.‘bias’ permulaan.

Oleh sebab laman sampel dihimpun Oleh sebab laman sampel dihimpun berdasarkan ‘random walk’, carian kecil berdasarkan ‘random walk’, carian kecil yang berkaitan cukup untuk pendekatan yang berkaitan cukup untuk pendekatan ‘random walk’.‘random walk’.

Maka, andaian bahawa ‘bias’ adalah Maka, andaian bahawa ‘bias’ adalah kecil,carian kecil akan berkesankecil,carian kecil akan berkesan

Our Random WalksOur Random Walks ‘‘Random Walks’ menggunakan Mercator.Random Walks’ menggunakan Mercator.Apabila suatu ‘walk’ lompat secara rawak Apabila suatu ‘walk’ lompat secara rawak

ke satu laman yang rawak tanpa mengikut ke satu laman yang rawak tanpa mengikut suatu link, ia memilih satu ‘host’ secara suatu link, ia memilih satu ‘host’ secara seragam.seragam.

Kemudian, ia memilih satu laman dalam Kemudian, ia memilih satu laman dalam ‘host’ secara seragam di semua laman ‘host’ secara seragam di semua laman dalam ‘host’ tersebut dimana semua ‘host’ dalam ‘host’ tersebut dimana semua ‘host’ dipilih secara rawak. dipilih secara rawak.

Ini adalah pseudo-code bagi ‘random walk’ Ini adalah pseudo-code bagi ‘random walk’ algorithmalgorithm

The following variables are shared by all threads: The following variables are shared by all threads: HostSetHostSet, the set of host names discovered so far , the set of host names discovered so far UrlSet(h)UrlSet(h), the set of URLs discovered so far that belong to host , the set of URLs discovered so far that belong to host hh SamplesSamples, a list of URLs representing a sample sequence , a list of URLs representing a sample sequence Their initial values are: Their initial values are: HostSetHostSet = { www.yahoo.com } = { www.yahoo.com } UrlSetUrlSet(www.yahoo.com) = { www.yahoo.com/ } (www.yahoo.com) = { www.yahoo.com/ } UrlSet(h)UrlSet(h) = {} for all other hosts = {} for all other hosts hh SamplesSamples = [ ] = [ ] All threads execute the following algorithm in parallel: All threads execute the following algorithm in parallel: RandomResetRandomReset::

   Choose a host    Choose a host hh uniformly at random from uniformly at random from HostSetHostSet..   Choose a URL    Choose a URL uu uniformly at random from uniformly at random from UrlSet(h)UrlSet(h)..   Download laman    Download laman pp referred to by referred to by uu..StepStep::   If    If pp contains at least one link: contains at least one link:     Let      Let hh be the host component of be the host component of uu..     If      If hh is not in is not in HostSetHostSet, add it., add it.     If      If uu is not in is not in UrlSet(h)UrlSet(h), add it., add it.   With probability    With probability cc, add , add uu to to SamplesSamples..   With probability    With probability dd, go to RandomReset., go to RandomReset.   Let    Let UU be the set of derelativized URLs contained in be the set of derelativized URLs contained in pp..   While    While UU is non-empty: is non-empty:     Choose and remove a URL      Choose and remove a URL uu uniformly at random from uniformly at random from UU..     Attempt to download laman      Attempt to download laman pp referred to by referred to by uu, following, following      HTTP redirects as necessary.      HTTP redirects as necessary.     If      If pp could be downloaded and is an HTML document, go to Step. could be downloaded and is an HTML document, go to Step.   Go to RandomReset.    Go to RandomReset.

Figure 1:Figure 1: Pseudo-code for the random walk algorithm. Pseudo-code for the random walk algorithm.

‘‘Random walk’ boleh melayari banyak Random walk’ boleh melayari banyak laman pada suatu masa.laman pada suatu masa.

Ini bermakna laman yang ber’PageRank’ Ini bermakna laman yang ber’PageRank’ tinggi akan sentiasa dilayari oleh tinggi akan sentiasa dilayari oleh pengguna.pengguna.

Pengujian data dan analisisPengujian data dan analisis

Dalam melaksanakan ujian terhadap data Dalam melaksanakan ujian terhadap data dan analisi, keputusan yang didapati dan analisi, keputusan yang didapati adalah berdasarkan ‘random walk’.adalah berdasarkan ‘random walk’.

Keputusan dibahagi kepada dua iaitu:Keputusan dibahagi kepada dua iaitu:

i) dapat menentusahkan ‘random walk’ i) dapat menentusahkan ‘random walk’ yang bersifat kualiti.yang bersifat kualiti.

ii) membandingkan ukuran kualiti indeks ii) membandingkan ukuran kualiti indeks enjin gelintar berdasarkan kepada enjin gelintar berdasarkan kepada persampelan daripada ‘random walks’.persampelan daripada ‘random walks’.

KeberkesananKeberkesanan ‘Random Walk’ ‘Random Walk’

Table 1:Table 1: Most frequently hit lamans on the random walks. Most frequently hit lamans on the random walks.

laman W2 Freq. W1 Freq. (Rank)

www.microsoft.com/ 3172 1600 ( 1)

www.microsoft.com/windows/ie/default.htm 2064 1045 ( 3)

www.netscape.com/ 1991 876 ( 6)

www.microsoft.com/ie/ 1982 1017 ( 4)

www.microsoft.com/windows/ie/download/ 1915 943 ( 5)

www.microsoft.com/windows/ie/download/all.htm 1696 830 ( 7)

www.adobe.com/prodindeks/acrobat/readstep.html 1634 780 ( 8)

home.netscape.com/ 1581 695 (10)

www.linkexchange.com/ 1574 763 ( 9)

www.yahoo.com/ 1527 1132 ( 2)

home.netscape.com/comprod/mirror/indeks.html 1015 479 (13)

www.lycos.com/ 982 597 (11)

search.microsoft.com/default.asp 895 452 (15)

www.microsoft.com/search/default.asp 749 392 (17)

www.microsoft.com/Support/ 721 388 (18)

www.adobe.com/homelaman.shtml 690 361 (19)

www.excite.com/ 678 436 (16)

www.infoseek.com/ 676 320 (22)

www.microsoft.com/misc/cpyright.htm 673 355 (20)

www.microsoft.com/products/default.asp 663 343 (21)

Table 2:Table 2: Most frequently hit hosts on the random walks. Most frequently hit hosts on the random walks.

Site W2 Freq. W1 Freq. (Rank)

www.microsoft.com 32452 16917 ( 1)

home.netscape.com 23329 11084 ( 2)

www.adobe.com 10884 5539 ( 3)

www.amazon.com 10146 5182 ( 4)

www.netscape.com 4862 2307 (10)

excite.netscape.com 4714 2372 ( 9)

www.real.com 4494 2777 ( 5)

www.lycos.com 4448 2645 ( 6)

www.zdnet.com 4038 2562 ( 8)

www.linkexchange.com 3738 1940 (12)

www.yahoo.com 3461 2595 ( 7)

www.sun.com 2613 1309 (16)

www.hitbox.com 2570 1115 (19)

www.excite.com 2504 1644 (14)

members.aol.com 2450 1159 (18)

www.ibm.com 2418 1807 (13)

www.macromedia.com 2043 971 (23)

www.infoseek.com 2001 1005 (22)

www.compaq.com 1983 1079 (20)

www.digital.com 1927 1034 (21)

Table 1 dan 2 menunjukkan kekerapan Table 1 dan 2 menunjukkan kekerapan yang paling tinggi ‘lamans’ dan ‘hosts’ yang paling tinggi ‘lamans’ dan ‘hosts’ yang dilayari.yang dilayari.

WW22 – frekuensi bagi ‘second longer walk’. – frekuensi bagi ‘second longer walk’. WW11 – frekuensi bagi ‘first walk’. – frekuensi bagi ‘first walk’. ‘‘Random walk’ berhubung dengan Random walk’ berhubung dengan

‘lamans’ dan ‘hosts’ yang mempunyai ‘lamans’ dan ‘hosts’ yang mempunyai hubungan yang tinggi dalam web.hubungan yang tinggi dalam web.

‘‘Random walk’ lebih menitikberatkan Random walk’ lebih menitikberatkan dalam ‘lamans’ dan ‘hosts’ dimana dalam ‘lamans’ dan ‘hosts’ dimana mempunyai hubungan rangkaian yang mempunyai hubungan rangkaian yang lebih kerap.lebih kerap.

Membandingkan indeks Enjin Membandingkan indeks Enjin GelintarGelintar

Kita menggunakan kueri yang kuat untuk Kita menggunakan kueri yang kuat untuk menentukan sama ada enjin tersebut menentukan sama ada enjin tersebut mempunyai ‘laman’ yang diberi.mempunyai ‘laman’ yang diberi.

Untuk memadankan URL dengan hasil Untuk memadankan URL dengan hasil daripada enjin gelintar, kita gunakan 3 daripada enjin gelintar, kita gunakan 3 ‘matching’ kriteria :‘matching’ kriteria :

i) Exact : satu ‘match’ adalah betul jika i) Exact : satu ‘match’ adalah betul jika enjin gelintar memulangkan URL dalam enjin gelintar memulangkan URL dalam keadaan yang normal dan sepadan keadaan yang normal dan sepadan dengan sasaran URL. dengan sasaran URL.

ii) Host : ‘host match’ akan terjadi jika ii) Host : ‘host match’ akan terjadi jika ‘laman’ dengan ‘host’ yang sama apabila ‘laman’ dengan ‘host’ yang sama apabila sasaran URL pulang.sasaran URL pulang.

iii) Non-zero : ‘non-zero’ match terjadi jika iii) Non-zero : ‘non-zero’ match terjadi jika enjin gelintar memulangkan mana-mana enjin gelintar memulangkan mana-mana ‘laman’ sebagai hasil kueri yang kuat.‘laman’ sebagai hasil kueri yang kuat.

Terdapat perbezaan di antara 3 ‘matching’ kriteria.Terdapat perbezaan di antara 3 ‘matching’ kriteria. ‘‘Non-zero match’ akan membatasi taksiran yang Non-zero match’ akan membatasi taksiran yang

kita anggarkan berbanding dengan ‘host match’ kita anggarkan berbanding dengan ‘host match’ dan ‘exact match’ lebihdan ‘exact match’ lebih tepat.tepat.

Search Exact Host Non-zero Est. Size

Engine W1 W2 W1 W2 W1 W2 (mill. lamans)

AltaVista 0.2680 0.2709 0.3429 0.3409 0.5182 0.5164 125

HotBot 0.1517 0.1582 0.2128 0.2082 0.3764 0.3691 100

Excite 0.1675 0.1836 0.2227 0.2355 0.3892 0.3645 45

Infoseek 0.1025 0.1191 0.1399 0.1391 0.2374 0.2245 37

Google 0.0778 0.0764 0.1005 0.1036 0.2315 0.2191 25

Lycos 0.1281 0.1264 0.1606 0.1691 0.3005 0.2891 21

Figure 2: the quality scores for various search engine indekses,scaled,in Figure 2: the quality scores for various search engine indekses,scaled,in the case of exact matchesthe case of exact matches

Figure 3 : the average laman quality for various search engine Figure 3 : the average laman quality for various search engine indekses,scaled,in the case of exact matchesindekses,scaled,in the case of exact matches

kesimpulankesimpulan

Kualiti indeks enjin gelintar.Kualiti indeks enjin gelintar.Kaedah pengukuran berdasarkan Kaedah pengukuran berdasarkan

‘PageRank’.‘PageRank’.Kaedah untuk menganggarkan indeks Kaedah untuk menganggarkan indeks

enjin gelintar dengan menggunakan enjin gelintar dengan menggunakan ‘random walk’.‘random walk’.

‘‘Random walk’ bersifat kualiti.Random walk’ bersifat kualiti.