Thematic clustering

• US 8,886,651 B1
• Filed: 12/22/2011
• Issued: 11/11/2014
• Est. Priority Date: 12/22/2011
• Status: Active Grant

• Current Assignee: Reputation.com, Inc.
• Original Assignee: Reputation.com, Inc.
• Inventors: Wang, Sherman, Dignan, Thomas Gerardo
• Primary Examiner(s): Truong, Dennis
• Application Number:
  US13/335,665
• Time in Patent Office: 1,055 Days
• Field of Search: 707/737, 707/999.101, 707/739, 707/741, 706/45, 706/12, 706/48, 1/1, 704/2, 704/9, 704/235
• US Class Current: 707/738
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing

Abstract

A data set is clustered into one or more initial clusters using a first term space. Initial themes for the initial clusters are determined. The first term space is reduced to create a reduced term space. At least a portion of the data set is reclustered into one or more baby clusters using the reduced term space. One or more singletons are reassigned to form one or more renovated clusters from the baby clusters. A renovated theme is determined for at least some of the renovated clusters. One or more of the renovated clusters and their respective themes are provided as output.

Claims

1. A system, comprising:

a processor configured to;

cluster a data set into one or more initial clusters using a first term space comprising a plurality of keywords;

determine an initial theme for each initial cluster, wherein the initial theme for each initial cluster is determined based on at least one keyword in the first term space;

reduce the first term space to create a reduced term space, wherein reducing the first term space includes removing from the first term space a keyword term that is determined to be present in a first document clustered into a first initial cluster and is also determined to be present in a second document clustered into a second initial cluster, and wherein a term frequency for the keyword at least meets a predetermined threshold;

recluster at least a portion of the data set into one or more baby clusters using the reduced term space, wherein after reclustering, at least one singleton is present, wherein a singleton is an element from the data set that was not assigned to any baby clusters during the reclustering;

assign at least one singleton to a baby cluster to form one or more renovated clusters;

determine a renovated theme for at least one of the renovated clusters; and

provide as output one or more of the renovated clusters and their respective themes; and

a memory coupled to the processor and configured to provide the processor with instructions.

2. The system of claim 1 wherein a first renovated theme for a first renovated cluster comprises one or more frequent keywords that are uniquely associated with the first renovated cluster.

3. The system of claim 1 wherein the processor is configured to cluster the data set into the one or more initial clusters at least in part by using singular value decomposition on a keyword-by-document matrix and wherein the processor is configured to recluster at least in part by using a vector space model.

4. The system of claim 1 wherein the data set includes entity data.

5. The system of claim 1 wherein the processor is configured to recluster at least in part by:

using a first relevance criterion to generate a set of baby clusters and a set of singletons; and

using a second relevance criterion to assign at least one singleton included in the set of singletons to a baby cluster included in the set of baby clusters, wherein the first and second relevance criteria are different.

6. The system of claim 1 wherein the processor is further configured to preprocess the data set at least in part by generating a keyword-by-document matrix.

7. The system of claim 1 wherein the processor is further configured to preprocess the data set at least in part by generating the first term space.

8. The system of claim 7 wherein the data set comprises a plurality of documents and wherein the processor is configured to generate the first term space at least in part by evaluating keywords present in the data set and not include in the first term space a solo keyword that occurs solely in a single document included in the plurality of documents.

9. The system of claim 7 wherein the processor is configured to generate the first term space at least in part by evaluating keywords present in the data set and not include in the first term space one or more keywords associated with numbers.

10. The system of claim 1 wherein at least some of the data included in the data set describes a first individual, wherein at least some of the data included in the data set describes a second individual, and wherein the output is provided to the first individual.

13. The system of claim 1 wherein the processor is further configured to:

determine a theme for at least one baby cluster or singleton that was not included in any renovated clusters during the assignment; and

provide as output one or more of the baby clusters or singletons for which a theme was determined, and the determined theme.

11. A method, comprising:

clustering a data set into one or more initial clusters using a first term space comprising a plurality of keywords;

determining an initial theme for each initial cluster, wherein the initial theme for each initial cluster is determined based on at least one keyword in the first term space;

reducing the first term space to create a reduced term space, wherein reducing the first term space includes removing from the first term space a keyword that is determined to be present in a first document clustered into a first initial cluster and is also determined to be present in a second document clustered into a second initial cluster, and wherein a term frequency for the keyword at least meets a predetermined threshold;

reclustering at least a portion of the data set into one or more baby clusters using the reduced term space, wherein after reclustering, at least one singleton is present, wherein a singleton is an element from the data set that was not assigned to any baby clusters during the reclustering;

assigning at least one singleton to a baby cluster to form one or more renovated clusters;

determining a renovated theme for at least one of the renovated clusters; and

providing as output one or more of the renovated clusters with their respective themes.

14. The method of claim 11 wherein a first renovated theme for a first renovated cluster comprises one or more frequent keywords that are uniquely associated with the first renovated cluster.

15. The method of claim 11 wherein clustering the data set into the one or more initial clusters includes using singular value decomposition on a keyword-by-document matrix and wherein reclustering includes using a vector space model.

16. The method of claim 11 wherein reclustering includes:

using a first relevance criterion to generate a set of baby clusters and a set of singletons; and

using a second relevance criterion to assign at least one singleton included in the set of singletons to a baby cluster included in the set of baby clusters, wherein the first and second relevance criteria are different.

17. The method of claim 11 further comprising preprocessing the data set at least in part by generating a keyword-by-document matrix.

18. The method of claim 11 further comprising preprocessing the data set at least in part by generating the first term space.

19. The method of claim 18 wherein the data set comprises a plurality of documents and wherein generating the first term space includes evaluating keywords terms present in the data set and not including in the first term space a solo term keyword that occurs solely in a single document included in the plurality of documents.

20. The method of claim 18 generating the first term space includes evaluating keywords present in the data set and not including in the first term space one or more keywords associated with numbers.

12. A computer program product embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

clustering a data set into one or more initial clusters using a first term space comprising a plurality of keywords;

determining an initial theme for each initial cluster, wherein the initial theme for each initial cluster is determined based on at least one keyword in the first term space;

reducing the first term space to create a reduced term space, wherein reducing the first term space includes removing from the first term space a keyword term that is determined to be present in a first document clustered into a first initial cluster and is also determined to be present in a second document clustered into a second initial cluster, and wherein a term frequency for the keyword at least meets a predetermined threshold;

reclustering at least a portion of the data set into one or more baby clusters using the reduced term space, wherein after reclustering, at least one singleton is present, wherein a singleton is an element from the data set that was not assigned to any baby clusters during the reclustering;

assigning at least one singleton to a baby cluster to form one or more renovated clusters;

determining a renovated theme for at least one of the renovated clusters; and

providing as output one or more of the renovated clusters and their respective themes.