Giới thiệu BIRCH
BIRCH (Balanced Iterative Reducing and Clustering Using Hierarchies) thiết kế cho phân cụm lượng lớn bản ghi số bằng cách tích hợp phân cụm phân cấp và các phương pháp khác (phân vùng lặp).
Hai khái niệm cốt lõi
- Clustering Feature (CF - Đặc trưng phân cụm)
- Clustering Feature Tree (CF Tree - Cây đặc trưng phân cụm)
Cấu trúc này giúp đạt tốc độ và khả năng mở rộng tốt nhất trên CSDL lớn, cũng hiệu quả cho phân cụm tăng dần (incremental) và động của đối tượng đến.
Biểu diễn cụm
Cho n đối tượng điểm d-chiều trong cụm, tâm (centroid) x₀, bán kính R, đường kính D:
- x₀ = (Σxᵢ) / n
- R = √(Σ(xᵢ - x₀)² / n) - khoảng cách trung bình từ phần tử đến tâm
- D = √(ΣΣ(xᵢ - xⱼ)² / n(n-1)) - khoảng cách cặp trung bình trong cụm
Cả R và D phản ánh độ chặt của cụm quanh tâm.
Clustering Feature (CF)
CF là vector 3 chiều tóm tắt dữ liệu về cụm đối tượng. Cho n đối tượng d-chiều {xᵢ} trong cụm:
CF = (n, LS, SS)
- n: số điểm trong cụm
- LS: tổng tuyến tính n điểm = Σxᵢ
- SS: tổng bình phương điểm dữ liệu = Σxᵢ²
CF là tóm tắt thống kê cho cụm: moment bậc 0, 1, 2. CF có tính cộng: nếu C1, C2 rời rạc với CF1, CF2 → CF(C1 ∪ C2) = CF1 + CF2.
CF Tree
Cây cân bằng chiều cao lưu trữ clustering features cho phân cụm phân cấp.
- Nút không phải lá: có con (children). Lưu tổng CF của con → tóm tắt thông tin phân cụm về con.
- Hai tham số: branching factor B (số con tối đa/nút không lá), threshold T (đường kính tối đa cụm con ở nút lá). Kiểm soát kích thước cây kết quả.