Methods and apparatus for clustering evolving data streams through online and offline components
AssigneeInternational Business Machines Corporation
InventorsCharu C. Aggarwal, Philip Shi-Lung Yu
Life of this patent
Estimating the term…
Abstract
A technique of clustering data of a data stream is provided. Online statistics are first created from the data stream. Offline processing of the online statistics is then performed when offline processing either required or desired. Online statistics may be created through the reception of data points from the data stream and the formation and updating of data groups. Offline processing may be performed by reclustering groups of data points around sampled data points and reporting the newly formed clusters.
Claims13
A method of clustering data of a data stream of electronic consumer transactions comprising the steps of:
- receiving at least one data point from the data stream;
- assigning the at least one data point to one of a plurality of groups of data points;
- updating and storing online statistics of the one of the plurality of groups of data points, wherein the online statistics comprise lower-level clusters;
- determining whether offline processing is one of required and desired for analysis of the lower-level clusters;
- performing offline processing of the online statistics through at least one re-clustering of the plurality of groups of data points around at least one sampled pseudo-point to create higher-level clusters, when offline processing is one of required and desired;
- utilizing the online statistics to monitor data stream evolution by performing offline processing to subtract online statistics over specified horizons, and to determine evolution classification based on subtracted statistics;
- reporting the higher-level clusters of electronic consumer transactions for analysis by a user;
- and
- repeating the receiving, assigning, updating and determining steps when offline processing is not one of required and desired.
Apparatus for clustering data of a data stream of electronic consumer transactions, the apparatus comprising:
- a memory;
- and
- at least one processor coupled to the memory and operative to:
- (i) receive at least one data point from the data stream;
- (ii) assign the at least one data point to one of a plurality of groups of data points;
- (iii) update and store online statistics of the one of the plurality of groups of data points, wherein the online statistics comprise lower-level clusters;
- (iv) determine whether offline processing is one of required and desired for analysis of the lower-level clusters;
- (v) perform offline processing of the online statistics through at least one re-clustering of the plurality of groups of similar data points around at least one sampled pseudo-point to create higher-level clusters, when offline processing is one of required and desired;
- (vi) utilize the online statistics to monitor data stream evolution by performing offline processing to subtract online statistics over specified horizons, and to determine evolution classification based on subtracted statistics;
- (vii) report the higher-level clusters of electronic consumer transactions for analysis by a user;
- and (viii) repeat the receiving, assigning, updating and determining steps, when offline processing is not one of required and desired.
An article of manufacture for clustering data of a data stream of electronic consumer transactions, comprising a machine readable medium containing one or more programs which when executed implement the steps of:
- receiving at least one data point from the data stream;
- assigning the at least one data point to one of a plurality of groups of data points;
- updating and storing online statistics of the one of the plurality of groups of data points wherein the online statistics comprise lower-level clusters;
- determining whether offline processing is one of required and desired for analysis of the lower-level clusters;
- performing offline processing of the online statistics through at least one re-clustering of the plurality of groups of data points around at least one sampled pseudo-point to create higher-level clusters, when offline processing is one of required and desired;
- utilizing the online statistics to monitor data stream evolution by performing offline processing to subtract online statistics over specified horizons, and to determine evolution classification based on subtracted statistics;
- reporting the higher-level clusters of electronic consumer transactions for analysis by a user;
- and
- repeating the receiving, assigning, updating and determining steps when offline processing is not one of required and desired.
Dependencies are inferred from the claim text.