Phân tích cụm (Cluster analysis) được dùng để hình thành các nhóm hoặc cụm của các bản ghi giống nhau tùy thuộc trên các đo lường khác nhau được làm trên các bản ghi này. Có thể xác định các cụm theo những cách có thể hữu ích cho mục đích của phân tích. Dữ liệu này đã được dùng trong nhiều lĩnh vực, như thiên văn học (astronomy), khảo cổ học (archaeology), y học (medicine), hóa học (chemistry), giáo dục (education), tâm理学 (psychology), ngôn ngữ học (linguistics), và xã hội học (sociology).
Có nhiều loại cụm như sau:
Tách biệt tốt (Well-Separated)
Một cụm là nhóm đối tượng trong đó mỗi phần tử gần hơn đến mọi phần tử khác trong cụm hơn đến bất kỳ đối tượng nào không trong cụm. Đôi khi ngưỡng có thể xác định rằng tất cả đối tượng trong một cụm nên đủ gần (hoặc tương tự) với nhau. Mô tả cụm này chỉ cần thiết khi dữ liệu bao gồm các cụm tự nhiên hoàn toàn xa nhau.
Dựa trên nguyên mẫu (Prototype-Based)
Một cụm là nhóm đối tượng trong đó mỗi đối tượng gần hơn đến nguyên mẫu (prototype) đại diện cho cụm hơn đến nguyên mẫu của bất kỳ cụm nào khác. Đối với dữ liệu với thuộc tính liên tục, nguyên mẫu của một cụm là centroid như trung bình (mean) của các điểm trong cụm. Khi centroid không có ý nghĩa, bao gồm khi bản ghi có thuộc tính categorical, nguyên mẫu là medoid như điểm đại diện của cụm.
Dựa trên đồ thị (Graph-Based)
Nếu dữ liệu điển hình như một đồ thị, nơi nút là đối tượng và liên kết xác định kết nối giữa đối tượng thì một cụm có thể được biểu diễn như một thành phần kết nối (connected component); tức là, một tập đối tượng được liên kết với nhau, nhưng không có kết nối với đối tượng xa hơn nhóm.
Các ví dụ quan trọng của cụm dựa trên đồ thị là cụm dựa trên sự liền kề (contiguity-based clusters), nơi hai đối tượng chỉ được liên kết nếu chúng nằm trong một khoảng cách xác định của nhau. Điều này chỉ ra rằng mỗi đối tượng trong cụm dựa trên sự liền kề gần hơn đến nhiều đối tượng trong cụm hơn đến bất kỳ điểm nào trong cụm khác.
Phương pháp dựa trên mật độ (Density-based Methods)
Một số kỹ thuật phân hoạch cụm đối tượng tùy thuộc trên khoảng cách giữa đối tượng. Những cách tiếp cận như vậy chỉ có thể khám phá cụm hình cầu (spherical-shaped clusters) và gặp khó khăn trong khám phá cụm hình dạng tùy ý (arbitrary shapes). Có nhiều phương pháp phân cụm được tạo ra dựa trên khái niệm mật độ (density).
DBSCAN là một phương pháp dựa trên mật độ thường xuyên mở rộng cụm theo ngưỡng mật độ. OPTICS là phương pháp dựa trên mật độ tính toán thứ tự phân cụm mở rộng (augmented clustering ordering) cho phân cụm tự động và tương hỗ (mutual cluster analysis).
Phương pháp dựa trên lưới (Grid-based Methods)
Phương pháp dựa trên lưới (Grid-based methods) lượng tử hóa (quantize) không gian đối tượng thành số hữu hạn ô (cells) tạo thành cấu trúc lưới. Một số dịch vụ phân cụm được triển khai trên cấu trúc lưới (tức là, trên không gian lượng tử hóa).
Lợi thế của cách tiếp cận này là thời gian xử lý nhanh chóng thường độc lập với số lượng đối tượng dữ liệu và chỉ dựa trên số ô trong mỗi chiều trong không gian lượng tử hóa.