Cụm hóa là phương pháp khai phá dữ liệu quan trọng cho khám phá tri thức. Cụm hóa là phương pháp phân tích dữ liệu khám phá phân loại nhiều đối tượng dữ liệu thành các nhóm giống nhau, gọi là cụm (clusters).
DENCLUE đại diện cho Density-based Clustering (Cụm hóa dựa trên mật độ). Đây là phương pháp cụm hóa dựa trên một nhóm hàm phân phối mật độ. Thuật toán DENCLUE sử dụng mô hình cụm dựa trên ước lượng mật độ hạt nhân (kernel density estimation). Một cụm được biểu diễn bởi một cực đại cục bộ của hàm mật độ dự đoán.
DENCLUE không hoạt động trên bản ghi với phân phối đồng đều. Trong không gian chiều cao, dữ liệu luôn trông như phân phối đồng đều do lời nguyền chiều. Do đó, DENCLUE không hoạt động tốt trên bản ghi chiều cao nói chung.
Phương pháp xây dựng trên các ý tưởng sau:
- Ảnh hưởng của mỗi điểm dữ liệu có thể được mô hình hóa chính thức bằng hàm toán học, gọi là hàm ảnh hưởng (influence function), mô tả tác động của điểm dữ liệu trong lân cận của nó.
- Mật độ hoàn chỉnh của không gian dữ liệu có thể được mô hình hóa giải tích như tổng của hàm ảnh hưởng áp dụng cho các điểm dữ liệu.
- Cụm có thể được xác định bằng số học bằng cách nhận diện các điểm hút mật độ (density attractors), nơi điểm hút mật độ là cực đại cục bộ của hàm mật độ hoàn chỉnh.
Cho x và y là đối tượng hoặc điểm trong f^d, không gian đầu vào d chiều. Hàm ảnh hưởng của đối tượng dữ liệu y lên x là hàm, f_B^y: f^d → R₀⁺, được định nghĩa qua hàm ảnh hưởng cơ bản f_B:
f_B^y(X) = f_B(X, Y)
Điều này phản ánh tác động của y lên x. Về nguyên tắc, hàm ảnh hưởng có thể là hàm tùy ý được xác định bởi khoảng cách giữa hai đối tượng trong lân cận. Hàm khoảng cách d(x, y) phải phản xạ và đối xứng, bao gồm hàm khoảng cách Euclidean.
Thường dùng để tính hàm ảnh hưởng sóng vuông:
f_square(X, Y) = 0 nếu d(x, y) > σ, ngược lại = 1
hoặc hàm ảnh hưởng Gaussian:
f_Gauss(x, y) = e^(-d(x, y)² / 2σ²)
Ưu điểm của DENCLUE
- Có nền tảng số học vững chắc và khái quát hóa nhiều phương pháp cụm hóa như phân vùng, phân cấp, và dựa trên mật độ.
- Có tính chất cụm hóa tốt cho tập dữ liệu với lượng lớn nhiễu.
- Cho phép mô tả số học compact của cụm hình dạng tùy ý trong tập thông tin chiều cao.
- Sử dụng ô lưới, nhưng chỉ giữ thông tin về ô lưới thực sự chứa điểm dữ liệu. Quản lý các ô trong cấu trúc truy cập dựa trên cây, do đó nhanh hơn đáng kể so với các thuật toán có ảnh hưởng như DBSCAN.
- Phương pháp này đòi hỏi lựa chọn cẩn thận tham số mật độ σ và ngưỡng nhiễu ξ, vì lựa chọn tham số có thể ảnh hưởng lớn chất lượng kết quả cụm hóa.