Cắt tỉa (Pruning) là thủ tục giảm kích thước cây quyết định. Giảm nguy cơ overfitting bằng cách giới hạn kích thước cây hoặc loại bỏ vùng cây hỗ trợ sức mạnh nhỏ. Cắt tỉa giúp cắt tỉa nhánh tuân theo bất thường trong thông tin huấn luyện do nhiễu hoặc giá trị ngoại lai và hỗ trợ cây gốc cách tăng cường hiệu quả tổng quát hóa của cây.
Các phương pháp khác nhau thường dùng thước độ thống kê để loại bỏ bộ phận kém tin cậy nhất, thường dẫn đến phân loại nhanh hơn và cải thiện khả năng cây phân loại đúng dữ liệu test độc lập.
Có hai phương pháp cắt tỉa cây:
Phương Pháp Tiền Cắt Tỉa (Pre-pruning)
Trong phương pháp tiền cắt tỉa, cây "cắt tỉa" bằng cách dừng xây dựng sớm (ví dụ: quyết định không phân chia thêm tập con mẫu huấn luyện tại nút cho trước). Khi dừng, nút biến thành lá. Lá có thể mang lớp phổ biến nhất trong tập con mẫu, hoặc phân phối xác suất những mẫu đó.
Khi tạo cây, thước độ bao gồm ý nghĩa thống kê, x2, information gain, v.v., dùng để đánh giá sự hào phóng của phân chia. Nếu phân chia mẫu tại nút dẫn đến phân chia dưới ngưỡng xác định trước, phân chia tập con cho trước dừng. Vấn đề chọn ngưỡng phù hợp. Ngưỡng cao dẫn đến cây quá đơn giản, ngưỡng thấp dẫn đến ít đơn giản hóa.
Phương Pháp Hậu Cắt Tỉa (Post-pruning)
Phương pháp hậu cắt tỉa loại bỏ nhánh từ cây "hoàn toàn phát triển". Nút cây cắt tỉa bằng cách loại bỏ nhánh. Nút cắt tỉa biến thành lá và gán nhãn lớp phổ biến nhất trong nhánh trước.
Đối với mỗi nút không phải lá, thuật toán tính tỷ lệ lỗi kỳ vọng nếu cây con tại nút đó được cắt ngắn. Tiếp theo, tỷ lệ lỗi kỳ vọng nếu nút không cắt tính dùng tỷ lệ lỗi mỗi nhánh, kết hợp theo trọng số theo kích thước quan sát dọc mỗi nhánh. Nếu cắt nút dẫn đến tỷ lệ lỗi kỳ vọng cao hơn, cây con được giữ. Do đó, cắt tỉa.
Sau tạo tập cây cắt tỉa tăng dần, tập test độc lập ước lượng hiệu quả mỗi cây. Cây quyết định làm giảm chi phí lỗi kỳ vọng được ưu tiên.