Thursday, July 8, 2021

Memahami Collaborative filtering di Sistem rekomendasi

Collaborative filtering adalah teknik dalam sistem rekomendasi yang populer digunakan saat ini. Banyak penelitian yang membahas tentang teknik ini karena beberapa keunggulannya seperti: menghasilkan serendipity(tak terduga) item,  sesuai trend market, mudah diimplementasikan dan memumgkinkan diterapkan pada beberapa domain (book, movies, music, dll). 

Pengenalan sistem rekomendasi dan teknik lainnya bisa anda temukan pada artikel berikut:

Cara kerja teknik ini adalah dengan memanfaatkan data pada komunitas dengan cara mencari kemiripan atar pengguna, yaitu mengasumsikan bahwa pengguna yang memiliki preferensi serupa di masa lalu cenderung memiliki preferensi yang sama di masa depan. Pada dasarnya kita akan lebih percaya dengan rekomendasi dari orang yang memiliki preferensi sama dengan kita, inilah dasar yang digunakan oleh collaborative filtering dalam mengenerate item rekomendasi.


Dalam menghasilkan rekomendasi, sistem perlu mengumpulkan data. Tujuan dari pengumpulan data ini adalah untuk mendapatkan ide preferensi pengguna, dimana nantinya akan dibuat suatu rekomendasi berdasarkan preferensi tersebut. Terdapat 2 cara dalam mengumpulkan data, yaitu: Implicit dan Explicit.

Explicit merupakan cara pengumpulan informasi yang membutuhkan effort dari pengguna dengan memberikan feedback terhadap sistem, seperti mengisikan rating pada item (skala 1-5 atau skala lainnya) dan memilih tombol like atau dislike. Di sisi lain, implisit tidak membutuhkan interaksi dari pengguna ke sistem. Dengan kata lain, sistem secara otomatis mempelajari behavior dari pengguna saat menggunakan sistem, seperti melakukan perekaman informasi lama waktu saat melihat item, genre/kategori apa saja yang sering dilihat dan item apa saja yang pernah dibeli. Cara explisit lebih susah diterapkan, karena tidak semua pengguna melakukan penilaian terhadap item, hal ini yang akan menyebabkan kendala pada teknik collaborative filtering karena banyaknya rating kosong.

Collaborative filtering sendiri terbagi menjadi 2 bagian, yaitu Memory-based dan Model-based. Memory-based melakukan komputasi secara real-time, sedangkan Model-based menggunakan beberapa teknik di machine learning atau matrix factorization untuk melakukan training model terlebih dahulu dan bisa dilakukan secara offline. Memory-based memiliki keunggulan dalam hal kemudahan implementasi tetapi terkendala pada ukuran matrix besar yang menyebabkan scalablity dalam perhitungan. Teknik Memory-based terbagi ke dalam 2 class, yaitu: User-based dan Item-based. Teknik lain yaitu Model-based dengan beberapa metode seperti: Matrix factorization, Neural network, Bayesian, dll akan saya bahas di artikel lain. Kali ini saya akan detail bahas untuk yang Memory-based Collaborative filtering.

Kategori collaborative filtering


User-based vs Item-based CF

Memory-based collaborative filtering sering disebut juga dengan neighborhood-based collaborative filtering algorithms. Berikut ini penjelasan detail dari kedua class dalam Memory-based:

1. User-based collaborative filtering

Merupakan teknik yang digunakan untuk memprediksi item yang mungkin disukai pengguna berdasarkan penilaian yang diberikan pada item tersebut oleh pengguna lain yang memiliki selera yang sama dengan pengguna target. Berikut ini contoh penerapan dalam excel:



Pada matrix diatas, pengguna target adalah Arif, dimana kita akan memprediksi rating pada item_5. Tahap awal yang dilakukan adalah mencari pengguna yang memiliki preferensi sama dengan Arif. Lakukan perhitungan rata-rata rating dari setiap pengguna untuk item selain item_5, dihasilkan seperti berikut:



Kolom terakhir tersebut merupakan rata-rata dari tiap pengguna, misalkan Arif = (5+4+1+4)/4 = 3.50. Jika anda gunakan excel maka akan sangat cepat melakukan hitungan tersebut. Selanjutnya kita buat matrix baru yang berisi selisih dari rating asal dengan nilai rata-rata dari tiap pengguna.


Jika anda perhatikan rating Arif - item_1 didapatkan dari rating asal dikurangkan nilai rerata pengguna, yaitu:  5 - 3.5 = 1.5, rating Arif - item_2, yaitu:  4 - 3.5 = 0.5, dan seterusnya. Tahapan berikutnya adalah kita menghitung nilai similarity antar Arif dengan pengguna lainnya. Disini akan digunaan rumus cosine similarity yaitu seperti ini:

Misalkan kita akan hitung nilai similarity Arif dan Bob, maka didapatkan hasil seperti dibawah:

Dengan bantuan excel cukup kita drag saja rumus tersebut dan hasil dari similarity dari Arif dan ketiga pengguna lainnya adalah sebagai berikut:


Dari hasil perhitungan tersebut terlihat bahwa nilai similarity paling tinggi adalah antar Arif dengan Don yaitu 0.707. Nilai cosine similarity semakin besar nilai nya (mendekati 1) maka semakin mirip kedua vektor tersebut. Selanjutnya adalah prediksi rating untuk pengguna Arif pada item_5. Untuk menentukan prediksi ini kita bisa tentukan threshold/batas nilai kemiripan dari similarity pengguna, misalkan kita asumsikan similarity di dataset ini jika nilainya lebih dari 0.3, maka yang akan kita lakukan perhitungan data dari Arif, Bob dan Don. Clark tidak masuk perhitungan karena nilai similarity dibawah 0.3 (threshold yang kita tentukan). Untuk penentuan nilai threshold ini tidak ada aturan baku, jadi jika anda melakukan eksperimen silahkan di uji coba beberapa nilai threshold yang akan digunakan.

Dari rumus diatas kita bisa melakukan perhitungan untuk prediksi rating Arif ke item_5 dengan menggunakan neighbor Bob dan Don, yaitu nilai rerata Arif dijumlahkan dengan sigma dari nilai similarity antar pengguna dikalikan selisih rating dan rerata dibagi nilai absolute dari similarity beberapa pengguna tersebut.


Hasil dari prediksi rating tersebut (Arif - item_5) adalah 4.425. Bagaimana selanjutnya untuk mengenerate item rekomendasinya? Simulasi diatas hanya prediksi satu rating saja, untuk menghasilkan item rekomendasi kita bisa gunakan data real dengan jumlah data yang besar. Misalkan pada dataset real, rating Arif masih kosong di sejumlah item, misalkan item_5, item_13, item_104, item_451, item_533, dst. Dari hasil perhitungan prediksi pada rating-rating kosong tersebut, kita bisa urutkan dari rating besar ke kecil, kemudian iem-item berdasar rating tersebut bisa kita jadikan list sebagai item rekomendasi, kita juga bisa batasi sejumlah item saja(misal 5 item atau 10 item), atau biasa disebut Top-N recommendations.

2. Item-based collaborative filtering

Item-based collaborative filtering pertama kali digunakan oleh Amazon pada tahun 1998. Teknik ini tidak mencocokan kemiripan antar pengguna, tetapi melakukan pencocokan setiap item yang dinilai/rating pengguna dengan item serupa, lalu menggabungkan item serupa tersebut ke dalam daftar rekomendasi. Secara detail proses nya sebagai berikut:



Pada contoh dataset diatas, kita akan melakukan prediksi dari 3 rating kosong, yaitu: Arif - item_2, Bob - item_3 dan Don - item_1. Rumus yang kita gunakan masih sama pada user-based collaborative filtering, yaitu cosine similarity. Tahap awal adalah kita lakukan proses similarity dari ketga item tersebut, yaitu:

similarity item_1 dan item_2
i1 = 5(B1) + 3(C1)
i2 = 2(B2) + 3(C2)
sim(i1, i2) = (5*2)+(3*3)/sqrt(5^2 + 3^2) . sqrt(2^2 + 3^2) = 0.90

Perhatikan pada perhitungan diatas, hanya rating yang tidak kosong pada kedua item diatas yang dilakukan untuk perhitungannya, yaitu rating pada item_1 dan item_2 yang dinilai oleh Bob dan Clark.


Tabel diatas adalah hasil perhitungan di excel dari similarity ketiga item tersebut. Selanjutnya adalah kita lakukan prediksi untuk rating-rating kosong diatas. Berikut ini contoh perhitungan prediksi untuk rating(Arif, item_2) 

Dari hasil perhitungan di excel dari ketiga rating kosong tersebut didapatkan hasil seperti ini


Proses berikutnya dalam menghasilkan item rekomendasi sama seperti pada proses user-based diatas, yaitu dengan menghitung similarity antar item, melakukan prediksi rating kosong, kemudian melakukan ordering untuk dijadikan item rekomendasi.

Kesimpulan

Collaborative filtering merupakan teknik/paradigma yang populer digunakan dalam sistem rekomendasi. Terdapat 2 metode yang digunakan dalam collaborative filtering yaitu: memory-based dan model-based. Memory-based memiliki keunggulan dalam kemudahan proses perhitunganya tetapi memiliki kendala dalam scalabilty, karena metode ini berjalan secara real-time dan terkendala jika matrix user-item berukuran besar. Dua cara dalam perhitungan di memory-based, yaitu: user-based dan item-based, kedua teknik tersebut sama-sama memanfaatkan rating pengguna terhadap item dalam proses perhitungannya. Pada user-based dilakukan proses perhitungan similarity/kesamaan atara pengguna, sedangkan item-based melakukan proses perhitungan similarity antar item.

Bagaimana kita melakukan siimulasi perhitungan data berukuran besar, pastinya menggunakan excel akan sangat merepotkan. InshaAllah pada artikel berikutnya saya akan bahas cara perhitungan nya menggunakan python di jupyter notebook atau google colab.

Jika anda membutuhkan file excel dari perhitungan diatas, silahkan tuliskan alamat email pada kolom komentar, segera akan saya kirimkan file excel tersebut. Semoga bermanfaat!

Referensi

  1. Recommender System, A Computer Science Comprehensive Exercise, Carleton College, https://www.cs.carleton.edu/cs_comps/0607/recommend/recommender/collaborativefiltering.html
  2. Pengantar Recommender System, Yotube: Mas Baizal, https://www.youtube.com/watch?v=gu-tf3tzMgA&t=20s
  3. F.O.Isinkaye, et al, Recommendation systems: Principles, methods and evaluation, Egyptian Informatics Journal Volume 16, Issue 3, November 2015, Pages 261-273
  4. User-based collaborative filtering, https://www.geeksforgeeks.org/user-based-collaborative-filtering/
  5. Item-to-item based collaborative filtering, https://www.geeksforgeeks.org/item-to-item-based-collaborative-filtering/
  6. Item-based collaborative filtering in Python, https://predictivehacks.com/item-based-collaborative-filtering-in-python/


Subscribe to: Posts (Atom)