CLIQUE là thuật toán đầu tiên được đề xuất cho cụm hóa subspace tăng chiều (dimension-growing subspace clustering) trong không gian chiều cao. Trong cụm hóa subspace tăng chiều, quy trình cụm hóa bắt đầu ở subspace đơn chiều và mở rộng lên các chiều cao hơn.
Vì CLIQUE phân vùng mỗi chiều như cấu trúc lưới và quyết định ô có đậm đặc dựa trên số điểm nó chứa. Nó có thể được xem như tích hợp của phương pháp cụm hóa dựa trên mật độ và dựa trên lưới.
Ý tưởng của thuật toán cụm hóa CLIQUE:
- Cho tập lớn điểm dữ liệu đa chiều, không gian dữ liệu thường không được chiếm dụng đồng đều bởi điểm dữ liệu. Cụm hóa CLIQUE nhận diện vùng thưa và "chật chội" trong không gian (hoặc đơn vị), từ đó tìm mẫu phân phối hoàn chỉnh của tập dữ liệu.
- Một đơn vị là đậm đặc nếu phân số tổng điểm dữ liệu chứa trong nó vượt quá tham số mô hình đầu vào. Trong CLIQUE, một cụm được biểu diễn như nhóm tối đa các đơn vị đậm đặc liên kết.
CLIQUE thực hiện cụm hóa đa chiều trong hai quy trình:
Quy trình đầu tiên, CLIQUE phân vùng không gian dữ liệu d chiều thành các đơn vị hình chữ nhật không chồng chéo, nhận diện đơn vị đậm đặc giữa chúng. Điều này hoàn thành (trong 1-D) cho mỗi chiều.
Việc xác định không gian tìm kiếm ứng viên phụ thuộc vào tính chất Apriori dùng trong khai phá luật liên kết. Nói chung, tính chất dùng kiến thức trước của mục trong không gian tìm kiếm để các phần không gian có thể cắt giảm.
Tính chất cho CLIQUE: Nếu đơn vị k chiều đậm đặc, thì các chiếu của nó trong không gian (k−1) chiều cũng đậm đặc. Tức là, cho đơn vị đậm đặc ứng viên k chiều, nếu kiểm tra đơn vị chiếu (k−1) và tìm một số không đậm đặc, thì biết đơn vị k chiều không thể đậm đặc.
Do đó, có thể tạo đơn vị đậm đặc ứng viên trong không gian k chiều từ đơn vị đậm đặc tìm thấy trong không gian (k−1) chiều. Nói chung, không gian tìm kiếm kết quả nhỏ hơn nhiều không gian gốc. Các đơn vị đậm đặc được kiểm tra để quyết định cụm.
Trong quy trình thứ hai, CLIQUE tạo mô tả tối thiểu cho mỗi cụm như sau. Với mỗi cụm, quyết định vùng tối đa bao phủ cụm đơn vị đậm đặc liên kết. Quyết định bao phủ tối thiểu (mô tả logic) cho mỗi cụm.
CLIQUE bắt buộc khám phá subspace chiều lớn nhất bao gồm cụm mật độ cao tồn tại trong những subspace. Nó không nhạy cảm với thứ tự đối tượng đầu vào và không giả định phân phối dữ liệu kinh điển. Nó mở rộng tuyến tính với kích thước đầu vào và có khả năng mở rộng tốt nhất khi số chiều dữ liệu tăng.