ডিসিশন ট্রি [Decision Tree, Machine Learning Algorithm]

০৯ ই সেপ্টেম্বর, ২০১৮ দুপুর ১:০৮

সেই ছোটবেলা থেকেই প্রতি মূহুর্তে বিভিন্ন বিষয়ে আমাদের সিদ্ধান্ত নিতে হয়। খুব ছোট বাচ্চারা যখন দোকান থেকে চিপস আর জ্যুস দুটোই কিনতে চায়, তাদের মা’রা ভারী গলায় বলে যেকোন একটা কিনে দেয়া হবে তাকে। ছোট মানুষ তখন সিদ্ধান্তহীনতায় ভুগে।

সুতরাং “সিদ্ধান্ত” নেয়ার সাথে আমরা খুব ছোটবেলা থেকেই পরিচিত। সঠিক সিদ্ধান্ত নেয়ার দক্ষতা আমাদের বয়সের সাথে বাড়তে থাকে। আমরা অনেক কিছু দেখি, শিখি। যেমন – বাংলাদেশের ক্রিকেটের উদাহরণ যদি নিয়ে আসি। তামিম ইকবাল যে ম্যাচে ভালো খেলে (মানে শত রান করে) বাংলাদেশ সেই ম্যাচ জিতে যায়। আবার তামিম যদি খারাপ খেলে কিন্তু সাকিব আল হাসান যদি ভালো খেলে তবে আবার বাংলাদেশ জিতে যায়। এই সিদ্ধান্তে আমরা পৌঁছেছি অনেকগুলো ম্যাচের ফলাফল জেনে।

এই জিনিসটাকেই একটু সুন্দর করে যদি তুলে ধরি ঠিক এইভাবে -


এই প্রেজেন্টেশনটাকে ট্রি প্রেজেন্ট্রেশন বলা হয়। বাস্তবে গাছের মূল (Root) মাটির নিচে থাকলেও এই ট্রি এর root থাকে সবার উপরে। আর সেখান থেকে ডালপালা (branches) বিস্তৃত হয়ে নিচের দিকে নামতে থাকে।

এইটাই ডিসিশন ট্রি (Decision Tree একটি classification algorithm) – একটা করে বৈশিষ্ট্য (attribute) এর মানের উপর নির্ভর করে একটা ফলাফলে আমরা পৌঁছে যাচ্ছি। বাস্তবে আমরা মানুষরা যেভাবে সিদ্ধান্ত নিয়ে থাকি ঠিক সেভাবেই।

ছবিটি যদি ব্যবহার করি আমাদের আসন্ন এশিয়া কাপের প্রথম ম্যাচে – তামিমের ব্যাটিং শেষে, তামিম কি সেঞ্চুরি করেছে? যদি করে থাকে তাহলে বাংলাদেশ জিতবে। আর যদি না করে থাকে সাকিবের ব্যাটিং পর্যন্ত অপেক্ষা করলাম।এরপর প্রশ্ন করলাম সাকিব কি সেঞ্চুরি করেছে? যদি করে থাকে তাহলে আমরা ম্যাচটা জিতবো নতুবা হারবো।

আমরা এর(Decision Tree) মাধ্যমে আমাদের সৃষ্ট মেশিনকেও সিদ্ধান্ত নিতে সাহায্য করতে পারি। বাংলাদেশের খেলার যে উদাহরণ দিলাম ঐটাকে যদি আরেকটু বর্ধিত করি – গত দুই বছরের বাংলাদেশের সকল ওয়ানডে ম্যাচের তথ্যের উপর নির্ভর করে যদি একটা এইরকম ট্রি নির্মাণ করি? যেই তথ্য তালিকায় প্রতিটি ম্যাচের ব্যাটিং বোলিং করা প্রত্যেক খেলোয়াড়ের তথ্য থাকবে এবং সেই ম্যাচের বাংলাদেশের ফলাফল থাকবে। অর্থাৎ খেলোয়াড়রা কেমন খেলেছিল এবং বাংলাদেশ ম্যাচটা জিতেছিল কি না?

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

আমরা এতক্ষণ দেখলাম এবং বুঝলাম ট্রি এর দ্বারা কিভাবে সিদ্ধান্ত নেয়া হয়। কিন্তু মূল চ্যালেঞ্জটা হচ্ছে সঠিকভাবে ট্রি-টা গঠন করা। যেভাবে গঠন করলে একের পর এক প্রশ্ন করে আমাদের সঠিক উত্তরের দিকে ধাবিত হওয়ার সম্ভাবনা বেশি থাকবে। আর এই ট্রি গঠনের জন্য আমাকে দেয়া হবে কোন নির্দিষ্ট সিদ্ধান্ত নেয়ার জন্য যথাপোযুক্ত পরিমাণ তথ্য।

ID3 Algorithm এর মাধ্যমে আমরা Decision Tree তৈরি করাটা দেখবো।

সেক্ষেত্রে আমরা বাংলাদেশের ক্রিকেট খেলা থেকে বের হয়ে টেনিস খেলার দিকে মুখ ফেরাবো এবং নিম্নোক্ত তথ্যের টেবিল ব্যবহার করবো –


এই টেবিলে আমাকে ১৪ দিনের তথ্য দেয়া আছে। প্রতিদিনের ৪ টা বৈশিষ্ট্য আমাকে দেয়া আছে যার উপর নির্ভর করে একজন টেনিস প্লেয়ার কোনদিন টেনিস খেলেছে কোনদিন খেলি নি। আমাকে এখন যদি কোন একদিনের এই ৪ টা বৈশিষ্ট্য দেয়া হয় তাহলে আমাকে বলতে হবে ঐদিন কি সেই টেনিস প্লেয়ার টেনিস খেলবে নাকি খেলবে না (অথবা সেইরকম কোনদিনে টেনিস খেলোয়াড়টা কি খেলেছিল নাকি খেলে নি)। ট্রি নির্মাণের সময় যে জিনিসটা খেয়াল রাখা হয় তা হলো leaf node (একেবারে শেষের সিদ্ধান্ত) যেন absolute হয়। অর্থাৎ হ্যাঁ ও না এর মিশেল থাকবে না। যেকোন একটা থাকবে।

এর জন্য আমাদের মোটে দুইটা সূত্র জানতে হবে –

Entropy(S) = ∑ – p(I) . log2p(I)

Gain(S, A) = Entropy(S) – ∑ [ p(S|A) . Entropy(S|A) ]

আরেকটা জিনিস হলো P(x) এর মানে x ঘটার সম্ভাবনা কত এবং P(x|y)  মানে y দেয়া থাকলে x ঘটার সম্ভাবনা কত (probability of x given y)

এখন ঠিক মতো বুঝা না গেলেও সমস্যা নেই, আমরা ধীরে ধীরে এগুচ্ছি। Entropy আর Gain এই দুইটা নাম নিয়ে টেনশনের কিছু নেই। নিচে আমরা যা কাজ করবো সব উপরের টেবিলের উপর নির্ভর করে।

প্রথমে আমরা টেবিল থেকে Decision এর Entropy বের করবো। Decision এর পসিবল ভ্যালু হলো দুটা – Yes or No.

Entropy(Decision) = – p(Yes) . log2p(Yes) – p(No) . log2p(No)

টেবিলে মোট instance(ঘটনা) আছে ১৪ টি, যার মধ্যে খেলা হয়েছে ৯ টিতে এবং খেলা হয় নি বাকি ৫ টিতে। তাহলে আমাদের সম্ভাব্যতার জ্ঞান থেকে বলতে পারি কোন একদিন খেলা হওয়ার সম্ভাবনা 9/14 এবং না হওয়ার সম্ভাবনা 5/14.

Entropy(Decision) = – (9/14) . log2(9/14) – (5/14) . log2(5/14)

                              = 0.940

এখন আমরা চারটা বৈশিষ্ট্যের মধ্যে যাচাই করবো কোনটাকে আমার root-এ দিলে সবচেয়ে ভালো হয়। যেই বৈশিষ্ট্যের Gain সবচেয়ে বেশি হবে সে-ই root  এ বসার যোগ্যতা অর্জন করবে।

Root এ বসার যোগ্যতা wind  এর আছে কিনা দেখি আমরা –

Gain(Decision, Wind) = Entropy(Decision) – ∑ [ p(Decision|Wind) . Entropy(Decision|Wind) ]

এখন wind এর আবার দুইটা ভ্যালু হতে পারে strong আবার weak. সুতরাং উপরের লাইনটি একটু পরিবর্তীত হয়ে( তার মানে wind এর দুইটা মানকে বিবেচনায় নিয়ে আমাদের এগুতে হবে) -  

Gain(Decision, Wind) = Entropy(Decision) – [ p(Decision|Wind=Weak) . Entropy(Decision|Wind=Weak) ] – [ p(Decision|Wind=Strong) . Entropy(Decision|Wind=Strong) ]

এখন আমাদের কাজ হবে Entropy(Decision|Wind=Weak) এবং Entropy(Decision|Wind=Strong) বের করা।

Entropy(Decision|Wind=Weak) = – p(No) . log2p(No) – p(Yes) . log2p(Yes)

এই সূত্রটা আগে একবার ব্যবহার করা হয়েছে। p(No) দ্বারা বুঝাচ্ছে না হওয়ার সম্ভাবনা কতটুকু যখন wind = weak. Wind= weak এমন instance(ঘটনা) আছে ৮ টি, যার মধ্যে ২ দিন খেলা হয় নি। তাই wind= weak হলে খেলা না হওয়ার সম্ভাবনা 2/8

Entropy(Decision|Wind=Weak) = – (2/8) . log2(2/8) – (6/8) . log2(6/8)

= 0.811

অনুরূপভাবে –

Entropy(Decision|Wind=Strong) = – p(No) . log2p(No) – p(Yes) . log2p(Yes)

 = – (3/6) . log2(3/6) – (3/6) . log2(3/6)

 = 1

এখন ফিরে যাই সেই বিদঘুটে দেখনেওয়ালা সূত্রের কাছে এবং বসিয়ে দেই এতক্ষণ ধরে বের করা মানগুলো –

Gain(Decision, Wind) = Entropy(Decision) – [ p(Decision|Wind=Weak) . Entropy(Decision|Wind=Weak) ] – [ p(Decision|Wind=Strong) . Entropy(Decision|Wind=Strong) ]

= 0.940 – [ (8/14) . 0.811 ] – [ (6/14). 1]

= 0.048

একইভাবে বাকি তিনটা বৈশিষ্ট্যের Gain হিসেব করে ফেলি –

1- Gain(Decision, Outlook) = 0.246

2- Gain(Decision, Temperature) = 0.029

3- Gain(Decision, Humidity) = 0.151

এখন দেখবো কোনটার Gain সবচেয়ে বেশি সেটাকেই আমি আমার ডিসিশন ট্রি-য়ের root এর আসনে বসাবো।

Outlook দিয়ে আমার ডিসিশন ট্রি যদি শুরু করি সেক্ষেত্রে আমার সঠিক উত্তর পাবার সম্ভাবনা বেশি হবে।একটা যখন ফিক্স করে ফেললাম, কাজ কেবল শুরু। আপাতত এই পর্যায়ে ট্রি নিম্নোক্ত দশায় আছে -


এখন পুনরায় Gain(Outlook=Sunny|Temperature), Gain(Outlook=Sunny|Humidity), Gain(Outlook=Sunny|Wind) বের করবো । যেটার গেইন বেশি হবে সেটা Sunny হওয়ার পরে কি চেক করতে হবে সেটা নির্দেশ দিবে। এভাবে ধীরে ধিরে ট্রি-টা তৈরি হতে থাকবে।

সবশেষে ছবিটা হবে এই ধরনের –



এখন আমরা টেবিল থেকে ১৩তম দিনের ইনফো দিয়ে ট্রি-টাকে একটু চেক করি। প্রথমে Outlook = Overcast আছে, তাহলে ট্রি থেকে পাই ঐদিন খেলা হবে, দারুন। আবার টেবিলেও দেয়া আছে ঐদিন খেলা হবে।

এইবার outllok = sunny আছে এমন একটা দিনের তথ্য নেই টেবিল থেকে। ৮ম দিনের তথ্য দিয়ে চেক করে দেখি –

Outlook = Sunny আছে সুতরাং ট্রি-এর বামে যাবো। এইবার humidity চেক করবো। Humidity = High আছে সুতরাং ঐদিন খেলা হবে না। টেবিলে গিয়ে দেখি, হ্যাঁ ঐদিন খেলা হয় নি।

পুরোটা হাতে লিখে বুঝিয়ে সমাধান করে দেয়া সময় সাপেক্ষ ব্যাপার তাছাড়া লিখাটাকেও অহেতুক বড় করা হবে। তার চেয়ে একটা জিনিস বুঝিয় দিলে, সেই জ্ঞান দিয়ে যদি পরে নিজে থেকে পারা যায়, সেটাই উত্তম।

লিখাটার ID3 algorithm বুঝানোর জন্য আমি যে ছবি এবং ডাটা এর টেবিল ব্যবহার করেছি তা নিম্নোক্ত website থেকে –

A Step by Step ID3 Decision Tree Example

আরো কিছু প্রয়োজনীয় লিংক ডিসিশন ট্রি কোডিং কিংবা বোঝার জন্য –

1 -  Visualizing a Decision Tree - Machine Learning Recipes #2

2 - Let’s Write a Decision Tree Classifier from Scratch - Machine Learning Recipes
3 - Learning: Identification Trees, Disorder

লিখাটা পড়ার জন্য ধন্যবাদ  

৩ টি +০/-০