Cluster-based scalable collaborative filtering

• US 20070239554A1
• Filed: 03/16/2006
• Published: 10/11/2007
• Est. Priority Date: 03/16/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chen, Zheng, Zhang, Benyu, Wang, Jian, Zeng, Hua-Jun, Lin, Chenxi, Xue, Gui-Rong
• Granted Patent: US 8,738,467 B2
• Time in Patent Office: Days
• US Class Current: 705/26
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06Q 30/0212 Chance discounts or incentives
• CPC Class Codes: G06Q 30/0601 Electronic shopping [e-shopping]
• CPC Class Codes: G06Q 30/0631 Item recommendations

Abstract

Methods for determining a predictive rating are disclosed. In an embodiment, an active user is compared to a set of clusters. One or more of the clusters are determined to be most similar to the active user. From the one or more clusters, K users are determined to be most similar to the active user. Prior ratings for an item by the K users may be used to predict a rating for the item for the active user.

Claims

1. A method of providing a predictive recommendation for a first item to an active user based on ratings of the first item made by users, the method comprising:

(a) selecting from a set of N clusters at least one cluster that is similar to the active user;

(b) from the at least one cluster, determining K users that are most similar to the active user; and

(c) providing the predictive recommendation for the first item to the active user based on the ratings for the first item made by the K users.

2. The method of claim 1, wherein the providing in (c) comprises:

(i) determining an average deviation in the rating for the first item made by the K users; and

(ii) adding the average deviation in rating for the first item to the average rating of the active user to form the predictive recommendation for the first item.

3. The method of claim 1, further comprising:

(d) sorting the users into the set of N clusters.

4. The method of claim 3, wherein the sorting of the users is performed in advance of the active user requesting information.

5. The method of claim 1, wherein predictive recommendation is provided in response to an input provided by the active user.

6. The method of claim 5, wherein the input is a selection of a second item related to the first item.

7. The method of claim 1, wherein the at least one cluster comprises a plurality of clusters and the plurality of clusters consists of about 30% of the total number of previous users.

8. A computer readable medium comprising computer executable instructions for performing the steps:

(a) sorting a database of users into N clusters;

(b) in response to an input by an active user, determining a subset of the N clusters that are similar to the active user;

(c) determining K users in the subset of clusters that are closest to the active user; and

(d) providing a predictive rating for a first item to the active user based on ratings for the first item made by the K users.

9. The computer readable medium of claim 8, wherein the sorting in (a) comprises:

(i) using a K-means algorithm to sort the users into N clusters.

10. The computer readable medium of claim 8, wherein the determining in (b) comprises:

(i) selecting a number of clusters so as to include about 30 percent of the total users in the subset of N clusters.

11. The computer readable medium of claim 8, wherein the determining in (b) comprises:

(i) determining a set of ratings associated with the active user;

(ii) determining the similarity of each of the N clusters to the active user; and

(iii) selecting a subset of the N clusters that are the most similar to the active user.

12. The computer readable medium of claim 11, wherein the determining in (ii) comprises:

(1) comparing the set of ratings associated with the active user to a centroid of each cluster.

13. The computer readable medium of claim 8, wherein the predictive rating is a recommendation to purchase the first item.

14. The computer readable medium of claim 13, wherein the input is a request for information regarding a second item related to the first item.

15. The computer readable medium of claim 8, wherein the determining in (c) comprises:

(i) determining a set of ratings associated with the active user; and

(ii) determining the similarity between the set of ratings associated with the active user and the ratings associated with each of the users in the subset of N clusters.

16. A method of providing a predictive rating to an active user, comprising:

(a) receiving a request from the active user, the request associated with a first item;

(b) selecting from a set of clusters at least one cluster that is most similar to the active user;

(c) determining a predictive rating for the first item based on ratings of the first item by K users selected from the at least one cluster; and

(d) providing the predictive rating to the active user.

17. The method of claim 16, wherein the request received from the active user comprises a request for search results for a class of product.

18. The method of claim 16, wherein the selecting in (b) comprises:

(i) determining a first set of ratings associated with the active user;

(ii) determining the similarity between the first set of ratings and a centroid of each cluster in the set of clusters; and

(iii) selecting at least one cluster that has the centroid that is most similar to the first set of ratings.

19. The method of claim 18, wherein the centroid for each cluster is the average rating value for each item.

20. The method of claim 16, wherein the request is a purchase of a second item.