Document comparision using multiple similarity measures

• US 20070143322A1
• Filed: 12/15/2005
• Published: 06/21/2007
• Est. Priority Date: 12/15/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Mukherjea, Sougata, Kothari, Ravi
• Granted Patent: US 7,472,121 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 40/194 Calculation of difference between files

Abstract

Disclosed herein is a method for comparing documents. The method includes the steps of: determining a plurality of similarity measures; and determining an overall similarity measure for the plurality of documents, based on the plurality of similarity measures. In one embodiment, the similarity measures are chosen from the group of similarity measures consisting of semantic and reference similarity measures. When comparing documents from the chemical, biochemical or pharmaceutical domains, the determination of the similarity utilizes a determination of structural similarity of the chemical formulas described in the plurality of documents.

Claims

1. A method of comparing a plurality of documents, said method comprising:

determining a plurality of similarity measures for said plurality of documents; and

determining an overall similarity measure for said plurality of documents, based on said plurality of similarity measures.

2. The method according to claim 1, wherein said plurality of similarity measures are chosen from the group of similarity measures comprising:

a semantic similarity measure based on similarity of terms contained in said plurality of documents;

a structural similarity measure based on the structures of chemical terms described in said plurality of documents; and

a reference similarity measure based on references contained in said plurality of documents.

3. The method according to claim 2, wherein said plurality of similarity measures include each of a semantic, a structural, and a reference similarity measure.

4. The method according to claim 1, further comprising:

weighting the plurality of similarity measures to determine said overall similarity measure.

5. The method according to claim 2, wherein said documents being compared comprise chemical documents, and one of said similarity measures is a semantic similarity measure, wherein determination of said semantic similarity measure utilizes a determination of chemical structural similarity of said terms contained in said plurality of documents.

6. The method according to claim 2, wherein said reference similarity measure is determined utilizing a reference graph, each of said plurality of documents associated with a corresponding node in said reference graph, said reference similarity measure comprising the inverse of the minimum path length between nodes in the reference graph associated with said plurality of documents.

7. The method according to claim 2, wherein said plurality of similarity measures include a semantic similarity measure and a reference similarity measure, and

further wherein two documents P_i and P_j being compared are represented by corresponding vectors:

d_i={w_i1, w_i2, . . . , w_in}, where w_ik (1<

k<

n) is a non-negative value denoting the weight of the term k in the document i, and

d_j={(w_j1, w_j2, . . . , w_in}, where w_ik (1<

k<

n) is a non-negative value denoting the weight of the term k in the document j,

and the semantic similarity measure SemSim( ) is given by the equation;

$\mathrm{SemSim}<br><br>\left(P_i,P_j\right)=\frac{d_i,d_j}{\sqrt{d_i·<br><br>d_i}<br><br>\sqrt{d_j·<br><br>d_j}},$

 

in which where d_i·

d_j is the dot product between the vectors, calculated as

$\underset{k=0}{\overset{n}{\sum <br><br>}}<br><br>\underset{l=0}{\overset{n}{\sum <br><br>}}<br><br>w_{\mathrm{ik}}·<br><br>w_{\mathrm{jl}}.$

8. The method according to claim 7, wherein if terms k and l are the same, w_ik·

w_jl is calculated as;

${\mathrm{tf}}_{\mathrm{ik}}\times <br><br>{\log }_2<br><br>\frac{N}{n_k}\times <br><br>{\mathrm{tf}}_{\mathrm{jl}}*{\log }_2<br><br>\frac{N}{n_l},$

wherein

tf_ik is the frequency of the term k in the document i,

tf_jl is the frequency of the term l in the document j,

N is the number of documents in a collection,

n_k is the number of documents in which the term k occurs at least once, and

n_l is the number of documents in which the term l occurs at least once.

9. The method according to claim 7, wherein if terms k and l belong to ontology classes Ck and Cl, respectively, w_ik·

w_jl is calculated as;

tf_ik×

tf_jl×

idf(Ck)×

idf(Cl)×

sim(Ck,Cl)×

WT_Ont,

wherein

tf_ik is the frequency of the term k in the document i,

tf_jl is the frequency of the term 1 in the document j,

idf(Ck) represents the inverse document frequency of class Ck in document corpus of document i and is calculated as;

${\log }_2<br><br>\frac{N}{n_{\mathrm{Ck}}},$

 

where N is the number of documents in a collection, and n_Ck is the number of documents in which a term of class Ck occurs at least once,

idf(Cl) represents the inverse document frequency of class Cl in document corpus of document j and is calculated as;

${\log }_2<br><br>\frac{N}{n_{\mathrm{Cl}}},$

 

where N is the number of documents in a collection, and n_Cl is the number of documents in which a term of class Cl occurs at least once,

sim(Ck, Cl) is calculated as;

$\mathrm{sim}<br><br>\left(\mathrm{Ck},\mathrm{Cl}\right)=\frac{2\times <br><br>\left[\ln <br><br>\left(p_{\min }\right)\right]}{\ln <br><br>\left(p_{\mathrm{Ck}}\right)+\ln <br><br>\left(p_{\mathrm{Cl}}\right)},$

 

where p_Ck is the probability of encountering the class Ck or a child of the term in a given taxonomy, p_Cl is the probability of encountering the class Cl or a child of the term in a given taxonomy and p_min is the minimum probability among common ancestors of classes Ck and Cl, and

WT_ont is a predefined constant in the range 0 to 1.

10. The method according to claim 2, further comprising:

determining said terms contained in said plurality of documents by utilizing at least one of an ontology, a taxonomy, and a dictionary.

11. The method according to claim 5, wherein said terms contained in said plurality of documents are associated with chemical substructures represented as strings.

12. A computer program product having a computer readable medium having a computer program recorded therein for comparing documents, said computer program product comprising a method comprising:

determining a plurality of similarity measures for said plurality of documents; and

determining an overall similarity measure for said plurality of documents, based on said plurality of similarity measures.

13. A computer program product having a computer readable medium having a computer program recorded therein for comparing documents, said computer program product comprising a method comprising:

determining a reference similarity measure, based on references contained in said plurality of documents;

determining a semantic similarity measure, based on the similarity of terms contained in said plurality of documents; and

determining a similarity measure for said plurality of documents, based on said reference similarity measure and said semantic similarity measure.

15. The system of claim 13, further comprising:

a crawler for obtaining said presented materials from the Internet.

16. The system of claim 13, wherein said required information is selected from inventors'"'"' names, assignees, titles, and abstracts.

17. The system of claim 13, wherein said annotated terms are scientific terms identified and classified from said parsed presented materials.

18. The system of claim 13, wherein said annotator further creates a reference graph based on references contained within said parsed presented materials.

19. The system of claim 13, wherein said presented materials comprise patent documents.

14. A knowledge retrieval system, comprising:

a parser for extracting required information from presented materials;

an annotator for annotating terms from said parsed presented materials, by utilizing at least one of an ontology, a taxonomy, and a dictionary;

a chemical representation device for deriving information about said annotated terms, based on a connection table;

an integrator for collating said derived information for storage in a database; and

a retrieval system for retrieving information from said database, based on input search criteria.