Sistem Rekomendasi Dasar

Saat Netflix menyarankan film yang akan kita tonton, atau Spotify menyusun playlist mingguan, algoritma yang bekerja di balik layar adalah sistem rekomendasi. Salah satu pendekatan paling klasik dan tetap relevan adalah collaborative filtering — memanfaatkan pola rating dari banyak user untuk memprediksi preferensi user lain. Pada Chapter ini kita akan membangun sistem rekomendasi item-based sederhana: matriks rating user-item disimpan dalam hash map, similarity antar item dihitung dengan cosine similarity, dan prediksi dilakukan dengan rata-rata tertimbang dari tetangga terdekat. Implementasi ini memperlihatkan bagaimana struktur data sederhana seperti unordered_map dapat merepresentasikan graph bipartit user-item secara efisien.

Model Data: Graph Bipartit User-Item #

Data rekomendasi secara alami membentuk graph bipartit: satu sisi adalah user, sisi lain adalah item, dan edge berlabel rating menghubungkan keduanya. Sparse matrix R[u][i] menyatakan rating user u pada item i, dengan mayoritas entri kosong (sparse). Penyimpanan sebagai hash map user_item_[u][i] = rating menghemat memori dibanding matriks penuh.

Kita akan fokus pada item-based CF karena similarity antar item relatif stabil dan dapat di-precompute.

Cosine Similarity: Aturan dan Mekanisme #

Aturan #

Cosine similarity mengukur sudut antara dua vektor rating. Untuk dua item a dan b, setiap user yang merating keduanya menjadi satu dimensi pada vektor. Vektor rating r_a = [rating u1, rating u2, ...] dan r_b serupa. Similarity dihitung sebagai:

sim(a, b) = (r_a · r_b) / (||r_a|| × ||r_b||)

Nilai berkisar dari 0 (tidak ada user yang cocok) hingga 1 (vektor identik proporsional).

Mekanisme di Balik Layar #

Hash map item_users_[item][user] = rating menyimpan vektor rating tiap item secara sparse. Saat menghitung similarity, kita iterasi user pada item dengan vektor lebih pendek, lalu lookup pada vektor item lain — jika user juga merated item kedua, tambahkan ke dot product. Trik ini menghindari iterasi seluruh user ketika kedua item sangat sparse. Kompleksitas per pasangan item: O(min(|U_a|, |U_b|)).

Prediksi Rating #

Untuk memprediksi rating user u pada item i yang belum dirated, kita ambil k item tetangga (paling mirip dengan i) yang sudah dirated u. Prediksi adalah rata-rata tertimbang:

pred(u, i) = Σ sim(i, j) × R[u][j] / Σ |sim(i, j)|

Kode: Item-Based Recommender #

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <set>
using namespace std;

class ItemRecommender {
public:
    // Tambahkan rating: user_id, item_id, skor 1..5
    void addRating(int user_id, int item_id, double rating) {
        user_item_[user_id][item_id] = rating;
        item_users_[item_id][user_id] = rating;
        items_.insert(item_id);
        users_.insert(user_id);
    }

    // Cosine similarity antara dua item berdasarkan vektor rating user
    double itemSimilarity(int a, int b) {
        const auto& ra = item_users_[a];
        const auto& rb = item_users_[b];

        double dot = 0, na = 0, nb = 0;
        for (const auto& kv : ra) {
            int u = kv.first;
            double va = kv.second;
            auto it = rb.find(u);
            if (it != rb.end()) dot += va * it->second;
            na += va * va;
        }
        for (const auto& kv : rb) {
            double vb = kv.second;
            nb += vb * vb;
        }

        if (na == 0 || nb == 0) return 0.0;
        return dot / (sqrt(na) * sqrt(nb));
    }

    // Prediksi rating user u untuk item i (belum dirated)
    double predict(int user_id, int item_id, int k = 3) {
        vector<pair<double,int>> sims;  // (similarity, neighbor_item)
        for (int other : items_) {
            if (other == item_id) continue;
            auto it = user_item_[user_id].find(other);
            if (it == user_item_[user_id].end()) continue;
            double s = itemSimilarity(item_id, other);
            sims.push_back({s, other});
        }
        sort(sims.begin(), sims.end(), greater<pair<double,int>>());
        if ((int)sims.size() > k) sims.resize(k);

        double num = 0, den = 0;
        for (const auto& p : sims) {
            double s = p.first;
            int other = p.second;
            double rating = user_item_[user_id][other];
            num += s * rating;
            den += fabs(s);
        }
        if (den == 0) return 0.0;
        return num / den;
    }

    // Top-N rekomendasi untuk user
    vector<pair<int,double>> recommend(int user_id, int top_n = 3) {
        vector<pair<int,double>> recs;
        for (int item : items_) {
            if (user_item_[user_id].count(item)) continue;
            recs.push_back({item, predict(user_id, item)});
        }
        sort(recs.begin(), recs.end(),
             [](const auto& a, const auto& b){ return a.second > b.second; });
        if ((int)recs.size() > top_n) recs.resize(top_n);
        return recs;
    }

private:
    unordered_map<int, unordered_map<int,double>> user_item_;
    unordered_map<int, unordered_map<int,double>> item_users_;
    set<int> items_;
    set<int> users_;
};

int main() {
    ItemRecommender rec;

    rec.addRating(1, 101, 5.0); rec.addRating(1, 102, 4.0); rec.addRating(1, 103, 1.0);
    rec.addRating(2, 101, 5.0); rec.addRating(2, 102, 4.0); rec.addRating(2, 104, 5.0);
    rec.addRating(3, 101, 1.0); rec.addRating(3, 103, 5.0); rec.addRating(3, 105, 4.0);
    rec.addRating(4, 102, 4.0); rec.addRating(4, 104, 5.0); rec.addRating(4, 105, 2.0);

    cout << "=== Sistem Rekomendasi Item-Based ===\n\n";

    cout << "Similarity antar item (cosine):\n";
    cout << "Item A | Item B | Similarity\n";
    cout << "-------|--------|-----------\n";
    vector<int> items = {101, 102, 103, 104, 105};
    for (size_t i = 0; i < items.size(); ++i) {
        for (size_t j = i+1; j < items.size(); ++j) {
            double s = rec.itemSimilarity(items[i], items[j]);
            cout << items[i] << "     | " << items[j] << "     | "
                 << fixed << setprecision(4) << s << "\n";
        }
    }

    cout << "\nRekomendasi untuk user 1 (belum rate item 104 & 105):\n";
    cout << left << setw(10) << "Item" << setw(12) << "Prediksi" << "\n";
    cout << "----------|-----------\n";
    auto recs = rec.recommend(1, 3);
    for (const auto& kv : recs) {
        cout << left << setw(10) << kv.first
             << fixed << setprecision(4) << kv.second << "\n";
    }
    return 0;
}

Output yang Dihasilkan:

=== Sistem Rekomendasi Item-Based ===

Similarity antar item (cosine):
Item A | Item B | Similarity
-------|--------|-----------
101     | 102     | 0.8085
101     | 103     | 0.2746
101     | 104     | 0.4951
101     | 105     | 0.1252
102     | 103     | 0.1132
102     | 104     | 0.8165
102     | 105     | 0.2582
103     | 104     | 0.0000
103     | 105     | 0.8771
104     | 105     | 0.3162

Rekomendasi untuk user 1 (belum rate item 104 & 105):
Item      Prediksi
----------|-----------
104       4.3775
105       2.0120

Bedah Kode Baris-per-Baris #

1. unordered_map<int, unordered_map<int,double>> user_item_;: matriks sparse dua tingkat. user_item_[u][i] memberi rating user u pada item i. Struktur ini hanya menyimpan entri non-kosong, sangat efisien untuk data rekomendasi yang biasanya 99% kosong.
2. item_users_[item_id][user_id] = rating;: struktur inverse — untuk setiap item, daftar user yang merating beserta skornya. Diperlukan untuk menghitung similarity antar item dengan cepat.
3. for (const auto& kv : ra) { auto it = rb.find(u); ... }: iterasi user pada item a, lalu cek apakah user juga merating item b. Lookup O(1) rata-rata pada hash map menghasilkan kompleksitas O(min(|U_a|, |U_b|)) per pasangan item — lebih cepat daripada iterasi seluruh user.
4. return dot / (sqrt(na) * sqrt(nb));: rumus cosine similarity. Pembagian oleh norma menormalkan magnitude, sehingga item populer tidak otomatis mendapat similarity tinggi.
5. vector<pair<double,int>> sims;: daftar similarity dengan item yang sudah dirated user. Akan di-sort descending untuk memilih k tetangga terdekat.
6. sort(sims.begin(), sims.end(), greater<pair<double,int>>());: urutkan similarity dari tertinggi ke terendah. k item teratas menjadi tetangga yang dipakai untuk prediksi.
7. num += s * rating; den += fabs(s);: akumulasi numerator dan denominator rumus prediksi. Nilai fabs memastikan denominator selalu positif meskipun similarity nol.
8. if (user_item_[user_id].count(item)) continue;: lewati item yang sudah dirated user — rekomendasi hanya untuk item yang belum pernah dipakai.

Kompleksitas #

Untuk dataset dengan n user, m item, dan r rating: precompute similarity membutuhkan O(m² × r/m) = O(m × r). Pada dataset besar, ini menjadi ratusan juta operasi tetap lebih cepat daripada memfilter seluruh user.

Tantangan Praktis #

Ringkasan #

• Collaborative filtering memanfaatkan pola rating banyak user untuk memprediksi preferensi.
• Item-based CF lebih stabil daripada user-based karena item jarang berubah.
• Cosine similarity mengukur sudut antara vektor rating — robust terhadap perbedaan skala rating antar user.
• Hash map dua tingkat menyimpan matriks sparse rating secara efisien.
• Pada skala besar, similarity di-precompute secara offline; query hanya melakukan lookup.
• Untuk produksi nyata, kombinasikan dengan content-based atau matrix factorization untuk mengatasi cold-start dan sparsity.