Một lưới là phương pháp hiệu quả để tổ chức một tập dữ liệu, tối thiểu ở số chiều thấp. Ý tưởng là chia các giá trị áp dụng của mỗi thuộc tính thành một số khoảng liên tiếp, tạo thành một tập hợp các ô lưới. Mỗi đối tượng rơi vào một ô lưới mà các khoảng thuộc tính tương ứng chứa giá trị của đối tượng.
Các đối tượng có thể được gán cho ô lưới trong một lượt duyệt qua bản ghi, và thông tin về mỗi ô, bao gồm số điểm trong ô, cũng có thể được thu thập đồng thời.
Có nhiều cách để thực hiện phân cụm sử dụng lưới, nhưng hầu hết các phương pháp dựa trên mật độ. Thuật toán phân cụm dựa trên lưới như sau:
Định nghĩa một tập hợp ô lưới.
Gán đối tượng cho các ô thích hợp và tính mật độ của mỗi ô.
Loại bỏ các ô có mật độ dưới ngưỡng xác định, r.
Hình thành cụm từ tập hợp các ô dày đặc liền kề.
Định nghĩa ô lưới (Defining grid cells) – Đây là bước cơ bản trong quy trình, nhưng cũng là bước tối thiểu rõ ràng, vì có nhiều cách chia các giá trị có thể của mỗi thuộc tính thành một số khoảng liên tiếp. Đối với thuộc tính liên tục, một cách là chia giá trị thành các khoảng cùng độ rộng. Nếu phương pháp này dùng cho mỗi thuộc tính, do đó các ô lưới kết quả đều có cùng thể tích, và mật độ của ô đơn giản được định nghĩa là số điểm trong ô.
Mật độ của ô lưới (The Density of Grid Cells) – Có thể định nghĩa mật độ ô lưới là số điểm chia cho thể tích vùng. Nói cách khác, mật độ là số điểm trên đơn vị diện tích, bất kể chiều của vùng đó.
Hình thành cụm từ các ô lưới dày đặc (Forming Clusters from Dense Grid Cells) – Hình thành cụm từ tập hợp liền kề các ô dày đặc tương đối dễ dàng. Có một số vấn đề như cần định nghĩa gì là ô liền kề. Phương pháp phân cụm có một số nhược điểm có thể được giải quyết bằng cách làm thuật toán hơi tinh vi hơn. Ví dụ, có thể có các ô một phần rỗng trên ranh giới của cụm.
Có thể cải tiến phân cụm dựa trên lưới cơ bản bằng cách sử dụng nhiều hơn dữ liệu mật độ. Trong một số trường hợp, bản ghi có cả thuộc tính không gian và phi không gian. Nói cách khác, có nhiều thuộc tính định nghĩa vị trí đối tượng trong thời gian hoặc không gian, trong khi các thuộc tính khác định nghĩa các khía cạnh khác của đối tượng.
Một ví dụ là nhà, có cả vị trí và nhiều đặc điểm, bao gồm giá hoặc diện tích sàn tính bằng feet vuông. Do tự tương quan không gian (hoặc thời gian), các đối tượng trong một ô cụ thể có giá trị giống nhau cho các thuộc tính khác của chúng.