CART เป็นอัลกอริธึมแผนผังการตัดสินใจที่มีชื่อเสียงซึ่งผลิตโดย Leo Breiman, Jerome Friedman, Richard Olshen และ Charles Stone ในปี 1984 CART แสดงถึงต้นไม้การจำแนกและการถดถอย อัลกอริธึม CART ปรับปรุงไบนารีทรีและแบ่งต่อเมื่อพิจารณาการแยกใหม่ซึ่งช่วยเพิ่มความบริสุทธิ์
มีทรีย่อยที่ง่ายกว่า ซึ่งแต่ละอันกำหนดการแลกเปลี่ยนที่แตกต่างกันระหว่างความซับซ้อนของแบบจำลองและอัตราการจำแนกกลุ่มการฝึกอบรมผิด อัลกอริธึม CART รู้จักกลุ่มของทรีย่อยดังกล่าวเป็นโมเดลตัวเลือก ทรีย่อยตัวเลือกเหล่านี้ใช้กับกลุ่มการตรวจสอบ และต้นไม้ที่มีอัตราการจำแนกประเภทชุดการตรวจสอบขั้นต่ำจะถูกเลือกเป็นรูปแบบสุดท้าย
อัลกอริธึม CART รู้จักต้นไม้ย่อยของผู้สมัครผ่านขั้นตอนการตัดแต่งกิ่งซ้ำๆ มีวัตถุประสงค์เพื่อตัดกิ่งแรกที่สนับสนุนพลังทำนายน้อยที่สุดต่อใบไม้ สามารถรับรู้สาขาที่เป็นประโยชน์น้อยที่สุดเหล่านี้ CART ตามแนวคิดที่เรียกว่าอัตราความผิดพลาดที่ปรับปรุงแล้ว
นี่เป็นมาตรการที่ช่วยปรับปรุงค่าใช้จ่ายในการจัดประเภทที่ไม่ถูกต้องของแต่ละโหนดในการฝึกอบรมที่กำหนดโดยบทลงโทษด้านความซับซ้อนที่น่าประทับใจขึ้นอยู่กับใบไม้หลายใบในต้นไม้ อัตราความผิดพลาดที่ปรับแล้วสามารถระบุกิ่งที่อ่อนแอ (สาขาที่มีอัตราการจำแนกผิดไม่เพียงพอที่จะเอาชนะบทลงโทษ) และระบุสาขาสำหรับการตัดแต่งกิ่ง
งานต่อไปคือการเลือกจากกลุ่มของทรีย่อยของผู้สมัคร ซึ่งทำงานได้ดีที่สุดในเรกคอร์ดใหม่ ทรีย่อยของผู้สมัครแต่ละรายสามารถกำหนดข้อมูลในชุดการตรวจสอบความถูกต้องได้ ต้นไม้ที่ดำเนินการงานนี้ด้วยอัตราความผิดพลาดที่สมบูรณ์ต่ำสุดถูกกำหนดให้เป็นผู้ชนะ ทรีย่อยที่ชนะได้รับการตัดแต่งอย่างเพียงพอเพื่อขจัดผลกระทบของการฝึกมากเกินไป แต่ไม่มากเท่าการสูญเสียข้อมูลที่มีค่า
เนื่องจากอัลกอริธึมการตัดแต่งกิ่งนี้ขึ้นอยู่กับอัตราการจัดประเภทที่ไม่ถูกต้อง โดยไม่ต้องคำนึงถึงความน่าจะเป็นของแต่ละประเภทด้วย มันคืนค่าทรีย่อยบางตัวที่ปล่อยให้ทั้งหมดสร้างการจัดประเภทเดียวกันกับพาเรนต์ทั่วไปที่สร้างการจำแนกประเภทนั้นด้วย
วัตถุประสงค์คือเลือกข้อมูลส่วนน้อย (เช่น 1 เปอร์เซ็นต์บนสุดหรือ 10 เปอร์เซ็นต์ เป็นต้น) อัลกอริธึมการตัดแต่งกิ่งนี้อาจส่งผลเสียต่อการนำต้นไม้ไปใช้ เนื่องจากใบที่ถูกตัดออกบางส่วนมีพื้นที่ของคลาสเป้าหมายที่สูงมาก . มีเครื่องมือต่างๆ รวมถึง SAS Enterprise Miner ที่ช่วยให้ผู้ใช้ตัดต้นไม้อย่างเหมาะสมสำหรับวิธีการดังกล่าว
ทรีย่อยที่ชนะได้รับเลือกโดยพิจารณาจากอัตราความผิดพลาดทั้งหมดเมื่อใช้กับภารกิจการกำหนดข้อมูลในชุดการตรวจสอบความถูกต้อง สามารถคาดหวังได้ว่าทรีย่อยที่เลือกจะยังคงเป็นทรีย่อยที่ปรับใช้ได้ดีที่สุดเมื่อใช้กับชุดข้อมูลหลายชุด อัตราข้อผิดพลาดที่สร้างให้สามารถเลือกได้อาจกล่าวเกินจริงไปเล็กน้อย
