Multi-concept latent semantic analysis queries

• US 9,015,160 B2
• Filed: 12/14/2011
• Issued: 04/21/2015
• Est. Priority Date: 12/14/2011
• Status: Active Grant

• Current Assignee: Brainspace Corporation (Reveal Data Corp.)
• Original Assignee: Brainspace Corporation (Reveal Data Corp.)
• Inventors: Jakubik, Paul A.
• Primary Examiner(s): Jalil, Neveen Abel
• Assistant Examiner(s): BISKEBORN, KRISTOFER M
• Application Number:
  US13/326,284
• Publication Number:
  US 20130159313A1
• Time in Patent Office: 1,224 Days
• Field of Search: 707/737, 707/739, 707/748, 707/750
• US Class Current: 707/737
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/358 Browsing; Visualisation therefor
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

A method includes accessing text, identifying a plurality of terms from the text, determining a plurality of term vectors associated with the identified plurality of terms, and clustering the determined plurality of term vectors into a plurality of clusters, the plurality of clusters comprising a first and a second cluster, the first and second clusters each comprising two or more of the determined term vectors. The method further includes creating a first pseudo-document according to the first cluster, creating a second pseudo-document according to the second cluster, identifying a first set of terms associated with the first cluster using latent semantic analysis (LSA) of the first pseudo-document, identifying a second set of terms associated with the second cluster using LSA of the second pseudo-document, and combining the first and second sets of terms into a list of output terms.

Claims

1. A system, comprising:

one or more memory units; and

one or more processing units operable to;

access text;

identify a plurality of terms from the text;

determine a plurality of term vectors associated with the identified plurality of terms;

calculate a weight of each of the determined plurality of term vectors;

cluster the determined plurality of term vectors into a plurality of clusters, the plurality of clusters comprising a first cluster related to a first concept of the text and a second cluster related to a second concept of the text, the first concept being distinct from the second concept, the first and second clusters each comprising two or more of the determined term vectors, the clustering comprising grouping two or more of the determined term vectors together based on the determined weights of the two or more term vectors and a distance between the two or more term vectors;

create a first pseudo-document according to the first cluster;

create a second pseudo-document according to the second cluster;

identify, using latent semantic analysis (LSA) of the first pseudo-document, a first set of terms associated with the first cluster;

identify, using LSA of the second pseudo-document, a second set of terms associated with the second cluster;

determine a first weight associated with the first cluster and a second weight associated with the second cluster, wherein the first weight is based at least on the determined weights of the term vectors of the first cluster, and wherein the second weight is based at least on the determined weights of the term vectors of the second cluster;

determine a first percentage of a list of output terms that should come from the first cluster and a second percentage of the list of output terms that should come from the second cluster, the first percentage based on a ratio of the first weight to a sum of the first and second weights, the second percentage based on a ratio of the second weight to the sum of the first and second weights;

select one or more terms from the first set of terms according to the determined first percentage;

select one or more terms from the second set of terms according to the determined second percentage;

combine the selected terms from the first and second sets of terms into the list of output terms, the list of output terms having the first and second concepts of the text; and

store the list of output terms in the one or more memory units.

2. The system of claim 1, wherein identifying the plurality of terms from the text comprises using a vocabulary driven parser.

3. The system of claim 1, wherein clustering the determined plurality of term vectors into the plurality of clusters comprises using agglomerative clustering.

4. The system of claim 1, wherein combining the selected terms from the first and second sets of terms into the list of output terms comprises using log-entropy mixing.

5. The system of claim 1, wherein:

the one or more processing units are further operable to;

create a query pseudo-document from the determined plurality of term vectors;

create a first leaned pseudo-document using the first pseudo-document and the query pseudo-document; and

create a second leaned pseudo-document using the second pseudo-document and the query pseudo-document;

wherein;

identifying the first set of terms associated with the first cluster comprises using LSA of the first leaned pseudo-document; and

identifying the second set of terms associated with the second cluster comprises using LSA of the second leaned pseudo-document.

6. The system of claim 5, wherein creating the first and second leaned pseudo-documents comprises:

determining a query vector according to the query pseudo-document;

determining a first cluster vector according to the first pseudo-document;

determining a second cluster vector according to the second pseudo-document;

normalizing the query vector and the first cluster vector to the same length;

normalizing the query vector and the second cluster vector to the same length;

determining a first leaned cluster vector that points to a location that is between the query vector and the first cluster vector; and

determining a second leaned cluster vector that points to a location that is between the query vector and the second cluster vector.

7. The system of claim 1, wherein:

the weights of each of the determined plurality of term vectors comprise log-entropy weights;

the first weight associated with the first cluster comprises a sum of the determined log-entropy weights of the term vectors of the first cluster; and

the second weight associated with the second cluster comprises a sum of the determined log-entropy weights of the term vectors of the second cluster.

8. A computer-implemented method, comprising:

accessing text by a processing system;

identifying, by the processing system, a plurality of terms from the text;

determining, by the processing system, a plurality of term vectors associated with the identified terms;

calculating a weight of each of the determined term vectors;

clustering, by the processing system, the determined term vectors into a plurality of clusters, each of the clusters being related to a distinct concept of the text, each cluster comprising at least one of the determined term vectors, the clustering comprising selecting the at least one of the determined term vectors based on the determined weights of the term vectors and distances between the determined term vectors;

creating, by the processing system, a first pseudo-document according to a first cluster of the plurality of clusters and a second pseudo-document according to a second cluster of the plurality of clusters;

identifying, by the processing system using latent semantic analysis (LSA), a first set of terms associated with the first cluster and a second set of terms associated with the second cluster;

determining a first weight associated with the first cluster and a second weight associated with the second cluster, wherein the first weight is based at least on the determined weights of the term vectors of the first cluster, and wherein the second weight is based at least on the determined weights of the term vectors of the second cluster;

determining a first percentage of a list of output terms that should come from the first cluster and a second percentage of the list of output terms that should come from the second cluster, the first percentage based on a ratio of the first weight to a sum of the first and second weights, the second percentage based on a ratio of the second weight to the sum of the first and second weights;

selecting one or more terms from the first set of terms according to the determined first percentage;

selecting one or more terms from the second set of terms according to the determined second percentage;

creating, by the processing system, the list of output terms using at least a portion of the selected terms from the first and second sets of terms, the list of output terms having the distinct concepts of the plurality of clusters; and

storing the list of output terms in one or more memory units.

9. The computer-implemented method of claim 8, wherein identifying the terms from the text comprises using a vocabulary driven parser.

10. The computer-implemented method of claim 8, wherein clustering the determined term vectors into the plurality of clusters comprises using agglomerative clustering.

11. The computer-implemented method of claim 8, wherein creating the list of output terms comprises using log-entropy mixing.

12. The computer-implemented method of claim 8, further comprising:

creating a query pseudo-document from the determined term vectors; and

creating a leaned pseudo-document using the first pseudo-documents and the query pseudo-document;

wherein identifying the first set of terms comprises using LSA of the leaned pseudo-document.

13. The computer-implemented method of claim 12, wherein creating the leaned pseudo-document comprises:

determining a query vector according to the query pseudo-document;

determining a cluster vector according to the first pseudo-document;

normalizing the query vector and the cluster vector to the same length; and

determining a leaned cluster vector that points to a location that is between the query vector and the cluster vector.

14. The computer-implemented method of claim 8, wherein:

the weights of each of the determined term vectors comprise log-entropy weights;

the first weight associated with the first cluster comprises a sum of the determined log-entropy weights of the term vectors of the first cluster; and

the second weight associated with the second cluster comprises a sum of the determined log-entropy weights of the term vectors of the second cluster.

15. A non-transitory computer-readable medium comprising software, the software when executed by one or more processing units operable to perform operations comprising:

accessing text;

identifying a plurality of terms from the text;

determining a plurality of term vectors associated with the identified plurality of terms;

calculating a weight of each of the determined plurality of term vectors;

clustering the determined plurality of term vectors into a plurality of clusters, the plurality of clusters comprising a first cluster related to a first concept of the text and a second cluster related to a second concept of the text, the first concept being distinct from the second concept, the first and second clusters each comprising two or more of the determined term vectors, the clustering comprising grouping two or more of the determined term vectors together based on the determined weights of the two or more term vectors and a distance between the two or more term vectors;

creating a first pseudo-document according to the first cluster;

creating a second pseudo-document according to the second cluster;

identifying, using latent semantic analysis (LSA) of the first pseudo-document, a first set of terms associated with the first cluster;

identifying, using LSA of the second pseudo-document, a second set of terms associated with the second cluster;

determining a first weight associated with the first cluster and a second weight associated with the second cluster, wherein the first weight is based at least on the determined weights of the term vectors of the first cluster, and wherein the second weight is based at least on the determined weights of the term vectors of the second cluster;

determining a first percentage of a list of output terms that should come from the first cluster and a second percentage of the list of output terms that should come from the second cluster, the first percentage based on a ratio of the first weight to a sum of the first and second weights, the second percentage based on a ratio of the second weight to the sum of the first and second weights;

selecting one or more terms from the first set of terms according to the determined first percentage;

selecting one or more terms from the second set of terms according to the determined second percentage;

combining the selected terms from the first and second sets of terms into the list of output terms, the list of output terms having the first and second concepts of the text; and

storing the list of output terms in one or more memory units.

16. The non-transitory computer-readable medium of claim 15, wherein clustering the determined plurality of term vectors into the plurality of clusters comprises using agglomerative clustering.

17. The non-transitory computer-readable medium of claim 15, wherein combining the selected terms from the first and second sets of terms into the list of output terms comprises using log-entropy mixing.

18. The non-transitory computer-readable medium of claim 15, the one or more processing units further operable to perform operations comprising:

creating a query pseudo-document from the determined plurality of term vectors;

creating a first leaned pseudo-document using the first pseudo-document and the query pseudo-document; and

creating a second leaned pseudo-document using the second pseudo-document and the query pseudo-document; and

wherein;

identifying the first set of terms associated with the first cluster comprises using LSA of the first leaned pseudo-document; and

identifying the second set of terms associated with the second cluster comprises using LSA of the second leaned pseudo-document.

19. The non-transitory computer-readable medium of claim 18, wherein creating the first and second leaned pseudo-documents comprises:

determining a query vector according to the query pseudo-document;

determining a first cluster vector according to the first pseudo-document;

determining a second cluster vector according to the second pseudo-document;

normalizing the query vector and the first cluster vector to the same length;

normalizing the query vector and the second cluster vector to the same length;

determining a first leaned cluster vector that points to a location that is between the query vector and the first cluster vector; and

determining a second leaned cluster vector that points to a location that is between the query vector and the second cluster vector.

20. The non-transitory computer-readable medium of claim 15, wherein:

the weights of each of the determined plurality of term vectors comprise log-entropy weights;

the first weight associated with the first cluster comprises a sum of the determined log-entropy weights of the term vectors of the first cluster; and

the second weight associated with the second cluster comprises a sum of the determined log-entropy weights of the term vectors of the second cluster.