Dynamic clustering for streaming data

Abstract

In general, embodiments of the present invention provide systems, methods and computer readable media for modeling multi-dimensional, dynamically evolving data using dynamic clustering. In one aspect, a method includes receiving a core group of clusters of objects, each object being represented by a corresponding instance of a multi-dimensional feature vector including a dimension k; receiving a stream of data points representing a group of objects, each data point respectively representing an instance of dimension k describing a feature of an object within the group of objects; and, for each data point, adding an object described by the data point to a first cluster of objects within the core group of clusters; updating properties of the first cluster of objects in response to adding the object; and determining whether to update the core group of clusters using the updated properties of the first cluster of objects.

What is claimed is: 
     
         1 - 20 . (canceled) 
     
     
         21 . A system, comprising one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to cause the one or more computers to:
 add an object described by a data point of a multi-dimensional stream of data points to a cluster of objects within a core group of clusters of objects in response to a determination that the object corresponds to a classification associated with the cluster of objects;   calculate a standard deviation of the cluster of objects for a dimension describing a feature of the object within the objects; and   in response to receiving a request via a network for core cluster information related to the core group of clusters, update the core group of clusters based at least in part on a comparison between the standard deviation and a minimum standard deviation for the dimension.   
     
     
         22 . The system of  claim 21 , wherein the one or more storage devices store instructions that are operable, when executed by the one or more computers, to further cause the one or more computers to:
 determine a tuning parameter associated with the core group of clusters; and   update the core group of clusters based at least in part on the tuning parameter and the comparison between the standard deviation and the minimum standard deviation.   
     
     
         23 . The system of  claim 21 , wherein the one or more storage devices store instructions that are operable, when executed by the one or more computers, to further cause the one or more computers to:
 in response to determining that the standard deviation is greater than the minimum standard deviation for the dimension,
 split the cluster of objects into a first cluster of objects and a second cluster of objects; and 
 update the core group of clusters based at least in part on first properties associated with the first cluster of objects and second properties associated with the second cluster of objects. 
   
     
     
         24 . The system of  claim 21 , wherein the cluster of objects is a first cluster of objects within the core group of clusters, and wherein the one or more storage devices store instructions that are operable, when executed by the one or more computers, to further cause the one or more computers to:
 in response to determining that the standard deviation is less than the minimum standard deviation for the dimension,
 determine a second cluster of objects within the core group of clusters based on a similarity comparison associated with the first cluster of objects; and 
 update the core group of clusters based at least in part on properties associated with the second cluster of objects. 
   
     
     
         25 . The system of  claim 24 , wherein the standard deviation is a first standard deviation, and wherein the one or more storage devices store instructions that are operable, when executed by the one or more computers, to further cause the one or more computers to:
 update the core group of clusters based at least in part on a second standard deviation associated with the second cluster of objects.   
     
     
         26 . The system of  claim 24 , wherein the standard deviation is a first standard deviation, and wherein the one or more storage devices store instructions that are operable, when executed by the one or more computers, to further cause the one or more computers to:
 update the core group of clusters based at least in part on the first standard deviation and a second standard deviation associated with the second cluster of objects.   
     
     
         27 . The system of  claim 21 , wherein the one or more storage devices store instructions that are operable, when executed by the one or more computers, to further cause the one or more computers to:
 calculate the standard deviation of the cluster of objects for a clustering dimension describing a geographic feature of the object.   
     
     
         28 . The system of  claim 21 , wherein the one or more storage devices store instructions that are operable, when executed by the one or more computers, to further cause the one or more computers to:
 calculate the standard deviation of the cluster of objects for a clustering dimension describing a taxonomy feature of the object.   
     
     
         29 . The system of  claim 21 , wherein the one or more storage devices store instructions that are operable, when executed by the one or more computers, to further cause the one or more computers to:
 generate the core group of clusters based on a machine learning technique.   
     
     
         30 . The system of  claim 21 , wherein the one or more storage devices store instructions that are operable, when executed by the one or more computers, to further cause the one or more computers to:
 generate the core group of clusters based on a k-means clustering model.   
     
     
         31 . A computer-implemented method, comprising:
 adding, by a device comprising a processor, an object described by a data point of a multi-dimensional stream of data points to a cluster of objects within a core group of clusters of objects in response to a determination that the object corresponds to a classification associated with the cluster of objects;   calculating, by the device, a standard deviation of the cluster of objects for a dimension describing a feature of the object within the objects; and   in response to receiving a request via a network for core cluster information related to the core group of clusters, updating, by the device, the core group of clusters based at least in part on a comparison between the standard deviation and a minimum standard deviation for the dimension.   
     
     
         32 . The computer-implemented method of  claim 31 , further comprising:
 determining, by the device, a tuning parameter associated with the core group of clusters,   wherein the updating the core group of clusters comprises updating the core group of clusters based at least in part on the tuning parameter and the comparison between the standard deviation and the minimum standard deviation.   
     
     
         33 . The computer-implemented method of  claim 31 , further comprising:
 in response to determining that the standard deviation is greater than the minimum standard deviation for the dimension,
 splitting, by the device, the cluster of objects into a first cluster of objects and a second cluster of objects; and 
 updating, by the device, the core group of clusters based at least in part on first properties associated with the first cluster of objects and second properties associated with the second cluster of objects. 
   
     
     
         34 . The computer-implemented method of  claim 31 , wherein the cluster of objects is a first cluster of objects within the core group of clusters, and the computer-implemented method further comprising:
 in response to determining that the standard deviation is less than the minimum standard deviation for the dimension,
 determining, by the device, a second cluster of objects within the core group of clusters based on a similarity comparison associated with the first cluster of objects; and 
 updating, by the device, the core group of clusters based at least in part on properties associated with the second cluster of objects. 
   
     
     
         35 . The computer-implemented method of  claim 34 , wherein the standard deviation is a first standard deviation, and
 wherein the updating the core group of clusters comprises updating the core group of clusters based at least in part on a second standard deviation associated with the second cluster of objects.   
     
     
         36 . The computer-implemented method of  claim 34 , wherein the standard deviation is a first standard deviation, and
 wherein the updating the core group of clusters comprises updating the core group of clusters based at least in part on the first standard deviation and a second standard deviation associated with the second cluster of objects.   
     
     
         37 . A computer program product, stored on a computer readable medium, comprising instructions that when executed by one or more computers cause the one or more computers to:
 add an object described by a data point of a multi-dimensional stream of data points to a cluster of objects within a core group of clusters of objects in response to a determination that the object corresponds to a classification associated with the cluster of objects;   calculate a standard deviation of the cluster of objects for a dimension describing a feature of the object within the objects; and   in response to receiving a request via a network for core cluster information related to the core group of clusters, update the core group of clusters based at least in part on a comparison between the standard deviation and a minimum standard deviation for the dimension.   
     
     
         38 . The computer program product of  claim 37 , wherein the computer program product further comprises instructions that when executed by the one or more computers cause the one or more computers to:
 determine a tuning parameter associated with the core group of clusters; and   update the core group of clusters based at least in part on the tuning parameter and the comparison between the standard deviation and the minimum standard deviation.   
     
     
         39 . The computer program product of  claim 37 , wherein the computer program product further comprises instructions that when executed by the one or more computers cause the one or more computers to:
 calculate the standard deviation of the cluster of objects for a clustering dimension describing a geographic feature of the object.   
     
     
         40 . The computer program product of  claim 37 , wherein the computer program product further comprises instructions that when executed by the one or more computers cause the one or more computers to:
 calculate the standard deviation of the cluster of objects for a clustering dimension describing a taxonomy feature of the object.