Method for a topic hierarchy classification system

• US 6,947,936 B1
• Filed: 04/30/2001
• Issued: 09/20/2005
• Est. Priority Date: 04/30/2001
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Suermondt, Henri Jacques, Forman, George Henry
• Primary Examiner(s): Alam, Shahid
• Assistant Examiner(s): EHICHIOYA, FRED I
• Application Number:
  US09/846,069
• Time in Patent Office: 1,604 Days
• Field of Search: 707 1- 10, 707/100, 707/101, 707/103.R, 707/104.1, 707/200, 707/202, 707/102, 707/104, 715/12, 715/512, 706/47, 706/16, 706/12
• US Class Current: 1/1
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A method and system is provided for categorization of an item. A plurality of categories is organized in a hierarchy of categories with a plurality of categorizers corresponding to the plurality of categories. A featurizer featurizes the item to create a list of item features. The list is used in a categorizer system, including the plurality of categorizers, for determining a plurality of levels of goodness. The item is categorized in the categorizer system in the plurality of categories based on the respective plurality of levels of goodness. The best categories are processed first, allowing termination at any time. The system successively refines an item down a hierarchy, until the features no longer support further refinement. The categories and the degree of support for the categories are provided.

Claims

1. A computer based method for categorization of an item comprising:

providing a plurality of categories organized in a hierarchy of categories;

providing a plurality of categorizers corresponding to the plurality of categories;

featurizing the item to create a list of item features;

using the list of item features in a categorizer system including the plurality of categorizers for determining a plurality of levels of goodness, wherein using the list of item features determines the plurality of levels of goodness using a process to quantify the plurality of levels of goodness, to prioritize the plurality of levels of goodness, and to resolve two levels of goodness into a third level of goodness;

using one of the plurality of levels of goodness for invoking an additional categorizer of the plurality of categorizers as required;

categorizing the item in the categorizer system in the plurality of categories based on the respective plurality of levels of goodness; and

returning the item categorized.

2. The method as claimed in claim 1 including:

using a categorizer system knowledge base for determining the level of goodness for a category with the list of item features.

3. The method as claimed in claim 1 including:

listing the plurality of categories and the respective levels of goodness on a list; and

categorizing from the list.

4. The method as claimed in claim 1 wherein:

returning one category for the item among the plurality of categories selected from a group consisting of the one category with the best level of goodness for all the plurality of categories and with the best level of goodness for which determining is completed where all of the plurality of categories are not compared.

5. The method as claimed in claim 1 wherein:

returning a plurality of categories for the item among the plurality of categories returns a plurality of categories selected from a group consisting of categories up to a fixed number of the plurality of categories, categories having more than a fixed level of goodness, categories fulfilling a user specified preference, categories not from a categorizer, and categories which are a combination thereof.

6. The method as claimed in claim 1 wherein:

returning the category for a plurality of items establishes a categorizer system knowledge base for a topic hierarchy.

7. The method as claimed in claim 1 including:

listing a plurality of labels for each of the plurality of categories; and

training a categorizer system trainer using a plurality of items having known categories and the plurality of labels to provide a categorizer system knowledge base.

8. The method as claimed in claim 1 including:

providing a categorizer system knowledge base;

using a plurality of items with known categories to learn knowledge in the categorizer system knowledge base.

9. The method as claimed in claim 1 including:

providing a categorizer system knowledge base;

providing a plurality of categorizers, each using knowledge in a categorizer system knowledge base and the list of item features to compute a degree of goodness for a plurality of categories, independent of other categorizers, each using a subset of item features to compute a degree of goodness for a plurality of categories, independent of other categorizers, and each subset independent of subsets used by other categorizers; and

providing a mechanism to resolve the levels of goodness for a plurality of categories resulting from multiple categorizers into a combined level of goodness for a plurality of categories.

10. A computer based method for categorization of an item comprising:

featurizing the item to create a list of item features;

providing a plurality of categories organized in a hierarchy of categories and having respective lists of category features using a categorizer system knowledge base for determining the lists of category features;

providing a plurality of categorizers corresponding to one of the plurality of categories, each of the plurality of categorizers using knowledge in the categorizer system knowledge base and the list of item features to compute a degree of goodness for a plurality of categories independent of other categorizers, each of the plurality of categorizers using a subset of item features to compute a degree of goodness for a plurality of categories independent of other categorizers, and each subset independent of subsets used by other categorizers;

using the list of item features in a categorizer system including the plurality of categorizers with the lists of category features to respectively determine a plurality of levels of goodness, the plurality of levels of goodness determined using a process to quantify the plurality of levels of goodness, to prioritize the plurality of levels of goodness, and to resolve two levels of goodness into a third level of goodness;

using one of the plurality of levels of goodness for invoking an additional categorizer of the plurality of categorizers as required;

categorizing the item in the categorizer system in the plurality of categories based on the respective plurality of levels of goodness;

listing the plurality of categories and the respective levels of goodness on a list;

returning a category for the item from the list; and

providing a mechanism to resolve the levels of goodness for a plurality of categories resulting from multiple categorizers into a combined level of goodness for a plurality of categories.

11. A computer based method for categorization of a document comprising:

providing a plurality of categories organized in a hierarchy of categories;

providing a plurality of categorizers corresponding to the plurality of categories;

featurizing the document to create a list of document features;

using the list of document features in a categorizer system including the plurality of categorizers for determining a plurality of levels of goodness, wherein using the list of item features determines the plurality of levels of goodness using a process to quantify the plurality of levels of goodness, to prioritize the plurality of levels of goodness, and to resolve two levels of goodness into a third level of goodness;

using one of the plurality of levels of goodness for invoking an additional categorizer of the plurality of categorizers as required;

categorizing the document in categorizer system in the plurality of categories based on the respective plurality of levels of goodness; and

returning a category for the document.

12. The method as claimed in claim 11 wherein:

determining the plurality of levels of goodness includes using a process selected from a group consisting of Naive Bayes, quantitative decision-tree classifiers such as C4.5, Bayesian networks, rule-based multi-class classifiers that output a degree of goodness, conditional probability statements, simple heuristics, and a combination thereof.

13. The method as claimed in claim 11 including:

using a categorizer system knowledge base for determining the level of goodness for a category with the list of document features.

14. The method as claimed in claim 11 including:

listing the plurality of categories as the document is compared and the respective levels of goodness on a list; and

categorizing from the list.

15. The method as claimed in claim 11 wherein:

returning one category for the document among the plurality of categories selected from a group consisting of the one category with the best level of goodness for all the plurality of categories and with the best level of goodness for which determining is completed where all of the plurality of categories are not compared.

16. The method as claimed in claim 11 wherein:

returning a plurality of categories for the document among the plurality of categories returns a plurality of categories selected from a group consisting of categories up to a fixed number of the plurality of categories, categories having more than a fixed level of goodness, categories fulfilling a user specified preference, categories not from a categorizer, and categories which are a combination thereof.

17. The method as claimed in claim 11 wherein:

returning the category for a plurality of documents establishes a categorizer system knowledge base for a topic hierarchy.

18. The method as claimed in claim 11 including:

listing a plurality of labels for each of the plurality of categories; and

training a categorizer system trainer using a plurality of documents having known categories and the plurality of labels to provide a categorizer system knowledge base.

19. The method as claimed in claim 11 including:

providing a categorizer system knowledge base;

using a plurality of documents with known categories to learn knowledge in the categorizer system knowledge base.

20. The method as claimed in claim 11 including:

providing a categorizer system knowledge base;

providing a plurality of categorizers, each using knowledge in a categorizer system knowledge base and the list of document features to compute a degree of goodness for a plurality of categories, independent of other categorizers, each using a subset of document features to compute a degree of goodness for a plurality of categories, independent of other categorizers, and each subset independent of subsets used by other categorizers; and

providing a mechanism to resolve the levels of goodness for a plurality of categories resulting from multiple categorizers into a combined level of goodness for a plurality of categories.

21. A computer based method for categorization of a document comprising:

featurizing the document to create a list of document features;

providing a plurality of categories organized in a hierarchy of categories and having respective lists of category features using a categorizer system knowledge base resulting from determining a plurality of documents for determining the lists of category features;

providing a plurality of categorizers corresponding to the plurality of categories, each of the plurality of categorizers using knowledge in the categorizer system knowledge base and the list of document features to compute a degree of goodness for a plurality of categories independent of other categorizers, each of the plurality of categorizers using a subset of document features to compute a degree of goodness for a plurality of categories, independent of other categorizers, and each subset independent of subsets used by other categorizers;

using the list of document features in a categorizer system including the plurality of categorizers with the lists of category features to respectively determine a plurality of levels of goodness;

using one of the plurality of levels of goodness for invoking an additional categorizer of the plurality of categorizers as required;

categorizing the document in categorizer system including the plurality of categorizers in the plurality of categories based on the respective plurality of levels of goodness from the list;

listing the plurality of categories as the document is compared and the respective levels of goodness on a list;

returning a category for the document from the list; and

providing a mechanism to resolve the levels of goodness for a plurality of categories resulting from multiple categorizers into a combined level of goodness for a plurality of categories.

22. A computer based system for categorization of an item comprising:

a plurality of categories organized in a hierarchy of categories;

a plurality of categorizers corresponding to the plurality of categories;

a featurizer for featurizing the item to create a list of item features;

a categorizer system including the plurality of categorizers using the list of item features in determining a plurality of levels of goodness, wherein using the list of item features determines the plurality of levels of goodness using a process to quantify the plurality of levels of goodness, to prioritize the plurality of levels of goodness, and to resolve two levels of goodness into a third level of goodness, the categorizer system for categorizing the item in the plurality of categories based on the respective plurality of levels of goodness, the categorizer system for using one of the plurality of levels of goodness for invoking an additional categorizer as required; and

a return for returning the item categorized.

23. The system as claimed in claim 22 wherein:

determining the plurality of levels of goodness includes using a process to quantify the plurality of levels of goodness, to prioritize the plurality of levels of goodness, and to resolve two levels of goodness into a third level of goodness.

24. The system as claimed in claim 22 including:

a categorizer system knowledge base for determining the level of goodness for a category with the list of item features.

25. The system as claimed in claim 22 including:

a categorizer system trainer trained using a plurality of items having known categories and the plurality of labels to provide a categorizer system knowledge base.

26. A computer based system for categorization of an item comprising:

a categorizer system knowledge base having a plurality of categories organized in a hierarchy of categories and having respective lists of category features;

a featurizer for featurizing the item to create a list of item features;

a categorizer system connected to the categorization system knowledge base including;

a plurality of categorizers having one of the plurality of categories, the plurality of categorizers for using the list of item features with the lists of category features and knowledge in the categorizer system knowledge base to respectively determine a plurality of levels of goodness using a process to quantify the plurality of levels of goodness, prioritize the plurality of levels of goodness, and to resolve two levels of goodness into a third level of goodness, the plurality of categorizers categorizing the item in the categorizer system in the plurality of categories based on the respective plurality of levels of goodness;

a mechanism for using one of the plurality of levels of goodness for invoking an additional categorizer of the plurality of categorizers as required; and

a return for returning the item categorized.

27. The system as claimed in claim 26 wherein:

the plurality of categorizers determine the plurality of levels of goodness using a process to quantify the plurality of levels of goodness, to prioritize the plurality of levels of goodness, and to resolve two levels of goodness into a third level of goodness.

28. The system as claimed in claim 26 wherein:

the categorizer system knowledge base determines the lists of category features.

29. The system as claimed in claim 26 wherein:

the plurality of categorizers include a list mechanism for listing the plurality of categories and the respective levels of goodness; and

the plurality of categorizers categorizes from the list mechanism.

30. The system as claimed in claim 26 wherein:

the return returns one category for the item among the plurality of categories elected from a group consisting of the one category with the best level of goodness for all the plurality of categories and with the best level of goodness for which determining is completed where all of the plurality of categories are not compared.

31. The system as claimed in claim 26 wherein:

the return returns a plurality of categories for the item among the plurality of categories returns a plurality of categories selected from a group consisting of categories up to a fixed number of the plurality of categories, categories having more than a fixed level of goodness, categories fulfilling a user specified preference, categories not from a categorizer, and categories which are a combination thereof.

32. The system as claimed in claim 26 wherein:

the return returns the category for a plurality of items to the categorizer system knowledge base for building a topic hierarchy.

33. The system as claimed in claim 26 including:

a further listing mechanism for listing a plurality of labels for each of the plurality of categories; and

a categorizer system trainer trained using a plurality of items having known categories and the plurality of labels to provide the categorizer system knowledge base.

34. A computer based system for categorization of an item comprising:

a categorizer system knowledge base having a plurality of categories organized in a hierarchy of categories and having respective lists of category features;

a featurizer for featurizing the item to create a list of item features; and

a categorizer system connected to the categorizer system knowledge base including;

a plurality of categorizers having the plurality of categories, the plurality of categorizers for determining the list of item features with the lists of category features and knowledge in the categorizer system knowledge base to respectively determine a plurality of levels of goodness using a process to quantify the plurality of levels of goodness, prioritize the plurality of levels of goodness, and to resolve two levels of goodness into a third level of goodness, the plurality of categorizers categorizing the item in the categorizer system in the plurality of categories based on the respective plurality of levels of goodness;

a mechanism for using one of the plurality of levels of goodness for invoking an additional categorizer of the plurality of categorizers as required;

a listing mechanism for listing the plurality of categories and the respective levels of goodness on a list; and

a return for returning a category for the item from the list.