JUDUL TA :
PENERAPAN COLLABORATIVE FILTERING UNTUK SISTEM REKOMENDASI PADA RENTAL VCD “HAPPY”
BAB III. METODE PENELITIAN
3.1 Analisa Kebutuhan 3.2 Perancangan Penelitian 3.3 Teknik Analisis 3.4 Jadwal Penelitian 3.1 Analisa Kebutuhan Secara umum, sistem rekomendasi bertugas membantu para user dengan cara menyediakan rekomendasi bagi para usernya. Rekomendasi yang diberikan berupa film-film yang mungkin cocok dengan selera user. Pada sistem ini user dapat memberikan rating pada berbagai macam film yang sudah dilihatnya. Rating yang diberikan oleh masing–masing user tersebut digunakan sebagai dasar untuk menentukan rekomendasi film bagi user yang bersangkutan. Nilai rating dari film yang ditentukan secara eksplisit oleh user adalah input yang diperlukan oleh sistem dalam menciptakan rekomendasi. Berdasarkan input yang diberikan oleh user, sistem akan menciptakan output berupa rekomendasi film-film apa saja yang diperkirakan akan disukai oleh user tersebut. User juga dapat melihat nilai prediksi rating yang diberikan oleh sistem terhadap masing-masing judul film yang terdapat pada sistem tersebut. Sistem Rekomendasi film ini dibuat karena disebabkan adanya
permasalahan yang dialami oleh para user dalam menentukan film apa saja yang ingin dilihat oleh user. Berikut ini beberapa permasalahan tersebut. •
Jumlah Film yang sangat banyak Setiap bulannya bermunculan film-film baru dengan katagori yang bermacammacam dimana ada yang berupa drama, comedy, action, thriller, horror, animasi dan sebagainya. Dengan jumlah film yang semakin banyak tentu membuat orang bingung untuk menentukan pilihannya oleh karena itu sistem rekomendasi untuk film sangat dibutuhkan untuk membantu di dalam memberikan rekomendasi film-film yang disukai oleh orang.
•
Kurangnya informasi mengenai film-film yang ada Sedikit sekali atau kurangnya informasi mengenai film-film yang sedang ditayangkan, yang sudah ditayangkan dan yang sedang diproduksi. Informasi / referensi mengenai film biasanya hanya dibahas sekilas secara garis besarnya saja di koran, majalah dan iklan di televisi atau di Internet.
•
Kesulitan menentukan kualitas dari sebuah film Sebuah film dapat dikatakan baik atau buruk tergantung dari jalan cerita dan selera dari orang yang menontonnya.Orang yang menyukai jenis film action tentu akan mengatakan bahwa film Mission Impposible adalah film yang sangat bagus tetapi orang lain belum tentu sependapat dengannya. Orang menganggap suatu film memiliki kualitas baik apabila film itu benar-benar cocok dengan seleranya.
•
Terbatasnya rekomendasi yang didapatkan Dalam kehidupan sehari-hari,orang dapat menilai kualitas dari suatu film berdasarkan rekomendasi/pendapat yang diberikan oleh relasi maupun sahabat. Rekomendasi yang diberikan sangat bermanfaat dan tentunya juga mengenai film-film yang sudah dilihat oleh para relasi itu akan tetapi bagaimana dengan film lainnya yang belum ditonton? Oleh karena itu dibutuhkan sumber rekomendasi yang memiliki ruang lingkup yang luas dan mampu memberikan pendapat mengenai kualitas dari berbagai macam film.
•
Mendapatkan informasi dalam waktu singkat Keinginan orang untuk mendapatkan informasi mengenai kualitas sebuah film dalam waktu singkat. Oleh karena banyaknya jumlah film yang ada. Maka akan memakan waktu lama apabila harus memilih film yang ingin ditonton sehingga memerlukan sebuah sistem yang dapat membantu mereka dalam memilih film yang berkualitas dalam waktu yang singkat.
3.2 Perancangan Penelitian 3.2.1 Context Diagram Context Diagram memberikan gambaran umum mengenai interaksi yang terjadi antara sistem dan user. Context diagram dari sistem ini ditunjukan pada gambar berikut ini Pada context diagram digambarkan proses umum yang terjadi di dalam sistem. Terdapat dua komponen utama yaitu user dan sistem rekomendasi. User dapat meminta kepada sistem untuk memberikan rekomendasi mengenai itemitem apa saja yang diperkirakan akan paling disukai oleh user tersebut. Setelah melakukan proses, sistem akan menghasilkan output berupa rekomendasi filmfilm yang ditujukan bagi user .
3.2.2 Dataset Dataset yang digunakan adalah dataset real, yaitu data-data rating yang sungguh-sungguh diberikan oleh user pada suatu sistem rekomendasi. Pada sistem ini digunakan dataset MovieLens. MovieLens adalah sebuah sistem rekomendasi yang dikembangkan oleh GroupLens 1 Research pada University of Minnesota. MovieLens menyediakan sebagian dari datasetnya bagi umum, untuk keperluan pendidikan dan riset. Dataset MovieLens telah sangat banyak digunakan untuk keperluan riset yang berhubungan dengan bidang sistem rekomendasi. Dataset ini mengandung data-data rating yang diberikan user MovieLens terhadap berbagai macam film hingga tahun 2000 an dimana rating berkisar antara 1 sampai dengan 5. Program ini tidak menggunakan keseluruhan dari dataset MovieLens, melainkan hanya mengambil sebagian dari dataset tersebut yaitu meliputi 3952 film dan 2000 user. Contoh dataset yang digunakan pada penelitian ini dapat dilihat pada tabel berikut ini :
Contoh Dataset
User
Judul Film
1
A
B
C
D
E
1
3
4
3
0
0
2
3
4
3
1
1
3
3
4
3
3
4
4
4
2
3
4
5
5
4
3
4
4
3
6
5
1
5
0
0
http ://www.cs.umn.edu/GroupLens
Dalam contoh dataset terdiri atas 6 user dengan jumlah film adalah 5. Untuk sel yang terisi angka 0 dianggap bahwa nilai dari user terhadap film tersebut tidak ada. Hal ini kemungkinan disebabkan user belum pernah menyaksikan film tersebut, sehingga total film yang diberi penilaian/ dirating dalam dataset ini hanya sejumlah 26 buah sedang yang tidak diberi nilai adalah 4 buah. Sejumlah 26 data tersebut akan menjadi acuan dalam melakukan proses prediksi untuk keempat buah data yang masing kosong tersebut. Nilai rating yang dapat diberikan berkisar antara 1 sampai dengan 5.
3.2.3 Proses Modeling
3.3 Teknik Analisis 3.3.1. Proses Kerja dari Collaborative Filtering Pada umumnya collaborative filtering menggunakan data input berupa database yang mencatat informasi tentang selera user untuk memprediksi topiktopik atau produk-produk baru yang mungkin disukai oleh user aktif. Bentuk dataset yang umum digunakan sebagai dataset input untuk proses collaborative filtering adalah matriks 2 dimensi dengan produk-produk sebagai kolom, nama user sebagai baris, dan hasil perpotongannya sebagai nilai rating yang diberikan user tertentu terhadap produk yang ditunjuk (matrik user-item). Bentuk dataset tersebut lebih dikenal sebagai bentuk transactional database. Collaborative filtering merupakan sistem yang mampu memberi rekomnedasi kepada user aktif mengenai suatu item atau produk tertentu yang mungkin
menarik
baginya.
Dalam
usaha
menyusun
rekomendasinya
tersebut,Collaborative filtering menggunakan kolaborasi informasi user lain yang memiliki selera hampir sama dengan user aktif. Jadi tugas utama dari collaborative filtering adalah mencari sekelompok user yang memiliki selera
hampir sama dengan user aktif sebagai acuan untuk memprediksi selera user aktif terhadap topik atau produk tertentu. Collaborative filtering sebagai suatu sistem penyusun rekomendasi pada dasarnya terdiri atas tiga tahapan penting, yang dapat dijabarkan sebagai berikut:
1. Mendapatkan profil dari setiap user dalam sistem, yaitu dengan mendapatkan nilai rating terhadap item-item yang ada. Nilai rating dari user bisa merupakan angka dengan kondisi tertentu, misalnya angka 5 menunjukkan sangat suka dan akan terus turun ke angka 1 menunjukkan sangat tidak suka, jadi diantara angka-angka tersebut bisa dimasukkan. 2. Sesudah setiap user diperoleh profilnya maka sistem akan melakukan perbandingan antara profil dari yang aktif dengan semua profil user yang ada dan melakukan pengukuran terhadap tingkat kemiripan/ nilai korelasi. Pada umumnya untuk mengukur tingkat kemiripan antar user dapat dilakukan dengan cara perhitungan korelasi Pearson. 3. Sesudah diperoleh nilai korelasi , maka dipilih sekolompok user yang akan bertindak sebagai advisor terhadap user yang aktif. Pemilihan advisor ini didasarkan pada nilai korelasi yang tinggi antara user yang aktif dengan user lain dan menggunakan informasi yang ada pada mereka untuk menyusun rekomendasi bagi user aktif tersebut. Untuk memperjelas penjelasan bagaimana proses collaborative filtering memberikan rekomendasi, maka dapat dilihat proses collaborative filtering pada gambar berikut ini.
Algoritma yang paling sering digunakan untuk collaborative filtering adalah correlation atau vector similarity. Dengan algoritma ini, langkah pertama yang harus dilakukan adalah memilih sekelompok user berdasarkan tingkat kesamaannya dengan user aktif, kemudian ranking yang menyatakan selera dari masing-masing user tersebut digunakan untuk menentukan prediksi yang tepat bagi user aktif. Jika Vij merupakan rating yang diberikan oleh user i untuk item j, dan Ii adalah sekumpulan item yang telah diberi rating oleh user i, maka rata-rata rating vi untuk user i dapat didefinisikan sebagai berikut : vi =
1 ∑Vi, j . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . .(3.1) | Ii | j∈i
Yang paling penting dalam algoritma ini adalah menghitung ω(a,i) yang menyatakan tingkat kesamaan seorang user i dengan user aktif a. Metode yang paling terkenal yang juga diadopsi oleh GroupLens adalah perhitungan korelasi Pearson yang menghasilkan range nilai antara +1 dan -1. Bila nilai korelasi mendekati atau sama dengan +1 maka dapat dikatakan bahwa user dan user pembanding memiliki selera yang hampir sama. Sebaliknya bila nilai korelasi mendekati -1 maka user dan user pembanding memiliki selera yang berkebalikan. Bila nilai korelasi 0 maka kedua user dinyatakan tidak memiliki korelasi.
ω(a,i) =
∑ (va, j − va)(vi, j − vi) …………. . . . ..…………(3.2) ∑ (va, j − va)2(vi, j − vi)2 j
j
Dengan hasil perhitungan tingkat kesamaan antar user aktif dengan user lain seperti yang digambarkan persamaan 3.2 maka rekomendasi untuk user aktif mungkin untuk dibuat. Prediksi tersebut dapat dilakukan dengan mengeliminasi user-user yang memiliki tingkat kesamaan di bawah nilai threshold yang ditentukan. Jika k adalah factor normalisasi, dan n adalah jumlah user dalam database collaborative filtering dengan ω(a,i)>0, dimana ω(a,i) menggambarkan jarak, korelasi, atau tingkat kesamaan antara tiap user i dengan user aktif, maka Paj yang merupakan nilai rating yang diprediksi akan diberikan oleh user aktif a terhadap item j dapat dirumuskan sebagai berikut : n
Paj = va + k ∑ w(a, i )(vij − vi) . . . . . . . . . . . . . . . . . . . . . . . . . . .(3.3) i =l
Meskipun algoritma ini dapat bekerja dengan baik pada beberapa kasus, algoritma ini masih memiliki keterbatasan. Umumnya korelasi terjadi jika ada overlap antar profil user. Ketika jumlah item yang dapat dipilih oleh user cukup banyak, overlap antar item-item yang dirating dapat saja menjadi sedikit. Dalam kasus ini perhitungan korelasi tidak dapat menjadi jaminan dalam pengukuran tingkat kesamaan. Sebagai contoh : user A dan B memiliki korelasi yang tinggi, user B dan C pun juga demikian, kemudian user A dan user C mungkin saja juga berkorelasi tinggi meskipun hanya sedikit item yang diberi rating oleh keduanya. Keterbatasan lain dari algoritma ini adalah tingkat efisiensi dalam penyusunan rekomendasi bagi user aktif. Ketika database menjadi semakin besar, perhitungan on-line untuk sekelompok user menjadi tidak efisien (selalu melakukan pembacaan database). Customer pada umumnya tidak sabar untuk menunggu hasil dari
rekomendasi. Untuk mengatasi masalah ini, algoritma
memory-based menggunakan teknik sampling meskipun terkadang metode sampling tersebut dapat membahayakan faktor keakuratan rekomendasi (ada
kalanya sampling database input mereduksi pengetahuan yang ada pada database asli).
Algoritma ComputeCorrelationSimilarity Subrutin ComputeCorrelationSimilarity() Input
: Y adalah dataset yang berisikan nilai rating untuk film yang dinilai user Output : Matrik bujur sangkar yang berisi bobot kemiripan antar user wij Metode : Bobot kemiripan antar user dihitung ber dasarkan prosedur berikut ini. Untuk setiap user ra dihitung bobot kemiripan wa,u terhadap user lain ru dalam dataset Y dengan menggunakan korelasi Pearson :
Wa,u = ∑
( ra , j − ra ) ( ru , j − ru )
Ya ,u
ru =
σuσu Ya , u
ru , k
∑ Ya, u
Ya ,u
σ2u =
( ru , j − ru ) 2 Ya , u Ya ,u
∑
Ya,k={k| k ∈ M ∪ ra,k ≠ Θ ∪ ru,k ≠ Θ}
Dari algoritma diatas dapat dijelaskan proses perhitungan korelasi antara user 1 dan user 3 dengan menggunakan korelasi Pearson. Langkah pertama ialah menghitung nilai rata-rata dari masing-masing user dimana akan didapatkan nilai rata-rata dari user 1 dan user 3 berturut-turut adalah 3,33. Perlu diketahui nilai rata-rata user 3 adalah 3,33 karena hanya film 1,2 dan 3 saja yang dihitung, karena perhitungan dilakukan untuk item dimana kedua user sudah memberikan nilai hal
ini terus berlaku dalam proses-proses berikutnya dalam penggunaan metode korelasi Pearson ini. Langkah berikutnya ialah memperoleh nilai varians (σ2) dari kedua user ini. Langkah terakhir ialah memperoleh nilai korelasi (w1,3) antar user 1 dan 3 dimana diperoleh nilai 1. Apabila subrutin ComputeCorrelationSimilarity() diimplemen tasikan secara keseluruhan kepada masing-masing kelompok seperti pada tabel 5.2 maka akan diperoleh hasil seperti yang terdapat pada tabel 5.3. Untuk melakukan proses pada fase pelatihan, kompleksitas waktunya adalah O(n2/k). Hal ini dapat dibuktikan demikian, waktu yang dibutuhkan untuk melakukan perhitungan pelatihan antar user pada sebuah kelompok adalah O(n/k)2.
Algoritma ComputeCorrelationSimilarity Input
: Y merupakan dataset untuk pelatihan dan juga merupakan dataset dari semua rating yang sudah diberikan user. K merupakan jumlah kelompok yang dibuat, sehingga jumlah k lebih kecil dari jumlah user pada dataset Y. t adalah jumlah maksimum batas dari perulangan yang dilakukan. minChange adalah nilai batasan apabila perubahan titik pusat kelompok yang sekarang dan sebelumnya kurang dari nilai minChange,maka perulangan akan dihentikan.
Output :
k kelompok data yang dikarakteristik tengah masing-masing : c1, c2, c3,…ck.
melalui
titik
Metode : Kelompok akan dibentuk dengan melakukan prosedur berikut : 1. Hitung vektor mula-mula ro sebagai titik pusat dari Y dengan menggunakan rumus berikut ro = 2. Pemilihan c2,c3,…ck
k
titik
∑ r Y ,i ∈Y
awal
i
yang
saling
terpisah
:
c1,
3. Penempatan setiap user dari Y pada kelompok Cn, dimana cn berkorelasi paling dekat dengan nilai rating dari user tersebut 4. Perhitungan titik tengah yang baru untuk tiap kelompok yang didapat dari rata-rata dari user pada kelompok tersebut, dengan menggunakan rumus : c
j
=
∑ ri / cj , i ∈ Cj
5. Iterations ++ 6. Jika iterations > t maka lanjut ke langkah 8 7. Jika perubahan yang terjadi pada titik pusat lebih besar dari batasan minChange maka kembali kelangkah 3. d(Cj , Cj 8. Stop
prev
)
< minChange
