Computer >> Hướng Dẫn Máy Tính >  >> Lập Trình >> Lập Trình

Phương pháp dựa trên lưới (Grid-based Methods) trong phân cụm

Khái niệm

Phương pháp phân cụm dựa trên lưới (grid-based clustering) sử dụng cấu trúc dữ liệu lưới đa độ phân giải (multi-resolution grid data structure). Nó lượng tử hóa không gian đối tượng thành số hữu hạn các ô tạo thành cấu trúc lưới, trên đó tất cả các phép toán phân cụm được thực hiện.

Ưu điểm chính

Thời gian xử lý nhanh, thường độc lập với số lượng đối tượng dữ liệu, chỉ phụ thuộc vào số ô trong mỗi chiều của không gian lượng tử hóa.

Các thuật toán điển hình

  • STING (STatistical INformation Grid): Khám phá dữ liệu thống kê lưu trữ trong ô lưới.
  • WaveCluster: Phân cụm đối tượng sử dụng phương pháp biến đổi sóng (wavelet transform).
  • CLIQUE: Phương pháp kết hợp lưới và mật độ (grid-and density-based) cho phân cụm không gian dữ liệu chiều cao.

Chi tiết STING - Phân cụm đa độ phân giải dựa trên lưới

STING chia không gian gian thành các ô hình chữ nhật. Có nhiều cấp độ ô hình chữ nhật tương ứng với nhiều mức độ phân giải, các ô này tạo thành cấu trúc phân cấp: mỗi ô ở cấp cao được phân chia thành nhiều ô ở cấp thấp hơn.

Tham số thống kê được tính trước và lưu trữ cho mỗi ô lưới:

  • Tham số độc lập thuộc tính: count (số lượng điểm).
  • Tham số phụ thuộc thuộc tính: mean (trung bình), stdev (độ lệch chuẩn), min (tối thiểu), max (tối đa).
  • Loại phân phối giá trị thuộc tính trong ô: normal (chuẩn), uniform (đều), exponential (mũ), hoặc none (nếu phân phối không xác định).

Tính toán tham số:

  • Khi dữ liệu nạp vào CSDL: tham số count, mean, stdev, min, max của ô cấp thấp nhất tính trực tiếp từ dữ liệu.
  • Loại phân phối: gán bởi người dùng nếu biết trước hoặc đạt được qua kiểm định giả thuyết (ví dụ kiểm định χ²).
  • Phân phối cấp cao: tính dựa trên phân phối chiếm đa số của các ô cấp thấp tương ứng kết hợp thủ tục lọc ngưỡng. Nếu phân phối ô cấp thấp không đồng ý và không vượt ngưỡng, loại phân phối cấp cao đặt là none.

Ứng dụng trong truy vấn top-down:

  1. Xác định lớp trong cấu trúc phân cấp để bắt đầu thủ tục trả lời truy vấn (thường có số ô nhỏ).
  2. Với mỗi ô trong lớp hiện tại, tính khoảng tin cậy (hoặc phạm vi xác suất ước lượng) phản ánh độ liên quan của ô đến truy vấn cho trước.