TECHNIQUES FOR COMPARING AND CLUSTERING DOCUMENTS

• US 20130013612A1
• Filed: 07/07/2011
• Published: 01/10/2013
• Est. Priority Date: 07/07/2011
• Status: Active Grant

• Current Assignee: Software AG
• Original Assignee: Software AG
• Inventors: FITTGES, Klaus, El Mansouri, Khalid
• Granted Patent: US 8,983,963 B2
• Time in Patent Office: Days
• US Class Current: 707/739
• CPC Class Codes: G06F 16/1774 Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files
• CPC Class Codes: G06F 16/353 into predefined classes

Abstract

Certain example embodiments relate to techniques for analyzing documents. A plurality of documents/document portions are imported into a database, with at least some of the documents/document portions being structured and at least some being unstructured. The imported documents/document portions are organized into one or more collections. A selection of at least one of the one or more collections is made. An index of words and/or groups of words is built (and optionally refined in accordance with one or more predefined rules) based on each of the document or document portion in each selection. A document-word matrix is built (and optionally weighted using a semantic approach), with the matrix including a value indicative of a number of times each word and/or group of words in the index appears in each document/document portion. One or more clusters of documents are generated using the document-word matrix.

Claims

1. A method for analyzing documents, the method comprising:

importing into a database a plurality of documents and/or document portions, at least some of the documents and/or document portions being structured and at least some of the documents and/or document portions being unstructured;

organizing the imported documents and/or document portions into one or more collections;

receiving a selection of at least one of said one or more collections;

building an index of words and/or groups of words based on each said document or document portion in each said selection;

building a document-word matrix including a value indicative of a number of times each said word and/or group of words in the index of words and/or groups of words appears in each said document or document portion in each said selection; and

generating, via at least one processor, one or more clusters of documents using the document-word matrix.

2. The method of claim 1, further comprising:

building a weighted document-word matrix including a weighted value indicative of a number of times each said word in the index of words appears in each said document or document portion in each said selection, the weighting being performed in accordance with a semantics-based algorithm,

wherein the one or more clusters of documents are generated using the weighted document-word matrix.

3. The method of claim 2, wherein the semantics-based algorithm involves Latent Semantic Indexing (LSI).

4. The method of claim 1, further comprising refining (a) the index of words and/or groups of words prior to the building of the document-word matrix and/or (b) document-word matrix, the refining being performed in accordance with one or more predefined rules.

5. The method of claim 4, wherein the one or more predefined rules include rules defining semantic and/or non-semantic stopwords and specifying how the defined semantic and/or non-semantic stopwords are to be handled.

6. The method of claim 4, wherein the one or more predefined rules include rules for standardizing transliterations or suspected transliterations.

7. The method of claim 4, wherein the one or more predefined rules include rules for applying a stemming algorithm to reduce the size of the index of words and/or groups of words prior to the building of the document-word matrix and/or the document-word matrix.

8. The method of claim 4, wherein a plurality of predefined rules are provided, the rules including rules (i) defining semantic and/or non-semantic stopwords and specifying how the defined semantic and/or non-semantic stopwords are to be handled, (ii) for standardizing transliterations or suspected transliterations, and (iii) for applying a stemming algorithm to reduce the size of the index of words and/or groups of words prior to the building of the document-word matrix and/or the document-word matrix.

9. The method of claim 4, wherein an index is built for words and for groups of words.

10. The method of claim 9, wherein the groups of words include a given word and one word immediately to the left of the given word.

11. The method of claim 1, further comprising removing linkages between documents in a given cluster when threshold values indicative of degrees of similarity between two documents are not met.

12. The method of claim 11, wherein the clustering is based on a cosine similarity calculation.

13. The method of claim 12, wherein the threshold value is 80%.

14. The method of claim 12, wherein the threshold is user-adjustable.

15. The method of claim 12, further comprising ordering documents in the given cluster based on respective degrees of similarity.

19. A non-transitory computer readable storage medium storing instructions, that when executed by at least one processor of a computer system, perform a method according to claim 1.

16. A method for analyzing documents, the method comprising:

organizing a plurality of assets including structured and unstructured documents and/or document portions into a plurality of user-defined collections;

enabling a user to select one or more of said user-defined collections for subsequent analysis;

building an index of words and/or groups of words based on the documents and document portions in each said selected collection;

building a document-word matrix including a value indicative of a number of times each said word and/or group of words in the index of words and/or groups of words appears in each said document or document portion in each said selection;

refining the index of words and/or groups of words, and/or the document-word matrix based on predefined rules stored in a database of rules;

weighting entries in the document-word matrix based on a semantic indexing approach; and

clustering together, via at least one processor, documents in dependence on the weighted entries.

17. The method of claim 16, wherein the predefined rules included rules (a) defining semantic and/or non-semantic stopwords and specifying how the defined semantic and/or non-semantic stopwords are to be handled, (b) for standardizing transliterations or suspected transliterations, and/or (c) for applying a stemming algorithm to reduce the size of the index of words and/or groups of words prior to the building of the document-word matrix and/or the document-word matrix.

18. The method of claim 16, further comprising removing linkages between documents in a given cluster when threshold values indicative of degrees of similarity between two documents are not met.

20. A non-transitory computer readable storage medium storing instructions, that when executed by at least one processor of a computer system, perform a method according to claim 16.

21. An asset analysis system, comprising:

a database configured to store a plurality of imported assets in one or more collections, the assets being documents and/or document portions, wherein at least some of the documents and/or document portions being structured and at least some being unstructured;

an asset splitting module, executable via at least one processor, configured to split the documents and/or document portions into sub-documents and/or sub-document portions automatically and/or based on user input and store generated sub-documents and/or sub-document portions as assets in the database;

a user interface configured to enable a user to select one or more collections of assets for analysis;

an index builder, under control of the at least one processor, configured to access from the database assets belonging to the one or more selected collections and generate a word and/or groups of words index, the word and/or groups of words index including a listing of words appearing in the accessed assets;

a rules database configured to store a plurality of user-defined rules for refining the word and/or groups of words index and/or the document-word matrix;

a matrix builder, under control of the at least one processor, configured to build a document-word matrix including a value indicative of a number of times each said word and/or group of words in the index of words and/or groups of words appears in each said accessed asset;

an index refining module, under control of the at least one processor, configured to refine the word and/or groups of words index and/or the document-word matrix, based on rules stored in the rules database;

a weighting engine, under control of the at least one processor, configured to weight entries in the document-word matrix based on a semantic indexing approach; and

a clustering engine, under control of the at least one processor, configured to cluster together documents in dependence on the weighted entries.

22. The system of claim 21, wherein the rules in the rules database include rules (a) defining semantic and/or non-semantic stopwords and specifying how the defined semantic and/or non-semantic stopwords are to be handled, (b) for standardizing transliterations or suspected transliterations, and (c) for applying a stemming algorithm to reduce the size of the index of words and/or groups of words prior to the building of the document-word matrix and/or the document-word matrix.

23. The system of claim 21, wherein an index is build for words and for groups of words.

24. The system of claim 21, wherein the groups of words include a given word and one word immediately to the left of the given word.

25. The system of claim 21, wherein the clustering engine is farther configured to remove linkages between documents in a given cluster when threshold values indicative of degrees of similarity between two documents are not met.

26. The system of claim 25, wherein the clustering is based on a cosine similarity calculation.

27. The system of claim 26, wherein the threshold value is 80%.

28. The method of claim 25, wherein the threshold is user-adjustable.