Why Are Douyin and Toutiao So Popular? Unveiling Recommendation System Principles: The Collaborative Filtering Algorithm

The previous article briefly introduced the basic principles and classification of recommendation systems. This article focuses on the principles and implementation of collaborative filtering~

Collaborative Filtering

Collaborative filtering recommends information that users may be interested in by leveraging the preferences of a group of people with similar interests and shared experiences.

Collaborative filtering algorithms make maximum use of the similarity correlations between users or between items, and then make recommendations based on this information. For example, you and one of your friends both like listening to music, and the genres you like are quite similar. Your friend has a high opinion of a certain song that you haven't heard yet. So, couldn't I recommend this song to you?

To implement collaborative filtering, the following 3 steps are needed:

1. Collect user preferences
2. Find similar users or items
3. Compute recommendations

Two common problems that collaborative filtering may encounter due to too small a sample size are:

1. Sparsity problem — because users have made too few ratings, the calculated correlation coefficients are inaccurate
2. Cold start problem — because items have received too few ratings, they have no “right” to enter the recommendation list

Therefore, when recommending for new users and new items, using some more general methods may work better. For example:

• Recommend more movies with extremely high average scores to new users;
• Recommend new movies to people who like similar movies (e.g., those with the same director or actors).

The latter approach requires maintaining an item classification table, which can be based on item metadata or obtained through clustering.

Classification of Collaborative Filtering

1. User-based recommendation (find similar neighbor users through shared tastes and preferences, K-nearest neighbors algorithm; if your friends like it, you might like it too)

2. Item-based recommendation (discover similarity between items and recommend similar items; if you like item A, and C is similar to A, you might also like C)

3. Model-based recommendation (construct a recommendation model based on sample user preference information, then predict recommendations based on real-time user preference information)

Collecting User Preferences

After collecting the raw user preference data, perform preprocessing:

• User behavior identification/combination

In typical applications, we usually extract more than one type of user behavior. Regarding how to combine these different user behaviors, for example, we can divide user behaviors into “view” and “purchase”, etc., and then compute different user / item similarities based on different behaviors.

Similar to Dangdang or JD.com's “People who bought this book also bought …”, “People who viewed this book also viewed …”

• Preference degree weighting

Weight them according to the degree to which different behaviors reflect user preferences, to obtain the user's overall preference for items.

Generally speaking, explicit user feedback has a larger weight than implicit feedback, but it is relatively sparse, since after all only a minority of users provide explicit feedback; at the same time, compared to “view”, “purchase” behavior reflects a greater degree of user preference, but this also varies by application.

• Data denoising and normalization.

1. Denoising: User behavior data is generated while users use the application. It may contain a large amount of noise and user misoperations. We can filter out the noise in the behavior data through classic data mining algorithms, which can make our analysis more precise.
2. Normalization: As mentioned earlier, when computing the user's degree of preference for items, we may need to weight different behavior data. But as one can imagine, the values of different behavior data may differ greatly. For example, a user's view data is bound to be much larger than purchase data. How to unify the data of each behavior into the same value range, so that the overall preference obtained by weighted summation is more precise, requires us to perform normalization. The simplest normalization is to divide each type of data by the maximum value in that type, to ensure that the normalized data values are in the [0,1] range.

• Forming the user preference matrix

Generally it is a two-dimensional matrix, one dimension is the user list, the other is the item list, and the values are the user's preferences for items, generally floating-point values in [0,1] or [-1, 1].

Finding Similar Users or Items

Finding similar users or items: compute the similarity of users or items, and find similar neighbors.

Similarity Computation

Both User CF and Item CF rely on similarity computation, because only by measuring the similarity between users or between items can we find a user's “neighbors” and complete the recommendation.

Similarity can be measured by computing Euclidean distance, Pearson correlation coefficient, Cosine similarity, and Tanimoto coefficient:

• Euclidean Distance

$$ d(x,y)=\sqrt{(∑(xi−yi)^2))} $$

$$ sim(x,y)=\frac{1}{1+d(x,y)} $$

• Pearson Correlation Coefficient

$$ p(x,y) =\frac{∑x_iy_i−n\overline{x}\overline{y}}{(n−1)S_xS_y} =\frac{n∑x_iy_i−∑x_i∑y_i}{\sqrt{n∑x_i^2−(∑x_i)^2}\sqrt{n∑y_i^2−(∑y_i)^2}} $$

• Cosine Similarity

$$ T(x,y) =\frac{x⋅y}{∥x∥^2×∥y∥^2} =\frac{\sum{x_iy_i}}{\sqrt{\sum{x_i^2}}\sqrt{\sum{y_i^2}}} $$

• Tanimoto Coefficient

$$ T(x,y)=\frac{x⋅y}{∥x∥^2+∥y∥^2−x⋅y} =\frac{\sum{xiyi}}{\sqrt{∑x_i^2}+\sqrt{∑y_i^2}−∑x_iy_i} $$

Similar Neighbor Computation

After computing similarity, similar neighbors can be selected through a fixed number of neighbors or threshold-based neighbors.

1. A Fixed Number of K Neighbors

K-neighborhoods: the meaning is quite clear — take the top K in descending order of scores.

Use the “nearest” K users or items as neighbors. As shown in A in the figure below, suppose we want to compute the 5-neighbors of point 1. Then according to the distances between points, we take the nearest 5 points, which are point 2, point 3, point 4, point 7, and point 5. But we can clearly see that this method does not work well for isolated points, because a fixed number of neighbors must be taken. When there are not enough relatively similar points nearby, it is forced to take some not-so-similar points as neighbors, which affects the degree of neighbor similarity. For example, in Figure 1, point 1 and point 5 are actually not very similar.

2. Threshold-Based Neighbors

Threshord-based neighborhood: take those with scores of K or above as neighbors

Unlike the principle of computing a fixed number of neighbors, threshold-based neighbor computation imposes a maximum limit on how far neighbors can be. All points that fall within a region centered on the current point with distance K are taken as neighbors of the current point. The number of neighbors computed by this method is uncertain, but there will not be large errors in similarity. As shown in B in the figure below, starting from point 1, compute neighbors whose similarity is within K, obtaining point 2, point 3, point 4, and point 7. The degree of neighbor similarity computed by this method is better than the previous one, especially in handling isolated points.

What Threshold-based neighborhoods aims to express is “better fewer than shoddy” — the effect is very pronounced when data is sparse.

Based on the different subjects of similarity computation, collaborative filtering recommendation algorithms can be divided into user-based collaborative filtering (UserCF) and item-based collaborative filtering (ItemCF). A comparison of the two is shown in the following table:

Example of user-based collaborative filtering:

User A and User C both like Item 1 and Item 3. The user-based collaborative filtering algorithm considers User A and User C to have similar preferences, so it recommends Item 4, which User C likes, to User A.

Example of item-based collaborative filtering:

Item 1 and Item 3 are both liked by User A and User B. The item-based collaborative filtering algorithm considers Item 1 and Item 3 to be of similar types. Because User C likes Item 1, Item 3 is recommended to User C.

Computing Recommendations

Recommendation Based on User Similarity

This is actually the computation process of the KNN algorithm.

For similarity computation, it is best to use the Pearson correlation coefficient and threshold-based neighbors to select similar users.

Recommendation Based on Item Similarity

As shown in the following example:

The table above is a user-movie rating table. If I want to predict User 5's rating of Movie 1 in order to make a recommendation decision (recommend only if the rating is greater than 3.5), we can do this:

Separately compute the similarity between Movie 1 and Movie 2, Movie 3, and other movies (preprocess the ratings if necessary to eliminate data differences), denoted as $$ sim(1,m) $$ Take two similarities: the largest and the second largest, which are 0.59,0.410.59,0.41 respectively. These are the similar neighbors. Then through weighted computation, User 5's predicted rating for Movie 1 is 2.6, and the recommendation decision is: do not recommend.

That's the basic principle and implementation of the collaborative filtering algorithm. Douyin and Toutiao may not necessarily use collaborative filtering, but this algorithm is essential for getting started with recommendation systems. For basically simple systems, using collaborative filtering is enough.

Welcome to Discuss

I have compiled a series of technical articles and materials. Reply with linux, flutter, c#, netcore, android, java, python, etc. in the backend of the WeChat official account “Programming Lab” to obtain related technical articles and materials. Meanwhile, if you have any questions, you can leave a message in the official account backend~