System and method for collaborative filtering with applications to e-commerce

• US 6,487,541 B1
• Filed: 01/22/1999
• Issued: 11/26/2002
• Est. Priority Date: 01/22/1999
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu Chandra, Wolf, Joel Leonard, Yu, Philip Shi-lung
• Primary Examiner(s): Coggins, Wynn
• Assistant Examiner(s): Garg, Yogesh C.
• Application Number:
  US09/236,051
• Time in Patent Office: 1,404 Days
• Field of Search: 705/26, 705/27, 705/14, 705/1
• US Class Current: 705/7.29
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: G06Q 30/0241 Advertisements
• CPC Class Codes: G06Q 30/0601 Electronic shopping [e-shopping]

Abstract

A rating of a plurality of ratings is predicted. The rating is associated with a user of a plurality of users and the rating corresponds to an item of a plurality of items. One of the plurality of ratings, corresponding to at least one of the plurality of items, is provided for each of the plurality of users. A predictability relation between ones of the plurality of users and other ones of the plurality of users is calculated based on ratings provided by users. One of a plurality of nodes is assigned to each of the plurality of users. Ones of the plurality of nodes are connected with other ones of the plurality of nodes by a plurality of edges based on the predictability relation. A graph which includes the plurality of nodes and the plurality of edges is searched for a path from a node assigned to the user of the plurality of users to another node assigned to another user of the plurality of users. The rating of the plurality of ratings associated with the user of a plurality of users is calculated based on the path and the predictability relation. If desired, a predicted rating may be produced for identifying products and customers in an e-commerce applications.

Claims

1. A method for predicting a rating of a plurality of ratings associated with a user of a plurality of users, the rating corresponding to an item of a plurality of items, said method comprising the steps of:

(a) providing, for each of the plurality of users, one of the plurality of ratings corresponding to at least one of the plurality of items;

(b) calculating a predictability relation between ones of the plurality of users and other ones of the plurality of users based on the result of step (a);

(c) assigning one of a plurality of nodes to each of the plurality of users;

(d) connecting ones of the plurality of nodes with other ones of the plurality of nodes by a plurality of edges based on the predictability relation;

(e) searching a graph which includes the plurality of nodes and the plurality of edges for a path from a node assigned to the user of the plurality of users to an other node assigned to an other user of the plurality of users; and

(f) calculating the rating of the plurality of ratings associated with the user of the plurality of users based on the path and the predictability relation.

2. The method of claim 1, wherein the plurality of users are a plurality of customers, the plurality of items represent a plurality of products for sale, and the plurality of ratings are an indication of satisfaction of a customer of the plurality of customers with a product of sale of the plurality of products for sale.

3. The method of claim 1, wherein step (e) includes searching the graph for a shortest path from the node to the other node, the other user having provided any of the plurality of ratings corresponding to the item.

4. The method of claim 1, wherein the path from the node to the other node searched for in step (e) includes less than a predetermined number of edges.

5. The method of claim 1, wherein step (b) includes determining a plurality of transformations of ratings corresponding to the predictability relation based on the result of step (a).

6. The method of claim 5, wherein step (b) further includes determining a plurality of prediction values, each of the plurality of prediction values associated with one of the plurality of transformations of ratings.

7. The method of claim 6, wherein step (f) includes the steps of:

composing ones of the plurality of transformations of ratings based on the path, and

calculating the rating based on the composition of the ones of the plurality of transformations and ones of the plurality of prediction values associated with the ones of the plurality of transformations.

8. The method of claim 1, further comprising the steps of:

partitioning the plurality of items into a plurality of categories;

selecting a category of the plurality of categories;

repeating steps (e) and (f) to calculate a respective rating corresponding to each respective item of the category, the respective rating associated with the user; and

sorting the respective items of the category according to the corresponding respective ratings.

9. The method of claim 1, further comprising the steps of:

partitioning the plurality of items into a plurality of categories;

selecting a category of the plurality of categories;

repeating steps (e) and (f) to calculate a respective rating corresponding to each respective item of the category, the respective rating associated with the user; and

reporting a preferred item of the plurality of items corresponding to a highest rating of the respective ratings of each respective item of the category.

10. The method of claim 1, further comprising the steps of:

partitioning the plurality of items into a plurality of categories;

selecting a category of the plurality of categories;

repeating steps (e) and (f) to calculate a respective rating corresponding to each respective item of the category, the respective rating associated with the user; and

reporting a rejected item of the plurality of items corresponding to a lowest rating of the respective ratings of each respective item of the category.

11. The method of claim 1, further comprising the steps of:

repeating steps (e) and (f) to calculate a respective rating associated with each respective user of the plurality of users, the respective rating corresponding to the item; and

sorting the respective users according to the respective ratings associated with each respective user.

12. An e-commerce method for producing a predicted rating of a plurality of ratings indicating a level of satisfaction of a given customer of a plurality of customers, the predicted rating corresponding to a product of a plurality of products for sale, said method comprising the steps of:

(a) providing, for each of the plurality of customers, one of the plurality of ratings corresponding to at least one of the plurality of products for sale;

(b) calculating a predictability relation between ones of the plurality of customers and other ones of the plurality of customers based on the result of step (a);

(c) assigning one of a plurality of nodes to each of the plurality of customers;

(e) connecting ones of the plurality of nodes with other ones of the plurality of nodes by a plurality of edges based on the predictability relation;

(f) searching a graph which includes the plurality of nodes and the plurality of edges for a path from a node assigned to the given customer of the plurality of customers to an other node assigned to an other customer of the plurality of customers which provided a rating of the plurality of ratings corresponding to the product; and

(g) calculating the predicted rating associated with the customer based on the path and the rating provided by the other customer.

13. The e-commerce method of claim 12, further comprising the steps of:

partitioning the plurality of products for sale into a plurality of categories;

selecting a category of the plurality of categories;

repeating steps (f) and (g) to calculate a respective predicted rating corresponding to each respective product for sale of the category, the respective predicted rating associated with the given customer; and

sorting the products for sale of the category according to the corresponding respective predicted ratings.

14. The e-commerce method of claim 12, further comprising the steps of:

repeating steps (f) and (g) to calculate a respective predicted rating associated with each respective given customer of the plurality of customers, the respective predicted rating corresponding to the product for sale; and

sorting the respective given customers according to the respective predicted ratings associated with each respective given customer.

15. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for predicting a rating of a plurality of ratings associated with a user of a plurality of users, the rating corresponding to an item of a plurality of items, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect:

(a) providing, for each of the plurality of users, one of the plurality of ratings corresponding to at least one of the plurality of items;

(b) calculating a predictability relation between ones of the plurality of users and other ones of the plurality of users based on the result of step (a);

(c) assigning one of a plurality of nodes to each of the plurality of users;

(d) connecting ones of the plurality of nodes with other ones of the plurality of nodes by a plurality of edges based on the predictability relation;

(e) searching a graph which includes the plurality of nodes and the plurality of edges for a path from a node assigned to the user of the plurality of users to an other node assigned to an other user of the plurality of users; and

(f) calculating the rating of the plurality of ratings associated with the user of the plurality of users based on the path and the predictability relation.

16. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for producing a predicted rating of a plurality of ratings indicating a level of satisfaction of a given customer of a plurality of customers, the predicted rating corresponding to a product of a plurality of products for sale, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect:

(a) providing, for each of the plurality of customers, one of the plurality of ratings corresponding to at least one of the plurality of products for sale;

(b) calculating a predictability relation between ones of the plurality of customers and other ones of the plurality of customers based on the result of step (a);

(c) assigning one of a plurality of nodes to each of the plurality of customers;

(e) connecting ones of the plurality of nodes with other ones of the plurality of nodes by a plurality of edges based on the predictability relation;

(f) searching a graph which includes the plurality of nodes and the plurality of edges for a path from a node assigned to the given customer of the plurality of customers to an other node assigned to an other customer of the plurality of customers which provided a rating of the plurality of ratings corresponding to the product; and

(g) calculating the predicted rating associated with the customer based on the path and the rating provided by the other customer.

17. An article of manufacture as recited in claim 16, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect:

partitioning the plurality of products for sale into a plurality of categories;

selecting a category of the plurality of categories;

repeating steps (f) and (g) to calculate a respective predicted rating corresponding to each respective product for sale of the category, the respective predicted rating associated with the given customer; and

sorting the products for sale of the category according to the corresponding respective predicted ratings.

18. An article of manufacture as recited in claim 16, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect:

repeating steps (f) and (g) to calculate a respective predicted rating associated with each respective given customer of the plurality of customers, the respective predicted rating corresponding to the product for sale; and

sorting the respective given customers according to the respective predicted ratings associated with each respective given customer.

19. A storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for predicting a rating of a plurality of ratings associated with a user of a plurality of users, the rating corresponding to an item of a plurality of items, said method comprising the steps of:

(a) providing, for each of the plurality of users, one of the plurality of ratings corresponding to at least one of the plurality of items;

(b) calculating a predictability relation between ones of the plurality of users and other ones of the plurality of users based on the result of step (a);

(c) assigning one of a plurality of nodes to each of the plurality of users;

(d) connecting ones of the plurality of nodes with other ones of the plurality of nodes by a plurality of edges based on the predictability relation;

(e) searching a graph which includes the plurality of nodes and the plurality of edges for a path from a node assigned to the user of the plurality of users to an other node assigned to an other user of the plurality of users; and

(f) calculating the rating of the plurality of ratings associated with the user of the plurality of users based on the path and the predictability relation.

20. A storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for producing a predicted rating of a plurality of ratings indicating a level of satisfaction of a given customer of a plurality of customers, the predicted rating corresponding to a product of a plurality of products for sale, said method comprising the steps of:

(a) providing, for each of the plurality of customers, one of the plurality of ratings corresponding to at least one of the plurality of products for sale;

(b) calculating a predictability relation between ones of the plurality of customers and other ones of the plurality of customers based on the result of step (a);

(c) assigning one of a plurality of nodes to each of the plurality of customers;

(e) connecting ones of the plurality of nodes with other ones of the plurality of nodes by a plurality of edges based on the predictability relation;

(f) searching a graph which includes the plurality of nodes and the plurality of edges for a path from a node assigned to the given customer of the plurality of customers to an other node assigned to an other customer of the plurality of customers which provided a rating of the plurality of ratings corresponding to the product; and

(g) calculating the predicted rating associated with the customer based on the path and the rating provided by the other customer.

21. The storage device as recited in claim 20, the program of instructions tangibly embodied in said storage device further comprising instructions to perform method steps executable by the machine of:

partitioning the plurality of products for sale into a plurality of categories;

selecting a category of the plurality of categories;

repeating steps (f) and (g) to calculate a respective predicted rating corresponding to each respective product for sale of the category, the respective predicted rating associated with the given customer; and

sorting the products for sale of the category according to the corresponding respective predicted ratings.

22. The storage device as recited in claim 20, the program of instructions tangibly embodied in said storage device further comprising instructions to perform method steps executable by the machine of:

repeating steps (f) and (g) to calculate a respective predicted rating associated with each respective given customer of the plurality of customers, the respective predicted rating corresponding to the product for sale; and

sorting the respective given customers according to the respective predicted ratings associated with each respective given customer.