US6233575B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Multilevel taxonomy based on features derived from training documents classification using fisher values as discrimination values
Assignee: International Business Machines Corp
•
Filing: 1998-06-23
•
Granted: 2001-05-15
•
Expires: 2018-06-23
Abstract
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.
Inventors
- 👤 Rakesh Agrawal
- 👤 Soumen Chakrabarti
- 👤 Byron Edward Dom
- 👤 Prabhakar Raghavan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 17:43
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/35; G06F16/355; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99936
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
318 words
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 c ∑ 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 c ∑ 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.
Claim 2
Dependent Claim
318 words
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 c ∑ 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 c ∑ 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.
Claim 3
Dependent Claim
46 words
A process as recited in claim 1 , 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 4
Dependent Claim
69 words
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 5
Dependent Claim
49 words
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 6
Dependent Claim
16 words
A process as recited in claim 4 , wherein said statistical model comprises a Bernoulli model.
Claim 7
Dependent Claim
16 words
A process as recited in claim 4 , wherein said statistical model comprises a Poisson model.
Claim 8
Dependent Claim
76 words
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 9
Dependent Claim
44 words
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 10
Dependent Claim
56 words
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 11
Dependent Claim
45 words
A process as recited in claim 1 , 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
Dependent Claim
45 words
A process as recited in claim 1 , 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
Dependent Claim
45 words
A process as recited in claim 1 , 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
Dependent Claim
36 words
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 15
Dependent Claim
86 words
A process as recited in claim 13 , 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 16
Dependent Claim
36 words
A process as recited in claim 14 , 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 17
Dependent Claim
41 words
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 18
Dependent Claim
29 words
A process as recited in claim 16 , wherein said signature for each given node comprises a plurality of features associated with the documents classified under the given node.
Claim 19
Dependent Claim
48 words
A process as recited in claim 16 , 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 20
Dependent Claim
298 words
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 c ∑ 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 c ∑ 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.
Claim 21
Dependent Claim
298 words
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 c ∑ 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 c ∑ 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.
Claim 22
Dependent Claim
72 words
A system as recited in claim 19 , 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 23
Dependent Claim
33 words
A system as recited in claim 20 , 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 24
Dependent Claim
49 words
A system as recited in claim 19 , 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 25
Dependent Claim
48 words
A system as recited in claim 19 , 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 26
Dependent Claim
47 words
A system as recited in claim 19 , 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 27
Dependent Claim
47 words
A system as recited in claim 19 , 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 28
Dependent Claim
316 words
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 c ∑ 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 c ∑ 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.
Claim 29
Dependent Claim
316 words
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 c ∑ 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 c ∑ 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.
Claim 30
Dependent Claim
68 words
An article as recited in claim 26 , 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 31
Dependent Claim
34 words
An article as recited in claim 27 , 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 32
Dependent Claim
47 words
An article as recited in claim 26 , 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 33
Dependent Claim
46 words
An article as recited in claim 26 , 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 34
Dependent Claim
45 words
An article as recited in claim 26 , 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 35
Dependent Claim
45 words
An article as recited in claim 26 , 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.
References Cited (Backward Citations)
US5168565A
Cited
US4975975A
Cited
US5469354A
Cited
US5519857A
Cited
US5535382A
Cited
US5317507A
Cited
US5325298A
Cited
US5557794A
Cited
US5418946A
Cited
US5428778A
Cited
US5659724A
Cited
US5838816A
Cited
US5600827A
Cited
US5506984A
Cited
US5568640A
Cited
US5576954A
Cited
US5625767A
Cited
EP0744702A1
Cited
US5675710A
Cited
US5918240A
Cited
US5826260A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-05-14 | 2004-11-13 | 2005-05-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-05-14 | 2008-11-13 | 2009-05-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-05-14 | 2012-11-13 | 2013-05-15 | $7700.00 | Window Closed / Lapsed |