CART là thuật toán cây quyết định nổi tiếng đầu tiên được tạo ra bởi Leo Breiman, Jerome Friedman, Richard Olshen, và Charles Stone năm 1984. CART là viết tắt của Classification and Regression Trees (Cây Phân loại và Hồi quy). Thuật toán CART tạo cây nhị phân và tiếp tục chia miễn là tìm thấy các phép chia mới cải thiện độ tinh khiết.
Có một số cây con đơn giản hơn, mỗi cái định nghĩa một sự đánh đổi khác nhau giữa độ phức tạp mô hình và tỷ lệ phân loại sai tập huấn luyện. Thuật toán CART nhận diện một nhóm các cây con như vậy như các mô hình ứng viên. Các cây con ứng viên này được áp dụng cho tập validation và cây với tỷ lệ phân loại sai tập validation thấp nhất được chọn là mô hình cuối cùng.
Thuật toán CART nhận diện các cây con ứng viên thông qua quy trình cắt tỉa lặp lại. Mục tiêu là cắt tỉa trước những nhánh mang lại sức mạnh dự báo ít nhất trên mỗi lá. Để nhận diện các nhánh ít có lợi này, CART dựa trên khái niệm gọi là tỷ lệ lỗi điều chỉnh (adjusted error rate).
Đây là thước đo cải thiện chi phí phân loại sai của mỗi nút trên tập huấn luyện bằng cách áp dụng phạt độ phức tạp dựa trên số lá trong cây. Tỷ lệ lỗi điều chỉnh có thể nhận diện nhánh yếu (những cái mà tỷ lệ phân loại sai không đủ để vượt qua phạt) và đánh dấu chúng để cắt tỉa.
Nhiệm vụ tiếp theo là chọn, từ hồ bơi các cây con ứng viên, cái hoạt động tốt nhất trên dữ liệu mới. Mỗi cây con ứng viên có thể định nghĩa dữ liệu trong tập validation. Cây thực hiện nhiệm vụ này với tổng tỷ lệ lỗi thấp nhất được định nghĩa là người thắng. Cây con thắng đã được cắt tỉa đủ để loại bỏ tác động của overfitting (quá khớp), nhưng không quá mức để mất thông tin quý giá.
Vì thuật toán cắt tỉa này dựa trên tỷ lệ phân loại sai, mà không lấy xác suất của mỗi phân loại vào tài khoản, nó khôi phục một số cây con mà các lá của chúng đều tạo cùng một phân loại với cha chung cũng tạo phân loại đó.
Mục tiêu là chọn một tỷ lệ nhỏ dữ liệu (top 1% hoặc 10%, ví dụ), thuật toán cắt tỉa này có thể làm tổn thương hiệu suất của cây, vì một số lá bị loại bỏ chứa tỷ lệ rất cao của lớp mục tiêu. Có nhiều công cụ, bao gồm SAS Enterprise Miner, cho phép người dùng cắt tỉa cây tối ưu cho các phương pháp như vậy.
Cây con thắng được chọn dựa trên tổng tỷ lệ lỗi khi áp dụng cho nhiệm vụ định nghĩa dữ liệu trong tập validation. Có thể kỳ vọng cây con được chọn sẽ tiếp tục là cây con triển khai tốt nhất khi áp dụng cho nhiều tập dữ liệu, tỷ lệ lỗi làm cho nó được chọn có thể hơi quá khẳng định sức mạnh của nó.