Các phương pháp phân nhóm dựa trên lưới sử dụng cấu trúc dữ liệu lưới đa độ phân giải. Nó lượng tử hóa các vùng đối tượng thành một số lượng hữu hạn các ô tạo thành cấu trúc lưới mà trên đó tất cả các hoạt động phân cụm được thực hiện. Lợi ích của phương pháp này là thời gian xử lý nhanh chóng, thường không phụ thuộc vào số lượng đối tượng dữ liệu, vẫn chỉ phụ thuộc vào nhiều ô trong mỗi chiều trong không gian lượng tử hóa.
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 và sử dụng các ô lưới dày đặc để tạo thành các cụm. Có một số phương pháp thú vị là STING, wave cluster và CLIQUE.
STING - Phương pháp tiếp cận lưới thông tin thống kê. Khu vực không gian được chia thành các ô 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 ô ở mức cao được tách thành nhiều ô nhỏ hơn ở mức thấp hơn tiếp theo. 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 các truy vấn. Đặc điểm kỹ thuật của các ô cấp cao hơn có thể được tính đơn giản từ đặc điểm kỹ thuật của các ô cấp thấp hơn:
- đếm, trung bình, s, tối thiểu, tối đa
- kiểu phân phối-bình thường, đồng nhất, v.v.
Phương pháp tiếp cận dựa trên lưới thông tin thống kê (STING) tuân theo phương pháp phân cấp để chia khu vực không gian thành các ô hình chữ nhật tương tự như một quadtree. Cơ sở dữ liệu không gian được quét một lần và các tham số thống kê được xác định cho từng ô. Kỹ thuật STING có thể được xem như một kiểu tiếp cận theo thứ bậc. Bước đầu tiên là tạo mô tả phân cấp. Cây được tạo chia riêng khu vực thành các góc phần tư.
Quá trình tạo cây được trình bày trong thuật toán dưới đây. Mỗi ô trong không gian tương ứng với một nút trong cây và được mô tả bằng cả dữ liệu phụ thuộc thuộc tính (số lượng) và dữ liệu phụ thuộc thuộc tính (trung bình, độ lệch chuẩn, phân phối tối thiểu, tối đa). Vì số nút trong cây ít hơn số mục trong cơ sở dữ liệu, nên độ phức tạp của STING BUILD là O (n).
Thuật toán
Đầu vào
D // Data to be placed in the hierarchical structure k // Number of desired cells at the lowest level
Đầu ra
T // Tree STING BUILD algorithm // Create an empty tree from top-down T = root node with data values initialized; // Initially only root node i = 1; repeat for each node in level i do create 4 children nodes with initial values; i = i +1; until 4i = k; // Populate tree from bottom-up for each item in D do determine leaf node j related to the position of D; update values of j based on attribute values in item; i := log4(k); repeat i: = i - 1; for each node j in level i do update values of j based on attribute values in its 4 children; until i = 1;