Assigning into one set of categories information that has been assigned to other sets of categories

• US 7,885,859 B2
• Filed: 03/10/2006
• Issued: 02/08/2011
• Est. Priority Date: 03/10/2006
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Han, Hui, Balasubramanyan, Ramnath, Pavlov, Dmitry Yurievich, Dom, Byron Edward
• Primary Examiner(s): Garg; Yogesh C
• Application Number:
  US11/373,726
• Publication Number:
  US 20070214140A1
• Time in Patent Office: 1,796 Days
• Field of Search: 705/26, 706/25, 707/740
• US Class Current: N/A
• CPC Class Codes: G06F 16/353 into predefined classes

Abstract

Techniques are described for assigning, to target categories of a target scheme, items that have been obtained from a plurality of sources. In situations in which one or more of the sources has organized its information according to a source scheme that differs from the target scheme, the assignment may be based, in part, on an estimate of the probability that items from a particular source category should be assigned to a particular target category. Such probability estimates may be based on how many training set items associated with the particular source category have been assigned to the particular target category. Source categories may be grouped into clusters. The probability estimates may also be based on how many training set items within the cluster to which the particular source category has been mapped, have been assigned the particular target category.

Claims

1. A method comprising:

automatically assigning items to target categories in a target scheme;

wherein the items assigned to the target categories in the target scheme include a first set of items;

wherein items in the first set of items have previously been assigned to source categories in a first source scheme that is different from said target scheme;

wherein the first set of items includes a particular item;

wherein the step of assigning items to categories in the target scheme includes;

receiving information about the particular item;

determining, from the information, a source category to which the particular item was assigned in the first source scheme;

determining a set of probability values, wherein each probability value in the set of probability values corresponds to a target category and represents an estimate of the probability that items associated with said source category should be assigned to said target category; and

assigning the particular item to a target category based, in part, on the source category to which the particular item was assigned and said set of probability values;

wherein the steps of the method are performed by one or more computing devices.

2. The method of claim 1 wherein:

the items assigned to the target categories in the target scheme also include a second set of items;

items in the second set of items have previously been assigned to source categories in a second source scheme that is different from said target scheme, and that is different from said first source scheme;

wherein the second set of items includes a second item;

wherein the step of assigning items to categories in the target scheme includes;

receiving information about the second item;

determining, from the information, a source category to which the second item was assigned in the second source scheme;

determining a second set of probability values, wherein each probability value in the second set of probability values corresponds to a target category and represents an estimate of the probability that items associated with said source category to which said second item was assigned should be assigned to said target category; and

assigning the particular item to a target category based, in part, on said second set of probability values.

3. The method of claim 2 wherein:

a first source identifier that identifies the first source is treated as a component of the source category of the particular item; and

a second source identifier that identifies the second source is treated as a component of the source category of the second item.

4. The method of claim 1 wherein a source identifier that identifies the first source is treated as a component of the source category of the particular item.

5. The method of claim 1 wherein:

the items are products; and

the step of automatically assigning items to target categories in a target scheme includes assigning products, offered by a plurality of merchants, to target categories in a shopping web site.

6. The method of claim 3 wherein:

the step of receiving information about the particular item includes receiving a product offer record for a particular product offered by a particular merchant;

the step of determining, from the information, a source category to which the particular item was assigned in the first source scheme includes determining, from the product offer record, a merchant category to which said particular merchant assigned said particular product.

7. The method of claim 1 wherein:

the items are products;

the step of automatically assigning items to target categories in a target scheme includes assigning products, offered by a plurality of merchants, to target categories in a shopping web site; and

each probability value in the set of probability values corresponds to a target category and represents an estimate of the probability that a product associated with said plurality of merchants should be assigned to said target category.

8. The method of claim 1 further comprising:

determining whether a source category associated with a new item is a non-determinative source category; and

if the source category associated with the new item is a non-determinative source category, then assigning the new item to a target category without estimating the probability that items associated with said source category should be assigned to each target category.

9. The method of claim 1 further comprising:

determining whether a source category associated with a new item is an insufficiently sampled source category; and

if the source category associated with the new item is an insufficiently sampled source category, then assigning the new item to a target category without estimating the probability that items associated with said source category should be assigned to each target category.

10. The method of claim 1 wherein the step of assigning the particular item to a target category is based on assignments made to items that belong to a training set.

11. The method of claim 10 wherein:

items from said training set that are associated with said source category have been assigned to a subset of the target categories of the target scheme; and

the step of assigning the particular item to a target category includes disqualifying, as target categories to which the particular item may be assigned, all target categories that do not belong to said subset.

12. The method of claim 1 wherein:

the step of assigning the particular item to a target category is based, in part, on assignments made to items that belong to a training set; and

a smoothing function is applied to statistics associated with the training set to determine the set of probability values.

13. The method of claim 1, wherein the step of assigning the particular item to a target category based, in part, on the source category to which the particular item was assigned includes:

determining, based on a source-category-to-cluster mapping, a cluster to which said source category has been mapped, and

assigning the particular item to a target category based, in part, on the cluster to which the source category has been mapped.

14. The method of claim 13 wherein the step of assigning the particular item to a target category based, in part, on the cluster to which the source category has been mapped includes:

determining a set of probability values, wherein each probability value in the set of probability values corresponds to a target category and represents an estimate of the probability that items associated with categories that map to said cluster should be assigned to said target category; and

assigning the particular item to a target category based, in part, on said set of probability values.

15. The method of claim 14 wherein:

the source-category-to-cluster mapping maps source categories to clusters; and

the clusters include at least one cluster to which source categories from multiple source schemes have been mapped.

16. The method of claim 14 further comprising:

determining whether a cluster associated with a new item is a non-determinative cluster; and

if the cluster associated with the new item is a non-determinative cluster, then assigning the new item to a target category without estimating the probability that items associated with source categories that map to said cluster should be assigned to each target category.

17. The method of claim 14 further comprising:

determining whether a cluster associated with a new item is an insufficiently sampled cluster; and

if the cluster associated with the new item is an insufficiently sampled cluster, then assigning the new item to a target category without estimating the probability that items associated with said source categories that map to said cluster should be assigned to each target category.

18. A non-transitory computer-readable medium that stores instructions which, when executed by one or more processors, cause one or more computing devices to perform the steps of:

automatically assigning items to target categories in a target scheme;

wherein the items assigned to the target categories in the target scheme include a first set of items;

wherein items in the first set of items have previously been assigned to source categories in a first source scheme that is different from said target scheme;

wherein the first set of items includes a particular item;

wherein assigning items to categories in the target scheme includes;

receiving information about the particular item;

determining, from the information, a source category to which the particular item was assigned in the first source scheme;

determining a set of probability values, wherein each probability value in the set of probability values corresponds to a target category and represents an estimate of the probability that items associated with said source category should be assigned to said target category; and

assigning the particular item to a target category based, in part, on the source category to which the particular item was assigned and said set of probability values.

19. The non-transitory computer-readable medium of claim 18, wherein:

the items are products;

the step of automatically assigning items to target categories in a target scheme includes assigning products, offered by a plurality of merchants, to target categories in a shopping web site; and

each probability value in the set of probability values corresponds to a target category and represents an estimate of the probability that a product associated with said plurality of merchants should be assigned to said target category.

20. The computer-readable storage of claim 18 wherein the step of assigning the particular item to a target category based, in part, on the source category to which the particular item was assigned includes:

determining, based on a source-category-to-cluster mapping, a cluster to which said source category has been mapped, and

assigning the particular item to a target category based, in part, on the cluster to which the source category has been mapped.

21. The computer-readable storage of claim 20 wherein the step of assigning the particular item to a target category based, in part, on the cluster to which the source category has been mapped includes:

determining a set of probability values, wherein each probability value in the set of probability values corresponds to a target category and represents an estimate of the probability that items associated with categories that map to said cluster should be assigned to said target category; and

assigning the particular item to a target category based, in part, on said set of probability values.

22. The non-transitory computer-readable medium of claim 18 wherein:

the items assigned to the target categories in the target scheme also include a second set of items;

items in the second set of items have previously been assigned to source categories in a second source scheme that is different from said target scheme, and that is different from said first source scheme;

wherein the second set of items includes a second item;

wherein the step of assigning items to categories in the target scheme includes;

receiving information about the second item;

determining, from the information, a source category to which the second item was assigned in the second source scheme;

determining a second set of probability values, wherein each probability value in the second set of probability values corresponds to a target category and represents an estimate of the probability that items associated with said source category to which said second item was assigned should be assigned to said target category; and

assigning the particular item to a target category based, in part, on said second set of probability values.