CURE là viết tắt của Clustering Using Representative (Phân cụm sử dụng đại diện). Đây là thuật toán phân cụm sử dụng nhiều kỹ thuật để tạo phương pháp có thể xử lý tập dữ liệu lớn, ngoại lai, và cụm với kiến trúc không cầu hình và kích thước không đồng đều. CURE định nghĩa một cụm bằng cách sử dụng nhiều điểm đại diện từ cụm.
Các điểm này sẽ nắm bắt hình học và kiến trúc của cụm. Điểm đại diện đầu tiên được chọn là điểm xa nhất từ tâm cụm, trong khi các điểm còn lại được chọn sao cho chúng xa nhất từ tất cả các điểm đã chọn trước đó. Theo cách này, các điểm đại diện được phân bố tương đối tốt. Số điểm được chọn là một tham số, nhưng đã phát hiện giá trị 10 hoặc hơn hoạt động tốt.
Vì các điểm đại diện được chọn, chúng được thu hẹp về phía tâm bằng một hệ số, α. Điều này giúp giảm thiểu tác động của ngoại lai, thường xa tâm hơn và do đó, bị thu hẹp nhiều hơn. Ví dụ, một điểm đại diện ở khoảng cách 10 đơn vị từ tâm có thể thay đổi 3 đơn vị (với α = 0.7), trong khi điểm đại diện ở khoảng cách 1 đơn vị chỉ thay đổi 0.3 đơn vị.
CURE tận dụng các đặc điểm cụ thể của quy trình phân cụm phân cấp để loại bỏ ngoại lai tại hai điểm khác nhau trong giai đoạn phân cụm. Thứ nhất, nếu một cụm tăng trưởng chậm, thì điều này có thể có nghĩa là nó chủ yếu bao gồm ngoại lai, vì bởi định nghĩa, ngoại lai xa các điểm khác và sẽ không được kết hợp với các điểm khác thường xuyên. Trong CURE, quy trình loại bỏ ngoại lai đầu tiên thường xuất hiện khi số cụm là 1/3 số điểm ban đầu. Quy trình loại bỏ ngoại lai thứ hai xuất hiện khi số cụmอยู่ trên cấp độ K, số cụm mong muốn. Lúc này, các cụm nhỏ bị loại bỏ.
Vì độ phức tạp trường hợp xấu nhất của CURE là O(m²log m), nó không thể được dùng chính xác cho tập dữ liệu lớn. CURE sử dụng hai phương pháp để tăng tốc quy trình phân cụm. Phương pháp đầu tiên lấy mẫu ngẫu nhiên và thực hiện phân cụm phân cấp trên các điểm dữ liệu được lấy mẫu. Điều này được theo sau bởi một lượt cuối gán mỗi điểm còn lại trong tập dữ liệu vào một trong các cụm bằng cách chọn cụm có điểm đại diện gần nhất.
Trong một số trường hợp, mẫu cần cho phân cụm lớn và một kỹ thuật thứ hai hơn được cần. Trong tình huống này, CURE phân hoạch dữ liệu mẫu và phân cụm các điểm trong mỗi phân hoạch. Quy trình tiền phân cụm này được theo sau bởi phân cụm các cụm trung gian và một lượt cuối gán mỗi điểm trong tập dữ liệu vào một trong các cụm.