Understanding k-nearest Neighbors

A nearest neighbor is the entity (a data point, in the case of a dataset) that is closest to the entity under consideration. Two entities are close if the distance between them is small.

We can intuitively conclude that users A and B are more similar to each other in terms of weight when compared to C.

The “distance” between user A and B can be measured as:

This kind of distance between users is calculated similarly to the way the distance between two points is calculated.

In the preceding table, if we were measuring to see the similarity between cars using the traditional “distance” metric , we might conclude that models A and C are most similar to each other (even though their number of gears are different). Yet intuitively we know that B and C are more similar to each other than A and C, because they have identical number of gears and their max attainable speeds are similar.

The discrepancy highlights the issue of scale of variables, where one variable has a very high magnitude when compared to the other variable. To get around this issue, typically we would normalize the variables before proceeding further with distance calculations. Normalizing variables is a process of bringing all the variables to a uniform scale.

Steps like these help normalize variables, thereby preventing the issues with scaling.

Once the distance of a data point to other data points is obtained—in the case of recommender systems, that is, once the nearest items to a given item are identified—the system will recommend these items to a user if it learns that the user has historically liked a majority of the nearest neighborhood items.

The k in k-nearest neighbors stands for the number of nearest neighbors to consider while taking a majority vote on whether the user likes the nearest neighbors or not. For example, if the user likes 9 out of 10 (k) nearest neighbors to an item, we’ll recommend the item to user. Similarly, if the user likes only 1 out of 10 nearest neighbors of the item, we’ll not recommend the item to user (because the liked items are in minority).

Neighborhood-based analysis takes into account the way in which multiple users can collaboratively help predict whether a user might like something or not.

With this background, we’ll move on and look at the evolution of recommender system algorithms.

Working Details of User-Based Collaborative Filtering

User-based refers, of course, to something based on users. Collaborative means using some relation (similarity) between users. And filtering refers to filtering out some users from all users.

Euclidian Distance

Calculating the Euclidian distance of Claudia with every other user can be done as follows (available in “Eucledian distance” sheet of “ubcf.xlsx” file in github):

We aren’t seeing the complete picture due to space and formatting constraints, but essentially the same formula is applied across columns.

The distance of every other user to Claudia for each movie is as follows:

Note that the overall distance value is the average of all the distances where both users have rated a given movie. Given that Lisa Rose is the user who has the least overall distance with Claudia, we will consider the rating provided by Lisa as the rating that Claudia is likely to give to the movie Lady in the Water.

One major issue to be considered in such a calculation is that some users may be soft critics and some users may be harsher critics. Users A and B may have implicitly had similar experiences watching a given movie , but explicitly their ratings might be different.

Normalizing for a User

Given that users differ in their levels of criticism, we need to make sure that we get around that problem. Normalization can help here.

We could normalize for a user as follows:

1. 1.

   Take the average rating across all movies of a given user.

    
2. 2.

   Take the difference between each individual movie and the average rating of the user.

    

By taking the difference between a rating of an individual movie and the average rating of the user, we would know whether they liked a movie more than the average movie they watch, less than the average movie they watch, or equal to the average movie they watch.

Let’s look at how this is done:

The formulas for the above are as follows (available in “Normalizing user” sheet of “ubcf.xlsx” file in github):

Now that we have normalized for a given user, we calculate which user is most similar to Claudia the same way we calculated user similarity earlier. The only difference is that now we will calculate distance based on normalized ratings, not the original ratings:

We can see that Lisa Rose is still the least distant (or closest, or most similar) user to Claudia Puig. Lisa rated Lady in the Water 0.50 units lower than her average movie rating of 3.00, which works out to ~8% lower than her average rating. Given that Lisa is the most similar user to Claudia, we would expect Claudia’s rating to likewise be 8% less than her average rating, which works out to the following:

3.5 × (1 – 0.5 / 3) = 2.91

Issue with Considering a Single User

So far, we have considered the single user who is most similar to Claudia. In practice, more is always better—that is, identifying the weighted average rating that k most similar users to a given user give is better than identifying the rating of the most similar user.

However, we need to note that not all k users are equally similar. Some are more similar, and others are less similar. In other words, some users’ ratings should be given more weightage, and other users’ ratings should be given less weightage. But using the distance-based metric, there is no easy way to come up with a similarity metric.

Cosine similarity as a metric comes in handy to solve this problem.

Cosine Similarity

We can look at cosine similarity by going through an example. Consider the following matrix:

	Movie1	Movie2	Movie3
User1	1	2	2
User2	2	4	4

In the preceding table, we see that both users’ ratings are highly correlated with each other. However, there is a difference in the magnitude of ratings.

If we were to compute Euclidian distance between the two users, we would notice that the two users are very different from each other. But we can see that the two users are similar in the direction (trend) of their ratings, though not in the magnitude of their ratings. The problem where the trend of users is similar but not the magnitude can be solved using cosine similarity between the users.

Cosine similarity between two users is defined as follows:

A and B are the vectors corresponding to user 1 and user 2 respectively.

Let’s look how similarity is calculated for the preceding matrix:

• Numerator of the given formula = (1 × 2 + 2 × 4 + 2 × 4) = 18

• Denominator of the given formula =

  

  ×

  

• Similarity = 18 / 18 = 1.

Based on the given formula, we can see that, on the basis of cosine similarity, we are in a position to assign high similarity to users that are directionally correlated but not necessarily in magnitude.

Cosine similarity on the rating matrix that we originally calculated (in the Euclidian distance calculation) earlier would be calculated in a similar way to how we calculated the preceding formula . The steps for cosine similarity calculation remain the same:

1. 1.

   Normalize users.

    
2. 2.

   Calculate the cosine similarity of rest of the users for a given user.

    

To illustrate how we calculate cosine similarity, let’s calculate the similarity of Claudia with every other user (available in “cosine similarity” sheet of “ubcf.xlsx” file in github):

1. 1.
   Normalize user ratings:

   

    
2. 2.
   Calculate the numerator part of the cosine similarity calculation:

   

   The numerator would be as follows:

   

    
3. 3.
   Prepare the denominator calculator of cosine similarity:

   

    
4. 4.
   Calculate the final cosine similarity, as follows:

   

    

We now have a similarity value that is associated between –1 and +1 that gives a score of similarity for a given user.

We have now overcome the issue we faced when we had to consider the ratings given by multiple users in predicting the rating that a given user is likely to give to a movie. Users who are more similar to a given user can now be calculated.

Now the problem of predicting the rating that Claudia is likely to give to the movie Lady in the Water movie can be solved in the following steps:

1. 1.

   Normalize users.

    
2. 2.

   Calculate cosine similarity.

    
3. 3.

   Calculate the weighted average normalized rating.

    

Let’s say we are trying to predict the rating by using the two most similar users instead of one. We would follow these steps:

1. 1.

   Identify the two most similar users who have also given a rating to the movie Lady in the Water.

    
2. 2.

   Calculate the weighted average normalized rating that they gave to the movie.

    

In this case, Lisa and Mick are the two most similar users to Claudia who have rate Lady in the Water. (Note that even though Toby is the most similar user, he has not rated Lady in the Water and so we cannot consider him for rating prediction.)

Weighted Average Rating Calculation

Let’s look at the normalized rating given and the similarity of the two most similar users:

	Similarity	Normalized rating
Lisa Rose	0.47	–0.5
Mick LaSalle	0.56	0.17

The weighted average rating would now be as follows:

(0.47 × –0.5 + 0.56 × 0.17) / (0.47 + 0.56) = –0.14

Potentially, Claudia’s average rating would now be reduced by 0.14 to come up with the predicted rating of Claudia for the movie Lady in the Water.

Another way to come up with weighted average rating is based on the percent over average rating, as follows:

	Similarity	Normalized rating	Average rating	% avg rating
Lisa Rose	0.47	–0.5	3	–0.5 / 3 = –0.16
Mick LaSalle	0.56	0.17	2.83	0.17 / 2.83 = 0.06

Weighted average normalized rating percentage would now be as follows:

(0.47 × –0.16 + 0.56 × 0.06) / (0.47 + 0.56) = –0.04

Thus, the average rating of Claudia can potentially be reduced by 4% to come up with the predicted rating for the movie Lady in the Water.

Choosing the Right Approach

In recommender systems, there is no fixed technique that is proven to always work. This calls for a typical train, validate, and test scenario to come up with the optimal parameter combination .

The parameter combination that can be tested is as follows:

• Optimal number of similar users to be considered

• Optimal number of common movies rated together by users before a user is eligible to be considered for similar user calculation

• Weighted average rating calculation approach (based on percentage or on absolute value)

We can iterate through multiple scenarios of various combinations of the parameters, calculate the test dataset accuracy, and decide that the combination that gives the least error rate is the optimal combination for the given dataset.

Calculating the Error

There are multiple ways of calculating , and the preferred method varies by business application. Let’s look at two cases:

• Mean squared error (MSE) of all predictions made on the test dataset

• Number of recommended items that a user bought in the next purchase

Note that although MSE helps in building the algorithm, in practice we might be measuring our model’s performance as a business-related outcome, as in the second case.

Item-Based Collaborative Filtering

Given that the number of computations is an issue in UBCF, we will modify the problem so that we observe the similarity between items and not users. The idea behind item-based collaborative filtering (IBCF) is that two items are similar if the ratings that they get from the same users are similar. Given that IBCF is based on items and not on user similarity, it doesn’t have the problem of performing billions of computations.

Let’s assume that there are a total of 10,000 movies in a database and 1 million customers attracted to the site. In this case, if we perform UBCF, we would be performing ~500 billion similarity calculations. But using IBCF, we would be performing 9,999 × 5,000 = ~ 50 million similarity calculations.

We can see that the number of similarity calculations increases exponentially as the number of customers grows. However, given that the number of items (movie titles, in our case) is not expected to experience the same growth rate as the number of customers, in general IBCF is less computationally sensitive than UBCF.

The way in which IBCF is calculated and the techniques involved are very similar to UBCF. The only difference is that we would work on a transposed form of the original movie matrix we saw in the previous section. This way, the rows are not of users, but of movies.

Note that although IBCF is better than UBCF in terms of computation, the number of computations is still very high.

Implementing Collaborative Filtering in R

In this code, we have reshaped our data so that it can be converted into a realRatingMatrix class that gets consumed by the Recommender function to provide the missing value predictions.

Implementing Collaborative Filtering in Python

Working Details of Matrix Factorization

Although user-based or item-based collaborative filtering methods are simple and intuitive, matrix factorization techniques are usually more effective because they allow us to discover latent features underlying the interactions between users and items.

In matrix factorization, if there are U users, each user is represented in K columns, thus we have a U × K user matrix. Similarly, if there are D items, each item is also represented in K columns, giving us a D × K matrix.

A matrix multiplication of the user matrix and the transpose of the item matrix would result in the U × D matrix, where U users may have rated on some of the D items.

The K columns could essentially translate into K features, where a higher or lower magnitude in one or the other feature could give us an indication of the type or genre of the item. This gives us the ability to know the features that a user would give a higher weightage to or the features that a user might not like. Essentially, matrix factorization is a way to represent users and items in such a way that the probability of a user liking or purchasing an item is high if the features that correspond to an item are the features that the user gives a higher weightage to.

Our task is to predict the missing values in the Actual column, which indicate that the user has not rated the movie yet.

The preceding objective and constraint can be specified as an optimization scenario in Solver, as follows:

Note that once we optimize for the given objective and constraint, the optimal values of weights in P and Q matrices are arrived at and are as follows:

Implementing Matrix Factorization in Python

Notice that the P matrix and Q matrix are obtained through Excel’s Solver, which essentially runs gradient descent in the back end. In other words, we are deriving the weights in a manner similar to the neural networks–based approach, where we are trying to minimize the overall squared error.

The function Embedding helps in creating vectors similar to the way we converted a word into a lower-dimensional vector in Chapter 8.

Now that the model is built, let’s extract the weights of the User and Movie matrices (P and Q matrices):

# User matrix

model.get_weights()[0]

# Movie matrix

model.get_weights()[1]

Implementing Matrix Factorization in R

Although matrix factorization can be implemented using the kerasR package, we will use the recommenderlab package (the same one we worked with for collaborative filtering).

The user matrix can thus be accessed as fsvd$U, and the item matrix by fsvd$V. The parameters are the learning rate and the epochs parameters we learned about in Chapter 7.

Summary