CURE đại diện cho đại diện sử dụng phân cụm. Đây là một thuật toán phân cụm sử dụng nhiều kỹ thuật để tạo ra một cách tiếp cận có thể quản lý các tập dữ liệu cao, các giá trị ngoại lai và các cụm có kiến trúc phi hình cầu và kích thước không đồng nhất. CURE xác định một cụm bằng cách sử dụng một số điểm đại diện từ cụm.
Các điểm này sẽ lấy 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ừ giữa cụm, trong khi các điểm còn lại được chọn sao cho chúng xa nhất so với tất cả các điểm đã chọn trước đó. Trong phương pháp này, các điểm đại diện được phân bổ tương đối tốt. Nhiều điểm được chọn là một tham số, nhưng người ta phát hiện ra rằng giá trị từ 10 trở lên hoạt động tốt.
Bởi vì các điểm đại diện được chọn, chúng bị giảm về phía trung tâm một hệ số, 𝛼. Sự hỗ trợ này kiểm soát ảnh hưởng của các vùng ngoại lai, thường nằm xa trung tâm hơn và do đó, bị thu hẹp nhiều hơn. Ví dụ:điểm đại diện cách tâm 10 đơn vị có thể thay đổi 3 đơn vị (đối với 𝛼 =0,7), trong khi điểm đại diện cách tâm 1 đơn vị có thể thay đổi 0,3 đơn vị.
CURE tận dụng lợi ích của các đặc điểm cụ thể của quá trình phân cụm phân cấp để loại bỏ các ngoại lệ tại hai điểm trong giai đoạn phân nhóm. Đầu tiên, nếu một cụm đang tăng chậm, thì điều này có thể có nghĩa là nó bao gồm hầu hết các điểm ngoại lệ, bởi vì theo định nghĩa, các điểm ngoại lệ khác xa những điểm khác và sẽ không thường xuyên được kết hợp với các điểm khác nhau.
Trong CURE, quy trình loại bỏ ngoại lệ đầu tiên này thường xuất hiện khi số lượng cụm bằng 1/3 số điểm ban đầu. Thủ tục thứ hai để loại bỏ ngoại lệ xuất hiện khi nhiều cụm theo thứ tự của K, nhiều cụm mong muốn. Tại thời điểm này, các cụm nhỏ bị loại bỏ.
Vì độ phức tạp trong trường hợp xấu nhất của CURE là $ \ mathrm {O (m ^ 2logm)} $, nó không thể được sử dụng chính xác cho các tập dữ liệu cao. 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ột 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. Tiếp theo là lần chuyển cuối cùng tạo từng điểm còn lại trong tập dữ liệu thành 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, lượng mẫu cần thiết để phân cụm cao và cần thêm kỹ thuật thứ hai. Trong tình huống này, CURE phân vùng dữ liệu mẫu và phân cụm các điểm trong mọi phân vùng. Quy trình phân nhóm trước này được theo sau bởi một nhóm các cụm trung gian và một lần vượt qua cuối cùng tạo ra mỗi điểm trong tập dữ liệu thành một trong các cụm.