Multi-Concept Latent Semantic Analysis Queries

• US 20130159313A1
• Filed: 12/14/2011
• Published: 06/20/2013
• Est. Priority Date: 12/14/2011
• Status: Active Grant

• Current Assignee: Brainspace Corporation (Reveal Data Corp.)
• Original Assignee: PureDiscovery Corporation (Reveal Data Corp.)
• Inventors: Jakubik, Paul A.
• Granted Patent: US 9,015,160 B2
• Time in Patent Office: Days
• US Class Current: 707/739
• 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;

cluster 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;

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; and

combine the first and second sets of terms into a list of output terms.

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 one or more clusters comprises using agglomerative clustering.

4. The system of claim 1, wherein combining 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 combining the first and second sets of terms into a list of output terms comprises:

determining a log-entropy weight of each of the term vectors;

determining a first log-entropy weight for the first cluster, the first log-entropy weight being a sum of the determined log-entropy weights of the term vectors of the first cluster;

determining a second log-entropy weight for the second cluster, the second log-entropy weight being a sum of the determined log-entropy weights of the term vectors of the second cluster;

determining a summed log-entropy weight by summing the first and second log-entropy weights;

determining a first percentage associated with the first cluster by dividing the first log-entropy weight by the summed log-entropy weight; and

determining a second percentage associated with the second cluster by dividing the second log-entropy weight by the summed log-entropy weight;

wherein the list of output terms comprises terms from the first and second set of terms according to the first and second percentages.

8. A computer-implemented method, comprising:

accessing text by a processing system;

identifying, by the processing system, one or more terms from the text;

determining, by the processing system, one or more term vectors associated with the identified terms;

clustering, by the processing system, the determined term vectors into one or more clusters, each cluster comprising at least one of the determined term vectors;

creating, by the processing system, one or more pseudo-documents, each pseudo-document created according to a particular one of the one or more clusters;

identifying, by the processing system using latent semantic analysis (LSA), a set of terms for each of the created pseudo-documents; and

creating, by the processing system, a list of output terms using the identified sets of terms.

9. The computer-implemented method of claim 8, wherein identifying the one or more 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 one or more clusters comprises using agglomerative clustering.

11. The computer-implemented method of claim 8, wherein creating the list of output terms using the identified sets of 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 a particular one of the one or more created pseudo-documents and the query pseudo-document;

wherein identifying the set of terms for each of the created pseudo-documents 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 particular 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 creating the list of output terms using the identified sets of terms comprises:

determining a log-entropy weight of each of the term vectors;

determining a first log-entropy weight for a first cluster of the one or more clusters, the first log-entropy weight being a sum of the determined log-entropy weights of the term vectors of the first cluster;

determining a second log-entropy weight for a second cluster of the one or more clusters, the second log-entropy weight being a sum of the determined log-entropy weights of the term vectors of the second cluster;

determining a summed log-entropy weight by summing the first and second log-entropy weights; and

determining a percentage associated with the cluster by dividing the first log-entropy weight by the summed log-entropy weight;

wherein the list of output terms comprises terms from the first and second set of terms according to the first and second percentages.

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;

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;

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; and

combining the first and second sets of terms into a list of output terms.

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

17. The non-transitory computer-readable medium of claim 15, wherein combining 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 combining the first and second sets of terms into a list of output terms comprises:

determining a log-entropy weight of each of the term vectors;

determining a first log-entropy weight for the first cluster, the first log-entropy weight being a sum of the determined log-entropy weights of the term vectors of the first cluster;

determining a second log-entropy weight for the second cluster, the second log-entropy weight being a sum of the determined log-entropy weights of the term vectors of the second cluster;

determining a summed log-entropy weight by summing the first and second log-entropy weights;

determining a first percentage associated with the first cluster by dividing the first log-entropy weight by the summed log-entropy weight; and

determining a second percentage associated with the second cluster by dividing the second log-entropy weight by the summed log-entropy weight;

wherein the list of output terms comprises terms from the first and second set of terms according to the first and second percentages.