Alternating Least Squares Fundamentals

Introduction to ALS and Collaborative Filtering

Welcome back! In our previous lesson, you explored the foundation of user-item explicit rating matrices used in recommendation systems. Today, we'll expand on that knowledge by diving into one of the powerful techniques for collaborative filtering known as the Alternating Least Squares (ALS) algorithm.

Recommendation systems have become essential in offering personalized experiences, with collaborative filtering being a primary method. Collaborative filtering works by understanding user preferences through their past interactions and leveraging similar users or items to provide recommendations. The ALS algorithm is a matrix factorization approach that enables us to predict missing ratings effectively, making it a valuable tool in recommendation systems.

Recap of the Setup

Before we proceed with implementing the ALS algorithm, let's quickly recap the fundamental steps we covered in the previous lesson for setting up our environment. You may remember how we:

  1. Read data from a file to create a user-item interaction matrix.
  2. Marked some entries with -1 to simulate missing data for testing purposes while saving actual ratings for future evaluation.

Here's a concise C++ code snippet capturing the setup:

C++
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <sstream>
#include <random>
#include <algorithm>
#include <Eigen/Dense>

using Eigen::MatrixXd;

// Function to load a matrix from a text file
MatrixXd load_matrix(const std::string& filename) {
    std::ifstream file(filename);
    std::string line;
    std::vector<std::vector<double>> data;
    int cols = 0;
    while (std::getline(file, line)) {
        std::stringstream ss(line);
        double value;
        std::vector<double> row;
        while (ss >> value) row.push_back(value);
        if (!row.empty()) {
            if (cols == 0) cols = row.size();
            data.push_back(row);
        }
    }
    MatrixXd matrix(data.size(), cols);
    for (size_t i = 0; i < data.size(); ++i) {
        for (size_t j = 0; j < data[i].size(); ++j) matrix(i, j) = data[i][j];
    }
    return matrix;
}

int main() {
    // Initialize user-item interaction matrix from file
    MatrixXd R = load_matrix("../data/explicit-ratings.txt");

    long num_users = R.rows();
    long num_items = R.cols();

    // Mark some entries as missing (-1) for testing
    std::vector<std::pair<int, int>> all_rated_indices;
    for (int r = 0; r < num_users; ++r) {
        for (int c = 0; c < num_items; ++c) {
            if (R(r, c) != -1) all_rated_indices.push_back({r, c});
        }
    }
    double missing_ratio = 0.1;  // Density of missing entries
    size_t num_missing = static_cast<size_t>(missing_ratio * all_rated_indices.size());

    std::random_device rd;
    std::mt19937 g(rd());
    std::shuffle(all_rated_indices.begin(), all_rated_indices.end(), g);

    std::vector<std::pair<int, int>> missing_indices(all_rated_indices.begin(), all_rated_indices.begin() + num_missing);

    // Save the original matrix for evaluation
    MatrixXd original_R = R;

    for (const auto& p : missing_indices) R(p.first, p.second) = -1;

    // ... (rest of the code)
}

This setup is crucial, as it establishes the data landscape we will work with throughout the ALS implementation.

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal