Core Algorithmsপড়তে ৮ মিনিট লাগবে

ডিসিশন ট্রি (Decision Trees)

একটি ফ্লোচার্ট (flowchart) যা বুঝতে পারে যে ঠিক কোন প্রশ্নগুলো করা উচিত

training:O(n * d * log n) — প্রতিটি স্প্লিটে বা ভাগে ফিচারগুলোকে সাজানো (sorting features) হয়prediction:O(depth) — শুধু এর শাখা বা ব্রাঞ্চগুলো (branches) অনুসরণ করতে হয়interpretability:অনেক বেশি — আপনি চাইলে নিজেই এই ট্রি বা গাছটি এঁকে তা পড়তে বা বুঝতে পারবেন

ছোটবেলার ২০ প্রশ্নের (20 Questions) গেমটির কথা মনে আছে? "এটি কি বেঁচে আছে? এটি কি একটি রুটির বাক্সের চেয়ে বড়? এর কি পা আছে?" প্রতিটি প্রশ্ন এখানকার উত্তরের সম্ভাবনাগুলোকে একটু একটু করে কমিয়ে আনতে থাকে যতক্ষণ না আপনি আসল উত্তরটি খুঁজে পাচ্ছেন।

একটি ডিসিশন ট্রি (decision tree) মূলত ঠিক এভাবেই কাজ করে। এটি আপনার ডেটা সম্পর্কে হ্যাঁ/না (yes/no) উত্তরের এমন কয়েকটি প্রশ্ন তৈরি করে নেয়, এবং এখানকার প্রতিটি উত্তর আপনাকে গাছটির একেকটি ভিন্ন শাখা ধরে নিচের দিকে নিয়ে যায় যতক্ষণ না আপনি এর একেবারে নিচে গিয়ে একটি প্রেডিকশন বা উত্তর খুঁজে পাচ্ছেন।

এর সবচেয়ে দারুণ দিকটি হলো, গাছটি শুধু আপনার ডেটা দেখে নিজেই বুঝে নিতে পারে যে, কোন প্রশ্নগুলো জিজ্ঞাসা করা সবচেয়ে ভালো হবে।

গাছটি কীভাবে তার প্রশ্নগুলো বেছে নেয়?

ভাবুন তো, আপনি আপেল এবং কমলার একটি মিশ্রিত বা মেশানো ব্যাগ থেকে ফলগুলো আলাদা করছেন। এসময় আপনি হয়তো প্রশ্ন করতে পারেন:

"এটি কি লাল রঙের?" — এটি বেশ ভালোভাবে ফলগুলোকে আলাদা করতে পারে! কারণ বেশিরভাগ আপেল লাল হয়, আর কমলা লাল হয় না।
"এর ওজন কি ৩০০ গ্রামের বেশি?" — এটি খুব একটা কাজের প্রশ্ন নয়। কারণ আপেল এবং কমলা দুটোরই ওজন বেশি বা কম হতে পারে।

গাছটি সবসময় সেই প্রশ্নটিকেই বেছে নেয় যা সবচেয়ে খাঁটি বা পিওর স্প্লিট (purest split) তৈরি করে — অর্থাৎ যে প্রশ্নটি ব্যবহার করে ক্লাস বা ফলগুলোকে সবচেয়ে ভালোভাবে আলাদা করা যায়। এটি মূলত ইনফরমেশন গেইন (information gain) (বা জিনি ইমপিউরিটি (Gini impurity)) নামক একটি কনসেপ্ট বা ধারণার মাধ্যমে পরিমাপ করা হয়।

ব্যাপারটা এভাবে চিন্তা করুন: এমন একটি স্তূপ যেখানে কেবলমাত্র আপেল রয়েছে, তা হলো পিওর বা খাঁটি (জিনি = 0)। কিন্তু এমন একটি স্তূপ যেখানে ৫০/৫০ অনুপাতে আপেল ও কমলা মেশানো আছে, সেটি হলো সবচেয়ে বেশি ইমপিওর বা অশুদ্ধ (maximally impure) (জিনি = 0.5)। গাছটি সবসময়ই এমন প্রশ্ন বেছে নেয়, যা দিয়ে এই ইমপিউরিটি বা অশুদ্ধতা সবচেয়ে বেশি কমানো যায়।

গাছ বড় করা (Growing the tree)

এর অ্যালগরিদমটি খুব সুন্দরভাবে রিকার্সিভ (recursive) নিয়মে কাজ করে:

সবগুলো ফিচার এবং যেকোনো জায়গায় আলাদা বা স্প্লিট করার সম্ভাব্য পয়েন্টগুলো (split points) দেখুন
এমন একটি স্প্লিট বেছে নিন যা সবচেয়ে ভালো ইনফরমেশন গেইন (information gain) দেয়
ডেটাগুলোকে দুটি গ্রুপে বা ভাগে ভাগ করুন
এরপর প্রতিটি গ্রুপের জন্য পুনরায় ১-৩ নং ধাপগুলোর পুনরাবৃত্তি (repeat) করুন
আর এভাবেই চলতে থাকুন যতক্ষণ না কোনো একটি গ্রুপ পিওর বা খাঁটি (অর্থাৎ সব একই ক্লাসের) হয়ে যায় অথবা আপনি এর ডেপ্থ বা গভীরতার (depth limit) একেবারে শেষ সীমায় পৌঁছে যান

কোনো লিমিট বা সীমা না থাকলে, গাছটি ততক্ষণ পর্যন্ত ভাঙতে বা স্প্লিট করতে থাকবে যতক্ষণ না প্রতিটি ট্রেইনিং উদাহরণ তার নিজের আলাদা একটি পাতায় গিয়ে পৌঁছায়। আর এটিকেই ওভারফিটিং (overfitting) বলা হয় — অর্থাৎ গাছটি তখন সাধারণ প্যাটার্নগুলো শেখার বদলে কেবল ট্রেইনিং ডেটাগুলো মুখস্থ করে ফেলে। এটি অনেকটা কোনো বিষয় ভালোভাবে না বুঝে কেবল এর উত্তরগুলো মুখস্থ করার মতো।

এটি আটকানোর জন্য আমরা প্রুনিং (pruning) ব্যবহার করি: এর ডেপ্থ বা গভীরতা নির্দিষ্ট করে দেওয়া, প্রতিটি পাতায় একটি ন্যূনতম (minimum) স্যাম্পল থাকার নিয়ম করে দেওয়া, অথবা যেসব শাখা দিয়ে ভ্যালিডেশন ডেটার (validation data) কোনো লাভ হয় না সেগুলোকে কেটে ফেলা বা বাদ দেওয়া।

ডিসিশন ট্রি: আমার কি বাইরে যাওয়া উচিত? (Decision Tree: Should I Go Outside?)

class Node:
    def __init__(self, feature=None, threshold=None,
                 left=None, right=None, prediction=None):
        self.feature = feature
        self.threshold = threshold
        self.left = left
        self.right = right
        self.prediction = prediction

# হাতে বানানো ডিসিশন ট্রি: বাইরে যাবো? (Hand-built decision tree for: go outside?)
# ফিচারস (Features): [তাপমাত্রা (temperature), বৃষ্টি হচ্ছে (is_raining) (0/1), বাতাসের গতি (wind_speed)]
tree = Node(feature=1, threshold=0.5,                   # বৃষ্টি হচ্ছে? (Is it raining?)
    left=Node(feature=0, threshold=15,                   # তাপমাত্রা > ১৫? (Temp > 15?)
        left=Node(prediction="ঘরে থাকুন (Stay in)"),                 # ঠাণ্ডা + বৃষ্টি নেই (Cold + not raining)
        right=Node(prediction="বাইরে যান! (Go outside!)")),            # গরম + বৃষ্টি নেই (Warm + not raining)
    right=Node(prediction="ঘরে থাকুন (Stay in)"))                    # বৃষ্টি হচ্ছে → ঘরে থাকুন (Raining → stay in)

def predict(node, x):
    if node.prediction is not None:
        return node.prediction
    if x[node.feature] <= node.threshold:
        return predict(node.left, x)
    return predict(node.right, x)

test_cases = [
    ([25, 0, 5], "Warm, no rain"),
    ([10, 0, 3], "Cold, no rain"),
    ([20, 1, 2], "Warm but raining"),
]
for features, desc in test_cases:
    print(f"{desc}: {predict(tree, features)}")

Output

Warm, no rain: বাইরে যান! (Go outside!)
Cold, no rain: ঘরে থাকুন (Stay in)
Warm but raining: ঘরে থাকুন (Stay in)

Note: ডিসিশন ট্রি (Decision trees) হলো হাতেগোনা কয়েকটি মেশিন লার্নিং মডেলের (ML models) মধ্যে অন্যতম, যাকে আপনি চাইলে হোয়াইটবোর্ডে এঁকে একজন নন-টেকনিক্যাল ব্যক্তিকেও বোঝাতে পারবেন। আর এটাই হলো এর সবচেয়ে বড় সুপারপাওয়ার বা ক্ষমতা। কিন্তু একটিমাত্র গাছ ওভারফিট করার সম্ভাবনা অনেক বেশি থাকে — যার কারণে আমরা সাধারণত অনেকগুলো গাছ একসাথে মিলিয়ে কাজ করি (দেখুন: র‍্যান্ডম ফরেস্ট বা Random Forests)।