Method and System for making Recommendation from Binary Data Using Neighbor-Score Matrix and Latent Factors
One embodiment is a method executed by a computer system that applies collaborative filtering to provide a recommendation to a user. The method includes retrieving a binary matrix that includes rows and columns of binary data for preferences of users on items; applying a neighborhood-based approach to convert the binary matrix into a neighbor-score matrix; applying a factorization to approximate the neighbor-score matrix with a product of lower rank matrices; calculating a user factor and an item factor based on the factorization; calculating scores for user-item pairs by computing a dot product between the user factor and the item factor; sorting the scores of the user-item pairs to generate the recommendation to the user; and providing the recommendation to a general-purpose computer of the user.
1 . A method for providing a recommendation to a user, the method comprising:
obtaining, by a computer system, a preference matrix (R) representing a plurality of preferences between a set of users and a set of items, wherein an entry in the preference matrix (R) for a user and an item indicates whether the user expressed preference for the item;
obtaining, by the computer system, a neighbor-score matrix (S) from the preference matrix (R) by computing neighbor scores for the set of users and the set of items, wherein a neighbor score for a particular user and a particular item in the neighbor-score matrix (S) represents user-user similarity between preferences of the particular user and preferences of other users who have expressed preferences for the particular item in the preference matrix (R), or item-item similarity between preferences for the particular item and preferences for other items that the particular user has expressed preferences for in the preference matrix (R);
determining a set of user factors and a set of item factors by applying a decomposition method to the neighbor-score matrix (S), a user factor representing a user in a latent space and an item factor representing an item in the latent space;
generating recommendations for one or more users and items from the set of user factors and the set of item factors;
approximating, by the computer system, an item factor for a new item v by:
V r ( v ,:)≈ S (:, v ) T U r
where S(:, v) is a neighbor-score vector for the new item v indicating neighbor scores for the set of users and the new item v, U r are the set of user factors for the set of users, and V r (v, :) is the item factor for the new item v; and
generating recommendations for the new item v from the item factor for the new item v and the set of user factors.
2 . The method of claim 1 , wherein determining the set of user factors and the set of item factors comprises applying singular value decomposition (SVD) as the decomposition method to the neighbor-score matrix (S).
3 . The method of claim 1 , wherein generating the recommendations for the one or more users and items comprises performing a dot product between a user factor for a respective user and an item factor for a respective item in the one or more users and items.
4 . The method of claim 1 , wherein obtaining the neighbor-score matrix (S) and determining the set of user factors and the set of item factors comprises:
partitioning, by the computer system, the set of users into blocks of size N b smaller than a number of the set of users;
for each block, iteratively calculating an N b ×M neighbor score matrix, where M indicates a number of the items in the block; and
for each block, performing the decomposition method to include user factors for the users in the block.
5 . The method of claim 4 , further comprising, for each block:
storing only a subset of p neighbor scores for a user in the block that are above a predetermined value or proportion.
6 . The method of claim 1 , further comprising:
approximating, by the computer system, the user factor for a new user u by:
U r ( u ,:)≈ S ( u ,:) V r
where S(u,:) is a neighbor-score vector for the new user u indicating neighbor scores for the new user u and the set of items, V r are the set of item factors for the set of items, and U r (u, :) is the user factor for the new user u; and
generating recommendations for the new user u from the user factor for the new user u and the set of item factors.
7 . The method of claim 1 , further comprising:
responsive to determining that a number of new items is above a predetermined threshold, updating the neighbor-score matrix (S) with neighbor scores for the new items; and
updating the set of user factors and the set of item factors by applying the decomposition method to the updated neighbor-score matrix (S).
8 . The method of claim 1 , wherein the entry in the preference matrix (R) for the user and the item is a non-zero value if the user interacted with the item, and zero otherwise.
9 . A method for providing a recommendation to a user, the method comprising:
obtaining, by a computer system, a preference matrix (R) representing a plurality of preferences between a set of users and a set of items, wherein an entry in the preference matrix (R) for a user and an item indicates whether the user expressed preference for the item;
obtaining, by the computer system, a neighbor-score matrix (S) from the preference matrix (R) by computing neighbor scores for the set of users and the set of items, wherein a neighbor score for a particular user and a particular item in the neighbor-score matrix (S) represents user-user similarity between preferences of the particular user and preferences of other users who have expressed preferences for the particular item in the preference matrix (R), or item-item similarity between preferences for the particular item and preferences for other items that the particular user has expressed preferences for in the preference matrix (R);
determining a set of user factors and a set of item factors by applying a decomposition method to the neighbor-score matrix (S), a user factor representing a user in a latent space and an item factor representing an item in the latent space;
generating recommendations for one or more users and items from the set of user factors and the set of item factors;
approximating, by the computer system, the user factor for a new user u by:
U r ( u ,:)≈ S ( u ,:) V r
where S(u,:) is a neighbor-score vector for the new user u indicating neighbor scores for the new user u and the set of items, V r are the set of item factors for the set of items, and U r (u, :) is the user factor for the new user u; and
generating recommendations for the new item v from the user factor for the new user u and the set of item factors.
10 . The method of claim 9 , wherein determining the set of user factors and the set of item factors comprises applying singular value decomposition (SVD) as the decomposition method to the neighbor-score matrix (S).
11 . The method of claim 9 , wherein generating the recommendations for the one or more users and items comprises performing a dot product between a user factor for a respective user and an item factor for a respective item in the one or more users and items.
12 . The method of claim 9 , wherein obtaining the neighbor-score matrix (S) and determining the set of user factors and the set of item factors comprises:
partitioning, by the computer system, the set of users into blocks of size N b smaller than a number of the set of users;
for each block, iteratively calculating an N b ×M neighbor score matrix, where M indicates a number of the items in the block; and
for each block, performing the decomposition method to include user factors for the users in the block.
13 . The method of claim 12 , further comprising, for each block:
storing only a subset of p neighbor scores for a user in the block that are above a predetermined value or proportion.
14 . The method of claim 9 , further comprising:
approximating, by the computer system, the item factor for a new item v by:
V r ( v ,:)≈ S (:, v ) T U r
where S(:, v) is a neighbor-score vector for the new item v indicating neighbor scores for the set of users and the new item v, U r are the set of user factors for the set of users, and V r (v, :) is the item factor for the new item v; and
generating recommendations for the new item v from the item factor for the new item v and the set of user factors.
15 . The method of claim 9 , further comprising:
responsive to determining that a number of new users is above a predetermined threshold, updating the neighbor-score matrix (S) with neighbor scores for the new users; and
updating the set of user factors and the set of item factors by applying the decomposition method to the updated neighbor-score matrix (S).
16 . The method of claim 9 , wherein the entry in the preference matrix (R) for the user and the item is a non-zero value if the user interacted with the item, and zero otherwise.