CluStream คืออะไร?

CluStream เป็น Algorithm สำหรับ Clustering ของ Evolving Data Streams บน User-specified Online Clustering Queries แบ่ง Clustering Process เป็น Online และ Offline Components

Online Component คำนวณและจัดเก็บ Summary Statistics เกี่ยวกับ Data Stream ใช้ Micro-clusters และ Perform Incremental Online Computation และ Maintenance ของ Micro-clusters Offline Component ทำ Macro-clustering และตอบ User Questions ต่างๆ ใช้ Stored Summary Statistics ที่ Based on Tilted Time Frame Model

เพื่อ Cluster Evolving Data Streams บน Historical และ Current Stream Data Information Tilted Time Frame Model (เช่น Progressive Logarithmic Model) ถูก Adopt ซึ่ง Store Snapshots ของ Set of Microclusters ที่ Different Levels of Granularity ขึ้นอยู่กับ Recency

Intuition คือ More Information จะต้องการสำหรับ More Recent Events เทียบกับ Older Events Stored Information ใช้สำหรับ Processing History-related User-specific Clustering Queries Microcluster ใน CluStream ถูก Defined เป็น Clustering Feature

CluStream Extend Concept ของ Clustering Feature ที่ Developed ใน BIRCH ให้รวม Temporal Domain ด้วย โดยเป็น Temporal Extension ของ Clustering Feature Microcluster สำหรับ Set of d-dimensional Points X₁, ..., X_n ด้วย Timestamps T₁,...,T_n ถูก Define เป็น (2d + 3) Tuple (CF2^x, CF1^x, CF2^t, CF1^t, n) โดย CF2^x และ CF1^x เป็น d-dimensional Vectors ในขณะที่ CF2^t, CF1^t, n เป็น Scalars CF2^x Maintain Sum of Squares ของ Data Values ต่อ Dimension คือ Σ X_i²

Similarly สำหรับแต่ละ Dimension Sum ของ Data Values Maintain ใน CF1^x จากมุมมอง Statistical CF2^x และ CF1^x Represent Second- และ First-order Moments ของ Data ตามลำดับ Sum of Squares ของ Timestamps Maintain ใน CF2^t Sum ของ Timestamps Maintain ใน CF1^t สุดท้าย Number of Data Points ใน Microcluster Maintain ใน n

Clustering Features มี Additive และ Subtractive Properties ทำให้ Very Useful สำหรับ Data Stream Cluster Analysis ตัวอย่าง: 2 Microclusters สามารถ Merge ได้โดย Add Respective Clustering Features อีกทั้ง Large Number ของ Microclusters สามารถ Maintain ได้โดยไม่ใช้ Memory มาก Snapshots ของ Microclusters ถูก Stored Away ที่ Key Points in Time ตาม Tilted Time Frame

Online Microcluster Processing แบ่งเป็น 2 Phases: Statistical Data Collection และ Updating of Microclusters ใน Phase แรก Total ของ q Microclusters M₁,..., M_q Maintained โดย q มัก Significantly Larger Than Natural Clusters และ Determined by Available Memory

ใน Phase ที่สอง Microclusters Updated แต่ละ New Data Point ถูก Add เข้า Existing Cluster หรือ New One สามารถ Decide ว่า New Cluster จำเป็นหรือไม่ Maximum Boundary สำหรับแต่ละ Cluster ถูก Defined