Differential LSI space-based probabilistic document classifier

• US 7,024,400 B2
• Filed: 05/08/2001
• Issued: 04/04/2006
• Est. Priority Date: 05/08/2001
• Status: Expired due to Term

• Current Assignee: SunFlare Co., Ltd.
• Original Assignee: SunFlare Co., Ltd.
• Inventors: Sasai, Hiroyuki, Tokuda, Naoyuki, Chen, Liang
• Primary Examiner(s): DAVIS, GEORGE B
• Application Number:
  US09/849,984
• Publication Number:
  US 20030037073A1
• Time in Patent Office: 1,792 Days
• Field of Search: 706/56, 706/55, 706/20
• US Class Current: 706/56
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/353 into predefined classes
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars

Abstract

A computerized method for automatic document classification based on a combined use of the projection and the distance of the differential document vectors to the differential latent semantics index (DLSI) spaces. The method includes the setting up of a DLSI space-based classifier to be stored in computer storage and the use of such classifier by a computer to evaluate the possibility of a document belonging to a given cluster using a posteriori probability function and to classify the document in the cluster. The classifier is effective in operating on very large numbers of documents such as with document retrieval systems over a distributed computer network.

Claims

1. A method of setting up a DLSI space-based classifier to be stored in a computer storage device for document classification using a computer, and using said classifier by said computer to classify a document according to a plurality of clusters within a database, comprising the steps of:

preprocessing documents using said computer to distinguish terms of a word and a noun phrase from stop words;

constructing system terms by setting up a term list as well as global weights using said computer;

normalizing document vectors of collected documents, as well as centroid vectors of each cluster using said computer;

constructing a differential term by intra-document matrix D_I<sup>m×

nI</sup> using said computer, such that each column in said matrix is a differential intra-document vector;

decomposing the differential term by intra-document matrix D_I, by an SVD algorithm using said computer, into D_I=U_IS_IV_I^T(S_I=diag(δ

_I,1,δ

_I,2, . . . )), followed by a composition of D_I,kI=U_kIS_kIV_kI^T giving an approximate D_I in terms of an appropriate k_I;

setting up a likelihood function of intra-differential document vector using said computer;

constructing a term by extra-document matrix D_E<sup>m×

nE</sup> using said computer, such that each column of said extra-document matrix is an extra-differential document vector;

decomposing D_E, by exploiting the SVD algorithm using said computer, into D_E=U_ES_EV_E^T(S_E=diag(δ

_E,1,δ

_E,2, . . . )), then with a proper k_E, defining D_E,kE=U_kES_kEV_kE^T to approximate D_E;

setting up a likelihood function of extra-differential document vector using said computer;

setting up a posteriori function using said computer; and

said computer using said DLSI space-based classifier, as set up in the foregoing steps, to classify the document as belonging to one of the plurality of clusters within the database.

2. An automatic document classification method using a DLSI space-based classifier operating on a computer as a computerized classifier to classify a document in accordance with clusters in a database, comprising the steps of:

a) setting up, by said computerized classifier, a document vector by generating terms as well as frequencies of occurrence of said terms in the document, so that a normalized document vector N is obtained for the document;

b) constructing, by said computerized classifier, using the document to be classified, a differential document vector x=N−

C, where C is the normalized vector giving a center or centroid of a cluster;

c) calculating an intra-document likelihood function P(x|D_I) for the document using said computerized classifier;

d) calculating an extra-document likelihood function P(x|D_E) for the document using said computerized classifier;

e) calculating a Bayesian posteriori probability function using said computerized classifier P(D_I|x);

f) repeating, for each of the clusters of the data base, steps b–

e;

g) selecting, by said computerized classifier, a cluster having a largest P(D_I|x) as the cluster to which the document most likely belongs; and

h) classifying, by said computerized classifier, the document in the selected cluster within said database thereby categorizing said document for an automated document retrieval system.

3. The method as set forth in claim 2, wherein the normalized document vector N is obtained using an equation, $b_{\mathrm{ij}}=a_{\mathrm{ij}}/\sqrt{\sum _{}^{}}$

k=1m⁢

akj2.

4. A method of setting up a DLSI space-based classifier to be stored in a computer storage device for document classification using a computer, and using said classifier by said computer to classify a document according to a plurality of clusters within a database, comprising the steps of:

setting up, using said computer, a differential term by intra-document matrix where each column of the matrix denotes a difference between a document and a centroid of a cluster to which the document belongs;

decomposing, using said computer, the differential term by intra-document matrix by an SVD algorithm to identify an intra-DLSI space;

setting up, using said computer, a probability function for a differential document vector being a differential intra-document vector;

calculating, using said computer, the probability function according to projection and distance from the differential document vector to the intra-DLSI space;

setting up, using said computer, a differential term by extra-document matrix where each column of the matrix denotes a differential document vector between a document vector and a centroid vector of a cluster which does not include the document;

decomposing, using said computer, the differential term by extra-document matrix by an SVD algorithm to identify an extra-DLSI space;

setting up, using said computer, a probability function for a differential document vector being a differential extra-document vector;

setting up, using said computer, a posteriori likelihood function using the differential intra-document and differential extra-document vectors to provide a most probable similarity measure of a document belonging to a given cluster; and

said computer using said DLSI space-based classifier, as set up in the foregoing steps, to classify the document as belonging to one of the plurality of clusters within the database.

5. The method as set forth in claim 4, wherein the step of setting up a probability function for a differential document vector being a differential intra-document vector is performed using an equation, $P$

(x|DI)=nI1/2⁢

exp⁡

(-nI2⁢

∑

i=1kI⁢

yi2δ

I,i2)·

exp⁡

(-nI⁢

ɛ

2⁡

(x)2⁢

ρ

I)(2⁢

π

)nI/2⁢

∏

i=1kI⁢

δ

I,i·

ρ

(rI-kI)/2,⁢

w⁢

⁢

h⁢

⁢

e⁢

⁢

r⁢

⁢

e⁢

⁢

y=UkIT⁢

x,ɛ

2⁡

(x)=

x

2-∑

i=1kI⁢

yi2,ρ

I=1rI-kI⁢

∑

i=kI+1rI⁢

δ

I,i2,⁢

and⁢

⁢

rI⁢

⁢

is⁢

⁢

the⁢

⁢

rank⁢

⁢

of⁢

⁢

matrix⁢

⁢

DI.

6. The method as set forth in claim 4, wherein the step of setting up a probability function for a differential document vector being a differential extra-document vector is performed using an equation, $P$

(x|DE)=nE1/2⁢

exp⁡

(-nE2⁢

∑

i=1kE⁢

yi2δ

E,i2)·

exp⁡

(-nE⁢

ɛ

2⁡

(x)2⁢

ρ

E)(2⁢

π

)nE/2⁢

∏

i=1kE⁢

δ

E,i·

ρ

E(rE-kE)/2,⁢

w⁢

⁢

h⁢

⁢

e⁢

⁢

r⁢

⁢

e⁢

⁢

y=UkET⁢

x,ɛ

2⁡

(x)=

x

2-∑

i=1kE⁢

yi2,ρ

E=1rE-kE⁢

∑

i=kE+1rE⁢

δ

E,i2,⁢

rE⁢

⁢

is⁢

⁢

the⁢

⁢

rank⁢

⁢

of⁢

⁢

matrix⁢

⁢

DE.

7. The method as set forth in claim 4, wherein the step of setting up a posteriori likelihood function is performed using an equation, $P$

(DI|x)=P⁢

(x|DI)⁢

P⁢

(DI)P⁢

(x|DI)⁢

P⁢

(DI)+P⁢

(x|DE)⁢

P⁢

(DE),

where P(D_I) is set to 1/n_c where n_c is the number of clusters in the database and P(D_E) is set to 1P(D_I).

8. The method as set forth in claim 4, the step of said computer using the DLSI space-based classifier to classify the document comprising the steps of:

a) setting up a document vector by generating terms as well as frequencies of occurrence of said terms in the document, so that a normalized document vector N is obtained for the document;

b) constructing, using the document to be classified, a differential document vector x=N−

C, where C is the normalized vector giving a center or centroid of a cluster;

c) calculating an intra-document likelihood function P(x|D_I) for the document;

d) calculating an extra-document likelihood function P(x|D_E) for the document;

e) calculating a Bayesian posteriori probability function P(D_I|x);

f) repeating, for each of the clusters of the data base, steps b–

e;

g) selecting a cluster having a largest P(D_I|x) as the cluster to which the document most likely belongs; and

h) classifying the document in the selected cluster.

9. The method as set forth in claim 8, wherein the normalized document vector N is obtained using an equation, $b_{\mathrm{ij}}=a_{\mathrm{ij}}/\sqrt{\sum _{}^{}}$

k=1m⁢

akj2.