PREDIKSI KUNJUNGAN HALAMAN WEB DENGAN N-GRAM MODEL WEB ACCESS PREDICTION USING N-GRAM MODEL

Prosiding Seminar Nasional Manajemen Teknologi XXII Program Studi MMT-ITS, Surabaya 24Januari 2015

PREDIKSI KUNJUNGAN HALAMAN WEB DENGAN N-GRAM MODEL WEB ACCESS PREDICTION USING N-GRAM MODEL Elok Sri Wahyuni,1)dan Yoyon K. Suprapto2) Jurusan Teknik Elektro, Institut Teknologi Sepuluh Nopember Surabaya 1)[email protected], 2)[email protected]

ABSTRAK Dalam penelitian ini akan dilakukan prediksi kunjungan halaman berikutnya website dengan menggunakan pengembangan konsep n-gram model atau yang dalam beberapa penulisan disebut dengan markov model. Meskipun model n-gram tradisional dianggap sangat sesuai untuk masalah prediksi dari sejumlah data berurut, namun ada beberapa masalah yang timbul. Model N-gram+ dan skema pruning digunakan untuk memperbaiki kinerja model n-gram dalam membuat prediksi. Hasil menunjukkan peningkatan akurasi sebesar 2% dan penurunan besar model mencapai 75% serta mampu mepertahankan tingkat cakupan model. Kata kunci: Web Mining, n-gram Model, Markov Model, Prediksi.

PENDAHULUAN Seiring perkembangan teknologi web, semakin banyak pula data yang tersedia bagi pengguna web dan jumlahnya terus bertambah. Namun demikian, ketersediaan data dalam jumlah besar pada web tidak menjamin bahwa seorang pengguna web dapat menemukan data yang dibutuhkannya dengan mudah. Salah satu cara untuk membantu pengguna untuk menemukan informasi yang mereka butuhkan adalah memprediksi permintaan pengguna dimasa masa depan dan menggunakan prediksi untuk berbagai sistem yang memberi penyajian informasi yang lebih selektif dan sesuai dengan pengguna seperti sistem rekomendasi, personalisasi web, caching dan presending dokumen. Beberapa penelitian dilakukan dengan berbagai metode untuk menghasilkan sistem prediksi dengan kinerja yang lebih baik. [Mar-tin Labsky, 2006] membandingkan penggunaan model berbasis aturan dan MarkovModel untuk melakukan prediksi pada website eccomerce. Peneliti lain [Ajeetku-mar S. Patel, 2014] menggunakan algritma genetik yang dipadukan dengan modelmarkov dalam membuat sistemprediksi yang didasarkan pada tingkah laku pengguna. [James Pitkow, 1999] mengusulkan model longest repeating subsequence (LRS) sebagai alternatif meningkatkan hasil kinerja Markov Model. Markov Model atau peneliti lain menyebutnya sebagai n-gram model [Zhong Su, 2000], telah digunakan untuk mempelajari dan memahami proses stokastik, dan terbukti cocok untuk pemodelan dan memprediksi perilaku pengguna berselancar pada situs web. Secara umum, masukan untuk masalah ini adalah urutan halaman web yang diakses oleh pengguna dan memodelkan perilaku ini, berdasarkan model yang dibuat bisa dilakukan prediksi halaman web yang paling mungkin akan diakses oleh pengguna. Dalam penelitian ini kami menggunakan pendekatan n-gram model yang biasa digunakan pada model linguistik untuk memprediksi kunjungan berikutnya halaman

ISBN: 978-602-70604-1-8 C-21-1


web dari pengguna website. kemudian akan diterapkan beberapa skema pruning untuk mengetahui skema yang paling sesuai dengan model yang dihasilkan yang bisa meningkatkan efektifitas model dalam membuat prediksi. METODE Sistem prediksi kunjungan halaman web dengan n-gram model ini dibangun dari log file web server. Adapun tahapan proses yang dilakukan untuk membuat prediksi kunjungan halaman berikutnya dengan n-gram model ini seperti ditunjukkan dalam Gambar1.

Gambar 1. Metode Penelitian A. Pra Proses Tahap pertama dalam pekerjaan ini adalah melakukan pra proses terhadap data yang diperoleh. Pembersihan data dimaksudkan untuk membersihkan log file dari data yang tidak diperlukan dalam proses prediksi kunjungan pengguna ke sebuah halaman web.Data yang tidak diperlukan antara lain, file image, script, atau hasil permintaan robot. Selain itu data yang pada field status-nya bernilai kurang dari 200 dan lebih dari 299 yang berikutnya harus dihilangkan. Identifikasi pengguna adalah proses mengidentifikasi setiap pengguna yang berbeda yang mengakses situs Web. Dalam proses identifikasi pengguna dilakukan aturan sebagai berikut: • Alamat IP yang berbeda merujuk ke pengguna yang berbeda. • IP yang sama dengan sistem operasi yang berbeda atau browser yang berbeda harus dipertimbangkan sebagai pengguna yang berbeda. • Sedangkan alamat IP, sistem operasi dan browser yang semua sama, pengguna barudapat ditentukan dari apakah halaman yang diminta dicapai dengan halaman yang diakses sebelumnya. Sesi adalah durasi waktu yang digunakan untuk mengakses halaman-halaman web. Sedangkan sebuah sesi pengguna didefinisikan sebagai urutan permintaan yang dilakukan oleh seorang pengguna selama beberapa periode waktu. [Liu Bing,2000] Tujuan identifikasi sesi ini adalah untuk membagi halaman yang diakses setiap pengguna ke setiap sesi.

ISBN: 978-602-70604-1-8 C-21-2


Berikut ini adalah aturan yang dgunakan untuk mengidentifikasi sesi pengguna: • Jika ada user baru, maka dibentuk sesi baru; • Dalam satu sesi pengguna, jika perujuk halaman (referer) bernilai null, maka dibentuk sesi baru; Dari proses ini akan didapatkan set sesi pengguna pada tabel sesi yang berisi informasi IP Address pengguna, waktu akses, dan urutan klik kunjungan (yang selanjutnya akan disebut dengan string). B. Pembuatan Model Dari tabel sesi pengguna akan dibangun n-gram model. Algoritma n-gram model didasarkan pada frekuensi kemunculan string. Setiap string dengan panjang n adalah sebuah n-gram. Setiap string yang ada pada tabel sesi pengguna dibaca sekali. sub string terakhir dari sebuah string dianggap sebagai kunjungan berikutnya. Kemudian dicatat frekuensi kemunculan untuk kunjungan berikutnya sampai semua sesi selesai dibaca. Klik berikutnya yang paling sering muncul digunakan sebagai prediksi untuk string tersebut. Sebagai contoh, misalkan dari set sesi didapatkan sesi pengguna sebagai berikut: A,B,C,D A,B,C,F A,B,C,F B,C,D,G B,C,D,G B,C,D,F Maka ketika dibangun 3-gram model akan didapatkan hasil sebagai berikut: A,B,C B,C,D Untuk string A,B,C prediksi yg dipakai adalah F karena frekuensi kejadian yang paling tinggi adalah F, sedangkan untuk string B,C,D frekuensi kejadian yang paling tinggi adalah G. Maka model 3-gram yang dihasilkan adalah sebagai berikut: Tabel 1. Model 3-gram String Prediksi A,B,C F C,D,E G Model 2-gram yang dihasilkan adalah sebagai berikut: Tabel 2. Model 2-gram String A,B B,C C,D

Prediksi C D G

ISBN: 978-602-70604-1-8 C-21-3


C. Prediksi Berdasarkan n-gram model yang dibangun dari log file akan dibuat prediksi kunjungan halaman berikutnya. Prediksi yang dilakukan didasarkan pada satu nilai n saja, bisa menggunakan model 1-gram, 2-gram atau 3-gram dan seterusnya. Dalam banyak aplikasi disebutkan, model 1-gram tidak menghasilkan prediksi kunjungan halaman berikutnya dengan hasil memuaskan. Sehingga untuk mengatasi hal tersebut digunakan model dengan berbagai tingkatan gram yang lebih tinggi. Namun, model n-gram tingkat tinggi ini memiliki beberapa keterbatasan yaitu kompleksitas besarnya string yang dihasilkan, cakupan yang tidak luas dan bahkan menurunnya tingkat akurasi. Jumlah string yang digunakan dalam model n-gram cenderung meningkat secara eksponensial sering dengan naiknya order n-gram. Karena model n-gram tingkat tinggi terbentuk dari kombinasi yang berbeda dari beberapa kunjungan halaman. Peningkatan jumlah string yang dramatis ini yang justru mempengaruhi cakupan penerapan model dalam membuat prediksi. Sedangkan model yang besar tentunya akan mempengaruhi kinerja beberapa aplikasi yang menerapkan sistem prediksi ini, dimana batasan memori sangat penting untuk kinerja aplikasi tersebut ( misalnya model n-gram yang digunakan untuk pengaturan sistem cache). [Despandhe, 2000] Namun, ada beberapa data set yang tidak memiliki jumlah string yang cukup banyak pada n-gram order tinggi yang mengakibatkan cakupan yang tidak luas karena sedikitnya jumlah model sehingga juga menurunkan tingkat akurasi prediksi yang dihasilkan. Salah satu metode sederhana untuk mengatasi masalah rendahnya kemampuan model n-gram tingkat tinggi dalam mengatasi keterbatasan cakupan adalah menggunakan berbagai order n-gram sekaligus untuk membuat prediksi. Dalam skema ini, untuk setiap data uji, model n-gram yang mencakup contoh data uji digunakan terlebih dahulu. Sebagai contoh misal dibangun model 3-gram, 2-gram dan 1-gram. Kemudian diberikan satu contoh data uji dengan panjang string 3, pertama kali dibuat prediksi dengan menggunakan model 3-gram. Jika model tidak memiliki string yang sesuai, maka dicoba membuat prediksi dengan menggunakan model 2-gram, dan seterusnya. Skema ini disebut dengan n-gram+.[zhongsu,2000] Untuk memperjelas algoritma n-gram+ bisa diilustrasikan dalam contoh berikut. Misalkan urutan halaman yang dikunjungi pengguna sekarang adalah ‘DBC’ sebagai P. Maka algoritma prediksi akan melihat tabel H3, apakah string ‘DBC’ ada atau tidak. Karena string ‘DBC’ tidak ditemukan, maka sub string pertama dari P dihilangkan menjadi ‘BC’. Selanjutnya algoritma akan mengecek tabel H2 untuk string ‘BC’. Berdasarkan tabel H2, maka prediksi untuk klik berikutnya untuk string ‘BC’ adalah ‘D’. D. Pruning Penggunaan berbagai model n-gram memiliki konsekuensi meningkatnya kompleksitas string model yang digunakan. Untuk itu diperlukan sebuah teknik untuk menghasilkan model dengan kompleksitas string yang rendah, tetapi bisa mempertahankan tingkat akurasi dan cakupan prediksinya. Skema yang diambil adalah menghapus string yang kemungkinan memiliki akurasi prediksi yang rendah. Dengan menghilangkan string-string tersebut akan mengurangi kompleksitas model. Stringstring yang lolos dari proses penghapusan (pruning) yang nantinya akan digunakan

ISBN: 978-602-70604-1-8 C-21-4


dalam proses prediksi. Ada beberapa teknik yang bisa digunakan dalam pemilihan string yang harus dihapus. Ada 2 skema yang digunakan dalam proses ini. Skema pertama hanya menghilangkan string yang memiliki nilai support yang rendah. Jumlah pemangkasan dalam skema support pruning ini dikendalikan oleh parameter φ yang disebut sebagai frekuensi threshold. String dengan nilai frekuensi kemunculan dibawah ambang frekuensi dihapus. Skema kedua menggunakan pendekatan penghapusan berbasis error untuk menghilangkan string dengan akurasi prediksi rendah.Dalam skema error pruning ini, diukur tingkat error masing-masing string untuk memutuskan perlu tidaknya string tersebut dihapus. Untuk memperkirakan error dari masing-masing string dilakukan proses validasi. Selama tahap validasi, seluruh model diuji dengan menggunakan bagian dari training set yang disebut set validasi. Set validasi ini tidak digunakan dalam proses pembentukan model. E. Evaluasi Untuk tujuan evaluasi kami membagi set sesi yang terbentuk menjadi dua bagian yaitu training set dan test set. Training set digunakan dalam pembentukan model. Dalam beberapa kasus, Model n-gram mungkin tidak dapat membuat prediksiuntuk sesi di tes set. Hal ini bisa terjadi karena ada dua kemungkinan, yaitu panjang sesi kurang dari panjang n-gram model, atau sesi tersebut tidak ditemukan dalam training set. Dalam kasus seperti ini, maka akan disebutkan model tidak membuat prediksi. Sehingga akan ada tiga nilai yang dikeluarkan dalam prediksi, yaitu prediksi salah, prediksi benar dan model tidak membuat prediksi. Secara umum ada tiga parameter yang digunakan untuk mengukur efektifitas dari model n-gram. 𝑃𝑃+

Akurasi : 𝑃𝑃+ +𝑃𝑃−

Jumlah string: Parameter ini digunakan mengukur kompleksitas model Cakupan model (Aplicability): mengukur berapa kali model mampu membuat prediksi. Aplicability =

𝑃𝑃+ +𝑃𝑃− |𝑅𝑅|

Dimana : P+ : prediksi yang betul P- : prediksi yang salah |R| : total data yang diobservasi HASIL DAN PEMBAHASAN Dari log file diambil selama 3 bulan diperoleh total data sebanyak 2.876.579 record, dengan perincian record bulan Januari sebanyak 1.009.805, record bulan Pebruari sebanyak 773.418 dan record bulan Maret sebanyak 1.093.356. Dari 18.420 sesi pada data training 5.974 string pada berbagai orde n-gram model.

ISBN: 978-602-70604-1-8 C-21-5


Gambar 2. Perbandingan Jumlah String Model n-gram dan Model n-gram+ Jika dilihat pada data tersebut, maka jumlah string pada model n-gram menurun seiring dengan semakin tingginya order model n-gram. Sedangkan pada model n-gram+ jumlah string meningkat tajam seiring dengan semakin tingginya orde n.

Gambar 3. Perbandingan Akurasi Model n-gram dan Model n-gram+ Semakin tinggi order n-gram hasil yang diperlihatkan untuk akurasinya semakin meningkat, sedangkan aplicability stabil tidak mengalami penurunan. akurasi terbaik dari ke empat model n-gram+ diatas diperoleh dari model 4-gram+ yaitu sebesar 61,62%. Namun konsekuensi yang diperoleh jumlah string meningkat seiring dengan naiknya order n-gram karena string yang digunakan pada prediksi n-gram order tinggi adalah gabungan dari string pada model tersebut ditambah dengan string pada order dibawahnya. Setelah dilakukan skema pruning diperoleh hasil seperti pada Gambar 4.

ISBN: 978-602-70604-1-8 C-21-6


Gambar 4. Perbandingan Kinerja Model n-gram+ Hasil menunjukkan data dengan urutan pendek meskipun jumlahnya sangat besar tetapi sarat dengan data noise. Sehingga skema pruning yang dilakukan sangat efektif untuk mengurasi besar model. Teknik support pruning yang menghapus string yang tidak diperlukan berdasarkan jumlah frekuensi kemunculannya menghasilkan hasil lebih baik, karena mampu mereduksi besar samapi 75% model tanpa terlalu banyak mengganggu kinerja mode, dibandingkan dengan kinerja error pruning yang mampu mengurangi besar model sebanyak 54%. Kedua skema sama-sama mampu mempertahankan nilai akurasi dan aplicability model meskipun ada pengurangan namun tidak terlalu signifikan jika dibandingkan dengan akurasi dan aplicability pada n-gram+. KESIMPULAN DAN SARAN Kesimpulan yang dapat diambil berdasarkan perhitungan dan analisis yang telah dilakukan sebelumnya adalah untuk website yang memiliki pola kunjungan berupa urutan yang pendek model n-gram menghasilkan akurasi mencapai 61%. Sedangkan penggunaan algoritma n-gram+ mampu menaikkan akurasi sebesar 2%. Skema error pruning menghasilkan kinerja lebih baik dengan mengurangi besar model hingga 75% tanpa terlalu banyak mempengaruhi akurasi dari prediksi dan cakupan model.

DAFTAR PUSTAKA Ajeetkumar S. Patel, A. P. K. (2014). Genetic algorithm and statistical markov model fusion for predicting users surfing behavior using sequence pattern mining. International Journal of Emerging Trends and Technology in Computer Science, 3. Deshpande, M. and Karypis, G. (2000). Selective Markov Models for Predicting WebPage Accesses. University of Minnesota,Army HPC Research Center Minneapolis. Ingrid Zukerman, D. W. A. (2001). Predictive statistical model for user modeling. School of Computer Science and Software Engineering, Monash University, Clayton, Victoria.

ISBN: 978-602-70604-1-8 C-21-7


James Pitkow, P. P. (1999). Mining longest repeating subsequence to predict world wide web surfing. Second USENIX Symposium on Internet Technologies and Systems, Boulder, C0. JOSEP DOMENECH, JULIO SAHUQUILLO, J. A. G. and PONT, A. (2012). A comparison of prediction algorithms for prefetching in the current web. Journal of Web Engineering, 11(1). Kurian, H. (2008). A MARKOV MODEL FOR WEB REQUEST PREDICTION. Dr. Babasaheb Ambedkar Technological University. Liu, B. (2006). Web DataMining: Exploring Hyperlinks, contents and Usage Data. Springer, New York, 1 edition. Martin Labsky, Vladimr Las, P. B. (2006). Mining Click-stream Data With Statistical and Rule-based Methods. Department of Information and KnowledgeEngineering, University of Economics, Prague, Praha, Czech Republic. Zhong Su, Qiang Yang, (2000). Whatnext: A prediction system forweb requests using n-gram sequence models. First International Conference onWeb Information Systems and Engineering Conference. 49

ISBN: 978-602-70604-1-8 C-21-8

PREDIKSI KUNJUNGAN HALAMAN WEB DENGAN N-GRAM MODEL WEB ACCESS PREDICTION USING N-GRAM MODEL

Recommend Documents