Processes for calculating item distances and performing item clustering

• US 8,019,766 B2
• Filed: 03/30/2007
• Issued: 09/13/2011
• 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
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): Chojnacki; Mellissa M
• Application Number:
  US11/694,757
• Publication Number:
  US 20080243816A1
• Time in Patent Office: 1,628 Days
• Field of Search: 707/737, 707/740
• US Class Current: 707/740
• 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 for using item clusters to generate and/or present item recommendations. One process involves calculating distances between items based on how the items are categorized within a hierarchical browse structure. These distance calculations may then be used as a basis for forming clusters of items.

Claims

1. A computer-implemented method of measuring the distance between a first item and a second item, the method comprising:

identifying a first set of one or more paths in a hierarchical browse structure from a root node of the hierarchical browse structure to the first item, said hierarchical browse structure comprising multiple levels of browse nodes arranged in a hierarchy, each browse node representing a respective item category;

identifying a second set of one or more paths in the hierarchical browse structure from the root node to the second item;

identifying a plurality 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, each shared browse node representing a respective item category in which the first and second items are both categorized;

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, such that different amounts of weight are given to different shared browse nodes in calculating the distance value; 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 oaths from the root node to the first item.

10. A computer system comprising one or more computers, said 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. The method of claim 1, wherein the items are products represented in an electronic catalog, and the method is performed by execution of code by one or more computers.

13. 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, each browse node representing a particular item category;

a distance calculation system comprising a machine, said distance calculation system configured to calculate distance values representing distances between particular items such that the distance value for a pair of items, item 1 and item 2, depends on (a) a number of browse nodes that are shared by both item 1 and item 2 in the hierarchical browse structure, and (2) weight values calculated for said shared browse nodes, said weight values calculated such that the shared browse nodes are not all weighted equally; and

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

14. The computer system of claim 13, wherein the distance value further depends on how many browse nodes item 1 falls under and how many browse nodes item 2 falls under.

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

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

17. The computer system of claim 16, 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.

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

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

20. The computer system of claim 16, 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.

21. The computer system of claim 20, 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.

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, each browse node representing an item category, said first item accessible via a first set of one or more paths from a root node of the hierarchical browse structure, said second item 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, said first and second sets of paths reflecting categorizations of the first and second items, respectively, in the hierarchical browse structure;

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, such that different amounts of weight are given to different shared browse nodes in calculating the distance value.

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.

29. The computer-readable medium of claim 22, wherein the items are products represented in an electronic catalog.