Construction of Decision Tree: Gain ratio

আমরা এর আগে ID3 অ্যালগরিদম ব্যাবহার করে ডিসিশন ট্রি গঠন করেছি। এর জন্য আমরা এন্ট্রপি আর ইনফরমেশন গেইন ব্যাবহার করেছি। কিন্তু এর কিছু সমস্যা আছে। যেসব অ্যাট্রিবিউটের বেশি ইউনিক ভ্যালু থাকে, ID3 সেইসব অ্যাট্রিবিউটের প্রতি বায়াস থাকে। অর্থাৎ মাল্টি-ভ্যালুড অ্যাট্রিবিউটকে সে বেস্ট অ্যাট্রিবিউট হিসেবে ধরে নেয় এবং রুট নোডে অ্যাসাইন করতে চায়। যেমন যদি একটা ডাটাসেট ধরি আমরা, যেইটার অ্যাট্রিবিউট ও তার ভ্যালু নিম্নরূপ –

Age: Youth, Middle-aged, Old (৩টি ইউনিক ভ্যালু)
Color: Blue, Red, Green, Yellow (৪টি ইউনিক ভ্যালু)
Size: Small, Medium, Large (৩টি ইউনিক ভ্যালু)
Temperature: Hot, Cold (২টি ইউনিক ভ্যালু)

ধরি, এইখানে ‘Temperature’ কে রুট নোড ধরলে আমরা বেশি ভাল ডিসিশন ট্রি পাব, কিন্তু ID3 এইখানে ‘Color’ কে বেশি ফেভার করবে কারণ এই অ্যাট্রিবিউটের ইউনিক ভ্যালু বেশি।

এইরকম কেস অ্যাভয়েড করার জন্য C4.5 অ্যালগরিদম ব্যাবহার করা হয়। এই অ্যালগরিদমে গেইন রেশিও ASM হিসেবে ব্যাবহার করা হয়।

Gain ratio: অ্যাট্রিবিউটের ইনফরমেশন গেইনকে Split information দিয়ে ভাগ করলেই অ্যাট্রিবিউটের গেইন রেশিও পাওয়া যায়। যার গেইন রেশিও সবচেয়ে বেশি, সেইটাই আমরা বেস্ট অ্যাট্রিবিউট হিসেবে সিলেক্ট করব আর অ্যাসাইন করে দিব নোডে।

$SplitInfo_{A}(D) = - \sum \frac{|D_{j}|}{|D|} \times log_{2}( \frac{|D_{j}|}{|D|}) \phantom{xxxxxxx}$

$GainRatio(A) = \frac{Information Gain(A)}{SplitInfo(A)} \phantom{xxxxxxx}$

এখন একটা C4.5 অ্যালগরিদম ব্যাবহার করে ডিসিশন ট্রি গঠন করব।

Age	Income	Student	Credit rating	Buys Computer
Youth	High	No	Fair	No
Youth	High	No	Excellent	No
Middle-aged	High	No	Fair	Yes
Senior	Medium	No	Fair	Yes
Senior	Low	Yes	Fair	Yes
Senior	Low	Yes	Excellent	No
Middle-aged	Low	Yes	Excellent	Yes
Youth	Medium	No	Fair	No
Youth	Low	Yes	Fair	Yes
Senior	Medium	Yes	Fair	Yes
Youth	Medium	Yes	Excellent	Yes
Middle-aged	Medium	No	Excellent	Yes
Middle-aged	High	Yes	Fair	Yes
Senior	Medium	No	Excellent	No

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

Age: Youth, Middle-aged, Senior
Income: High, Medium, Low
Student: Yes, No
Credit rating: Fair, Excellent

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

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

Buys Computer
Yes	No
9	5

E(Buys Computer) = – P_yes log₂(P_yes) – P_no log₂(P_no)

= – 9/14 log₂ (9/14) – 5/14 log2 (5/14) = 0.94

এখন আমরা অ্যাট্রিবিউটগুলোর গেইন রেশিও বের করব। প্রথমে Age এর গেইন রেশিও বের করি।

		Buys Computer
		Yes	No
Age	Youth	2	3	5
	Middle-aged	4	0	4
	Senior	3	2	5
				14

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

E(Youth) = – 2/5 log₂(2/5) – 3/5 log₂(3/5) = 0.97
E(Middle-aged) = -4/4 log₂(4/4) – 0/4 log₂(0/4) = 0
E(Senior) = – 3/5 log₂(3/5) – 2/5 log₂(2/5) = 0.97

এখন টার্গেটের সাপেক্ষে Outlook এর এন্ট্রপি বের করি –

E(Buys Computer, Age) = P(Youth)E(Youth) + P(Middle-aged)E(Middle-aged) + P(Senior)E(Senior) = 5/14 * 0.97 + 4/14 * 0 + 5/14 * 0.97 = 0.69

Age এর গেইন রেশিও –

Information Gain (Age) = E(Buys Computer) – E(Buys Computer, Age) = 0.94 – 0.69 = 0.25

SplitInfo (Age) = -5/14 log2 (5/14) – 4/14 log2(4/14) – 5/14 log2 (5/14) = 1.58

GainRatio(Age) = Information Gain(Age) / SplitInfo (Age) = 0.25 / 1.58 = 0.16

এইভাবে প্রত্যেক অ্যাট্রিবিউটের গেইন রেশিও বের করলে পাই:

GainRatio(Age) = 0.16
GainRatio(Income) = 0.02
GainRatio(Student) = 0.15
GainRatio(Credit rating) = 0.05

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

এখন আমরা Youth ব্রাঞ্চের স্প্লিটিং করব। আমাদের এখন অ্যাট্রিবিউট বাকি আছে – Income, Student, Credit rating। আমরা তাইলে এখন Youth এর সাপেক্ষে Income এর ইনফরমেশন গেইন বের করি।

Age = Youth		Buys Computer
		Yes	No
Income	Low	1	0	1
	Medium	1	1	2
	High	0	2	2
				5

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

E(Low) = -1/1 log₂ (1/1) – 0/1 log₂ (0/1) = 0
E(Medium) = -1/2 log₂(1/2) – 1/2 log₂(1/2) = 1
E(High) = -0/2 log₂(0/2) – 2/2 log₂(2/2) = 0

এখন Youth এর ব্রাঞ্চের জন্য Income এর এন্ট্রপি –

E(Youth, Income) = P(Low)E(Low) + P(Medium)E(Medium) + P(High)E(High) = 1/5 * 0 + 2/5 * 1 + 2/5 * 0 = 0.4

Income এর গেইন রেশিও –

Information Gain (Income) = E(Youth) – E(Youth, Income) = 0.97 – 0.4 = 0.57

SplitInfo (Income) = -1/5 log2(1/5) – 2/5 log2 (2/5) – 2/5 log2(2/5) = 1.52

GainRatio (Income) = Information Gain (Income) / SplitInfo (Income) = 0.57 / 1.52 = 0.38

অনুরূপভাবে,

GainRatio(Student) = 1

GainRatio(Credit rating) = 0.23

তাহলে দেখা যাচ্ছে Student এর গেইন রেশিও সবচেয়ে বেশি। সুতরাং এইটা হবে আমাদের পরবর্তী নোড। ব্রাঞ্চগুলোর এন্ট্রপি বের করলে দেখব যে এইগুলাই আমাদের রুট নোড হবে।

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

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

Learn with Gauhar

Learn computer science with me in Bangla

Construction of Decision Tree: Gain ratio

Like this:

Leave a ReplyCancel reply

Share this:

Like this:

Leave a ReplyCancel reply