Giới thiệu CluStream
CluStream là thuật toán phân cụm luồng dữ liệu tiến hóa dựa trên truy vấn phân cụm trực tuyến (online) do người dùng chỉ định. Nó chia quy trình phân cụm thành 2 thành phần: online và offline.
Hai thành phần chính
- Thành phần Online: Tính toán và lưu trữ thống kê tóm tắt về luồng dữ liệu sử dụng micro-clusters (cụm vi), thực hiện tính toán và bảo trì micro-clusters tăng dần (incremental).
- Thành phần Offline: Thực hiện macro-clustering (phân cụm vĩ mô) và trả lời các câu hỏi người dùng dùng thống kê tóm tắt đã lưu, dựa trên mô hình khung thời gian nghiêng (tilted time frame model).
Mô hình khung thời gian nghiêng (Tilted Time Frame)
Để phân cụm luồng dữ liệu dựa trên cả dữ liệu lịch sử và hiện tại, mô hình khung thời gian nghiêng (ví dụ: mô hình log tiến trình) được áp dụng, lưu trữ snapshot của tập micro-clusters ở các mức độ chi tiết (granularity) khác nhau tùy theo độ gần đây. Trực giác: cần nhiều thông tin hơn cho sự kiện gần đây hơn sự kiện cũ.
Micro-cluster trong CluStream
Micro-cluster được định nghĩa là đặc trưng phân cụm (clustering feature). CluStream mở rộng khái niệm clustering feature của BIRCH để bao gồm miền thời gian (temporal domain).
Micro-cluster cho tập hợp điểm d-chiều X₁,...,Xₙ với dấu thời gian T₁,...,Tₙ được định nghĩa là tuple (2d+3): (CF2ˣ, CF1ˣ, CF2ᵗ, CF1ᵗ, n), trong đó:
- CF2ˣ, CF1ˣ là vector d-chiều; CF2ᵗ, CF1ᵗ, n là vô hướng (scalars).
- CF2ˣ lưu tổng bình phương giá trị dữ liệu mỗi chiều: ΣXᵢ².
- CF1ˣ lưu tổng giá trị dữ liệu mỗi chiều: ΣXᵢ.
- CF2ᵗ lưu tổng bình phương dấu thời gian: ΣTᵢ².
- CF1ᵗ lưu tổng dấu thời gian: ΣTᵢ.
- n lưu số điểm dữ liệu trong micro-cluster.
Từ góc độ thống kê: CF2ˣ và CF1ˣ đại diện cho moment bậc 2 và bậc 1 của dữ liệu. Đặc trưng phân cụm có tính cộng và trừ → rất hữu ích cho phân cụm luồng dữ liệu. Hai micro-cluster có thể gộp bằng cách cộng đặc trưng. Có thể duy trì nhiều micro-cluster mà không tốn nhiều bộ nhớ. Snapshot lưu ở các thời điểm then chốt dựa trên tilted time frame.
Xử lý micro-cluster Online - 2 giai đoạn
- Thu thập dữ liệu thống kê: Duy trì q micro-clusters M₁,...,M_q (q lớn hơn số cụm tự nhiên nhiều, quyết định bởi bộ nhớ khả dụng).
- Cập nhật micro-clusters: Mỗi điểm dữ liệu mới thêm vào cụm hiện có hoặc tạo cụm mới. Quyết định cần cụm mới bằng cách định nghĩa ranh giới tối đa cho mỗi cụm.