Automatic index term augmentation in document retrieval
Disclosed are methods and systems for automatically assigning index terms to electronic documents such as Web pages or sites in a manner which may be used to facilitate the retrieval of electronic documents of interest. The method involves determining co-occurrences of terms in other documents with the electronic document, and selecting terms as index terms based upon those scores. The method permits the efficient retrieval of electronic documents.
1. A method for automatically choosing index terms to be associated with a document D, for purposes of facilitating document retrieval processes, comprising:
creating a search query Q comprised of terms in document D;
applying the search query Q to a collection of documents C 0 ;
selecting the N 0 documents from the collection of documents C 0 which achieve the highest scores upon application of the search query Q; and
selecting I T terms for use as index terms for document D from among terms in the N 0 documents based upon the co-occurrence of terms in the N 0 documents with terms in the document D.
2. The method of claim 1 , further comprising selecting the I T terms for use as index terms for document D by
(a) calculating, for terms T k which occur in the N 0 documents selected, the co-occurrence C n (T j , T k ) of the term T k with terms T j in document D:
C n (T j , T k )=log 10 (co ki (T j ,T k )+1)*idf(T k )/log 10 (N 0 ),
where
:
co
ki
(
T
j
,
T
k
)
=
∑
n
=
1
N
0
tf
(
T
k
,
n
)
*
tf
(
T
j
,
n
)
tf (T k , n)=number of occurrences of term T k in document n in the N 0 documents,
tf (T j , n)=number of occurrences of term T j in document n in the N 0 documents,
idf (T k )=the inverted document frequency for the term T k ,
=min (1.0, log 10 (N/N T )/5.0)
N=the number of documents in the collection C 0 over which the query Q was run,
N T =the number of documents in the collection C 0 over which the query Q was run, which contained the term T k
(b) calculating, for terms T k which occur in the N 0 documents selected, the co-occurrencef D (T k ) of that term T k with document D:
f
D
(
T
k
)
=
∏
j
=
1
T
0
(
δ
+
C
ni
(
T
k
,
T
j
)
)
idf
(
T
j
)
where
T j =a term in document D,
T 0 =the number of terms in document D,
idf (T j )=the inverted document frequency for the term T j ,
=min (1.0, log 10 (N/N 1 )/5.0),
N=the number of documents in the collection C 0 over which the query Q was run,
N j =the number of documents in the collection C 0 over which the query Q was run, which contained the term T j and
δ=a constant; and
(c) selecting I T terms for use as index terms for document D from among terms in the N 0 documents based upon the scores f D (T k ) achieved by the terms.
3. The method of claim 2 , wherein the documents are Web pages.
4. The method of claim 2 , wherein the documents are Web sites.
5. The method of claim 2 , wherein the search query Q which is applied comprises all of the terms in document D.
6. The method of claim 2 , wherein the search query Q which is applied comprises all of the terms in document D with preselected stop terms eliminated.
7. The method of claim 2 , wherein the search query Q is applied to select documents from among the documents in the collection C 0 by calculating for each document D in the collection C 0 a score S D based upon the occurrence in the document D of terms in the search query Q.
8. The method of claim 7 , wherein in applying the search query Q to the collection of documents C 0 the total score S D for a document D in the collection C 0 is
S
D
=
∑
T
=
1
T
0
TF
TD
*
IDF
T
where:
T 0 is the number of terms in the search query Q, and
TF TD is Robertson's term frequency for the term T in the document D,
=N TD /(N TD +K 1 +K 2 *(L D /L O )),
where:
N TD is the number of times the term T occurs in document D,
L D is the length of document D,
L O is the average length of documents in the collection C 0 to be searched, and
K 1 and K 2 are constants
and IDF T=log((N+K 3 )/N T )/ log (N+K 4 )
where:
N is the number of documents in the collection C 0 to be searched
N T is the number of documents containing the term T in the collection C 0 to be searched,
K 3 and K 4 are constants.
9. The method of claim 8 , wherein K 1 equals 0.5, K 2 equals 1.5, K 3 equals 0.5, and K 4 equals 1.0.
10. The method of claim 2 , wherein all terms whose scores f D (T k ) exceed a given cutoff score are selected for use as index terms.
11. The method of claim 9 , wherein the number N 0 of documents chosen by application of the search query Q is 50, δ=0.01, and the number I T is 30.
12. The method of claim 2 , wherein the number N 0 of documents chosen by application of the search query Q is predetermined.
13. The method of claim 12 , wherein the number N 0 is 50.
14. The method of claim 2 , wherein all documents whose scores upon application of the search query Q exceed a given cutoff score are selected.
15. The method of claim 2 , wherein co-occurrences f D (T k ) are calculated for all terms contained in the N 0 documents selected.
16. The method of claim 2 , wherein co-occurrences f D (T k ) are calculated for all terms contained in the N 0 documents selected, except that preselected stop terms are eliminated.
17. The method of claim 2 , wherein δ=0.01.
18. The method of claim 2 , wherein the number I T of terms chosen as index terms is predetermined.
19. The method of claim 17 , wherein the number I T is 30.
20. A device for automatically choosing index terms to be associated with a document D, for purposes of facilitating document retrieval processes, comprising:
(a) means for creating a search query Q comprised of terms in document D;
(b) means for applying the search query Q to a collection of documents C 0 ;
(c) means for selecting the N 0 documents from the collection of documents C 0 which achieve the highest scores upon application of the search query Q; and
(d) means for selecting I T terms for use as index terms for document D from among terms in the N 0 documents based upon the co-occurrence of terms in the N 0 documents with terms in the document D.
21. The device of claim 20 , further comprising means for selecting the I T terms for use as index terms for document D, which means are comprised of
(a) means for calculating, for terms T k which occur in the N 0 documents selected, the co-occurrence C n (T j ,T k ) of that term T k with terms T j in document D:
C n ( T j , T k )=log 10 ( co ki ( T j ,T k )+1)* idf ( T k )/ log 10 ( N 0 ),
where
:
co
ki
(
T
j
,
T
k
)
=
∑
n
=
1
N
0
tf
(
T
k
,
n
)
*
tf
(
T
j
,
n
)
.
tf (T k , n)=number of occurrences of term T k in document n in the N 0 documents,
tf (T j , n)=number of occurrences of term T j in document n in the N 0 documents,
idf(T k )=the inverted document frequency for the term T k ,
=min (1.0, log 10 (N/N T )/5.0)
N=the number of documents in the collection C 0 over which the query Q was run,
N T =the number of documents in the collection C 0 over which the query Q was run, which contained the term T k
(b) means for calculating, for terms T k which occur in the N 0 documents selected, the co-occurrence f D (T k ) of that term T k with document D:
f
D
(
T
k
)
=
∏
j
=
1
T
0
(
δ
+
C
ni
(
T
k
,
T
j
)
)
idf
(
T
j
)
where
T j =a term in document D,
T 0 =the number of terms in document D,
idf(T j )=the inverted document frequency for the term T j ,
=min (1.0, log 10 (N/N 1 )/5.0),
N=the number of documents in the collection C 0 over which the query Q was run,
N J =the number of documents in the collection C 0 over which the query Q was run, which contained the term T j and
δ=a constant; and
(c) means for selecting I T terms for use as index terms for document D from among terms in the N 0 documents based upon the scores f D (T k ) achieved by the terms.
22. The device of claim 21 , wherein the documents are Web pages.
23. The device of claim 21 , wherein the documents are Web sites.
24. The device of claim 21 , wherein the search query Q which is applied comprises all of the terms in document D.
25. The device of claim 21 , wherein the search query Q which is applied comprises all of the terms in document D with preselected stop terms eliminated.
26. The device of claim 21 , wherein the search query Q is applied to select documents from among the documents in the collection C 0 by calculating for each document D in the collection C 0 a score S D based upon the occurrence in the document D of terms in the search query Q.
27. The device of claim 26 , wherein in applying the search query Q to the collection of documents C 0 the total score S D for a document D in the collection C 0 is
S
D
=
∑
T
=
1
T
0
TF
TD
*
IDF
T
where:
T 0 is the number of terms in the search query Q, and
TF TD is Robertson's term frequency for the Term T in the Document D,
=N TD /(N TD +K 1 +K 2 *(L D /L O )),
where:
N TD is the number of times the term T occurs in document D,
L D is the length of document D,
L O is the average length of documents in the collection C 0 to be searched, and
K 1 and K 2 are constants
and IDF T =log ((N+K 3 )/N T )/ log (N+K 4 )
where:
N is the number of documents in the collection C 0 to be searched
N T is the number of documents containing the term T in the collection C 0 to be searched,
K 3 and K 4 are constants.
28. The device of claim 27 , wherein K 1 equals 0.5, K 2 equals 1.5, K 3 equals 0.5, and K 4 equals 1.0.
29. The device of claim 28 , wherein the number N 0 of documents chosen by application of the search query Q is 50, δ=0.01, and the number I T is 30.
30. The device of claim 21 , wherein the number N 0 of documents chosen by application of the search query Q is predetermined.
31. The device of claim 30 , wherein the number N 0 is 50.
32. The device of claim 21 , wherein all documents whose scores upon application of the search query Q exceed a given cutoff score are selected.
33. The device of claim 21 , wherein co-occurrences f D (T k ) are calculated for all terms contained in the N 0 documents selected.
34. The device of claim 21 , wherein co-occurrences f D (T k ) are calculated for all terms contained in the N 0 documents selected, except that preselected stop terms are eliminated.
35. The device of claim 21 , wherein δ=0.01.
36. The device of claim 21 , wherein the number I T of terms chosen as index terms is predetermined.
37. The device of claim 36 , wherein the number I T is 30 .
38. The device of claim 21 , wherein all terms whose scores f D (T k ) exceed a given cutoff score are selected for use as index terms.
39. A method for automatically assigning-an-index term to a document D, the method comprising:
selecting one or more index terms from a plurality of index terms;
identifying one or more documents of a plurality of documents to which each of the one or more index terms has been assigned;
comparing, for each of the one or more index terms, each of the identified documents to the document D;
determining a score for each of the one or more index terms based on the comparing; and
assigning the index term associated with the highest score to the document D.
40. The method of claim 39 wherein the comparing includes:
determining a log likelihood ratio between each of the identified documents and the document D.
41. The method of claim 39 wherein the score is a total score based on scores for each of the identified documents.
42. The method of claim 39 wherein the assigning includes:
assigning a predetermined number of the index terms associated with the highest scores to the document D.
43. A device for automatically assigning an index term to a document D, the device comprising:
means for selecting one or more index terms from a plurality of index terms;
means for identifying one or more documents of a plurality of documents to which each of the one or more index terms has been assigned;
means for comparing, for each of the one or more index terms, each of the identified documents to the document D;
means for determining a score for each of the one or more index terms based on the comparing; and
means for assigning the index term associated with the highest score to the document D.
44. The device of claim 43 wherein the means for comparing includes:
means for determining a log likelihood ratio between each of the identified documents and the document D.
45. The device of claim 43 wherein the score is a total score based on scores for each of the identified documents.
46. The device of claim 43 wherein the means for assigning includes:
means for assigning a predetermined number of the index terms associated with the highest scores to the document D.