উপরে একটা স্পিড লিমিট সাইন এবং একটা ডায়াগ্রাম দেওয়া। ডায়াগ্রামের সবার উপরের নোডে দেওয়া “গাড়ির স্পিড >= ৫০”। এখন আমরা জিজ্ঞেস করি “গাড়ির স্পিড কি ৫০ এর সমান বা বেশি?” যদি উত্তর হয় “হ্যাঁ”, তবে গাড়ির স্পিড কমায় আনতে হবে। যদি উত্তর হয় “না”, তবে গাড়ির স্পিড যেমন আছে, ওই স্পিডে চললেই হবে।
এইখানে একটা হ্যাঁ-না সূচক প্রশ্ন করে আমরা নির্ধারণ করছি গাড়ির স্পিড কি কমাবো নাকি চলতে থাকবে একই স্পিডে। এইটা একটা সিম্পল ডিসিশন ট্রি-এর উদাহরণ।
Decision Tree: ডিসিশন ট্রি একটা সুপার্ভাইসড মেশিন লার্নিং অ্যালগরিদম যা ক্লাসিফিকেশন এবং রিগ্রেশন দুই ক্ষেত্রেই ব্যবহৃত হয়। তবে ক্লাসিফিকেশনে বেশি ব্যবহৃত হয়। এইটা একটা ট্রি-স্ট্রাকচার্ড ক্লাসিফায়ার। অর্থাৎ এর একটা রুট থাকে, সেইখান থেকে ব্রাঞ্চ তৈরি হয়, সেইখান থেকে লিফ নোড বের হয়।
উপরের ডায়াগ্রামটা ডিসিশন ট্রি এর ট্রি-স্ট্রাকচারটা দেখায়। সবার উপরে থাকে রুটনোড, এইখান থেকেই অ্যালগরিদম শুরু হয়। রুট নোড থেকে ব্রাঞ্চ শুধু বের হয়। যে নোডগুলো থেকে ব্রাঞ্চ বের হয় এবং ব্রাঞ্চ প্রবেশ করে, সেইগুলা ইন্টার্নালনোড। এই দুই ধরনের নোডগুলো ডাটাসেটের ফিচার রিপ্রেজেন্ট করে। সবচেয়ে শেষের নোড হল লিফনোড। লিফ নোড থেকে কোন ব্রাঞ্চ বের হয়না, খালি প্রবেশ করে। লিফ নোড আউটকাম বা আউটপুট রিপ্রেজেন্ট করে। ব্রাঞ্চগুলা ডিসিশন রুলস রিপ্রেজেন্ট করে। প্রদত্ত সকল কন্ডিশনের সাপেক্ষে কোন একটা প্রব্লেমের যত সম্ভাব্য সলুশন আছে, তার একটা গ্র্যাফিকাল রিপ্রেজেন্টশন এই ট্রি।
কিছু টার্মিনোলজি জেনে রাখা উচিত, যেইটা বারবার ব্যাবহার করা হবে। আমরা আগেই রুট নোড, ইন্টার্নাল নোড, লিফ নোড, ব্রাঞ্চ – এইগুলা জেনেছি। রুট নোড ও ইন্টার্নাল নোড এই দুইটাকে ডিসিশননোড-ও বলা হয়। কারণ এই নোডগুলা ব্যাবহার করে ডিসাইড করা হয় আমরা এরপর কোন ব্রাঞ্চের দিকে আগাব। কন্ডিশনের সাপেক্ষে ডিসিশন নোডকে ভাগ করে আরও সাব-নোড বানানোকে স্প্লিটিংবলে। আমরা যখন ডিসিশন ট্রি গঠন করতে যাব, তখন দেখব যে সব ব্রাঞ্চ আসলে দরকার হয়না। যেই ব্রাঞ্চগুলা দরকার হয়না, সেইগুলাকে বাছাই করে বাদ দেওয়াকে প্রুনিং বলে। একটা ট্রি-কে স্প্লিটিং করে অনেকগুলা সাব-ট্রি তৈরি হয়।
ডিসিশন ট্রি গঠনের জন্য কয়েক ধরনের অ্যালগরিদম ব্যাবহার করে থাকে। কোন অ্যালগরিদম ব্যাবহার করবে ডিসিশন ট্রি গঠনের জন্য, সেইটা নির্ভর করে টার্গেট ভ্যারিয়াবলের টাইপের উপর। যেসব অ্যালগরিদম ব্যাবহার করা হয়:
- ID3 (এক্সটেনশন অফ D3)
- C4.5 (সাক্সেসর অফ ID3)
- ক্ল্যাসিফিকেশন অ্যান্ড রিগ্রেশন ট্রি (CART)
- কাই-স্কোয়ার অটোমাটিক ইন্টারেকশন ডিটেকশন (CHAID)
- মাল্টিভ্যারিয়াট অ্যাড্যাপটিভ রিগ্রেশন স্প্লাইন্স (MARS)
- হান্টস অ্যালগরিদম
ডিসিশন ট্রি অ্যালগরিদম কিভাবে কাজ করে?
কোন প্রদত্ত ডাটাসেটের ক্লাস প্রেডিক্ট করার জন্য অ্যালগরিদমটি ডিসিশন ট্রি-এর রুট নোড থেকে কাজ শুরু করে। রুট নোডের অ্যাট্রিবিউটের সাথে তুলনা করে (“গাড়ির স্পিড কি ৫০ এর চেয়ে বেশি?”) ডিসিশন নেওয়া হয় যে কোন ব্রাঞ্চের দিকে আগাবে (যদি উত্তর হয় “হ্যাঁ”, তবে গাড়ির স্পিড কমায় আনতে হবে। যদি উত্তর হয় “না”, তবে গাড়ির স্পিড যেমন আছে, ওই স্পিডে চললেই হবে)। এইভাবে পরবর্তী যে নোড সিলেক্ট হয়, সেই নোডের অ্যাট্রিবিউটের সাথে তুলনা করে আবার ঠিক করে এখন কোন ব্রাঞ্চের দিকে যাবে। এইভাবে প্রত্যেক ধাপে সে নোডের অ্যাট্রিবিউটের সাথে তুলনা করে ঠিক করতে থাকে এখন সে কোন ব্রাঞ্চের দিকে যাবে যতক্ষণ পর্যন্ত না লিফ নোডে পৌঁছায়। লিফ নোডে পৌঁছান মানে আমরা যেইটা ক্লাসিফাই করতে চাচ্ছিলাম, সেইটা ক্লাসিফাই করা হয়ে গিয়ছে। পুরো প্রসেসটা নিচে দেওয়া হল:
- স্টেপ১: রুট নোড থেকে শুরু করতে হবে যেইটায় এখন পুরো ডাটাসেট রয়েছে। ধরি এই রুট নোড ’S’।
- স্টেপ২: প্রত্যেক ইটারেশনে S-এ অব্যবহৃত অ্যাট্রিবিউটগুলোর অ্যাট্রিবিউট সিলেকশন মেজার (ASM) ইনডেক্সগুলো ক্যালকুলেট করে। (ASM নিয়ে পরবর্তীতে দেখব আমরা)
- স্টেপ৩: ক্যালকুলেশন থেকে বেস্ট অ্যাট্রিবিউট সিলেক্ট করে।
- স্টেপ৪: সিলেক্ট করা বেস্ট অ্যাট্রিবিউটের ভিত্তিতে S-কে স্প্লিট করে সাবসেট অফ ডাটা বানায়।
- স্টেপ৫: রিকার্সিভলি প্রত্যেক সাবসেটে এই অ্যালগরিদম চলতে থাকে, প্রত্যেকবার অব্যবহৃত অ্যাট্রিবিউটগুলো কন্সিডার করে।
ডিসিশন ট্রি-এর সুবিধা:
- ডিসিশন ট্রি-এর প্রসেস মানুষের চিন্তার প্রসেসের সাথে মিলে। এজন্য এই প্রসেস সহজে বুঝা যায়।
- ডিসিশন রিলেটেড প্রবলেম সমাধান করতে অনেক কাজে লাগে।
- কোন নির্দিষ্ট সমস্যার সম্ভাব্য সকল সমাধান নিয়ে ভাবা যায়।
- যেহেতু আউটলায়ারের প্রভাব কম, তাই অন্যান্য অ্যালগরিদমের তুলনায় ডাটা প্রিপ্রসেসিং এর কাজ কম প্রয়োজন হয়।
- ক্যাটাগরিকাল এবং নিউমেরিকাল উভয় ধরনের ডাটা টাইপ ব্যাবহার করা যায়।
- সহজেই নতুন ফিচার সহজে অ্যাড করা যায়।
ডিসিশন ট্রি-এর অসুবিধা:
- ওভারফিটিং এর প্রবণতা বেশি।
- প্যারামিটার টিউনিং এর সময় সাবধানতা অবলম্বন করা জরুরি।
- বায়াসড ট্রি তৈরি হয়ে যেতে পারে।
- ক্লাস লেবেল বাড়লে, ক্যালকুলেশন কমপ্লেক্সিটি বেড়ে যেতে পারে।
আরও পড়তে চাইলে:
- https://www.xoriant.com/blog/product-engineering/decision-trees-machine-learning-algorithm.html
- https://www.geeksforgeeks.org/decision-tree-introduction-example/
- https://www.kdnuggets.com/2020/01/decision-tree-algorithm-explained.html
- https://www.hackerearth.com/practice/machine-learning/machine-learning-algorithms/ml-decision-tree/tutorial/
- https://www.lucidchart.com/pages/decision-tree
- https://www.javatpoint.com/machine-learning-decision-tree-classification-algorithm
- https://hbr.org/1964/07/decision-trees-for-decision-making
- https://www.geeksforgeeks.org/decision-tree/
- https://towardsdatascience.com/decision-trees-in-machine-learning-641b9c4e8052