Methods and systems for constructing a taxonomy based on hierarchical clustering

• US 9,110,984 B1
• Filed: 06/22/2012
• Issued: 08/18/2015
• Est. Priority Date: 12/27/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Lewis, Glenn M., Buryak, Kirill, Benbarak, Nadav, Ben-Artzi, Aner, Peng, Jun
• Primary Examiner(s): Morrison, Jay
• Assistant Examiner(s): GORTAYO, DANGELINO N
• Application Number:
  US13/531,147
• Time in Patent Office: 1,152 Days
• Field of Search: 707/737, 707/736, 707/705, 707/739, 707/732, 707/738, 707/748, 707/758, 707/749, 707/750
• US Class Current: 1/1
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/36 Creation of semantic tools, e.g. ontology or thesauri

Abstract

Methods and systems for constructing a taxonomy based on hierarchical clustering are provided. The taxonomy is generated by first constructing a hierarchy of clusters using a clustering algorithm. A first level of the hierarchy of clusters is generated by providing a plurality of content files to a clustering algorithm. Subsequent levels of the hierarchy are generated by providing the clusters of the preceding levels to the clustering algorithm. Labels that characterize each cluster within the hierarchy are assigned to corresponding clusters. Labels and clusters are combined to form the taxonomy.

Claims

1. A computer system including instructions stored on one or more computer-readable medium and executable by one or more processors, the computer system comprising:

a statistic calculator configured to receive a plurality of content files and to determine at least one statistical measure of the content of the plurality of content files, said statistic calculator configured to store the at least one statistical measure within a statistics repository;

a cluster controller configured to cause the one or more processors to generate a hierarchy of clusters based on the at least one statistical measure stored in the statistics repository, wherein the hierarchy of clusters comprises at least two levels, each cluster within a first level of the hierarchy of clusters comprising at least one content file, each cluster within a second level of the hierarchy of clusters comprising at least one cluster of the first level of the hierarchy of clusters;

an aggregator configured to aggregate the content files of each cluster, and transmit the aggregated content file to said cluster controller to form a third level of the hierarchy of clusters;

a label manager configured to cause the one or more processors to determine a label for each cluster within the hierarchy of clusters based on the at least one statistical measure, the label identifying a topic of information contained within each cluster, the topic related to at least one of a problem experienced by a user and a request for assistance in solving the problem; and

a taxonomy manager configured to cause the one or more processors to output a taxonomy based on the hierarchy of clusters and the determined labels.

2. The computer system of claim 1, wherein said cluster controller further comprises at least one cluster algorithm module, said at least one cluster algorithm module configured to assign the at least one content file to each cluster within the first level of the hierarchy of clusters.

3. The computer system of claim 2, wherein said cluster controller further comprises an aggregator, said aggregator configured to generate a first aggregate data file for each cluster in the first level of the hierarchy of clusters.

4. The computer system of claim 3, wherein said at least one cluster algorithm module is further configured to generate the second level of the hierarchy of clusters using the first aggregate data file for each cluster in the first level of the hierarchy of clusters.

5. The computer system of claim 3, wherein said aggregator is configured to concatenate contents of the content files within each cluster.

6. The computer system of claim 1, wherein said cluster controller is further configured to generate a third level of the hierarchy of clusters, each cluster within the third level of the hierarchy of clusters comprising at least one cluster of the second level of the hierarchy of clusters.

7. The computer system of claim 1, wherein the taxonomy that is output by said taxonomy manager is a tree having labeled nodes.

8. One or more non-transitory computer-readable media having computer-executable instructions embodied thereon, wherein when executed by one or more processors, the computer-executable instructions cause the one or more processors to:

receive a plurality of content files;

determine at least one statistical measure of the content of the plurality of content files;

store the at least one statistical measure within a statistics repository for a content of the plurality of content files;

determine a number of clusters to be included in a first level of a hierarchy of clusters;

assign a plurality of content files to the first level of the hierarchy of clusters based on the at least one statistical measure stored in the statistics repository;

generate a first aggregate data file of the content files for each cluster in the first level of the hierarchy of clusters;

cluster the aggregate data file to generate a second level of the hierarchy of clusters;

aggregate the content files of each cluster;

form a third level of the hierarchy of clusters using the aggregated content file;

determine a label for each cluster in the hierarchy of clusters based on the at least one statistical measure, which identifies a topic of the content files within the cluster, the topic related to at least one of a problem experienced by a user and a request for assistance in solving the problem; and

output a taxonomy based on the determined labels.

9. The one or more non-transitory computer-readable media of claim 8, wherein determining a number of clusters to be included in a first level of the hierarchy of clusters comprises receiving user input.

10. The one or more non-transitory computer-readable media of claim 8, wherein generating a first aggregate data file for each cluster in the first level the hierarchy of clusters comprises concatenating contents of the content files within each cluster in the first level the hierarchy of clusters.

11. The one or more non-transitory computer-readable media of claim 8, wherein assigning a plurality of content files to the first level of the hierarchy of clusters comprises calculating statistical information about each of the content files assigned to each cluster within the first level of the hierarchy of clusters.

12. The one or more non-transitory computer-readable media of claim 11, wherein generating a first aggregate data file for each cluster in the first level of the hierarchy of clusters comprises concatenating the statistical information associated with each cluster within the first level of the hierarchy of clusters.

13. The one or more non-transitory computer-readable media of claim 8, further comprising instructions to selectively merge a plurality of clusters.

14. The one or more non-transitory computer-readable media of claim 8, further comprising instructions to generate a second aggregate data file for each cluster within the second level of the hierarchy of clusters.

15. The one or more non-transitory computer readable media of claim 14, further comprising instructions to generate a third level of the hierarchy of clusters.

16. A computer-implemented method including executing instructions stored on a computer-readable medium, the method comprising:

receiving a plurality of content files;

determining at least one statistical measure of the content of the plurality of content files;

storing the at least one statistical measure within a statistics repository of a content of a plurality of content files;

determining a number of clusters to be included in a first level of a hierarchy of clusters;

assigning a plurality of content files to the first level of the hierarchy of clusters by applying at least one clustering algorithm to the plurality of content files, wherein each cluster includes at least one content file;

generating a first aggregate data file for each cluster in the first level of the hierarchy of clusters by aggregating content data of each content file included within each of the clusters included in the first level of the hierarchy of clusters;

generating a second level of the hierarchy of clusters by providing each of the first aggregate data files to the at least one clustering algorithm;

aggregating the content files of each cluster;

forming a third level of the hierarchy of clusters using the aggregated content file;

determining a label for each cluster included in the hierarchy of clusters based on the at least one statistical measure, which identifies a topic of the content files within the cluster, the topic related to at least one of a problem experienced by a user and a request for assistance in solving the problem; and

outputting a taxonomy based on the determined labels.

17. The computer-implemented method of claim 16, further comprising selectively merging a plurality of clusters.

18. The computer-implemented method of claim 16, further comprising generating a second aggregate data file for each cluster within the second level of the hierarchy of clusters.

19. The computer-implemented method of claim 18, further comprising generating a third level of the hierarchy of clusters.

20. The computer-implemented method of claim 16, wherein determining a label for each cluster included within the hierarchy of clusters comprises receiving user input.