Computer method and apparatus for clustering documents and automatic generation of cluster keywords

• US 5,857,179 A
• Filed: 09/09/1996
• Issued: 01/05/1999
• Est. Priority Date: 09/09/1996
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Vaithyanathan, Shivakumar, Adler, Mark R., Hill, Christopher G.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Ho, Buay Lian
• Application Number:
  US08/709,755
• Time in Patent Office: 848 Days
• Field of Search: 395/601, 395/602, 395/603, 395/604, 395/605, 395/611, 395/616, 395/11, 395/13, 395/50, 395/751, 395/752, 395/758, 395/759, 395/760, 395/761, 395/779, 395/788, 395/792, 395/79 4
• US Class Current: 1/1
• CPC Class Codes: G06F 16/345 Summarisation for human users
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing

Abstract

A computer method and apparatus determines keywords of documents. An initial document by term matrix is formed, each document being represented by a respective M dimensional vector, where M represents the number of terms or words in a predetermined domain of documents. The dimensionality of the initial matrix is reduced to form resultant vectors of the documents. The resultant vectors are then clustered such that correlated documents are grouped into respective clusters. For each cluster, the terms having greatest impact on the documents in that cluster are identified. The identified terms represent key words of each document in that cluster. Further, the identified terms form a cluster summary indicative of the documents in that cluster.

Claims

1. A computer method for clustering documents comprising the steps of:

in a digital processor, representing each document by a respective M dimensional vector in a matrix, where M equals a number of words in a predefined domain of document terms, such that an initial matrix of documents is formed;

reducing dimensionality of the initial matrix to form resultant vectors of the documents; and

clustering the resultant vectors such that different respective documents are grouped into a plurality of clusters.

2. A method as claimed in claim 1 further comprising the step of identifying words having greatest impact on documents in each cluster, said identified words representing keywords for each cluster.

3. A method as claimed in claim 2 wherein the step of representing each document includes forming a term by document matrix for the initial matrix and wherein the loading vectors comprise a left matrix obtained by the step of applying singular value decomposition.

4. A method as claimed in claim 2 wherein the step of identifying words includes:

for each resultant vector, representing each component part of the resultant vector as a sum of products, each product being indicative of weight of a respective word;

identifying certain products as being substantially larger than other products; and

selecting respective words of said certain products as being words having greatest impact on the document represented by that resultant vector.

5. A method as claimed in claim 4 further comprising the step of:

in each resultant vector of a given cluster, for each component part, normalizing the products with respect to the largest product in that component part.

6. A method as claimed in claim 1 wherein the step of reducing dimensionality includes:

applying singular value decomposition to the initial matrix to obtain loading vectors; and

forming a reduced matrix obtained by projecting the initial matrix onto the loading vectors to obtain a matrix of reduced dimensionality.

7. A method as claimed in claim 6 wherein the loading vectors are selected from a set of Eigenvectors consisting of:

Eigenvectors of a sum squared of products matrix of the initial matrix;

Eigenvectors of a covariance matrix of the initial matrix; and

Eigenvectors of a correlation matrix of the initial matrix.

8. A method as claimed in claim 6 wherein the step of representing each document includes forming a document by term matrix for the initial matrix and wherein the loading vectors comprise a right matrix obtained by the step of applying singular value decomposition.

9. A method as claimed in claim 1 wherein the step of clustering includes performing K-means clustering on the resultant vectors.

10. A method as claimed in claim 1 further comprising the step of forming a cluster summary from the identified words for a cluster;

and

in response to a keyword query for document retrieval;

comparing keywords of the query to the cluster summaries; and

returning document clusters, including cluster summaries, based on said comparison.

20. The apparatus of claim 10 further comprising a summarizer for forming a cluster summary from the identified words for a cluster and means for responding to a key word query for document retrieval by comparing key words of the query to the cluster summaries, and returning document clusters, including cluster summaries based on the comparison.

11. A computer apparatus for clustering documents comprising:

a memory for storing documents, each one of said documents represented by a respective M dimensional vector in a matrix where M equals a number of words in a predefined domain of document terms such that an initial matrix of documents is stored;

a dimensionality reducer for reducing the dimensionality of the initial matrix to form resultant vectors of the documents, the reducer executed on a processor coupled to the memory;

a clusterer coupled to the reducer for receiving and clustering the resultant vectors such that different respective documents are grouped into different clusters.

12. The apparatus of claim 11 further comprising an identifier for identifying words having greatest impact on the documents in each cluster, said identified words representing key words in each cluster.

13. The apparatus of claim 12, wherein the identifier comprises:

means for representing each component part of the resultant vector as a sum of products, each product being indicative of weight of a respective word;

means for comparing the magnitude of relative products and identifying certain products as being substantially larger than other products; and

selecting means for selecting respective words of said certain products as being words having greatest impact on the document represented by that resultant vector.

14. The apparatus of claim 13 further comprising:

normalization means for normalizing the products with respect to the largest product in that component part.

15. The apparatus of claim 11, wherein the dimensionality reducer comprises a decomposer for applying singular value decomposition to the initial matrix to obtain loading vectors;

and a projector for forming a reduced matrix obtained by projecting the initial matrix onto the loading vectors to obtain a matrix of reduced dimensionality.

16. The apparatus of claim 15, wherein the loading vectors are selected from Eigenvectors consisting of:

Eigenvectors of the sum squared of products matrix;

Eigenvectors of the covariance matrix; and

Eigenvectors of the correlation matrix of the initial matrix.

17. The apparatus of claim 15, wherein the initial matrix is a document by term matrix and wherein the loading vectors comprise a right matrix obtained by singular value decomposition.

18. The apparatus of claim 11, wherein the initial matrix is a term by document matrix and wherein the loading vectors comprise a left matrix obtained by the decomposer.

19. The apparatus of claim 11, wherein the clusterer performs K-means clustering on the resultant vectors.