Identifying Clusters Of Words According To Word Affinities

• US 20090094207A1
• Filed: 10/01/2008
• Published: 04/09/2009
• Est. Priority Date: 10/05/2007
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Sidorowich, John J., Adler, B. Thomas, Marvit, David L., Stergiou, Stergios, Jain, Jawahar, Gilman, Alex
• Granted Patent: US 8,108,392 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/367 Ontology

Abstract

In one embodiment, identifying clusters of words includes accessing a record that records affinities. An affinity between a first and second word describes a quantitative relationship between the first and second word. Clusters of words are identified according to the affinities. A cluster comprises words that are sufficiently affine with each other. A first word is sufficiently affine with a second word if the affinity between the first and second word satisfies one or more affinity criteria. A clustering analysis is performed using the clusters.

Claims

1. A method comprising:

accessing a record stored in one or more tangible storage media, the record recording a plurality of affinities, an affinity between a first word and a second word describing a quantitative relationship between the first word and the second word;

identifying a plurality of clusters of the plurality of words according to the plurality of affinities, a cluster comprising one or more words that are sufficiently affine with each other, a first word sufficiently affine with a second word if the affinity between the first word and the second word satisfies one or more affinity criteria;

performing a clustering analysis using the clusters to yield a result; and

reporting the result of the clustering analysis.

2. The method of claim 1, the affinity further comprising an affinity selected from a set consisting of a basic affinity, a directional affinity, and a differential affinity.

3. The method of claim 1, the identifying the plurality of clusters of the plurality of words according to the plurality of affinities further comprising building a cluster by:

placing a seed word in the cluster; and

repeating the following for each word added to the cluster;

sorting the plurality of words according a forward affinity between the each word and the current word;

identifying one or more candidate words satisfying the one or more affinity criteria, the one or more affinity criteria comprising a forward affinity with the current word criterion and a backward affinity with the seed word criterion; and

placing the one or more candidate words in the cluster.

4. The method of claim 1, the identifying the plurality of clusters of the plurality of words according to the plurality of affinities further comprising sorting the words into the clusters by repeating the following for each word of the plurality of words:

if the affinity between the each word and a first word of a cluster satisfies an affinity threshold, placing the each word in the cluster; and

otherwise, placing the each word in an empty cluster.

5. The method of claim 1, the identifying the plurality of clusters of the plurality of words according to the plurality of affinities further comprising comparing a plurality of affinity vectors of the words by:

obtaining the plurality of affinity vectors recording the affinity values, an affinity vector associated with a word and comprising a plurality of affinity values, an affinity value indicating the affinity between the associated word and another word;

identifying a set of affinity vectors that are proximate to each other; and

placing the words associated with the set of affinity vectors in a cluster.

6. The method of claim 1, the performing the clustering analysis using the clusters to yield the result further comprising categorizing a page comprising the plurality of words according to the clusters.

7. The method of claim 1, the performing the clustering analysis using the clusters to yield the result further comprising categorizing a page according to the clusters by:

selecting one or more important words of the page;

determining one or more clusters of the plurality of clusters that include the one or more important words; and

categorizing the page according to the one or more clusters.

8. The method of claim 1, the performing the clustering analysis using the clusters to yield the result further comprising determining a corpus character of a corpus comprising the plurality of words according to the clusters.

9. The method of claim 1, the performing the clustering analysis using the clusters to yield the result further comprising:

determining one or more clusters of the plurality of clusters that comprise one or more search terms of a given search query;

selecting one or more words from the one or more clusters; and

reporting the selected one or more words.

10. The method of claim 1, the performing the clustering analysis using the clusters to yield the result further comprising:

determining one or more clusters of the plurality of clusters that comprise one or more search terms of a given search query;

selecting one or more words from the one or more clusters; and

generating one or more next search queries from the selected one or more words.

11. The method of claim 1, the performing the clustering analysis using the clusters to yield the result further comprising analyzing a social network of people, each person associated with a user identifier, the words comprising the user identifiers, the social network analyzed by:

determining one or more relationships among the people according to the clusters.

12. The method of claim 1:

the accessing the record stored in the one or more tangible storage media further comprising;

accessing the affinity values generated from a plurality of data sets, the plurality of data sets comprising the plurality of words;

the identifying the plurality of clusters of the plurality of words according to the plurality of affinities further comprising;

identifying a cluster set for each data set; and

the performing the clustering analysis using the clusters to yield the result further comprising;

comparing a first cluster set of a first data set with a second cluster set of a second data set to analyze a relationship between the first data set and the second data set.

13. One or more computer-readable tangible media encoding software operable when executed to:

access a record, the record recording a plurality of affinities, an affinity between a first word and a second word describing a quantitative relationship between the first word and the second word;

identify a plurality of clusters of the plurality of words according to the plurality of affinities, a cluster comprising one or more words that are sufficiently affine with each other, a first word sufficiently affine with a second word if the affinity between the first word and the second word satisfies one or more affinity criteria;

perform a clustering analysis using the clusters to yield a result; and

report the result of the clustering analysis.

14. The computer-readable tangible media of claim 13, the affinity further comprising an affinity selected from a set consisting of a basic affinity, a directional affinity, and a differential affinity.

15. The computer-readable tangible media of claim 13, the software further operable to identify the plurality of clusters of the plurality of words according to the plurality of affinities by building a cluster by:

placing a seed word in the cluster; and

repeating the following for each word added to the cluster;

sorting the plurality of words according a forward affinity between the each word and the current word;

identifying one or more candidate words satisfying the one or more affinity criteria, the one or more affinity criteria comprising a forward affinity with the current word criterion and a backward affinity with the seed word criterion; and

placing the one or more candidate words in the cluster.

16. The computer-readable tangible media of claim 13, the software further operable to identify the plurality of clusters of the plurality of words according to the plurality of affinities by sorting the words into the clusters by repeating the following for each word of the plurality of words:

if the affinity between the each word and a first word of a cluster satisfies an affinity threshold, placing the each word in the cluster; and

otherwise, placing the each word in an empty cluster.

17. The computer-readable tangible media of claim 13, the software further operable to identify the plurality of clusters of the plurality of words according to the plurality of affinities by comparing a plurality of affinity vectors of the words by:

obtaining the plurality of affinity vectors recording the affinity values, an affinity vector associated with a word and comprising a plurality of affinity values, an affinity value indicating the affinity between the associated word and another word;

identifying a set of affinity vectors that are proximate to each other; and

placing the words associated with the set of affinity vectors in a cluster.

18. The computer-readable tangible media of claim 13, the software further operable to perform the clustering analysis using the clusters to yield the result by categorizing a page comprising the plurality of words according to the clusters.

19. The computer-readable tangible media of claim 13, the software further operable to perform the clustering analysis using the clusters to yield the result by categorizing a page according to the clusters by:

selecting one or more important words of the page;

determining one or more clusters of the plurality of clusters that include the one or more important words; and

categorizing the page according to the one or more clusters.

20. The computer-readable tangible media of claim 13, the software further operable to perform the clustering analysis using the clusters to yield the result by determining a corpus character of a corpus comprising the plurality of words according to the clusters.

21. The computer-readable tangible media of claim 13, the software further operable to perform the clustering analysis using the clusters to yield the result by:

determining one or more clusters of the plurality of clusters that comprise one or more search terms of a given search query;

selecting one or more words from the one or more clusters; and

reporting the selected one or more words.

22. The computer-readable tangible media of claim 13, the software further operable to perform the clustering analysis using the clusters to yield the result by:

determining one or more clusters of the plurality of clusters that comprise one or more search terms of a given search query;

selecting one or more words from the one or more clusters; and

generating one or more next search queries from the selected one or more words.

23. The computer-readable tangible media of claim 13, the software further operable to perform the clustering analysis using the clusters to yield the result by analyzing a social network of people, each person associated with a user identifier, the words comprising the user identifiers, the social network analyzed by:

determining one or more relationships among the people according to the clusters.

24. The computer-readable tangible media of claim 13, the software further operable to:

access the record stored in the one or more tangible storage media by;

accessing the affinity values generated from a plurality of data sets, the plurality of data sets comprising the plurality of words;

identify the plurality of clusters of the plurality of words according to the plurality of affinities by;

identifying a cluster set for each data set; and

perform the clustering analysis using the clusters to yield the result by;

comparing a first cluster set of a first data set with a second cluster set of a second data set to analyze a relationship between the first data set and the second data set.

25. A system comprising:

means for accessing a record stored in one or more tangible storage media, the record recording a plurality of affinities, an affinity between a first word and a second word describing a quantitative relationship between the first word and the second word;

means for identifying a plurality of clusters of the plurality of words according to the plurality of affinities, a cluster comprising one or more words that are sufficiently affine with each other, a first word sufficiently affine with a second word if the affinity between the first word and the second word satisfies one or more affinity criteria;

means for performing a clustering analysis using the clusters to yield a result; and

means for reporting the result of the clustering analysis.