সিদ্ধান্ত ট্রি অ্যালগরিদম - একটি সম্পূর্ণ গাইড

এই নিবন্ধটি একটি অংশ হিসাবে প্রকাশিত হয়েছিল ডেটা সায়েন্স ব্লগাথন

এখন অবধি আমরা লিনিয়ার রিগ্রেশন, লজিস্টিক রিগ্রেশন সম্পর্কে শিখেছি এবং সেগুলি বোঝা বেশ কঠিন ছিল। এখন ডিসিশন ট্রি'স দিয়ে শুরু করা যাক এবং আমি আপনাকে আশ্বস্ত করছি যে এটি সম্ভবত মেশিন লার্নিংয়ের সবচেয়ে সহজ অ্যালগরিদম। এখানে খুব বেশি গণিত জড়িত নেই। যেহেতু এটি ব্যবহার করা এবং ব্যাখ্যা করা খুবই সহজ, এটি মেশিন লার্নিং-এ ব্যবহৃত সবচেয়ে ব্যাপকভাবে ব্যবহৃত এবং ব্যবহারিক পদ্ধতিগুলির মধ্যে একটি।

বিষয়বস্তু

1. সিদ্ধান্ত গাছ কি?

2. একটি সিদ্ধান্ত গাছের উদাহরণ

3। এনট্রপি

4. তথ্য লাভ

5. কখন বিভাজন বন্ধ করবেন?

6. কিভাবে ওভারফিটিং বন্ধ করবেন?

• সর্বোচ্চ গভীরতা
• min_samples_split
• min_samples_leaf
• সর্বোচ্চ_ বৈশিষ্ট্য

7. ছাঁটাই

• ছাঁটাই-পরবর্তী
• প্রি-প্রুনিং

8. শেষ নোট

একটি সিদ্ধান্ত গাছ কি?

এটি এমন একটি টুল যা বিভিন্ন এলাকায় বিস্তৃত অ্যাপ্লিকেশন রয়েছে। ডিসিশন ট্রি শ্রেণীবিভাগের পাশাপাশি রিগ্রেশন সমস্যার জন্য ব্যবহার করা যেতে পারে। নামটি নিজেই পরামর্শ দেয় যে এটি বৈশিষ্ট্য-ভিত্তিক বিভাজনের একটি সিরিজের ফলে ভবিষ্যদ্বাণীগুলি দেখানোর জন্য একটি গাছের কাঠামোর মতো একটি ফ্লোচার্ট ব্যবহার করে। এটি একটি রুট নোড দিয়ে শুরু হয় এবং পাতার দ্বারা করা সিদ্ধান্তের সাথে শেষ হয়।

চিত্র 1

সিদ্ধান্ত গাছ সম্পর্কে আরও জানার আগে আসুন কিছু পরিভাষার সাথে পরিচিত হই।

রুট নোড - এটি একটি সিদ্ধান্ত গাছের শুরুতে উপস্থিত নোড এই নোড থেকে জনসংখ্যা বিভিন্ন বৈশিষ্ট্য অনুসারে বিভাজন শুরু করে।

সিদ্ধান্ত নোড রুট নোডগুলিকে বিভক্ত করার পর আমরা যে নোডগুলি পাই তাকে ডিসিশন নোড বলে

লিফ নোডস - যে নোডগুলিকে আরও বিভক্ত করা সম্ভব নয় তাকে লিফ নোড বা টার্মিনাল নোড বলে

উপ-গাছ – যেমন একটি গ্রাফের একটি ছোট অংশকে সাব-গ্রাফ বলা হয়, একইভাবে এই সিদ্ধান্ত গাছের একটি উপ-বিভাগকে সাব-ট্রি বলা হয়।

কেঁটে সাফ - ওভারফিটিং বন্ধ করার জন্য কিছু নোড কাটা ছাড়া কিছুই নয়।

চিত্র 2

সিদ্ধান্ত গাছের উদাহরণ

আসুন একটি উদাহরণের সাহায্যে সিদ্ধান্ত বৃক্ষগুলি বুঝতে পারি।

চিত্র 3

ডিসিশন ট্রিগুলি উল্টোদিকে থাকে যার অর্থ মূলটি শীর্ষে থাকে এবং তারপরে এই মূলটি বিভিন্ন নোডে বিভক্ত হয়। সিদ্ধান্ত গাছ সাধারণ মানুষের পদে যদি-অন্যথায় বিবৃতিগুলির একটি গুচ্ছ ছাড়া আর কিছুই নয়। এটি শর্তটি সত্য কিনা তা পরীক্ষা করে এবং যদি এটি হয় তবে এটি সেই সিদ্ধান্তের সাথে সংযুক্ত পরবর্তী নোডে যায়।

নীচের চিত্রে গাছটি প্রথমে জিজ্ঞাসা করবে আবহাওয়া কী? এটা কি রোদ, মেঘলা, নাকি বৃষ্টি? যদি হ্যাঁ হয় তবে এটি পরবর্তী বৈশিষ্ট্যে যাবে যা আর্দ্রতা এবং বায়ু। এটি আবার পরীক্ষা করবে যে একটি শক্তিশালী বাতাস আছে নাকি দুর্বল, যদি এটি একটি দুর্বল বাতাস হয় এবং এটি বৃষ্টি হয় তবে ব্যক্তিটি গিয়ে খেলতে পারে।

চিত্র 4

আপনি কি উপরের ফ্লোচার্টে কিছু লক্ষ্য করেছেন? আমরা দেখতে যে যদি আবহাওয়া মেঘলা তাহলে আমাদের খেলতে যেতে হবে। কেন এটা আরো বিভক্ত না? কেন এটা সেখানে থেমে গেল?

এই প্রশ্নের উত্তর দেওয়ার জন্য, আমাদের আরও কয়েকটি ধারণা সম্পর্কে জানতে হবে যেমন এনট্রপি, তথ্য লাভ এবং জিনি সূচক। কিন্তু সহজ কথায়, আমি এখানে বলতে পারি যে প্রশিক্ষণ ডেটাসেটের আউটপুট সবসময় মেঘলা আবহাওয়ার জন্য হ্যাঁ হয়, যেহেতু এখানে কোনো বিশৃঙ্খলা নেই আমাদের নোডটিকে আরও বিভক্ত করার দরকার নেই।

মেশিন লার্নিং এর লক্ষ্য হল ডেটাসেট থেকে অনিশ্চয়তা বা ব্যাধি কমানো এবং এর জন্য আমরা ডিসিশন ট্রি ব্যবহার করি।

এখন আপনি নিশ্চয়ই ভাবছেন কিভাবে বুঝবো রুট নোড কি হওয়া উচিত? সিদ্ধান্ত নোড কি হওয়া উচিত? আমি কখন বিভক্ত হওয়া বন্ধ করব? এটি নির্ধারণ করার জন্য, "এনট্রপি" নামে একটি মেট্রিক রয়েছে যা ডেটাসেটের অনিশ্চয়তার পরিমাণ।

এনট্রপি

এনট্রপি আমাদের ডেটাসেট বা ব্যাধির পরিমাপের অনিশ্চয়তা ছাড়া আর কিছুই নয়। আমি একটি উদাহরণের সাহায্যে এটি ব্যাখ্যা করার চেষ্টা করি।

ধরুন আপনার একদল বন্ধু আছে যারা সিদ্ধান্ত নেয় তারা কোন সিনেমাটি রবিবার একসাথে দেখতে পারবে। সিনেমার জন্য 2টি পছন্দ আছে, একটি হল "লুসি" এবং দ্বিতীয় হয় "টাইটানিক" এবং এখন প্রত্যেককে তাদের পছন্দ বলতে হবে। সবাই তাদের উত্তর দেওয়ার পরে আমরা তা দেখতে পাই "লুসি" 4 ভোট পায় এবং "টাইটানিক" পেয়েছে 5 ভোট. আমরা এখন কোন সিনেমা দেখি? এখন 1টি সিনেমা বেছে নেওয়া কি কঠিন নয় কারণ উভয় সিনেমার ভোট কিছুটা সমান।

এটাকেই আমরা বিশৃঙ্খলা বলি, উভয় সিনেমার জন্য সমান সংখ্যক ভোট রয়েছে এবং আমরা আসলেই ঠিক করতে পারি না যে আমাদের কোন সিনেমা দেখা উচিত। "লুসি" এর জন্য 8 এবং "টাইটানিক" এর জন্য 2 হলে এটি অনেক সহজ হত। এখানে আমরা সহজেই বলতে পারি যে বেশিরভাগ ভোট "লুসি" এর জন্য তাই সবাই এই মুভিটি দেখবে।

একটি সিদ্ধান্ত গাছে, আউটপুট বেশিরভাগই "হ্যাঁ" বা "না"

এনট্রপির সূত্রটি নীচে দেখানো হয়েছে:

এখানে পি₊ ইতিবাচক শ্রেণীর সম্ভাবনা

p_- নেতিবাচক শ্রেণীর সম্ভাবনা

S হল প্রশিক্ষণ উদাহরণের উপসেট

কিভাবে সিদ্ধান্ত গাছ এনট্রপি ব্যবহার করে?

এখন আমরা জানি এনট্রপি কী এবং এর সূত্র কী, এর পরে, আমাদের জানতে হবে যে এই অ্যালগরিদমে এটি ঠিক কীভাবে কাজ করে।

এনট্রপি মূলত একটি নোডের অপবিত্রতা পরিমাপ করে। অপবিত্রতা হল এলোমেলোতার মাত্রা; এটি আমাদের ডেটা কতটা এলোমেলো তা বলে। ক বিশুদ্ধ উপ-বিভক্ত মানে হয় আপনি "হ্যাঁ" পাচ্ছেন, অথবা আপনার "না" পাওয়া উচিত।

ধরুন ক বৈশিষ্ট্য 8টি "হ্যাঁ" এবং 4টি "না" আছে, প্রথমবার বাম নোডটি বিভক্ত করার পরে 5 'হ্যাঁ' এবং 2 'না' পায় ডান নোড যেখানে পায় 3 'হ্যাঁ' এবং 2 'না'।

আমরা এখানে দেখি বিভাজন শুদ্ধ নয় কেন? কারণ আমরা এখনও উভয় নোডে কিছু নেতিবাচক ক্লাস দেখতে পারি। একটি সিদ্ধান্ত গাছ তৈরি করার জন্য, আমাদের প্রতিটি বিভাজনের অশুচিতা গণনা করতে হবে এবং যখন বিশুদ্ধতা 100% হয়, তখন আমরা এটিকে একটি পাতার নোড হিসাবে তৈরি করি।

বৈশিষ্ট্য 2 এবং বৈশিষ্ট্য 3 এর অশুদ্ধতা পরীক্ষা করতে আমরা এনট্রপি সূত্রের সাহায্য নেব।

ছবির উৎস: লেখক

বৈশিষ্ট্য 3 এর জন্য,

আমরা গাছ থেকেই পরিষ্কারভাবে দেখতে পাচ্ছি যে বাম নোডে ডান নোডের তুলনায় কম এনট্রপি বা বেশি বিশুদ্ধতা রয়েছে যেহেতু বাম নোডের "হ্যাঁ" সংখ্যা বেশি এবং এখানে সিদ্ধান্ত নেওয়া সহজ।

সর্বদা মনে রাখবেন যে এনট্রপি যত বেশি হবে বিশুদ্ধতা কম হবে এবং অপবিত্রতা তত বেশি হবে।

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

এর জন্য, আমরা "তথ্য লাভ" নামে একটি নতুন মেট্রিক নিয়ে এসেছি যা আমাদের বলে যে প্যারেন্ট এনট্রপি কতটা কমেছে কিছু বৈশিষ্ট্যের সাথে বিভক্ত করার পরে।

তথ্য লাভ

তথ্য লাভ কিছু বৈশিষ্ট্য দেওয়া অনিশ্চয়তা হ্রাস পরিমাপ করে এবং এটি একটি সিদ্ধান্তকারী ফ্যাক্টর যার জন্য একটি সিদ্ধান্ত নোড বা রুট নোড হিসাবে বৈশিষ্ট্য নির্বাচন করা উচিত।

এটি সম্পূর্ণ ডেটাসেটের এনট্রপি - কিছু বৈশিষ্ট্য দেওয়া ডেটাসেটের এনট্রপি।

এটি আরও ভালভাবে বোঝার জন্য একটি উদাহরণ বিবেচনা করা যাক:
ধরুন আমাদের সমগ্র জনসংখ্যার মোট 30টি উদাহরণ রয়েছে। ডেটাসেটটি ভবিষ্যদ্বাণী করে যে ব্যক্তি জিমে যাবে কি না। ধরা যাক 16 জন লোক জিমে যায় এবং 14 জন যায় না

সে জিমে যাবে কি না তা ভবিষ্যদ্বাণী করার জন্য এখন আমাদের কাছে দুটি বৈশিষ্ট্য রয়েছে।

বৈশিষ্ট্য 1 হল "শক্তি" যা দুটি মান লাগে "উচু এবং নিচু"

বৈশিষ্ট্য 2 হল "অনুপ্রেরণা" যা 3 টি মান নেয় "কোন অনুপ্রেরণা নেই", "নিরপেক্ষ" এবং "অত্যন্ত অনুপ্রাণিত"।

এই 2টি বৈশিষ্ট্য ব্যবহার করে আমাদের সিদ্ধান্ত গাছটি কীভাবে তৈরি করা হবে তা দেখা যাক। কোন বৈশিষ্ট্যটি রুট নোড হওয়া উচিত এবং বিভক্ত হওয়ার পরে কোন বৈশিষ্ট্যটি স্থাপন করা উচিত তা নির্ধারণ করতে আমরা তথ্য লাভ ব্যবহার করব।

ছবির উৎস: লেখক

আসুন এনট্রপি গণনা করা যাক:

প্রতিটি নোডের এনট্রপির ওজনযুক্ত গড় দেখতে আমরা নিম্নরূপ করব:

এখন আমাদের কাছে E(Parent) এবং E(Parent|Energy) এর মান আছে, তথ্য লাভ হবে:

আমাদের প্যারেন্ট এনট্রপি 0.99 এর কাছাকাছি ছিল এবং তথ্য লাভের এই মানটি দেখার পরে, আমরা বলতে পারি যে ডেটাসেটের এনট্রপি 0.37 কমে যাবে যদি আমরা আমাদের রুট নোড হিসাবে "শক্তি" তৈরি করি।

একইভাবে, আমরা অন্যান্য বৈশিষ্ট্য "প্রেরণা" দিয়ে এটি করব এবং এর তথ্য লাভের হিসাব করব।

ছবির উৎস: লেখক

এখানে এনট্রপি গণনা করা যাক:

প্রতিটি নোডের এনট্রপির ওজনযুক্ত গড় দেখতে আমরা নিম্নরূপ করব:

এখন আমাদের কাছে E(Parent) এবং E(Parent|Motivation) এর মান আছে, তথ্য লাভ হবে:

আমরা এখন দেখতে পাচ্ছি যে "এনার্জি" বৈশিষ্ট্যটি "অনুপ্রেরণা" বৈশিষ্ট্যের চেয়ে 0.37 বেশি হ্রাস দেয়। তাই আমরা সেই বৈশিষ্ট্যটি নির্বাচন করব যা সর্বাধিক তথ্য লাভ করে এবং তারপর সেই বৈশিষ্ট্যের উপর ভিত্তি করে নোডকে বিভক্ত করব।

এই উদাহরণে "শক্তি" হবে আমাদের রুট নোড এবং আমরা সাব-নোডের জন্য একই কাজ করব। এখানে আমরা দেখতে পাচ্ছি যে যখন শক্তি "উচ্চ" হয় তখন এনট্রপি কম থাকে এবং তাই আমরা বলতে পারি একজন ব্যক্তি উচ্চ শক্তি থাকলে অবশ্যই জিমে যাবেন, কিন্তু শক্তি কম হলে কী হবে? আমরা আবার নতুন বৈশিষ্ট্যের উপর ভিত্তি করে নোডকে বিভক্ত করব যা হল "প্রেরণা"।

কখন বিভাজন বন্ধ করবেন?

আপনি অবশ্যই নিজেকে এই প্রশ্নটি জিজ্ঞাসা করছেন যে আমরা কখন আমাদের গাছ বাড়ানো বন্ধ করব? সাধারণত, বাস্তব-বিশ্বের ডেটাসেটগুলিতে প্রচুর সংখ্যক বৈশিষ্ট্য থাকে, যার ফলে প্রচুর পরিমাণে বিভাজন হয়, যা ফলস্বরূপ একটি বিশাল গাছ দেয়। এই ধরনের গাছ তৈরি হতে সময় লাগে এবং অতিরিক্ত ফিটিং হতে পারে। তার মানে গাছটি প্রশিক্ষণ ডেটাসেটে খুব ভাল নির্ভুলতা দেবে কিন্তু পরীক্ষার ডেটাতে খারাপ নির্ভুলতা দেবে।

হাইপারপ্যারামিটার টিউনিংয়ের মাধ্যমে এই সমস্যাটি মোকাবেলা করার অনেক উপায় রয়েছে। আমরা ব্যবহার করে আমাদের সিদ্ধান্ত গাছের সর্বোচ্চ গভীরতা সেট করতে পারি সর্বোচ্চ গভীরতা প্যারামিটার এর মান তত বেশি সর্বোচ্চ গভীরতা, আপনার গাছ আরো জটিল হবে. ট্রেনিং এরর অফকোর্স কমে যাবে যদি আমরা বাড়াই সর্বোচ্চ গভীরতা মান কিন্তু যখন আমাদের পরীক্ষার ডেটা ছবিতে আসে, তখন আমরা খুব খারাপ নির্ভুলতা পাব। তাই আপনার এমন একটি মান দরকার যা আমাদের ডেটাকে অত্যধিক ফিট করবে না এবং এটির জন্য আপনি GridSearchCV ব্যবহার করতে পারেন।

আরেকটি উপায় হল প্রতিটি স্পিল্টের জন্য নমুনার ন্যূনতম সংখ্যা সেট করা। এটি দ্বারা চিহ্নিত করা হয় min_samples_split. এখানে আমরা একটি স্পল্ট করার জন্য প্রয়োজনীয় নমুনাগুলির ন্যূনতম সংখ্যা নির্দিষ্ট করি। উদাহরণস্বরূপ, আমরা একটি সিদ্ধান্তে পৌঁছানোর জন্য সর্বনিম্ন 10টি নমুনা ব্যবহার করতে পারি। তার মানে যদি একটি নোডে 10 টির কম নমুনা থাকে তবে এই প্যারামিটারটি ব্যবহার করে, আমরা এই নোডটির আরও বিভাজন বন্ধ করতে পারি এবং এটিকে একটি পাতার নোড করতে পারি।

আরও হাইপারপ্যারামিটার রয়েছে যেমন:

min_samples_leaf - লিফ নোডে থাকা প্রয়োজনীয় নমুনাগুলির ন্যূনতম সংখ্যক প্রতিনিধিত্ব করে। আপনি যত বেশি সংখ্যা বাড়াবেন, ওভারফিটিং হওয়ার সম্ভাবনা তত বেশি।

সর্বোচ্চ_ বৈশিষ্ট্য - সেরা বিভাজন খুঁজতে গিয়ে কোন বৈশিষ্ট্যগুলি বিবেচনা করতে হবে তা নির্ধারণ করতে এটি আমাদের সাহায্য করে৷

এই হাইপারপ্যারামিটার সম্পর্কে আরও পড়তে আপনি এটি পড়তে পারেন এখানে.

কেঁটে সাফ

এটি আরেকটি পদ্ধতি যা আমাদের ওভারফিটিং এড়াতে সাহায্য করতে পারে। এটি উল্লেখযোগ্য নয় এমন নোড বা সাব-নোডগুলি কেটে গাছের কর্মক্ষমতা উন্নত করতে সাহায্য করে। এটি শাখাগুলিকে সরিয়ে দেয় যার গুরুত্ব খুব কম।

ছাঁটাই করার জন্য প্রধানত 2 টি উপায় রয়েছে:

(ঝ) প্রি-প্রুনিং - আমরা আগে গাছের বৃদ্ধি বন্ধ করতে পারি, যার মানে কম গুরুত্ব থাকলে আমরা নোড ছাঁটাই/মুছে ফেলতে/কাটতে পারি বৃদ্ধির সময় গাছটি.

(২) ছাঁটাই-পরবর্তী - একবার আমাদের গাছ তার গভীরতায় নির্মিত হয়, আমরা তাদের তাত্পর্যের উপর ভিত্তি করে নোডগুলি ছাঁটাই শুরু করতে পারি।

শেষটীকা

সংক্ষেপে, এই নিবন্ধে আমরা সিদ্ধান্ত গাছ সম্পর্কে শিখেছি। কিসের ভিত্তিতে গাছটি নোডগুলিকে বিভক্ত করে এবং কীভাবে ওভারফিটিং বন্ধ করা যায়। শ্রেণীবিন্যাস সমস্যার ক্ষেত্রে কেন লিনিয়ার রিগ্রেশন কাজ করে না।

পরের প্রবন্ধে, আমি র‍্যান্ডম ফরেস্ট ব্যাখ্যা করব, যা আবার ওভারফিটিং এড়াতে একটি নতুন কৌশল।
সিদ্ধান্ত গাছের সম্পূর্ণ বাস্তবায়ন পরীক্ষা করতে অনুগ্রহ করে আমার দেখুন গিটহাব সংগ্রহস্থল।

নীচের মন্তব্যে আপনার কোন প্রশ্ন থাকলে আমাকে জানান।

লেখক সম্পর্কে

এই নিবন্ধে প্রদর্শিত মিডিয়াগুলি অ্যানালিটিক্স বিদ্যা মালিকানাধীন নয় এবং এটি লেখকের বিবেচনার ভিত্তিতে ব্যবহৃত হয়।

চিত্র উত্স

1. ছবি 1 – https://wiki.pathmind.com/decision-tree
2. ছবি 2 – https://wiki.pathmind.com/decision-tree
3. ছবি 3 – www.hackerearth.com
4. ছবি 4 – www.hackerearth.com

সংশ্লিষ্ট

সূত্র: https://www.analyticsvidhya.com/blog/2021/08/decision-tree-algorithm/