Scalable user clustering based on set similarity

• US 20070038659A1
• Filed: 08/15/2005
• Published: 02/15/2007
• Est. Priority Date: 08/15/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Datar, Mayur, Garg, Ashutosh
• Granted Patent: US 7,739,314 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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

Abstract

Methods and apparatus, including systems and computer program products, to provide clustering of users in which users are each represented as a set of elements representing items, e.g., items selected by users using a system. In one aspect, a program operates to obtain a respective interest set for each of multiple users, each interest set representing items in which the respective user expressed interest; for each of the users, to determine k hash values of the respective interest set, wherein the i-th hash value is a minimum value under a corresponding i-th hash function; and to assign each of the multiple users to each of the respective k clusters established for the respective user, the i-th cluster being represented by the i-th hash value. The assignment of each of the users to k clusters is done without regard to the assignment of any of the other users to k clusters.

Claims

1. A computer program product, encoded on an information carrier, comprising instructions operable to cause data processing apparatus to:

obtain a respective interest set for each of multiple users, each interest set representing items in which the respective user has expressed interest through interaction with a data processing system;

for each of the multiple users, determine k hash values of the respective interest set, wherein the i-th hash value is a minimum value in the respective interest set under a corresponding i-th hash function, where i is an integer between 1 and k, and where k is an integer greater than or equal to 1; and

assign each of the multiple users to each of the respective k clusters established for the respective user, the i-th cluster being represented by the i-th hash value, wherein the assignment of each of the multiple users to k clusters is done without regard to the assignment of any of the other users to k clusters.

2. The product of claim 1, further comprising instructions operable to cause data processing apparatus to:

record actions expressing user interest in a log; and

use the log to generate the interest sets for the multiple users.

3. The product of claim 1, further comprising instructions operable to cause data processing apparatus to:

obtain a changed interest set for a first user of the multiple users;

determine k hash values for the first user using the changed interest set; and

assign the first user only to each of the respective k clusters represented by the k hash values determined using the changed interest set without changing the assignment of any the other multiple users to clusters.

4. A computer program product, encoded on an information carrier, comprising instructions operable to cause data processing apparatus to:

obtain an interest set for a user, the interest set representing items in which the user has expressed interest through interaction with a data processing system;

determine k hash values of the interest set, wherein the i-th hash value is a minimum value in the interest set under a corresponding i-th hash function, where i is an integer between 1 and k, and where k is an integer greater than or equal to 1; and

assign the user to each of k clusters, the i-th cluster being represented by the i-th hash value.

5. The product of claim 4, wherein:

the interest set has m elements;

the i-th hash value is a minimum value of m applications of a one-way hash function, each application hashing an i-th seed value and a respective one of the m elements of the interest set.

6. The product of claim 4, further comprising instructions operable to cause data processing apparatus to:

use the k user clusters to perform collaborative filtering for the user.

7. A system, comprising:

a log of items selected by multiple users using a data processing system;

means for using a fingerprint function and the log of items to assign each of the multiple users to k clusters, where k is an integer greater than or equal to 1; and

a collaborative filtering computer program application operable to provide information to a first user of the multiple users based on the assignment of the first user to one or more of the k clusters.

8. The system of claim 7, wherein the information comprises at least one of a recommendation, a prediction, or a ranking.

9. A computer program product, encoded on an information carrier, comprising instructions operable to cause data processing apparatus to:

use an ordered set of k elements to identify a user of a data processing system, where k is an integer greater than 1, where each of the k elements corresponds to an element in an interest set, each element in the interest set representing an item in which the user has expressed interest through actions by the user using the data processing system.

10. The product of claim 9, further comprising instructions operable to cause data processing apparatus to:

use the ordered set of k elements to identify the user in performing collaborative filtering for the user.

11. The product of claim 10, wherein:

the collaborative filtering comprises recommending items to the user or ranking items for the user.

12. The product of claim 9, further comprising instructions operable to cause data processing apparatus to:

receive input from the user in response to which input the data processing system removes elements from the interest set to generate a revised interest set;

determine a revised ordered set of k elements where each of the k elements corresponds to an element in the revised interest set; and

use the revised ordered set of k elements rather than the initial ordered set of k elements to identify the user.

13. The product of claim 9, wherein:

the ordered set of k elements identifies the user as belonging to each of k user clusters.

14. The product of claim 9, further comprising instructions operable to cause data processing apparatus to:

record actions expressing user interest in a log; and

use the log to generate the interest set for the user.

15. The product of claim 9, wherein:

the data processing system comprises a web site; and

the interest set for the user comprises representations of one or more items the user has clicked on in a web page, items the user has purchased from an on-line retailer, or items the user has added to a shopping cart.

16. The product of claim 9, wherein the actions by the user expressing interest in items comprise actions implicitly expressing interest.

17. The product of claim 9, wherein the actions by the user expressing interest in items comprise actions expressly expressing interest.

18. The product of claim 9, wherein the user is an individual identified by a user logon.

19. The product of claim 9, wherein the user is an individual identified by a cookie.

20. The product of claim 9, wherein the user is one or more individuals having an observed attribute in common, where the attribute is an attribute disclosed to the data processing system by each of the one or more individuals.

21. The product of claim 9, wherein the user is a session of an individual interacting with the data processing system.

22. The product of claim 9, wherein each element in the interest set is an item that the user has selected in interaction with the data processing system.

23. A method comprising:

obtaining a respective interest set for each of multiple users, each interest set representing items in which the respective user has expressed interest through interaction with a data processing system;

for each of the multiple users, determining k hash values of the respective interest set, wherein the i-th hash value is a minimum value in the respective interest set under a corresponding i-th hash function, where i is an integer between 1 and k, and where k is an integer greater than or equal to 1; and

assigning each of the multiple users to each of the respective k clusters established for the respective user, the i-th cluster being represented by the i-th hash value, wherein the assignment of each of the multiple users to k clusters is done without regard to the assignment of any of the other users to k clusters.

24. The method of claim 23, further comprising:

recording actions expressing user interest in a log; and

using the log to generate the interest sets for the multiple users.

25. A method comprising:

obtaining an interest set for a user, the interest set representing items in which the user has expressed interest through interaction with a data processing system;

determining k hash values of the interest set, wherein the i-th hash value is a minimum value in the interest set under a corresponding i-th hash function, where i is an integer between 1 and k, and where k is an integer greater than or equal to 1; and

assigning the user to each of k clusters, the i-th cluster being represented by the i-th hash value.

26. The method of claim 25, wherein:

the interest set has m elements;

the i-th hash value is a minimum value of m applications of a one-way hash function, each application hashing an i-th seed value and a respective one of the m elements of the interest set.

27. The method of claim 25, further comprising:

using the k user clusters to perform collaborative filtering for the user.

28. A method comprising:

using an ordered set of k elements to identify a user of a data processing system, where k is an integer greater than 1, where each of the k elements corresponds to an element in an interest set, each element in the interest set representing an item in which the user has expressed interest through actions by the user using the data processing system.

29. The method of claim 28, further comprising:

using the ordered set of k elements to identify the user in performing collaborative filtering for the user.

30. The method of claim 29, wherein:

the collaborative filtering comprises recommending items to the user or ranking items for the user.

31. The method of claim 28, further comprising:

recording actions expressing user interest in a log; and

using the log to generate the interest set for the user.

32. The method of claim 28, wherein:

the data processing system comprises a web site; and

the interest set for the user comprises representations of one or more items the user has clicked on in a web page, items the user has purchased from an on-line retailer, or items the user has added to a shopping cart.