Very-large-scale automatic categorizer for Web content

• US 20050021545A1
• Filed: 08/20/2004
• Published: 01/27/2005
• Est. Priority Date: 05/07/2001
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Lulich, Daniel P., Guilak, Farzin G.
• Application Number:
  US10/923,431
• Publication Number:
  US 20050021545A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3323 using document space presentation or visualization, e.g. category, hierarchy or range presentation and selection
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing
• CPC Class Codes: Y10S 707/914 Video
• CPC Class Codes: Y10S 707/915 Image
• CPC Class Codes: Y10S 707/916 Audio
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A method and apparatus for efficiently classifying and categorizing data objects such as electronic text, graphics, and audio based documents within very-large-scale hierarchical classification trees is provided. In accordance with one embodiment of the invention, a first node of a plurality of nodes of a subject hierarchy is selected. Previously classified data objects corresponding to a selected first node of a subject hierarchy as well as any associated sub-nodes of the selected node are aggregated to form a content class of data objects. Similarly, data objects corresponding to sibling nodes of the selected node and any associated sub-nodes of the sibling nodes are then aggregated to form an anti-content class of data objects. Features are then extracted from each of the content class of data objects and the anti-content class of data objects to facilitate characterization of said previously classified data objects.

Claims

1. A method of training a classifier system by utilizing previously classified data objects comprising one or more electronic documents and organized into a subject hierarchy of a plurality of nodes, the method comprising:

selecting one node of the plurality of nodes;

aggregating those of the previously classified data objects corresponding to the selected node and any associated sub-nodes of the selected node, to form a content class of data objects, said content class of data objects comprising a content class of the one or more electronic documents;

aggregating those of the previously classified data objects corresponding to any associated sibling nodes of the selected node and any associated sub-nodes of the sibling nodes to form an anti-content class of data objects, said anti-content class of data objects comprising an anti-content class of the one or more electronic documents; and

extracting features from at least one of the content class of data objects and the anti-content class of data objects to facilitate characterization of said previously classified data objects.

12. The method of claim 1, wherein said one or more electronic documents comprise at least one of a text document, an image file, an audio sequence, a video sequence, and a hybrid document including a combination of text and images.

2-11. -11. (canceled)

13. A method of classifying a data object, the method comprising:

selecting a first node of a hierarchically organized classifier having a plurality of nodes;

determining if the first node of said plurality of nodes is the parent of one or more child nodes;

upon determining that said first node is the parent of one or more child nodes, selecting a first of said one or more child nodes and classifying said data object at the first of said one or more child nodes to produce a confidence rating, said data object comprising an electronic document;

recursively selecting each of said one or more child nodes that remain and classifying the data object at each selected one or more child nodes to respectively produce a confidence rating for each selected one or more child nodes; and

assigning the data object to each node of said plurality of nodes having produced an acceptable confidence rating.

14. The method of claim 13, wherein the first node is a root node.

15. The method of claim 13, wherein said acceptable confidence rating comprises a confidence rating that exceeds a minimum threshold.

16. The method of claim 13, further comprising:

assigning the data object to the first node if the first node is the parent of said one or more child nodes and none of said one or more child nodes producing a confidence rating that exceeds the minimum threshold.

17. The method of claim 13, wherein if said first node is a root node, then categorizing the data object as undefined.

18. The method of claim 13, further comprising:

determining a mean and standard deviation of the confidence ratings of the one or more child nodes.

19. The method of claim 18, wherein the data object is assigned to only those of the plurality of nodes having an associated confidence rating that exceeds the mean minus the standard deviation.

20. The method of claim 13, further comprising:

determining if at least one of said child nodes producing an acceptable confidence rating is a parent of one or more additional child nodes; and

upon determining that at least one of said child nodes producing an acceptable confidence rating is a parent of said one or more additional child nodes, successively selecting and classifying each of said additional child nodes.

22. The method of claim 13, wherein said electronic document comprises at least one of a text document, an image file, an audio sequence, a video sequence, and a hybrid document including a combination of text and images.

21. (canceled)

23-34. -34. (canceled)

35. An apparatus comprising:

a storage medium having stored therein a plurality of programming instructions designed to implement a plurality of functions of a category name service for providing a category name to a data object, including first one or more functions to

select a first node of a hierarchically organized classifier having a plurality of nodes,

determine if the first node of said plurality of nodes is a parent of one or more child nodes,

select a first of said one or more child nodes and classify said data object at the first of said one or more child nodes to produce a confidence rating if said first node is the parent of one or more child nodes,

select each of said one or more child nodes that remain and classify the data object at each selected one or more child nodes to respectively produce a confidence rating for each selected one or more child nodes,

assign the data object to each node of said plurality of nodes having produced an acceptable confidence rating; and

a processor coupled to the storage medium to execute the programming instructions.

36. The apparatus of claim 35, wherein the first node is a root node.

37. The apparatus of claim 35, wherein said acceptable confidence rating comprises a confidence rating that exceeds a minimum threshold.

38. The apparatus of claim 35, wherein said plurality of programming instructions further comprises instructions to

assign the data object to the first node if the first node is the parent of said one or more child nodes and none of said one or more child nodes produces a confidence rating that exceeds the minimum threshold.

39. The apparatus of claim 35, wherein if said first node is a root node, then said data object is categorized as undefined.

40. The apparatus of claim 35, wherein said plurality of instructions further determine a mean and standard deviation of the confidence ratings of the one or more child nodes.

41. The apparatus of claim 40, wherein the data object is assigned to only those of the plurality of nodes having an associated confidence rating that exceeds the mean minus the standard deviation.

42. The apparatus of claim 35, wherein said plurality of programming instructions further comprises instructions to

determine if at least one of said child nodes producing an acceptable confidence rating is a parent of one or more additional child nodes;

and

successively select and classify each of said additional child nodes, if it is determined that at least of said child nodes producing an acceptable confidence rating is a parent of said one of more additional child nodes.

43. The apparatus of claim 35, wherein said data object comprises an electronic document.

44. The apparatus of claim 43, wherein said electronic document comprises at least one of the text document, an image file, an audio sequence, a video sequence, and a hybrid document including a combination of text and images.