# US 2001/0037324 A1 · Multilevel taxonomy based on features derived from training documents classification using fisher values as discrimination values

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2001/0037324 A1
- Document ID: US20010037324A1
- Status: Published application
- Kind: A1
- Application number: 09/777,278
- Filed: 2001-02-05
- Published: 2001-11-01
- Earliest claimed: 1997-06-24
- Assignees: International Business Machines Corporation
- Inventors: Rakesh Agrawal; Soumen Chakrabarti; Byron Edward Dom; Prabhakar Raghavan
- Web page: https://patentgrep.com/patent/US20010037324A1

## CPC

- G06F 16/355: Creation or modification of classes or clusters
- Y10S 707/99932: Access augmentation or optimizing
- Y10S 707/99936: Pattern matching access
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## 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.

## Claims

### Claim 1

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.

### Claim 2 (depends on 1)

A process as recited in claim 1, wherein said step of associating comprises the steps of:
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; and
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.

### Claim 3 (depends on 1)

A process as recited in claim 1, wherein said step of classifying comprises:
scanning each new document to determine the features in the document; and
defining, for each of said plurality of said plurality of nodes and for each new document, the probability that the new document is classified under the node, based on the set of features associated with the node and the features in the document.

### Claim 4 (depends on 3)

A process as recited in claim 3, wherein said step of defining the probability comprises the step of applying a statistical model to define said probability that features in each given new document would occur at the frequency at which they do occur in the given new document.

### Claim 5 (depends on 4)

A process as recited in claim 4, wherein said statistical model comprises a Bernoulli model.

### Claim 6 (depends on 4)

A process as recited in claim 4, wherein said statistical model comprises a Poisson model.

### Claim 7 (depends on 4)

A process as recited in claim 4, wherein said step of classifying further comprises the step of assigning each given new document to at least one respective node in at least one level of the taxonomy, wherein the at least one node to which each given new document is assigned is the node for which the defined probability is above a predefined threshold among all of the nodes at the same level in the taxonomy.

### Claim 8 (depends on 7)

A process as recited in claim 7, wherein the at least one node to which each given new document is assigned is the node for which the defined probability is maximum among all of the nodes at the same level in the taxonomy.

### Claim 9 (depends on 8)

A process as recited in claim 8, wherein said step of assigning each given new document to at least one respective node in at least one level of the taxonomy comprises the step of assigning each given new document to at least one respective node in each of a plurality of levels of the taxonomy.

### Claim 10 (depends on 2)

A process as recited in claim 2, wherein said step of selecting a set of features comprises selecting features that are in a plurality of training documents classified under the associated node and that have discrimination values equal to or above the minimum discrimination value.

### Claim 11 (depends on 2)

A process as recited in claim 2, wherein said step of selecting a set of features comprises selecting features that are in all of training documents classified under the associated node and that have discrimination values equal to or above the minimum discrimination value.

### Claim 12 (depends on 2)

A process as recited in claim 2, wherein said step of determining a discrimination value comprises determining a discrimination value for each feature in a plurality of training documents which are classified under each one of a plurality of the nodes of the taxonomy.

### Claim 13 (depends on 2)

A process as recited in claim 2, wherein said step of determining a discrimination value comprises determining a discrimination value for each feature in all of the training documents which are classified under each one of a plurality of the nodes of the taxonomy.

### Claim 14 (depends on 2)

A process as recited in claim 2, wherein said step of determining a discrimination value for each feature comprises determining a Fisher value for each feature, based on the equation:
20 Fisher ⁡ ( t ) = ∑ c 1 · c 2 ⁢ ⁢ ( μ ⁢ ( c 1 , t ) - μ ⁢ ( c 2 , t ) ) 2 ∑ c ⁢ ⁢ 1 / [LeftBracketingBar] c [RightBracketingBar] ⁢ ⁢ ( x ⁢ ( d , t ) - μ ⁢ ( c , t ) ) 2
where: t represents a term, d represents a document,
μ(c,t)=1/|c|Σd∈c X(d,t), and
x(d,t) =the occurrence rate of t in d.

### Claim 15 (depends on 1)

A process as recited in claim 1, wherein said step of associating a respective set of features with each node comprises the step of determining the number of features to associate with each respective node.

### Claim 16 (depends on 15)

A process as recited in claim 15, wherein said step of associating a respective set of features with each given node comprises the steps of:
ranking, by discrimination power, each of a plurality of features that are in at least one training document classified under the each given node;
providing an optimal number N of features for each given node; and
defining the set of features associated with a given node as the features ranked highest to the Nth highest in said step of ranking.

### Claim 17 (depends on 16)

A process as recited in claim 16, wherein said step of providing an optimal number N comprises the step of determining the number N for each given node based on a test set of documents.

### Claim 18 (depends on 1)

A process as recited in claim 1, further comprising the step of displaying, for given node of a plurality of nodes of the taxonomy, a signature comprising at least one feature associated with the documents classified under the given node.

### Claim 19 (depends on 18)

A process as recited in claim 18, wherein said signature for each given node comprises a plurality of features associated with the documents classified under the given node.

### Claim 20 (depends on 18)

A process as recited in claim 18, wherein said signature for each given node comprises a plurality of features that occur in the documents classified under the given node, but which are determined to have a relatively low frequency of occurrence among documents under the given node.

### Claim 21

A process for searching for documents relevant to a search query from a group of accessible documents containing terms, comprising the steps of:
defining a multilevel taxonomy having a plurality of nodes, including a root node, at least one intermediate node associated with and under the root node and a plurality of terminal nodes associated with and under each intermediate node;
classifying each one of a plurality of training documents with at least one of the terminal and intermediate nodes;
determining a discrimination value for each term in at least one training document which is classified with each one of a plurality of the terminal and intermediate nodes of the taxonomy;
determining a minimum discrimination value for each of said plurality of terminal and intermediate nodes;
selecting a set of feature terms associated with each one of said plurality of terminal and intermediate nodes, said feature terms comprising terms that are in at least one training document classified with the associated node or any node under the associated node and that have discrimination values equal to or above the minimum discrimination value;
receiving a search query:
determining a plurality of search documents, each search document comprising one of the accessible document that is relevant to the search query;
classifying each search document with at least one of the terminal and intermediate nodes of the taxonomy, based on the sets of feature terms associated with the terminal and intermediate nodes of the taxonomy;
displaying a list of nodes with or under which said search documents are classified;
selecting at least one of the displayed nodes; and
displaying at least one search document classified under each selected node.

### Claim 22 (depends on 21)

A process as recited in claim 21:
wherein said search query comprises at least one search term; and
wherein each search document comprises one of the accessible document that contain said at least one search term as one of the terms in the document.

### Claim 23 (depends on 21)

A process as recited in claim 21:
wherein, following said step of selecting at least one of the displayed nodes and prior to said step of displaying at least one search document, said process further includes the steps of displaying a second list of further nodes with or under which said search documents are classified; and selecting at least one of the displayed further nodes; and
wherein said step of displaying at least one search document comprises the step of displaying at least one search document classified under each selected further node.

### Claim 24 (depends on 21)

A process as recited in claim 21, wherein said step of displaying a list of nodes with or under which said search documents are classified further comprises the step of displaying signature terms associated with said search documents classified with or under each of said nodes in the displayed list.

### Claim 25 (depends on 24)

A process as recited in claim 24, wherein said signature terms comprise a plurality of the most frequently occurring terms in the search documents that are also feature terms.

### Claim 26

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 of the taxonomy, the system comprising:
means for 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;
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; and
means for classifying each new document under at least one node, based on the feature terms associated with said at least one node.

### Claim 27 (depends on 26)

A system as recited in claim 26, wherein said means for classifying comprises:
means for scanning each new document to determine the terms in the document; and
means for defining, for each of said plurality of said plurality of nodes and for each new document, the probability that the new document is classified under the node, based on the feature terms associated with the node and the terms in the document.

### Claim 28 (depends on 27)

A system as recited in claim 27, wherein said means for defining the probability comprises means for applying a Bernoulli model to define said probability for each of said plurality of nodes.

### Claim 29 (depends on 26)

A system as recited in claim 26, wherein said means for selecting a set of feature terms comprises means for selecting terms that are in a plurality of training documents classified under the associated node and that have discrimination values equal to or above the minimum discrimination value.

### Claim 30 (depends on 26)

A system as recited in claim 26, wherein said means for selecting a set of feature terms comprises means for selecting terms that are in all of training documents classified under the associated node and that have discrimination values equal to or above the minimum discrimination value.

### Claim 31 (depends on 26)

A system as recited in claim 26, wherein said means for determining a discrimination value comprises means for determining a discrimination value for each term in a plurality of training documents which are classified under each one of a plurality of the nodes of the taxonomy.

### Claim 32 (depends on 26)

A system as recited in claim 26, wherein said means for determining a discrimination value comprises means for determining a discrimination value for each term in all of the training documents which are classified under each one of a plurality of the nodes of the taxonomy.

### Claim 33 (depends on 26)

A system as recited in claim 26, wherein said means for determining a discrimination value for each term comprises means for determining a Fisher value for each term, based on the equation:
21 Fishers ⁡ ( t ) = ∑ c1 , c2 ⁢ ( μ ⁡ ( c 1 , t ) - μ ⁡ ( c 2 , t ) ) 2 ∑ c ⁢ 1 / [LeftBracketingBar] c [RightBracketingBar] ⁢ ( x ⁡ ( d , t ) - ⁣ μ ⁡ ( c , t ) ) 2
where: t represents a term, d represents a document,
μ(c,t)=1/|c|Σd∈cx(d,t), and
x(d,t)=the occurrence rate of t in d.

### Claim 34

A system for searching for documents relevant to a search query from a group of accessible documents containing terms, comprising:
means for defining a multilevel taxonomy having a plurality of nodes, including a root node, at least one intermediate node associated with and under the root node and a plurality of terminal nodes associated with and under each intermediate node;
means for classifying each one of a plurality of training documents with at least one of the terminal and intermediate nodes;
means for determining a discrimination value for each term in at least one training document which is classified with each one of a plurality of the terminal and intermediate nodes of the taxonomy;
means for determining a minimum discrimination value for each of said plurality of terminal and intermediate nodes;
means for selecting a set of feature terms associated with each one of said plurality of terminal and intermediate nodes, said feature terms comprising terms that are in at least one training document classified with the associated node or any node under the associated node and that have discrimination values equal to or above the minimum discrimination value;
means for receiving a search query;
means for determining a plurality of search documents, each search document comprising one of the accessible document that is relevant to the search query;
means for classifying each search document with at least one of the terminal and intermediate nodes of the taxonomy, based on the sets of feature terms associated with the terminal and intermediate nodes of the taxonomy;
means for displaying a list of nodes with or under which said search documents are classified;
means for selecting at least one of the displayed nodes; and
means for displaying at least one search document classified under each selected node.

### Claim 35 (depends on 34)

A system as recited in claim 34:
wherein said search query comprises at least one search term; and
wherein each search document comprises one of the accessible document that contain said at least one search term as one of the terms in the document.

### Claim 36 (depends on 34)

A system as recited in claim 34, wherein said means for displaying a list of nodes with or under which said search documents are classified further comprises means for displaying signature terms associated with said search documents classified with or under each of said nodes in the displayed list.

### Claim 37 (depends on 34)

A system as recited in claim 34, wherein said signature terms comprise a plurality of the most frequently occurring terms in the search documents that are also feature terms.

### Claim 38

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;
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.

### Claim 39 (depends on 38)

An article as recited in claim 38, wherein said step of classifying comprises:
scanning each new document to determine the terms in the document; and
defining, for each of said plurality of said plurality of nodes and for each new document, the probability that the new document is classified under the node, based on the feature terms associated with the node and the terms in the document.

### Claim 40 (depends on 39)

An article as recited in claim 39, wherein said step of defining the probability comprises the step of applying a Bernoulli model to define said probability for each of said plurality of nodes.

### Claim 41 (depends on 38)

An article as recited in claim 38, wherein said step of selecting a set of feature terms comprises selecting terms that are in a plurality of training documents classified under the associated node and that have discrimination values equal to or above the minimum discrimination value.

### Claim 42 (depends on 38)

An article as recited in claim 38, wherein said step of selecting a set of feature terms comprises selecting terms that are in all of training documents classified under the associated node and that have discrimination values equal to or above the minimum discrimination value.

### Claim 43 (depends on 38)

An article as recited in claim 38, wherein said step of determining a discrimination value comprises determining a discrimination value for each term in a plurality of training documents which are classified under each one of a plurality of the nodes of the taxonomy.

### Claim 44 (depends on 38)

An article as recited in claim 38, wherein said step of determining a discrimination value comprises determining a discrimination value for each term in all of the training documents which are classified under each one of a plurality of the nodes of the taxonomy.

### Claim 45 (depends on 38)

An article as recited in claim 38, wherein said step of determining a discrimination value for each term comprises determining a Fisher value for each term, based on the equation:
22 Fishers ⁡ ( t ) = ∑ c1 , c2 ⁢ ( μ ⁡ ( c 1 , t ) - μ ⁡ ( c 2 , t ) ) 2 ∑ c ⁢ 1 / [LeftBracketingBar] c [RightBracketingBar] ⁢ ( x ⁡ ( d , t ) - ⁣ μ ⁡ ( c , t ) ) 2
where: t represents a term, d represents a document,
μ(c,t)=1/|c|Σd∈cx(d,t), and
x(d,t)=the occurrence rate of t in d.

### Claim 46

An article of manufacture comprising a computer program carrier readable by a computer and embodying one or more instructions executable by the computer for searching for documents relevant to a search query from a group of accessible documents containing terms, comprising the steps of:
defining a multilevel taxonomy having a plurality of nodes, including a root node, at least one intermediate node associated with and under the root node and a plurality of terminal nodes associated with and under each intermediate node;
classifying each one of a plurality of training documents with at least one of the terminal and intermediate nodes;
determining a discrimination value for each term in at least one training document which is classified with each one of a plurality of the terminal and intermediate nodes of the taxonomy;
determining a minimum discrimination value for each of said plurality of terminal and intermediate nodes;
selecting a set of feature terms associated with each one of said plurality of terminal and intermediate nodes, said feature terms comprising terms that are in at least one training document classified with the associated node or any node under the associated node and that have discrimination values equal to or above the minimum discrimination value;
receiving a search query;
determining a plurality of search documents, each search document comprising one of the accessible document that is relevant to the search query;
classifying each search document with at least one of the terminal and intermediate nodes of the taxonomy, based on the sets of feature terms associated with the terminal and intermediate nodes of the taxonomy;
displaying a list of nodes with or under which said search documents are classified;
selecting at least one of the displayed nodes; and
displaying at least one search document classified under each selected node.

### Claim 47 (depends on 46)

An article as recited in claim 46, wherein said step of displaying a list of nodes with or under which said search documents are classified further comprises the step of displaying signature terms associated with said search documents classified with or under each of said nodes in the displayed list.

### Claim 48 (depends on 47)

An article as recited in claim 47, wherein said signature terms comprise a plurality of the most frequently occurring terms in the search documents that are also feature terms.
