OBJECT CLASSIFICATION USING TAXONOMIES

• US 20100185577A1
• Filed: 03/30/2009
• Published: 07/22/2010
• Est. Priority Date: 01/16/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Papadimitriou, Panagiotis, Getoor, Lise C., Agrawal, Rakesh, Fuxman, Ariel D., Tsaparas, Panayiotis
• Granted Patent: US 8,275,726 B2
• Time in Patent Office: Days
• US Class Current: 706/52
• CPC Class Codes: G06F 16/906 Clustering; Classification
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

As provided herein objects from a source catalog, such as a provider'"'"'s catalog, can be added to a target catalog, such as an enterprise master catalog, in a scalable manner utilizing catalog taxonomies. A baseline classifier determines probabilities for source objects to target catalog classes. Source objects can be assigned to those classes with probabilities that meet a desired threshold and meet a desired rate. A classification cost for target classes can be determined for respective unassigned source objects, which can comprise determining an assignment cost and separation cost for the source objects for respective desired target classes. The separation and assignment costs can be combined to determine the classification cost, and the unassigned source objects can be assigned to those classes having a desired classification cost.

Claims

1. A method for classifying objects from a source catalog to a target catalog, comprising:

determining a probability that an object from a source catalog belongs to a class in a target catalog for respective classes in the target catalog using a baseline statistical classification algorithm;

assigning a source object to a target class corresponding to a desired target class probability for the source object if the target class probability meets a desired threshold;

determining a classification cost for assigning an unassigned source object to a target class for respective target classes from a set of desired target classes, comprising;

determining an assignment cost for respective desired target classes for the unassigned source object, the assignment cost comprising a function of the probability that the unassigned source object belongs to the target class;

determining a separation cost of the unassigned source object for respective desired target classes, comprising combining a function of distance between a desired target class for the unassigned source object and an assigned source object'"'"'s target class and a function of similarity between the unassigned source object and the assigned source object; and

combining the assignment cost and separation cost of the source object for respective desired target classes; and

assigning the unassigned source object to a target class corresponding to a desired classification cost for the unassigned source object.

2. The method of claim 1, assigning a source object to a target class corresponding to a desired target class probability for the source object comprising assigning a source object to a target class corresponding to a highest target class probability for the source object.

3. The method of claim 1, the desired threshold comprising a probability value that yields a desired source object assignment error rate when training the baseline statistical classification algorithm.

4. The method of claim 1, selecting a set of desired target classes comprising selecting a desired number of target classes having a desired probability, the desired number of target classes corresponding to a number of classes that meets an accuracy threshold for a set of desired target classes object classification, determined when training the baseline statistical classification algorithm.

5. The method of claim 1, determining an assignment cost comprising:

determining a probability that an object belongs to respective desired target classes using the baseline statistical classification algorithm; and

calculating a function of the probability for respective desired target classes.

6. The method of claim 5, the assignment cost (A(x,l)) for assigning an object (x) to a target class (l) comprising:

A(x,l)=1−

P(x,l)

where P(x,l) is a probability that x belongs in l.

7. The method of claim 1, determining a function of distance between the target class for the unassigned source object and the assigned source object'"'"'s target class comprising determining a function of a number of node hops from the target class for the unassigned source object to the assigned source object'"'"'s target class in a hierarchical taxonomy tree of target classes.

8. The method of claim 7, determining a function of distance (dist) between the target class for the unassigned source object (l) and the assigned source object'"'"'s target class (t_y) comprising:

dist(l,t_y)=1−

2<sup>−

hops(l,ty)</sup>

where hops(l,t_y) is a number of node hops from the target class for the unassigned source object (l) to the assigned source object'"'"'s target class (t_y) in the hierarchical taxonomy tree of the target classes.

9. The method of claim 1, determining a function of similarity between the unassigned source object and an assigned source object, comprising determining a similarity between the unassigned source object'"'"'s source class and the assigned source object'"'"'s source class from the source catalog.

10. The method of claim 9, determining a similarity between the unassigned source object'"'"'s source class and the assigned source object'"'"'s source class from the source catalog comprising calculating a function of a distance between the unassigned source object'"'"'s source class and the assigned source object'"'"'s source class in the source catalog.

11. The method of claim 1, combining a function of similarity (sim) between the unassigned source object (x) and the assigned source object (y) and a function of distance (dist) between the target class for the unassigned source object (l) and the assigned source object'"'"'s target class (t_y) comprising:

12. The method of claim 1, combining the assignment cost and separation cost comprising:

summing the assignment cost and separation cost; and

combining a regularization parameter with the combination of the assignment cost and separation cost.

13. The method of claim 1, assigning the unassigned source object to a target class corresponding to a desired classification cost for the unassigned source object comprising assigning the unassigned source object to a target class corresponding to a lowest classification cost for the unassigned source object.

14. The method of claim 1, combining a function of similarity and a function of distance to determine a separation cost of the unassigned source object for respective desired target classes comprising combining a normalization factor with the combination of the function of similarity and a function of distance, the normalization factor comprising a function that compensates for an uneven distribution of objects in a hierarchical taxonomy tree.

15. The method of claim 1, comprising training the baseline statistical classification algorithm with source objects that are assigned to target classes using a classification cost and their corresponding target class to which they were assigned.

16. A system for classifying objects from a source catalog to a target catalog, comprising:

a baseline classifier configured to determine a probability that an object from a source catalog belongs to a class in a target catalog for respective classes in the target catalog;

an object assignment component configured to assign a source object to a target class corresponding to a desired probability for the source object if the desired probability meets a desired threshold;

a classification cost determination component configured to determine a classification cost of an unassigned source object for respective target classes from a set of desired target classes, comprising;

an assignment cost determination component configured to determine an assignment cost of respective desired target classes for the unassigned source object, the assignment cost comprising a function of the probability that the unassigned source object belongs to a desired target class;

a separation cost determination component configured to determine a separation cost of the unassigned source object for the respective desired target classes, the separation cost comprising a combination of a function of similarity between the unassigned source object and an assigned source object and a function of distance between a desired target class for the unassigned source object and the assigned source object'"'"'s target class; and

a combination component configured to combine the assignment cost and separation cost of respective source objects for respective desired target classes; and

an unassigned object assignment component configured to assign respective unassigned source objects to corresponding target classes having a desired classification cost for the unassigned source objects.

17. The system of claim 16, comprising a desired target class selection component configured to select a number of desired target classes for an unassigned source object corresponding to a number of classes that meets an accuracy threshold for a set of desired target classes object classification, determined when training the baseline statistical classification algorithm for the source catalog.

18. The system of claim 16, the separation cost determination component comprising:

a distance determiner configured to determine a function of a number of node hops from the target class for the unassigned source object to the assigned source object'"'"'s target class in a hierarchical taxonomy tree of target classes; and

a similarity determiner configured to determine a similarity between the unassigned source object'"'"'s source class and the assigned source object'"'"'s source class from the source catalog.

19. The system of claim 16, comprising a normalization factor determination component configured to determine a normalization factor used by the separation cost determination component to compensate for an uneven distribution of objects in a hierarchical taxonomy tree when combining the function of similarity and the function of distance of source objects for desired target classes.

20. A method for classifying products from a source catalog to a target catalog, comprising:

determining a probability that an object from a source catalog belongs to a class in a target catalog for respective classes in the target catalog using a baseline statistical classification algorithm;

assigning a source object to a target class corresponding to a highest target class probability for the source object if the target class probability meets a desired threshold;

determining a classification cost for assigning an unassigned source object to a target class for respective target classes from a set of desired target classes, comprising;

determining an assignment cost for respective desired target classes for the unassigned source object, comprising;

determining a probability that an object belongs to respective desired target classes using the baseline statistical classification algorithm; and

calculating a function of the probability for respective desired target classes;

determining a separation cost of the unassigned source object for respective desired target classes, comprising;

determining a function of distance between the target class for the unassigned source object and the assigned source object'"'"'s target class comprising determining a number of node hops from the target class for the unassigned source object to the assigned source object'"'"'s target class in a hierarchical taxonomy tree of target classes;

determining a function of similarity between the unassigned source object and an assigned source object comprising determining a similarity between the unassigned source object'"'"'s source class and the assigned source object'"'"'s source class from the source catalog; and

combining the function of similarity and the function of distance with a normalization factor; and

summing the assignment cost with a combination of a regularization parameter and the separation cost; and

assigning the unassigned source object to a target class corresponding to a lowest classification cost for the unassigned source object.