5.2.1 Pencarian frequent item ................................................................... 62 5.2.2 FP-Tree ............................................................................................ 63 5.2.3 Conditional FP-Tree ........................................................................ 68 5.2.4 Ekstraksi itemset .............................................................................. 71 5.3 Implementasi Cosine Similarity .............................................................. 72 5.4 Implementasi Penentuan Rekomendasi .................................................. 73 BAB VI HASIL DAN PEMBAHASAN .............................................................. 77 6.1 Data Pengujian ........................................................................................ 77 6.1.1 Dokumen pengujian ......................................................................... 77 6.1.2 Data transaksi ................................................................................... 77 6.1.3 Stopword .......................................................................................... 79 6.2 Metode Pengumpulan Data ..................................................................... 79 6.3 Skenario Pengujian ................................................................................. 79 6.4 Hasil Pengujian ....................................................................................... 79 6.4.1 Precision .......................................................................................... 80 6.4.2 Recall ............................................................................................... 84 6.4.3 F-Measure ........................................................................................ 87 6.4.4 Mean average precision................................................................... 90 BAB VII KESIMPULAN DAN SARAN ............................................................. 94 7.1 Kesimpulan ............................................................................................. 94 7.2 Saran ....................................................................................................... 95 DAFTAR PUSTAKA ........................................................................................... 96 LAMPIRAN 1 ..................................................................................................... 101 LAMPIRAN 2 ..................................................................................................... 106 LAMPIRAN 3 ..................................................................................................... 117 LAMPIRAN 4 ..................................................................................................... 126 LAMPIRAN 5 ..................................................................................................... 130
ix
DAFTAR TABEL Tabel 2.1 Tinjauan pustaka ................................................................................... 16 Tabel 3.1 Data transaksi ........................................................................................ 20 Tabel 3.2 Representasi keranjang ......................................................................... 20 Tabel 3.3 Frequent itemset .................................................................................... 20 Tabel 3.4 Daftar partikel ....................................................................................... 27 Tabel 3.5 Daftar kata ganti kepunyaan ................................................................. 27 Tabel 3.6 Daftar awalan pertama .......................................................................... 28 Tabel 3.7 Kombinasi ilegal ................................................................................... 28 Tabel 3.8 Daftar akhiran ....................................................................................... 29 Tabel 3.9 Daftar awalan kedua.............................................................................. 29 Tabel 3.10 Awalan ganda ...................................................................................... 29 Tabel 3.11 Pembagian kondisi hasil yang memungkinkan ................................... 32 Tabel 4.1 Contoh data transaksi ............................................................................ 44 Tabel 4.2 Seleksi data transaksi ............................................................................ 45 Tabel 4.3 Jumlah kemunculan item....................................................................... 45 Tabel 4.4 Urutan frequent item ............................................................................. 47 Tabel 4.5 Data transaksi terurut dan terseleksi ..................................................... 48 Tabel 4.6 Hasil frequent itemset............................................................................ 49 Tabel 4.7 Rancangan tabel administrator ............................................................. 53 Tabel 4.8 Rancangan tabek transaksi .................................................................... 53 Tabel 4.9 Rancangan tabel dokumen .................................................................... 54 Tabel 4.10 Rancangan tabel ambang batas ........................................................... 54 Tabel 4.11 Rancangan tabel stoplist...................................................................... 55 Tabel 4.12 Rancangan tabel dokumen term .......................................................... 55 Tabel 5.1 Penyimpanan jumlah item pada array .................................................. 63 Tabel 5.2 Urutan frequent itemset ......................................................................... 75 Tabel 6.1 Dokumen uji .......................................................................................... 78 Tabel 6.2 Jumlah data transaksi masing-masing dokumen uji.............................. 78 Tabel 6.3 Komposisi perhitungan item ID 91 ....................................................... 80
x
Tabel 6.4 Precision minimum similarity 40% dengan minimum support 20% ..... 81 Tabel 6.5 Nilai precision jumlah rekomendasi maksimal..................................... 81 Tabel 6.6 Nilai precision jumlah rekomendasi terbatas ........................................ 83 Tabel 6.7 Recall minimum similarity 40% dengan minimum support 20% .......... 84 Tabel 6.8 Nilai recall jumlah rekomendasi maksimal .......................................... 85 Tabel 6.9 Nilai recall jumlah rekomendasi terbatas ............................................. 86 Tabel 6.10 F-measure minimum similarity 40% dengan minimum support 20% . 88 Tabel 6.11 Nilai F-measure jumlah rekomendasi maksimal ................................. 88 Tabel 6.12 Nilai F-measure jumlah rekomendasi terbatas .................................... 89 Tabel 6.13 AP ID 9 minimum similarity 40% dengan minimum support 20% ..... 91 Tabel 6.14 MAP minimum similarity 40% dengan minimum support 20% ......... 92 Tabel 6.15 Nilai mean average precision ............................................................. 92
xi
DAFTAR GAMBAR Gambar 3.1 Penentuan frequent item .................................................................... 21 Gambar 3.2 FP-Tree .............................................................................................. 22 Gambar 3.3 Pembentukan conditional FP-Tree item „e‟ ...................................... 22 Gambar 3.4 Conditional FP-Tree item „e‟ ............................................................ 23 Gambar 3.5 Pembentukan conditional FP-Tree item „b e‟ ................................... 23 Gambar 3.6 Urutan hasil penggalian frequent itemset .......................................... 24 Gambar 3.7 Skema Tala stemmer ......................................................................... 26 Gambar 4.1 Gambaran umum hybrid recommendation system ............................ 35 Gambar 4.2 Arsitektur hybrid recommendation system ........................................ 38 Gambar 4.3 Flowchart tokenisasi ......................................................................... 39 Gambar 4.4 Flowchart stopword removal ............................................................ 41 Gambar 4.5 Flowchart Tala stemmer.................................................................... 42 Gambar 4.6 Flowchart pembobotan ..................................................................... 43 Gambar 4.7 Flowchart pencarian frequent item ................................................... 46 Gambar 4.8 Flowchart pembentukan FP-Tree...................................................... 48 Gambar 4.9 FP-Tree dan Prefix Path .................................................................... 49 Gambar 4.10 Flowchart penggalian frequent itemset ........................................... 50 Gambar 4.11 Flowchart cosine similarity............................................................. 51 Gambar 4.12 Flowchart penentuan rekomendasi ................................................. 52 Gambar 4.13 Rancangan halaman penampilan rekomendasi ............................... 56 Gambar 4.14 Flowchart pembentukan data transaksi ........................................... 57 Gambar 5.1 Potongan kode tokenisasi .................................................................. 59 Gambar 5.2 Potongan kode stopword removal ..................................................... 59 Gambar 5.3 Potongan kode stemming ................................................................... 60 Gambar 5.4 Potongan kode perhitungan term frequency ...................................... 61 Gambar 5.5 Potongan kode frequent item search ................................................. 62 Gambar 5.6 Pengurutan frequent item .................................................................. 63 Gambar 5.7 Potongan kode struktur data Tree...................................................... 64 Gambar 5.8 Potongan kode pembentukan FP-Tree .............................................. 64
xii
Gambar 5.9 Pembentukan FP-Tree data transaksi 1, 2, 4, 5, dan 6 ...................... 66 Gambar 5.10 FP-Tree semua data transaksi .......................................................... 67 Gambar 5.11 Implementasi FP-Tree akhir ............................................................ 67 Gambar 5.12 Potongan kode pembentukan conditional FP-Tree ......................... 68 Gambar 5.13 Conditional FP-Tree untuk item id 2............................................... 69 Gambar 5.14 Conditional FP-Tree untuk item id 20............................................. 70 Gambar 5.15 Conditional FP-Tree untuk item id 3............................................... 70 Gambar 5.16 Conditional FP-Tree untuk item id 4............................................... 71 Gambar 5.17 Potongan kode ekstraksi itemset ..................................................... 71 Gambar 5.18 Urutan penggalian itemset ............................................................... 72 Gambar 5.19 Potongan kode perhitungan cosine similarity ................................. 73 Gambar 5.20 Potongan kode proses rekomendasi ................................................ 74 Gambar 5.21 Antar muka halaman rekomendasi .................................................. 76 Gambar 6.1 Grafik nilai precision jumlah rekomendasi maksimal ...................... 82 Gambar 6.2 Grafik nilai precision jumlah rekomendasi terbatas ......................... 84 Gambar 6.3 Grafik nilai recall jumlah rekomendasi maksimal ............................ 86 Gambar 6.4 Grafik nilai recall rekomendasi terbatas ........................................... 87 Gambar 6.5 Grafik nilai F-measure jumlah rekomendasi maksimal .................... 89 Gambar 6.6 Grafik nilai F-measure jumlah rekomendasi terbatas ....................... 90 Gambar 6.7 Grafik nilai mean average precision ................................................. 93
xiii
INTISARI HYBRID RECOMMENDATION SYSTEM MEMANFAATKAN PENGGALIAN FREQUENT ITEMSET DAN PERBANDINGAN KEYWORD Oleh Wayan Gede Suka Parwita 11/322973/PPA/03599 Recommendation system sering dibangun dengan memanfaatkan data peringkat item dan data identitas pengguna. Data peringkat item merupakan data yang langka pada sistem yang baru dibangun. Sedangkan, pemberian data identitas pada recommendation system dapat menimbulkan kekhawatiran penyalahgunaan data identitas. Hybrid recommendation system memanfaatkan algoritma penggalian frequent itemset dan perbandingan keyword dapat memberikan daftar rekomendasi tanpa menggunakan data identitas pengguna dan data peringkat item. Penggalian frequent itemset dilakukan menggunakan algoritma FP-Growth. Sedangkan perbandingan keyword dilakukan dengan menghitung similaritas antara dokumen dengan pendekatan cosine similarity. Hybrid recommendation system memanfaatkan kombinasi penggalian frequent itemset dan perbandingan keyword dapat menghasilkan rekomendasi tanpa menggunakan identitas pengguna dan data peringkat dengan penggunaan ambang batas berupa minimum similarity, minimum support, dan jumlah rekomendasi. Dengan data uji yang digunakan, nilai pengujian yaitu precision, recall, F-measure, dan MAP dipengaruhi oleh besarnya nilai ambang batas yang ditetapkan. Selain itu, kasus biasa pada kondisi terbaik dapat mencapai nilai yang lebih tinggi dibandingkan dengan kasus coldstart baik untuk jumlah rekomendasi terbatas maupun rekomendasi maksimal. Kata kunci : Hybrid recommendation system, frequent itemset, cosine similarity.
xiv
ABSTRACT HYBRID RECOMMENDATION SYSTEM USING FREQUENT ITEMSET MINING AND KEYWORD COMPARISON By Wayan Gede Suka Parwita 11/322973/PPA/03599 Recommendation system was commonly built by manipulating item ranking data and user identity data. Item ranking data was a rare data on newly constructed system. Whereas, giving identity data to the recommendation system can cause concern about identity data misuse. Hybrid recommendation system used frequent itemset mining algorithm and keyword comparison, it can provide recommendations without identity data and item ranking data. Frequent itemset mining was done using FP-Gwowth algorithm and keyword comparison with calculating document similarity value using cosine similarity approach. Hybrid recommendation system with a combination of frequent itemset mining and keywords comparison can give recommendations without using user identity and rating data. Hybrid recommendation system used 3 thresholds ie minimum similarity, minimum support, and number of recommendations. With the testing data used, precision, recall, F-measure, and MAP testing value are influenced by the threshold value. In addition, the usual problem in the best threshold can achieve a higher testing value than the coldstart problem both for the limited number of recommendations and the maximum recommendations. Keyword : Hybrid recommendation system, frequent itemset, cosine similarity.
xv
BAB I PENDAHULUAN 1.1 Latar Belakang Peningkatan jumlah dokumen ilmiah yang ada menimbulkan kebutuhan akan suatu sistem yang dapat memberikan rekomendasi dokumen ilmiah yang baik. Recommendation system merupakan model aplikasi yang dibangun dari hasil pengamatan terhadap keadaan dan keinginan pengguna. Sistem ini memanfaatkan opini pengguna terhadap suatu item dalam domain atau kategori tertentu. Karena itu sistem ini memerlukan model rekomendasi yang tepat agar apa yang direkomendasikan sesuai dengan keinginan pengguna, serta mempermudah pengguna mengambil keputusan yang tepat (McGinty dan Smyth, 2006). Recommendation system atau disebut pula recommender system mulai diperhatikan sejak kemunculan penelitian tentang collaborative filtering pada pertengahan 90‟an (Goldberg, dkk., 1992), (Resnick, dkk., 1994). Selama dekade terakhir ini, recommendation system telah banyak diterapkan dengan berbagai pendekatan baru, baik oleh dunia industri maupun akademis. Pada dunia industri, recommendation system sangat diperlukan terutama pada e-commerce web sites. Ini ditunjukkan dengan penggunaan recommendation system pada sebagian besar e-commerce web sites yang dimiliki oleh industri. Selain membantu pengguna dalam mencari item yang diinginkan, recommendation system juga dapat meningkatkan penjualan, ketertarikan maupun loyalitas pengguna terhadap suatu item dan juga perusahaan (Godfrey, 2007). Amazone.com merupakan contoh industri yang menerapkan sistem rekomendasi dalam e-commerce web sites mereka (Linden, dkk., 2003). Penerapan recommendation system berbasis collaborative filtering juga diterapkan pada jejaring sosial seperti Facebook, MySpace, dan LinkedIn (Ricci, dkk., 2011) Berbagai metode pendekatan telah diterapkan dan dikembangkan dalam implementasi recommendation system. Berdasarkan object filtering, metode tersebut dapat dikelompokkan ke dalam 3 jenis umum, yaitu metode collaborative
1
2
filtering, content-based filtering, dan hybrid filtering (Hsieh, dkk., 2004). Metode yang banyak digunakan adalah collaborative filtering dan content-based filtering. Masing-masing metode tersebut memiliki sejumlah kelebihan. Umpan balik yang digunakan pada metode collaborative filtering mengakibatkan sistem dapat memprediksi keinginan pengguna. Sedangkan metode content-based filtering menggunakan konten dari item sehingga dapat memberikan rekomendasi tanpa adanya umpan balik dari pengguna. Di samping memiliki kelebihan, kedua metode tersebut juga memiliki sejumlah kelemahan. Metode collaborative filtering baik user-based maupun item-based sangat tergantung dengan umpan balik yang diberikan oleh pengguna. Umpan balik berupa peringkat, data transaksi, maupun data identitas yang diberikan oleh pengguna. Tanpa umpan balik, metode collaborative filtering tidak dapat melakukan rekomendasi. Penggunaan data identitas pada metode user-based collaborative filtering juga mengakibatkan pengguna harus terdaftar pada sistem untuk membedakan klasifikasi data yang dikumpulkan dari pengguna. Akan tetapi, pengguna terkadang enggan untuk mendaftar pada sistem karena kekhawatiran terhadap penyalahgunaan data identitas. Di sisi lain, metode content-based memiliki ketergantungan terhadap perbandingan konten maupun atribut antara item. Recommendation system berbasis data mining dapat dikategorikan menjadi collaborative filtering maupun content-based filtering. Namun recommendation system yang memanfaatkan data mining berbasis data transaksi dapat dikategorikan
ke
dalam
item-based
collaborative
collaborative filtering menggunakan kedekatan
filtering.
item untuk
Item-based menentukan
rekomendasi. Kedekatan dapat dicari dengan melihat data transaksi yang melibatkan item tersebut. Metode pada data mining dapat dimanfaatkan dalam pencarian rekomendasi karena data mining juga memiliki fungsi untuk mencari kedekatan atara item. Dalam penerapan item-based ini dapat digunakan berbagai metode dalam data mining diantaranya klasifikasi, asosiasi, dan klaterisasi.
3
Kaidah asosiasi digunakan untuk mencari hubungan asosiatif antara kombinasi item. Asosiasi telah sukses diterapkan dalam masalah market basket. Pada pencarian kaidah asosiasi terdapat 2 tahap yang dilalui. Salah satu tahap yang dilakukan untuk pencarian kaidah asosiasi adalah penggalian frequent itemset dengan memanfaatkan minimum support. Tahap ini merupakan tahap yang menggunakan sumber daya yang paling besar. Semakin besar data transaksi yang digunakan maka semakin besar sumber daya yang digunakan. Data transaksi menyimpan informasi penting yang dihasilkan selama interaksi manusia dan komputer yang berguna untuk algoritma pembentukan rekomendasi. Data transaksi juga mencakup umpan balik eksplisit pengguna (Ricci, dkk., 2011). Untuk menghasilkan frequent itemset yang baik, maka minimum support pada tahap ini harus disesuaikan dengan data transaksi yang dimiliki. Recommendation system untuk dokumen ilmiah dapat memanfaatkan fungsi dari penggalian frequent itemset ini. Hanya saja, hubungan antara item belum dapat dipastikan secara jelas walaupun fungsi dari penggalian itu sendiri merupakan pencarian hubungan antara item. Ini disebabkan karena tahap penggalian frequent itemset tidak dilanjutkan dengan perhitungan confident antara item/itemset. Untuk mendapatkan kepastian hubungan antar item dalam itemset, dapat digunakan perbandingan keyword yang diekstraksi dari masing-masing dokumen ilmiah. Ekstraksi keyword yang dilakukan secara manual membutuhkan waktu yang tidak sedikit. Untuk itu, ekstraksi keyword pada dokumen ilmiah dapat menggunakan keyword extraction system. Dalam penerapannya, umumnya sistem ini digunakan untuk identifikasi topik dokumen. Pembandingan keyword dokumen termasuk content-based recommendation system karena menggunakan isi dari dokumen untuk membentuk rekomendasi. Keyword extraction system merupakan sistem yang dapat menemukan keyword dari dokumen secara otomatis. Metode cosine similarity merupakan salah satu metode untuk menghitung similaritas dokumen. Kelebihan utama dari metode cosine similarity adalah tidak terpengaruh pada panjang pendeknya suatu dokumen (Rozas dan
4
Sarno, 2011). Dengan melakukan perbandingan keyword yang dihasilkan, maka kedekatan antara item-pun dapat dipastikan. Penentuan rekomendasi tanpa penggunaan data peringkat dan data identitas pengguna dapat dilakukan dengan menggunakan kombinasi metode penggalian frequent itemset dan perbandingan keyword yang menjadi kontribusi penelitian ini. Penggunaan penggalian frequent itemset yang dikombinasikan dengan perbandingan keyword akan menghasilkan hybrid recommendation system. Penggalian frequent itemset akan memperkecil jumlah pembandingan keyword yang dilakukan sehingga jumlah perbandingan keyword dapat dikurangi. Sedangkan perbandingan keyword akan memastikan item yang dihasilkan algoritma penggalian frequent itemset saling terkait. Berdasarkan latar belakang tersebut, maka pada penelitian ini akan dilakukan kombinasi dari algorima penggalian frequent itemset dan perbandingan hasil keyword extraction system untuk penentuan rekomendasi. Kombinasi ini akan menghasilkan hybrid recommendation system untuk penentuan rekomendasi dokumen ilmiah. 1.2 Rumusan Masalah Berdasarkan latar belakang yang telah dipaparkan dapat dirumuskan masalah yang akan dikaji dalam penelitian ini yaitu bagaimana menghasilkan recommendation system untuk merekomendasikan dokumen ilmiah tanpa menggunakan data identitas pengguna dan data peringkat yang diberikan oleh pengguna dengan memanfaatkan kombinasi 2 metode. Metode pertama melakukan penggalian frequent itemset pada data transaksi pemilihan dokumen ilmiah. Kemudian metode kedua melakukan perbandingan antar item yang masuk pada itemset dengan membandingkan keyword yang dihasilkan secara otomatis.
5
1.3 Batasan Masalah Berikut merupakan batasan masalah yang digunakan agar penelitian ini tetap mengacu pada topik penelitian: a.
Keyword extraction system akan didasarkan pada dokumen ilmiah berbahasa Indonesia.
b.
Keyword extraction system melakukan ekstraksi terhadap teks bukan gambar ataupun bentuk lain selain teks.
c.
Recommendation system yang dibangun tidak menekankan pada proses seleksi dokumen saat pencarian dokumen.
d.
Jumlah rekomendasi yang dihasilkan oleh sistem akan ditentukan secara manual oleh administrator sistem.
e.
Dokumen ilmiah yang digunakan untuk pengujian merupakan 100 dokumen ilmiah yang berupa jurnal bahasa Indonesia yang diambil secara acak.
1.4 Tujuan Penelitian Tujuan penelitian yaitu menghasilkan recommendation system dokumen ilmiah bahasa Indonesia yang berfokus pada pemanfaatan algoritma penggalian frequent itemset dan perbandingan keyword dengan memanfaatkan data transaksi dan isi dari dokumen. 1.5 Manfaat Penelitian Penelitian ini diharapkan menjadi referensi tentang pengembangan hybrid recommendation
system
untuk
dokumen
berbahasa
Indonesia
tanpa
memperhitungkan peringkat yang diberikan pengguna dan juga dapat mengatasi kelemahan dari item-based collaborative filtering dan content-based filtering yang berdiri sendiri. Selain itu, penelitian ini juga diharapkan menjadi referensi dalam pemanfaatan algoritma pada data mining dan text mining untuk pengembangan recommendation system.
6
1.6 Metodologi Penelitian Penelitian ini dilakukan dengan mengikuti langkah-langkah sebagai berikut: 1.
Mempelajari pustaka dan literatur acuan: tahap ini dilakukan dengan membaca serta memahami buku teks, jurnal, dan karya ilmiah lainnya yang terkait dengan penelitian.
2.
Analisis: kegiatan analisa meliputi analisa metode, alternatif algoritma yang diterapkan, sepesifikasi perangkat lunak, dan analisa fungsionalitas.
3.
Perancangan: tahap ini meliputi perancangan algoritma dan pemodelan arsitektur untuk metode keyword extraction system, penggalian frequent itemset, dan perbandingan keyword yang diterapkan untuk penentuan rekomendasi dokumen.
4.
Implementasi:
tahap
implementasi
merupakan
pembangunan
sistem
perangkat lunak berdasarkan perancangan yang telah dilakukan sebelumnya. 5.
Evaluasi dan perbaikan: pada tahap ini dilakukan evaluasi dari sistem serta memperbaikinya jika terdapat kesalahan yang terjadi.
6.
Pengujian dan analisa akhir: tahap ini meliputi pengujian kualitas dan kinerja dari recommendation system yang dibangun.
7.
Penulisan laporan: pada tahap ini dilakukan penulisan laporan dari hasil penelitian yang telah dilakukan.
7
1.7 Sistematika Penulisan Penulisan tesis ini terdiri dari 7 bab, adapun sistematika dari tesis ini adalah: BAB I PENDAHULUAN Pada bab ini diuraikan secara singkat mengenai latar belakang masalah, perumusan masalah, batasan masalah, tujuan penelitian, manfaat penelitian, metodologi penlitian, dan sistematika penulisan. BAB II TINJAUAN PUSTAKA Pada bab ini dibahas penelitian-penelitian yang sudah dilakukan sebagai perbandingan dan acuan untuk penelitian ini. BAB III LANDASAN TEORI Pada bab ini diuraikan teori-teori dasar berkaitan dengan penelitian yang dilakukan sebagai dasar dalam pemecahan masalah. Teori tersebut meliputi recommendation system, keyword extraction system, penggalian frequent itemset serta cosine similarity. BAB IV ANALISIS DAN PERANCANGAN Pada bab ini diuraikan perancangan metode-metode yang digunakan pada penelitian. BAB V IMPLEMENTASI Pada bab ini dibahas tentang implementasi rancangan algoritma dan antarmuka yang digunakan pada sistem meliputi potongan program serta implementasi rancangan antarmuka sistem. BAB VI HASIL DAN PEMBAHASAN Pada bab ini dilakukan pengujian terhadap recommendation system yang dibangun
serta
pembahasan
hasil
pengujian.
Pengujian
meliputi
8
perhitungan nilai precision, recall, F-measure, mean average precision dari sistem yang dibangun. BAB VII KESIMPULAN DAN SARAN Pada bab ini berisi kesimpulan dari hasil penelitian serta saran-saran untuk penelitian lebih lanjut.
BAB II TINJAUAN PUSTAKA Recommendation system pertama kali muncul pada tahun 1997 (Resnick dan Varian, 1997). Beberapa penelitian yang telah dilakukan sebelumnya berkaitan dengan document recommendation system dan hybrid recommendation system. 2.1 Document Recommendation System Hsieh dkk. (2004) mengajukan recommendation system yang dapat melakukan penyaringan berita online secara efektif pada world wide web. Recommendation system ini menggunakan pendekatan content-based dan collaborative filtering
yang dimodifikasi.
Untuk meminimalisasi
waktu
komputasi, pendekatan ini mengatur minimum support dan confident untuk pencarian hunbungan asosiatif antar item. Klasterisasi akan diterapkan dalam pencarian kedekatan berita dengan berbasis isi dari berita. Setiap pengguna sistem harus memasukkan peringkat untuk setiap berita yang dibaca, sehingga pengguna harus terdaftar sebelumnya. Jika pengguna membaca berita dan merasa tertarik pada isi berita, maka berita tersebut akan direkomendasikan ke tetangga terdekat. Dimana kedekatan ini dihitung dengan algoritma lintasan terpendek. Dengan penggunaan pendekatan yang diusulkan Hsieh dkk. (2004), sistem dapat mengatasi kelemahan cluster-based recommnedation system yaitu dapat memberikan rekomendasi kepada pengguna walaupun pengguna tidak masuk ke dalam salah satu kelas. Penelitian Hsieh dkk. (2004) memiliki perbedaan dengan penelian ini pada penggunaan data input untuk menentukan rekomendasi. Penelitian ini hanya melibatkan data transaksi pemilihan dokumen dan konten dokumen untuk menentukan rekomendasi. Penelitian dkk. (2004) menggunakan kaidah asosiasi sebagai algoritma untuk mencari hubungan asosiatif antara berita, sedangkan penelitian ini hanya menggunakan penggalian itemset untuk pencarian hubungan asosiatif antara dokumen.
9
10
Market-based collaborative information-filtering (MarCol) dibangun untuk untuk pencarian dokumen yang relevan untuk pengguna. MarCol diusulkan oleh Melamed dkk. (2007) dengan memanfaatkan pendekatan collaborative filtering. Pencarian dokumen yang relevan dicari menggunakan kemiripan antara query yang dimasukkan pengguna serta kemiripan antara pengguna. Dengan kata lain, dokumen yang direkomendasikan dihasilkan dari pencocokan keyword yang dimasukkan oleh pengguna yang dikombinasikan dengan data transaksi dan data profil penggguna. Selain itu, recommendation system diaplikasikan dengan penerapan biaya rekomendasi. Dalam penelitian Melamed dkk. (2007) terdapat 2 biaya yang diuji yaitu gratis dan berbayar. Berdasarkan hasil penelitian, penerapan model MarCol menunjukkan adanya peningkatan umpan balik dan kualitas rekomendasi. MarCol merupakan penelitian yang berfokus pada perbedaan anatara sistem gratis dan berbayar. Selain dalam penggunaan algoritma, penelitian ini berbeda dengan MarCol pada bagian penggunaan data identitas pengguna dalam penentuan rekomendasi dokumen. Penelitian recommendation system untuk dokumen juga dilakukan oleh Popa dkk. (2008). Hanya saja, penelitian Popa dkk. (2008) difokuskan untuk dokumen ilmiah dan menerapkan sistem yang terdistribusi. Sistem yang dibangun akan menghasilkan 2 rekomendasi yaitu “pengguna yang mirip” dan “dokumen yang mungkin disukai”. Untuk rekomendasi “pengguna yang mirip”, sistem akan menghitung kemiripan menggunakan pendekatan klasifikasi dengan berbasis pada identitas pengguna. Daftar rekomendasi pengguna tersebut akan digunakan untuk membentuk identitas pengguna yang baru terdaftar. Sedangkan untuk “dokumen yang mungkin disukai”, sistem akan melakukan klaterisasi terhadap dokumen. Sebelum melakukan klasterisasi, sistem akan mencari dokumen yang sesuai dengan pengguna berdasarkan data transaksi pengguna lain yang memiliki karakteristik sama. Dalam implementasinya, pendekatan Popa dkk. (2008) berhasil melakukan rekomendasi dokumen ilmiah berbasis sudut pandang pengguna. Penelitian Popa dkk. (2008) juga memanfaatkan content-based filtering dengan isi dokumen sebagai data untuk melakukan penyaringan dokumen
11
rekomendasi. Penelitian Popa dkk. (2008) dan penelitian ini memiliki perbedaan pada bagian penggunaan data identitas untuk menghitung kemiripan antara pengguna. Penelitian ini tidak memperhatikan latar belakang dari pengguna sistem dalam penentuan dokumen terkait. Pham dan Trach (2011) mengungkapkan bahwa menemukan dan merekomendasikan dokumen yang relevan bagi pengguna yang membutuhkan bukanlah
tugas
yang
mudah.
Mereka
lalu
mengusulkan
pendekatan
recommendation system dengan memanfaatkan kemiripan dokumen. Pendekatan Pham dan Trach (2011) menggunakan konten dari dokumen digabungkan dengan social tags dan data pengguna yang terkait. Ketiga faktor tersebut lalu disebut sebagai 3 dimensi dokumen. Dilihat dari faktor yang digunakan, pendekatan yang diusulkan merupakan gabungan antara user-based, item-based collaborative filtering, dan content-based filtering. Dengan demikian, pendekatan sistem yang diusulkan merupakan sistem hybrid. Penelitian Pham dan Trach (2011) mendapati hasil bahwa ketiga dimensi tersebut memiliki kontribusi penting dalam perhitungan kemiripan dokumen. Akan tetapi, penggunaan tag yang diberikan oleh komunitas dan profil pengguna untuk menghitung kemiripan mengakibatkan pengguna harus terdaftar terlebih dahulu di dalam sistem. Suzuki dkk. (2011) mengusulkan metode recommendation system baru untuk dokumen dengan pendekatan content-based menggunakan kompresi data. Berbeda dengan penelitian recommendation system dokumen sebelumnya yang hanya menggunakan sejumlah kata pada dokumen untuk mencari kedekatan profil pengguna serta dokumen, pendekatan Suzuki dkk. (2011) menggunakan kombinasi kompresi data, kedekatan profil pengguna, dan dokumen berdasarkan kata yang ada pada dokumen. Hasil eksperimen menggunakan surat kabar Jepang menunjukkan bahwa metode kompresi data lebih baik daripada metode yang hanya mengandalkan sejumlah kata pada dokumen, terutama ketika topik pada surat kabar berjumlah besar. Selain itu metode kombinasi Suzuki dkk. (2011) mengungguli metode kompresi data sebelumnya dan kombinasi kompresi data serta pemanfaatan kata pada dokumen juga dapat meningkatkan kinerja. Maka
12
dari itu dapat disimpulkan bahwa metode Suzuki dkk. (2011) lebih baik dalam menangkap profil pengguna dan dengan demikian memberikan kontribusi untuk membuat recommendation system untuk dokumen yang lebih baik. Perbedaan penelitian ini dengan penelitian Suzuki dkk. (2011) terletak pada penggunaan algoritma dan data acuan untuk menentukan rekomendasi. Penelitian ini menggunakan keyword sebagai penentu rekomendasi. Penentuan keyword ini tidak menggunakan tahap kompresi data. Penelitian ini juga mengabaikan data identitas pengguna dalam penentuan rekomendasi. 2.2 Hybrid Recommendation System Item-based Clustering Hybrid Method (ICHM) diusulkan oleh Li dan Kim (2003). Metode ini dirancang untuk mengatasi kasus cold-start yang terdapat pada metode
collaborative
filtering.
Bebeda
dengan
penelitian
ini,
ICHM
memanfaatkan atribut dari item dalam penemtuaan rekomendasi saat kasus coldstart. Metode ini memanfaatkan klasterisasi untuk pengelompokan item dengan memanfaatkan kemiripian setiap item yang dicari berdasarkan atribut dari item tersebut. Lalu dengan collaborative filtering, data peringkat yang diberikan pengguna akan digunakan untuk menentukan kemiripan selera pengguna satu dengan pengguna lain terhadap item tertentu. Sistem ICHM diaplikasikan untuk rekomendasi data film yang diambil dari MovieLens.org. Sistem ICHM diuji dengan menggunakan perhitungan mean absolute error (MAE). Setelah diuji, sistem
ICHM
dikatakan
dapat
mengatasi
cold-start
problem
dengan
memanfaatkan teknik klasterisasi tersebut. Selain itu, sistem ICHM juga dapat meningkatkan kualitas prediksi yang dihasilkan. Liangxing dan Aihua (2010) mengusulkan sebuah hybrid recommendation system yang berbasis content-base filtering dan collaborative filtering yang dapat memberikan rekomendasi pembelian bagi pelanggan VIP dari toko pakaian ritel. Sebelum menghasilkan rekomendasi akhir, sistem yang diusulkan Liangxing dan Aihua (2010) membentuk daftar rekomendasi awal dengan menggunakan gabungan hasil dari 2 proses collaborative filtering. Proses pertama adalah
13
pengolahan
data
transaksi
pembelian
menggunakan
metode
item-based
collaborative filtering. Proses kedua adalah pengolahan data pengguna menggunakan metode user-based collaborative filtering. Daftar rekomendasi awal tersebut diproses dengan content-based filtering yang berupa pengklasifikasian produk untuk menghasilkan rekomendasi akhir. Penggunaan metode user-based collaborative filtering mebuat penelitian Liangxing dan Aihua (2010) berbeda dengan
penelitian
ini.
Hasil
pengujian
menunjukkan
bahwa
hybrid
recommendation system dapat melaksanakan analisis selera pelanggan dan rekomendasi produk di toko pakaian ritel. Penelitian tentang Item-based Clustering Hybrid Method (ICHM) kembali dilakukan oleh Djamal dkk. (2010). ICHM merupakan salah satu cara untuk menggabungkan metode yang digunakan dalam pembangunan recommendation system. Pembahasan pada penelitian difokuskan pada implementasi ICHM dalam recommendation system untuk film dengan dataset yang bersumber dari movielens.org. Pada sistem yang dibangun, content-based filtering dimanfaatkan pada klasterisasi pada konten setiap item. Sedangkan item-based collaborative filtering dimanfaatkan dalam perhitungan kedekatan antara item dengan menggunakan peringkat yang telah diberikan oleh pengguna. Untuk perhitungan prediksi yang dihasilkan, sistem ICHM menggunakan 2 pendekatan yang berbeda. Yang pertama untuk masalah cold-start dan yang kedua untuk masalah non coldstart. Walaupun dapat memberikan rekomendasi tanpa data peringkat, penggunaan data peringkat sebagai salah satu penentu rekomendasi pada penelitian Djamal dkk. (2010) berbeda dengan penelitian ini yang sama sekali tidak memperhitungkan data peringkat item sebagai penentu rekomendasi. Hasil implementasi menunjukkan bahwa recommender system dengan metode ICHM dapat memprediksi item baru yang belum memiliki peringkat sama sekali dengan cara memperhitungkan kedekatan berdasarkan genre item. Selain itu setelah dihitung berdasarkan mean absolute error (MAE) penambahan jumlah cluster hingga 70 buah cenderung meningkatkan akurasi prediksi baik untuk kasus coldstart dan kasus non cold-start, namun akurasi turun pada jumlah cluster sebanyak
14
60 buah karena terdapat nilai membership yang saling bertolak belakang untuk beberapa item di beberapa cluster. Hybrid recommendation system yang menerapkan pendekatan berbeda diajukan oleh Chikhaoui dkk. (2011) dengan melakukan penelitian tentang recommendation system yang menggunakan 3 pendekatan, yaitu collaborative filtering, content-based, dan demographic filtering untuk rekomendasi film. Pada collaborative filtering digunakan pendekatan dengan menggunakan neigborhoodbased terhadap data peringkat. Dalam pendekatan neigborhood-based, kesukaan dari pengguna u terhadap item i akan dihitung berdasarkan kesukaan pengguna lain yang memiliki karakteristik mirip dengan pengguna u terhadap item i. Dengan algoritma KNN, data karakteristik film seperti genre, negara pembuat, dan tanggal perilisan digunakan sebagai pembanding untuk menentukan kemiripan suatu item terhadap item i. Pengolahan data karakteristik film tersebut merupakan contentbased filtering. Pada sisi demographic filtering dicari pengguna yang memiliki kesukaan yang mirip atau selera yang sama. Demographic filtering ini digunakan untuk mengatasi kelemahan dari collaborative filtering dan juga content-based filtering pada saat terjadinya kasus coldstart. Selain algoritma yang digunakan, penggunaan data identitas pengguna dan penggunaan atribut item merupakan perbedaan utama antara penelitian ini dan penelitian Chikhaoui dkk. (2011). Dengan melalui eksperimen, hasil penelitian Chikhaoui dkk. (2011) menunjukkan bahwa pendekatan tersebut mencapai akurasi yang baik dengan cakupan tinggi melebihi algoritma penyaringan konvensional serta metode hybrid biasa. Selain itu, hasil eksperimen menunjukkan bagaimana pendekatan Chikhaoui dkk. (2011) berhasil mengatasi kasus cold-start dengan memasukkan karakteristik demografis pengguna. Di tahun yang sama, Hayati (2011) membangun hybrid recommendation system untuk penentuan daerah wisata. Dalam penentuan rekomendasi, sistem yang dibangun menggunakan peringkat daerah wisata dan profil pengguna sebagai acuan. Sistem tersebut juga memiliki keunggulan dengan tidak diperlukannya data masukan dan peringkat awal untuk mendapatkan rekomendasi karena penggunaan
15
algoritma klasifikasi terhadap data daerah wisata dan profil pengguna. Pengklasifikasian dilakukan dengan menggunakan algoritma nearest neighbor untuk mencari kedekatan antara daerah wisata dan juga pengguna, sehingga hybrid recommendation system yang dibangun berhasil mengatasi masalah coldstart. Penentuan rekomendasi dokumen dilakukan dengan memperhatikan data peringkat dan data identitas pengguna. Pendekatan tersebut memiliki kelemahan pada kasus coldstart yaitu saat sistem tidak memiliki data umpan balik dari pengguna. Selain itu, penelitian sebelumnya tidak memperhatikan data transaksi yang didapat dari pemilihan dokumen. Secara umum, terdapat beberapa perbedaan antara penelitian ini dengan penelitian-penelitian sebelumnya. Selain pada algoritma penentuan rekomendasi, penelitian ini tidak memanfaatkan data identitas pengguna dan data peringkat sebagai data acuan untuk penentuan rekomendasi. Hal ini dapat mengurangi kekhawatiran penyalahgunaan data identitas pengguna. Selain itu, untuk pengguna baru maupun saat sistem baru dibangun tidak akan terkendala dengan kebutuhan data umpan balik dari pengguna untuk penentuan rekomendasi dokumen. Hal ini dimungkinkan karena penggunaan konten dokumen sebagai data penentuan rekomendasi. Pada Tabel 2.1 akan ditunjukkan perbandingan dan ringkasan dari beberapa penelitian yang telah disebutkan diatas.
16 Tabel 2.1 Tinjauan pustaka No. Peneliti 1. Li dan Kim (2003)
Domain Film
2.
Hsieh, Huang, Hsu dan Chang (2004)
Berita
3.
Melamed, Shapira dan Elovici (2007)
Dokumen
4.
Popa, Negru, Pop dan Muscalagiu (2008) Liangxing dan Aihua (2010)
Dokumen ilmiah Pakaian
6.
Djamal, Maharani dan Kurniati (2010)
Film
7.
Pham dan Thach (2011)
Dokumen
8.
Chikhaoui, Chiazzaro dan Wang (2011)
Film
9.
Hayati (2011)
Daerah wisata
5.
Metode Collaborative filtering pada pemeringkatan item dan klasifikasi terhadap atribut item Collaborative fitering pada pemeringkatan item dan content-based filtering pada konten beserta data transaksi item
Collaborative filtering pada umpan balik pengguna dan pencarian dengan memperhatikan query yang dimasukkan pengguna Pendekatan klasifikasi dengan berbasis pada profil pengguna dan klasterisasi pada data dokumen Item-based collaborative filtering pada data transaksi pembelian, user-based collaborative filtering pada data pengguna, content-base filtering untuk pengklasifikasian produk Content-base filtering pada klasterisasi pada konten setiap item. Item-based collaborative filtering dalam perhitungan peringkat User-based collaborative filtering terhadap data pengguna, item-based collaborative filtering terhadap social tag, dan content-based filteringterhadap isi dokumen collaborative filtering pada data peringkat item, content-based pada data karakteristik film, dan demographic filtering pada data pengguna Collaborative filtering pada peringkat daerah wisata dan profil pengguna. Jika tidak
Hasil Mengatasi masalah cold-start pada collaborative filtering Mengatasi kelemahan cluster-based recommnedation system yaitu dapat memberikan rekomendasi kepada pengguna walaupun pengguna tidak masuk ke dalam salah satu kelas Menunjukkan adanya peningkatan umpan balik dan kualitas rekomendasi Menghasilkan recommendation system terdistribusi berbasis sudut pandang pengguna Dapat melaksanakan analisis selera pelanggan dan rekomendasi produk di toko pakaian ritel
Dapat memprediksi item baru yang belum memiliki peringkat sama sekali Ketiga dimensi dokumen Memiliki kontribusi penting dalam perhitungan kemiripan dokumen
Mengatasi kasus cold-start dengan memasukkan karakteristik demografis pengguna Mengatasi masalah cold-start dengan penerapan klasifikasi
17
10.
11.
Suzuki, Hasegawa, Hamamoto dan Aizawa (2011) Parwita (2014)
Berita
Dokumen Ilmiah
memungkinkan dilakukan klasifikasi atribut daerah wisata dan profil pengguna. Content-based filtering menggunakan kompresi data Item-based collaborative filtering pada penggalian frequent itemset dengan memanfaatkan data transaksi dan content-based filtering pada perbandingan keyword dokumen dengan perhitungan cosine similarity.
Meningkatkan kinerja recommendation system yang menggunakan “kantong kata” Menghasilkan rekomendasi tanpa menggunakan data identitas pengguna dan data peringkat. Serta mengatasi kelemahan dan menggabungkan keunggulan penggunaan metode collaborative filtering atau contentbased filtering yang berdiri sendiri.
BAB III LANDASAN TEORI 3.1 Recommendation System Recommendation
system
merupakan
teknik
dan
software
untuk
menghasilkan usulan item yang akan dimanfaatkan oleh pengguna. “Item” merupakan istilah yang digunakan untuk menyatakan apa yang direkomendasikan oleh sistem kepada pengguna. Usulan tersebut dihasilkan berdasarkan berbagai proses pengambilan keputusan seperti barang apa yang akan dibeli, lagu apa yang ingin didengarkan dan berita apa yang akan dibaca. Dalam bentuknya, recommendation system akan memberikan semacam daftar item. Item tersebut dapat berupa produk maupun jasa. Dalam pembuatan daftar item tersebut, recommendation system mencoba untuk menemukan produk atau jasa yang paling sesuai berdasarkan kebutuhan dan keinginan pengguna. Untuk menemukannya, recommendation system menggunakan data ketertarikan pengguna yang dinyatakan secara eksplisit dalam data peringkat item atau disimpulkan dengan menebak tindakan pengguna (Ricci, dkk., 2011). Pembangunan recommendation system dimulai dari keinginan untuk meniru kebiasaan sederhana yaitu pengguna sering mengandalkan rekomendasi yang diberikan oleh pengguna lain dalam membuat rutinitas maupun keputusan. Contohnya adalah saat penonton ingin menyaksikan sebuah film. Untuk memutuskan apakah layak atau tidak menyaksikan film tersebut, maka penonton akan menilai dari review maupun pendapat dari penonton yang telah menyaksikan film tersebut. Dalam pembangunan recommendation system, dilakukan penerapan algoritma dengan memanfaatkan rekomendasi yang dihasilkan oleh komunitas pengguna untuk memberikan rekomendasi kepada pengguna lain. Item yang direkomendasikan merupakan item yang disukai oleh pengguna-pengguna dengan selera serupa. Pendekatan ini disebut collaborative filtering dengan dasar pemikirannya adalah jika pengguna setuju dengan pendapat beberapa pengguna lain terhadap suatu item, maka rekomendasi yang dihasilkan dari pengguna lain dengan selera sama akan relevan dan menarik bagi pengguna tersebut. Pendapat 18
19
pengguna dapat berupa peringkat yang diberikan maupun pilihan yang dilakukan oleh pengguna. Collaborative filtering merupakan implementasi paling sederhana dan merupakan versi awal dari pendekatan recommendation system. Kemiripan selera dari dua pengguna dihitung berdasarkan kesamaan dalam pendapat pengguna terhadap item. Dengan kata lain, collaborative filtering adalah proses penyaringan atau evaluasi item menggunakan pendapat dari orang lain (Schafer, dkk., 2007). Content-based filtering dan collaborative filtering telah lama dipandang saling melengkapi. Content-based filtering dapat memprediksi relevansi untuk item tanpa peringkat (misalnya, item baru, artikel berita, halaman website). Content-based filtering memerlukan konten untuk melakukan analisis. Pada beberapa hal, konten merupakan sesuatu yang langka (misalnya, rekomendasi untuk restoran dan buku teks yang tersedia tanpa ulasan) atau sulit untuk mendapatkan dan mewakili konten itu (misalnya, film dan musik). Di sisi lain, collaborative filtering membutuhkan peringkat item untuk melakukan prediksi tanpa memerlukan konten. Content based filtering dan collaborative filtering dapat dikombinasikan secara manual oleh pengguna untuk menentukan fitur tertentu. Dalam implementasinya kedua metode tersebut dapat digabungkan secara otomatis yang disebut dengan pendekatan hybrid. Ada banyak cara dalam menggabungkan metode tersebut dan tidak ada kesepakatan di antara peneliti untuk cara menggabungannya. 3.2 Penggalian Frequent Itemset Kaidah asosiasi adalah teknik data mining untuk menemukan aturan asosiatif antara suatu kombinasi item. Fungsi kaidah asosiasi seringkali disebut dengan “market basket analysis”. Penting tidaknya suatu aturan asosiatif dapat diketahui dengan menggunakan dua parameter, support yaitu persentase kombinasi item tersebut dalam basis data dan confidence yaitu kuatnya hubungan antar item dalam aturan asosiatif. Salah satu tahap dalam kaidah asosiasi adalah
20
menemukan semua kombinasi dari item, disebut dengan itemset, yang jumlah kemunculannya lebih besar daripada minimum support (Rajaraman dan Ullman, 2010). Misalkan, ada sekumpulan data transaksi pembelian perangkat komputer seperti yang ditunjukkan pada Tabel 3.1. Tabel 3.1 Data transaksi Transaction ID (TID) 1 2 3 4 5 6 7 8 9 10
Item processor, motherboard, memory processor, motherboard, memory processor processor, motherboard motherboard processor, motherboard processor, memory motherboard, memory motherboard memory
Setiap data transaksi sering disebut dengan keranjang (basket). Setelah disusun, setiap keranjang tersebut dapat direpresentasikan dengan Tabel 3.2. Tabel 3.2 Representasi keranjang Produk processor motherboard memory processor, motherboard processor, memory motherboard, memory processor, motherboard, memory
TID 1, 2, 3, 4, 6, 7 1, 2, 4, 6, 8, 9 1, 2, 7, 8, 10 1, 2, 4, 6 1, 2, 7 1, 2, 8 1, 2
Tabel 3.3 Frequent itemset Produk processor motherboard memory processor, motherboard
Jumlah 6 6 5 4 3 3 2
21
Data transaksi tersebut akan dikenakan minimum support sebesar 40% dari jumlah data transaksi sehingga didapatkan beberapa itemset melebihi minimum support disebut dengan frequent itemset yang ditunjukkan oleh Tabel 3.3. 3.2.1
FP-Growth Salah satu algoritma penggalian frequent itemset yang cepat dan juga
populer adalah algoritma FP-Growth. FP-Growth berbasis pada tree disebut dengan FP (Frequent Pattern)-Tree (Zaki dan Meira, 2014). FP-Tree dapat menghemat penggunaan memori untuk penyimpanan data transaksi. Ide dasar dari FP-Growth dapat digambarkan sebagai skema eliminasi secara rekursif. Dalam langkah preprocessing, dilakukan penghapusan semua item yang kemunculannya kurang dari minimum support yang diberikan. Kemudian dipilih semua transaksi yang mengandung frequent item lalu dibentuk FP-Tree berdasarkan data transaksi tersebut. Dalam penggalian frequent itemset, dibentuk conditional FP-Tree yang berakhir pada salah satu frequent item. Pembentukan ini dilakukan secara rekursif dengan mengeliminasi satu persatu frequent item akhir yang terdapat pada tree tersebut. Penentuan frequent itemset dilakukan bersamaan saat pengeliminasian dengan melihat support dari frequent item tersebut (Han, dkk., 2011). adf acde bd bcd bc abd bde bceg cdf abd
d b c a e f g
8 7 5 4 3 2 1
da dcae db dbc bc dba dbe bce dc dba
Gambar 3.1 Penentuan frequent item Sebelum membentuk FP-Tree, semua item tunggal yang memenuhi minimum support (frequent item) diidentifikasi dan diurutkan berdasarkan banyaknya jumlah kemunculan (Han, dkk., 2011). Kemudian untuk item yang tidak memenuhi minimum support akan diabaikan dari data transaksi, karena item tersebut sudah pasti bukan bagian dari frequent itemset. Pengurutan item
22
dilakukan dari yang paling sering muncul ke yang paling jarang. Hal ini untuk meningkatkan kinerja dari algoritma (Borgelt, 2005). Gambar 3.1 merupakan contoh penentuan frequent item untuk minimum support 3 dan pengurutan itemset berdasarkan jumlah kemunculan. d:8
d:8
b:7
c:5
b:5
b:2
c:1
a:4
c:2
a:2
e:3
a:1
e:1
c:2
a:1
e:1
e:1
Gambar 3.2 FP-Tree FP-Tree mengandung data label, jumlah kemunculan, alamat parent, child, dan prefix path (Han, dkk., 2011). Contoh FP-Tree ditunjukkan oleh Gambar 3.2. Untuk kepentingan pembentukan prefix path, maka child sebuah node diurutkan berdasarkan jumlah kemunculan keseluruhan. d:8
d:8
b:7
c:5
a:4
e:3
b:5
b:2
c:1
c:2
a:2
a:1
e:1
e:1
c:2
a:1
e:1
Gambar 3.3 Pembentukan conditional FP-Tree item „e‟
23
Conditional FP-Tree merupakan bagian FP-Tree yang berakhir pada node tertentu. Conditional FP-Tree digunakan untuk penggalian frequent itemset (Han, dkk., 2011). Misalnya, untuk penentuan item „e‟ akan diambil semua path node yang berakhir di „e‟. Lalu, node „e‟ di masing path akan dihapus. Gambar 3.3 dan Gambar 3.4 merupakan contoh pembentukan conditional FP-Tree yang berakhir pada node „e‟. d:2
b:2
d:2
b:1
b:1
c:2
c:1
a:1
a:1
c:1
Gambar 3.4 Conditional FP-Tree item „e‟ Untuk penentuan itemset lain yang mengandung „e‟, maka conditional FPTree item tersebut akan dibentuk dari conditional FP-Tree „e‟. Gambar 3.5 merupakan contoh pembentukan conditional FP-Tree untuk itemset „b e‟. Penggalian frequent itemset dilakukan secara rekursif. Jika node memenuhi minimum support maka node tersebut merupakan frequent itemset. Gambar 3.6 merupakan urutan itemset hasil penggalian frequent itemset dalam FP-Growth. d:2
b:2
d:2
b:1
b:1
c:2
c:1
a:1
a:1
c:1
Gambar 3.5 Pembentukan conditional FP-Tree item „b e‟
24
e
ae
cae
bcae
dbcae
dcae bae
dbae
dae ce
a
bce
……...
dce
……...
be
……...
de
……...
……...
….
Gambar 3.6 Urutan hasil penggalian frequent itemset 3.3 Keyword Extraction System Dalam
dokumen
ilmiah,
keyword
adalah
kata
pokok
yang
merepresentasikan masalah yang diteliti atau istilah-istilah yang merupakan dasar pemikiran dan dapat berupa kata tunggal atau gabungan kata. Similaritas keyword dokumen dapat digunakan untuk menentukan relevansi dokumen terhadap dokumen lain (Weiss, dkk., 2005). Automatic keyword extraction system memiliki tugas untuk mengidentifikasi kumpulan kata, frase kunci, keyword, atau segmen kunci dari sebuah dokumen yang dapat menggambarkan arti dari dokumen (Hulth, 2003). Tujuan dari ekstraksi otomatis adalah menekan kelemahan pada ekstraksi manual yang dilakukan manusia yaitu pada kecepatan, ketahanan, cakupan, dan juga biaya yang dikeluarkan. Salah satu pendekatan yang dapat digunakan dalam automatic keyword extraction yaitu pendekatan tata bahasa. Pendekatan ini menggunakan fitur tata bahasa dari kata-kata, kalimat, dan dokumen. Metode ini memperhatikan fitur tata bahasa seperti bagian kalimat, struktur sintaksis, dan makna yang dapat menambah bobot. Fitur tata bahasa tersebut dapat digunakan sebagai penyaring untuk keyword yang buruk. Dalam ekstraksi keyword dengan pendekatan tata bahasa berbasis struktur sintaksis, ada beberapa tahap yang dilakukan yaitu tokenisasi, stopword removal, stemming, dan pembobotan kata (Oelze, 2009).
25
3.3.1
Tokenisasi Teks elektronik adalah urutan linear simbol (karakter, kata-kata atau
frase). Sebelum dilakukan pengolahan, teks perlu disegmentasi ke dalam unit-unit linguistik seperti kata-kata, tanda baca, angka, alpha-numeric, dan lain-lain Proses ini disebut tokenisasi. Tokenisasi sederhana (white space tokenization) merupakan tokenisasi yang memisahkan kata berdasarkan karakter spasi, tab, dan baris baru (Weiss, dkk., 2005). Namun, tidak setiap bahasa melakukan hal ini (misalnya bahasa Cina, Jepang, Thailand). Dalam bahasa Indonesia, selain tokenisasi sederhana diperlukan juga tokenisasi yang memisahkan kata-kata berdasarkan karakter lain seperti “/” dan “-“. 3.3.2
Stopword removal Stopword removal adalah pendekatan mendasar dalam preprocessing yang
menghilangkan kata-kata yang sering muncul (stopword). Fungsi utamanya adalah untuk mencegah hasil proses selanjutnya terpengaruh oleh stopword tersebut. Banyak diantara stopword tersebut tidak berguna dalam Information Retrival (IR) dan text mining karena kata-kata tersebut tidak membawa informasi (seperti ke, dari, dan, atau). Cara biasa untuk menentukan apa yang dianggap sebagai stopword adalah menggunakan stoplist. Stoplist merupakan kumpulan kata atau kamus yang berisi daftar stopword. Langkah penghilangan stopword ini adalah langkah yang sangat penting dan berguna (Srividhya dan Anitha, 2010). 3.3.3
Stemming Algoritma stemming adalah proses yang melakukan pemetaan varian
morfologi yang berbeda dari kata-kata ke dalam kata dasar/kata umum (stem). Stemming berguna pada banyak bidang komputasi linguistik dan information retrieval (Lovins, 1968). Dalam kasus bahasa Indonesia, sejauh ini hanya ada dua algoritma untuk melakukan proses stemming yaitu algoritma yang dikembangkan oleh Nazief dan Adriani serta algoritma yang dikembangkan oleh Tala. Algoritma Nazief dan Adriani dikembangkan dengan menggunakan pendekatan confix stripping dengan
26
disertai pemindaian pada kamus. Sedangkan stemming yang dikembangkan Tala menggunakan pendekatan yang berbasis aturan (rule-based). Pengembangan Algoritma Tala didasarkan pada kenyataan bahwa sumber daya seperti kamus besar digital untuk bahasa mahal karena kurangnya penelitian komputasi di bidang linguistik. Maka, ada kebutuhan untuk algoritma stemming tanpa keterlibatan kamus. Algoritma Tala sendiri dikembangkan dari algoritma Porter stemmer yang dimodifikasi untuk bahasa Indonesia. Algoritma Tala menghasilkan banyak kata yang tidak dipahami. Ini disebabkan oleh ambiguitas dalam aturan morfologi Bahasa Indonesia. Dalam beberapa kasus kesalahan tidak mempegaruhi kinerja, tetapi dalam kasus lain menurunkan kinerja (Tala, 2003). 3.3.4
Tala stemmer Kata
Hilangkan Partikel
Hilangkan Akhiran Kepunyaan
Hilangkan Awalan Pertama Gagal
Aturan terpenuhi
Hilangkan Awalan Kedua
Hilangkan Akhiran Aturan terpenuhi
Hilangkan Akhiran
Hilangkan Awalan Kedua
Kata Dasar Gambar 3.7 Skema Tala stemmer
Gagal
27
Algoritma Tala memproses awalan, akhiran, dan kombinasi keduanya dalam kata turunan. Walaupun dalam bahasa Indonesia terdapat sisipan, jumlah kata yang diturunkan menggunakan sisipan sangat sedikit. Karena hal tersebut dan juga demi penyederhanaan, sisipan akan diabaikan. Algoritma Porter stemmer dibangun berdasarkan ide tentang akhiran pada bahasa Inggris yaitu kebanyakan merupakan kombinasi dari akhiran yang lebih sederhana dan lebih kecil. Beberapa perubahan dilakukan pada algoritma Porter stemmer agar sesuai dengan Bahasa Indonesia. Perubahan dilakukan pada bagian kumpulan aturan dan penilaian kondisi. Karena algoritma Porter stemmer hanya dapat menangani akhiran, maka perlu penambahan agar dapat menangani awalan, akhiran, dan juga penyesuaian penulisan dalam kasus dimana terjadi perubahan karakter pertama kata dasar. Gambar 3.7 menunjukkan langkah-langkah proses pada algoritma Tala. Tabel 3.4 Daftar partikel Akhiran kah lah pun
Pengganti NULL NULL NULL
Penurunan kata dasar diawali dengan penghilangan imbuhan yang melekat pada kata. Imbuhan ini dapat berupa awalan, akhiran maupun kombinasi keduanya. Akhiran yang berupa partikel dan akhiran ganti kepunyaan akan dihapus lebih dulu dibandingkan awalan. Daftar partikel ditunjukkan pada Tabel 3.4 dan daftar akhiran ganti kepunyaan pada Tabel 3.5. Tabel 3.5 Daftar kata ganti kepunyaan Akhiran ku mu nya
Pengganti NULL NULL NULL
28
Setelah itu, proses akan dilanjutkan dengan penghilangan awalan pertama yang ditunjukkan pada Tabel 3.6. Langkah selanjutnya dilakukan dengan memperhatikan kombinasi awalan dan akhiran yang ilegal. Daftar kombinasi ini dapat dilihat pada Tabel 3.7. Tabel 3.6 Daftar awalan pertama Awalan meng meny men mem mem me peng peny pen pem di ter ke
Pengganti NULL s NULL p NULL NULL NULL s NULL p NULL NULL NULL
Tabel 3.7 Kombinasi ilegal Awalan ber di ke meng peng ter
Akhiran i an i|kan an i|kan an
Jika kombinasi awalan dan akhiran merupakan kombinasi ilegal, maka hanya awalan yang dihilangkan sedangkan akhiran tidak dihilangkan. Daftar akhiran dapat dilihat pada Tabel 3.8 dan awalan kedua pada Tabel 3.9. Pada penghapusan awalan juga diperhatikan karakter ganti yang disebabkan oleh penggunaan awalan. Awalan juga dapat terdiri dari dua awalan (awalan ganda). Daftar kombinasi awalan ganda dapat dilihat pada Tabel 3.10.
29
Tabel 3.8 Daftar akhiran Akhiran kan an i
Pengganti NULL NULL NULL
Kondisi awalan ∉ {ke, peng} awalan ∉ {di, meng, ter} V|K…c1c1, c1 ≠ s, c2 ≠ I, dan awalan ∉ {ber, ke, peng}
Tabel 3.9 Daftar awalan kedua Awalan ber bel be per pel pe
Pengganti NULL NULL NULL NULL NULL NULL
Tabel 3.10 Awalan ganda Awalan 1 meng di ter ke
Awalan 2 per ber
Dalam Bahasa Indonesia, unit terkecil dari suatu kata adalah suku kata. Suku kata paling sedikit terdiri dari satu huruf vokal. Desain implementasi algoritma Tala belum dapat mengenali seluruh suku kata. Ini disebabkan karena adanya dua huruf vokal yang dianggap satu suku kata yaitu ai, au, dan oi. Kombinasi dua huruf vokal (terutama ai, oi) tersebut dapat menjadi masalah, apalagi jika berada pada akhir sebuah kata. Ini disebabkan oleh sulitnya membedakannya dengan kata yang mengandung akhiran –i. Hal ini menyebabkan kombinasi huruf vokal ai/oi akan diperlakukan seperti kata turunan. Huruf terakhir (-i) akan dihapus pada hasil proses stemming. Kebanyakan kata dasar terdiri dari minimal dua suku kata. Inilah alasan kenapa kata yang akan diproses memiliki minimal dua suku kata.
30
3.3.5
Pembobotan Tahapan ini dilakukan dengan tujuan untuk memberikan suatu bobot pada
term yang terdapat pada suatu dokumen. Term adalah satu kata atau lebih yang dipilih langsung dari corpus dokumen asli dengan menggunakan metode termextraction. Fitur tingkat term, hanya terdiri dari kata-kata tertentu dan ekspresi yang ditemukan dalam dokumen asli (Feldman dan Sanger, 2007). Misalnya, jika dokumen berisi kalimat: “Presiden Indonesia mengalami perjalanan karir yang membawa beliau dari rumah sederhana hingga Istana Merdeka” Daftar term untuk mewakili dokumen dapat mencakup bentuk kata tunggal seperti “Indonesia”, “perjalanan”, “karir”, dan “rumah” lalu untuk yang lebih dari satu kata seperti “Presiden Indonesia”, “rumah sederhana”, and “Istana Merdeka”. Dalam pengkategorian teks dan aplikasi lain di information retrieval maupun machine learning, pembobotan term biasanya ditangani melalui metode yang diambil dari metode pencarian teks, yaitu yang tidak melibatkan tahap belajar (Debole dan Sebastiani, 2003). Ada tiga asumsi monoton yang muncul di hampir semua metode pembobotan dapat dalam satu atau bentuk lain yaitu (Zobel dan Moffat, 1998): a. Term yang langka tidak kalah penting daripada term yang sering muncul (asumsi IDF). b. Kemunculan berkali-kali dari term pada dokumen tidak kalah penting daripada kemunculan tunggal (asumsi TF). c. Untuk pencocokan term dengan jumlah pencocokan yang sama, dokumen panjang tidak lebih penting daripada dokumen pendek (asumsi normalisasi). Bobot diperlukan untuk menentukan apakah term tersebut penting atau tidak. Bobot yang diberikan terhadap sebuah term bergantung kepada metode yang digunakan untuk membobotinya.
31
3.4 Cosine Similarity Pendekatan cosine similarity sering digunakan untuk mengetahui kedekatan antara dokumen teks. Perhitungan cosine similarity dimulai dengan menghitung dot product. Dot product merupakan perhitungan sederhana untuk setiap komponen dari kedua vektor. Vektor merupakan representasi dari masingmasing dokumen dengan jumlah term pada masing-masing dokumen sebagai dimensi dari vektor (Manning, dkk., 2009). Vektor ditunjukkan oleh notasi (3.1) dan (3.2). Hasil dot product bukan berupa vektor tetapi berupa skalar. Persamaan (3.3) merupakan perhitungan dot product dimana n merupakan dimensi dari vector (Axler, 1997). 𝑎 = 𝑎1 , 𝑎2 , 𝑎3 , … , 𝑎𝑛
(3.1)
𝑏 = 𝑏1 , 𝑏2 , 𝑏3 , … , 𝑏𝑛
(3.2)
𝑛
𝑎∙𝑏 =
𝑎𝑖 𝑏𝑖 = 𝑎1 𝑏1 + 𝑎2 𝑏2 + ⋯ + 𝑎𝑛 𝑏𝑛 𝑖=1
(3.3) 𝑎𝑛 dan 𝑏𝑛 merupakan komponen dari vektor (bobot term masing-masing dokumen) dan n merupakan dimensi dari vektor. Cosine similarity merupakan perhitungan yang mengukur nilai cosine dari sudut antara dua vektor (atau dua dokumen dalam vector space). Cosine similarity dapat dilihat sebagai perbandingan antara dokumen karena tidak hanya mempertimbangkan besarnya masing-masing jumlah kata (bobot) dari setiap dokumen, tetapi sudut antara dokumen. Persamaan (3.4) dan (3.5) adalah notasi dari metode cosine similarity dimana
a
merupakan Euclidean norm dari vektor a dan
b
merupakan
Euclidean norm vektor b (Han, dkk., 2011). a∙𝑏 = a cos 𝜃 =
b cos θ 𝑎 ∙𝑏 𝑎
𝑏
(3.4) (3.5)
32
Dari notasi (3.5) dapat dibentuk persamaan matematika yang ditunjukkan oleh persamaan (3.6) (Lops, dkk., 2011). 𝑆𝑖𝑚𝑖𝑙𝑎𝑟𝑖𝑡𝑦 𝑥, 𝑦 =
𝑛 𝑖=1 𝑎𝑖 𝑏𝑖 𝑛 2 𝑖=1 𝑎𝑖
∙
2 𝑛 𝑖=1 𝑏𝑖
(3.6) Dimana: ai : term ke-i yang terdapat pada dokumen a. bi : term ke-i yang terdapat pada dokumen b. 3.5 Evaluasi Recommendation System 3.5.1
Precision Precision bersama recall merupakan salah satu pengujian dasar dan paling
sering digunakan dalam penentuan efektifitas information retrival system maupun recommendation system. True positive (tp) pada information retrival merupakan item relevan yang dihasilkan oleh sistem. Sedangkan false positive (fp) merupakan semua item yang dihasilkan oleh sistem. Sehingga dalam information retrival, precision dihitung dengan persamaan (3.7) (Manning, dkk., 2009). 𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 =
𝑡𝑝 𝑟𝑒𝑙𝑒𝑣𝑎𝑛𝑡 𝑖𝑡𝑒𝑚 𝑟𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑑 = 𝑡𝑝 + 𝑓𝑝 𝑟𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑑 𝑖𝑡𝑒𝑚 (3.7)
Istilah positive dan negative mengacu pada prediksi yang dilakukan oleh sistem. Sedangkan istilah true dan false mengacu pada prediksi yang dilakukan oleh pihak luar atau pihak yang melakukan observasi. Pembagian kondisi tersebut dapat dilihat pada Tabel 3.11 (Manning, dkk., 2009). Tabel 3.11 Pembagian kondisi hasil yang memungkinkan Retrieved Not retrieved
Relevant True positive (tp) False negative (fn)
Nonrelevant False positive (fp) True negative (tn)
33
3.5.2
Recall Recall digunakan sebagai ukuran dokumen yang relevan yang dihasilkan
oleh sistem. False negative (fn) merupakan semua item relevan yang tidak dihasilkan oleh sistem. Dalam evaluasi information retrival system, recall dihitung dengan persamaan (3.8) (Manning, dkk., 2009). 𝑅𝑒𝑐𝑎𝑙𝑙 =
𝑡𝑝 𝑟𝑒𝑙𝑒𝑣𝑎𝑛𝑡 𝑖𝑡𝑒𝑚 𝑟𝑒𝑡𝑟𝑖𝑒𝑣𝑒𝑑 = 𝑡𝑝 + 𝑓𝑛 𝑟𝑒𝑙𝑒𝑣𝑎𝑛𝑡 𝑖𝑡𝑒𝑚 (3.8)
3.5.3
F-Measure F-measure merupakan nilai tunggal hasil kombinasi antara nilai precision
dan nilai recall. F-measure dapat digunakan untuk mengukur kinerja dari recommendation system ataupun information retrival system. Karena merupakan rata-rata harmonis dari precision dan recall, F-measure dapat memberikan penilaian kinerja yang lebih seimbang. Persamaan (3.9) merupakan persamaan untuk menghitung F-measure (Jannach, dkk., 2010). 𝐹𝑚𝑒𝑎𝑠𝑢𝑟𝑒 = 2 ∙
𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 ∙ 𝑟𝑒𝑐𝑎𝑙𝑙 𝑝𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 + 𝑟𝑒𝑐𝑎𝑙𝑙 (3.9)
3.5.4
Mean average precision Nilai mean average precision (MAP) merupakan nilai rata-rata dari
average precision. Average precision merupakan nilai yang didapatkan dari setiap nilai precision item relevan yang dihasilkan dan menggunakan nilai 0 untuk item relevan yang tidak dihasilkan oleh sistem. Nilai precision untuk average precision dihitung dengan memperhatikan urutan item yang diberikan oleh sistem, sehingga nilai precision diberikan untuk setiap item yang dihasilkan oleh sistem. Persamaan (3.10) merupakan persamaan untuk menghitung nilai mean average precision dalam information retrival (Manning, dkk., 2009).
34
1 𝑀𝐴𝑃 𝑄 = 𝑄
𝑄
𝑗 =1
1 𝑚𝑗
𝑚𝑗
𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 𝑅𝑗𝑘 𝑘=1
(3.10) Dimana: Q
: jumlah query uji
R
: item relevan yang dihasilkan oleh sistem
m
: jumlah item relevan yang dihasilkan dari query
Dalam penelitian ini, query (Q) merupakan item uji yang digunakan dalam pengujian.
BAB IV ANALISIS DAN RANCANGAN SISTEM 4.1 Gambaran Umum Sistem Hybrid recommendation system yang dibangun menghasilkan rekomendasi dokumen. Rekomendasi dokumen merupakan dokumen-dokumen yang saling terkait atau terasosiasi dengan dokumen yang dibutuhkan oleh pengguna. Untuk mencari dokumen terasosiasi dapat digunakan penggalian frequent itemset. Keterkaitan dokumen dapat dicari dengan perhitungan kedekatan dokumen. Perhitungan kedekatan dokumen dapat memanfaatkan perhitungan cosine similarity. Proses yang digunakan pada keyword extraction system dan perbandingan keyword menggunakan penndekatan berbasis aturan. Gambaran umum proses pada hybrid recommendation system dideskripsikan pada Gambar 4.1. Pemilihan Dokumen
teks
Data Transaksi
ID Dokumen
User Data Transaksi Terseleksi
Penggalian Frequent Itemset
Tokenisasi Informasi Dokumen
Dokumen Frequent
Basis Data
Stopword Removal Keyword Dokumen Terseleksi
Stemming
Pembobotan
Keyword
Keyword Dokumen Acuan
Cosine Similarity
Rekomendasi
Gambar 4.1 Gambaran umum hybrid recommendation system Dengan penggunaan algoritma frequent itemset dan perhitungan cosine similarity pada perbandingan keyword, sistem rekomendasi dibentuk dalam beberapa proses. Proses pemilihan dokumen digunakan sebagai proses untuk pengambilan data transaksi. Proses pemilihan dokumen adalah saat pengguna melakukan pemilihan dokumen yang disajikan oleh sistem. Dokumen yang
35
36
disajikan oleh sistem dapat berupa dokumen hasil pencarian dan dokumen rekomendasi. Dokumen teks diproses pada keyword extraction system untuk memperoleh keyword dokumen. Dokumen pilihan pengguna digunakan sebagai dokumen acuan dalam penggalian frequent itemset maupun perbandingan keyword. Penggalian frequent itemset dilakukan untuk mendapatkan frequent document. Keyword extraction system melakukan ekstraksi keyword untuk dokumen yang dimasukkan pada sistem sehingga setiap dokumen akan memiliki daftar keyword hasil ekstraksi. Data transaksi dibentuk saat proses pemilihan dokumen yang dilakukan oleh pengguna. Proses pemilihan adalah saat pengguna melakukan pemilihan dokumen yang ada pada daftar dokumen hasil pencarian atau hasil rekomendasi. Setiap sesi merupakan satu data transaksi. Dalam satu data transasi, terdapat deret item yang merupakan id dari dokumen. Deret item ini merupakan dokumendokumen yang dipilih pada sesi penggunaan sistem. Sesi yang digunakan merupakan sesi default pada browser. Dengan demikian, walaupun pengguna sama tetapi penggunaan sistem dilakukan pada sesi yang berbeda, maka data pemilihan dokumen tersebut akan dipisahkan. Hal ini dilakukan untuk mengantisipasi proses pemilihan dokumen dengan konten yang berbeda walaupun penggunanya sama. Penggunaan asumsi tersebut mengakibatkan data identitas pengguna dapat diabaikan. Selain menjadi data transaksi, dokumen pilihan pengguna juga menjadi dokumen acuan untuk menentukan daftar data transaksi terseleksi yang digunakan pada proses penggalian frequent itemset. Keyword dokumen frequent lalu dibandingkan dengan keyword dokumen acuan menggunakan metode cosine similarity. Nilai cosine similarity digunakan untuk
penentuan
rekomendasi
dokumen.
Dokumen
pembanding
akan
direkomendasikan kepada pengguna apabila nilai similaritas memenuhi ambang batas. Hasil rekomendasi berupa daftar dokumen yang memenuhi ambang batas yang ditentukan oleh pengguna.
37
Untuk melakukan proses-proses tersebut, sistem memerlukan 3 ambang batas yaitu minimum similarity, minimum support dan jumlah rekomendasi. Minimum similarity digunakan untuk menentukan ambang batas similaritas minimal antara dokumen yang akan direkomendasikan. Minimum support diperlukan pada penggalian frequent itemset untuk menentukan minimal kemunculan setiap itemset. Untuk penentuan jumlah rekomendasi yang dihasilkan oleh sistem, diperlukan ambang batas jumlah rekomendasi. Pengaturan ambang batas dilakukan oleh administrator sistem. Selain pengaturan ambang batas, administrator juga melakukan manajemen data dokumen dan data stopword yang ada pada sistem. 4.2 Arsitektur Sistem Pembangunan recommendation system terbagi menjadi beberapa bagian proses. Bagian-bagian proses tersebut ditunjukkan oleh Gambar 4.2. Proses terdiri dari 3 bagian utama yaitu penggalian pencarian rekomendasi, tranformasi data, dan ekstraksi keyword. Pencarian rekomendasi dilakukan dengan penggalian itemset dan pembandingan keyword antara dokumen menggunakan metode cosine similarity. Penggalian frequent itemset terbagi menjadi 3 bagian yaitu penggalian frequent item, pembentukan FP-Tree, dan pembentukan conditional FP-Tree. Penggalian frequent item merupakan pencarian item tunggal yang melebihi minimum support. Proses ini juga disebut penggalian 1-itemset. Pembentukan conditional FP-Tree merupakan proses dimana frequent itemset ditentukan. Proses perbandingan menggunkan cosine similarity menghasilkan nilai similaritas antara dokumen acuan dan dokumen pembanding. Proses transformasi data merupakan proses dimana data umpan balik pengguna yang berupa data pemilihan dokumen diubah menjadi data transaksi. Keyword extraction terdiri dari tokenisasi, stopword removal, stemming, dan pembobotan. Pada tokenisasi dilakukan proses pemecahan deret kata dan penghilangan karakter selain huruf dan angka. Tokenisasi yang digunakan adalah tokenisasi dengan pemisah kata berupa karakter spasi. Daftar kata yang dihasilkan tokenisasi akan diseleksi pada stopword removal. Stopword removal merupakan
38
proses untuk menghilangkan kata yang dianggap tidak penting. Daftar kata yang tidak mengandung stopword lalu diproses pada stemming. Proses stemming merupakan proses untuk mengubah kata turunan menjadi kata dasar. Daftar kata dasar yang didapatkan pada stemming akan diberikan bobot dengan skema term frequency. Skema term frequency memberikan bobot dengan menghitung jumlah kemunculan kata pada dokumen. Kata dasar beserta bobot yang didapatkan disimpan pada basis data. Hybrid Recommendation System
Frequent Itemset Mining
Rekomendasi
Transformasi Data
Cosine Similarity
Tokenisasi
Pembobotan
Stemming Frequent Item Search
Conditional FPTree
Keyword Extraction
Stopword Removal
FP-Tree
Gambar 4.2 Arsitektur hybrid recommendation system Penggalian frequent itemset menghasilkan daftar frequent dokumen. Dokumen pilihan juga menjadi dokumen acuan yang akan dibandingkan dengan dokumen terseleksi. Dokumen terseleksi untuk perbandingan merupakan frequent dokument dan atau dokumen hasil pencarian. Keyword dokumen acuan dan keyword dokumen terseleksi dibandingkan dengan menggunakan cosine similarity. Dokumen hasil pencarian akan digunakan apabila penggalian frequent itemset tidak menghasilkan dokumen frequent atau dokumen frequent yang ditemukan tidak dapat memenuhi kebutuhan jumlah rekomendasi. 4.2.1 Keyword extraction system Implementasi keyword extraction system menggunakan pendekatan tata bahasa berbasis struktur sintaksis yaitu dengan melakukan tokenisasi, stopword removal, stemming, dan pembobotan kata. Proses stemming menggunakan algoritma yang dikembangkan oleh Tala. Hasil keyword extraction system
39
merupakan daftar term disertai dengan term frequency untuk masing-masing dokumen pada sistem. Tokenisasi Untuk melakukan ekstraksi dokumen ke dalam bentuk daftar kata, diperlukan proses tokenisasi. Alur proses tokenisasi ditunjukkan oleh Gambar 4.3. Start
dokumen PDF
teks = convert(dokumen PDF)
kata = pecah(teks)
i=0
hilangkan simbol(kata [i])
jumlah(kata [i]) < 2
ya
Hapus(kata [i])
ya tidak inc i
i < jumlah(kata)
tidak kata
End
Gambar 4.3 Flowchart tokenisasi
40
Sebelum melakukan tokenisasi, input yang berupa dokumen pdf terlebih dahulu dikonversi menjadi dokumen txt. Proses konversi ini dibutuhkan karena pembacaan setiap baris text menggunakan file operation PHP yang dapat membaca file txt. Baris-baris teks yang didapatkan dari dokumen txt lalu dipecah menjadi daftar kata berdasarkan karakter spasi dan disimpan pada variabel kata. Proses selanjutnya adalah penghapusan simbol-simbol yang ada pada setiap kata. Pada tahap ini juga dilakukan penghapusan kata yang terdiri dari satu karakter. Proses ini dilakukan karena kata yang mengandung satu karakter tidak mengandung informasi penting. Jumlah karakter kata ke-i dihitung pada fungsi jumlah(kata[i]). Proses ini diulang sebanyak jumlah(kata). Jumlah(kata) merupakan jumlah kata yang didapatkan pada proses pemecahan berdasarkan karakter spasi. Output dari proses tokenisasi ini merupakan kumpulan kata yang sudah bersih dari simbol-simbol tidak diperlukan. Stopword removal Daftar kata hasil tokenisasi tidak semua merupakan kata-kata yang dianggap penting. Proses stopword removal melakukan penghapusan kata-kata yang dianggap tidak penting tersebut. Kata dan stopword sebagai input proses berbentuk daftar kata. Daftar kata tidak penting disimpan dalam variabel stopword. Contoh dari kata yang dianggap tidak penting adalah kata penghubung. Untuk melakukan stopword removal, diperlukan stoplist (daftar stopword) yang tersimpan pada basis data. Stoplist merupakan daftar kata yang dibuat oleh pengguna. Setiap kata yang terdapat pada stoplist akan dihapus dari daftar kata, sehingga kata yang tidak mengandung informasi dapat diminimalkan. Kata output dari proses stopword removal berbentuk daftar kata. Daftar kata yang telah memasuki proses stopword removal selanjutnya akan masuk ke proses stemming. Alur proses stopword removal dapat dilihat pada Gambar 4.4.
41
Start
kata stopword
i=0
kata [i] adalah stopword
ya
Hapus(kata [i])
tidak ya
inc i
i < jumlah(kata)
tidak kata
End
Gambar 4.4 Flowchart stopword removal Tala stemming Stemming dilakukan untuk mempermudah pemberian bobot dengan mengurangi jumlah kata turunan. Gambar 4.5 memperlihatkan alur proses dari Tala stemming. Untuk melakukan proses stemming diperlukan kata yang telah melalui proses tokenisasi dan stopword removal. Proses stemming dilakukan dalam beberapa tahap. Tahap pertama adalah menghilangkan partikel yang melekat pada kata. Tahap kedua yaitu menghilangkan kata ganti kepunyaan. Setelah melalui dua tahap tersebut, selanjutnya pada tahap ketiga akan diperiksa apakah pada kata melekat awalan pertama. Jika terdapat awalan pertama, maka awalan tersebut akan dihilangkan. Selanjutnya kata akan diperiksa apakah mengandung akhiran dan apakah kondisi pada sub bab 3.3.4 dipenuhi.
42
Pemeriksaan ini dilakukan untuk menentukan apakah diperlukan penghilangan akhiran dan awalan kedua yang melekat pada kata. Start
kata
i=0
hilangkan partikel (kata [i])
hilangkan kata ganti kepunyaan (kata [i])
ya awalan pertama kata [i] ≠ null
ya
hilangkan awalan pertama (kata [i])
tidak akhiran kata [i] ≠ null & kondisi terpenuhi
hilangkan awalan kedua (kata [i])
hilangkan akhiran (kata [i]) tidak i < jumlah(kata)
ya
inc i hilangkan akhiran (kata [i])
tidak hilangkan awalan kedua (kata [i]) kata dasar
End
Gambar 4.5 Flowchart Tala stemmer Jika pada tahap ketiga tidak ditemukan awalan pertama, maka proses akan dilanjutkan ke penghilangan awalan kedua dan selanjutnya penghilangan akhiran kata. Untuk daftar partikel, kata ganti kepunyaan, awalan pertama, awalan kedua, akhiran, dan juga kondisi yang mungkin terjadi dapat dilihat pada sub bab 3.3.4. Setelah melewati proses steamming maka akan diperoleh kata dasar.
43
Term frequency Pembobotan diberikan berdasarkan skema term frequency. Kata-kata dasar yang didapatkan pada proses stemming diberikan bobot untuk menentukan apakah kata tersebut penting atau tidak. Setiap kata dasar akan diberikan bobot berdasarkan jumlah kemunculan kata tersebut dalam suatu dokumen. Term merupakan kata yang telah melalui proses tokenisasi stopword, removal, dan stemming.. Daftar term merupakan daftar kata dasar yang telah berisi bobot dari kata tersebut. Daftar term akan berbentuk „kata [jumlah]‟. Saat pemindaian seluruh daftar kata dasar, komponen jumlah akan ditambahkan jika kata dasar tersebut kembali ditemukan. Apabila kata dasar tidak ditemukan, maka kata dasar akan ditambahkan ke dalam daftar term. Alur proses pembobotan ditunjukkan oleh Gambar 4.6. Start
kata dasar
i=0
kata [i] ada pada daftar term
tidak
tambah kata [i] ke daftar term
ya inc term [kata [i]] [jumlah] ya inc i
i < jumlah (kata dasar)
tidak
term
End
Gambar 4.6 Flowchart pembobotan
44
Daftar term yang didapatkan beserta jumlah kemunculannya akan diproses pada pencarian similaritas dokumen. Daftar term yang telah memiliki bobot juga disebut keyword. 4.2.2 Penggalian frequent itemset Fungsi penggalian frequent itemset adalah mencari dokumen-dokumen yang terasosiasi dengan dokumen acuan. Penggalian frequent itemset mengolah data transaksi yang dimiliki oleh sistem. Salah satu algoritma yang dapat digunakan untuk melakukan penggalian frequent itemset adalah algoritma FPGrowth. Algoritma FP-Growth dikenal cepat dan juga populer dalam penggalian frequent itemset. Data transaksi pada sistem merupakan hasil perekaman data pemilihan dokumen. Setiap sesi penggunaan sistem akan merekam data pemilihan dokumen sebagai sebuah data transaksi. Dalam setiap data transaksi terdapat deret item yang merupakan id dari dokumen yang dipilih oleh pengguna. Dalam algoritma ini terdapat beberapa tahap yang dilakukan yaitu pencarian frequent item, pembentukan FP-Tree, penggalian frequent itemset dengan menggunakan conditional FP-Tree. Data transaksi yang digunakan adalah data transaksi yang mengandung dokumen acuan. Sebagai contoh data transaksi ditunjukkan oleh Tabel 4.1. Tabel 4.1 Contoh data transaksi No 1 2 3 4 5 6 7 8 9 10
TID 1 13 14 20 1 2 3 4 5 19 20 236 178 1 3 4 9 10 1 2 3 4 11 17 18 2 4 12 2 4 15 16 4 14
Misalkan id dokumen yang dipilih adalah 1 maka data transaksi yang terseleksi ditunjukkan oleh Tabel 4.2.
45
Tabel 4.2 Seleksi data transaksi No 1 2 4 5 6 10
TID 1 13 14 20 1 2 3 4 5 19 20 178 1 3 4 9 10 1 2 3 4 11 17 18 14
Pencarian frequent item Data transaksi merupakan kebutuhan utama untuk dapat melakukan proses penggalian frequent itemset. Data transaksi merupakan data yang diolah dari proses pemilihan yang dilakukan pengguna sistem. Frequent item merupakan item tunggal yang memiliki jumlah kemunculan lebih dari atau sama dengan minimum support yang telah ditentukan. Pada tahap pencarian frequent item, semua itemset dalam data transaksi terseleksi akan dipindai untuk menemukan frequent item. Itemset berbentuk deretan item yang terlibat dalam suatu transaksi. Itemset akan dipecah menjadi item-item lalu dihitung jumlah kemunculan item tersebut. Hasil perhitungan jumlah kemunculan item dengan data transaksi pada Tabel 4.2 ditunjukkan oleh Tabel 4.3. Tabel 4.3 Jumlah kemunculan item ID Item 1 13 14 20 2 3 4 5
Jumlah Kemunculan 6 1 1 2 2 3 4 1
ID Item 19 7 8 9 10 11 17 18
Jumlah Kemunculan 1 1 1 1 1 1 1 1
46
Variabel id pada Gambar 4.7 merupakan variabel untuk menyimpan itemitem hasil pemecahan. Jika item berjumlah lebih dari atau sama dengan minimum support, maka item tersebut akan tetap berada pada daftar frequent item. Start
data transaksi minimum support
id = pecah (data transaksi [i])
i=0
j=0
item [id [j]] ≠ null
ya
item [id [j]] = 0
tidak ya inc item [id [j]] ya k=0 ya
inc j
jumlah (item [k]) < minimum support
j < jumlah (item)
ya
Hapus (item [k])
tidak
ya tidak
tidak inc i
inc k
i < jumlah (data transaksi)
k < jumlah (item)
urut item berdasarkan jumlah
tidak
frequent item
End
Gambar 4.7 Flowchart pencarian frequent item
47
Sebaliknya, jika kurang dari minimum support, maka item akan dihapus dari daftar frequent item. Sebagai contoh, dengan penggunaan minimum support 40% maka jumlah minimal kemunculan setiap item adalah sebagai berikut: Jumlah minimal kemunculan = jumlah transaksi dipilih × 𝑚𝑖𝑛𝑖𝑚𝑢𝑚 𝑠𝑢𝑝𝑝𝑜𝑟𝑡 Jumlah minimal kemunculan = 6 ×
40 100
Jumlah minimal kemunculan = 2,4
Jumlah minimal kemunculan akan dibulatkan kebawah sehingga, jumlah minimal kemunculan menjadi 2. Selain menyimpan frequent item, daftar frequent item juga menyimpan jumlah kemunculan item tersebut. Hal ini diperlukan karena item pada daftar akan diurutkan berdasarkan jumlah kemunculan. Flowchart dari proses ini ditunjukkan oleh Gambar 4.7. Hasil proses pencarian frequent item Tabel 4.3 serta hasil pengurutannya ditunjukkan pada Tabel 4.4. Tabel 4.4 Urutan frequent item ID Item 1 4 3 20 2
Jumlah Kemunculan 6 4 3 2 2
FP-Tree FP-Tree merupakan skema tree yang digunakan pada algoritma FPGrowth. Proses pembentukan FP-Tree diawali dengan melakukan seleksi terhadap data transaksi. Dari itemset pada masing-masing data transaksi, item yang tidak terdapat pada frequent item akan diabaikan. Root pada tree merupakan id dokumen yang menjadi acuan rekomendasi. Item acuan merupakan id dokumen yang dipilih oleh pengguna. Flowchart pembentukan FP-Tree ditunjukkan pada Gambar 4.8. Contoh pada sub bab 4.2.2 menggunakan id dokumen 1 sebagai id
48
dokumen pilihan sehingga, data transaksi yang telah diurutkan dan diseleksi ditunjukkan oleh Tabel 4.5. Start
data transaksi frequent item id dokumen id transaksi = pecah(data transaksi [i])
seleksi data transaksi urut data transaksi
i=0
root = bentuk root (id dokumen)
j=0
id transaksi [j] = id dokumen
ya
tidak
node child [id transaksi [k]] ≠ null
ya
ya
node = root
node = child [id transaksi [k]]
tidak
node child [id transaksi [k]] = bentuk child (id transaksi [k])
inc support node
ya
inc j
j < jumlah (id transaksi)
prefix path = urut child (root)
tidak inc i
tidak prefix path
i < jumlah (data transaksi)
End
Gambar 4.8 Flowchart pembentukan FP-Tree Tabel 4.5 Data transaksi terurut dan terseleksi No 1 2 4 5 6 10
TID 1 20 1 4 3 20 2 1 143 1432 14
49
Selain membentuk FP-Tree, proses ini juga membentuk prefix path yaitu penunjuk alamat node pertama setiap frequent item pada FP-Tree. FP-Tree beserta prefix path yang dihasilkan oleh proses ini ditunjukkan pada Gambar 4.9. ID : 1
ID : 1
ID : 4
ID : 4
ID : 3
ID : 3
ID : 20
ID : 20
ID : 20 ID : 2
ID : 2
ID : 2
Gambar 4.9 FP-Tree dan Prefix Path Conditional FP-Tree Algoritma FP-Growth diakhiri pada proses penggalian frequent itemset. Dengan contoh pada subbab 4.2.2, maka frequent itemset yang dihasilkan ditunjukkan oleh Tabel 4.6. Tabel 4.6 Hasil frequent itemset No 1 2 3 4 5 6 7
Frequent Itemset 21 321 4321 421 20 1 31 41
Gambar 4.10 menunjukkan alur proses penggalian frequent itemset. Pembentukan
conditional
FP-Tree
merupakan
proses
untuk
melakukan
penggalian frequent itemset. Conditional FP-Tree merupakan pecahan dari FP-
50
Tree sesuai dengan item yang akan digali. Hasil proses yang berupa frequent itemset akan diurutkan berdasarkan jumlah kemunculan dari yang paling sering muncul ke yang paling jarang. Start
prefix path
i = jumlah (prefix path – 1)
node = prefix path [i]
node [support] ≥ minimum support
ya ya
frequent itemset = conditional fp-tree [node]
tidak
frequent itemset = node [label]
dec i
i≥0
tidak frequent itemset
End
Gambar 4.10 Flowchart penggalian frequent itemset 4.2.3 Cosine similarity Untuk membandingkan similaritas antara dokumen dilakukan proses perhitungan dengan pendekatan cosine similarity. Proses cosine similarity
51
melakukan perbandingan dua dokumen. Term dokumen yang dibandingkan beserta bobotnya akan diambil untuk melakukan perhitungan similaritas. Perhitungan cosine dapat dilihat pada sub bab 3.4. Gambar 4.11 merupakan flowchart dari perhitungan cosine similarity. Input proses cosine similarity merupakan daftar term dokumen A dan daftar term dokumen B. Start
term A term B
i=0
ya
term B [term A [i]] [TF] ≠ null
jumlah A = sqrt(sum(term A [TF])2)
ya
jumlah B = sqrt(sum(term B [TF])2)
dot = dot + (term A [i] [TF] * term B [term A [i]] [TF])
similarity = (dot / (jumlah A * jumlah B)) tidak
inc i
similarity
End
i < jumlah (term A)
Gambar 4.11 Flowchart cosine similarity 4.2.4 Penentuan rekomendasi Proses penentuan rekomendasi merupakan proses terakhir dapam pencarian
rekomendasi.
Penentuan
rekomendasi
dilakukan
dengan
membandingkan kemiripan keyword antara dokumen dengan menggunakan perhitungan cosine similarity. Proses penentuan rekomendasi terbagi atas dua tahap. Tahap pertama merupakan tahap perbandingan dokumen acuan terhadap dokumen-dokumen yang ada pada daftar frequent itemset. Dokumen-dokumen yang ada pada daftar frequent itemset disebut sebagai dokumen frequent.
52
Dokumen acuan merupakan dokumen yang sedang dipilih oleh pengguna sistem. Proses ini ditunjukkan oleh Gambar 4.12. Start
frequent itemset (fi) terrm dokumen id dokumen minimum rekomendasi (mr) minimum similarity
i=0
ya
fi ≠ null
tidak
Dok B = pilih dokumen jumlah (rekomendasi) < mr
tidak
Dok B ≠ null
ya cosine = (term[id dokumen],term[dok B])
ya cosine = (term[id dokumen],term[dok B]) cosine > minimum similarity
ya
rekomendasi = fi[i] ya cosine > minimal similarity
tidak
ya
rekomendasi = dok B ya
inc i
tidak tidak jumlah (rekomendasi) < mr
i < jumlah (fi) tidak
tidak
rekomendasi
End
Gambar 4.12 Flowchart penentuan rekomendasi Tahap kedua merupakan tahap perbandingan dokumen acuan terhadap dokumen-dokumen hasil pencarian. Perbandingan dokumen acuan dengan dokumen lain (Dok B) tanpa memperhatikan frequent itemset akan dilakukan apabila frequent itemset tidak ditemukan atau jumlah item pada frequent itemset yang memiliki similarity lebih dari minimum similarity tidak dapat memenuhi jumlah minimal rekomendasi yang ditentukan. Pemilihan daftar dokumen lain tersebut dilakukan dengan mencocokkan kata kunci pencarian yang diberikan pengguna terhadap judul atau abstrak dokumen. Dokumen akan direkomendasikan
53
apabila hasil cosine similarity melebihi ambang batas yang ditentukan. Apabila jumlah rekomendasi telah memenuhi ketentuan atau rekomendasi tidak dapat ditemukan, proses perbandingan dokumen akan dihentikan. 4.3 Basis Data Data yang digunakan dalam sistem adalah data dokumen, data transaksi, ambang batas rekomendasi dan juga daftar stopword. Selain itu dibutuhkan juga administrator untuk melakukan manajemen data yang ada. Maka dari itu, basis data yang dibutuhkan adalah administrator, traksaksi, dokumen, ambang batas, stoplist, dan dokumen term. 4.3.1 Administrator Administrator dibutuhkan untuk membatasi pengguna yang dapat melakukan pengubahan stoplist beserta ambang batas yang digunakan oleh sistem. Tabel administrator menyimpan username dan password sebagai autentifikasi pengguna. Tabel 4.7 merupakan rancangan tabel administrator. Tabel 4.7 Rancangan tabel administrator Field id username password
Tipe Integer (auto_increment) Varchar (20) Varchar (100)
Keterangan Primary Key Primary Key
4.3.2 Transaksi Rancangan tabel transaksi ditunjukkan oleh Tabel 4.8. History pemilihan dokumen yang dilakukan pengguna sistem akan diolah sebagai data transaksi yang digunakan dalam penggalian frequent itemset. Tabel 4.8 Rancangan tabek transaksi Field id tid
Tipe Integer (auto_increment) Varchar (200)
Keterangan Primary Key
54
Tabel transaksi menyimpan data pemilihan dokumen pada field tid dengan memisahkan setiap data pemilihan menggunakan spasi yaitu dalam bentuk „id_1 id_2 id_3 dst‟. 4.3.3 Dokumen Tabel dokumen hanya menyimpan keterangan yang dibutuhkan oleh sistem yaitu judul, abstrak, dan path dokumen. Path dokumen adalah nama dokumen hasil hashing nama asli dokumen dengan algoritma MD5. Hashing dilakukan untuk menghilangkan simbol-simbol selain angka dan huruf pada nama dokumen. Simbol tersebut dihilangkan agar aplikasi pdftotxt yang melakukan konversi dokumen pdf ke dokumen txt dapat mengidentifikasi dokumen pdf. Rancangan tabel dokumen ditunjukkan oleh Tabel 4.9. Tabel 4.9 Rancangan tabel dokumen Field id nama judul abstrak path
Tipe Integer (auto_increment) Varchar (100) Varchar (200) Teks Varchar (100)
Keterangan Primary Key
4.3.4 Ambang batas Tabel ambang batas yang rancangannya ditunjukkan oleh Tabel 4.10, merupakan tabel yang menyimpan ambang batas yang digunakan oleh sistem. Ambang batas ini berupa minimum support yang digunakan dalam penggalian frequent itemset, minimum similarity yang digunakan untuk perbandingan kedekatan keyword antara dokumen serta jumlah rekomendasi untuk menentukan jumlah rekomendasi yang dihasilkan oleh sistem. Tabel 4.10 Rancangan tabel ambang batas Field Tipe minimum_support Integer (11) jumlah_rekomendasi Integer (11) minimum_similarity Integer (11)
Keterangan
55
4.3.5 Stoplist Tabel stoplist berisi daftar stopword yang digunakan oleh proses keyword extraction system pada tahap stopword removal. Stopword menentukan jumlah term yang dihasilkan oleh keyword extraction system karena stopword digunakan pada proses stopword removal yaitu penghilangan kata yang tidak membawa informasi. Rancangan tabel ini ditunjukkan oleh Tabel 4.11. Tabel 4.11 Rancangan tabel stoplist Field stopword
Tipe Varchar (20)
Keterangan
4.3.6 Dokumen Term Untuk efisiensi waktu pencarian rekomendasi, maka term beserta term frequency akan disimpan dalam tabel dokumen term. Efisiensi dapat dilakukan karena saat perbandingan similaritas keyword, tidak dibutuhkan lagi ekstraksi term dari dokumen yang dicari similaritasnya. Sistem hanya akan mengambil term serta term frequency tersebut dari tabel dokumen term. Term masing-masing dokumen yang disimpan dalam tabel ini adalah kumpulan term-term yang diekstraksi dari dokumen. Jadi satu record memuat kumpulan term dan term frequency yang merepresentasikan satu dokumen. Rancagan tabel ini ditunjukkan oleh Tabel 4.12. Tabel 4.12 Rancangan tabel dokumen term Field id_dokumen
Tipe Integer (11)
term
Text
Keterangan Primary Key Foreign Key (dokumen.id)
4.4 Perancangan Antar Muka Rekomendasi ditampilkan pada halaman rekomendasi dokumen berbentuk daftar vertikal. Dalam halaman ini juga ditampilkan abstrak dan judul dokumen yang dipilih sebelumnya oleh pengguna. Tombol download juga disediakan pada
56
halaman ini jika pengguna ingin melakukan pengunduhan dokumen tersebut. Rancangan halaman ini ditunjukkan oleh Gambar 4.13.
< header > < menu > Rekomendasi Dokumen Judul Abstrak
Download Rekomendasi 1 Rekomendasi 2 Rekomendasi 3 dst..
< footer > Gambar 4.13 Rancangan halaman penampilan rekomendasi 4.5 Pembentukan Data Transaksi Data transaksi dibentuk dengan cara seperti pada Gambar 4.14. Data transaksi perlu dibentuk karena belum adanya data transaksi yang dibentuk dari data pemilihan dokumen. Pembentukan data transaksi dilakukan dengan mempertimbangkan similaritas dokumen. Similaritas dokumen yang ditetapkan
57
adalah 30% karena rekomendasi relevan umpan balik dari pengguna umumnya memiliki similaritas diatas 30%. Start
Dokumen Uji Dokumen ID Dokumen Keyword
tidak
i=0 num!=doc_uji[i] and num not in tid
ya
Similaritas doc[num] > 30%
ya
tid[] = num; k++
j=0
k = 0; tid = array()
tidak
num = rand (1,100)
j++
Data Transaksi = tid
tidak
k < 20
ya
tidak
j < 100
ya
i++
i < 11
ya End
Gambar 4.14 Flowchart pembentukan data transaksi
BAB V IMPLEMENTASI Recommendation system dibangun berbasis web menggunakan bahasa pemrograman PHP dengan basis data MySQL. Berdasarkan perancangan sistem yang telah dilakukan sebelumnya, proses implementasi ke dalam bahasa pemrograman dibagi menjadi empat bagian yaitu implementasi text processing untuk
keyword
extraction
system,
implementasi
algoritma
FP-Growth,
implementasi perbandingan keyword dengan pendekatan kemiripan keyword menggunakan cosine similarity dan penentuan rekomendasi. 5.1 Implementasi Text Processing Proses text processing digunakan untuk mengekstraksi dokumen ke dalam bentuk term dan juga bobot masing-masing term. Proses text processing dimulai dengan melakukan konversi terhadap dokumen dengan format pdf ke dalam format txt menggunakan aplikasi pdftotxt. Selanjutnya berturut-turut dilakukan proses tokenisasi, stopword removal, stemming, dan terakhir perhitungan term frequency sebagai bobot term. 5.1.1 Tokenisasi Bahasa Indonesia menggunakan karakter spasi sebagai pemisah kata sehingga tokenisasi yang digunakan merupakan white space tokenization. Proses tokenisasi diawali dengan pembacaan setiap baris pada dokumen txt. Baris-baris itu lalu dipecah berdasarkan karakter spasi dan disimpan pada variabel $text. Proses tersebut terdapat pada baris pertama hingga ke-4 pada Gambar 5.1. Selanjutnya akan dilakukan penghapusan karakter yang terkandung pada variabel $tanda agar kata tidak mengandung karakter-karakter yang tidak diperlukan. Pada tokenisasi juga dilakukan penghapusan karakter yang memiliki jumlah karakter kurang dari satu seperti yang ditunjukkan baris ke-7 hingga baris ke-9 pada Gambar 5.1. Selain spasi, karakter lain yang menjadi pemisah antar kata adalah “/” dan “-”. Khusus untuk pemisah karakter “-” akan dilakukan bersama proses stemming karena jika kata tersebut sama, maka hanya akan dihitung satu kali saja. 58
59
Baris ke-10 pada Gambar 5.1 menggunakan fungsi strpos untuk melakukan pemeriksaan karakter “/” yang digunakan sebagai pemisah antara kata. Jika terdapat karakter “/” yang terkandung dalam kata maka kata akan dipecah dengan karakter “/” sebagai pemisah. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17.
while(!feof($file)){ $text = array_merge((array)$text,(array)explode(" ",fgets($file,filesize($document)))); } fclose($file); foreach ($text as $key => $val){ $text[$key]= strtolower(trim((str_replace ($tanda,"",$val))); if (strlen($text[$key]) < 2){ unset($text[$key]); } elseif (strpos($text[$key],"/")){ $temp_text = explode("/",$text[$key]); $text[$key] = $temp_text[0]; for ($a=1;$a
Gambar 5.1 Potongan kode tokenisasi 5.1.2 Stopword removal Seleksi stopword dilakukan dengan membandingkan antara daftar kata yang ada pada variabel $text hasil tokenisasi dan kata yang terdapat pada stoplist. Stoplist disimpan dalam basis data. Jika kata tersebut terdaftar dalam stoplist maka kata tersebut akan dihapus dari variabel $text dengan fungsi unset. Pencarian kata pada stoplist dilakukan dengan perintah SQL pada baris ke-2 Gambar 5.2. Gambar 5.2 menunjukkan potongan kode dari fungsi stopword removal. 1. 2. 3. 4. 5. 6. 7.
foreach ($text as $key => $val){ $query = "select * from stoplist where stopword = '$val'"; $count = mysql_num_rows (mysql_query($query,$database)); if($count == 1){ unset($text[$key]); } }
Gambar 5.2 Potongan kode stopword removal
60
5.1.3 Stemming Fungsi stemming digunakan untuk merubah daftar kata yang terdapat pada variabel $text menjadi kata dasar. Fungsi ini memerlukan lima fungsi lain yaitu fungsi untuk penghapusan partikel (particle), kata ganti kepunyaan (possessive pronoun), awalan pertama (first prefix), awalan kedua (second prefix), dan juga akhiran (suffix). Kata merupakan masukan yang diperlukan oleh fungsi stemming dan disimpan dalam variabel $word. Proses pertama yang dilakukan adalah penghapusan partikel pada kata. Penghapusan partikel akan dilakukan apabila ditemukan partikel pada kata. Proses penghapusan partikel ditunjukkan oleh baris ke-1 hingga ke-3 pada Gambar 5.3. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19.
if (particle($word)){ $word = substr($word,0,-3); } $word = possesive_pronoun($word); $s3_word = first_prefix($word); if ($s3_word["word"] == $word){ $sp_word = second_prefix($word); $word = $sp_word["word"]; $word = suffix($word,$sp_word["prefix"]); } elseif ($s3_word["word"] != $word){ $word = $s3_word["word"]; $suffix_word = suffix($word,$s3_word["prefix"]); if ($suffix_word != $word){ $word = $suffix_word; $sp_word = second_prefix($word); $word = $sp_word["word"]; } }
Gambar 5.3 Potongan kode stemming Proses selanjutnya adalah penghapusan kata ganti kepunyaan. Proses ini ditangani pada fungsi possessive_pronoun($word). Proses ketiga adalah penghapusan awalan pertama. Jika awalan pertama ditemukan, maka fungsi first_prefix() menghasilkan kata yang telah dihilangkan awalannya serta awalan yang terkadung dalam kata. Awalan ini digunakan untuk membedakan kombinasi imbuhan yang diijinkan (legal) dan yang tidak diijinkan (ilegal) saat penghapusan akhiran. Fungsi second_prefix juga menghasilkan awalan yang terkandung dalam kata. Proses selanjutnya yang dilakukan berturut-turut jika ditemukan awalan
61
pertama adalah penghapusan akhiran dan penghapusan awalan kedua. Apabila awalan pertama tidak ditemukan, maka proses yang dilakukan berturut-turut adalah penghapusan awalan kedua dan penghapusan akhiran. Proses penghapusan akhiran dikerjakan pada fungsi suffix(). Fungsi suffix membutuhkan kata serta awalan sebagai masukan dan menghasilkan kata yang telah dihilangkan akhirannya. Pada fungsi suffix juga berisi aturan tentang imbuhan yang tidak diijinkan. Fungsi terakhir yaitu fungsi second_prefix yang digunakan untuk menhapus awalan kedua. Fungsi ini menghasilkan kata yang telah dihilangkan awalan keduanya. 5.1.4 Term frequency Pembobotan dengan skema term frequency dilakukan dengan cara menghitung jumlah kemunculan term. Penghitungan term frequency dilakukan bersama proses stopword dan juga stemming. Pembobotan dilakukan dengan mengkalkulasi jumlah term yang muncul. Term frequency akan disimpan pada variabel $term dalam bentuk $term[“nama term”] = jumlah kemunculan. Pada saat kata selesai diproses oleh fungsi stemming, jumlah kata yang sama akan ditambahkan ke dalam variabel. Gambar 5.4 merupakan potongan kode pembobotan dengan term frequency. 1. 2. 3. 4. 5.
foreach ($text as $key => $val){ ............ $text[$key] = stem($text[$key]); $term[$text[$key]] += 1; }
Gambar 5.4 Potongan kode perhitungan term frequency 5.2 Implementasi Algoritma FP-Growth Fungsi dari algoritma FP-Growth adalah mencari itemset yang melebihi minimum support yang ditentukan pengguna. Pada sistem yang dibangun, itemset adalah item tunggal maupun serangkaian item dimana item tersebut berupa id dari dokumen. Algoritma FP-Growth terbagi menjadi empat bagian yaitu frequent item search, pembentukan FP-Tree, pembangunan conditional FP-Tree, dan ekstraksi frequent itemset berdasarkan conditional FP-Tree yang telah dibentuk.
62
Untuk efisisensi waktu akses basis data, sistem hanya melakukan proses pengambilan data transaksi pada dua proses yaitu pencarian frequent item dan pembentukan FP-Tree. Setelah data didapatkan, semua data dan hasil proses dari data tersebut akan dimasukkan ke dalam sebuah variabel. Sedangkan proses lain pada penggalian frequent itemset tidak akan melibatkan basis data. 5.2.1 Pencarian frequent item Data transaksi disimpan pada basis data dengan spasi sebagai pemisah antara item. Setiap data transaksi juga diawali dan diakhiri dengan karakter spasi untuk memudahkan seleksi item tertentu pada data transaksi. Seleksi data transaksi pada basis data menggunakan perintah SQL (Structured Query Language) yang ditunjukkan oleh baris pertama pada Gambar 5.5. Penggalian frequent item dilakukan dengan menghitung jumlah dari setiap item yang muncul dimana data transaksi yang terlibat adalah data transaksi yang memiliki id dokumen (item) sesuai dengan pilihan pengguna. Frequent item merupakan item yang memiliki jumlah yang melebihi minimum support. Item disimpan pada variabel $tid_array sebagai key dan jumlah sebagai value. Setelah seluruh data transaksi diseleksi, maka item yang memiliki jumlah kemunculan kurang dari minimum support akan dihapus. Gambar 5.5 merupakan potongan kode dari fungsi pencarian frequent item. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
$query = "select tid from transaction_id where tid like '% $tid %'"; $tid_row = mysql_query($query,$database); while ($tid_list = mysql_fetch_row($tid_row)){ $tid_array = explode(" ",trim($tid_list[0])); for ($id = 0; $id < count($tid_array); $id++){ $id_count[$tid_array[$id]] = $id_count[$tid_array[$id]]+1; } } arsort($id_count); foreach ($id_count as $key => $count){ if ($count < $minimum_support) unset($id_count[$key]); } $frequent_item = array_keys($id_count);
Gambar 5.5 Potongan kode frequent item search
63
Selain seleksi item, pada fungsi ini juga dilakukan pengurutan item secara ascending dengan memperhatikan jumlah kemunculan item. Dengan contoh data transaksi pada sub bab 4.2.2, akan didapatkan jumlah data transaksi menjadi 6 data transaksi dengan jumlah kemunculan setiap item dan bentuk penyimpanan dalam array ditunjukkan oleh Tabel 5.1. Tabel 5.1 Penyimpanan jumlah item pada array $id_count [1] = 6 $id_count [13] = 1 $id_count [14] = 1 $id_count [20] = 2 $id_count [2] = 2 $id_count [3] = 3 $id_count [4] = 4 $id_count [5] = 1
$id_count [19] = 1 $id_count [7] = 1 $id_count [8] = 1 $id_count [9] = 1 $id_count [10] = 1 $id_count [11] = 1 $id_count [17] = 1 $id_count [18] = 1
Proses penghitungan jumlah kemunculan ditunjukkan oleh baris 3 hinggan 8 pada Gambar 5.5. Dengan dikenakan minimum support 40% maka jumlah minimal kemunculan setiap item adalah 2,4. Jumlah minimal kemunculan akan dibulatkan dengan menggunakan fungsi round() sehingga jumlah minimal kemunculan menjadi 2. Dengan melihat jumlah minimal dan pengurutan berdasarkan jumlah kemunculan maka didapatkan frequent item yang ditunjukkan Gambar 5.6. $id_count [1] = 6 $id_count [1] = 6 $id_count [20] = 2 $id_count [4] = 4 Sort $id_count [2] = 2 $id_count [3] = 3 $id_count [3] = 3 $id_count [20] = 2 $id_count [4] = 4 $id_count [2] = 2 Gambar 5.6 Pengurutan frequent item 5.2.2 FP-Tree Struktur data yang digunakan untuk membentuk tree merupakan sebuah class. Selain stuktur data, diperlukan variabel untuk menampung prefix path dari FP-Tree dan conditional FP-Tree yang terbentuk. Gambar 5.7 merupakan potongan kode class tree.
64
1. class Tree { 2. public $count; //jumlah kemunculan 3. public $child; //daftar node child 4. public $label; //label node 5. public $parent; // node parent 6. public $path; //node selanjutnya 7. public $parent_label; //label node parent 8. function __construct($id,$node_parent){...} 9. function IncCount() {...} 10. function ReadCount() {...} 11. function ReadLabel() {...} 12. function AddChild($addr,$id) {...} 13. function PathUpdate($path_point) {...} 14. function ChildSort($order) {...} 15. }
Gambar 5.7 Potongan kode struktur data Tree Penyimpanan child pada tree menggunakan array dengan bentuk $parent[id item] = “alamat”. Pembangunan FP-Tree dimulai dari penentuan root yaitu item yang dipilih oleh pengguna. Setelah root terbentuk, setiap data transaksi akan dibaca dan dimasukkan ke dalam tree. Potongan kode pembentukan data transaksi ditunjukkan oleh Gambar 5.8. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23.
$query = "select tid from transaction_id where tid like '% $tid %'"; $tid_row = mysql_query($query,$database); $fp_tree = new Tree($tid,"root"); while ($tid_list = mysql_fetch_row($tid_row)){ $tid_array = explode(" ",trim($tid_list[0])); $tid_array = tid_sort($tid_array,$frequent_item); $fp_current = $fp_tree; foreach ($tid_array as $id){ if ($id == $fp_current->label){ $fp_current->IncCount(); } else if ($fp_current->child[$id] == null){ $fp_current->child[$id] = new Tree($id,$fp_current); $fp_current = $fp_current->child[$id]; $fp_current->IncCount(); } else{ $fp_current = $fp_current->child[$id]; $fp_current->IncCount(); } } } $prefix_path = reorder_child($fp_tree,$frequent_item,$prefix_path);
Gambar 5.8 Potongan kode pembentukan FP-Tree
65
Untuk memasukkan data transaksi, diperlukan pemecahan data transaksi ke dalam bentuk kumpulan item. Setiap item dimasukkan ke dalam node yang menyimpan jumlah kemunculan, parent, child, dan path. Path merupakan penunjuk ke node terdekat berikutnya yang memiliki item sama. Node baru akan dibentuk bila node item yang dibaca belum belum terdapat pada tree. Jika node item sudah ada, maka akan dilakukan penambahan jumlah yang dari node tersebut. Penambahan jumlah node dilakukan pada fungsi IncCount(). Pembentukan FP-Tree berakhir pada pembuatan tabel prefix path. Pengisian tabel prefix path serta pengurutan child setiap node akan dilakukan pada fungsi reorder_child(). Hal tersebut dilakukan karena prefix path setiap node adalah node paling kiri pada tree sehingga pembentukan prefix path baru dimungkinkan pada saat item telah diurutkan. Pemindaian data transaksi untuk kedua kalinya ditunjukkan oleh baris 2 pada Gambar 5.8. Data transaksi yang dipilih merupakan data transaksi yang memiliki id dokumen yang dipilih oleh pengguna. Dengan menggunakan frequent item yang didapatkan pada sub bab 4.2.2, data transaksi akan dimasukkan perbaris ke dalam FP-Tree setelah diurutkan dan diseleksi sesuai dengan urutan dan daftar frequent item. Item yang tidak terdapat pada frequent item akan dibuang dari data transaksi yang akan dimasukkan ke dalam FP-Tree. Proses pengurutan dan seleksi dilakukan dalam fungsi tid_sort() baris 6 pada Gambar 5.8. Proses penambahan jumlah kemunculan node (count) dibagi menjadi 3 kondisi yaitu kondisi dimana item tersebut merupakan root (baris 9 Gambar 5.8), item merupakan child baru (baris 12 Gambar 5.8) dan item merupakan child (baris 17 Gambar 5.8). Proses pembentukan FP-Tree dengan memasukkan data transaksi 1, 2, 4, 5, dan 6 dapat dilihat pada Gambar 5.9.
66
Label : 1 Count : 1 Parent : root
Label : 1 Count : 2 Parent : root
Label : 1 Count : 3 Parent : root
2
4
1 Label : 20 Count : 1 Parent : 1
Label : 4 Count : 1 Parent : 1
Label : 20 Count : 1 Parent : 1
Label : 4 Count : 1 Parent : 1
Label : 3 Count : 1 Parent : 4
Label : 3 Count : 1 Parent : 4
Label : 20 Count : 1 Parent : 3
Label : 20 Count : 1 Parent : 3
Label : 2 Count : 1 Parent : 20
Label : 2 Count : 1 Parent : 20
5
Label : 20 Count : 1 Parent : 1
Label : 1 Count : 4 Parent : root
Label : 20 Count : 1 Parent : 1
Label : 1 Count : 4 Parent : root Label : 4 Count : 3 Parent : 1 6
Label : 3 Count : 3 Parent : 4
Label : 20 Count : 1 Parent : 3
Label : 2 Count : 1 Parent : 20
Label : 20 Count : 1 Parent : 1
Label : 4 Count : 2 Parent : 1
Label : 3 Count : 2 Parent : 4 Label : 2 Count : 1 Parent : 1
Label : 20 Count : 1 Parent : 3
Label : 2 Count : 1 Parent : 20
Gambar 5.9 Pembentukan FP-Tree data transaksi 1, 2, 4, 5, dan 6 Sedangkan bentuk FP-Tree saat seluruh data transaksi telah dimasukkan pada Gambar 5.10. Setelah pembentukan FP-Tree, proses selanjutnya merupakan proses pengurutan child berdasarkan urutan frequent itemset dan pembentukan prefix path. Gambar 5.11 merupakan FP-Tree akhir disertai dengan prefix path dari FP-Tree tersebut.
67
Label : 1 Count : 6 Parent : root
Label : 20 Count : 1 Parent : 1
Label : 4 Count : 4 Parent : 1
Label : 3 Count : 3 Parent : 4
Label : 20 Count : 1 Parent : 3
Label : 2 Count : 1 Parent : 1
Label : 2 Count : 1 Parent : 20
Gambar 5.10 FP-Tree semua data transaksi Label : 1 Count : 6 Parent : root
Label : 1 Count : 6
Label : 4 Count : 4
Label : 4 Count : 4 Parent : 1
Label : 3 Count : 3
Label : 3 Count : 3 Parent : 4
Label : 20 Count : 2
Label : 20 Count : 1 Parent : 3
Label : 2 Count : 2
Label : 2 Count : 1 Parent : 20
Label : 20 Count : 1 Parent : 1
Label : 2 Count : 1 Parent : 1
Gambar 5.11 Implementasi FP-Tree akhir
68
5.2.3 Conditional FP-Tree Berbeda dengan pembentukan FP-Tree yang dibentuk menggunakan data transaksi, pembentukan conditional FP-Tree dilakukan dengan memecah FP-Tree ke bagian yang lebih kecil sesuai dengan item yang ada pada tabel prefix path. Potogan kode pembentukan conditional FP-Tree dapat dilihat pada Gambar 5.12. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41.
while ($prefix_path_temp != null){ $parent_node = explode(" ",$prefix_path_temp->parent_label); foreach ($parent_node as $label){ if ($conditional_fp_tree == null){ $conditional_fp_tree = new Tree($label,"root"); $conditional_fp_tree->count = $prefix_path_temp->count; $conditional_temp = $conditional_fp_tree; $conditional_prefix[$label]["id"] = $conditional_fp_tree; $conditional_prefix[$label]["path"] = $conditional_fp_tree; $conditional_prefix[$label]["count"] = $prefix_path_temp>count; } else if ($conditional_fp_tree->label == $label){ $conditional_fp_tree->count += $prefix_path_temp->count; $conditional_prefix[$label]["count"] += $prefix_path_temp>count; $conditional_temp = $conditional_fp_tree; } else{ if ($conditional_temp->child[$label] != null){ $conditional_temp->count += $prefix_path_temp ->count; $conditional_prefix[$label]["count"] += $prefix_path_temp->count; $conditional_temp = $conditional_temp->child[$label]; } else{ $conditional_temp->child[$label] = new Tree($label,$conditional_temp); $conditional_temp = $conditional_temp ->child[$label]; $conditional_temp->count += $prefix_path_temp->count; if ($conditional_prefix[$label] == null){ $conditional_prefix[$label]["id"] = $conditional_temp; $conditional_prefix[$label]["path"] = $conditional_temp; } else{ $conditional_prefix[$label]["path"]->path = $conditional_temp; $conditional_prefix[$label]["path"] = $conditional_temp; } $conditional_prefix[$label]["count"] = $prefix_path_temp>count; } } } $prefix_path_temp = $prefix_path_temp->path; } $keypp = array_keys($conditional_prefix);
Gambar 5.12 Potongan kode pembentukan conditional FP-Tree
69
Pembentukan conditional FP-Tree dimulai dengan penentuan item yang digunakan sebagai acuan. Item tersebut adalah item yang kemunculannya paling sedikit atau dapat pula dikatakan item yang berada pada posisi paling bawah dalam tabel prefix path. Cabang yang dipertahankan adalah yang berakhir pada node yang ditentukan dan selain cabang tersebut akan dihapus dari conditional FP-Tree. Prefix path untuk conditional FP-Tree disebut conditional prefix path. Variabel $conditional_prefix merupakan variabel yang digunakan untuk menyimpan conditional prefix path. Variabel ini meyimpan jumlah dari item, path node pertama, dan juga label dari item tersebut. Penggunaan FP-Tree untuk pembentukan conditional FP-Tree hanya dilakukan apabila item acuan merupakan pecahan langsung dari FP-Tree atau dengan kata lain item acuan terdapat pada prefix path. Pembentukan conditional FP-Tree dari FP-Tree yang terdapat pada sub bab 5.2.2 ditunjukkan oleh Gambar 5.13 hingga Gambar 5.16. Label : 1 Count : 2 Parent : root
1:2
Label : 1 Count : 2 Parent : root
1:2
4:2
Label : 4 Count : 2 Parent : 1
4:2
Label : 4 Count : 2 Parent : 1
3:2
Label : 3 Count : 2 Parent : 4
3:2
Label : 3 Count : 2 Parent : 4
20 : 1
Label : 20 Count : 1 Parent : 3
Label : 2 Count : 2 Parent : 1 Label : 1 Count : 2 Parent : root
1:2 2:2
Label : 2 Count : 1 Parent : 20
4:2
Label : 4 Count : 2 Parent : 1
Gambar 5.13 Conditional FP-Tree untuk item id 2
70
Label : 1 Count : 2 Parent : root
1:2
4:1
Label : 4 Count : 1 Parent : 1
3:1
Label : 3 Count : 1 Parent : 4
Label : 1 Count : 2 Parent : root
1:2
Label : 20 Count : 1 Parent : 1
4:1
Label : 4 Count : 1 Parent : 1
3:1
Label : 3 Count : 1 Parent : 4
Label : 20 Count : 1 Parent : 3
20 : 2
Gambar 5.14 Conditional FP-Tree untuk item id 20 Jika item acuan merupakan pecahan conditional FP-Tree atau dengan kata lain merupakan item yang diambil dari conditional prefix path, maka Tree yang digunakan untuk pembentukan conditional FP-Tree adalah conditional FP-Tree item sebelumnya. Pembentukan conditional FP-Tree didasarkan pada FP-Tree dimana node yang tidak terkait dan tidak memenuhi minimum support akan dihapus. Label : 1 Count : 3 Parent : root
1:3
4:3
Label : 4 Count : 3 Parent : 1
3:3
Label : 3 Count : 3 Parent : 4
Label : 1 Count : 3 Parent : root
1:3
4:3
Label : 4 Count : 3 Parent : 1
Gambar 5.15 Conditional FP-Tree untuk item id 3
71
Label : 1 Count : 4 Parent : root
1:4
4:4
Label : 4 Count : 4 Parent : 1
Gambar 5.16 Conditional FP-Tree untuk item id 4 5.2.4 Ekstraksi itemset Ektraksi itemset juga merupakan bagian dari proses pembentukan conditional FP-Tree. Proses ini dilakukan dengan memeriksa semua item pada tabel conditional prefix path yang terbentuk pada saat pembentukan conditional FP-Tree. Jika jumlah item yang membentuk conditional FP-Tree melebihi jumlah minimum support, maka item tersebut merupakan bagian dari frequent itemset. Ekstraksi itemset dimasukkan ke dalam proses pembentukan conditional FP-Tree karena untuk meneruskan proses rekursif pembentukan conditional FP-Tree diperlukan jumlah item yang melebihi minimum support sehingga pembentukan conditional FP-Tree tidak sia-sia. Jika item tersebut merupakan bagian dari frequent itemset, maka conditional FP-Tree akan dibentuk kembali berdasarkan condtional FP-Tree yang telah digunakan sebelumnya. Gambar 5.17 merupakan potongan kode proses ekstraksi itemset. 1. 2. 3. 4. 5. 6. 7. 8.
for ($i = count($conditional_prefix)-1;$i >= 1;$i--){ if ($conditional_prefix[$keypp[$i]]["count"] >= $minimum_support){ $fi_temp = $keypp[$i]." ".$fi; $fi_list[count($fi_list)] = $fi_temp; $fi_list = create_conditional_fp_tree ($conditional_prefix[$keypp[$i]] ["id"],$fi_temp,$fi_list); } } return $fi_list;
Gambar 5.17 Potongan kode ekstraksi itemset Dengan contoh pada sub bab 5.2.1 hingga sub bab 5.2.3, frequent itemset yang diproses pertama adalah item dengan id 2. Conditional FP-Tree item id 2 ditunjukkan oleh Gambar 5.13. Pada gambar kiri menunjukkan conditional FP-
72
Tree awal item 2. Lalu item 2 akan dihilangkan pada pembentukan conditional FP-Tree untuk itemset “2, 20”. Dengan count yang lebih kecil dari minimum support, maka itemset “2, 20” bukan bagian dari frequent itemset. Oleh karena itu, proses pembentukan conditional FP-Tree yang mengandung item 2 dan 20 tidak dilakukan. Gambar 5.13 kanan atas merupakan conditional FP-Tree untuk itemset “2, 3” dan Gambar 5.13 kanan bawah untuk itemset “2, 3, 4”. Penggalian tidak dilanjutkan hingga root (item id 1) karena root merupakan item yang digunakan sebagai acuan penggalian. Proses yang ditunjukkan dengan Gambar 5.14, Gambar 5.15, dan Gambar 5.16 merupakan penggalian itemset yang secara garis besar sama dengan proses yang dilakukan pada Gambar 5.13. Dari conditional FP-Tree akan didapatkan frequent itemset dengan urutan penggalian ditunjukkan oleh Gambar 5.18. No 1 2 3 4 5 6 7
Frequent Itemset 21 321 4321 421 20 1 31 41
1
21
321
4321
421 20 1 31 41
Gambar 5.18 Urutan penggalian itemset
5.3 Implementasi Cosine Similarity Perhitungan kemiripan antar dokumen dimulai dengan perhitungan dot product. Dot product dihitung dengan menambahkan semua hasil perkalian antara term dokumen A dan term dokumen B yang bersesuaian. Setelah dot product didapatkan, dot product lalu dibagi dengan hasil perkalian dari jumlah kemunculan semua term pada dokumen A dan dokumen B. Nilai similaritas disajikan dalam bentuk persentase untuk memudahkan pengguna. Untuk menyajikan hasil dalam bentuk persentase, maka hasil perhitungan cosine
73
similarity dikalikan 100. Dot product ditunjukkan oleh baris ke-1 sampai ke-5 pada Gambar 5.19. Perhitungan akhir ditunjukkan pada baris 6 hingga 15. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.
foreach ($term1 as $key => $val){ if ($term2[$key] != null){ $dot += $term1[$key]*$term2[$key]; } } foreach ($term1 as $key => $val){ $count_term1 += $term1[$key]*$term1[$key]; } $count_term1 = sqrt($count_term1); foreach ($term2 as $key => $val){ $count_term2 += $term2[$key]*$term2[$key]; } $count_term2 = sqrt($count_term2); $count_term = $count_term1 * $count_term2; $similarity = ($dot/$count_term)*100; return $similarity;
Gambar 5.19 Potongan kode perhitungan cosine similarity 5.4 Implementasi Penentuan Rekomendasi Penentuan rekomendasi dilakukan dengan membandingkan dokumen acuan dengan dokumen pembanding berdasarkan keyword. Perbandingan ini mencari nilai similaritas dengan metode cosine similarity. Dokumen acuan ($id) akan dibandingkan dengan dokumen yang terdapat pada frequent itemset. Frequent itemset berbentuk daftar itemset. Frequent itemset didapatkan dari data transaksi yang diolah pada algoritma penggalian frequent itemset. Penentuan urutan item pada frequent itemset dilakukan berdasarkan jumlah item terbanyak tanpa memperhatikan jumlah kemunculan item. Untuk melakukan pengurutan, diperlukan pemecahan masing-masing frequent itemset ke dalam bentuk array sehingga jumlah item dapat dihitung. Proses pemecahan ini dapat dilihat pada baris 2 hingga 4 pada Gambar 5.20. Setelah jumlah item yang disimpan pada variabel $count_id didapatkan, selanjutnya frequent itemset akan diurutkan berdasarkan variabel $count_id dengan menggunakan fungsi array_multisort(). Setelah pengurutan, proses akan dilanjutkan dengan perhitungan similaritas dokumen acuan terhadap setiap item yang ada pada frequent itemset.
74
1. If (count($fi_list)>0){ 2. foreach ($fi_list as $key => $f_id){ 3. $count_id[] = count(explode(" ",trim($f_id))); 4. } 5. array_multisort($count_id, SORT_DESC, $fi_list); 6. foreach ($fi_id as $key => $f_id){ 7. $cosine[$f_id] = calculate_term($id,$f_id,$database); 8. if ($cosine[$f_id] >= $minimum_similarity){ 9. $rekomendasi[] = $f_id; 10. if (count($rekomendasi)>=$jumlah_rekomendasi){ 11. break; 12. } 13. } 14. } 15. } 16. if (count($rekomendasi)<$jumlah_rekomendasi){ 17. $query = "select id from document where judul like '%$keyword%' or abstrak like '%$keyword%'"; 18. $doc_search = mysql_query($query,$database); 19. while($doc_row = mysql_fetch_row($doc_search)){ 20. if ((!in_array($doc_row[0],$rekomendasi)) && ($doc_row[0]!=$id)){ 21. $cosine_doc = calculate_term($id,$doc_row[0],$database); 22. if ($cosine_doc >= $minimum_similarity){ 23. $rekomendasi[] = $doc_row[0]; 24. if (count($rekomendasi)>=$jumlah_rekomendasi){ 25. break; 26. } 27. } 28. } 29. } 30. } 31. $query = "select * from document where id='$id'"; 32. $doc_row = mysql_query($query,$database); 33. if (mysql_num_rows($doc_row) > 0){ 34. while ($doc_list = mysql_fetch_row($doc_row)){ 35. $doc_id = $doc_list[0]; 36. $doc_nama = $doc_list[1]; 37. $doc_judul = $doc_list[2]; 38. $doc_abstrak = $doc_list[3]; 39. $doc_path = $doc_list[4]; 40. } 41. }
Gambar 5.20 Potongan kode proses rekomendasi Dengan menggunakan frequent itemset yang didapat pada sub bab 5.2.4 maka urutan frequent itemset yang didapatkan ditunjukkan oleh Tabel 5.2. Frequent itemset diurutkan dengan menempatkan jumlah item yang lebih banyak pada posisi lebih tinggi agar kumpulan item rekomendasi dapat saling terasosiasi dengan item rekomendasi selanjutnya. Hal ini akan menguntungkan dalam pencarian rekomendasi dengan jumlah terbatas.
75
Tabel 5.2 Urutan frequent itemset No 1 2 3 4 5 6 7
Frequent Itemset 4321 321 421 20 1 21 31 41
Jumlah item 4 3 3 3 2 2 2
Frequent itemset yang didapatkan lalu diseleksi agar sistem tidak mengulangi perbandingan yang sama. Sehingga, dokumen acuan akan dibandingkan dengan dokumen yang memiliki id 4, 3, 2, 1, dan 20 secara berturut-turut. Daftar dokumen ini dimasukkan pada variabel $fi_id dan proses perbandingan ditunjukkan oleh baris 6 hingga baris 14 pada Gambar 5.20. Apabila dokumen dengan similaritas melebihi ambang batas kurang dari jumlah rekomendasi yang diharapkan, maka proses rekomendasi dilakukan dengan melakukan perhitungan similaritas dokumen acuan dengan dokumen hasil pencarian yang memanfaatkan keyword yang dimasukkan pengguna. Perhitungan similaritas dilakukan pada fungsi calculate_term(). Proses perbandingan dengan dokumen hasil pencarian ditunjukkan oleh baris 16 hingga 30 pada Gambar 5.20. Id dokumen-dokumen melebihi ambang batas yang ditentukan disimpan dalam variabel $rekomendasi. Id pada variabel rekomendasi selanjutnya digunakan untuk pencarian atribut dokumen pada basis data. Proses pencarian ditunjukkan pada baris 31 hingga 41 pada Gambar 5.20. Hasil pencarian atribut dokumen rekomendasi akan disajikan dalam bentuk daftar dokumen. Antar muka rekomendasi ditunjukkan oleh Gambar 5.21.
76
Gambar 5.21 Antar muka halaman rekomendasi
BAB VI HASIL DAN PEMBAHASAN 6.1 Data Pengujian Pengujian hybrid recommendation system memanfaatkan penggalian frequent itemset dan perbandingan keyword memerlukan 3 set data yang berupa 100 dokumen ilmiah berbahasa Indonesia, stopword bahasa Indonesia, dan data transaksi untuk melakukan penggalian frequent itemset. 6.1.1
Dokumen pengujian Dokumen untuk set data merupakan 95 dokumen ilmiah pada bidang ilmu
komputer Prosiding Semantik 2012 dan 5 dokumen ilmiah bidang ilmu komputer Prosiding Senaputro 2012. Untuk rincian dokumen yang digunakan dapat dilihat pada Lampiran 1. Pemilihan dokumen dilakukan agar ektraksi keyword memiliki output dengan kriteria dan bentuk yang sama. Untuk dokumen yang diuji berjumlah 9 dokumen yang dapat dilihat pada Tabel 6.1. Dokumen dipilih karena similaritas dengan dokumen lain yang melebihi 50% berjumlah lebih dari atau sama dengan 4. Perhitungan similaritas antara dokumen dapat dilihat pada Lampiran 2. 6.1.2
Data transaksi Pembentukan data transaksi dilakukan dengan cara seperti yang
ditunjukkan pada sub bab 4.5. Jumlah panjang deret item maksimal yang ditentukan adalah 20 dan minimal 1. Item akan dimasukkan apabila similaritas antara item melebih 30 %. Similarias antar dokumen dapat dilihat pada Lampiran 2. Data transaksi hanya dibentuk untuk 9 item yang akan dilibatkan dalam pengujian dan 2 item acak. Data transaksi yang dibentuk untuk masing-masing item tersebut berjumlah 100 data transaksi sehingga total data transaksi yang terlibat berjumlah 1100 data transaksi. Akan tetapi, dalam hasil pembentukan data transaksi tidak terdapat deret item berjumlah 20 dan jumlah data transaksi yang terlibat pada masing-masing item uji melebihi 100 data transaksi. Jumlah data
77
78
transaksi yang mengandung masing-masing data uji dapat dilihat pada Tabel 6.2. Data transaksi dapat dilihat pada Lampiran 3. Tabel 6.1 Dokumen uji No 1. 2.
3.
4. 5.
6.
7. 8. 9.
ID Judul Dokumen Dokumen 21 Membangun Sistem Informasi Pembelian Tunai Pada Apotik Cipta Dengan Object Oriented Methodology 29 Penerapan Enterprise Application Integration Sebagai Model Integrasi Sistem Informasi di Universitas Katolik Parahyangan 33 Rancang Bangun Sistem Informasi Pelayanan Kesehatan Dengan Metodologi Berorientasi Obyek : Studi Kasus SMK Telkom Sandhy Putra Jakarta 37 Sistem Informasi Geografis Industri di Kabupaten Kudus 59 Rancang Bangun Sistem Informasi Administrasi Pemeriksaan Jentik Pusat Kesehatan Masyarakat (Puskesmas) Studi Kasus Puskesmas Ciledug 63 Analisa dan Perancangan Sistem Informasi Administrasi Rawat Jalan Pada Klinik dengan Metodologi Object Oriented Studi Kasus : Klinik Maharani Tangerang 68 Implementasi Web-Service pada Sistem Pelayanan Perijinan Terpadu Satu Atap di Pemerintah Kota Palu 77 Pengembangan Aplikasi Audit Sistem Informasi Berdasarkan Cobit Framework di Rumah Sakit XXX 91 Rancang Bangun Sistem Informasi Industri Kreatif Bidang Penyewaan Sarana Olahraga
Tabel 6.2 Jumlah data transaksi masing-masing dokumen uji ID Dokumen 21 29 33 37 59 63 68 77 91
Jumlah Data Transaksi 245 239 233 231 240 248 233 253 227
79
6.1.3
Stopword Daftar stopword dapat dilihat pada Lampiran 4. Stopword yang digunakan
merupakan stopword yang diusulkan oleh Tala dalam penelitian pengembangan stemmer untuk bahasa Indonesia. 6.2 Metode Pengumpulan Data Pengumpulan data dokumen relevan terhadap dokumen acuan dilakukan dengan menggunakan umpan balik dari pengguna. Pengguna akan diberikan seluruh dokumen uji dan beberapa set dokumen. Pengguna mencari dokumen relevan terhadap dokumen uji yang ada pada Tabel 6.1 pada set dokumen. Hasil umpan balik pengguna dapat dilihat pada Lampiran 5. 6.3 Skenario Pengujian Pengujian dilakukan menggunakan minimum similarity 20% hingga 70% dan minimum support 5% hingga 25% dengan peningkatan setiap 5%. Jumlah rekomendasi maksimal akan digunakan untuk pengujian precision, recall, Fmeasure, dan mean average precision. Perhitungan nilai precision juga menggunakan jumlah rekomendasi terbatas. Sistem akan diuji dalam kasus biasa dan juga kasus coldstart. Kasus biasa merupakan pengujian dengan menggunakan data transaksi untuk penggalian frequent itemset. Sedangkan untuk kasus coldstart, data transaksi akan dikosongkan. Dokumen yang sepatutnya direkomendasikan (dokumen relevan) ditentukan secara manual oleh pengguna sistem. 6.4 Hasil Pengujian Pengujian dilakukan dengan menghitung precision, recall, F-measure, dan mean average precission untuk kasus biasa dan kasus coldstart. Pengujian ini dipilih karena dapat dilakukan tanpa melibatkan data peringkat sebagai variabel uji. Nilai precision, recall, dan F-measure dihitung dengan hanya melihat keseluruhan rekomendasi untuk masing-masing item tanpa memperhatikan urutan item rekomendasi yang diberikan oleh sistem (macro precision). Sedangkan pada
80
mean average precision akan dihitung nilai precision masing-masing item yang direkomendasikan dengan memperhatikan urutan item rekomendasi yang diberikan oleh sisitem (micro precision). Jumlah rekomendasi sebanyak 5 dokumen digunakan untuk perhitungan nilai precision jumlah rekomendasi terbatas. 6.4.1
Precision Nilai precision digunakan untuk menunjukkan ketepatan rekomendasi
yang dihasilkan oleh recommendation system. Perhitungan nilai precision dapat dilihat pada sub bab 3.5.1. Komposisi perhitungan precision untuk item ID 91 dengan mimimum similarity 40%, minimum support 20% dan jumlah rekomendasi maksimal dapat dilihat pada Tabel 6.3. Tabel 6.3 Komposisi perhitungan item ID 91 ID Relevan Item 8 11 21 33 37 41 45 54 59 63 77 80
ID Retrived Item 8 21 29 33 37 45 46 59 63 67 68 72 77 1 3 20 41 50 57
ID Hit Item 8 21 33 37 41 45 59 63 77
Rekomendasi yang dihasilkan oleh sistem merupakan semua rekomendasi (all recommendation). Hit adalah item rekomendasi benar yang direkomendasikan oleh sistem (good recommendation). Dengan demikian, perhitungan untuk nilai
81
precision item 91 dengan minimum similarity 40% persamaan (6.1). Tabel 6.4 menunjukkan nilai precision recommendation system yang dibangun untuk semua data uji pada Tabel 6.1. 9
𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 = 19 = 0.474
(6.1)
Tabel 6.4 Precision minimum similarity 40% dengan minimum support 20% ID Item 21 29 33 37 59 63 68 77 91
Hit 7 3 8 1 9 6 5 6 9
Retrived 15 14 11 14 18 13 15 15 19 Rata-rata
Precision 0.467 0.214 0.727 0.071 0.5 0.462 0.333 0.4 0.474 0.405
Nilai precision untuk jumlah rekomendasi maksimal dengan minimum similarity dan minimum support yang berbeda-beda ditunjukkan oleh Tabel 6.5 serta Gambar 6.1. Tabel 6.5 menunjukkan adanya peningkatan nilai precision saat nilai minimum support dan minimum similarity ditingkatkan.
Minimum similarity (%)
Tabel 6.5 Nilai precision jumlah rekomendasi maksimal
20 25 30 35 40 45 50 55 60 65 70
5 0.147 0.152 0.17 0.247 0.329 0.433 0.705 0.892 0.667 0.667 0.333
Minimum support (%) 10 15 20 0.172 0.207 0.289 0.176 0.212 0.302 0.181 0.217 0.315 0.25 0.269 0.339 0.33 0.351 0.405 0.433 0.437 0.453 0.705 0.716 0.703 0.892 0.892 0.836 0.667 0.667 0.667 0.667 0.667 0.667 0.333 0.333 0.333
25 0.289 0.303 0.317 0.334 0.394 0.449 0.711 0.836 0.667 0.667 0.333
Coldstart 0.289 0.303 0.317 0.334 0.394 0.449 0.711 0.836 0.667 0.667 0.333
82
Peningkatan ini terjadi karena berkurangnya jumlah rekomendasi yang dihasilkan saat nilai ambang batas tersebut ditingkatkan. Nilai precision tertinggi dicapai pada saat minimum support 5% hingga 15% untuk minimum similarity 55%.
Gambar 6.1 Grafik nilai precision jumlah rekomendasi maksimal Pada kasus coldstart, minimum support tidak mempengaruhi peningkatan atau penurunan nilai precison. Ini disebakan karena penggalian frequent itemset tidak dapat digunakan saat terjadinya kasus coldstart. Perbedaan nilai precision hanya disebabkan oleh peningkatan minimum similarity. Nilai precision pada kasus coldstart dengan minimum similarity 50% sama dengan nilai precision kasus biasa dengan minimum support 25% dan minimum similarity 50%. Untuk minimum similarity kurang dari 50%, nilai precision pada kasus biasa relatif lebih tinggi dari kasus coldstart saat minimum support kasus biasa sebesar 20%. Hal ini disebabkan oleh adanya peningkatan jumlah item hit yang direkomendasikan karena penggalian frequent itemset. Hasil berbeda terlihat pada pengujian dengan jumlah rekomendasi terbatas. Dengan minimum support 5% dan 20%, nilai precision kasus biasa relatif lebih
83
tinggi untuk semua minimum similarity yang digunakan. Hal ini disebabkan karena adanya perbedaan urutan rekomendasi yang didapatkan antara penggalian frequent itemset dan perbandingan dokumen biasa. Selain itu, penggunaan frequent itemset juga mampu menemukan item hit lebih banyak saat dikenakan minimum similarity rendah. Tabel 6.6 menunjukkan nilai precision jumlah rekomendasi terbatas. Gambar 6.2 menunjukkan bahwa nilai precision relatif meningkat untuk minimum similarity yang lebih besar.
Minimum similarity (%)
Tabel 6.6 Nilai precision jumlah rekomendasi terbatas
20 25 30 35 40 45 50 55 60 65 70
5 0.311 0.311 0.311 0.444 0.444 0.467 0.728 0.885 0.667 0.667 0.333
Minimum support (%) 10 15 20 0.178 0.244 0.422 0.178 0.244 0.422 0.178 0.244 0.422 0.222 0.244 0.444 0.311 0.333 0.467 0.333 0.333 0.467 0.683 0.683 0.731 0.907 0.907 0.852 0.667 0.667 0.667 0.667 0.667 0.667 0.333 0.333 0.333
25 0.289 0.289 0.289 0.311 0.356 0.4 0.687 0.852 0.667 0.667 0.333
Coldstart 0.178 0.178 0.2 0.222 0.356 0.422 0.687 0.852 0.667 0.667 0.333
Seperti yang terjadi pada jumlah rekomendasi maksimal, nilai precision tertinggi pada jumlah rekomendasi terbatas dicapai pada saat minimum support 10% dan 15%. Nilai precision kasus biasa pada jumlah rekomendasi terbatas kadang kala lebih tinggi dibandingkan pada rekomendasi maksimal. Akan tetapi, nilai precision kasus coldstart pada rekomendasi terbatas selalu lebih rendah dibandingkan nilai precision kasus coldstart dengan jumlah rekomendasi maksimal.
84
Gambar 6.2 Grafik nilai precision jumlah rekomendasi terbatas 6.4.2
Recall Recall merupakan nilai yang digunakan sebagai ukuran jumlah item
relevan yang dihasilkan recommendation system. Perhitungan nilai recall ditunjukkan pada sub bab 3.5.2. Perhitungan recall melibatkan hit dan rekomendasi yang benar (all good recommendation). Perhitungan recall untuk item 91 dengan komposisi perhitungan pada Tabel 6.3 ditunjukkan pada persamaan (6.2). Tabel 6.7 Recall minimum similarity 40% dengan minimum support 20% ID Item 21 29 33 37 59 63 68 77 91
Hit 7 3 8 1 9 6 5 6 9
Relevan 11 4 12 3 11 12 8 10 12 Rata-rata
9
Recall 0.636 0.75 0.667 0.333 0.818 0.5 0.625 0.6 0.75 0.668
𝑅𝑒𝑐𝑎𝑙𝑙 = 12 = 0.75
(6.2)
85
Perhitungan recall untuk semua dokumen uji dengan minimum similarity 40% dan minimum support 20% ditunjukkan oleh Tabel 6.7. Tabel 6.8 dan Gambar 6.3 menunjukkan nilai recall untuk penggunaan minimum similarity dan minimum support yang berbeda-beda untuk semua dokumen uji. Nilai recall untuk minimum similarity yang meningkat cenderung menurun pada kasus biasa dan kasus coldstart jumlah rekomendasi maksimal. Hal yang sama terjadi saat minimum
support
ditingkatkan.
Penurunan
nilai
recall
terjadi
karena
berkurangnya item retrieve yang disertai dengan berkurangnya item hit yang dihasilkan oleh sistem. Dari Tabel 6.8 dapat dilihat bahwa nilai recall kasus coldstart selalu lebih rendah dari nilai recall kasus biasa untuk penggunaan minimum similarity yang berbeda-beda. Ini menunjukkan bahwa penggalian frequent itemset dapat menemukan item hit yang tidak dapat ditemukan pada saat sistem menggunakan perbandingan keyword saja.
Minimum similarity (%)
Tabel 6.8 Nilai recall jumlah rekomendasi maksimal
20 25 30 35 40 45 50 55 60 65 70
5 0.896 0.896 0.896 0.887 0.772 0.598 0.458 0.342 0.147 0.071 0.033
Minimum support (%) 10 15 20 0.896 0.828 0.661 0.896 0.828 0.661 0.896 0.828 0.661 0.887 0.819 0.651 0.772 0.751 0.631 0.598 0.578 0.518 0.458 0.458 0.421 0.342 0.342 0.305 0.147 0.147 0.147 0.071 0.071 0.071 0.033 0.033 0.033
25 0.608 0.608 0.608 0.599 0.578 0.498 0.421 0.305 0.147 0.071 0.033
Coldstart 0.608 0.608 0.608 0.599 0.579 0.498 0.421 0.305 0.147 0.071 0.033
86
Gambar 6.3 Grafik nilai recall jumlah rekomendasi maksimal Tabel 6.9 menunjukkan nilai recall jumlah rekomendasi terbatas. Hal sebaliknya terjadi pada nilai recall jumlah rekomendasi terbatas. Peningkatan minimum similarity dan minimum support cenderung meningkatkan nilai recall hingga minimum similarity 50%. Akan tetapi, terlihat dari Gambar 6.4 bahwa nilai recall pada minimum support 5% cenderung lebih tinggi dibandingkan minimum support 10% dan 15%. Hal ini disebabkan oleh perbedaan hasil frequent itemset yang didapatkan.
Minimum similarity (%)
Tabel 6.9 Nilai recall jumlah rekomendasi terbatas
20 25 30 35 40 45 50 55 60 65 70
5 0.155 0.155 0.155 0.217 0.218 0.229 0.392 0.323 0.147 0.071 0.033
Minimum support (%) 10 15 20 0.101 0.129 0.209 0.101 0.129 0.209 0.101 0.129 0.209 0.12 0.129 0.218 0.16 0.17 0.246 0.172 0.171 0.245 0.391 0.391 0.383 0.333 0.333 0.296 0.147 0.147 0.147 0.071 0.071 0.071 0.033 0.033 0.033
25 0.153 0.153 0.153 0.163 0.183 0.223 0.363 0.296 0.147 0.071 0.033
Coldstart 0.101 0.101 0.11 0.119 0.183 0.255 0.363 0.296 0.147 0.071 0.033
87
Di sisi lain, seperti halnya pada jumlah rekomendasi maksimal, nilai recall kasus biasa cenderung lebih tinggi dibandingkan dengan kasus coldstart. Berbeda dengan nilai recall pada jumlah rekomendasi maksimal, nilai recall tertinggi pada jumlah rekomendasi terbatas didapatkan pada saat nilai minimum similarity 50%. Hal tersebut berlaku untuk kasus biasa maupun kasus coldstart.
Gambar 6.4 Grafik nilai recall rekomendasi terbatas 6.4.3
F-Measure Nilai F-measure ditunjukkan pada sub bab 3.5.3. F-measure merupakan
nilai yang menunjukkan rata-rata harmonis antara precision dan recall. Perhitungan nilai F-measure untuk item 91 dengan minimum similarity 40% dan minimum support 20% ditunjukkan pada persamaan (6.3). 𝐹𝑚𝑒𝑎𝑠𝑢𝑟𝑒 = 2 ∙
0.474∙0.75 0.474+0.75
= 0.581
(6.3)
Tabel 6.10 Merupakan hasil perhitungan nilai F-measure untuk item 91 dengan minimum similarity 40% dan minimum support 20%. Perhitungan Fmeasure masing-masing dokumen uji pada kasus biasa ditunjukkan oleh Tabel 6.11 dan Gambar 6.5. Hasil perhitungan menunjukkan bahwa untuk minimum similarity dan minimum support yang semakin meningkat, nilai F-measure yang
88
didapatkan juga cenderung meningkat. Peninglkatan terjadi hingga minimum similarity hingga 50%. Peningkatan ini disebabkan oleh meningkatnya nilai precision pada saat dilakukan peningkatan minimum similarity dan minimum support tanpa disertai penurunan nilai recall yang dapat menurunkan nilai Fmeasure. Tabel 6.10 F-measure minimum similarity 40% dengan minimum support 20% ID Item 21 29 33 37 59 63 68 77 91
Precision Recall 0.467 0.636 0.214 0.75 0.727 0.667 0.071 0.333 0.5 0.818 0.462 0.5 0.333 0.625 0.4 0.6 0.474 0.75 Rata-rata
F-measure 0.539 0.333 0.696 0.117 0.621 0.48 0.434 0.48 0.581 0.476
Minimum similarity (%)
Tabel 6.11 Nilai F-measure jumlah rekomendasi maksimal
20 25 30 35 40 45 50 55 60 65 70
5 0.249 0.255 0.28 0.376 0.444 0.47 0.521 0.479 0.236 0.128 0.06
Minimum support (%) 10 15 20 0.284 0.325 0.391 0.289 0.331 0.403 0.295 0.337 0.414 0.38 0.394 0.433 0.446 0.46 0.476 0.47 0.467 0.463 0.521 0.528 0.504 0.479 0.479 0.434 0.236 0.236 0.236 0.128 0.128 0.128 0.06 0.06 0.06
25 0.381 0.393 0.405 0.416 0.45 0.452 0.507 0.434 0.236 0.128 0.06
Coldstart 0.381 0.393 0.405 0.416 0.45 0.452 0.507 0.435 0.236 0.128 0.06
Dari Tabel 6.11 dan Gambar 6.5 juga dapat dilihat nilai F-measure pada kasus coldstart yang didapatkan oleh sistem yang dibangun. Peningkatan nilai Fmeasure pada kasus coldstart terjadi saat minimum similarity yang digunakan
89
semakin besar. Seperti pada kasus biasa, peningkatan juga terjadi hingga minimum similarity 50%.
Gambar 6.5 Grafik nilai F-measure jumlah rekomendasi maksimal Nilai F-measure pada kasus biasa saat penggunaan minimum support 20% cenderung lebih tinggi dibandingkan pada kasus coldstart. Hal ini disebabkan karena nilai precision dan recall kasus biasa jumlah rekomendasi terbatas cenderung lebh tinggi dibandingkan pada kasus coldstart. Untuk jumlah rekomendasi terbatas ditunjukkan oleh Tabel 6.12 dan Gambar 6.6.
Minimum similarity (%)
Tabel 6.12 Nilai F-measure jumlah rekomendasi terbatas
20 25 30 35 40 45 50 55 60 65 70
5 0.201 0.201 0.201 0.285 0.286 0.301 0.482 0.461 0.236 0.128 0.06
Minimum support (%) 10 15 20 0.124 0.164 0.273 0.124 0.164 0.273 0.124 0.164 0.273 0.151 0.164 0.286 0.205 0.219 0.311 0.221 0.22 0.31 0.467 0.467 0.48 0.474 0.474 0.43 0.236 0.236 0.236 0.128 0.128 0.128 0.06 0.06 0.06
25 0.195 0.195 0.195 0.208 0.236 0.276 0.453 0.43 0.236 0.128 0.06
Coldstart 0.124 0.124 0.137 0.15 0.236 0.299 0.453 0.43 0.236 0.128 0.06
90
Pada jumlah rekomendasi terbatas untuk kedua kasus uji, nilai F-measure yang didapatkan lebih rendah dari jumlah rekomendasi maksimal. Seperti halnya pada jumlah rekomendasi maksimal, nilai F-measure untuk kasus coldstart relatif lebih rendah dari kasus biasa dengan minimum support 20%. Nilai F-measure tertinggi untuk jumlah rekomendasi maksimal dan jumlah rekomendasi terbatas didapatkan saat penggunaan minimum similarity 50%.
Gambar 6.6 Grafik nilai F-measure jumlah rekomendasi terbatas 6.4.4
Mean average precision Average precision (AP) digunakan untuk menghitung rata-rata ketelitian
prediksi item yang direkomendasikan. Average precision dihitung dengan memperhatikan precision setiap item hit yang direkomendasikan. Precision setiap rekomendasi dihitung dengan memperhatikan jumlah rekomendasi (TP+FP) dan jumlah hit (TP) saat item tersebut direkomendasikan. Komposisi perhitungan average precision untuk item 91 dengan minimum similarity 40% dapat dilihat pada Tabel 6.15. Perhitungan average precision item 91 ditunjukkan pada persamaan (6.4). 𝐴𝑣𝑒𝑟𝑎𝑔𝑒 𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 =
7.055907491 19
= 0.587992291
(6.4)
91
Tabel 6.13 AP ID 9 minimum similarity 40% dengan minimum support 20% ID Rekomendasi 8 21 29 33 37 45 46 59 63 67 68 72 77 1 3 20 41 50 57
Jumlah Hit 1 2 2 3 4 5 5 6 7 7 7 7 8 8 8 8 9 9 9
Urutan Retrived 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
Micro Precision 1 1 0.667 0.75 0.8 0.833 0.714 0.75 0.778 0.7 0.636 0.583 0.615 0.571 0.533 0.5 0.529 0.5 0.473 Total
Hit Precision 1 1 0.75 0.8 0.833 0.75 0.778
0.615
0.529
7.056
Mean average precision (MAP) merupakan nilai rata-rata dari nilai average precision untuk semua kasus uji. Perhitungan nilai MAP ada pada sub bab 3.5.4. Untuk perhitungan nilai mean average precision item 91 dengan minimum similarity 40% dan minimum support 20% ditunjukkan oleh Tabel 6.14. Perhitungan mean average precision setiap item uji ditunjukkan oleh Tabel 6.15. Pengujian dengan penggunaan minimum similarity dan minimum support yang berbeda menunjukkan nilai mean average precision tidak selalu meningkat. Nilai mean average precision maksimal diperoleh saat minimum similarity yang digunakan sebesar 50% dan minimum support sebesar 5%. Nilai mean average precision dengan minimum support 5% selalu lebih tinggi saat penggunaan minimum similarity lebih besar dari 30%.
92
Tabel 6.14 MAP minimum similarity 40% dengan minimum support 20% ID Item 21 29 33 37 59 63 68 77 91
Total Hit Precision 5.143 0.983 6.918 0.083 5.079 2.917 1.607 4.007 7.056
Relevan 11 4 12 3 11 12 8 10 12 MAP
Average Precision 0.468 0.246 0.576 0.028 0.462 0.243 0.201 0.401 0.588 0.357
Minimum similarity (%)
Tabel 6.15 Nilai mean average precision
20 25 30 35 40 45 50 55 60 65 70
5 0.29 0.291 0.296 0.362 0.368 0.32 0.395 0.339 0.147 0.071 0.033
Minimum support (%) 10 15 20 0.19 0.218 0.326 0.19 0.218 0.329 0.19 0.218 0.332 0.236 0.265 0.347 0.294 0.337 0.357 0.297 0.298 0.292 0.358 0.367 0.33 0.341 0.341 0.299 0.147 0.147 0.147 0.071 0.071 0.071 0.033 0.033 0.033
25 0.232 0.237 0.244 0.247 0.281 0.269 0.341 0.304 0.147 0.071 0.033
Coldstart 0.188 0.194 0.202 0.207 0.258 0.274 0.336 0.304 0.147 0.071 0.033
Nilai mean average precision cenderung selalu meningkat pada saat penggunaan minimum similarity 10% dan pada kasus coldstart. Selain penggunaan minimum similarity 10% dan kasus coldstart, nilai mean average precision menurun saat minimum similarity 45%. Penurunan nilai mean average precision saat minimum similarity 45% lebih disebabkan oleh berkurangnya item hit yang didapatkan oleh sistem.
93
Pada kasus coldstart, nilai mean average precision cenderung lebih rendah dari kasus biasa untuk semua minimum similarity. Pada pengunaan minimum similarity 50%, kasus coldstart hanya unggul dari penggunaan minimum support 20%. Sedangkan pada saat penggunaan minimum support 10%, kasus coldstart hanya unggul pada penggunaan minimum similarity 25% dan 30%. Grafik nilai mean average precision dapat dilihat pda Gambar 6.7.
Gambar 6.7 Grafik nilai mean average precision
BAB VII KESIMPULAN DAN SARAN 7.1 Kesimpulan Setelah melakukan pengujian terhadap hybrid recommendation system yang dibangun, maka dapat diperoleh kesimpulan sebagai berikut: 1. Hybrid recommendation system dapat dibangun dengan kombinasi penggalian frequent itemset dan perbandingan similaritas keyword antara dokumen. 2. Pada pengujian untuk kasus biasa untuk jumlah rekomendasi maksimal, peningkatan nilai precision terjadi saat minimum similarity dan minimum support ditingkatkkan. Hasil terbaik didapatkan saat minimum support yang digunakan sebesar 20% dan minimum similarity 55%. Sedangkan nilai recall cenderung menurun saat minimum similarity dan minimum support ditingkatkkan. Hasil terbaik didapatkan pada saat minimum similarity kurang dari 40% dan minimum support kurang dari 15%. Nilai F-measure terbaik didapatkan saat penggunaan minimum similarity 50%. Untuk nilai mean average precision, nilai terbaik didapatkan pada saat minimum support 20% dan minimum similarity 50%. 3. Untuk rekomendasi terbatas, nilai precision tertinggi didapatkan pada penggunaan minimum support 10% dan 15%. Penetapan minimum support yang lebih tinggi hingga mencapai 55%, dapat meningkatkan nilai precision. Sedangkan pada nilai recall dan F-measure, nilai tertinggi didapatkan pada penggunaan minimum support 5%. Hal ini menunjukkan bahwa kemunculan kombinasi item yang lebih sering belum tentu mengakibatkan hasil rekomendasi yang lebih baik. Nilai tertinggi pada precision didapatkan pada minimum similarity 55%. Sedangkan nilai recall, dan F-measure terbaik didapatkan pada saat penggunaan minimum similarity 50%.
94
95
4. Berdasarkan hasil pengujian, nilai precision, recall, F-measure, dan mean average precision untuk kasus biasa pada kondisi terbaik dapat mencapai nilai yang lebih tinggi dibandingkan dengan kasus coldstart baik untuk jumlah rekomendasi terbatas maupun rekomendasi maksimal. 7.2 Saran Dari penelitian yang telah dilakukan, adapun saran yang dapat diberikan adalah sebagai berikut: 1. Diterapkan skema baru untuk mengatasi perubahan stopword. Ini diperlukan karena penambahan dan pengurangan stopword dapat mengakibatkan keyword yang diekstraksi dari dokumen menjadi tidak valid. 2. Penggunaan stopword yang khusus untuk dokumen ilmiah agar stopword yang terdaftar tepat guna sehingga dapat meningkatkan kinerja sistem. 3. Penerapan algoritma lain saat penggalian frequent itemset tidak dapat memenuhi jumlah rekomendasi yang diinginkan untuk meningkatkan jumlah item relevan yang dihasilkan oleh sistem. 4. Penerapan algoritma algoritma incremental untuk penggalian frequent itemset yang dapat mengurangi pengulangan proses penggalian frequent itemset. 5. Penggunaan dokumen uji yang lebih banyak dan bervariasi untuk menguji sistem pada kumpulan dokumen ilmiah selain bidang ilmu komputer.
