CART প্রুনিং অ্যালগরিদম
CART হল একটি বিখ্যাত ডিসিশন ট্রি অ্যালগরিদম যা প্রথমে লিও ব্রেইম্যান, জেরোম ফ্রিডম্যান, রিচার্ড অলশেন, এবং চার্লস স্টোন ১৯৮৪ সালে তৈরি করেছিলেন। CART অর্থাৎ Classification and Regression Trees। CART অ্যালগরিদম বাইনারি ট্রি তৈরি করে এবং বিভাজন চালিয়ে যেতে থাকছে যতক্ষণ না নতুন বিভাজন পাওয়া যায় যা পিউরিটি উন্নত করে।
কিছু সহজ সাবট্রি রয়েছে, যারা প্রতিটি মডেল কমপ্লেক্সিটি এবং ট্রেনিং গ্রুপ মিসক্লাসিফিকেশন রেটের মধ্যে ভিন্ন ট্রেড-অফ উপস্থাপন করে। CART অ্যালগরিদম таких সাবট্রির একটি গোষ্ঠীকে প্রার্থী মডেল হিসেবে চিহ্নিত করে। এই প্রার্থী সাবট্রিগুলোকেও ভ্যালিডেশন গ্রুপে প্রয়োগ করা হয় এবং সর্বনিম্ন ভ্যালিডেশন সেট মিসক্লাসিফিকেশন রেট वाला ট্রিকে চূড়ান্ত মডেল হিসেবে বেছে নেওয়া হয়।
CART অ্যালগরিদম পুনরাবৃত্তিমূলক প্রুনিং প্রক্রিয়ার মাধ্যমে প্রার্থী সাবট্রি চিহ্নিত করে। লক্ষ্য হল সেই ব্রাঞ্চগুলোকে প্রথমে প্রুন করা যারা কম প্রেডিক্টিভ পাওয়ার প্রদান করে প্রতি লিফ। এই সবচেয়ে কম উপকারী ব্রাঞ্চগুলো চিহ্নিত করতে, CART একটি কনসেপ্টের ওপর ভিত্তি করে যাকে অjusted এরর রেট (adjusted error rate) বলা হয়।
এটি একটি মাপ যা ট্রেনিং সেটে প্রতিটি নোডের মিসক্লাসিফিকেশন কস্টকে একটি কমপ্লেক্সিটি পেনাল্টি দিয়ে আপডেট করে যা ট্রিতে লিফের সংখ্যার ওপর ভিত্তি করে। অ্যাডজাস্টেড এরর রেট দুর্বল ব্রাঞ্চ চিহ্নিত করতে পারে (যেসবর মিসক্লাসিফিকেশন রেট পেনাল্টি ওবারকাম করার জন্য পর্যাপ্ত নয়) এবং সেগুলোকেও প্রুন করার জন্য চিহ্নিত করে।
পরবর্তী কাজ হল প্রার্থী সাবট্রির পুল থেকে সেটি বেছে নেওয়া যা নতুন ডেটায় সেরা পারফর্ম করে। প্রতিটি প্রার্থী সাবট্রি ভ্যালিডেশন সেটের ডেটা ক্লাসিফাই করতে পারে। যে ট্রি এই কাজটি সর্বনিম্ন মোট এরর রেটে করে সেটিকে বিজয়ী হিসেবে সংজ্ঞায়িত করা হয়। বিজয়ী সাবট্রি পর্যাপ্ত প্রুন করা হয়েছে ওভারট্রেনিং-এর প্রভাব দূর করতে, কিন্তু অত্যধিক প্রুন করা হয়নি যাতে মূল্যবান তথ্য হারায় না।
যেহেতু এই প্রুনিং অ্যালগরিদম মিসক্লাসিফিকেশন রেটের ওপর ভিত্তি করে, প্রতিটি ক্লাসিফিকেশনের প্রোবাবিলিটি বিবেচনা ছাড়া, এটি এমন একটি সাবট্রিকে পুনर्स্থাপন করে যেসব লিফ সব একই ক্লাসিফিকেশন তৈরি করে এক সাধারণ পেরেন্টের সাথে যেটিও সেটি ক্লাসিফিকেশন তৈরি করে।
যদি লক্ষ্য হয় ডেটার একটি ছোট অনুপাত বেছে নেওয়া (শীর্ষ ১ শতাংশ বা ১০ শতাংশ, উদাহরণস্বরূপ), এই প্রুনিং অ্যালগরিদম ট্রির পারফরম্যান্সকে ক্ষতি করতে পারে, কারণ সরানো লিফগুলোর মধ্যে কিছু টার্গেট ক্লাসের খুব উচ্চ অনুপাত ধারণ করে। বিভিন্ন টুল, যেমন SAS এন্টারপ্রাইজ মাইনার, ব্যবহারকারীকে সেরকম পদ্ধতির জন্য ট্রি অপ্টিমালি প্রুন করার অনুমতি দেয়।
বিজয়ী সাবট্রি তার মোট এরর রেটের ভিত্তিতে বেছে নেওয়া হয়েছিল যখন ভ্যালিডেশন সেটের ডেটা ক্লাসিফাই করার কাজে প্রয়োগ করা হয়েছিল। এটি অনুমান করা যেতে পারে যে নির্বাচিত সাবট্রি অন্যান্য ডেটাসেটে প্রয়োগ করলে সেরা পারফর্মিং সাবট্রি থাকবে, কিন্তু যে এরর রেটে এটিকে বেছে নেওয়া হয়েছিল সেটি কিছুটা এর শক্তি অতিরিক্তভাবে বলতে পারে।
