DAFTAR TABEL
Tabel 3-1 Dokumen Term 1 .................................................................................. 17 Tabel 3-2 Representasi .......................................................................................... 18 Tabel 3-3 Centroid pada pengulangan ke-0 .......................................................... 19 Tabel 3-4 Hasil Perhitungan Jarak ........................................................................ 19 Tabel 3-5 Hasil Perhitungan Jarak dan Pengelompokkan Data ............................ 20 Tabel 3-6 Hasil Centroid Akhir............................................................................. 20 Tabel 4-1 Hasil Iterasi Koefisien c Pada Kasus Non Cold Start ........................... 25 Tabel 4-2 Hasil Rata-rata MAE dan MAPE Tiap Metode .................................... 27 Tabel 4-3 Nilai ILS Tiap Metode Terhadap Adjusted Cosine Similarity ............. 28
xii
PENDAHULUAN 1.1 Latar Belakang
Seiring berkembangnya teknologi informasi, ketersediaan data dan informasi
yang dapat diakses manusia juga semakin meningkat. Berbagai macam informasi
seperti berita, iklan, film, dan lainnya kini telah mudah didapatkan di internet. Dengan kondisi tersebut, kebutuhan akan suatu sistem dalam memilah informasi
yang akan ditampilkan juga ikut meningkat. Sehingga banyak website maupun aplikasi yang telah menerapkan recommender system untuk memudahkan penggunanya dalam mendapatkan informasi yang dibutuhkan.
Recommender system merupakan bagian dari ilmu information filtering system
yang mana memiliki fungsi untuk merekomendasikan suatu konten kepada audiensinya [1]. Berbagai metode yang digunakan untuk memberikan rekomendasi
kepada pengguna ini yaitu collaborative filtering, content-based filtering, knowledge-based filtering, dan hybrid [1]. Terdapat dua metode yang umum
digunakan dalam membangun recommender system, yaitu content-based filtering dan collaborative filtering [7,8].
Content-based filtering merupakan metode yang memanfaatkan konten dan
karakteristik dari item untuk melakukan proses rekomendasinya [1]. Metode ini memiliki kekurangan dimana hasil rekomendasi yang diberikan kurang beragam (diversity) karena hanya mengacu pada konten daripada item tersebut [2]. Sedangkan
preferensi seseorang terhadap suatu item tidak selalu bergantung pada karakteristik
maupun konten item tersebut [1]. Penelitian pada recommender system saat ini telah melakukan eksperimen pada pengukuran lain untuk menilai suatu recommender
system selain menggunakan akurasi [12], salah satunya ialah diversity yang akan dihitung dengan metode intra-list similarity.
Berbeda dengan content-based filtering, metode collaborative filtering
merupakan metode rekomendasi yang memanfaatkan kesamaan minat atau kesukaan
antar penggunanya. Metode ini melihat pola kesamaan rating yang diberikan tiap
user. Kekurangan dari metode ini adalah ketidakmampuannya dalam memberikan rekomendasi untuk item baru yang belum memiliki data rating sama sekali, atau biasa disebut masalah cold start pada item [2, 9, 10, 11].
1
Penelitian ini akan berfokus pada salah satu metode hybrid yang bernama Item-
based Clustering Hybrid Method (ICHM). Metode ini mengkombinasikan pendekatan content-based dan collaborative filtering untuk mengatasi kekurangankekurangan dari kedua metode tersebut.
Dengan menggunakan skenario-skenario pengujian yang telah disesuaikan,
penelitian ini akan menggunakan dataset MovieLens yang telah lengkap untuk melakukan analisis dan pengujian dari sistem yang telah dibangun. Diharapkan dengan dibangunnya sistem yang telah teruji pada penelitian ini dapat memberikan pengembangan pada penelitian recommender system.
1.2 Perumusan Masalah
Permasalahan yang menjadi objek dari penelitian ini, terdiri atas :
1. Bagaimana membangun sistem rekomendasi yang mengimplementasikan metode ICHM?
2. Bagaimana menganalisis parameter yang optimal untuk ICHM?
3. Sejauh mana kemampuan ICHM dalam mengatasi masalah cold start yang merupakan kekurangan dari metode collaborative filtering?
4. Sejauh mana kemampuan ICHM dalam mengatasi kurang beragamnya data yang merupakan kekurangan dari metode content-based filtering?
1.3 Tujuan
Untuk menjawab beberapa permasalahan yang ada, maka tujuan yang ingin dicapai dari tugas akhir ini adalah : 1. Mengimplementasikan metode ICHM yang optimal.
2. Menganalisis metode ICHM dalam mengatasi masalah cold start.
3. Menganalisis metode ICHM dalam memberikan hasil rekomendasi yang lebih beragam dibandingkan metode content-based filtering.
Batasan-batasan yang digunakan untuk mempermudah permasalahan dalam tugas akhir ini adalah:
1. Penanganan masalah cold start pada ICHM di penelitian ini hanya menggunakan average method, tidak menggunakan weighted sum method.
2. Penelitian ini berfokus pada masalah cold start pada item baru, tidak membahas masalah cold start pada user baru.
2
1.4 Hipotesis
Hipotesis untuk penelitian ini adalah penggabungan pendekatan content-based
dan collaborative filtering dapat membentuk arsitektur Hybrid Recommender System yang optimal sehingga dapat meningkatkan akurasi prediksi rekomendasi pada masalah cold start serta memiliki derajat diversity yang lebih baik dibandingkan metode content-based filtering.
3
1.5 Metodologi Penyelesaian Masalah
Tugas akhir ini dilakukan beberapa metode dalam penyelesaian masalah sebagai berikut :
1. Studi Literatur Pada tahap ini dilakukan pencarian, pengumpulan, dan mempelajari informasi referensi yang bersumber dari buku, jurnal maupun sumber lain dari internet sebagai landasan teori dalam pengerjaan dan penyusunan tugas akhir. Referensi yang dicari berkaitan dengan Recommender System, Item-based Clustering Hybrid Method, masalah cold start dan diversity. 2. Pengumpulan Data Mencari, mengumpulkan dan membagi data sample untuk digunakan dalam pelatihan. 3. Analisis Merancang dan desain arsitektur Recommender System dengan metode ICHM yang memadukan metode content-based dan collaborative filtering. 4. Implementasi Sistem Implementasi rancangan desain Item-based Clustering Hybrid Method. 5. Analisis Hasil Pengujian Menganalisis hasil implementasi berupa tingkat akurasi prediksi yang dihasilkan serta komparasi kemampuan dan akurasinya dalam mengatasi kekurangan metode content-based filtering dan collaborative filtering. 6. Pembuatan Laporan Tugas Akhir. Mendokumentasikan penyelesaian tugas akhir ke dalam bentuk laporan tertulis.
1.6 No. 1
Jadwal Kegiatan Kegiatan
Studi Literatur
2
Perancangan Sistem
4
Analisis Hasil Implementasi Sistem
3 5
Bulan 1
Bulan 2
Bulan 3
Bulan 4
Bulan 5
Bulan 6
Implementasi Sistem Penyusunan Laporan
4
TINJAUAN PUSTAKA 2.1
Recommender System
Recommender System merupakan bagian dari ilmu Information Filtering
System yang mana merupakan sistem yang berfungsi merekomendasikan suatu hal
kepada audiensi [1]. Pada penelitian ini digunakan recommender system yang bersifat personalized atau disesuaikan dengan audiensinya. Terdapat beberapa
metode recommender system yang ada saat ini yaitu collaborative, content-based, knowledge-based, dan hybrid. Penelitian ini akan berfokus pada metode item-based
clustering hybrid method yang memadukan content-based dan collaborative filtering.
2.2
Collaborative Filtering
Collaborative filtering merupakan metode rekomendasi yang memanfaatkan
kesamaan minat atau kesukaan antar penggunanya. Gagasan dasar dari collaborative filtering adalah jika dua pengguna membeli item yang sama sebelumnya, maka besar
kemungkinan mereka memiliki minat yang sama ke depannya. Contohnya, jika pengguna A dan pengguna B memiliki banyak kesamaan pada histori pembeliannya
kemudian pengguna A baru saja membeli buku Z yang belum pernah dilihat oleh pengguna B, maka secara rasional sistem akan merekomendasikan buku ini pula ke pengguna B [1].
Metode collaborative recommendation tidak membutuhkan pengetahuan
apapun dari item yang akan direkomendasikannya. Sehingga kelebihan sistem ini adalah tidak perlu menganalisa dan mengurus data-data tiap item. Sedangkan kelemahan dan tantangan bagi pendekatan ini adalah sebagai berikut [2]:
1. Masalah cold-start, dimana rekomendasi dibutuhkan bagi item baru yang belum pernah mendapatkan rating dari pengguna [2, 11].
2. Sama sekali mengabaikan informasi yang dapat diekstrak dari konten.
5
2.2.1 Pearson Correlation
Pengukur yang paling banyak digunakan dalam menghitung similarity
adalah algoritma Pearson correlation coefficient. Pearson correlation
menghitung berapa nilai linear antara 2 variabel atau pengguna. Similarity antara pengguna a dengan u dihitung pada persamaan berikut [1]: wa ,u
iI
iI
(ra,i - ra )(ru,i - ru )
(ra,i - ra )
2
iI
(ru,i - ru )
2
(2.1)
Keterangan: wa ,u
= similarity antara pengguna u dengan pengguna aktif a
ru,i
= rating item i oleh pengguna u
i
ru
= item yang diberikan rating oleh kedua pengguna
= rating rata-rata oleh pengguna u
Untuk menggunakan sebuah prediksi, sistem menggabungkan semua
rating dari pengguna lain yang mirip terhadap pengguna aktif. Prediksi ini
digunakan untuk memberikan nilai rating suatu item terhadap pengguna aktif. Metode yang umum digunakan adalah menghitung nilai rata-rata, sistem
menggunakan korelasi antara pengguna aktif dengan pengguna lain yang mirip untuk memberikan ranting [1]. Rating dari pengguna lain yang memiliki
derajat similarity lebih tinggi dengan pengguna aktif akan memiliki nilai lebih besar ketika semua nilai rating dari pengguna yang mirip digabungkan [1].
Metode yang menggunakan deviasi menghitung prediksi rating dengan
cara menghitung rating dari setiap pengguna yang mirip. Pertama-tama, nilai deviasi rata-rata dari rating rata-rata untuk semua pengguna yang mirip
dihitung dan ditambahkan dengan nilai rata-rata rating pengguna aktif. Berikut rumus menghitung prediksi dengan deviasi [1]: p a ,i r a
( ru ,i ru ) wa ,u
iK
ueK
wa ,u
(2.2)
Keterangan: pa , i
= prediksi untuk pengguna aktif a untuk item i 6
wa ,u K
= nilai similarity antara pengguna a dan u
= kumpulan pengguna yang memiliki similarity tertinggi
2.3 Content-Based Filtering
Content-based filtering merupakan metode rekomendasi yang memanfaatkan
ketersediaan data profil pengguna dan data item yang akan direkomendasikan [1]. Data tersebut kemudian dicocokkan satu sama lain kemudian dipilih beberapa item yang relevan untuk direkomendasikan ke pengguna [1]. Sebagai contoh pada studi
kasus toko buku, maka konten item adalah deskripsi buku, genre, topik, dan penulisnya. Data tersebut kemudian dicocokkan dengan data penggunanya seperti
profil, data perilaku, kesukaan, dan data lainnya. Setelah ditemukan kesamaan yang cocok, maka item yang memiliki kesamaan tersebut direkomendasikan kepada pengguna [1].
Metode content-based recommendation memiliki dua kelebihan jika dibanding
metode lainnya. Pertama, metode ini tidak membutuhkan grup pengguna yang besar untuk dapat menghasilkan akurasi rekomendasi yang layak [2]. Kedua, item-item
baru dapat langsung direkomendasikan ketika mulai tersedia karena metode ini cukup membutuhkan data dari item tersebut untuk menghasilkan rekomendasi. Kekurangan dan batasan dari metode ini adalah sebagai berikut [2]:
1. Sulit menyediakan rekomendasi yang variatif karena semua informasi dipilih hanya terpaku pada konten
2. Sulit untuk menggunakan sistem content-based secara efektif bagi peneliti baru
2.3.1 Model Vektor TF-IDF
Konten dari dokumen dapat dibentuk menjadi daftar kata kunci dengan
berbagai cara. Pendekatan yang paling sederhana adalah dengan membuat daftar kata-kata yang muncul pada semua dokumen dan menggambarkan tiap dokumen dengan Boolean vector. Dimana nilai 1 mengindikasikan kata
tersebut muncul di suatu dokumen dan nilai 0 bahwa kata tersebut tidak muncul. Jika profil pengguna dideskripsikan dalam daftar yang sama maka
pencocokan dokumen dengan pengguna dapat dilakukan dengan mengukur kesamaan antara profil minat pengguna dengan konten dokumen [1].
7
Pada pendekatan TF-IDF, dokumen dideskripsikan dalam format TF-
IDF. TF-IDF merupakan teknik dalam bidang information retrieval yang merupakan singkatan dari term frequency – inverse document frequency.
Term frequency (TF) mendeskripsikan seberapa sering term tertentu
muncul di sebuah dokumen. Term pada penelitian ini adalah suatu kata yang
muncul pada item. Persamaan (2.3) mendeskripsikan cara untuk mendapatkan nilai term frequency. Variabel freq(i,j) menghitung jumlah munculnya term i
pada dokumen j. Dengan menggunakan term i, maka OtherKeywords(i,j)
merupakan kumpulan term lain yang muncul di dokumen j. Setelah itu dihitung maxOthers(i,j) sebagai max(freq(z,j)), z ∈ OtherKeywords(i,j) [1].
TF (i, j ) Keterangan:
TF (i, j )
freq(i, j )
freq(i, j ) max Others(i, j )
(2.3)
= Nilai term frequency
= Jumlah munculnya term i dalam dokumen j
max Others(i, j ) = Maksimum munculnya term selain i dalam dokumen j Inverse document frequency (IDF) merupakan pengukur kedua yang
akan dikombinasikan dengan term frequency. IDF bertujuan untuk mengurangi
bobot dari kata kunci yang sering muncul di semua dokumen [1]. Gagasan utamanya adalah kata-kata yang sering muncul di banyak dokumen bukanlah
kata yang begitu penting sehingga tidak begitu membantu dalam membedakan dokumen [1]. Contohnya adalah kata-kata seperti “dan”, “kemudian”, dan
“maka. Nilai bobot lebih besar seharusnya diberikan pada kata-kata yang lebih penting dan berarti. N merupakan jumlah dokumen dan n(i) adalah jumlah dokumen dari N dimana kata kunci i muncul. Nilai inverse document frequency dicari dengan menggunakan persamaan:
IDF (i ) log
N n(i )
(2.4)
Keterangan:
IDF (i) = Nilai inverse document frequency
8
n(i)
= Jumlah seluruh dokumen = Jumlah dokumen yang muncul kata kunci i
Setelah hasil dari masing-masing nilai TF dan IDF didapatkan, bobot TF-
IDF untuk kata kunci i di dokumen j dihitung dengan menggunakan persamaan:
TF IDF TF (i, j ) IDF (i)
(2.5)
2.5 Item Based Clustering Hybrid Method
Item-Based Clustering Hybrid Method (ICHM) [2] merupakan metode yang
membawa konten dari item ke dalam item-based collaborative filtering. ICHM
mengintegrasikan data rating item oleh pengguna dengan tingkat kemiripan dari masing-masing item.
Metode ICHM mengatasi kekurangan-kekurangan yang dimiliki oleh
pendekatan Collaborative dan Content-based Filtering. Dari sisi collaborative, ICHM mengatasi masalah cold-start pada pendekatan collaborative yang biasa
terjadi ketika terdapat item baru. Pendekatan collaborative memiliki kesulitan untuk
memberikan rekomendasi item baru karena belum ada pengguna yang memberikan rating pada item tersebut. Metode ICHM dapat memberikan prediksi rekomendasi item baru karena tidak hanya mengambil informasi dari matriks item-rating namun
juga dari matriks group-rating [2] yang merupakan matriks kemiripan item berdasarkan cluster-nya. Sedangkan dari sisi content-based, metode ini mengatasi masalah over-specialization yang biasa terdapat pada jenis metode content-based.
Item Content
Clustering
Item Group Vector
Group Rater
Rating Data
Result
Collaborative Filtering
Group Rating
Item Rating
9
Gambar 2-1 Gambaran metode ICHM
Berikut merupakan proses kerja pada metode ICHM:
1. Melakukan clustering untuk mengelompokkan item-item, kemudian menggunakan hasilnya untuk menciptakan matriks group-rating.
2. Menghitung tingkat kemiripan (similarity). Metode ini menggunakan tiga perhitungan similarity yaitu: Pertama menggunakan adjusted-cosine
algorithm untuk menghitung similarity dari matriks group-rating. Kedua, mengkalkulasi similarity dari matriks item-rating menggunakan Pearson
correlation similarity. Terakhir, melakukan kombinasi linier dari kedua perhitungan similarity sebelumnya untuk mendapatkan total similarity.
3. Membuat prediksi suatu item dengan melakukan deviasi rata-rata bobot dari rata-rata neighbour.
Group Rating Group Rating bertujuan untuk mengelompokkan tiap item ke dalam
beberapa cluster. Matriks group rating merupakan matriks probabilitas tiap item masuk ke dalam masing-masing cluster. Matriks inilah yang menyediakan informasi content-based metode ICHM [2, 5, 8].
Tiap item akan memiliki atribut-atribut data teks seperti contohnya
kategori, nama, dan deskripsi. Atribut-atribut item tersebut dihitung nilai TF IDF-nya menggunakan persamaan (2.5) yang kemudian hasilnya akan
digunakan untuk proses clustering menggunakan algoritma Adjusted K-Means Clustering.
10
Algoritma 1: Adjusted K-Means Clustering
Input: jumlah cluster k dan atribut item
Output: himpunan k cluster yang meminimalkan nilai error, dan probabilitas tiap item masuk ke masing-masing cluster yang direpresentasikan sebagai himpunan fuzzy (1) (2)
(3)
Pilih sejumlah k dokumen secara acak sebagai pusat cluster awal Ulangi (a) dan (b) hingga terjadi perubahan yang kecil a. Masukkan tiap dokumen ke cluster yang paling mendekati menggunakan euclidean distance b. Update rata-rata cluster Hitung nilai probabilitas dari tiap dokumen masuk ke masing-masing cluster k
Gambar 2-2-2 Algoritma Adjusted K-Means Clustering
Algoritma ini diturunkan dari algoritma K-Means Clustering yang
dikembangkan
dengan
mengaplikasikan
teori
fuzzy
set
untuk
merepresentasikan hubungan probabilitas antara objek dan cluster pada
langkah akhir algoritmanya [2, 5, 8]. Berikut merupakan persamaan untuk menentukan group rating dari suatu item. Pr o( j , k ) 1
Keterangan:
CS ( j , k ) MaxCS (k )
Pr o( j, k )
= probabilitas objek j masuk cluster k
MaxCS(k )
= nilai maksimum counter-similarity pada cluster k
CS ( j , k )
(2.6)
= counter-similarity antar dokumen j dengan cluster k
Dimana nilai dari CS(j,k) merupakan jarak antara dokumen j dengan
centroid cluster k. Nilai jarak tersebut dihitung dengan menggunakan persamaan Euclidean distance berikut
d ( p, q ) Keterangan:
n i
1
( pi qi ) 2
(2.7)
( , ) = Jarak dokumen p terhadap cluster q = Jumlah dokumen
11
= Nilai TF IDF term i pada dokumen p
= Nilai rata-rata TF IDF term i pada cluster q
Nilai pi didapatkan dari persamaan (2.5). Komputasi Similarity Setelah mendapatkan matriks group-rating, metode ini akan menggunakan algoritma item-based collaborative untuk mengkalkulasi similarity dan membuat prediksi untuk tiap user. Berikut beberapa metode untuk menghitung nilai similarity tersebut 1) Pearson Correlation-based Similarity
Pearson similarity merupakan salah satu metode kalkulasi similarity
yang paling banyak digunakan dalam collaborative filtering. Pearson
mengukur derajat hubungan linier antar dua variabel yang ada.
Persamaan ini akan digunakan untuk menghitung similarity item berdasarkan nilai rating item yang diberikan oleh penggunanya [5,8].
(R m
sim(k , l )
Keterangan:
u 1
(R m
u 1
u ,k
u ,k
R k )( Ru ,l R t )
R k )2
(R m
u 1
u ,l
Rl )2
sim(k , l )
= similarity antar item k dan l
R k , Rt
= rata-rata rating dari item k dan l
m
Ru ,k , Ru ,l
(2.8)
= jumlah pengguna yang memberi rating k dan l
= rating pengguna u pada item k dan l
2) Adjusted Cosine Similarity
Adjusted cosine similarity merupakan pengembangan dari cosine
similarity yang bertujuan untuk mengatasi masalah perbedaan skala
rating yang diberikan. Adjusted cosine similarity memiliki perbedaan dimana setiap nilai rating akan dikurangi oleh nilai rata-ratanya. Berikut merupakan persamaan cosine similarity.
12
