US6606620B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for classifying semi-structured documents
Assignee: Google LLC
•
Filing: 2000-07-24
•
Granted: 2003-08-12
•
Expires: 2020-07-24
Abstract
Abstract A classifier for semi-structured documents and associated method dynamically and accurately classify documents with an implicit or explicit schema by taking advantage of the term-frequency and term distribution information inherent in the document. The system uses a structured vector model that allows like terms to be grouped together and dissimilar terms to be segregated based on their frequency and distribution within the sub-vectors of the structure vector, thus achieving context sensitivity. The final decision for assigning the class of a document is based on a mathematical comparison of the similarity of the terms in the structured vector to those of the various class models. The classifier of the present invention is capable of both learning and testing. In the learning phase the classifier develops models for classes with information it develops from the composite information gleaned from numerous training documents. Specifically, it develops a structured vector model for each training document. Then, within a given class of documents it adds and then normalizes the occurrences of terms.
Inventors
- 👤 Neelakantan Sundaresan
- 👤 Jeonghee Yi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 17:00
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99941; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
519 words
A classifier, for use on a computer readable medium, for dynamically classifying a semi-structured document with a schema, comprising: a vectorization module for parsing the document into a structured vector model, wherein the structured vector model is divided into a tree of sub-vectors to reflect a plurality of hierarchical levels beginning with a root and ending with a plurality of leaves; a sorting module for searching the, document and for counting the occurrences of individual terms in the document; the sorting module further accounting for the frequency of occurrence of the terms at each hierarchical level to achieve a high contextual sensitivity; a testing module for assigning a class to the document by using a statistical model based on probability calculation to create a classification model; and wherein the classification model assigns a class to the document that maximizes a posteriori class probability Pr[c|d,F k ] according to the following expression: Pr [ c d , F k ] = π ( c ) ∏ t ε p d ( i , j ) , t ε d ⋂ F k ( e d ( i , j ) ) f ( c , p d ( i , j ) , t ) n ( d , p d ( i , j ) , t ) ∑ c ′ π ( c ′ ) ∏ t ε p d ( i · ) , t ε d ⋂ F k ( e d ( i , j ) ) f ( c , p d ( i , j ) , t ) n ( d , p d ( i , j ) , t ) where d is the document, p(c) is a prior distribution on the class c; c′ is a class in a set of documents; p d is a path to a structure node e d from a root; n is a number of occurrences of term t in p d , f is a maximum likelihood estimation; F k is a set of selected terms; F is a Fisher index defined by the following equation, where c 1 and c 2 are children of an internal class c 0 , and m is an average number of an occurrence of term t in class c: F ( t ) = ∑ ( μ ( c 1 , t ) - μ ( c 2 , t ) ) 2 c 1 , c 2 ∑ c 1 c ∑ ( f ( t , d , c ) - μ ( c , t ) ) 2 d ε c .
Claim 2
Dependent Claim
519 words
A classifier, for use on a computer readable medium, for dynamically classifying a semi-structured document with a schema, comprising: a vectorization module for parsing the document into a structured vector model, wherein the structured vector model is divided into a tree of sub-vectors to reflect a plurality of hierarchical levels beginning with a root and ending with a plurality of leaves; a sorting module for searching the, document and for counting the occurrences of individual terms in the document; the sorting module further accounting for the frequency of occurrence of the terms at each hierarchical level to achieve a high contextual sensitivity; a testing module for assigning a class to the document by using a statistical model based on probability calculation to create a classification model; and wherein the classification model assigns a class to the document that maximizes a posteriori class probability Pr[c|d,F k ] according to the following expression: Pr [ c d , F k ] = π ( c ) ∏ t ε p d ( i , j ) , t ε d ⋂ F k ( e d ( i , j ) ) f ( c , p d ( i , j ) , t ) n ( d , p d ( i , j ) , t ) ∑ c ′ π ( c ′ ) ∏ t ε p d ( i · ) , t ε d ⋂ F k ( e d ( i , j ) ) f ( c , p d ( i , j ) , t ) n ( d , p d ( i , j ) , t ) where d is the document, p(c) is a prior distribution on the class c; c′ is a class in a set of documents; p d is a path to a structure node e d from a root; n is a number of occurrences of term t in p d , f is a maximum likelihood estimation; F k is a set of selected terms; F is a Fisher index defined by the following equation, where c 1 and c 2 are children of an internal class c 0 , and m is an average number of an occurrence of term t in class c: F ( t ) = ∑ ( μ ( c 1 , t ) - μ ( c 2 , t ) ) 2 c 1 , c 2 ∑ c 1 c ∑ ( f ( t , d , c ) - μ ( c , t ) ) 2 d ε c .
Claim 3
Dependent Claim
23 words
The classifier according to claim 1 , wherein the sorting module stores the frequency of occurrence of the terms in separate histogram bins.
Claim 4
Dependent Claim
22 words
The classifier according to claim 1 , further including a modeling module that uses a statistical model to create a classification model.
Claim 5
Dependent Claim
28 words
The classifier according to claim 3 , wherein the testing module uses the classification model created by the modeling module to assign the class based on probability calculation.
Claim 6
Dependent Claim
23 words
The classifier according to claim 3 , wherein the modeling module normalizes the frequency of occurrence of the terms at each hierarchical level.
Claim 7
Dependent Claim
14 words
The classifier according to claim 1 , wherein the document is an XML document.
Claim 8
Dependent Claim
26 words
The classifier according to claim 1 , further including a training module for classifying documents with known class labels and for developing structured vector models therefrom.
Claim 9
Dependent Claim
30 words
The classifier according to claim 7 , wherein the testing module classifies documents with unknown class labels, based on the class label structured vector models developed by the training module.
Claim 10
Dependent Claim
29 words
The classifier according to claim 1 , wherein the structured vector model uses structured information embedded in the document schema and text content to develop the structured vector model.
Claim 11
Dependent Claim
13 words
The classifier according to claim 1 , wherein the leaves include textual terms.
Claim 12
Dependent Claim
15 words
The classifier according to claim 10 , wherein the leaves consist exclusively of textual terms.
Claim 13
Dependent Claim
514 words
A software program product for dynamically classifying a semi-structured document with a schema, comprising: a vectorization module for parsing the document into a structured vector model, wherein the structured vector model is divided into a tree of sub-vectors to reflect a plurality of hierarchical levels beginning with a root and ending with a plurality of leaves; a sorting module for searching the document and for counting the occurrences of individual terms in the document; the sorting module further accounting for the frequency of occurrence of the terms at each hierarchical level to achieve a high contextual sensitivity; a testing module for assigning a class to the document by using a statistical model based on probability calculation to create a classification model; and wherein the classification model assigns a class to the document that maximizes a posteriori class probability Pr[c|d,F k ] according to the following expression: Pr [ c d , F k ] = π ( c ) ∏ t ε p d ( i , j ) , t ε d ⋂ F k ( e d ( i , j ) ) f ( c , p d ( i , j ) , t ) n ( d , p d ( i , j ) , t ) ∑ c ′ π ( c ′ ) ∏ t ε p d ( i · ) , t ε d ⋂ F k ( e d ( i , j ) ) f ( c , p d ( i , j ) , t ) n ( d , p d ( i , j ) , t ) where d is the document, p(c) is a prior distribution on the class c; c′ is a class in a set of documents; p d is a path to a structure node e d from a root; n is a number of occurrences of term t in p d , f is a maximum likelihood estimation; F k is a set of selected terms; F is a Fisher index defined by the following equation, where c 1 and c 2 are children of an internal class c 0 , and m is an average number of an occurrence of term t in class c: F ( t ) = ∑ ( μ ( c 1 , t ) - μ ( c 2 , t ) ) 2 c 1 , c 2 ∑ c 1 c ∑ ( f ( t , d , c ) - μ ( c , t ) ) 2 d ε c .
Claim 14
Dependent Claim
514 words
A software program product for dynamically classifying a semi-structured document with a schema, comprising: a vectorization module for parsing the document into a structured vector model, wherein the structured vector model is divided into a tree of sub-vectors to reflect a plurality of hierarchical levels beginning with a root and ending with a plurality of leaves; a sorting module for searching the document and for counting the occurrences of individual terms in the document; the sorting module further accounting for the frequency of occurrence of the terms at each hierarchical level to achieve a high contextual sensitivity; a testing module for assigning a class to the document by using a statistical model based on probability calculation to create a classification model; and wherein the classification model assigns a class to the document that maximizes a posteriori class probability Pr[c|d,F k ] according to the following expression: Pr [ c d , F k ] = π ( c ) ∏ t ε p d ( i , j ) , t ε d ⋂ F k ( e d ( i , j ) ) f ( c , p d ( i , j ) , t ) n ( d , p d ( i , j ) , t ) ∑ c ′ π ( c ′ ) ∏ t ε p d ( i · ) , t ε d ⋂ F k ( e d ( i , j ) ) f ( c , p d ( i , j ) , t ) n ( d , p d ( i , j ) , t ) where d is the document, p(c) is a prior distribution on the class c; c′ is a class in a set of documents; p d is a path to a structure node e d from a root; n is a number of occurrences of term t in p d , f is a maximum likelihood estimation; F k is a set of selected terms; F is a Fisher index defined by the following equation, where c 1 and c 2 are children of an internal class c 0 , and m is an average number of an occurrence of term t in class c: F ( t ) = ∑ ( μ ( c 1 , t ) - μ ( c 2 , t ) ) 2 c 1 , c 2 ∑ c 1 c ∑ ( f ( t , d , c ) - μ ( c , t ) ) 2 d ε c .
Claim 15
Dependent Claim
25 words
The software program product according to claim 12 , wherein the sorting module stores the frequency of occurrence of the terms in separate histogram bins.
Claim 16
Dependent Claim
24 words
The software program product according to claim 12 , further including a modeling module that uses a statistical model to create a classification model.
Claim 17
Dependent Claim
30 words
The software program product according to claim 14 , wherein the testing module uses the classification model created by the modeling module to assign the class based on probability calculation.
Claim 18
Dependent Claim
25 words
The software program product according to claim 14 , wherein the modeling module normalizes the frequency of occurrence of the terms at each hierarchical level.
Claim 19
Dependent Claim
16 words
The software program product according to claim 12 , wherein the document is an XML document.
Claim 20
Dependent Claim
28 words
The software program product according to claim 12 , further including a training module for classifying documents with known class labels and for developing structured vector models therefrom.
Claim 21
Dependent Claim
32 words
The software program product according to claim 18 , wherein the testing module classifies documents with unknown class labels, based on the class label structured vector models developed by the training module.
Claim 22
Dependent Claim
31 words
The software program product according to claim 12 , wherein the structured vector model uses structured information embedded in the document schema and text content to develop the structured vector model.
Claim 23
Independent Claim
491 words
A method for dynamically classifying a semi-structured document, comprising: parsing the document into a structured vector model; dividing the structured vector model into a tree of sub-vectors to reflect a plurality of hierarchical levels beginning with a root and ending with a plurality of leaves; searching the document and counting the occurrences of individual terms in the document; accounting for the frequency of occurrence of the terms at each hierarchical level to achieve a high contextual sensitivity; assigning a class to the document by using a statistical model based on probability calculation to create a classification model; and wherein the classification model assigns a class to the document that maximizes a posteriori class probability Pr[c|d,F k ] according to the following expression: Pr [ c d , F k ] = π ( c ) ∏ t ε p d ( i , j ) , t ε d ⋂ F k ( e d ( i , j ) ) f ( c , p d ( i , j ) , t ) n ( d , p d ( i , j ) , t ) ∑ c ′ π ( c ′ ) ∏ t ε p d ( i · ) , t ε d ⋂ F k ( e d ( i , j ) ) f ( c ′ , p d ( i , j ) , t ) n ( d , p d ( i , j ) , t ) where d is the document, p(c) is a prior distribution on the class c; c′ is a class in a set of documents; p d is a path to a structure node e d from a root; n is a number of occurrences of term t in p d , f is a maximum likelihood estimation; F k is a set of selected terms; F is a Fisher index defined by the following equation, where c 1 and c 2 are children of an internal class c 0 , and m is an average number of an occurrence of term t in class c: F ( t ) = ∑ ( μ ( c 1 , t ) - μ ( c 2 , t ) ) 2 c 1 , c 2 ∑ c 1 c ∑ ( f ( t , d , c ) - μ ( c , t ) ) 2 d ε c .
Claim 24
Independent Claim
491 words
A method for dynamically classifying a semi-structured document, comprising: parsing the document into a structured vector model; dividing the structured vector model into a tree of sub-vectors to reflect a plurality of hierarchical levels beginning with a root and ending with a plurality of leaves; searching the document and counting the occurrences of individual terms in the document; accounting for the frequency of occurrence of the terms at each hierarchical level to achieve a high contextual sensitivity; assigning a class to the document by using a statistical model based on probability calculation to create a classification model; and wherein the classification model assigns a class to the document that maximizes a posteriori class probability Pr[c|d,F k ] according to the following expression: Pr [ c d , F k ] = π ( c ) ∏ t ε p d ( i , j ) , t ε d ⋂ F k ( e d ( i , j ) ) f ( c , p d ( i , j ) , t ) n ( d , p d ( i , j ) , t ) ∑ c ′ π ( c ′ ) ∏ t ε p d ( i · ) , t ε d ⋂ F k ( e d ( i , j ) ) f ( c ′ , p d ( i , j ) , t ) n ( d , p d ( i , j ) , t ) where d is the document, p(c) is a prior distribution on the class c; c′ is a class in a set of documents; p d is a path to a structure node e d from a root; n is a number of occurrences of term t in p d , f is a maximum likelihood estimation; F k is a set of selected terms; F is a Fisher index defined by the following equation, where c 1 and c 2 are children of an internal class c 0 , and m is an average number of an occurrence of term t in class c: F ( t ) = ∑ ( μ ( c 1 , t ) - μ ( c 2 , t ) ) 2 c 1 , c 2 ∑ c 1 c ∑ ( f ( t , d , c ) - μ ( c , t ) ) 2 d ε c .
Claim 25
Dependent Claim
24 words
The method according to claim 21 , wherein counting the occurrences includes storing the frequency of occurrence of the terms in separate histogram bins.
Claim 26
Dependent Claim
30 words
The method according to claim 21 , wherein accounting for the frequency of occurrence of the terms includes storing the frequency of occurrence of the terms in separate histogram bins.
Claim 27
Dependent Claim
21 words
The method according to claim 21 , further including normalizing the frequency of occurrence of the terms at each hierarchical level.
Claim 28
Independent Claim
515 words
A method for dynamically classifying a semi-structured document, comprising: parsing the document into a structured vector; organizing the structured vector into a tree comprised of any of sub-vectors or structured vectors, to reflect a plurality of hierarchical levels in the document, beginning with a root and ending with a plurality of leaves; searching the document and counting the occurrences of individual terms in the document; accounting for the frequency of occurrence of the terms at each hierarchical level to achieve a high contextual sensitivity; assigning a class to the document based on both term frequency and term distribution information and structure within the structured vector of the document, by using a statistical model based on probability calculation to create a classification model; and wherein the classification model assigns a class to the document that maximizes a posteriori class probability Pr[c|d,F k ] according to the following expression: Pr [ c d , F k ] = π ( c ) ∏ t ε p d ( i , j ) , t ε d ⋂ F k ( e d ( i , j ) ) f ( c , p d ( i , j ) , t ) n ( d , p d ( i , j ) , t ) ∑ c ′ π ( c ′ ) ∏ t ε p d ( i · ) , t ε d ⋂ F k ( e d ( i , j ) ) f ( c , p d ( i , j ) , t ) n ( d , p d ( i , j ) , t ) where d is the document, p(c) is a prior distribution on the class c; c′ is a class in a set of documents; p d is a path to a structure node e d from a root; n is a number of occurrences of term t in p d , f is a maximum likelihood estimation; F k is a set of selected terms; F is a Fisher index defined by the following equation, where c 1 and c 2 are children of an internal class c 0 , and m is an average number of an occurrence of term t in class c: F ( t ) = ∑ ( μ ( c 1 , t ) - μ ( c 2 , t ) ) 2 c 1 , c 2 ∑ c 1 c ∑ ( f ( t , d , c ) - μ ( c , t ) ) 2 d ε c .
Claim 29
Independent Claim
515 words
A method for dynamically classifying a semi-structured document, comprising: parsing the document into a structured vector; organizing the structured vector into a tree comprised of any of sub-vectors or structured vectors, to reflect a plurality of hierarchical levels in the document, beginning with a root and ending with a plurality of leaves; searching the document and counting the occurrences of individual terms in the document; accounting for the frequency of occurrence of the terms at each hierarchical level to achieve a high contextual sensitivity; assigning a class to the document based on both term frequency and term distribution information and structure within the structured vector of the document, by using a statistical model based on probability calculation to create a classification model; and wherein the classification model assigns a class to the document that maximizes a posteriori class probability Pr[c|d,F k ] according to the following expression: Pr [ c d , F k ] = π ( c ) ∏ t ε p d ( i , j ) , t ε d ⋂ F k ( e d ( i , j ) ) f ( c , p d ( i , j ) , t ) n ( d , p d ( i , j ) , t ) ∑ c ′ π ( c ′ ) ∏ t ε p d ( i · ) , t ε d ⋂ F k ( e d ( i , j ) ) f ( c , p d ( i , j ) , t ) n ( d , p d ( i , j ) , t ) where d is the document, p(c) is a prior distribution on the class c; c′ is a class in a set of documents; p d is a path to a structure node e d from a root; n is a number of occurrences of term t in p d , f is a maximum likelihood estimation; F k is a set of selected terms; F is a Fisher index defined by the following equation, where c 1 and c 2 are children of an internal class c 0 , and m is an average number of an occurrence of term t in class c: F ( t ) = ∑ ( μ ( c 1 , t ) - μ ( c 2 , t ) ) 2 c 1 , c 2 ∑ c 1 c ∑ ( f ( t , d , c ) - μ ( c , t ) ) 2 d ε c .
Claim 30
Dependent Claim
13 words
The method according to claim 25 , wherein the leaves include textual terms.
References Cited (Backward Citations)
US5546474A
Cited
US5832480A
Cited
US6072809A
Cited
US5974412A
Cited
US6389436B1
Cited
US6212532B1
Cited
US6385619B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-08-11 | 2007-02-10 | 2007-08-12 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-08-11 | 2011-02-10 | 2011-08-12 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-08-11 | 2015-02-10 | 2015-08-12 | $7700.00 | Window Closed / Lapsed |