Collaborative filtering

• US 8,135,718 B1
• Filed: 02/16/2007
• Issued: 03/13/2012
• Est. Priority Date: 02/16/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Das, Abhinandan S., Garg, Ashutosh, Datar, Mayur
• Primary Examiner(s): Robinson, Greta
• Assistant Examiner(s): Chang, Jeffrey
• Application Number:
  US11/676,264
• Time in Patent Office: 1,852 Days
• Field of Search: 707/1, 707/6, 707/100, 707/101, 707/748, 707/736
• US Class Current: 707/748
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

Systems, methods, and apparatus, including computer program products, for collaborative filtering are provided. A method is provided. The method includes clustering a plurality of entities with respect to one or more latent variables in a probability distribution model of a relationship between a set of entities and a set of items, the probability distribution model comprising a probability distribution of the set of items with respect to the latent variables. The method also includes, as new items are added to the set of items, updating the probability distribution of the set of the items with respect to the latent variables, and generating an updated relationship score for an entity with respect to the set of items based on the entity'"'"'s fractional membership in the clustering with respect to the latent variables and based on the updated probability distribution of the set of the items with respect to the latent variables.

Claims

1. A computer-implemented method comprising:

clustering a plurality of users with respect to one or more latent variables in a probability distribution model of a relationship between a set of users and a set of items, the probability distribution model comprising a probability distribution of the set of items with respect to the latent variables;

as new items are added to the set of items, updating the probability distribution of a current set of items with respect to the latent variables including determining counter values incremented in response to item selections in the current set of items and according to user membership in categories represented by the latent variables and where updating the probability distribution includes calculating, for each category, a fraction of counts for an item relative to all the counter values for items in the particular category; and

generating a relationship score for one or more users with respect to the set of items, each relationship score relating the particular user to a particular item based on the particular user'"'"'s category memberships and based on the updated probability distribution of the set of the items with respect to the latent variables.

2. The method of claim 1, wherein the relationship score is used to generate an item recommendation for a user.

3. The method of claim 1, wherein the probability distribution of the set of items with respect to the latent variables is represented by counts of user clicks on items.

4. The method of claim 3, wherein the user clicks are discounted as a function of time.

5. The method of claim 3, wherein the counts of user clicks on items are normalized across the set of items.

6. The method of claim 1, wherein the relationship score is modified based on a history of other items clicked by the user within a period of time.

7. The method of claim 1, where calculating the updated probability distribution relating items of the set of items to latent variables is represented by:

8. The method of claim 1, where each selection of an item by a user increments one or more category counters by a total count of 1 distributed as a function of member categories of the user that selected the item.

9. The method of claim 1, where counter values are only incremented for associated user item selections occurring within a specified time range.

10. The method of claim 1, where the probability distribution of the set of items with respect to the latent variables is updated as a function of a rate of change in members of the set of items.

11. A computer program product, encoded on a tangible program carrier, operable to cause data processing apparatus to perform operations comprising:

clustering a plurality of users with respect to one or more latent variables in a probability distribution model of a relationship between a set of users and a set of items, the probability distribution model comprising a probability distribution of the set of items with respect to the latent variables;

as new items are added to the set of items, updating the probability distribution of a current set of items with respect to the latent variables including determining counter values incremented in response to item selections in the current set of items and according to user membership in categories represented by the latent variables and where updating the probability distribution includes calculating, for each category, a fraction of counts for an item relative to all the counter values for items in the particular category; and

generating a relationship score for one or more users with respect to the set of items, each relationship score relating the particular user to a particular item based on the particular user'"'"'s category memberships and based on the updated probability distribution of the set of the items with respect to the latent variables.

12. The computer program product of claim 11, wherein the relationship score is used to generate an item recommendation for a user.

13. The computer program product of claim 11, wherein the probability distribution of the set of items with respect to the latent variables is represented by counts of user clicks on items.

14. The computer program product of claim 13, wherein the user clicks are discounted as a function of time.

15. The computer program product of claim 13, wherein the counts of user clicks on items are normalized across the set of items.

16. The computer program product of claim 11, wherein the relationship score is modified based on a history of other items clicked by the user within a period of time.

17. A system comprising:

one or more computers configured to perform operations including;

clustering a plurality of users with respect to one or more latent variables in a probability distribution model of a relationship between a set of users and a set of items, the probability distribution model comprising a probability distribution of the set of items with respect to the latent variables;

as new items are added to the set of items, updating the probability distribution of a current set of items with respect to the latent variables including determining counter values incremented in response to item selections in the current set of items and according to user membership in categories represented by the latent variables and where updating the probability distribution includes calculating, for each category, a fraction of counts for an item relative to all the counter values for items in the particular category; and

generating a relationship score for one or more users with respect to the set of items, each relationship score relating the particular user to a particular item based on the particular user'"'"'s category memberships and based on the updated probability distribution of the set of the items with respect to the latent variables.

18. The system of claim 17, wherein the relationship score is used to generate an item recommendation for a user.

19. The system of claim 17, wherein the probability distribution of the set of items with respect to the latent variables is represented by counts of user clicks on items.

20. The system of claim 19, wherein the user clicks are discounted as a function of time.

21. The system of claim 19, wherein the counts of user clicks on items are normalized across the set of items.

22. The system of claim 17, wherein the relationship score is modified based on a history of other items clicked by the user within a period of time.

23. The system of claim 17, where calculating the updated probability distribution relating items of the set of items to latent variables is represented by:

24. The system of claim 17, where each selection of an item by a user increments one or more category counters by a total count of 1 distributed as a function of member categories of the user that selected the item.

25. The system of claim 17, where counter values are only incremented for associated user item selections occurring within a specified time range.

26. The system of claim 17, where the probability distribution of the set of items with respect to the latent variables is updated as a function of a rate of change in members of the set of items.

27. A computer-implemented method comprising:

identifying data including a set of users that includes as members a plurality of users and a set of items that includes as members a plurality of user selectable items;

calculating an initial overall probability distribution using the set of users, the set of items, and a set of categories representing latent variables, where the overall probability distribution includes a first probability distribution relating the set of users and the set of categories and a second probability distribution relating the set of items and the set of categories;

determining a new second probability distribution relating an updated set of items and the set of categories using selection data relating item selections from users of the set of users and the categories associated with the users;

calculating an overall probability distribution relating users of the set of users and items of the updated set of items using the first probability distribution and the new second probability distribution; and

using the overall probability distribution to recommend one or more items to one or more users of the set of users.

28. The method of claim 27, further comprising:

receiving a request from a first user in the set of users;

identifying one or more recommended items for a first user using the first probability distribution and the new second probability distribution; and

presenting the one or more recommended items to the first user.

29. The method of claim 27, where the new second probability distribution is determined after the first probability distribution and the second probability distribution.

30. The method of claim 27, where determining the new second probability distribution occurs at a greater frequency than determining the first probability distribution.

31. The method of claim 30, where the set of items has a high turnover rate including adding and removing distinct items from the set of items, and the new second probability distribution is determined according to a current membership of the set of items at a time in which the new second probability distribution is determined.

32. The method of claim 27, where determining the new second probability distribution further comprises:

providing one or more counters for each item in the updated item set; and

incrementing one or more counters for an item when the item is selected by a user.

33. The method of claim 32, where incrementing the one or more counters for an item further comprises:

incrementing the one or more counters for an item according to a category membership of the user.

34. The method of claim 33, where each counter value is discounted as a function of time.

35. The method of claim 33, where the probability of selecting a particular item given a particular category is calculated as the count for the item divided by the sum of the counts for the category across all items.

36. The method of claim 27, where a number of categories in the set of categories is less than a number of items in the set of items.

37. The method of claim 32, where the counter values of member categories are incremented according to a first probability distribution relating entities and categories.

38. A computer program product, encoded on a tangible program carrier, operable to cause data processing apparatus to perform operations comprising:

identifying data including a set of users that includes as members a plurality of users and a set of items that includes as members a plurality of user selectable items;

calculating an initial overall probability distribution using the set of users, the set of items, and a set of categories representing latent variables, where the overall probability distribution includes a first probability distribution relating the set of users and the set of categories and a second probability distribution relating the set of items and the set of categories;

determining a new second probability distribution relating an updated set of items and the set of categories using selection data relating item selections from users of the set of users and the categories associated with the users;

calculating an overall probability distribution relating users of the set of users and items of the updated set of items using the first probability distribution and the new second probability distribution; and

using the overall probability distribution to recommend one or more items to one or more users of the set of users.

39. A system comprising:

one or more computers operable to;

identify data including a set of users that includes as members a plurality of users and a set of items that includes as members a plurality of user selectable items;

calculate an initial overall probability distribution using the set of users, the set of items, and a set of categories representing latent variables, where the overall probability distribution includes a first probability distribution relating the set of users and the set of categories and a second probability distribution relating the set of items and the set of categories;

determine a new second probability distribution relating an updated set of items and the set of categories using selection data relating item selections from users of the set of users and the categories associated with the users;

calculate an overall probability distribution relating users of the set of users and items of the updated set of items using the first probability distribution and the new second probability distribution; and

use the overall probability distribution to recommend one or more items to one or more users of the set of users.

40. The system of claim 39, wherein the one or more computers comprise a server operable to interact with the user interface device through a data communication network, and the user interface device is operable to interact with the server as a client.

41. The system of claim 40, wherein the user interface device comprises a personal computer running a web browser or a mobile telephone running a WAP browser.

42. The system of claim 41, wherein the one or more computers comprises one personal computer, and the personal computer comprises the user interface device.

43. The system of claim 39, further operable to:

receive a request from a first user in the set of users;

identify one or more recommended items for a first user using the first probability distribution and the new second probability distribution; and

present the one or more recommended items to the first user.

44. The system of claim 39, where the new second probability distribution is determined after the first probability distribution and the second probability distribution.

45. The system of claim 39, where determining the new second probability distribution occurs at a greater frequency than determining the first probability distribution.

46. The system of claim 45, where the set of items has a high turnover rate including adding and removing distinct items from the set of items, and the new second probability distribution is determined according to a current membership of the set of items at a time in which the new second probability distribution is determined.

47. The system of claim 39, where determining the new second probability distribution further comprises:

providing one or more counters for each item in the updated item set; and

incrementing one or more counters for an item when the item is selected by a user.

48. The system of claim 47, where incrementing the one or more counters for an item further comprises:

incrementing the one or more counters for an item according to a category membership of the user.

49. The system of claim 48, where each counter value is discounted as a function of time.

50. The system of claim 48, where the probability of selecting a particular item given a particular category is calculated as the count for the item divided by the sum of the counts for the category across all items.

51. The system of claim 39, where a number of categories in the set of categories is less than a number of items in the set of items.

52. The system of claim 47, where the counter values of member categories are incremented according to a first probability distribution relating entities and categories.