Method and system for naming a cluster of words and phrases

• US 7,031,909 B2
• Filed: 03/12/2002
• Issued: 04/18/2006
• Est. Priority Date: 03/12/2002
• Status: Active Grant

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Verity Incorporated (Healthstream Incorporated)
• Inventors: Mao, Jianchang, Taank, Sumit, Chung, Christina, Luk, Alpha
• Primary Examiner(s): MCFADDEN, SUSAN IRIS
• Application Number:
  US10/096,048
• Publication Number:
  US 20030177000A1
• Time in Patent Office: 1,498 Days
• Field of Search: None
• US Class Current: 704/9
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

The present invention provides a method, system and computer program for naming a cluster, or a hierarchy of clusters, of words and phrases that have been extracted from a set of documents. The invention takes these clusters as the input and generates appropriate labels for the clusters using a lexical database. Naming involves first finding out all possible word senses for all the words in the cluster, using the lexical database; and then augmenting each word sense with words that are semantically similar to that word sense to form respective definition vectors. Thereafter, word sense disambiguation is done to find out the most relevant sense for each word. Definition vectors are clustered into groups. Each group represents a concept. These concepts are thereafter ranked based on their support. Finally, a pre-specified number of words and phrases from the definition vectors of the dominant concepts are selected as labels, based on their generality in the lexical database. Therefore, the labels may not necessarily consist of the original words in the cluster. A hierarchy of clusters is named in a recursive fashion starting from leaf clusters. Dominant concepts in child clusters are propagated into their parent to reduce the labeling complexity of parent clusters.

Claims

1. A method of naming a cluster of words and phrases extracted from a set of documents, using a lexical database, comprising the steps of:

a. generating definition vectors of words in the cluster using the lexical database;

b. determining support of the definition vectors;

c. determining most relevant definition vector corresponding to each word in the cluster;

d. generating concepts from the most relevant definition vectors using a preselected clustering method;

e. determining support of said concepts;

f. designating predetermined number of top ranked concepts as dominant concepts;

g. naming the cluster by a predetermined number of most frequent words from the cluster, if the dominant concepts are not designated; and

h. naming the cluster by choosing words from the lexical database that describe the dominant concepts in accurate detail, if the dominant concepts are designated.

2. The method according to claim 1, wherein one or more of the steps is embodied in a hardware chip.

3. The method according to claim 1, wherein said step of generating definition vectors, further comprises the steps of:

a. determining all word senses of the words in the cluster using the lexical database;

b. augmenting the word senses with words that are semantically related to the word sense, using the lexical database.

4. The method according to claim 3, wherein said step of augmenting the word senses with words that are semantically related to the word sense, using the lexical database, further comprises augmenting the word sense with its synonyms, hyponyms, hypernyms, meronyms and metonyms.

5. The method according to claim 1, wherein said step of determining support of the definition vectors, further comprises the steps of:

a. designating a definition vector of a word as a selected definition vector;

b. computing similarity measure between the selected definition vector and all other definition vectors of all other words;

c. computing support of the selected definition vector by determining the number of definition vectors with which the similarity measure is above a predetermined threshold; and

d. repeating steps a–

c, if all the definition vectors of all the words have not been designated as the selected definition vector for determining their support.

6. The method according to claim 5, wherein said step of computing similarity measure between the selected definition vector and all other definition vectors of all other words, further comprises the steps of:

a. designating a definition vector of a word as a chosen definition vector for computing its similarity measure with the selected definition vector;

b. finding out the number of words that are common in the chosen definition vector and the selected definition vector;

c. outputting the number of words as the similarity measure; and

d. repeating steps a–

c for all the definition vectors for all other the words.

7. The method according to claim 1, wherein said step of determining most relevant definition vector corresponding to each word in the cluster, further comprises the steps of:

a. designating a word from the cluster as a selected word;

b. choosing the definition vector with highest support among all other definition vectors for the selected word, as most relevant definition vector for the selected word; and

c. repeating steps a-b for all words in the cluster.

8. The method according to claim 1, wherein said step of determining support of the concepts, further comprises the steps of:

a. determining support of corresponding most relevant definition vectors; and

b. determining support of the concepts by adding support of corresponding most relevant definition vectors.

9. The method according to claim 8, wherein said step of determining support of corresponding most relevant definition vectors, further comprises the steps of:

a. designating a most relevant definition vector of the concept as a selected definition vector;

b. computing similarity measure between the selected definition vector and all other most relevant definition vectors of all other concepts;

c. computing support of the selected definition vector by finding out the number of most relevant definition vectors with which the similarity measure is above a predetermined threshold; and

d. repeating steps a–

c, if all the most relevant definition vectors of all the concepts have not been designated as the selected definition vector for determining their support.

10. The method according to claim 1, wherein said step of naming the cluster by choosing words from the lexical database that describe the dominant concepts in accurate detail, if dominant concepts are found, further comprises the steps of:

a. designating a word from the dominant concepts as a designated concept, to generate an appropriate name for the cluster, using the designated concept and the lexical database;

b. generating the designated concept'"'"'s hypernyms and hyponyms using the lexical database;

c. determining depth of the designated concept using the lexical database;

d. repeating steps a-c for rest of words in the dominant concepts; and

e. choosing words from the lexical database that best describes essence of the cluster using generated hypernyms and hyponyms, and the determined depths.

11. A system for naming a cluster of words and phrases extracted from a document, using a lexical database, comprising:

a. means for generating definition vectors of words in said cluster using said lexical database;

b. means for determining support of said definition vectors;

c. means for determining most relevant definition vector corresponding to each said word in said cluster;

d. means for generating concepts from said most relevant definition vectors;

e. means for determining support of said concepts;

f. means for designating predetermined number of top ranked said concepts as dominant concepts; and

g. means for naming said cluster using said dominant concepts.

12. The system according to claim 11, wherein said means for generating definition vectors, comprises:

a. means for determining all word senses of said words in said cluster, using said lexical database; and

b. means for augmenting said word senses with words that are semantically related to said word sense, using said lexical database.

13. The system according to claim 12, wherein said augmenting means augments said word sense with its synonyms, hyponyms, hypernyms, meronyms and metonyms.

14. The system according to claim 11, wherein said means for determining support of said definition vectors, comprises:

a. means for designating a definition vector of a word as a selected definition vector;

b. means for computing similarity measure between said selected definition vector and all other definition vectors of all other words; and

c. means for computing support of said selected definition vector.

15. The system according to claim 14, wherein said means for computing similarity measure between said selected definition vector and all other definition vectors of all other words, comprises:

a. means for designating a definition vector of a word as a chosen definition vector for computing its similarity measure with said selected definition vector;

b. means for finding out the number of words that are common in said chosen definition vector and said selected definition vector; and

c. means for outputting said number of words as the similarity measure.

16. The system according to claim 11, wherein said means for determining most relevant definition vector corresponding to each said word in said cluster, comprises:

a. means for designating a word from said cluster as a selected word; and

b. means for choosing said definition vector with highest support among all other said definition vectors for said selected word, as most relevant definition vector for said selected word.

17. The system according to claim 11, wherein said means for determining support of said concepts, comprises:

a. means for determining support of corresponding said most relevant definition vectors; and

b. means for determining support of said concepts by adding support of corresponding said most relevant definition vectors.

18. The system according to claim 17, wherein said means for determining support of corresponding said most relevant definition vectors, comprises:

a. means for designating said most relevant definition vector of said concept as a selected definition vector;

b. means for computing similarity measure between said selected definition vector and all other most relevant definition vectors of all other said concepts; and

c. means for computing support of said selected definition vector by finding out the number of said most relevant definition vectors with which said similarity measure is above a pre-determined threshold.

19. The system according to claim 11, wherein said means for naming said cluster using said dominant concepts, comprises:

a. means for designating a word from said dominant concepts as a designated concept, to generate an appropriate name for said cluster, using said designated concept and said lexical database;

b. means for generating said designated concept'"'"'s hypernyms and hyponyms using said lexical database;

c. means for determining depth of said designated concept using said lexical database; and

d. means for choosing words from said lexical database that best describes essence of said cluster using said generated hypernyms and hyponyms, and said determined depths.

20. A computer program product for naming a cluster of words and phrases, extracted from a document, using a lexical database, the computer program product embodied in a computer-readable medium and comprising:

a. computer-readable program code means for generating definition vectors of words in said cluster using said lexical database;

b. computer-readable program code means for determining support of said definition vectors;

c. computer-readable program code means for determining most relevant definition vector corresponding to each said word in said cluster;

d. computer-readable program code means for generating concepts from said most relevant definition vectors;

e. computer-readable program code means for determining support of said concepts;

f. computer-readable program code means for designating predetermined number of top ranked said concepts as dominant concepts; and

g. computer-readable program code means for naming said cluster using said dominant concepts.

21. The computer program product according to claim 20, wherein said computer-readable program code means for generating definition vectors, comprises:

a. computer-readable program code means for determining all word senses of said words in said cluster, using said lexical database; and

b. computer-readable program code means for augmenting said word senses with words that are semantically related to said word sense, using said lexical database.

22. The computer program product according to claim 21, wherein said computer-readable program code augmenting means augments said word sense with its synonyms, hyponyms, hypernyms, meronyms and metonyms.

23. The computer program product according to claim 20, wherein said computer-readable program code means for determining support of said definition vectors, comprises:

a. computer-readable program code means for designating a definition vector of a word as a selected definition vector;

b. computer-readable program code means for computing similarity measure between said selected definition vector and all other definition vectors of all other words; and

c. computer-readable program code means for computing support of said selected definition vector.

24. The computer program product according to claim 23, wherein said computer-readable program code means for computing similarity measure between said selected definition vector and all other definition vectors of all other words, comprises:

a. computer-readable program code means for designating a definition vector of a word as a chosen definition vector for computing its similarity measure with said selected definition vector;

b. computer-readable program code means for finding out the number of words that are common in said chosen definition vector and said selected definition vector; and

c. computer-readable program code means for outputting said number of words as the similarity measure.

25. The computer program product according to claim 20, wherein said computer-readable program code means for determining most relevant definition vector corresponding to each said word in said cluster, comprises:

a. computer-readable program code means for designating a word from said cluster as a selected word; and

b. computer-readable program code means for choosing said definition vector with highest support among all other said definition vectors for said selected word, as most relevant definition vector for said selected word.

26. The computer program product according to claim 20, wherein said computer-readable program code means for determining support of said concepts, comprises:

a. computer-readable program code means for determining support of corresponding said most relevant definition vectors; and

b. computer-readable program code means for determining support of said concepts by adding support of corresponding said most relevant definition vectors.

27. The computer program product according to claim 26, wherein said computer-readable program code means for determining support of corresponding said most relevant definition vectors, comprises:

a. computer-readable program code means for designating said most relevant definition vector of said concept as a selected definition vector;

b. computer-readable program code means for computing similarity measure between said selected definition vector and all other most relevant definition vectors of all other said concepts; and

c. computer-readable program code means for computing support of said selected definition vector by finding out the number of said most relevant definition vectors with which said similarity measure is above a pre-determined threshold.

28. The computer program product, according to claim 20, wherein said computer-readable program code means for naming said cluster using said dominant concepts, comprises:

a. computer-readable program code means for designating a word from said dominant concepts as a designated concept, to generate an appropriate name for said cluster, using said designated concept and said lexical database;

b. computer-readable program code means for generating said designated concept'"'"'s hypernyms and hyponyms using said lexical database;

c. computer-readable program code means for determining depth of said designated concept using said lexical database; and

d. computer-readable program code means for choosing words from said lexical database that best describes essence of said cluster using said generated hypernyms and hyponyms, and said determined depths.

29. A method of naming clusters of words and phrases extracted from a set of documents in a hierarchy that is in the form of a tree, using a lexical database, comprising the steps of:

a. designating a cluster from the hierarchy of clusters as a selected cluster;

b. determining whether the selected cluster is a leaf cluster in the hierarchy;

c. if the selected cluster is a leaf cluster, performing the steps of;

i. designating the selected cluster as an updated cluster;

ii. generating definition vectors of words in the updated cluster using the lexical database;

iii. determining support of the definition vectors;

iv. determining most relevant definition vector corresponding to each word in the updated cluster;

v. generating concepts from the most relevant definition vectors using a preselected clustering method;

vi. determining support of the concepts;

vii. designating predetermined number of top ranked concepts as dominant concepts;

viii. naming the selected cluster by a predetermined number of most frequent words from the cluster, if the dominant concepts are not designated; and

ix. naming the selected cluster by choosing words from the lexical database that describe the dominant concepts in accurate detail, if the dominant concepts are designated;

d. if the selected cluster is not a leaf cluster, performing the steps of;

i. augmenting the selected cluster with already generated dominant concepts of the selected cluster'"'"'s children clusters;

ii. augmenting the selected cluster with concepts of the selected cluster'"'"'s children clusters that may not be dominant in that children cluster;

iii. designating augmented cluster as an updated cluster;

iv. generating definition vectors of words in the updated cluster using the lexical database;

v. determining support of the definition vectors;

vi. determining most relevant definition vector corresponding to each word in the updated cluster;

vii. generating concepts from the most relevant definition vectors using a preselected clustering method;

viii. determining support of the concepts;

ix. designating predetermined number of top ranked concepts as dominant concepts;

x. naming the selected cluster by a predetermined number of most frequent words from the cluster, if the dominant concepts are not designated; and

xi. naming the selected cluster by choosing words from the lexical database that describe the dominant concepts in accurate detail, if the dominant concepts are designated;

e. if all clusters of the hierarchy of clusters have not been designated as the selected cluster for naming, repeating steps a–

d.

30. The method according to claim 29, wherein one or more of the steps is embodied in a hardware chip.

31. The method according to claim 29, wherein said step of generating definition vectors, further comprises the steps of:

a. determining all word senses of the words in the updated cluster using the lexical database;

b. augmenting the word senses with words that are semantically related to the word sense, using the lexical database.

32. The method according to claim 31, wherein said step of augmenting the word senses with words that are semantically related to the word sense, using the lexical database, further comprises augmenting the word sense with its synonyms, hyponyms, hypernyms, meronyms and metonyms.

33. The method according to claim 29, wherein said step of determining support of the definition vectors, further comprises the steps of:

a. designating a definition vector of a word as a selected definition vector;

b. computing similarity measure between the selected definition vector and all other definition vectors of all other words;

c. computing support of the selected definition vector by finding out the number of definition vectors with which the similarity measure is above a predetermined threshold; and

d. if all definition vectors of all the words have not been designated as the selected definition vector for determining their support, repeating steps a–

c.

34. The method according to claim 33, wherein said step of computing similarity measure between the selected definition vector and all other definition vectors of all other words, further comprises the steps of:

a. designating a definition vector of a word as a chosen definition vector for computing its similarity measure with the selected definition vector;

b. finding out the number of words that are common in the chosen definition vector and the selected definition vector;

c. outputting the number of words as the similarity measure; and

d. repeating steps a–

c for all the definition vectors for all other the words.

35. The method according to claim 29, wherein said step of determining most relevant definition vector corresponding to each word in the updated cluster, further comprises the steps of:

a. designating a word from the updated cluster as a selected word;

b. choosing the definition vector with highest support among all other definition vectors for the selected word, as most relevant definition vector for the selected word; and

c. repeating steps a-b for all words in the updated cluster.

36. The method according to claim 29, wherein said step of determining support of the concepts, further comprises the steps of:

a. determining support of corresponding most relevant definition vectors; and

b. determining support of the concepts by adding support of corresponding most relevant definition vectors.

37. The method according to claim 36, wherein said step of determining support of corresponding most relevant definition vectors, further comprises the steps of:

a. designating a most relevant definition vector of the concept as a selected definition vector;

b. computing similarity measure between the selected definition vector and all other most relevant definition vectors of all other concepts;

c. computing support of the selected definition vector by finding out the number of most relevant definition vectors with which the similarity measure is above a predetermined threshold; and

d. repeating steps a–

c, if all the most relevant definition vectors of all the concepts have not been designated as the selected definition vector for determining their support.

38. The method according to claim 29, wherein said step of naming the selected cluster by choosing words from the lexical database that describe the dominant concepts in accurate detail, if dominant concepts are found, comprises the steps of:

a. designating a word from the dominant concepts as a designated concept, to generate an appropriate name for the selected cluster, using the designated concept and the lexical database;

b. generating the designated concept'"'"'s hypernyms and hyponyms using the lexical database;

c. determining depth of the designated concept using the lexical database;

d. repeating steps a–

c for rest of words in the dominant concepts; and

e. choosing words from the lexical database that best describes essence of the updated cluster using the generated hypernyms and hyponyms, and the determined depths.

39. A system for naming clusters of words and phrases extracted from a set of documents in a hierarchy that is in the form of a tree, using a lexical database, comprising:

a. means for selecting a cluster of words and phrases from said hierarchy of clusters;

b. means for updating said cluster depending upon whether said cluster is a leaf cluster or not;

c. means for generating definition vectors of words in said updated cluster using said lexical database;

d. means for determining support of said definition vectors;

e. means for determining most relevant definition vector corresponding to each said word in said updated cluster;

f. means for generating concepts from said most relevant definition vectors using a preselected clustering method;

g. means for determining support of said concepts;

h. means for designating predetermined number of top ranked said concepts as dominant concepts; and

i. means for naming said cluster using said dominant concepts.

40. The system according to claim 39, wherein said means for generating definition vectors, comprises:

a. means for determining all word senses of said words in said updated cluster, using said lexical database; and

b. means for augmenting said word senses with words that are semantically related to said word sense, using said lexical database.

41. The system according to claim 40, wherein said augmenting means augments said word sense with its synonyms, hyponyms, hypernyms, meronyms and metonyms.

42. The system according to claim 39, wherein said means for determining support of said definition vectors, comprises:

a. means for designating a definition vector of a word as a selected definition vector;

b. means for computing similarity measure between said selected definition vector and all other definition vectors of all other words;

c. means for computing support of said selected definition vector.

43. The system according to claim 42, wherein said means for computing similarity measure between said selected definition vector and all other definition vectors of all other words, comprises:

a. means for designating a definition vector of a word as a chosen definition vector for computing its similarity measure with said selected definition vector;

b. means for finding out the number of words that are common in said chosen definition vector and said selected definition vector; and

c. means for outputting said number of words as the similarity measure.

44. The system according to claim 39, wherein said means for determining most relevant definition vector corresponding to each said word in said updated cluster, comprises:

a. means for designating a word from said updated cluster as a selected word; and

b. means for choosing said definition vector with highest support among all other said definition vectors for said selected word, as most relevant definition vector for said selected word.

45. The system according to claim 39, wherein said means for determining support of said concepts, comprises:

a. means for determining support of corresponding said most relevant definition vectors; and

b. means for determining support of said concepts by adding support of corresponding said most relevant definition vectors.

46. The system according to claim 45, wherein said means of determining support of corresponding said most relevant definition vectors, comprises:

a. means for designating a most relevant definition vector of said concept as a selected definition vector;

b. means for computing similarity measure between said selected definition vector and all other most relevant definition vectors of all other said concepts; and

c. means for computing support of said selected definition vector by finding out the number of said most relevant definition vectors with which said similarity measure is above a predetermined threshold.

47. The system according to claim 39, wherein said means for naming said cluster using said dominant concepts, comprises:

a. means for designating a word from said dominant concepts as a designated concept, to generate an appropriate name for said cluster, using said designated concept and said lexical database;

b. means for generating said designated concept'"'"'s hypernyms and hyponyms using said lexical database;

c. means for determining depth of said designated concept using said lexical database; and

d. means for choosing words from said lexical database that best describes essence of said updated cluster using said generated hypernyms and hyponyms, and said determined depths.

48. The system as claimed in claim 39 wherein the system comprises a computer program for use in a stored program computer.