WaveCluster là một thuật toán phân cụm đa độ phân giải, trước tiên tóm tắt các bản ghi bằng cách áp dụng một kiến trúc lưới đa chiều lên không gian dữ liệu. Nó có thể sử dụng biến đổi wavelet để chuyển đổi không gian đặc trưng gốc, tìm các miền dày đặc trong không gian đã chuyển đổi.
Trong phương pháp này, mỗi ô lưới tóm tắt dữ liệu của một nhóm điểm được ánh xạ vào ô đó. Dữ liệu tóm tắt này thường phù hợp với bộ nhớ chính để sử dụng cho biến đổi wavelet đa độ phân giải và phân tích cụm tiếp theo.
Biến đổi wavelet là một phương pháp xử lý tín hiệu phân rã tín hiệu thành nhiều dải con tần số. Mô hình wavelet có thể áp dụng cho tín hiệu d chiều bằng cách sử dụng biến đổi wavelet một chiều d lần. Khi áp dụng biến đổi wavelet, dữ liệu được chuyển đổi để bảo toàn khoảng cách tương đối giữa các đối tượng ở nhiều mức độ phân giải. Điều này cho phép các cụm tự nhiên trong dữ liệu trở nên dễ phát hiện hơn. Các cụm có thể được nhận diện bằng cách tìm kiếm các vùng dày đặc trong miền mới.
Ưu điểm của biến đổi wavelet
Cung cấp phân cụm không giám sát – Sử dụng bộ lọc hình nón nhấn mạnh các vùng mà các điểm tập trung, đồng thời ức chế dữ liệu yếu hơn bên ngoài ranh giới cụm. Do đó, các vùng dày đặc trong không gian đặc trưng ban đầu đóng vai trò là lực hút cho các điểm liền kề và lực ức chế cho các điểm xa hơn. Điều này khiến các cụm trong dữ liệu tự động nổi bật và "làm sạch" các vùng xung quanh. Một lợi ích khác là biến đổi wavelet có thể tự động loại bỏ các giá trị ngoại lai.
Đặc tính đa độ phân giải của biến đổi wavelet hỗ trợ phát hiện cụm ở nhiều mức độ chính xác.
Phân cụm dựa trên wavelet rất nhanh, với độ phức tạp tính toán O(n), trong đó n là số đối tượng trong cơ sở dữ liệu. Triển khai thuật toán có thể được song song hóa.
WaveCluster là thuật toán dựa trên lưới và mật độ – Nó đáp ứng nhiều yêu cầu của một thuật toán phân cụm tốt: xử lý hiệu quả tập dữ liệu lớn, tìm cụm với hình dạng tùy ý, xử lý thành công các giá trị ngoại lai, không nhạy cảm với thứ tự đầu vào, và không cần định nghĩa các tham số đầu vào như số cụm hoặc bán kính lân cận.
Trong các nghiên cứu sơ bộ, WaveCluster được phát hiện vượt trội hơn BIRCH, CLARANS và DBSCAN về cả hiệu quả và chất lượng phân cụm. Nghiên cứu cũng cho thấy WaveCluster có khả năng xử lý dữ liệu lên đến 20 chiều.