Implicit hierarchical clustering

• US 8,316,024 B1
• Filed: 02/04/2011
• Issued: 11/20/2012
• Est. Priority Date: 02/04/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Buryak, Kirill, Ben-Artzi, Aner, Lewis, Glenn M., Peng, Jun, Benbarak, Nadav
• Primary Examiner(s): Ruiz, Angelica
• Application Number:
  US13/021,278
• Time in Patent Office: 655 Days
• Field of Search: None
• US Class Current: 707/736
• CPC Class Codes: G06F 16/41 Indexing; Data structures therefor; Storage structures

Abstract

A number of levels of a cluster hierarchy may be determined, and a current level of the levels may be obtained by providing a current input to at least one clustering algorithm to thereby obtain a current output of the at least one clustering algorithm, where the current output includes a current plurality of clusters and defines the current level. Content information associated with each cluster of the current output from the at least one clustering algorithm may be aggregated to obtain aggregated content information for each cluster of the current output. The obtaining and the aggregating may be repeated, using the aggregated content information as the new current input, to thereby obtain a new current output defining a new current level during the obtaining, and using the new current output during the aggregating, until the new current level equals the number of levels.

Claims

1. A computer system including instructions stored on a computer-readable medium and executable by at least one processor, the computer system comprising:

a level manager configured to cause the at least one processor to;

determine a number of levels of a cluster hierarchy, and generate a level of the cluster hierarchy by;

providing a current input to a clustering algorithm, and

obtaining a current output of the clustering algorithm, the current output including a current plurality of clusters,

wherein the current output defines the level; and

an aggregator configured to cause the at least one processor to execute an aggregating of content information associated with each cluster of the current output to obtain aggregated content information for each cluster of the current output,

wherein the level manager is further configured to repeat the generating to generate a new level of the cluster hierarchy until the new level equals the number of levels by;

using the aggregated content information as new current input for the clustering algorithm, obtaining a new current output defining the new level, and

when the new level is not equal to the number of levels, causing the aggregator to repeat the execution of the aggregating using the new current output, to obtain new aggregated content information for each cluster of the new current output to be used as new current input.

2. The system of claim 1, wherein as part of determining the number of levels, the level manager is configured to receive the number of levels from a user by way of a graphical user interface.

3. The system of claim 1, wherein as part of determining the number of levels, the level manager is configured receive a number of clusters to be generated at each level of the cluster hierarchy.

4. The system of claim 1, wherein the level manager is configured to receive a specified clustering algorithm for each level of the cluster hierarchy for use as the clustering algorithm.

5. The system of claim 1, wherein the level manager is configured to select a first clustering algorithm for obtaining the current output, and configured to select a second clustering algorithm for obtaining the new current output.

6. The system of claim 1, wherein the first current input to the clustering algorithm includes a plurality of content files.

7. The system of claim 6, wherein as part of aggregating of content information, the aggregator is configured to concatenate contents of content files within each cluster.

8. The system of claim 6, wherein the clustering algorithm is configured to calculate statistical information characterizing the plurality of content files to thereby execute clustering thereof.

9. The system of claim 8, wherein as part of aggregating of content information, the aggregator is configured to concatenate the statistical information associated with each cluster.

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

determining a number of levels of a cluster hierarchy;

generating a level of the cluster hierarchy by;

providing a current input to a clustering algorithm, and

obtaining a current output of the clustering algorithm, the current output including a current plurality of clusters,

wherein the current output defines the level;

aggregating content information associated with each cluster of the current output from the clustering algorithm to obtain aggregated content information for each cluster of the current output; and

repeating, until the new level equals the number of levels;

the generating to generate a new level of the cluster hierarchy by using the aggregated content information as new current input to the clustering algorithm to obtain a new current output defining the new level of the cluster hierarchy, and

the aggregating using the new current output, when the new level is not equal to the number of levels.

11. The method of claim 10 wherein the determining the number of levels includes receiving a number of clusters to be generated at each level of the cluster hierarchy.

12. The method of claim 10 wherein the determining the number of levels includes receiving a specified clustering algorithm for the clustering algorithm to use at each level, wherein the specified algorithm used at a first level differs from the specified algorithm used at a second level.

13. The method of claim 10, wherein the first current input to the clustering algorithm includes a plurality of content files.

14. The method of claim 13, wherein the aggregating of content information includes concatenating contents of content files within each cluster.

15. The method of claim 13, wherein the clustering algorithm is configured to calculate statistical information characterizing the plurality of content files to thereby execute clustering thereof.

16. The method of claim 15, wherein the aggregating of content information includes concatenating the statistical information associated with each cluster.

17. A computer program product, the computer program product being tangibly embodied on a computer-readable medium and including executable code that is configured to cause a data processing apparatus to:

determine a number of levels of a cluster hierarchy;

generate a level of the cluster hierarchy by;

providing a current input to a clustering algorithm, and

obtaining a current output of the clustering algorithm, the current output including a current plurality of clusters,

wherein the current output defines the level;

aggregate content information associated with each cluster of the current output from the clustering algorithm to obtain aggregated content information for each cluster of the current output; and

repeat, until the new level equals the number of levels;

the generating to generate a new level of the cluster hierarchy until the new level equals the number of levels by using the aggregated content information as new current input to the clustering algorithm to obtain a new current output defining the new level of the cluster hierarchy, and

the aggregating using the new current output, when the new level is not equal to the number of levels.

18. The computer program product of claim 17, wherein the determining the number of levels includes receiving a number of clusters to be generated at each level of the cluster hierarchy.

19. The computer program product of claim 17, wherein the determining the number of levels includes receiving a specified clustering algorithm for the clustering algorithm to use at each level, wherein the specified algorithm used at a first level differs from the specified algorithm used at a second level.

20. The computer program product of claim 17, wherein the first current input includes a plurality of content files and the clustering algorithm is configured to calculate statistical information characterizing the plurality of content files to thereby execute clustering thereof, and the aggregating the content information includes concatenating the statistical information associated with each cluster.