Method for calculating relevance between words based on document set and system for executing the method

• US 8,407,233 B2
• Filed: 12/10/2007
• Issued: 03/26/2013
• Est. Priority Date: 12/12/2006
• Status: Active Grant

• Current Assignee: Naver Corporation
• Original Assignee: NHN Business Platform Corp. (Naver Corporation)
• Inventors: Song, Ki Ho, Kim, Byoung Hak, Kwak, Tae Yeong, Kim, Min uk
• Primary Examiner(s): Pham, Khanh
• Assistant Examiner(s): CHEEMA, AZAM M
• Application Number:
  US11/953,769
• Publication Number:
  US 20080140648A1
• Time in Patent Office: 1,933 Days
• Field of Search: None
• US Class Current: 707/750
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/3346 using probabilistic model

Abstract

A method and system for calculating a relevance between words using a document set is provided. The method of calculating the relevance between words based on a document set, includes: obtaining statistical information about the words based on at least one of the words, documents, a word classification of the words, and a document classification of the documents, wherein the words and the documents are included in the document set; standardizing the statistical information; and calculating the relevance between the words based on the standardized statistical information.

Claims

1. A method, using a processor, of calculating relevance among words based on a relevance of each word in a document, the method comprising:

generating statistical information associated with relevance among words by calculating a crossing frequency of words associated with a number of times of each of cross-word being appeared in a document, an appearance frequency of a word, or a word-word combination frequency associated with an appearance and a non-appearance of a combination of a first word and a second word, wherein the appearance frequency is a number of times that a word appears and frequency information is generated based on one of the appearance frequency or the crossing frequency, or the word-word combination frequency to provide the statistical information, the calculation being performed by the processor according to word-word or word-document classification;

standardizing the statistical information by applying a parameter to the calculated statistical information, wherein the standardizing the statistical information comprises generating a combination probability distribution of a random variable corresponding to a pair of words and standardizing the statistical information based on the word-word combination frequency, wherein the word-word combination frequency associated with the pair of words is a number of documents that include all words in the pair, a number of documents that do not include any word in the pair, and a number of documents that include one of the words in the pair, and wherein the random variable is defined in a point space of columns and rows that comprise appearance or non-appearance points of the word;

determining, by the processor, the relevance among the words as a numerical value based on the standardization; and

providing the numerical value associated with the relevance among words to a search system.

2. The method of claim 1, wherein the frequency information comprises one of a word-document classification appearance frequency, a document frequency, a document classification frequency, a word-word classification crossing frequency, or any combination thereof.

3. The method of claim 2, wherein the word-document classification appearance frequency associated with words is a number of times that each word is included in a document which is classified by the document classification.

4. The method of claim 2, wherein the document frequency associated with words is a number of documents that include one or more of the words, and the document classification frequency comprises a number of document classifications that include the one or more of word.

5. The method of claim 2, wherein the word-word classification crossing frequency associated with words comprise a word-reference frequency that a number of documents that include one or more of the words which is classified by the word classification.

6. The method of claim 2, wherein the word-word combination frequency associated with words in a number of documents comprises a pair of the first word and the second word, a number of documents that do not include any pair of the first word and the second word, or a number of documents that include one of the pair of the first word and the second word.

7. The method of claim 1, wherein the standardizing the statistical information further comprises:

setting, as a column for a multi-dimensional vector set, at least one of the words, the documents, the word classification, or the document classification, wherein each vector comprises each independent dimension in the multi-dimensional space; and

setting, as a row of the multi-dimensional vector set, the word corresponding to a vector of the multi-dimensional space.

8. The method of claim 1, wherein the standardizing the statistical information further comprises:

setting, as a column of a real-number-typed random variable set, at least one of the words, the documents, the word classification, or the document classification; and

setting, as a row of a real-number-typed random variable set, the word corresponding to a random variable, wherein the random variable comprises a real number value, and the random variable comprises, as a random variable value, a frequency value corresponding to the column and the row.

9. The method of claim 1, wherein the standardizing the statistical information further comprises:

setting the word as a column of a discrete random variable set to indicate each independent point in a point space where a random variable is defined; and

setting the word as a row of the discrete random variable set to indicate a discrete random variable,

wherein the discrete random variable is generated based on the crossing frequency associated with words comprising a first word and a second word that is a number of documents that include both the first word and the second word.

10. The method of claim 1, wherein the calculation comprises calculating the relevance among the words based on a distance or an angle between vectors that are included in a multi-dimensional vector set, wherein the multi-dimensional vector set is determined based on the generated statistical information.

11. The method of claim 1, wherein the calculation comprises calculating the relevance between the words based on a statistical correlation between random variables, wherein the random variables are included in a real-number-typed random variable set that is determined based on the generated statistical information.

12. The method of claim 1, wherein the calculation comprises calculating the relevance between the words based on information about two random variables of a combination probability distribution that is determined based on the generated statistical information.

13. The method of claim 1, wherein the calculation comprises calculating the relevance among the words comprising a first word and a second word based on a document frequency and a crossing frequency wherein the document frequency is a number of documents that include one of the first word and the second word, and the crossing frequency is a number of documents that include both the first word and the second word.

14. A method, using a processor, of calculating relevance among words based on a relevance of each word in a document, the method comprising:

generating statistical information associated with relevance among words by calculating a crossing frequency of words associated with a number of times of each of cross-word being appeared in a document, an appearance frequency of a word, or a word-word combination frequency associated with an appearance and a non-appearance of a combination of a first word and a second word, wherein the appearance frequency is a number of times that a word appears and frequency information is generated based on one of the appearance frequency or the crossing frequency, or the word-word combination frequency to provide the statistical information, the calculation is performed by the processor according to word-word and word-document classification;

standardizing the statistical information by applying a multi-dimensional vector set to the statistical information, wherein the standardizing the statistical information comprises generating a combination probability distribution of a random variable corresponding to a pair of words and standardizing the statistical information based on the word-word combination frequency, wherein the word-word combination frequency associated with the pair of words is a number of documents that include all words in the pair, a number of documents that do not include any word in the pair, and a number of documents that include one of the words in the pair, and wherein the random variable is defined in a point space of columns and rows that comprise appearance or non-appearance points of the word;

determining, by the processor, the relevance among the words as a numerical value based on the standardization; and

providing the numerical value associated with the relevance among words to a search system.

15. The method of claim 14, wherein determining the relevance among the words comprises calculating the appearance frequency data by using one of an inverse Lp, a cosine coefficient, an extended Dice coefficient, an extended Jaccard'"'"'s coefficient, a correlation with respect to two vectors a and b of the multi-dimensional vector set, or any combination thereof.

16. A method, using a processor, of calculating a relevance among words based on a relevance of each word in a document, the method comprising:

generating statistical information associated with relevance among words by calculating a crossing frequency of words associated with a number of times of each of cross-word being appeared in a document, an appearance frequency of a word, or a word-word combination frequency associated with an appearance and a non-appearance of a combination of a first word and a second word, wherein the appearance frequency is a number of times that a word appears and frequency information is generated based on one of the appearance frequency or the crossing frequency, or the word-word combination frequency to provide the statistical information, the calculation is performed by the processor according to word-word and word-document classification;

standardizing the statistical information by applying a parameter to the calculated statistical information, wherein the standardizing the statistical information comprises generating a combination probability distribution of a random variable corresponding to a pair of words and standardizing the statistical information based on the word-word combination frequency, wherein the word-word combination frequency associated with the pair of words is a number of documents that include all words in the pair, a number of documents that do not include any word in the pair, and a number of documents that include one of the words in the pair, and wherein the random variable is defined in a point space of columns and rows that comprise appearance or non-appearance points of the word;

determining, by the processor, the relevance among the words as a numerical value based on the standardization; and

providing the numerical value associated with the relevance among words to a search system.

17. The method of claim 16, wherein determining the relevance among the words comprises calculating the appearance frequency data by using one of a Pearson'"'"'s correlation coefficient, a coherence with respect to two random variables X and Y of the real-number-typed random variable set, or any combination thereof.

18. A system for calculating relevance among words based on relevance of each word in a document, the system comprising:

a statistical information unit, coupled to a processor, to generate statistical information associated with relevance among words according to word-word and word-document classification by calculating a crossing frequency of words associated with a number of times of each of cross-word being appeared in a document, an appearance frequency of a word, or a word-word combination frequency associated with an appearance and a non-appearance of a combination of a first word and a second word, wherein the appearance frequency is a number of times that a word appears and frequency information is generated based on one of the appearance frequency or the crossing frequency, or the word-word combination frequency to provide the statistical information, the calculation is performed by the processor according to the classification; and

a standardization unit to standardize the statistical information by applying a parameter to the statistical information, wherein to standardize the statistical information comprises to generate a combination probability distribution of a random variable corresponding to a pair of words and to standardize the statistical information based on the word-word combination frequency, wherein the word-word combination frequency associated with the pair of words is a number of documents that include all words in the pair, a number of documents that do not include any word in the pair, and a number of documents that include one of the words in the pair, and wherein the random variable is defined in a point space of columns and rows that comprise appearance or non-appearance points of the word, and

wherein the relevance among the words is determined by the processor based on the standardized statistical information.

19. The system of claim 18,

wherein the statistical information unit comprises:

an appearance frequency measurement unit to measure the appearance frequency associated with each word, wherein the frequency is a number of times that a word appears;

a crossing frequency measurement unit to measure the crossing frequency;

a frequency information unit to generate frequency information based on at least one of the appearance frequency or the crossing frequency to provide the statistical information with at least one of the appearance frequency, the crossing frequency, or the frequency information.

20. The system of claim 18, wherein the standardization unit is configured to standardize the statistical information using at least one of a multi-dimensional vector set, a real-number-typed random variable set, a combination probability distribution of random variables, a discrete random variable set, or any combination thereof.

21. The system of claim 18, wherein the relevance among words is determined by using at least one of an inverse Lp, a cosine coefficient, an extended Dice coefficient, an extended Jaccard'"'"'s coefficient, a correlation with respect to two vectors a and b of the multi-dimensional vector set, or any combination thereof.

22. The system of claim 18, wherein the relevance among words is determined by using at least one of a Pearson'"'"'s correlation coefficient, a coherence with respect to two random variables of the real-number-typed random variable set, or any combination thereof.

23. The system of claim 18, wherein the relevance among words is determined by using at least one of a Jaccard'"'"'s coefficient, a Dice coefficient, an odds-ratio, mutual information, point-wise mutual information with respect to two random variables comprising A and B by using the combination probability distribution, or any combination thereof.