CART là một thuật toán cây quyết định nổi tiếng do Leo Breiman, Jerome Friedman, Richard Olshen và Charles Stone sản xuất lần đầu tiên vào năm 1984. CART đại diện cho các Cây phân loại và hồi quy. Thuật toán CART cải thiện cây nhị phân và tiếp tục phân chia xem xét các phân chia mới có thể được tìm thấy để cải thiện độ tinh khiết.
Có một số cây con đơn giản hơn, mỗi cây con xác định sự cân bằng khác nhau giữa độ phức tạp của mô hình và tỷ lệ phân loại sai nhóm đào tạo. Thuật toán CART nhận dạng một nhóm các cây con như vậy là các mô hình ứng viên. Các cây con ứng cử viên này được sử dụng cho nhóm xác thực và cây có tỷ lệ phân loại sai được thiết lập xác thực tối thiểu được chọn làm mô hình cuối cùng.
Thuật toán CART nhận ra các cây con ứng viên thông qua một quy trình cắt tỉa lặp đi lặp lại. Mục tiêu là trước tiên phải cắt tỉa những cành hỗ trợ ít khả năng dự đoán nhất trên mỗi lá. Nó có thể nhận ra những nhánh ít có lợi nhất này, CART dựa trên một khái niệm được gọi là tỷ lệ lỗi đã điều chỉnh.
Đây là một biện pháp giúp cải thiện chi phí phân loại sai của mỗi nút trong quá trình đào tạo được đặt ra bằng cách ấn tượng mức phạt phức tạp phụ thuộc vào nhiều lá trong cây. Tỷ lệ sai sót được điều chỉnh có thể xác định các nhánh yếu (những nhánh có tỷ lệ phân loại sai không đủ để vượt qua hình phạt) và chỉ ra chúng để cắt tỉa.
Nhiệm vụ tiếp theo là chọn từ nhóm các cây con ứng cử viên, cây nào hoạt động tốt nhất trên bản ghi mới. Mỗi cây con ứng cử viên có thể xác định dữ liệu trong tập xác nhận. Cây thực hiện nhiệm vụ này với tỷ lệ lỗi hoàn thành thấp nhất được xác định là cây chiến thắng. Cây con chiến thắng đã được lược bớt phù hợp để loại bỏ ảnh hưởng của việc luyện tập quá sức, nhưng không quá nguy hiểm đến mức mất dữ liệu quý giá.
Bởi vì thuật toán lược bớt này phụ thuộc vào tỷ lệ phân loại sai, mà không tính đến xác suất của từng phân loại, nó khôi phục một số cây con mà các lá của chúng đều tạo ra cùng một phân loại với một cha mẹ chung cũng tạo ra phân loại đó.
Mục tiêu là chọn một tỷ lệ nhỏ dữ liệu (ví dụ:1 phần trăm hoặc 10 phần trăm hàng đầu), thuật toán cắt tỉa này có thể ảnh hưởng đến việc triển khai cây, bởi vì một số lá bị loại bỏ bao gồm một khu vực rất cao của lớp mục tiêu . Có nhiều công cụ khác nhau, bao gồm cả SAS Enterprise Miner, cho phép người dùng cắt tỉa cây một cách tối ưu cho các phương pháp như vậy.
Cây con chiến thắng được chọn trên cơ sở tỷ lệ lỗi hoàn toàn của nó khi được sử dụng cho nhiệm vụ xác định dữ liệu trong bộ xác thực. Có thể mong đợi rằng cây con đã chọn sẽ tiếp tục là cây con triển khai tốt nhất khi được sử dụng cho nhiều tập dữ liệu, tỷ lệ lỗi tạo ra nó để được chọn có thể hơi phóng đại sức mạnh của nó.