Method and system for incremental centroid clustering

Abstract

A method at a computing device for anomaly detection, the method including storing, at the computing device, a full batch model for a plurality of data points, wherein each of the plurality of data points is associated with one of a plurality of clusters, and wherein the storing comprises a table for storing information about the plurality of clusters without storing the plurality of data points; receiving a new data point from a hardware sensor; determining that the new data point falls outside the full batch model, thereby detecting an anomaly; and performing an action based on the anomaly.

The invention claimed is: 
     
         1 . A method at a computing device for anomaly detection, the method comprising:
 storing, at the computing device, a full batch model for a plurality of data points, wherein each of the plurality of data points is associated with one of a plurality of clusters, wherein the storing comprises storing in a table, information about the plurality of clusters without storing the plurality of data points, and wherein the information about the plurality of clusters comprises, for each cluster of the plurality of clusters, a number of data points within the cluster, a centroid of the cluster, a sum of features across all the data points in the cluster, and an approximate distance between points within the cluster;   receiving a new data point from a hardware sensor;   determining that the new data point falls outside the full batch model based on the stored information, thereby detecting an anomaly; and   performing an action based on the anomaly.   
     
     
         2 . The method of  claim 1 , wherein the computing device creates the full batch model by:
 selecting a data point;
 determining that the data point falls within a threshold an average distance to a center of a cluster; 
 adding the data point to the cluster; and 
 iteratively performing the determining and adding for subsequent data points in a data point training set. 
   
     
     
         3 . The method of  claim 2 , wherein the adding the data point to the cluster comprises:
 incrementing an index indicating a number of data points within the cluster;   adding information for the data point to a sum of features for the cluster;   updating a centroid of the cluster; and   updating a value comprising an approximate distance between points in the cluster.   
     
     
         4 . The method of  claim 2 , further comprising:
 determining that a second data point does not fall within the threshold of the average distance to the center of the cluster; and   creating a new cluster for the data point.   
     
     
         5 . The method of  claim 4 , further comprising:
 determining that a number of clusters in the anomaly detection system exceeds a function;   removing all clusters with a single data point in the cluster from the anomaly detection system; and   updating the threshold to a higher value.   
     
     
         6 . The method of  claim 5 , wherein the function is a function of a square root below a total number of data points processed. 
     
     
         7 . The method of  claim 1 , wherein the computing device stores only incremental information about each cluster. 
     
     
         8 . The method of  claim 1 , wherein the action comprises at least one of:
 providing an alert; and   autonomously controlling a device associated with the computing device.   
     
     
         9 . The method of  claim 1 , wherein the computing device is an edge device within an internet of things system. 
     
     
         10 . A computing device for anomaly detection, the computing device comprising:
 a processor;   memory; and   a communications subsystem, wherein the computing device is configured to:   store a full batch model for a plurality of data points, wherein each of the plurality of data points is associated with one of a plurality of clusters, wherein the storing comprises storing in a table, information about the plurality of clusters without storing the plurality of data points, and wherein the information about the plurality of clusters comprises, for each cluster of the plurality of clusters, a number of data points within the cluster, a centroid of the cluster, a sum of features across all the data points in the cluster, and an approximate distance between points within the cluster;   receive a new data point from a hardware sensor;   determine that the new data point falls outside the full batch model based on the stored information, thereby detecting an anomaly; and   perform an action based on the anomaly.   
     
     
         11 . The computing device of  claim 10 , wherein the computing device is configured to create the full batch model by:
 selecting a data point;   determining that the data point falls within a threshold an average distance to a center of a cluster;   adding the data point to the cluster; and   iteratively perform the determining and adding for subsequent data points in a training data point set.   
     
     
         12 . The computing device of  claim 11 , wherein the computing device is configured to add the data point to the cluster by:
 incrementing an index indicating a number of data points within the cluster;   adding information for the data point to a sum of features for the cluster;   updating a centroid of the cluster; and   updating a value comprising an approximate distance between points in the cluster.   
     
     
         13 . The computing device of  claim 11 , wherein the computing device is further configured to:
 determine that a second data point does not fall within the threshold of the average distance to the center of the cluster; and   create a new cluster for the data point.   
     
     
         14 . The computing device of  claim 13 , wherein the computing device is further configured to:
 determine that a number of clusters in for anomaly detection exceeds a function;   remove all clusters with a single data point in the cluster; and   update the threshold to a higher value.   
     
     
         15 . The computing device of  claim 14 , wherein the function is a function of a square root below a total number of data points processed. 
     
     
         16 . The computing of  claim 10 , wherein the computing device stores only incremental information about each cluster. 
     
     
         17 . The computing device of  claim 10 , wherein the action comprises at least one of:
 providing an alert; and   autonomously controlling a device associated with the computing device.   
     
     
         18 . The computing device of  claim 10 , wherein the computing device is an edge device within an internet of things system. 
     
     
         19 . A non-transitory computer storage medium for storing instruction code for anomaly detection, which, when executed by a processor on a computing device, cause the computing device to:
 store a full batch model for a plurality of data points, wherein each of the plurality of data points is associated with one of a plurality of clusters, wherein the storing comprises storing in a table, information about the plurality of clusters without storing the plurality of data points, and wherein the information about the plurality of clusters comprises, for each cluster of the plurality of clusters, a number of data points within the cluster, a centroid of the cluster, a sum of features across all the data points in the cluster, and an approximate distance between points within the cluster;   receive a new data point from a hardware sensor;   determine that the new data point falls outside the full batch model based on the stored information, thereby detecting an anomaly; and   perform an action based on the anomaly.