একটি ডিসিশন ট্রি হলো একটি ফ্লো-চার্ট-সদৃশ ট্রি মেকানিজম, যেখানে প্রতিটি ইন্টারনাল নোড একটি অ্যাট্রিবিউটে একটি টেস্ট নির্দেশ করে, প্রতিটি ব্রাঞ্চ টেস্টের ফলাফল নির্দেশ করে, এবং লিফ নোড ক্লাস বা ক্লাস ডিস্ট্রিবিউশন বর্ণনা করে। একটি ট্রির সর্বোচ্চ নোড হলো রুট নোড।
ডিসিশন ট্রি শিখার অ্যালগরিদম
অ্যালগরিদম — প্রদত্ত ট্রেনিং ইনফরমেশন থেকে একটি ডিসিশন ট্রি তৈরি করা।
ইনপুট — ট্রেনিং স্যাম্পলস, স্যাম্পলস, ডিসক্রিট-ভ্যালুড অ্যাট্রিবিউট দ্বারা বর্ণিত; অ্যাট্রিবিউট সেট, অ্যাট্রিবিউট-লিস্ট।
আউটপুট — একটি ডিসিশন ট্রি।
পদ্ধতি (Method)
একটি নোড N তৈরি করুন;
যদি স্যাম্পলস সব একই ক্লাস C-এর হয়, তবে
N কে ক্লাস C লেবেল্ড একটি লিফ নোড হিসেবে রিটার্ন করুন
যদি অ্যাট্রিবিউট-লিস্ট নাল হয়, তবে
N কে স্যাম্পলসে সবচেয়ে কমন ক্লাস লেবেল্ড একটি লিফ নোড হিসেবে রিটার্ন করুন। // মেজোরিটি ভোটিং
টেস্ট-অ্যাট্রিবিউট সিলেক্ট করুন, অ্যাট্রিবিউট-লিস্ট থেকে সেরা ইনফরমেশন গেইনওয়ালা অ্যাট্রিবিউট।
নোড N কে টেস্ট অ্যাট্রিবিউট দিয়ে লেবেল করুন।
টেস্ট-অ্যাট্রিবিউটের প্রতিটি জানা মান a_i এর জন্য // স্যাম্পলস পার্টিশন করুন।
নোড N থেকে শর্ত test-attribute = a_i জন্য একটি ব্রাঞ্চ বড়ান।
s_i কে স্যাম্পলসের সেট হোন যাদের জন্য test-attribute = a_i।
যদি s_i খালি হয়, তবে
স্যাম্পলসে সবচেয়ে কমন ক্লাস লেবেল্ড একটি লিফ সংযুক্ত করুন।
অথবা Generate decision tree (s_i, attribute-list - test-attribute) রিটার্ন করা নোড সংযুক্ত করুন।
ডিসিশন ট্রি ইন্ডাকশন (Decision Tree Induction)
ডিসিশন রুলের স্বয়ংক্রিয় উৎপাদন উদাহরণের জন্য রুল ইন্ডাকশন বা অটোমেটিক রুল ইন্ডাকশন বলা হয়। ডিসিশন ট্রির ইমপ্লিসিট ফর্মে ডিসিশন রুল তৈরি করাকেও প্রায়শই রুল ইন্ডাকশন বলা হয়, কিন্তু টার্ম ট্রি ইন্ডাকশন বা ডিসিশন ট্রি ইন্ডাকশন সর্বদা পছন্দ করা হয়।
ডিসিশন ট্রি ইন্ডাকশনের বেসিক অ্যালগরিদম একটি গ্রিডি অ্যালগরিদম। এটি টপ-ডাউন রিকার্সিভ ডিভাইড-এন্ড-কঙ্কার পদ্ধতিতে ডিসিশন ট্রি জেনারেট করতে ব্যবহৃত হয়। ডিসিশন ট্রি শিখার বেসিক অ্যালগরিদম, ID3-র একটি ফর্ম, একটি বিখ্যাত ডিসিশন ট্রি ইন্ডাকশন অ্যালগরিদম।
বেসিক মেথডগুলো নিচে দেয়া হলো:
ট্রি একটি একক নোড হিসেবে শুরু হয় যা ট্রেনিং স্যাম্পলসকে রিপ্রেজেন্ট করে।
যদি স্যাম্পলস সব একই ক্লাসের হয়, তবে নোড একটি লিফে রূপান্তরিত হয় এবং সে ক্লাস দিয়ে লেবেল করা হয়।
অ্যালগরিদম একটি এন্ট্রপি-ভিত্তিক মেজার যাকে ইনফরমেশন গেইন বলা হয় সেটি হিউরিস্টিক হিসেবে ব্যবহার করে সেরা অ্যাট্রিবিউট বেছে নেওয়ার জন্য যা স্যাম্পলসকে আলাদা ক্লাসে ভাগ করবে। এই অ্যাট্রিবিউট নোডে "টেস্ট" বা "ডিসিশন" অ্যাট্রিবিউটে ডেভেলপ হয়। এই ফর্মে, সব অ্যাট্রিবিউট ক্যাটাগরিক্যাল, অর্থাৎ ডিসক্রিট-ভ্যালুড। কন্টিনিউয়াস ভ্যালুড অ্যাট্রিবিউট ডিসক্রেটাইজ করা উচিত।
টেস্ট অ্যাট্রিবিউটের প্রতিটি জানা মানের জন্য একটি ব্রাঞ্চ জেনারেট করা হয়, এবং স্যাম্পলস উপযুক্তভাবে পার্টিশন করা হয়।
অ্যালগরিদম একই প্রসেস লুপিংয়ে ব্যবহার করে প্রতিটি পার্টিশনে স্যাম্পলসের জন্য একটি ডিসিশন ট্রি ফর্ম করতে। যেহেতু একটি অ্যাট্রিবিউট একটি নোডে আবির্ভূত হয়েছে, সেটি নোডের ডেসেন্ডেন্টগুলোর যেকোনোতে বিবেচনা করা বাধ্য নয়।
