Method and apparatus for item recommendation using automated collaborative filtering

• US 6,041,311 A
• Filed: 01/28/1997
• Issued: 03/21/2000
• Est. Priority Date: 06/30/1995
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lashkari, Yezdezard Z., McNulty, John E., Chislenko, Alexander
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Jeanty, Romain
• Application Number:
  US08/789,758
• Time in Patent Office: 1,148 Days
• Field of Search: 395/61, 395/183, 395/52, 705/7, 705/27, 705/8, 705/9, 364/401, 364/419, 707/102
• US Class Current: 705/26.7
• 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/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0204 Market segmentation
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions
• CPC Class Codes: G06Q 30/0631 Item recommendations
• CPC Class Codes: H04N 21/252 Processing of multiple end-users' preferences to derive collaborative data
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method for recommending items to users using automated collaborative filtering stores profiles of users relating ratings to items in memory. Profiles of items may also be stored in memory, the item profiles associating users with the rating given to the item by that user or inferred for the user by the system The user profiles include additional information relating to the user or associated with the rating given to an item by the user. Similarity factors with respect to other users, and confidence factors associated with the similarity factors, are calculated for a user and these similarity factors, in connection with the confidence factors, are used to select a set of neighboring users. The neighboring users are weighted based on their respective similarity factors, and a rating for an item contained in the domain is predicted. In one embodiment, items in the domain have features. In this embodiment, the values for features can be clustered, and the similarity factors incorporate assigned feature weights and feature value cluster weights.

Claims

1. A method for operating a machine to recommend an item to one of a plurality of users, the item not yet rated by the user, the method comprising the steps of:

(a) storing, using the machine, a user profile in a memory for each of the plurality of users, wherein at least one of the user profiles includes a plurality of values, one of the plurality of values representing a rating given to one of a plurality of items by the user and another of the plurality of values representing additional information;

(b) calculating, using the machine, for the user, a plurality of similarity factors responsive to both ratings given to items by the user and the additional information, each of the plurality of similarity factors representing a similarity between the user and another one of the plurality of users;

(c) selecting, using the machine, for the user, a plurality of neighboring users based on the similarity factors, the selecting step comprising the steps of, for each of the plurality of users;

(c1) comparing associated similarity factors for the user and each one of the plurality of users; and

(c2) choosing said each one of the plurality of users as one of the neighboring users if a difference between the associated similarity factors exceeds a predetermined threshold value;

(d) assigning, using the machine, a weight to each of the neighboring users; and

(e) recommending, using the machine, at least one of the plurality of items to the user based on the weights assigned to the plurality of neighboring users and ratings given to the plurality of items by the plurality of neighboring users.

2. The method of claim 1 wherein step (a) further comprises:

storing, using the machine, a user profile in a memory for each of the plurality of users, wherein at least one of the user profiles includes a plurality of values, one of the plurality of values representing a rating given to one of a plurality of items by the user and another of the plurality of values representing information relating to the given ratings.

3. The method of claim 1 wherein step (a) further comprises:

storing, using the machine, a user profile in memory for each of the plurality of users, wherein at least one of the user profiles includes a plurality of values, one of the plurality of values representing a rating given to one of a plurality of items by the user and another of the plurality of values representing information about the user.

4. The method of claim 1 wherein step (a) further comprises sub-steps of:

i) storing, in the machine, a user profile in a memory for each of the plurality of users, wherein at least one of the user profiles includes a plurality of values, one of the plurality of values representing a rating given to one of a plurality of items by the user and another of the plurality of values representing additional information; and

ii) creating, using the machine, a confidence factor for one of the given ratings based on the additional information.

5. The method of claim 1 wherein step (c) further comprises:

calculating, using the machine, for a user, a plurality of similarity factors and a plurality of similarity confidence factors, each of the plurality of similarity factors representing a similarity between the user and another one of the plurality of users, and each of the similarity confidence factors representing possible imprecision in the associated similarity factor.

6. The method claim 5 wherein step (d) further comprises selecting, using the machine, for the user, a plurality of neighboring users from the plurality of other users based on the similarity factors and the similarity confidence factors.

7. The method of claim 5 wherein step (e) further comprises:

assigning, using the machine, a weight to each of the neighboring users, wherein the weight is the similarity confidence factor.

8. The method of claim 5 wherein step (e) further comprises:

i) recommending, using the machine, at least one of a plurality of items to the user based on the weights assigned to the plurality of neighboring users and the ratings given to the item by the plurality of neighboring users; and

ii) generating, using the machine, a recommendation confidence factor based on the similarity confidence factors.

9. The method of claim 1 wherein step (c) further comprises:

calculating, using the machine, for a user, a plurality of similarity factors based on the ratings given to items by users and the additional information associated with the given ratings, each of the plurality of similarity factors representing a similarity between the user and another one of the plurality of users.

10. The method of claim 1 wherein the step of storing a user profile further comprises:

i) inferring, using the machine, a user'"'"'s rating for one of the plurality of items based on the user'"'"'s behavior;

ii) updating, using the machine, the user'"'"'s profile with the inferred rating; and

iii) calculating, using the machine, for the user a plurality of similarity factors, each of the plurality of similarity factors representing a similarity between the user and another user.

11. The method of claim 10 wherein the behavior of the user used to infer a user'"'"'s rating includes, at least one of Web sites for which the user has created bookmarks, and a length of time that the user views a particular Web page.

12. The method of claim 1 further comprising the step of storing, using the machine, an item profile in a memory for each of the plurality of items, wherein at least one of the item profiles includes a plurality of values, at least one of the plurality of values representing a rating given to the item by one of the plurality of users.

13. The method of claim 12 wherein the step of storing a user profile further comprises:

i) inferring, using the machine, a user'"'"'s rating for one of the plurality of items based on the user'"'"'s behavior;

ii) retrieving, using the machine, the item profile;

iii) determining, using the machine, from the item profile, other users having ratings for the item; and

iv) calculating, using the machine, a similarity factor between the user and each of the plurality of other users that have also rated the item.

14. The method of claim 1 wherein step (d) further comprises selecting, using the machine, for the user, at least one neighboring user based on the additional information.

15. The method of claim 1 wherein step (e) further comprises:

i) recommending, using the machine, at least one of the plurality of items to the user based on the weights assigned to the plurality of neighboring users and the ratings given to the item by the plurality of neighboring users; and

ii) generating, using the machine, a recommendation confidence factor based on the additional information associated with the ratings given to the item.

16. The method of claim 1 wherein, in the step of selecting a plurality of neighboring users, if one of the plurality of users has cumulative item ratings, it is not selected as a neighboring user.

17. The method of claim 1 wherein, in the step of assigning a weight to each of the neighboring users, similar users are weighted more heavily that less similar users.

18. The method of claim 1 wherein, in the step of assigning a weight to each of the neighboring users, the weight is based on a confidence factors.

19. The method of claim 1 further comprising a step of grouping the plurality of items to define a plurality of groups, wherein each of the groups have a rating based on the ratings of the items defining the groups, and wherein, in the step of calculating, for a user, a plurality of similarity factors, the similarly factors are based on the ratings of the groups.

24. A computer readable medium having computer executable instructions stored therein, said instructions being executed by a computer for performing the steps of claim 1.

20. A computer-implemented method for operating a machine to recommend an item to one of a plurality of users, the item not yet rated by the user, the method comprising the steps, performed by the machine, of:

(a) storing a user profile in a memory for each of the plurality of users, wherein at least one of the user profiles includes a plurality of values, one of the plurality of values representing a rating given to one of a plurality of items by the user and another of the plurality of values representing additional information;

(b) calculating for the user, a plurality of similarity factors responsive to both ratings given to items by the user and the additional information, each of the plurality of similarity factors representing a similarity between the user and another one of the plurality of users;

(c) selecting for the user, a plurality of neighboring users based on the similarity factors, the selecting step comprising the steps of, for each of the plurality of users;

(c1) comparing associated similarity factors for the user and each one of the plurality of users; and

(c2) choosing said each one of the plurality of users as one of the neighboring users if both a difference between the associated similarity factors is less than a first predetermined threshold and a total number of selected neighboring users is less than a second predetermined threshold;

(d) assigning a weight to each of the neighboring users; and

(e) recommending at least one of the plurality of items to the user based on the weights assigned to the plurality of neighboring users and ratings given to the plurality of items by the plurality of neighboring users.

25. A computer readable medium having computer executable instructions stored therein, said instructions being excuted by a computer for performing the steps of claim 20.

21. A computer-implemented method for operating a machine to recommend an item to one of a plurality of users, the item not yet rated by the user, the method comprising the steps, performed by the machine, of:

(a) storing a user profile in a memory for each of the plurality of users, wherein at least one of the user profiles includes a plurality of values, one of the plurality of values representing a rating given to one of a plurality of items by the user and another of the plurality of values representing additional information;

(b) calculating for the user, a plurality of similarity factors responsive to both ratings given to items by the user and the additional information, each of the plurality of similarity factors representing a similarity between the user and another one of the plurality of users;

(c) selecting for the user, a plurality of neighboring users based on the similarity factors, the selecting step comprising the steps of, for each of the plurality of users;

(c1) comparing associated similarity factors for the user and each one of the plurality of users; and

(c2) choosing said one of the plurality of users as one of the neighboring users if both a difference between the associated similarity factors is less than a first predetermined threshold and a confidence factor determined for the associated similarities factors is greater than a second predetermined threshold;

(d) assigning a weight to each of the neighboring users; and

(e) recommending at least one of the plurality of items to the user based on the weights assigned to the plurality of neighboring users and ratings given to the plurality of items by the plurality of neighboring users.

26. A computer readable medium having computer executable instructions stored therein, said instructions being excuted by a computer for performing the steps of claim 21.

22. A computer-implemented method for operating a machine to recommend an item to one of a plurality of users, the item not yet rated by the user, the method comprising the steps, performed by the machine, of:

(a) storing a user profile in a memory for each of the plurality of users, wherein at least one of the user profiles includes a plurality of values, one of the plurality of values representing a rating given to one of a plurality of items by the user and another of the plurality of values representing additional information;

(b) calculating for the user, a plurality of similarity factors responsive to both ratings given to items by the user and the additional information, each of the plurality of similarity factors representing a similarity between the user and another one of the plurality of users;

(c) selecting for the user, a plurality of neighboring users based on the similarity factors, the selecting step comprising the steps of;

(c1) defining a domain of items to be recommended; and

(c2) choosing each one of said users as one of the neighboring users unless said one user has less than a predetermined number of ratings of the items in the domain;

(d) assigning a weight to each of the neighboring users; and

(e) recommending at least one of the plurality of items to the user based on the weights assigned to the plurality of neighboring users and ratings given to the plurality of items by the plurality of neighboring users.

27. A computer readable medium having computer executable instructions stored therein, said instructions being excuted by a computer for performing the steps of claim 22.

23. A computer-implemented method for operating a machine to recommend an item to one of a plurality of users, the item not yet rated by the user, the method comprising the steps, performed by the machine, of:

(a) storing a user profile in a memory for each of the plurality of users, wherein at least one of the user profiles includes a plurality of values, one of the plurality of values representing a rating given to one of a plurality of items by the user and another of the plurality of values representing additional information;

(b) grouping the plurality of items into a plurality of groups, wherein each of the groups has a rating based on the ratings of the items contained within said each group, wherein the grouping step comprises the steps of;

(b1) randomly assigning all items to a number of initial groups;

(b2) for each of the initial groups, determining a centroid of the ratings for the items assigned to the initial group;

(b3) for each item, moving the item to the group with a centroid of ratings closest to its rating; and

(b4) repeating steps (b1) through (b3) until both a certain number of iterations has been performed and distances, between all group centroids and items assigned to each of the groups, are below a predetermined threshold;

(c) calculating for the user, a plurality of similarity factors in response to ratings given to items by the user, the additional information, and the ratings of the groups, wherein each of the plurality of similarity factors represents a similarity between the user and another one of the plurality of users;

(d) selecting for the user, a plurality of neighboring users based on the similarity factors;

(e) assigning a weight to each of the neighboring users; and

(f) recommending at least one of the plurality of items to the user based on the weights assigned to the plurality of neighboring users and ratings given to the plurality of items by the plurality of neighboring users.

28. A computer readable medium having computer executable instructions stored therein, said instructions being excuted by a computer for performing the steps of claim 23.

29. A Computer-implemented apparatus for recommending an item to one of a plurality of users, the item not yet rated by the user, the apparatus comprising:

(a) a processor; and

(b) a memory connected to the processor and storing computer executable instructions therein;

(c) wherein the processor, in response to execution of the instructions;

(c1) stores, in the memory, a user profile for each of the plurality of users, wherein at least one of the user profiles includes a plurality of values, one of the plurality of values representing a rating given to one of a plurality of items by the user and another of the plurality of values representing additional information;

(c2) calculates, for the user, a plurality of similarity factors responsive to both ratings given to items by the user and the additional information, each of the plurality of similarity factors representing a similarity between the user and another one of the plurality of users;

(c3) selects for the user, a plurality of neighboring users based on the similarity factors, by;

(c3a) comparing associated similarity factors for the user and each one of the plurality of users; and

(c3b) choosing said each one of the plurality of users as one of the neighboring users if a difference between the associated similarity factors exceeds a predetermined threshold value;

(d) assigns a weight to each of the neighboring users; and

(e) recommends at least one of the plurality of items to the user based on the weights assigned to the plurality of neighboring users and ratings given to the plurality of items by the plurality of neighboring users.

30. A Computer-implemented apparatus for recommending an item to one of a plurality of users, the item not yet rated by the user, the apparatus comprising:

(a) a processor; and

(b) a memory connected to the processor and storing computer executable instructions therein;

(c) wherein the processor, in response to execution of the instructions;

(c1) stores, in the memory, a user profile for each of the plurality of users, wherein at least one of the user profiles includes a plurality of values, one of the plurality of values representing a rating given to one of a plurality of items by the user and another of the plurality of values representing additional information;

(c2) calculates, for the user, a plurality of similarity factors responsive to both ratings given to items by the user and the additional information, each of the plurality of similarity factors representing a similarity between the user and another one of the plurality of users;

(c3) selects for the user, a plurality of neighboring users based on the similarity factors, by;

(c3a) comparing associated similarity factors for the user and each one of the plurality of users; and

(c3b) choosing said each one of the plurality of users as one of the neighboring users if both a difference between the associated similarity factors is less than a first predetermined threshold and a total number of selected neighboring users is less than a second predetermined threshold;

(d) assigns a weight to each of the neighboring users; and

(e) recommends at least one of the plurality of items to the user based on the weights assigned to the plurality of neighboring users and ratings given to the plurality of items by the plurality of neighboring users.

31. A Computer-implemented apparatus for recommending an item to one of a plurality of users, the item not yet rated by the user, the apparatus comprising:

(a) a processor; and

(b) a memory connected to the processor and storing computer executable instructions therein;

(c) wherein the processor, in response to execution of the instructions;

(c1) stores, in the memory, a user profile for each of the plurality of users, wherein at least one of the user profiles includes a plurality of values, one of the plurality of values representing a rating given to one of a plurality of items by the user and another of the plurality of values representing additional information;

(c2) calculates, for the user, a plurality of similarity factors responsive to both ratings given to items by the user and the additional information, each of the plurality of similarity factors representing a similarity between the user and another one of the plurality of users;

(c3) selects for the user, a plurality of neighboring users based on the similarity factors, by;

(c3a) comparing associated similarity factors for the user and each one of the plurality of users; and

(c3b) choosing said one of the plurality of users as one of the neighboring users if both a difference between the associated similarity factors is less than a first predetermined threshold and a confidence factor determined for the associated similarities factors is greater than a second predetermined threshold;

(d) assigns a weight to each of the neighboring users; and

(e) recommends at least one of the plurality of items to the user based on the weights assigned to the plurality of neighboring users and ratings given to the plurality of items by the plurality of neighboring users.

32. A Computer-implemented apparatus for recommending an item to one of a plurality of users, the item not yet rated by the user, the apparatus comprising:

(a) a processor; and

(b) a memory connected to the processor and storing computer executable instructions therein;

(c) wherein the processor, in response to execution of the instructions;

(c1) stores, in the memory, a user profile for each of the plurality of users, wherein at least one of the user profiles includes a plurality of values, one of the plurality of values representing a rating given to one of a plurality of items by the user and another of the plurality of values representing additional information;

(c2) calculates, for the user, a plurality of similarity factors responsive to both ratings given to items by the user and the additional information, each of the plurality of similarity factors representing a similarity between the user and another one of the plurality of users;

(c3) selects for the user, a plurality of neighboring users based on the similarity factors, by;

(c3a) defining a domain of items to be recommended; and

(c3b) choosing each one of said users as one of the neighboring users unless said one user has less than a predetermined number of ratings of the items in the domain;

(d) assigns a weight to each of the neighboring users; and

(e) recommends at least one of the plurality of items to the user based on the weights assigned to the plurality of neighboring users and ratings given to the plurality of items by the plurality of neighboring users.

33. A Computer-implemented apparatus for recommending an item to one of a plurality of users, the item not yet rated by the user, the apparatus comprising:

(a) a processor; and

(b) a memory connected to the processor and storing computer executable instructions therein;

(c) wherein the processor, in response to execution of the instructions;

(c1) stores, in the memory, a user profile for each of the plurality of users, wherein at least one of the user profiles includes a plurality of values, one of the plurality of values representing a rating given to one of a plurality of items by the user and another of the plurality of values representing additional information;

(c2) groups the plurality of items into a plurality of groups, wherein each of the groups has a rating based on the ratings of the items contained within said each group, by;

(c2a) randomly assigning all items to a number of initial groups;

(c2b) for each of the initial groups, determining a centroid of the ratings for the items assigned to the initial group;

(c2c) for each item, moving the item to the group with a centroid of ratings closest to its rating; and

(c2d) repeating steps (c2a) through (c2c) until both a certain number of iterations has been performed and distances, between all group centroids and items assigned to each of the groups, are below a predetermined threshold;

(c3) calculates, for the user, a plurality of similarity factors in response to ratings given to items by the user, the additional information, and the ratings of the groups, wherein each of the plurality of similarity factors represents a similarity between the user and another one of the plurality of users;

(c4) selects for the user, a plurality of neighboring users based on the similarity factors;

(c5) assigns a weight to each of the neighboring users; and

(c6) recommends at least one of the plurality of items to the user based on the weights assigned to the plurality of neighboring users and ratings given to the plurality of items by the plurality of neighboring users.