Phương pháp phân cụm dựa trên lưới sử dụng cấu trúc dữ liệu lưới đa độ phân giải (multi-resolution). Nó lượng tử hóa không gian đối tượng thành số hữu hạn ô tạo thành cấu trúc lưới mà trên đó tất cả các phép toán cho phân cụm được thực hiện. Lợi ích của phương pháp là thời gian xử lý nhanh, thường độc lập với số đối tượng dữ liệu, chỉ phụ thuộc vào số ô trong mỗi chiều trong không gian lượng tử hóa.
Phân cụm dựa trên lưới dùng cấu trúc dữ liệu lưới đa độ phân giải và dùng ô lưới dày đặc để hình thành cụm. Có một số phương pháp thú vị là STING, wave cluster, và CLIQUE.
STING – Phương pháp lưới thông tin thống kê (Statistical Information Grid). Không gian không gian được chia thành ô hình chữ nhật. Có nhiều cấp độ ô tương ứng với các phương pháp độ phân giải khác nhau. Mỗi ô ở cấp cao được chia thành nhiều ô nhỏ hơn ở cấp thấp hơn. Dữ liệu thống kê của mỗi ô được tính toán và lưu trữ trước và có thể trả lời truy vấn. Đặc tả ô cấp cao có thể dễ dàng tính từ đặc tả ô cấp thấp:
- count, mean, s, min, max
- loại phân phối - chuẩn, đều, v.v.
Phương pháp lưới thông tin thống kê (STING) tuân theo phương pháp phân cấp để chia không gian không gian thành ô hình chữ nhật tương tự quadtree. Cơ sở dữ liệu không gian được quét một lần, và tham số thống kê được xác định cho mỗi ô. Kỹ thuật STING có thể được xem như một loại phương pháp phân cấp. Bước đầu là tạo mô tả phân cấp. Cây được tạo riêng biệt chia vùng thành tứ phần.
Quy trình tạo cây được hiển thị trong thuật toán cho trước. Mỗi ô trong không gian tương ứng với nút trong cây và được mô tả với cả dữ liệu độc lập thuộc tính (count) và phụ thuộc thuộc tính (mean, độ lệch chuẩn, minimum, maximum phân phối). Vì số nút trong cây nhỏ hơn số mục trong cơ sở dữ liệu, độ phức tạp STING BUILD là O(n).
Thuật toán
Đầu vào (Input)
D // Dữ liệu được đặt trong cấu trúc phân cấp k // Số ô mong muốn ở cấp thấp nhất
Đầu ra (Output)
T // Cây STING BUILD algorithm // Tạo cây rỗng từ top-down T = root node với giá trị dữ liệu khởi tạo; // Ban đầu chỉ root node i = 1; lặp lại cho mỗi nút ở cấp i làm tạo 4 nút con với giá trị khởi tạo; i = i +1; cho đến khi 4i = k; // Điền cây từ bottom-up cho mỗi mục trong D làm xác định nút lá j liên quan đến vị trí của D; cập nhật giá trị của j dựa trên giá trị thuộc tính trong mục; i := log4(k); lặp lại i: = i - 1; cho mỗi nút j ở cấp i làm cập nhật giá trị của j dựa trên giá trị thuộc tính trong 4 nút con của nó; cho đến khi i = 1;