New differential LSI space-based probabilistic document classifier

• US 20030037073A1
• Filed: 05/08/2001
• Published: 02/20/2003
• Est. Priority Date: 05/08/2001
• Status: Active Grant

• Current Assignee: SunFlare Co., Ltd.
• Original Assignee: SunFlare Co., Ltd.
• Inventors: Sasai, Hiroyuki, Chen, Liang, Tokuda, Naoyuki
• Granted Patent: US 7,024,400 B2
• Time in Patent Office: Days
• US Class Current: 715/500
• 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 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 and the use of such classifier to evaluate the possibility of a document belonging to a given cluster using a posteriori probability function.

Claims

1. A method of setting up a DLSI space-based classifier for document classification comprising the steps of:

preprocessing documents 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;

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

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

n_I</sup>, 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, 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;

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

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

decomposing D_E, by exploiting the SVD algorithm, 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;

setting up a posteriori function; and

using the DLSI space-based classifier to automatically classify a document.

2. An automatic document classification method using a DLSI space-based classifier for classifying a document in accordance with clusters in a database, 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.

3. The method as set forth in claim 2, wherein the normalized document vector N is obtained using an equation,

4. A method of setting up a DLSI space-based classifier for document classification, comprising the steps of:

setting up 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 the differential term by intra-document matrix by an SVD algorithm to identify an intra-DLSI space;

setting up a probability function for a differential document vector being a differential intra-document vector;

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

setting up 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 the differential term by extra-document matrix by an SVD algorithm to identify an extra-DLSI space;

setting up a probability function for a differential document vector being a differential extra-document vector;

setting up 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 cluster; and

using the DLSI space-based classifier to automatically classify a document.

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,

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,

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

8. The method as set forth in claim 4, the step of using the DLSI space-based classifier to automatically classify a 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,