Cắt tỉa là quy trình làm giảm kích thước của cây quyết định. Nó có thể làm giảm nguy cơ quá mức bằng cách xác định kích thước của cây hoặc loại bỏ các khu vực cây hỗ trợ ít năng lượng. Việc cắt tỉa hỗ trợ bằng cách cắt tỉa các nhánh có biểu hiện bất thường trong thông tin huấn luyện do nhiễu hoặc các yếu tố khác thường và hỗ trợ cây gốc theo phương pháp nâng cao hiệu quả tổng quát của cây.
Các phương pháp khác nhau thường sử dụng các biện pháp thống kê để xóa các bộ phận kém tin cậy nhất, thường dẫn đến việc phân loại nhanh hơn và cải thiện khả năng phân loại dữ liệu thử nghiệm độc lập của cây.
Có hai cách tiếp cận để cắt tỉa cây như sau -
Phương pháp tiếp cận trước khi cắt tỉa
Trong cách tiếp cận trước khi cắt tỉa, một cây được “cắt tỉa” bằng công việc xây dựng sớm (ví dụ, bằng cách xác định không chia hoặc phân vùng thêm tập hợp con của các mẫu đào tạo tại một nút đã cho). Khi dừng lại, nút biến thành một chiếc lá. Lá có thể ảnh hưởng đến lớp phổ biến nhất giữa các mẫu tập hợp con hoặc phân phối xác suất của các mẫu đó.
Khi tạo một cây, có thể sử dụng các biện pháp bao gồm ý nghĩa thống kê, x2, thu thập thông tin, v.v., để tạo ra mức độ rộng rãi của sự phân chia. Nếu việc phân vùng các mẫu tại một nút có thể dẫn đến sự phân tách giảm xuống dưới ngưỡng được chỉ định trước, thì việc phân chia tập hợp con đã cho sẽ bị tạm dừng. Có vấn đề trong việc chọn một ngưỡng thích hợp. Ngưỡng cao có thể dẫn đến cây đơn giản hóa quá mức, trong khi ngưỡng thấp có thể dẫn đến đơn giản hóa rất ít.
Phương pháp sau khi cắt tỉa
Phương pháp sau khi cắt tỉa sẽ loại bỏ các cành khỏi cây "đã trưởng thành hoàn toàn". Một nút cây được cắt tỉa bằng cách loại bỏ các nhánh của nó. Thuật toán cắt tỉa độ phức tạp giá là một ví dụ của phương pháp cắt tỉa sau. Nút được cắt tỉa biến thành một chiếc lá và được gắn nhãn bởi lớp phổ biến nhất giữa các nhánh trước của nó.
Đối với mỗi nút không phải là lá trong cây, thuật toán sẽ tính toán tỷ lệ lỗi dự kiến có thể xuất hiện nếu cây con tại nút đó được rút ngắn. Tiếp theo, tỷ lệ lỗi dự kiến xuất hiện nếu nút không được lược bỏ được tính toán bằng cách sử dụng tỷ lệ lỗi cho mỗi nhánh, được kết nối bằng trọng số theo thứ nguyên của các quan sát dọc theo mỗi nhánh. Nếu việc lược bớt nút dẫn đến tỷ lệ lỗi dự kiến cao hơn, thì cây con được giữ nguyên. Do đó, nó được cắt tỉa.
Sau khi tạo ra một tập hợp các cây ngày càng được cắt tỉa, một tập hợp thử nghiệm độc lập có thể ước tính hiệu quả của từng cây. Cây quyết định làm giảm chi phí lỗi dự kiến được ưu tiên hơn.