Method and System for making Recommendation from Binary Data Using Neighbor-Score Matrix and Latent Factors

Abstract

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.

What is claimed is: 
     
         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.