Method of vector analysis for a document

• US 7,562,066 B2
• Filed: 11/15/2001
• Issued: 07/14/2009
• Est. Priority Date: 11/20/2000
• Status: Expired due to Fees

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Kawatani, Takahiko
• Primary Examiner(s): Breene; John E
• Assistant Examiner(s): MYINT, DENNIS Y
• Application Number:
  US10/380,264
• Publication Number:
  US 20040068396A1
• Time in Patent Office: 2,798 Days
• Field of Search: 704/1, 704/260, 707/5, 707/2, 707/3
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3347 using vector based model
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

The invention provides a document representation method and a document analysis method including extraction of important sentences from a given document and/or determination of similarity between two documents.

The inventive method detects terms that occur in the input document, segments the input document into document segments, each segment being an appropriately sized chunk and generates document segment vectors, each vector including as its element values according to occurrence frequencies of the terms occurring in the document segments. The method further calculates eigenvalues and eigenvectors of a square sum matrix in which a rank of the respective document segment vector is represented by R and selects from the eigenvectors a plural (L) of eigenvectors to be used for determining the importance. Then, the method calculates a weighted sum of the squared projections of the respective document segment vectors onto the respective selected eigenvectors and selects document segments having the significant importance based on the calculated weighted sum of the squared projections of the respective document segment vectors.

Claims

1. A computer-implemented method for extracting important document segments from an input document, comprising:

detecting k terms that occur in said input document;

segmenting said input document into N document segments, each segment being a predetermined part of said document;

generating document segment vectors, each vector including as its element values occurrence of frequencies of said terms occurring in said document segments, wherein a n-th document vector d_n (n=1, . . . , N) is represented by (d_n1, d_n2, . . . , d_nk) and d_ni represents the occurrence frequency of an i-th term among a total k terms in a n-th document segment;

determining eigenvalues and eigenvectors of a square sum matrix A, where said square sum matrix A is a k×

k matrix, k>

1, and each component A_ab of said square sum matrix A indicates a degree of co-occurrence of a-th and b-th terms (a,b=1, . . . , k) in said input document and is calculated by;

$A_{a<br><br><br><br>b}=\underset{n=1}{\overset{N}{\sum <br><br>}}<br><br>d_{n<br><br><br><br>a}<br><br>d_{n<br><br><br><br>b},$

and a rank of said square sum matrix is represented by R;

selecting, from said eigenvectors, a plural of (L) eigenvectors to be used for determining importance;

calculating a weighted sum of squared projections of said document segment vectors onto the selected eigenvectors; and

selecting documents having significant importance based on said calculated weighted sum of square projections of the document segment vectors;

wherein the vector d_n after the projection is represented by z_n=(z_n1, z_n2, . . . z_nL), a projection value of d_n to a m^-th eigenvector is given by z_nm=φ

_m^td_n, where φ

_m represents the m^-th eigenvector and t represents transpose;

a sum of squared projections onto a L dimensional subspace being given by;

Σ

_m^L=IZ_nm²

or

Σ

_m^L=Iλ

_m^znm²,

where λ

_m represents the eigenvalue of the m^-th eigenvector”

.

2. A method as claimed in claim 1, wherein a value of said L being determined based on a ratio of the central concept to an overall concept of said input document, which is given by:

$\underset{m=1}{\overset{L}{\sum <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}_m/\underset{m=1}{\overset{R}{\sum <br><br>}}<br><br>{\mathrm{\lambda <br><br>}}_m.$

3. A system for extracting sentences from a document, said system comprising a storage medium and a processor for executing the steps comprising:

detecting k terms that occur in said input document;

segmenting said input document into N document segments, each segment being a predetermined part of said document;

generating document segment vectors, each vector including as its element values occurrence of frequencies of said terms occurring in said document segments, wherein a n-th document vector d_n (n=1, . . . , N) is represented by (d_n1, d_n2, . . . , d_nk) and d _ni represents the occurrence frequency of an i-th term among a total k terms in a n-th document segment;

determining eigenvalues and eigenvectors of a square sum matrix A, where said square sum matrix A is a k×

k matrix, k>

1, and each component A_ab of said square sum matrix A indicates a degree of co-occurrence of a-th and b-th terms (a,b=1, . . . , k) in said input document and is calculated by;

$A_{a<br><br><br><br>b}=\underset{n=1}{\overset{N}{\sum <br><br>}}<br><br>d_{\mathrm{na}}<br><br>d_{\mathrm{nb}},$

and a rank of said square sum matrix is represented by R;

selecting, from said eigenvectors, a plural of (L) eigenvectors to be used for determining importance;

calculating a weighted sum of squared projections of said document segment vectors onto the selected eigenvectors; and

selecting documents having significant importance based on said calculated weighted sum of square projections of the document segment vectors;

wherein the vector d_n after the projection is represented by z_n=(z_n1, z_n2, . . . z_nL), a projection value of d_n to a m^-th eigenvector is given by z<sub>nm=φ

m</sub>^td_n, where 100 _m represents the m^-th eigenvector and t represents transpose;

a sum of squared projections onto a L dimensional subspace being given by;

Σ

_m^L=IZ_nm²

or

Σ

_m^L=Iλ

_m^znm²

where λ

_m represents the eigenvalue of the m^-th eigenvector.