Methods and Apparatus for Clustering Evolving Data Streams Through Online and Offline Components

• US 20070226209A1
• Filed: 05/30/2007
• Published: 09/27/2007
• Est. Priority Date: 08/14/2003
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Aggarwal, Charu, Yu, Philip
• Application Number:
  US11/755,473
• Publication Number:
  US 20070226209A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

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.

Claims

1. A method of clustering data of a data stream comprising the steps of:

creating online statistics from the data stream in accordance with one or more groups of similar data points from the data stream, wherein the online statistics comprise lower-level clusters; and

performing offline processing of the online statistics through at least one re-clustering of the one or more 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.

2. The method of claim 1, further comprising the step of determining whether offline processing is one of required and desired.

3. The method of claim 1, wherein the step of creating online statistics comprises the steps of:

receiving a data point from the data stream; and

updating the online statistics from the data stream.

4. The method of claim 3, wherein the step of updating online statistics comprises the steps of:

finding a group of similar data points closest to the data point;

determining if a distance to the closest group is greater than a threshold;

creating a new group having the data point if the distance to the closest group is greater than the threshold;

adding the data point to the closest group if the distance to the closest group is less than the threshold; and

updating the statistics of the new group if created or closest group if the data point was added.

5. The method of claim 1, wherein the step of performing off-line processing comprises the steps of:

sampling a defined number of pseudo-points;

re-clustering the one or more groups of similar data points around the sampled pseudo-points;

determining if additional iterations of sampling and re-clustering are required;

redefining the sampled pseudo-points as centroids of the one or more re-clustered groups of data points if additional iterations are required, before re-clustering groups of data points around the redefined sampled pseudo-points; and

reporting clusters formed in the re-clustering.

6. The method of claim 1, wherein the step of performing off-line processing comprises the step of re-clustering lower level clusters.

7. The method of claim 1, wherein the step of performing offline processing comprises the step of utilizing the online statistics to monitor data stream evolution.

8. The method of claim 7, wherein the step of utilizing the online statistics to monitor data stream evolution comprises the step of comparing the online statistics at two different horizons.

9. The method of claim 7, wherein the step of utilizing the online statistics to monitor data stream evolution comprises the steps of:

subtracting online statistics over specified horizons; and

determining evolution classification based on subtracted statistics.

10. The method of claim 1, further comprising the step of storing online statistics at specific times depending upon a pyramidal distribution.

11. Apparatus for clustering data of data stream, the apparatus comprising:

a memory; and

at least one processor coupled to the memory and operative to;

(i) create online statistics from the data stream in accordance with one or more groups of similar data points from the data stream, wherein the online statistics comprise lower-level clusters; and

(ii) perform offline processing of the online statistics through at least one re-clustering of the one or more 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.

12. The apparatus of claim 11, wherein the at least one processor is further operative to determine whether offline processing is one of required and desired.

13. The apparatus of claim 11, wherein the operation of creating online statistics is operative to:

receive a data point from the data stream; and

update the online statistics from the data stream.

14. The apparatus of claim 13, wherein the operation of updating online statistics is operative to:

find a group of similar data points closest to the data point;

determine if a distance to the closest group is greater than a threshold;

create a new group having the data point if the distance to the closest group is greater than the threshold;

add the data point to the closest group if the distance to the closest group is less than the threshold; and

update the statistics of the new group if created or closest group if the data point was added.

15. The apparatus of claim 11, wherein the operation of performing off-line processing is operative to:

sample a defined number of pseudo-points;

re-cluster the one or more groups of similar data points around the sampled pseudo-points;

determine if additional iterations of sampling and re-clustering are required;

redefine the sampled pseudo-points as centroids of the one or more re-clustered groups of data points if additional iterations are required, before re-clustering groups of data points around the redefined sampled pseudo-points; and

report clusters formed in the re-clustering.

16. The apparatus of claim 11, wherein the operation of performing off-line processing is operative to re-cluster lower level clusters.

17. The apparatus of claim 11, wherein the operation of performing offline processing is operative to utilize the online statistics to monitor data stream evolution.

18. The apparatus of claim 17, wherein the operation of utilizing the online statistics to monitor data stream evolution is operative to compare the online statistics at two different horizons.

19. The apparatus of claim 17, wherein the operation of utilizing the online statistics to monitor data stream evolution is operative to:

subtract online statistics over specified horizons; and

determine evolution classification based on subtracted statistics.

20. The apparatus of claim 11, wherein the at least one processor is further operative to store online statistics at specific times depending upon a pyramidal distribution.

21. An article of manufacture for clustering data of a data stream, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

creating online statistics from the data stream in accordance with one or more groups of similar data points from the data stream, wherein the online statistics comprise lower-level clusters; and

performing offline processing of the online statistics through at least one re-clustering of the one or more 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.