System and method for performing efficient document scoring and clustering

• US 7,610,313 B2
• Filed: 07/25/2003
• Issued: 10/27/2009
• Est. Priority Date: 07/25/2003
• Status: Active Grant

• Current Assignee: Nuix North America Inc. (Nuix Ltd.)
• Original Assignee: Attenex Corp. (FTI Consulting Incorporated)
• Inventors: Kawai, Kenji, Evans, Lynne Marie
• Primary Examiner(s): Alam; Hosain T
• Assistant Examiner(s): HARPER, ELIYAH STONE
• Application Number:
  US10/626,984
• Publication Number:
  US 20050022106A1
• Time in Patent Office: 2,286 Days
• Field of Search: 707/3, 707/100, 707/4.1, 707/1, 707/200, 707/104.1, 707/10, 707/8, 707/6, 707/5, 707/4, 707/7
• US Class Current: 1/1
• 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 16/36 Creation of semantic tools, e.g. ontology or thesauri
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A system and method for providing efficient document scoring of concepts within a document set is described. A frequency of occurrence of at least one concept within a document retrieved from the document set is determined. A concept weight is analyzed reflecting a specificity of meaning for the at least one concept within the document. A structural weight is analyzed reflecting a degree of significance based on structural location within the document for the at least one concept. A corpus weight is analyzed inversely weighing a reference count of occurrences for the at least one concept within the document. A score associated with the at least one concept is evaluated as a function of the frequency, concept weight, structural weight, and corpus weight.

Claims

1. A system for providing efficient document scoring of concepts within and clustering of documents in an electronically-stored document set, comprising:

a database electronically storing a document set;

a scoring module scoring a document in the electronically-stored document set, comprising;

a frequency submodule determining a frequency of occurrence of at least one concept within a document;

a concept weight submodule analyzing a concept weight reflecting a specificity of meaning for the at least one concept within the document, wherein the concept weight is based on a number of terms for the at least one concept;

a structural weight submodule analyzing a structural weight reflecting a degree of significance based on structural location within the document for the at least one concept;

a corpus weight submodule analyzing a corpus weight inversely weighing a reference count of occurrences for the at least one concept within the document;

a scoring evaluation submodule evaluating a score to be associated with the at least one concept as a function of a summation of the frequency, concept weight, structural weight, and corpus weight in accordance with the formula;

2. A system according to claim 1, further comprising:

the concept weight module evaluating the concept weight in accordance with the formula;

3. A system according to claim 1, further comprising:

the structural weight module evaluating the structural weight in accordance with the formula;

4. A system according to claim 1, further comprising:

the corpus weight module evaluating the corpus weight in accordance with the formula;

5. A system according to claim 1, further comprising:

a compression module compressing the score in accordance with the formula;

S′

_i=log(S_i+1)

 

where S′

_i comprises the compressed score for each such concept i.

6. A system according to claim 1, further comprising:

a global stop concept vector cache maintaining concepts and terms; and

a filtering module filtering selection of the at least one concept based on the concepts and terms maintained in the global stop concept vector cache.

7. A system according to claim 1, further comprising:

a parsing module identifying terms within at least one document in the document set, and combining the identified terms into one or more of the concepts.

8. A system according to claim 7, further comprising:

the parsing module structuring each such identified term in the one or more concepts into canonical concepts comprising at least one of word root, character case, and word ordering.

9. A system according to claim 7, wherein at least one of nouns, proper nouns and adjectives are included as terms.

10. A system according to claim 1, further comprising:

the similarity submodule calculating the similarity in accordance with the formula;

11. A computer-implemented method for providing efficient document scoring of concepts within and clustering of documents in an electronically-stored document set, comprising:

scoring a document in an electronically-stored document set, comprising;

determining a frequency of occurrence of at least one concept within a document;

analyzing a concept weight reflecting a specificity of meaning for the at least one concept within the document, wherein the concept weight is based on a number of terms for the at least one concept;

analyzing a structural weight reflecting a degree of significance based on structural location within the document for the at least one concept;

analyzing a corpus weight inversely weighing a reference count of occurrences for the at least one concept within the document; and

evaluating a score to be associated with the at least one concept as a function of a summation of the frequency, concept weight, structural weight, and corpus weight and in accordance with the formula;

12. A computer-implemented method according to claim 11, further comprising:

evaluating the concept weight in accordance with the formula;

13. A computer-implemented method according to claim 11, further comprising:

evaluating the structural weight in accordance with the formula;

14. A computer-implemented method according to claim 11, further comprising:

evaluating the corpus weight in accordance with the formula;

15. A computer-implemented method according to claim 11, further comprising:

compressing the score in accordance with the formula;

S′

_i=log(S_i+1)

 

where S′

_i comprises the compressed score for each such concept i.

16. A computer-implemented method according to claim 11, further comprising:

maintaining concepts and terms in a global stop concept vector cache; and

filtering selection of the at least one concept based on the concepts and terms maintained in the global stop concept vector cache.

17. A computer-implemented method according to claim 11, further comprising:

identifying terms within at least one document in the document set; and

combining the identified terms into one or more of the concepts.

18. A computer-implemented method according to claim 17, further comprising:

structuring each such identified term in the one or more concepts into canonical concepts comprising at least one of word root, character case, and word ordering.

19. A computer-implemented method according to claim 17, further comprising:

including as terms at least one of nouns, proper nouns and adjectives.

20. A computer-implemented method according to claim 11, further comprising:

calculating the similarity substantially in accordance with the formula;

21. A computer-readable storage medium holding code for providing efficient document scoring of concepts within and clustering of documents in an electronically-stored document set, comprising:

code for scoring a document in an electronically-stored document set, comprising;

code for determining a frequency of occurrence of at least one concept within a document;

code for analyzing a concept weight reflecting a specificity of meaning for the at least one concept within the document, wherein the concept weight is based on a number of terms for the at least one concept;

code for analyzing a structural weight reflecting a degree of significance based on structural location within the document for the at least one concept;

code for analyzing a corpus weight inversely weighing a reference count of occurrences for the at least one concept within the document; and

code for evaluating a score to be associated with the at least one concept as a function of a summation of the frequency, concept weight, structural weight, and corpus weight in accordance with the formula;

22. An apparatus for providing efficient document scoring of concepts within and clustering of documents in an electronically-stored document set, comprising:

means for scoring a document in an electronically-stored document set, comprising;

means for determining a frequency of occurrence of at least one concept within a document;

means for analyzing a concept weight reflecting a specificity of meaning for the at least one concept within the document, wherein the concept weight is based on a number of terms for the at least one concept;

means for analyzing a structural weight reflecting a degree of significance based on structural location within the document for the at least one concept;

means for analyzing a corpus weight inversely weighing a reference count of occurrences for the at least one concept within the document; and

means for evaluating a score to be associated with the at least one concept as a function of a summation of the frequency, concept weight, structural weight, and corpus weight in accordance with the formula;