aplikasi matematik dalam engin google

8/10/2019 Aplikasi Matematik Dalam Engin Google

http://slidepdf.com/reader/full/aplikasi-matematik-dalam-engin-google 1/11

1.2 KOK KAR MUN

APLIKASI MATEMATIK DALAM ENJIN PENCARIAN GOOGLE

Pengenalan

Rajah 1. Enjin pencarian internet Google.

Misi Google adalah untuk menyusun maklumat dunia dan menjadikannya boleh

diakses dan berguna di serata dunia. Sejak Google ditubuhkan pada 1998, ia telah

menjadi enjin pencarian internet yang paling popular di dunia.

Rajah 2 . Enjin pencarian internet yang paling popular.

Satu perkara yang membezakan Google dengan enjin pencarian internet yang

lain adalah Google sentiasa membekalkan halaman web yang lebih berkualiti dan

relevan kepada pengguna berbanding dengan enjin pencarian internet yang lain. Ini

disebabkan oleh penggunaan formula dan pengiraan PageRank (PR) yang menentukan



kedudukan sesebuah halaman web berdasarkan kepentingan dan kerelevan halaman

web tersebut dan seterusnya membenarkan Google mempersembahkan halaman web

yang paling penting kepada pengguna. Daripada julat 0 hingga 10, halaman web yang

mempunyai autoriti yang tinggi dan relevan akan mempunyai PageRank yang tinggi.

Sebagai contoh, Facebook dan youtube mempunyai RP9 dan Twitter mempunyai PR10.

Banyak pengiraan dan aplikasi Matematik telah digunakan dalam proses pengiraan

PageRank. Secara ringkasnya, proses enjin carian Google ini telah menggunakan

prinsip matriks dan algoritma.

Penggunaan Matriks

Dalam idea pengiraan PageRank, kepentingan sesebuah halaman web

bergantung kepada bilangan halaman web yang link kepadanya. Katakan halaman web i

direkakan dan ia mengandungi hyperlink kepada halaman web j . Ini bermaksud halaman

web j dianggap penting dan relevan oleh pereka halaman web i .

Untuk bermula menentukan PageRank, halaman web akan diwakili dalam rajah

yang mengandungi nod dan anak panah di mana nod mewakili halaman web dan anak

panah mewakili link antara halaman web.

Katakan, kita mempunyai 4 laman web iaitu www.page1.com, www.page2.com,

www.page3.com dan www.page4.com seperti yang ditunjukkan dalam rajah 3.

Rajah 3. Contoh empat halaman web.



Untuk langkah pertama, hubungan keempat-empat halaman web diwakili dalam

rajah dengan menggunakan 4 nod dan anak panah. Dalam Rajah 3, adalah jelas

menunjukkan bahawa page 1 mempunyai hyperlink kepada page 2 , page 3 dan page 4.

Jadi, nod 1 mempunyai 3 anak panah yang mengarah kepada nod 3, nod 4 dan nod 5

masing-masing. Untuk page 3 pula, ia hanya mempunyai 1 hyperlink kepada page 1,

jadi nod 3 mempunyai anak panah yang mengarah kepada nod 1. Selepas menganalisis

keempat-empat halaman web, kita dapat rajah 4 yang menunjukkan hubungan antara

keempat-empat halaman web.

Rajah 4. Hubungan page 1, page 2 , page 3 dan page 4.

Dalam model ini, sesebuah halaman web akan memberikan kepentingannya

secara rata kepada halaman web yang ia „link to‟. Nod 1 mempunyai 3 anak panah

mengarah luar, jadi ia membahagikan kepentingannya kepada 3 bahagi dan memberi

setiap laman web daripada kepentingannya. Manakala nod 3 hanya mempunyai 1

anak panah yang mengarah luar, jadi ia memberikan semua kepentingannya iaitu 1

kepada nod 1 seperti yang ditunjukkan dalam Rajah 5. Secara umumnya, jika sesebuah

nod mempunyai k anak panah mengarah luar, ia akan memberi daripada kepentingan

kepada setiap nod yang berhubung.

Rajah 5. Hubungan keempat-empat halaman web.



Seterusnya, hubungan keempat-empat halaman web dan kepentingan yang

diterima telah diwakili dalam bentuk matriks seperti yang berikut:

A =

Untuk mengetahui halaman yang paling penting dan akan muncul pada

kedudukan pertama, Page Rank Vector (V ) akan dikira dengan menggunakan matriks.

Kepentingan sepatutnya diagihkan secara rata antara 4 nod, di mana setiap nod

mendapat

atau 0.25. Jadi, rank vector awal (initial rank vector ) diwakili dengan v

seperti yang berikut:

v = Setiap link masuk meningkatkan kepentingan halaman web, jadi kedudukan

(rank) bagi setiap halaman akan dikemaskini dengan mendarab matriks A dengan v

seperti berikut:

Av =

=



Pengiraan diulangkan dan diteruskan dengan , , ,… sehingga

Page Rank Vector mencapai nilai yang sama dan seimbang (equilibrium value).

Keputusan pengiraan adalah seperti berikut:

= , = , = , = ,

= , = , =

Adalah didapati bahawa nilai keseimbangan (equilibrium value) = dan ini juga merupakan Page Rank Vector (V ) bagi keempat-empat halaman web. V

bagi page 1 adalah paling tinggi, iaitu 0.38 dan ini telah menunjukkan bahawa page 1

merupakan halaman yang paling relevan. Manakala Page 3 tidak begitu relevan

berbanding dengan Page 1 walaupun ia mempunyai 3 link yang mengarah kepadanya,

tetapi Page 1 hanya mempunyai 2 link yang mengarah kepadanya. Ini adalah

disebabkan oleh Page 3 hanya mempunyai satu hyperlink , iaitu Page 1. Keadaan ini

bermaksud Page 3 memberikan kesemua kepentingannya kepada Page 1 dan

pengguna yang melayai Page 3 hanya dapat melayai Page 1 jika mengikut hyperlink

yang terkandung dalam Page 3.

Kesimpulannya, kepentingan dan kedudukan sesuatu halaman web dapat

ditentukan dengan pengiraan Page Rank Vector (V ) dengan menggunakan matriks.



Penggunaan algoritma

PageRank adalah algoritma analisis link yang menyerahkan wajaran berangka

untuk setiap halaman web dengan tujuan untuk “mengukur ” kepentingan relative. Satu

algoritma PageRank telah dikemukakan oleh pengasas Google, Larry Page dan Sergey

Brin bagi mengira PageRank antara beberapa halaman web. Algoritma PageRank

adalah seperti berikut:

Algoritma awal

PR(A) = (1-d) + d ( ( PR(T1) / C(T1) ) + … + ( PR(Tn) / C(Tn) ) )

Algoritma lain yang diperkenalkan

PR(A) = (1-d) / N + d ( ( PR(T1) / C(T1) ) + … + ( PR(Tn) / C(Tn) ) )

di mana

PR(A) adalah PageRank halaman A

PR(T1) adalah PageRank halaman T1 yang mengarah ke halaman A

C(T1) adalah jumlah link keluar (outgoing link ) pada halaman T1

d adalah damping factor yang diberi antara 0 dan 1, biasanya ialah 0.85.

N adalah jumlah keseluruhan halaman web (yang didapati oleh Google)

Dalam algoritma yang diperkenalkan, kita tidak tahu PR(T1) tersebut, jadi apa

yang kita lakukan adalah membuat tekaan. Proses pengiraan akan berulang sehingga

mengemui hasil yang tepat.

Prinsip:

Ia tidak kira di mana pengira bermula tekaan, apabila pengiraan PageRank telah

ditetapkan, “taburan kebarangkalian normal” (PageRank purata untuk semua muka surat)akan menjadi 1.0.



Contoh 1 :

Kedua-dua halaman web mempunyai 1 link keluar, jadi C(A) = 1 dan C(B) = 1.

Diberi d = 0.85

Jadi, rumus yang didapat ialah :

PR(A) = (1 – d) + d(PR(B)/1)

PR(B) = (1 – d) + d(PR(A)/1)

Tekaan pertama

Teka bahawa PR (B) = 1,

PR(A) = 0.15 + 0.85 (1) = 1

PR(B) = 0.15 + 0.85 (1) = 1

Tekaan kedua


1) PR(A) = 0.15 + 0.85 (0) = 0.15

PR(B) = 0.15 + 0.85 (0.15) = 0.2775

2) PR(A) = 0.15 + 0.85 (0.2775) = 0.385875

PR(B) = 0.15 + 0.85 (0.385875) = 0.47799375

3) PR(A) = 0.15 + 0.85 (0.47799375) = 0.5562946875

PR(B) = 0.15 + 0.85 (0.5562946875) = 0.622850484375 ……

Adalah didapati bahawa nilai semakin meningkat dan berkemungkinan besar ia tidak

akan capai 1.0. Jadi tekaan ketiga diteruskan.

Tekaan ketiga


1) PR(A) = 0.15 + 0.85 (40) = 34.15

PR(B) = 0.15 + 0.85 (34.15) = 29.1775

Halaman web A Halaman web B



2) PR(A) = 0.15 + 0.85 (29.1775) = 24.950875

PR(B) = 0.15 + 0.85 (24.950875) = 21.35824375 ……

Adalah didapati bahawa nilai adalah semakin menurun, jadi ia boleh diteruskan supaya

mencapai 1.0 dan berhenti seperti yang dinyatakan dalam prinsip.

Contoh 2:

Diberi d = 0.5

Jadi, rumus yang didapat ialah:

PR(A) = 0.5 + 0.5 PR(C)

PR(B) = 0.5 + 0.5 (PR(A) / 2)

PR(C) = 0.5 + 0.5 (PR(A) / 2 + PR(B))

Teka bahawa PR (A) = 1,

1) PR(B) = 0.5 + 0.5 (0.5) = 0.75

PR(C) = 0.5 + 0.5 (0.5 + 0.75) = 1.125

2) PR (A) = 0.5 + 0.5 (1.125) = 1.0625

PR(B) = 0.5 + 0.5 (1.0625 / 2) = 0.765625

PR(C) = 0.5 + 0.5 (1.0625 / 2 + 0.765625) = 1.1484375

3) PR(A) = 0.5 + 0.5 (1.1484375) = 1.07421875

PR(B) = 0.5 + 0.5 (1.07421875/ 2) = 0.76855469PR(C) = 0.5 + 0.5 (1.07421875 / 2 + 0.76855469) = 1.15283203 ……

Pengiraan akan diteruskan sehingga nilai yang didapati tidak berubah terlalu banyak.

Jadual 1 menunjukkan keputusan pengiraan.

Halaman web A

Halaman web B Halaman web C



Jadual 1

Keputusan Pengiraan PR Bagi Halaman Web A, B dan C

Bilangan

pengiraanberulang

PR (A) PR (B) PR (C)

1 1 0.75 1.125

2 1.0625 0.765625 1.1484375

3 1.07421875 0.76855469 1.15283203

4 1.07641602 0.76910400 1.15365601

5 1.07682800 0.76920700 1.15381050

6 1.07690525 0.76922631 1.15383947

7 1.07691973 0.76922993 1.15384490

8 1.07692245 0.76923061 1.15384592

9 1.07692296 0.76923074 1.1538461110 1.07692305 0.76923076 1.15384615

11 1.07692307 0.76923077 1.15384615

12 1.07692308 0.76923077 1.15384615

Hasil daripada pengiraan algoritma, adalah didapati bahawa PR (A) = 1.0769,

PR(B) = 0.7692, dan PR(C) = 1.1538. Ini bermaksud halaman web C mempunyai

kepentingan dan kerelevanan yang paling tinggi berbanding dengan halaman web A dan

B.

Kesimpulannya, aplikasi Matematik telah digunakan dan memainkan peranan

yang penting dalam enjin pencarian Internet seperti Google untuk berfungsi secara

berkesan dan membawa manfaat kepada orang ramai untuk mendapatkan maklumat

yang relevan.



Rujukan

Amy, L. (n.d.). The Linear Algebra Behind Search Engines-Introduction. Journal of

Online Mathematics and its Applications. Retrieved from

http://www.maa.org/publications/periodicals/loci/joma/the-linear-algebra-behind-

search-engines-introduction

Cleve, M. (2011). Google PageRank. Retrieved from http://www.mathworks.com/moler/

exm/chapters/pagerank.pdf

eBizMBA. (2014). Top 15 Most Popular Search Engines. Retrieved from

http://www.ebizmba.com/articles/search-engines

eFactory GmBH & Co. KG. (2003 ). The PageRank Algoritma. Retrived from

http://pr.efactory.de/e-pagerank-algorithm.shtml

Farahat, A., LoFaro, T., Miller, J., Rae, G., Ward, L, (2006). "Authority Rankings from

HITS, PageRank, and SALSA: Existence, Uniqueness, and Effect of

Initialization". SIAM Journal on Scientific Computing, 27 (4), 1181 –1201.

Google Webmasters. (Producer). (2010). How do PageRank updates work? [Youtube ].

London: Google Webmasters

Ian, R. (2002). The Google Pagerank Algoritma and How It Works. Retrieved from

http://www.sirgroane.net/google-page-rank/

Kementerian Pendidikan Malaysia. (2013). Asas Matematik Kontemporari. In

Muhammad Shamsul Naim Mohd Sukri (Ed.), Modul MTE 3114 Aplikasi

Matematik (pp.10 - 12). Retrived from http://www.researchgate.net/profile/

Muhammad_Shamsul_Naim_Mohd_Sukri/publication/258555374_Modul_MTE31

14_ver.1/links/02e7e528a43ae54761000000?origin=publication_detail

Kurt, B., & Tanya, L. (n.d.). The Linear Algebra Behind Google. Retrieved from

http://www.rose-hulman.edu/~bryan/googleFinalVersionFixed.pdf

Society for Industrial and Applied Mathematics. (2011). Google PageRank: The

Mathematics of Google. Retrieved from http://www.whydomath.org/node/google/

math.html



Tim, C., & Anne, G. (2008). Ranking Web Pages. Retrieved from

http://www.math.washington.edu/~greenbau/Math_498/lecture03_pagerank.pdf

Wikipedia, the free encyclopedia. (2014). PageRank . Retrieved from

http://en.wikipedia.org/wiki/PageRank

Wikipedia, the free encyclopedia. (2014). Google matrix . Retrieved from

http://en.wikipedia.org/wiki/Google_matrix

aplikasi matematik dalam engin google

Documents