CluStream là một thuật toán để phân nhóm các luồng dữ liệu đang phát triển dựa trên các truy vấn phân nhóm trực tuyến, do người dùng chỉ định. Nó chia quá trình phân cụm thành các thành phần trực tuyến và ngoại tuyến.
Thành phần trực tuyến tính toán và lưu trữ thống kê tóm tắt về dòng dữ liệu bằng cách sử dụng các cụm vi mô và thực hiện tính toán trực tuyến gia tăng và bảo trì các cụm vi mô. Thành phần ngoại tuyến thực hiện phân nhóm macro và trả lời các câu hỏi khác nhau của người dùng bằng cách sử dụng thống kê tóm tắt được lưu trữ, dựa trên mô hình khung thời gian nghiêng.
Cụm luồng dữ liệu phát triển dựa trên cả thông tin dữ liệu luồng lịch sử và luồng hiện tại, mô hình khung thời gian nghiêng (chẳng hạn như mô hình lôgarit lũy tiến), lưu trữ ảnh chụp nhanh của một nhóm vi mô ở các mức độ phổ biến khác nhau tùy thuộc về lần truy cập gần đây.
Trực giác ở đây là sẽ cần nhiều thông tin hơn cho các sự kiện gần đây hơn là các sự kiện cũ hơn. Thông tin được lưu trữ có thể được sử dụng để xử lý các truy vấn phân cụm liên quan đến lịch sử, dành cho người dùng cụ thể. Một microcluster trong CluStream được định nghĩa là một tính năng phân cụm.
CluStream mở rộng khái niệm về tính năng phân cụm được phát triển trong BIRCH để bao gồm miền thời gian. Là một phần mở rộng tạm thời của tính năng phân cụm, amicrocluster cho một tập hợp các điểm d-chiều, X 1 ,. . . , X n , với dấu thời gian, T 1 , ..., T n , được định nghĩa là bộ (2d +3) (CF2 x , CF1 x , CF2 t , CF1 t , n), trong đó CF2 x và CF1 x là vectơ d-chiều trong khi CF2 t , CF1 t , và n là vô hướng. CF2 x duy trì tổng bình phương của các giá trị dữ liệu trên mỗi thứ nguyên, nghĩa là $ \ sum_ {i =1} ^ {n} {X_ {i}} ^ {2} $
Tương tự, đối với mỗi thứ nguyên, tổng giá trị dữ liệu được duy trì trong CF1 x . Từ quan điểm thống kê, CF2 x và CF1 x đại diện cho các khoảnh khắc bậc hai và bậc nhất của dữ liệu, tương ứng. Tổng các bình phương của dấu thời gian được duy trì trong CF2 t . Tổng các dấu thời gian được duy trì trong CF1 t . Cuối cùng, số lượng điểm dữ liệu trong microcluster được duy trì trong n.
Các tính năng phân cụm có các thuộc tính cộng và trừ khiến chúng rất hữu ích cho việc phân tích cụm luồng dữ liệu. Ví dụ, có thể gộp hai nhóm vi mô bằng cách thêm các tính năng phân nhóm tương ứng của chúng. Hơn nữa, một số lượng lớn vi cụm có thể được duy trì mà không cần sử dụng nhiều bộ nhớ. Ảnh chụp nhanh nếu các cụm vi mô này được lưu trữ tại các thời điểm quan trọng dựa trên khung thời gian nghiêng.
Xử lý vi cụm trực tuyến được chia thành hai giai đoạn như thu thập dữ liệu thống kê và cập nhật các vi cụm. Trong giai đoạn đầu, tổng số q vi cụm, M 1 , ..., M q , được duy trì, trong đó q thường lớn hơn đáng kể so với số cụm tự nhiên và được xác định bởi lượng bộ nhớ khả dụng.
Trong giai đoạn thứ hai, các vi cụm được cập nhật. Mỗi điểm dữ liệu mới được thêm vào một cụm hiện có hoặc một điểm mới. Nó có thể quyết định xem một cụm mới có được yêu cầu hay không, ranh giới tối đa cho mỗi cụm được xác định.