US 7,734,629 B2Granted

System and method using hierachical clustering for evolutionary clustering of sequential data sets

AssigneeYahoo! Inc.

InventorsDeepayan Chakrabarti, Shanmugasundaram Ravikumar, Andrew Tomkins

Life of this patent

Estimating the term…

Loading patent…

Abstract

An improved system and method for evolutionary clustering of sequential data sets is provided. A snapshot cost may be determined for representing the data set for a particular clustering method used and may determine the cost of clustering the data set independently of a series of clusterings of the data sets in the sequence. A history cost may also be determined for measuring the distance between corresponding clusters of the data set and the previous data set in the sequence of data sets to determine a cost of clustering the data set as part of a series of clusterings of the data sets in the sequence. An overall cost may be determined for clustering the data set by minimizing the combination of the snapshot cost and the history cost. Any clustering method may be used, including flat clustering and hierarchical clustering.

Claims19

Dependent claims

A computer-implemented method for clustering a data set, comprising:

determining a snapshot cost of using hierarchical clustering to cluster at least one data set in a sequence of data sets independently of a series of clusterings of the data sets in the sequence, the at least one data set having a plurality of data elements and each of the sequence of data sets being acquired at different times,
determining an overall cost of using hierarchical clustering to cluster the at least one data set in the sequence of data sets by minimizing a combination of the snapshot cost of using hierarchical clustering to cluster the at least one data set independently of the series of clusterings of the data sets in the sequence and a history cost of using hierarchical clustering to cluster the at least one data set as part of the series of clusterings of the data sets in the sequence;
and
using hierarchical clustering to cluster the at least one data set in the sequence of data sets according to the overall cost determined by minimizing the combination of both the snapshot cost of clustering the at least one data set independently of the series of clusterings of the data sets in the sequence and the history cost of clustering the at least one data set as part of the series of clusterings of the data sets in the sequence.

1 more element

Dependencies are inferred from the claim text.