PROCESSES FOR CALCULATING ITEM DISTANCES AND PERFORMING ITEM CLUSTERING

• US 20080243816A1
• Filed: 03/30/2007
• Published: 10/02/2008
• Est. Priority Date: 03/30/2007
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Ionkov, George M., Chan, James D., Chakrabarti, Kushal
• Granted Patent: US 8,019,766 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06F 16/904 Browsing; Visualisation therefor for navigating the web G06F16/954; browsing optimisation for the web G06F16/957
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/23211 with adaptive number of clusters
• CPC Class Codes: G06Q 10/00 Administration; Management
• CPC Class Codes: G06Q 30/00 Commerce
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising

Abstract

Computer-implemented processes are disclosed for clustering items and improving the utility of item recommendations. One process involves applying a clustering algorithm to a user'"'"'s collection of items. Information about the resulting clusters is then used to select items to use as recommendation sources. Another process involves displaying the clusters of items to the user via a collection management interface that enables the user to attach cluster-level metadata, such as by rating or tagging entire clusters of items. The resulting metadata may be used to improve the recommendations generated by a recommendation engine. Another process involves forming clusters of items in which a user has indicated a lack of interest, and using these clusters to filter the output of a recommendation engine. Yet another process involves applying a clustering algorithm to the output of a recommendation engine to arrange the recommended items into cluster-based categories for presentation to the user.

Claims

1. A computer-implemented method of measuring the distance between a first item and a second item represented in a hierarchical browse structure that comprises multiple levels of browse nodes, the first item being accessible via a first set of one or more paths from a root node of the hierarchical browse structure, and the second item being accessible via a second set of one or more paths from the root node, the method comprising:

identifying a set of shared browse nodes for the first and second items, said shared browse nodes being browse nodes that occur in both the first set of paths and the second set of paths;

calculating data values for particular shared browse nodes;

calculating a distance value that represents the distance between the first item and the second item such that the distance value is dependent upon at least (a) the number of said shared browse nodes, (b) the total number of browse nodes in the first and second sets of paths, and (c) said data values; and

storing the distance value in computer storage.

2. The method of claim 1, further comprising using the distance value, in combination with distance values calculated for other pairs of items, as inputs to a clustering process that clusters together items.

3. The method of claim 1, wherein the data value for a shared browse node depends upon how many items fall below that shared browse node in the hierarchical browse structure.

4. The method of claim 1, wherein the data values are calculated, and used to generate said distance value, such that an amount of weight given to a shared browse node is inversely proportional to the number of items falling below the shared browse node in the hierarchical browse structure.

5. The method of claim 1, wherein the data values specify an amount of weight given to corresponding shared browse nodes in calculating the distance value.

6. The method of claim 1, wherein calculating the data values comprises, for a particular shared browse node, calculating a first data value which corresponds to the first item, and calculating a second data value which corresponds to the second item.

7. The method of claim 6, wherein the first and second data values are conditional probability values.

8. The method of claim 6, wherein the first data value is dependent upon the number of paths in said first set of paths.

9. The method of claim 1, wherein the first set of paths comprises a plurality of paths from the root node to the first item.

10. A computer system programmed to perform the method of claim 1.

11. A computer-readable medium having stored thereon executable computer code that embodies the method of claim 1.

12. A computer system, comprising:

a computer data repository that stores a representation of a hierarchical browse structure for browsing a repository of items, said hierarchical browse structure comprising multiple levels of browse nodes;

a distance calculation system configured to use information about locations of items in the hierarchical browse structure to calculate distance values representing distances between particular items; and

a clustering system configured to use at least the distance values calculated by the distance calculation system to form clusters of related items.

13. The computer system of claim 12, wherein the distance calculation system gives different amounts of weight to different browse nodes of the hierarchical browse structure in calculating said distance values.

14. The computer system of claim 13, wherein the amount of weight given to a browse node by the distance calculation system is inversely proportional to the number of items falling below the browse node in the hierarchical browse structure.

15. The computer system of claim 12, wherein the clustering system is configured to use said distance values to divide a collection of items associated with a user into multiple clusters.

16. The computer system of claim 15, further comprising a user interface that provides functionality for the user to assigning a tag to multiple items at a time by tagging a selected one of said clusters, said user interface also providing functionality for requesting item recommendations that are specific to said tag.

17. The computer system of claim 15, further comprising a recommendation system that uses said multiple clusters to assess interests of, and provide recommendations to, said user.

18. The computer system of claim 17, wherein the recommendation system uses the clusters to select items to use as recommendation sources for generating personalized item recommendations.

19. The computer system of claim 15, wherein the hierarchical browse structure comprises a first set of paths from a root node to a first item, and comprises a second set of paths from the root node to a second item, each path comprising multiple browse nodes, and the distance calculation system is configured to calculate a distance value representing a distance between the first and second items such that the distance value is dependent upon at least (a) the number of browse nodes common to said first and second sets of paths, and (b) the total number of browse nodes in the first and second sets of paths.

20. The computer system of claim 19, wherein the distance calculation system is configured to assign data values to particular shared browse nodes, and to use said data values in calculating said distance value.

21. The computer system of claim 15, wherein the distance calculation system and the clustering system are implemented in software executed by a single computer.

22. A computer-readable medium having stored thereon executable instructions which, when executed by a computer system, cause the computer system to:

identify a set of shared browse nodes for a first item and a second item that are represented in a hierarchical browse structure, said hierarchical browse structure comprising multiple levels of browse nodes, said first item being accessible via a first set of one or more paths from a root node of the hierarchical browse structure, said second item being accessible via a second set of one or more paths from the root node, said shared browse nodes being browse nodes that occur in both the first set of paths and the second set of paths;

calculate data values for particular ones of said shared browse nodes; and

calculate and store a distance value that represents a distance between the first item and the second item such that the distance value is dependent upon at least (a) the number of said shared browse nodes, (b) the total number of browse nodes in the first and second sets of paths, and (c) said data values.

23. The computer-readable medium of claim 22, wherein execution of the instructions further causes the computer system to use the distance value, in combination with distance values calculated for other pairs of items, as inputs to a clustering process that clusters together items.

24. The computer-readable medium of claim 22, wherein the data value for a shared browse node depends upon how many items fall below that shared browse node in the hierarchical browse structure.

25. The computer-readable medium of claim 22, wherein the data values are calculated, and used to generate said distance value, such that an amount of weight given to a shared browse node is inversely proportional to the number of items falling below the shared browse node in the hierarchical browse structure.

26. The computer-readable medium of claim 22, wherein the data values specify an amount of weight given to corresponding shared browse nodes in calculating the distance value.

27. The computer-readable medium of claim 22, wherein the first data value is dependent upon the number of paths in said first set of paths.

28. The computer-readable medium of claim 27, wherein the first set of paths comprises a plurality of paths from the root node to the first item.