Methods to Recommend Songs

Cosine Similarity

When dealing with a large number of users and a large number of songs and find similarities between users or songs things can quickly get out of hand. For example, to calculate the song similarity between all songs we could go through each song and calculate its similarity with each other song, however that would involve nested for loops with \(\frac{n(n-1)}{2} \) operations. Since there are 149029 unique songs in the data set, this equates to 11104746906 operations. While this is highly parallelizable, for optimal use of resources, we use linear algebra.

To solve the similarity between users and songs we construct a sparse matrix, \(R(i,j)\), that is \(m\times n\), where m is the total number of users, and n is the total number of songs. The entry of the matrix for user i at song j represents the relative number of plays that of the song compared to the total number of songs the user listens to, i.e., is the user listens to a song 6 times out of listening to 60 songs total, the relative play would be 0.1. We use relative plays as it will make constructing the similarity matrices easier.

We define the cosine similarity for two arbitrary vectors as:

The user-user similarity matrix can be computed as:

which produces a symmetric \(m\times m\) matrix, where \(m\) is the total number of users. The item-item similarity can be calculated in a similar way:

which produces a symmetric \(n\times n\) matrix, where \(n\) is the total number of songs.

Evaluation Metric

We use the mean average precision (MAP) as the evaluation metric.

For any k, define the precision-at-k \(P_k\) as the proportion of correct recommendations within the top-k of the predicted ranking:

next we take the average of the computed precisions:

where \(\tau\) is the threshold that represents how many of the top predictions in \(y_u\) to include and \(n_u\) is the number of songs in the users hidden history.

Finally, we take the average over all users precisions:

The R functions for the evaluation metrics are shown below:

average_precision_at_k <- function(k, actual, predicted){
  score <- 0.0
  cnt <- 0.0
  for (i in 1:min(k,length(predicted)))
  {
    if (predicted[i] %in% actual && !(predicted[i] %in% predicted[0:(i-1)]))
    {
      cnt <- cnt + 1
      score <- score + cnt/i
    }
  }
  score <- score / min(length(actual), k)
  return(score)
}

mAP = mean(average_precision_at_k(500, valid_data, predicted_songs))

Strategy - Recommend top 500

A simple strategy would be to suggest the same top 500 most played songs to all users.

To do this, first, we load in the relevant libraries, and construct the training and validtion datasets. For details on the initial loading of the data from the text files and SQLite databases the R code above.

library(readr)
library(dplyr)
library(tidyr)
library(Matrix)
library(plyr)
library(pbapply)

# Load in data
triplets <- as.data.frame(read_table('data/kaggle/kaggle_visible_evaluation_triplets.txt'))
colnames(triplets) <- c('User_ID', 'Song_ID', 'Plays')

# Split data into train and validation set
set.seed(666) # reproducibility
train_data <- triplets %>%
  dplyr::group_by(User_ID) %>%
  dplyr::sample_frac(0.8) %>%
  dplyr::ungroup()

valid_data <- setdiff(triplets, train_data)

The top 1000 songs are chosen based on total number number of plays across all users.

# baseline is to recommend top n most played songs,
top1000songs <- train_data %>%
  dplyr::group_by(Song_ID) %>%
  dplyr::summarise(Total.Plays = sum(Plays)) %>%
  dplyr::arrange(desc(Total.Plays)) %>%
  dplyr::top_n(1000) %>%
  dplyr::ungroup()

getBaseline_AveragePrecision(user){
  actual.songs <- filter(valid_data, User_ID == unique_users$User_ID[user])
  avg.Pres <- average_precision_at_k(k=500, actual = actual.songs$Song_ID,
                                     predicted = top1000songs$Song_ID[1:500])
  return(avg.Pres)
}

mAP_baseline <- pbsapply(seq(nrow(multMat2)), getUser_Average_Precision)

Strategy - Recommend songs by finding similar songs to songs in users list of listened songs

Two songs are similar if they have many users in common that listen to both.

This is achieved in R by creating a sparse matrix, and performing the operations on the sparse matrix.

# Create data frames of the unique songs and users
unique_users <- unique(train_data$User_ID)
unique_songs <- unique(train_data$Song_ID)

unique_users <- as.character(unique_users)
unique_songs <- as.character(unique_songs)

# Create new column where user/song ID -> unique numeric
unique_users <- cbind(unique_users, as.numeric(seq(nrow(as.data.frame(unique_users)))))
unique_songs <- cbind(unique_songs, as.numeric(seq(nrow(as.data.frame(unique_songs)))))

colnames(unique_users) <- c('User_ID', 'UID')
colnames(unique_songs) <- c('Song_ID', 'SID')

train_data$User_ID <- as.character(train_data$User_ID)
train_data$Song_ID <- as.character(train_data$Song_ID)

# Join datasets
train_data_2 <- train_data %>%
  dplyr::left_join(as.data.frame(unique_users), by = 'User_ID') %>%
  dplyr::left_join(as.data.frame(unique_songs), by =  'Song_ID') %>%
  dplyr::group_by(User_ID) %>%
  dplyr::mutate(Relative.Plays = Plays/sum(Plays))

# remove all NAs
train_data_2[is.na(train_data_2)] <- 0

# Create sparse matrix
sparse_rating_df <- sparseMatrix(i = as.numeric(train_data_2$UID),
                                 j = as.numeric(train_data_2$SID),
                                 x = train_data_2$Relative.Plays)

The method used to recommend the songs will be to recommend songs that are similar to songs already in the users list of listened songs. This is shown using the Venn diagram below.

The R code to achieve the item-item similarity is as follows:

# Song similarity matrix
multMat1 <- t(sparse_rating_df) %*% (sparse_rating_df)

# Get top 500 similar songs of a given song
gettop500simSong <- function(song){
  user_sim <- multMat1[song,]
  user_sim <- as.data.frame(cbind(user_sim, seq(length(user_sim))))
  colnames(user_sim) <- c('Similarity', 'SID')
  user_sim <- user_sim %>%
    dplyr::left_join(unique_songs, by = 'SID') %>%
    dplyr::arrange(desc(Similarity)) %>%
    dplyr::top_n(500, Similarity)
  return(user_sim)
}

# Get average precision of user via song similarity
getSong_Average_Precision<- function(user){
  # Get the visible song in users song list
  songs <- train_data_2 %>%
    filter(UID == user) %>%
    select(SID)

  # If SID is of factor class change to integer
  if (class(songs$SID) == "factor"){
    songs$SID <- as.integer(levels(songs$SID))[songs$SID]
  }

  # Go through songs and get 500 most similar songs
  top500total <- ldply(songs$SID, gettop500simSong) %>%
    anti_join(songs, by = 'SID') %>% # remove songs already in users song list
    distinct() %>%                   # remove duplicates
    arrange(desc(Similarity)) %>%    # order by similarity
    top_n(500, Similarity)           # take top 500

  # Get actual songs from validation datset
  actual.songs <- filter(valid_data, User_ID == unique_users$User_ID[user])

  # Calculate average precision
  avg.Pres <- average_precision_at_k(k=500, actual = actual.songs$Song_ID, predicted = top500total$Song_ID)
  return(avg.Pres)
}

mAP <- mean(pbsapply(seq(nrow(multMat1)), getSong_Average_Precision))

Strategy - Recommend songs by finding similar users and selecting songs in their list of listened songs

Two users are similar if they have listened to many of the same songs. The user-user similarity is calculated in a similar way to the item-item similarity. After each users recommendations the songs are ordered in termes of total plays. The Venn diagram of the strategy is shown below.

The R code to achieve this is as follows:

# User similarity matrix
multMat2 <- sparse_rating_df %*% t(sparse_rating_df)

# Function that recommends songs based on 2 users song list
recommend_by_user <- function(user1, user2){
  # Get song intersection of 2 users
  user1.songs <- train_data %>%
    dplyr::filter(User_ID == user1) %>%
    dplyr::select(Song_ID, Plays)
  user2.songs <- train_data %>%
    dplyr::filter(User_ID == user2) %>%
    dplyr::select(Song_ID, Plays)

  # Get songs in user2, that not in user1
  recommend.songs <- dplyr::anti_join(user2.songs, user1.songs,
                                      by = 'Song_ID') %>%
    dplyr::arrange(desc(Plays)) %>%  # sort by number of plays
    dplyr::select(-Plays)
  return(recommend.songs)
}

getUser_Average_Precision<- function(user){
  # Get top 100 unique users
  user1_sim <- multMat2[user,]
  user1_sim <- as.data.frame(cbind(user1_sim, seq(length(user1_sim))))
  colnames(user1_sim) <- c('Similarity', 'UID')
  user1_sim <- user1_sim %>%
    dplyr::arrange(desc(Similarity)) %>%
    dplyr::top_n(100, Similarity) %>%
    dplyr::left_join(unique_users, by = 'UID')

  # Initialsize empty data frame
  rec.songs <- data.frame()
  i = 1
  while(nrow(rec.songs) < 500){
    # Recommend songs if they have any songs in common (similarity > 0)
    if(user1_sim$Similarity[i] > 0.00000){
      new.songs <- recommend_by_user(user1_sim$User_ID[user], user1_sim$User_ID[i])
      rec.songs <- unique(rbind(rec.songs, new.songs))
    }
    # otherwise choose from top 1000 songs
    else{
      new.songs <- as.data.frame(top1000songs$Song_ID[1:(1000-nrow(rec.songs))+1],
                                 stringsAsFactors = FALSE)
      colnames(new.songs) <- 'Song_ID'
      rec.songs <- unique(rbind(rec.songs, new.songs))
    }
    i = i + 1
  }

  # Get actual songs from validation datset
  actual.songs <- filter(valid_data, User_ID == unique_users$User_ID[user])

  # Calculate averag precision
  avg.Pres <- average_precision_at_k(k=500, actual = actual.songs$Song_ID, predicted = rec.songs$Song_ID)
  return(avg.Pres)
}

mAP <- mean(pbsapply(seq(nrow(multMat2)), getUser_Average_Precision))