Product line extraction

• US 7,853,597 B2
• Filed: 04/28/2008
• Issued: 12/14/2010
• Est. Priority Date: 04/28/2008
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Mahabala, Meera, Dharawat, Nimish G., Gupta, Gitika
• Primary Examiner(s): Wong; Don
• Assistant Examiner(s): Hwa; Shyue Jiunn
• Application Number:
  US12/110,390
• Publication Number:
  US 20090271367A1
• Time in Patent Office: 960 Days
• Field of Search: None
• US Class Current: 707/741
• CPC Class Codes: G06F 16/35 Clustering; Classification

Abstract

Methods, systems and computer readable media for extracting product lines from a plurality of product titles are provided. In one embodiment, the plurality of product titles are broken into tokens. Association rules are calculated for individual tokens and pairs of tokens. Brand specific terms and product class specific terms within the product titles are identified. In one embodiment, a token tree is used to identify product lines within the list of product titles using the association rules, the brand specific terms, and the product class specific terms.

Claims

1. One or more computer-readable media having computer-executable instructions embodied thereon for performing a method of extracting product lines from a plurality of product titles, the method comprising:

receiving the plurality of product titles;

breaking the plurality of product titles into a plurality of tokens, wherein the plurality of tokens includes unigrams and bigrams;

generating an association rule for each of a plurality of token pairs, wherein a token pair may include two of the bigrams, two of the unigrams, or one bigram and one unigram, wherein the association rule includes a confidence factor and a support factor, wherein the support factor is a total number of times a first token and a second token occur together in a single product title divided by a total number of product titles within the plurality of product titles, and wherein the confidence factor is the total number of times the first token and the second token occur together within the plurality of product titles divided by a number of times the first token occurs within the plurality of product titles;

generating a plurality of brand specific tokens that form part of a brand name;

generating a plurality of product class specific tokens using the plurality of brand specific tokens and the association rule for each of the plurality of token pairs;

generating a plurality of model specific tokens that form part of a product model; and

generating a plurality of product lines from the plurality of tokens.

2. The media of claim 1, wherein generating the plurality of brand specific tokens includes:

receiving a list of potential brands;

breaking the list of potential brands into tokens; and

applying one or more heuristics that identify the tokens that are likely brands.

3. The media of claim 2, wherein a unigram is a single alphanumeric sequence between spaces and a bigram is two consecutive alphanumeric sequences that occur together in the plurality of product titles.

4. The media of claim 1, wherein the plurality of product class specific tokens is determined by identifying tokens that have a brand count above a threshold number, wherein the brand count is a number of brand specific tokens to which the tokens are related.

5. The media of claim 4, wherein a first token is related to a second token if the association rule score is above a threshold.

6. The media of claim 1, wherein the plurality of product lines is generated using a token tree, wherein a root of the token tree is a brand.

7. The media of claim 6, wherein a first token is added to the root if the first token occurs as a suffix of the root within the plurality of product titles and a confidence factor between the root and the first token is above a threshold.

8. The media of claim 7, wherein a second token is added to the first token if the confidence factor between the second token and the first token exceeds the threshold.

9. A computerized system for generating a list of product lines from a list of product titles, the system including:

an association rule builder that calculates an associative probability that a first token is associated with a second token, wherein the first token and the second token are generated from the list of product titles, wherein the associative probability is determined based on a confidence factor and a support factor, wherein the support factor is a total number of times a first token and a second token occur together in a single product title divided by a total number of product titles within the list of product titles, and wherein the confidence factor is the total number of times the first token and the second token occur together within the list of product titles divided by a number of times the first token occurs within the list of product titles;

a product class recognizer that identifies product class specific tokens within the list of product titles, wherein the product class specific tokens describe a product category that is recognized across multiple brands; and

a product line extractor that identifies product lines within the list of product titles.

10. The computerized system of claim 9, further comprising a brand identifier that evaluates a list brands and the list of product titles to generate a plurality of brands specific tokens.

11. The computerized system of claim 10, wherein the product class recognizer identifies product class specific tokens by identifying a plurality of tokens that are related to more than one brand specific token and that are related to above a threshold number of brand specific tokens.

12. The computerized system of claim 9, wherein the product line extractor builds a token tree starting with brand tokens as a tree root.

13. The computerized system of claim 12, wherein a second level token is added to a root if a confidence factor for the second level token and the root exceeds a threshold confidence factor.

14. One or more computer-readable media having computer-executable instructions embodied thereon for performing a method of extracting product lines from a group of product titles, the method comprising:

tokenizing the group of product titles to create a plurality of tokens, wherein the plurality of tokens includes unigrams and bigrams;

generating an association rule for token pairs generated from the plurality of tokens, wherein the association rule indicates how frequently an individual pairing of tokens occur together within the group of product titles, wherein the association rule includes a confidence factor and a support factor, wherein the support factor is a total number of times a first token and a second token occur together in a single product title divided by a total number of product titles within the group of product titles, and wherein the confidence factor is the total number of times the first token and the second token occur together within the group of product titles divided by a number of times the first token occurs within the group of product titles;

creating a product line token tree that includes a brand token as a root node and suffix tokens as second level nodes;

analyzing token branches on the product line token tree to generate a plurality of product lines, wherein a token branch includes the root node and a suffix token; and

storing the plurality of product lines.

15. The media of claim 14, wherein a unigram is a single alphanumeric sequence between spaces and a bigram is two consecutive alphanumeric sequences that occur together in the group of product titles.

16. The media of claim 14, wherein the method further comprises recognizing product class specific tokens within the group of product titles using a product class heuristic that identifies a plurality of tokens that are related to more than one brand specific token and that are related to above a threshold number of brand specific tokens.

17. The media of claim 16, wherein a potential second level token node is added to the product line token tree if a confidence for a potential second level token and the root node exceeds a confidence threshold.

18. The media of claim 17, wherein a pair of tokens on the product line token tree are excluded as a product line if the pair of tokens occurs within the group of product titles less than a product-title threshold.