aplikasi matematik dalam engin google
TRANSCRIPT
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
8/10/2019 Aplikasi Matematik Dalam Engin Google
http://slidepdf.com/reader/full/aplikasi-matematik-dalam-engin-google 2/11
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.
8/10/2019 Aplikasi Matematik Dalam Engin Google
http://slidepdf.com/reader/full/aplikasi-matematik-dalam-engin-google 3/11
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.
8/10/2019 Aplikasi Matematik Dalam Engin Google
http://slidepdf.com/reader/full/aplikasi-matematik-dalam-engin-google 4/11
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 =
=
8/10/2019 Aplikasi Matematik Dalam Engin Google
http://slidepdf.com/reader/full/aplikasi-matematik-dalam-engin-google 5/11
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.
8/10/2019 Aplikasi Matematik Dalam Engin Google
http://slidepdf.com/reader/full/aplikasi-matematik-dalam-engin-google 6/11
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.
8/10/2019 Aplikasi Matematik Dalam Engin Google
http://slidepdf.com/reader/full/aplikasi-matematik-dalam-engin-google 7/11
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
Teka bahawa PR (B) = 0,
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
Teka bahawa PR (B) = 40,
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
8/10/2019 Aplikasi Matematik Dalam Engin Google
http://slidepdf.com/reader/full/aplikasi-matematik-dalam-engin-google 8/11
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
8/10/2019 Aplikasi Matematik Dalam Engin Google
http://slidepdf.com/reader/full/aplikasi-matematik-dalam-engin-google 9/11
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.
8/10/2019 Aplikasi Matematik Dalam Engin Google
http://slidepdf.com/reader/full/aplikasi-matematik-dalam-engin-google 10/11
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
8/10/2019 Aplikasi Matematik Dalam Engin Google
http://slidepdf.com/reader/full/aplikasi-matematik-dalam-engin-google 11/11
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