আমরা জানি ডিসিশন ট্রি গঠনের সময় আমরা ডিসিশন নোডগুলোতে বিভিন্ন অ্যাট্রিবিউট অ্যাসাইন করি। কিন্তু কোন নোডে কোনটা অ্যাসাইন করতে হবে, এইটা বুঝব কি করে? যদি আমরা র‍্যান্ডমলি অ্যাসাইন করি, তাহলে কি হবে? 

টার্গেট ভ্যারিয়াবল (যেইটার ভ্যালু আমরা প্রেডিক্ট করতে চাই) আর ফিচার ভ্যারিয়াবলগুলোর (বাকি সব অ্যাট্রিবিউট) মধ্যে সমান সম্পর্ক থাকেনা। কিছু কিছু ফিচার টার্গেট ভ্যারিয়াবলের ভ্যালু প্রেডিক্ট করতে বেশি কন্ট্রিবিউট করে, আর কিছু কিছু কম করে। এজন্য ডিসিশন ট্রি গঠনের সময় র‍্যান্ডমলি নোডগুলোতে অ্যাট্রিবিউট অ্যাসাইন না করে, একটা নিয়ম মেনে অ্যাসাইন করা হয় যেন আমাদের ডিসিশন ট্রি সুন্দরভাবে কাজ করতে পারে। এই উদ্দেশ্যে আমরা অ্যাট্রিবিউট সিলেকশন মেজার (ASM) ব্যাবহার করে বেস্ট অ্যাট্রিবিউট সিলেক্ট করি। 

ডিসিশন ট্রি গঠনের একটা অ্যালগরিদম ID3। ID3 (Iterative Dichotomiser) একটা টপ-ডাউন গ্রিডি সার্চ অ্যাপ্রোচ ফলো করে। সম্ভাব্য সকল ব্রাঞ্চের মধ্য দিয়ে গ্রিডি সার্চ করে ব্যাকট্র্যাকিং ছাড়া। ASM হিসেবে এই অ্যালগরিদম এন্ট্রপি আর ইনফরমেশন গেইন ব্যাবহার করে। বেস্ট অ্যাট্রিবিউট হবে যেইটার এন্ট্রপি সবচেয়ে কম এবং ইনফরমেশন গেইন সবচেয়ে বেশি। 

Entropy: কোন অ্যাট্রিবিউটের ইম্পুরিটি মেজার করে। ডাটার মধ্যে র‍্যান্ডমনেসকে বুঝায়। এন্ট্রপি ক্যালকুলেট করার সূত্র –

E(S) = – P_yes log₂ (P_yes) – P_no log₂ (P_no)

এইখানে,

E(S) = S অ্যাট্রিবিউটের এন্ট্রপি, S = S অ্যাট্রিবিউটের স্যাম্পল সংখ্যা, P_yes = হ্যাঁ হওয়ার প্রবাবিলিটি, P_no = না হওয়ার প্রবাবিলিটি

এন্ট্রপির ভ্যালু 0 থেকে 1 এর মধ্যে। যদি S এর সব মেম্বার একই ক্লাসের মেম্বার হয়, তাইলে এন্ট্রপি হবে 0। যদি ‘yes’ এবং ‘no’ উভয় ক্লাসে S এর সমান সংখ্যক মেম্বার থাকে, তাইলে এন্ট্রপি হবে 1। ID3 এর রুল – এন্ট্রপি 0 হলে, সেইটা একটা লিফ নোড। আর এন্ট্রপি 0 এর থেকে বেশি হলে আরও স্প্লিটিং দরকার। 

কোন ফিচারের সাপেক্ষে এন্ট্রপি বের করার জন্য –

E(T,X) = Σ P(X) E(X)

এইখানে, 

X = যে অ্যাট্রিবিউটের এন্ট্রপি বের করব, T = যে ফিচারের সাপেক্ষে বের করব, P(X) = অ্যাট্রিবিউটের ভ্যালুগুলোর প্রবাবিলিটি, E(X) = অ্যাট্রিবিউটের ভ্যালুগুলোর এন্ট্রপি

Information Gain: কোন অ্যাট্রিবিউটের ভিত্তিতে এন্ট্রপির পরিবর্তন মেজার করে। কোন ফিচার একটা ক্লাসের ব্যাপারে কি পরিমাণ ইনফরমেশন দেয়, সেইটা ক্যালকুলেট করে দেয়। ইনফরমেশন গেইন ক্যালকুলেট করার সূত্র –

Information Gain (T, X) = Entropy(T) – Entropy(T, X)

এইখানে, T = ফিচার ভ্যারিয়াবল এবং X = অ্যাট্রিবিউট

এখন আমরা প্রদত্ত ডাটাসেট থেকে ID3 অ্যালগরিদম ব্যাবহার করে ডিসিশন ট্রি গঠন করব। 

Outlook	Temperature	Humidity	Windy	Play Golf
Sunny	Hot	High	Weak	No
Sunny	Hot	High	Strong	No
Overcast	Hot	High	Weak	Yes
Rainy	Mild	High	Weak	Yes
Rainy	Cool	Normal	Weak	Yes
Rainy	Cool	Normal	Strong	No
Overcast	Cool	Normal	Strong	Yes
Sunny	Mild	High	Weak	No
Sunny	Cool	Normal	Weak	Yes
Rainy	Mild	Normal	Weak	Yes
Sunny	Mild	Normal	Strong	Yes
Overcast	Mild	High	Strong	Yes
Overcast	Hot	Normal	Weak	Yes
Rainy	Mild	High	Strong	No

এইখানে আমাদের অ্যাট্রিবিউট ও তাদের ভ্যালু:

• Outlook: Sunny, Overcast, Rainy
• Humidity: High, Normal
• Wind: Weak, Strong
• Temperature: Hot, Mild, Cold

আমাদের টার্গেট ক্লাস – Play Golf: Yes, No

প্রথমে টার্গেট ক্লাসের এন্ট্রপি বের করি- 

এখন আমরা বের করি কোনটা আমাদের রুট নোডে অ্যাসাইন করতে হবে। এর জন্য প্রত্যেকটা অ্যাট্রিবিউটের ইনফরমেশন গেইন বের করতে হবে। প্রথমে আমরা Outlook এর ইনফরমেশন গেইন বের করি। 

		Play Golf
		Yes	No
Outlook	Sunny	2	3	5
	Overcast	4	0	4
	Rainy	3	2	5
				14

প্রত্যেক ব্রাঞ্চের জন্য এন্ট্রপি বের করি – 

Outlook এর ইনফরমেশন গেইন –

Information Gain (Outlook) = E(Play Golf) – E(Play Golf, Outlook)                                                                                                                       = 0.94 – 0.69 = 0.25

প্রত্যেক অ্যাট্রিবিউটের ইনফরমেশন গেইন বের করলে, আমরা পাই – 

• Information Gain (Outlook) = 0.25
• Information Gain (Humidity) = 0.15
• Information Gain (Windy) = 0.05
• Information Gain (Temperature) = 0.03

এইখানে আমরা দেখতে পাচ্ছি Outlook এর ইনফরমেশন গেইন সবচেয়ে বেশি, সুতরাং এইটাই আমরা আমাদের ডিসিশন ট্রি এর রুট নোডে অ্যাসাইন করব। আমরা আরও দেখেছি যে Overcast ব্রাঞ্চের এন্ট্রপি 0, সুতরাং এইটাই হবে আমাদের লিফ নোড। বাকি দুই ব্রাঞ্চের এন্ট্রপি 0 এর থেকে বেশি, তাই আরও স্প্লিটিং হবে।

এখন আমরা Sunny ব্রাঞ্চের স্প্লিটিং করব। আমাদের এখন অ্যাট্রিবিউট বাকি আছে – Humidity, Windy, Temperature। আমরা তাইলে এখন Sunny এর সাপেক্ষে Humidity এর ইনফরমেশন গেইন বের করি। 

Outlook = Sunny		Play Golf
		Yes	No
Humidity	High	0	3	3
	Normal	2	0	2
				5

প্রত্যেক ব্রাঞ্চের জন্য এন্ট্রপি বের করি –

• E(High) = – 0/3 log₂ (0/3) – 3/3 log₂ (3/3) = 0
• E(Normal) = – 2/2 log₂ (2/2) – 0/2 log₂ (0/2) = 0

এখন Humidity এর এন্ট্রপি –

E(Sunny, Humidity) = P(High)E(High) + P(Normal)E(Normal)                                                                                                                       = 3/5 * 0 + 2/5 * 0 = 0

Humidity এর ইনফরমেশন গেইন –

Information Gain (Humidity) = E(Sunny) – E(Sunny, Humidity) = 0.97 – 0 = 0.97

অনুরূপভাবে,

• Information Gain (Windy) = 0.02
• Information Gain (Temperature) = 0.57

তাহলে আমাদের এরপরের নোড হবে Humidity। যেহেতু High ও Normal ব্রাঞ্চ দুইটার এন্ট্রপি 0, তাই আর স্প্লিটিং এর দরকার নাই। এইটাই হবে লিফ নোড।

অনুরূপভাবে আমরা পরবর্তী ডিসিশন নোড পাই হল Windy। এর ব্রাঞ্চের দুইটার এন্ট্রপি 0, তাই আর স্প্লিটিং হবেনা। আমরা এইখানেও লিফ নোড পেয়ে গেলাম। আমাদের ডিসিশন ট্রি গঠন সম্পূর্ণ হল। 

আরও পড়তে চাইলে:

• http://monaen.github.io/PrivacyDecisionTree/
• http://www2.cs.uregina.ca/~dbd/cs831/notes/ml/dtrees/c4.5/c4.5_prob1.html
• 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