US 6,233,575 B1Granted

Multilevel taxonomy based on features derived from training documents classification using fisher values as discrimination values

AssigneeInternational Business Machines Corporation

InventorsRakesh Agrawal, Soumen Chakrabarti, Byron Edward Dom, Prabhakar Raghavan

Life of this patent

Estimating the term…

Loading patent…

Abstract

A system, process, and article of manufacture for organizing a large text database into a hierarchy of topics and for maintaining this organization as documents are added and deleted and as the topic hierarchy changes. Given sample documents belonging to various nodes in the topic hierarchy, the tokens (terms, phrases, dates, or other usable feature in the document) that are most useful at each internal decision node for the purpose of routing new documents to the children of that node are automatically detected. Using feature terms, statistical models are constructed for each topic node. The models are used in an estimation technique to assign topic paths to new unlabeled documents. The hierarchical technique, in which feature terms can be very different at different nodes, leads to an efficient context-sensitive classification technique. The hierarchical technique can handle millions of documents and tens of thousands of topics. A resulting taxonomy and path enhanced retrieval system (TAPER) is used to generate context-dependent document indexing terms. The topic paths are used, in addition to keywords, for better focused searching and browsing of the text database.

Claims32

Dependent claims

A process for classifying new documents containing features under nodes defining a multilevel taxonomy, based on features derived from a training set of documents that have been classified under respective nodes of the taxonomy, the process comprising:

associating a respective set of features with each one of said plurality of nodes, each given set of features comprising a plurality of features that are in at least one training document classified under the associated node;
and
classifying each new document under at least one node, based on the set of features associated with said at least one node, further comprising:
determining a discrimination value for each term in at least one training document which is classified under each one of a plurality of the nodes of the taxonomy, wherein the discrimination value comprises a Fisher value based on the equation:
Fisher ⁢ ⁢ ( t ) = ∑ c 1 , c 2 ⁢ ( μ ⁡ ( c 1 , t ) - μ ⁡ ( c 2 , t ) ) 2 ∑ c ⁢ 1 [LeftBracketingBar] c [RightBracketingBar] ⁢ ∑ d ∈ c ⁢ ( n ⁡ ( t , d , c ) - μ ⁡ ( c , t ) ) 2
where t represents a term, d represents a document, c represents a class, μ ⁢ ( c , t ) = 1 [LeftBracketingBar] c [RightBracketingBar] ⁢ ∑ d ∈ c ⁢ x ⁢ ( d , t ) , ⁢ and x ⁡ ( d , t ) = an ⁢ ⁢ occurrence ⁢ ⁢ rate ⁢ ⁢ of ⁢ ⁢ t ⁢ ⁢ in ⁢ ⁢ d ;
determining a minimum discrimination value for each of said plurality of nodes;
wherein the features in each given set of features have discrimination values equal to or above the minimum discrimination value determined for the node associated with the given set of features.

5 more elements

A classifier system for classifying new documents containing terms under nodes defining a multilevel taxonomy, based on feature terms derived from a training set of documents which are classified under respective nodes on the taxonomy, the system comprising:

means for determining discrimination value for each term in at least one training document which is classified under each one of a plurality of the nodes of the taxonomy, wherein the discrimination value comprises a Fisher value based on the equation:
Fisher ⁢ ⁢ ( t ) = ∑ c1 , c2 ⁢ ( μ ⁡ ( c 1 , t ) - μ ⁡ ( c 2 , t ) ) 2 ∑ c ⁢ 1 [LeftBracketingBar] c [RightBracketingBar] ⁢ ∑ d ∈ c ⁢ ( x ⁡ ( t , d , c ) - μ ⁡ ( c , t ) ) 2
where t represents a term, d represents a document, c represents a class, μ ⁡ ( c , t ) = 1 [LeftBracketingBar] c [RightBracketingBar] ⁢ ∑ d ∈ c ⁢ x ⁡ ( d , t ) , ⁢ and x ⁡ ( d , t ) = an ⁢ ⁢ occurrence ⁢ ⁢ rate ⁢ ⁢ of ⁢ ⁢ t ⁢ ⁢ in ⁢ ⁢ d ;
means for determining a minimum discrimination value for each of said plurality of nodes;
means for selecting a set of feature terms associated with each one of said plurality of nodes, said feature terms comprising terms that are in at least one training document classified under the associated node and that have discrimination values equal to or above the minimum discrimination value;
means for classifying each new document under at least one node, based on the feature terms associated with said at least one node.

3 more elements

An article of manufacture comprising a computer program carrier readable by a computer and embodying one or more instructions executable by the computer to perform a process for classifying new documents containing terms under nodes defining a multilevel taxonomy, based on feature terms derived from a training set of documents which are classified under respective nodes of the taxonomy, the process comprising:

determining a discrimination value for each term in at least one training document which is classified under each one of a plurality of the nodes of the taxonomy, wherein the discrimination value comprises a Fisher value based on the equation:
Fisher ⁢ ⁢ ( t ) = ∑ c1 , c2 ⁢ ( μ ⁡ ( c 1 , t ) - μ ⁡ ( c 2 , t ) ) 2 ∑ c ⁢ 1 [LeftBracketingBar] c [RightBracketingBar] ⁢ ∑ d ∈ c ⁢ ( x ⁡ ( t , d , c ) - μ ⁡ ( c , t ) ) 2
where t represents a term, d represents a document, c represents a class, μ ⁡ ( c , t ) = 1 [LeftBracketingBar] c [RightBracketingBar] ⁢ ∑ d ∈ c ⁢ x ⁡ ( d , t ) , ⁢ and x ⁡ ( d , t ) = an ⁢ ⁢ occurrence ⁢ ⁢ rate ⁢ ⁢ of ⁢ ⁢ t ⁢ ⁢ in ⁢ ⁢ d ;
determining a minimum discrimination value for each of said plurality of nodes;
selecting a set of feature terms associated with each one of said plurality of nodes;
said feature terms comprising terms that are in at least one training document classified under the associated node and that have discrimination values equal to or above the minimum discrimination value;
and
classifying each new document under at least one node, based on the feature terms associated with said at least one node.

5 more elements

Dependencies are inferred from the claim text.