যেখানে সাপোর্ট ভেক্টর মেশিন বা রিগ্রেশন মডেল অবিচ্ছিন্ন জ্যামিতিক তল দিয়ে কাজ করে, সেখানে ডিসিশন ট্রি (Decision Tree) পরিচালিত হয় অনুক্রমিক যুক্তির মাধ্যমে। ১৯৮৪ সালে লিও ব্রেইম্যান, জেরোম ফ্রিডম্যান, রিচার্ড ওলশেন এবং চার্লস স্টোন তাঁদের ক্লাসিক মনোগ্রাফ “Classification and Regression Trees (CART)”-এ এমন এক কাঠামো তুলে ধরেন যা উচ্চ-মাত্রিক স্পেসকে অক্ষ-বরাবর আয়তক্ষেত্রাকার অঞ্চলে বিভক্ত করে। এর ফলে তৈরি হয় সম্পূর্ণ ব্যাখ্যাকরণযোগ্য এক সিদ্ধান্ত কাঠামো যা স্কেলিং পরিবর্তনের মুখেও চিরস্থির থাকে।
১. অর্থোগোনাল স্পেস পার্টিশনিংয়ের জ্যামিতি
ধরা যাক পুরো ইনপুট স্পেস $mathcal{X}$-কে $M$ সংখ্যক অসদৃশ অঞ্চলে $R_1, dots, R_M$ বিভক্ত করা হলো। একটি ডিসিশন ট্রি পূর্বাভাস দেয় একটি পিস-ওয়াইজ ধ্রুবক ফাংশন হিসেবে:
$$f(x) = sum_{m=1}^M c_m mathbb{I}(x in R_m)$$
যেখানে ক্লাসিফিকেশনের ক্ষেত্রে $c_m$ হলো ওই অঞ্চলের সর্বাধিক সংখ্যাগরিষ্ঠ ক্লাসের লেবেল।
গাণিতিকভাবে $d$ মাত্রায় $M$ সংখ্যক সর্বোত্তম অঞ্চলের সীমানা নিখুঁতভাবে বের করা একটি এনপি-কমপ্লিট (NP-complete) সমস্যা। তাই ট্রি তৈরি হয় গ্রিডি বা লোভী রিকার্সিভ বাইনারি স্প্লিটিংয়ের মাধ্যমে।
২. নোড অপবিত্রতা পরিমাপ: এনট্রপি বনাম জিনি
প্রতিটি নোডে ডেটা কতটা বিশৃঙ্খল বা মিশ্রিত তা পরিমাপ করতে ইমপিউরিটি ফাংশন $I(m)$ ব্যবহৃত হয়:
- শ্যানন এনট্রপি (Shannon Entropy): তথ্য তত্ত্বের আলোকে ডেটার অনিশ্চয়তা পরিমাপ করে:
$$I_E(m) = -sum_{k=1}^K p_{mk} log_2 p_{mk}$$
এনট্রপির হ্রাসকে বলা হয় ইনফরমেশন গেইন (Information Gain)।
- জিনি ইমপিউরিটি (Gini Impurity — CART): একটি নোড থেকে দৈবভাবে একটি উপাদান তুলে নিয়ে তাকে নোডের ডিস্ট্রিবিউশন অনুযায়ী লেবেল দিলে তা ভুল হওয়ার সম্ভাব্যতা:
$$I_G(m) = 1 – sum_{k=1}^K p_{mk}^2$$
যদি নোডে কেবল এক ক্লাসের ডেটা থাকে (বিশুদ্ধ নোড), তবে জিনির মান শূন্য হয়।
- মিন স্কয়ার্ড এরর (MSE): রিগ্রেশন ট্রির ক্ষেত্রে মানের ভ্যারিয়েন্স পরিমাপ করে।
৩. গ্রিডি স্প্লিটিং নীতি
প্রতিটি ধাপে অ্যালগরিদম সকল ফিচারের সম্ভাব্য সকল কাট-পয়েন্ট $s$ পরীক্ষা করে নোডটিকে ডানে ও বামে বিভক্ত করে:
$$R_L(j, s) = {x mid x_j le s}, quad R_R(j, s) = {x mid x_j > s}$$
যে স্প্লিটটি গড় ইমপিউরিটি সর্বাধিক হ্রাস করতে পারে, সেটিকেই চূড়ান্ত হিসেবে গ্রহণ করা হয়:
$$Delta I = I(m) – left( frac{|D_L|}{|D_m|} I(D_L) + frac{|D_R|}{|D_m|} I(D_R) right)$$
৪. ওভারফিটিং ও কস্ট-কমপ্লেক্সিটি প্রুনিং (Pruning)
কোনো বাধা না দিলে একটি ট্রি ততক্ষণ পর্যন্ত ডালপালা ছড়াতে থাকে যতক্ষণ না প্রতিটি পাতায় মাত্র একটি করে ডেটা অবশিষ্ট থাকে ($I(m) = 0$)। এর ফলে ট্রেনিং এরর শূন্য হলেও ভ্যারিয়েন্স চরমভাবে বৃদ্ধি পায় এবং মডেলটি ব্যর্থ হয়।
কার্ট (CART) এই সমস্যা সমাধান করে এক অনন্য কৌশলে: প্রথমে কোনো বাধা ছাড়াই একটি সুবিশাল ট্রি $T_0$ বড় হতে দেওয়া হয়, এবং পরে পেছন থেকে অপ্রয়োজনীয় ডালপালা ছাঁটাই বা প্রুনিং (Pruning) করা হয়। এর জন্য কস্ট-কমপ্লেক্সিটি শর্ত ব্যবহার করা হয়:
$$mathcal{C}_alpha(T) = sum_{m in text{leaves}(T)} |D_m| I(m) + alpha |text{leaves}(T)|$$
এখানে $alpha$ হলো ট্রির আকারের ওপর একটি পেনাল্টি। ক্রস-ভ্যালিডেশনের মাধ্যমে সঠিক $alpha^*$ নির্বাচন করে ট্রি ছাঁটাই করার মাধ্যমে বায়াস ও ভ্যারিয়েন্সের নিখুঁত ভারসাম্য নিশ্চিত করা হয়।
