Grouping of item data using seed expansion

• US 10,467,307 B1
• Filed: 07/14/2016
• Issued: 11/05/2019
• Est. Priority Date: 07/14/2016
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Chanda, Gaurav, Chappidi, Srinivas Vasu, Wadwekar, Saurabh
• Primary Examiner(s): Wong, Leslie
• Application Number:
  US15/210,847
• Time in Patent Office: 1,209 Days
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/906 Clustering; Classification
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

Features are provided for the analysis of collections of data and automatic grouping of data having certain similarities. A collection of data regarding user interactions with item-specific content can be analyzed. The analysis can be used to identify groups of items that are of interest to groups of similar users and/or to identify groups of users with demonstrated interests in groups of similar items. Data may be analyzed in a “bottom-up” manner in which correlations within the data are discovered in an iterative manner, or in a “top-down” manner in which desired top-level groups are specified at the beginning of the process. A bottom-up process may also be distributed among multiple devices or processors to more efficiently discover groups when using large collections of data.

Claims

1. A system comprising:

a computer-readable memory storing executable instructions; and

one or more processors in communication with the computer-readable memory, the one or more processors programmed by the executable instructions to at least;

obtain data regarding a plurality of item groups, wherein data regarding a first item group of the plurality of item groups comprises a first keyword with which the first item group is associated;

determine, using a keyword-to-keyword map, a second keyword associated with the first keyword;

determine, using a keyword-to-item map, a first item associated with the second keyword;

add the first item to the first item group based at least partly on the first item being associated with the second keyword;

obtain an item connection graph comprising a first node representing the first item, a second node representing a second item, and a connection between the first node and the second node, wherein the connection indicates a similarity between the first item and the second item;

select the first node as a seed node based at least in part on the first item being in the first item group;

assign a first score to the first node, the first score based on the first node being a seed node;

determine a second score for the second node using the first score and a decay factor, wherein the first score is used to determine the second score based at least partly on the connection between the first node and the second node; and

add the second item to the first item group based at least partly on the second score.

2. The system of claim 1, wherein the one or more processors are further programmed to at least:

determine a third score for a third node of the item connection graph, wherein the third node represents a third item, wherein the item connection graph comprises a second connection between the second node and the third node, and wherein the third score is determined using the second score and the decay factor squared; and

determine not to add the third item to the first item group based at least partly on the third score.

3. The system of claim 1, wherein the one or more processors are further programmed to at least:

generate the keyword-to-item map based at least partly on an analysis of items purchased or viewed in connection with keyword searches, wherein the keyword-to-item map associates the second keyword with the first item based at least partly on the first item being purchased or viewed by a user during a same browsing session as a search query is submitted by the user, the search query comprising the second keyword.

4. The system of claim 1, wherein the one or more processors are further programmed to at least:

generate the keyword-to-keyword map based at least partly on an analysis of textual bi-grams in data associated with one or more keywords, wherein the keyword-to-keyword map associates the first keyword with the second keyword based at least partly on a textual bi-gram comprising the second keying being observed in data associated with a topic of the first keyword.

5. A computer-implemented method comprising:

as performed by a computing system comprising a processor configured to execute specific instructions,

obtaining an item graph comprising a first node, a second node, and a connection between the first node and the second node, wherein the connection indicates a similarity between a first item represented by the first node and a second item represented by the second node;

selecting the first node as a seed node based at least partly on data regarding an association between the first item and a keyword, wherein the keyword is associated with an item group to which items are to be added;

determining a first score for the first node based at least partly on the first node being the seed node;

determining a second score for the second node using the first score, wherein determining the second score comprises applying a weighting factor to the first score, and wherein the first score is used to determine the second score based at least partly on the connection between the first node and the second node; and

adding the second item to the item group based at least partly on the second score, wherein the first item is also in the item group.

6. The computer-implemented method of claim 5, further comprising:

determining a third score for a third node of the item graph, wherein the third node represents a third item, wherein the item graph comprises a second connection between the second node and the third node, and wherein the third score is determined using the second score and a second weighting factor based at least partly on the weighting factor; and

determining not to add the third item to the item group based at least partly on the third score.

7. The computer-implemented method of claim 5, further comprising:

generating a keyword-to-keyword map based at least partly on an analysis of keywords submitted in search queries, wherein the keyword-to-keyword map associates the keyword with a second keyword based at least partly on the keyword being submitted in a first search query during a same browsing session as the second keyword is submitted in a second search query.

8. The computer-implemented method of claim 5, further comprising:

generating a keyword-to-item map based at least partly on an analysis of items purchased, or item-specific content requested, in connection with keyword searches, wherein the keyword-to-item map associates the keyword with the first item based at least partly on the first item being purchased, or content regarding the first item being requested, by a user during a same browsing session as search query is submitted by the user, and wherein the search query comprises the keyword; and

determining to add the first item to the item group based at least partly on the keyword-to-item map.

9. The computer-implemented method of claim 5, further comprising performing k-means clustering using the item group, wherein an initial cluster used in performing the k-means clustering comprises a data vector regarding an item in the item group.

10. The computer-implemented method of claim 5, further comprising generating the item group using k-means clustering, wherein the item group comprises one or more items selected from a cluster generated by the k-means clustering.

11. The computer-implemented method of claim 5, further comprising:

determining that a user is associated with the item group based at least partly on an interaction of the user with content regarding an item in the item group; and

customizing content to be presented to the user based at least partly on the user being associated with the item group.

12. The computer-implemented method of claim 11, wherein customizing content comprises recommending content regarding one or more items in the item group.

13. A non-transitory computer storage medium storing executable instructions that, when executed by one or more processors of a computing system, cause the one or more processors to perform a process comprising:

obtaining an item graph comprising a first node, a second node, and a connection between the first node and the second node, wherein the connection indicates a similarity between a first item represented by the first node and a second item represented by the second node;

selecting the first node as a seed node based at least partly on data regarding an association between the first item and a keyword, wherein the keyword is associated with an item group to which items are to be added;

determining a first score for the first node based at least partly on the first node being the seed node;

determining a second score for the second node using the first score, wherein determining the second score comprises applying a weighting factor to the first score, and wherein the first score is used to determine the second score based at least partly on the connection between the first node and the second node; and

adding the second item to the item group based at least partly on the second score, wherein the first item is also in the item group.

14. The non-transitory computer storage medium of claim 13, the process further comprising:

determining a third score for a third node of the item graph, wherein the third node represents a third item, wherein the item graph comprises a second connection between the second node and the third node, and wherein the third score is determined using the second score and a second weighting factor based at least partly on the weighting factor; and

determining not to add the third item to the item group based at least partly on the third score.

15. The non-transitory computer storage medium of claim 13, the process further comprising:

generating a keyword-to-keyword map based at least partly on an analysis of keywords submitted in search queries, wherein the keyword-to-keyword map associates the keyword with a second keyword based at least partly on the keyword being submitted in a first search query during a same browsing session as the second keyword is submitted in a second search query.

16. The non-transitory computer storage medium of claim 13, the process further comprising:

generating a keyword-to-item map based at least partly on an analysis of items purchased in connection with keyword searches, wherein the keyword-to-item map associates the keyword with the first item based at least partly on the first item being purchased by a user during a same browsing session as search query is submitted by the user, and wherein the search query comprises the keyword; and

determining to add the first item to the item group based at least partly on the keyword-to-item map.

17. The non-transitory computer storage medium of claim 13, the process further comprising performing k-means clustering using the item group, wherein an initial cluster used in performing the k-means clustering comprises a data vector regarding an item in the item group.

18. The non-transitory computer storage medium of claim 13, the process further comprising generating the item group using k-means clustering, wherein the item group comprises one or more items selected from a cluster generated by the k-means clustering.

19. The non-transitory computer storage medium of claim 13, the process comprising:

determining that a user is associated with the item group based at least partly on an interaction of the user with content regarding an item in the item group; and

customizing content to be presented to the user based at least partly on the user being associated with the item group.

20. The non-transitory computer storage medium of claim 19, wherein customizing content comprises recommending content regarding one or more items in the item group.