Problem 687666 · easy · Level 06 Heuristics & Optimization

Films Like This One

embeddings · collaborative filtering · cosine similarity · mean centring · similarity search

A streaming service has asked every viewer in a small test group to rate every film from 1 to 5. ratings[film] is the list of the film's ratings, one per viewer (the same viewer order for every film). Nobody has told the service which films are alike; the ratings should reveal it.

Write similar_films(ratings, query, k) that returns the k films most similar to query as a list of (film, similarity) pairs, most similar first:

  1. Embed every film: some viewers rate everything generously, so first compute each viewer's average rating over all films, and subtract it from that viewer's ratings. A film's embedding is its list of centred ratings.
  2. The similarity of two films is the cosine similarity of their embeddings, a·b / (|a|·|b|), or 0.0 if either embedding is all zeros. Round it to 9 decimal places.
  3. Rank every film except query by its rounded similarity to query, highest first; break ties by film name in alphabetical order. Return the first k (fewer if there are fewer other films).

viewer_ratings(n_films, n_viewers, seed) builds the tables the tests use; it is available in your code.

Examples

Input:  ratings = {"Rocket Run": [5, 4, 1, 2], "Steel Storm": [4, 5, 1, 1],
                   "Paris Again": [1, 2, 5, 4], "Two Hearts": [2, 1, 4, 5]}, query = "Rocket Run", k = 2
Output: [("Steel Storm", 0.866772944), ("Two Hearts", -0.836842912)]

Input:  ratings = {"A": [3, 3, 3], "B": [3, 3, 3], "C": [5, 1, 3]}, query = "A", k = 2
Output: [("B", 1.0), ("C", -1.0)]
Explanation: the viewers' averages are 11/3, 7/3 and 3, so A and B both become
[-0.667, 0.667, 0] and C becomes [1.333, -1.333, 0]. Raw ratings would have made A and C look similar.

Constraints

  • 2 <= len(ratings) <= 300 films, 1 to 200 viewers, 1 <= k <= 20
  • query is one of the films

Goals

  • Turn behaviour (ratings) into an embedding vector for every item
  • Remove each viewer's own rating level before comparing items
  • Rank items by cosine similarity with a reproducible tie rule
Starting Python…