الگوریتم درخت تصمیم - راهنمای کامل

بازنشر افلاطون

دنبال: 0

این مقاله به عنوان بخشی از بلاگاتون علم داده

تاکنون در مورد رگرسیون خطی، رگرسیون لجستیک یاد گرفته‌ایم و درک آنها بسیار سخت بود. بیایید اکنون با درخت تصمیم شروع کنیم و به شما اطمینان می دهم که این احتمالاً ساده ترین الگوریتم در یادگیری ماشین است. در اینجا ریاضیات زیادی درگیر نیست. از آنجایی که استفاده و تفسیر آن بسیار آسان است، یکی از پرکاربردترین و کاربردی ترین روش های مورد استفاده در یادگیری ماشینی است.

فهرست

1. درخت تصمیم چیست؟

2. نمونه ای از درخت تصمیم

3. آنتروپی

4. به دست آوردن اطلاعات

5. چه زمانی باید Splitting را متوقف کرد؟

6. چگونه می توان بیش از حد مناسب را متوقف کرد؟

بیشترین عمق
min_samples_split
min_samples_leaf
max_features

7. هرس

پس از هرس
پیش هرس

8. یادداشت های پایانی

درخت تصمیم چیست؟

این ابزاری است که دارای برنامه های کاربردی در چندین حوزه مختلف است. درختان تصمیم را می توان برای طبقه بندی و همچنین مشکلات رگرسیون استفاده کرد. خود نام نشان می‌دهد که از یک فلوچارت مانند ساختار درختی برای نشان دادن پیش‌بینی‌های حاصل از یک سری تقسیم‌بندی‌های مبتنی بر ویژگی استفاده می‌کند. با یک گره ریشه شروع می شود و با تصمیم گیری توسط برگ ها به پایان می رسد.

تصویر 1

قبل از یادگیری بیشتر در مورد درخت تصمیم، اجازه دهید با برخی از اصطلاحات آشنا شویم.

گره های ریشه - گره موجود در ابتدای درخت تصمیم از این گره است که جمعیت بر اساس ویژگی های مختلف شروع به تقسیم می کند.

گره های تصمیم گیری – گره هایی که پس از تقسیم گره های ریشه به دست می آوریم، گره تصمیم نامیده می شوند

گره های برگ - گره هایی که در آن تقسیم بیشتر امکان پذیر نیست، گره های برگ یا گره های پایانی نامیده می شوند

زیر درخت - درست مانند بخش کوچکی از یک نمودار، گراف فرعی نامیده می شود، به طور مشابه، بخش فرعی این درخت تصمیم را درخت فرعی می نامند.

هرس - چیزی نیست جز قطع کردن برخی گره ها برای جلوگیری از برازش بیش از حد.

تصویر 2

نمونه ای از درخت تصمیم

بیایید درخت های تصمیم را با کمک یک مثال درک کنیم.

تصویر 3

درختان تصمیم وارونه هستند که به این معنی است که ریشه در بالا قرار دارد و سپس این ریشه به چندین گره مختلف تقسیم می شود. درخت‌های تصمیم چیزی جز مجموعه‌ای از گزاره‌های if-else در اصطلاح عامیانه نیستند. بررسی می کند که آیا شرط درست است یا خیر، سپس به گره بعدی متصل به آن تصمیم می رود.

در نمودار زیر درخت ابتدا می پرسد آب و هوا چیست؟ آیا هوا آفتابی، ابری یا بارانی است؟ اگر بله، به ویژگی بعدی که رطوبت و باد است می رود. دوباره بررسی می‌کند که آیا باد شدیدی می‌وزد یا ضعیف، اگر باد ضعیفی است و بارانی است، ممکن است فرد برود و بازی کند.

تصویر 4

آیا در فلوچارت بالا متوجه چیزی شده اید؟ ما می بینیم که اگر هوا ابری است پس باید بریم بازی کنیم چرا بیشتر تقسیم نشد؟ چرا آنجا متوقف شد؟

برای پاسخ به این سوال، باید در مورد چند مفهوم دیگر مانند آنتروپی، افزایش اطلاعات و شاخص جینی بدانیم. اما به زبان ساده، در اینجا می توانم بگویم که خروجی مجموعه داده آموزشی برای هوای ابری همیشه بله است، زیرا در اینجا بی نظمی وجود ندارد، ما نیازی به تقسیم بیشتر گره نداریم.

هدف یادگیری ماشین کاهش عدم قطعیت یا اختلالات از مجموعه داده است و برای این کار از درخت تصمیم استفاده می کنیم.

اکنون باید به این فکر کنید که چگونه می توانم بدانم گره ریشه باید چه باشد؟ گره تصمیم چه باید باشد؟ چه زمانی باید جدایی را متوقف کنم؟ برای تصمیم گیری در این مورد، معیاری به نام «آنتروپی» وجود دارد که میزان عدم قطعیت در مجموعه داده است.

آنتروپی

آنتروپی چیزی نیست جز عدم قطعیت در مجموعه داده یا معیار بی نظمی ما. اجازه دهید سعی کنم این را با کمک یک مثال توضیح دهم.

فرض کنید شما یک گروه از دوستان دارید که تصمیم می گیرند کدام فیلم را در روز یکشنبه با هم تماشا کنند. 2 انتخاب برای فیلم وجود دارد، یکی این است "لوسی" و دومی است "تایتانیک" و حالا همه باید انتخاب خود را بگویند. بعد از اینکه همه پاسخ خود را می دهند، می بینیم که "لوسی" 4 رای می گیرد و تایتانیک 5 رای به دست آورد. حالا کدوم فیلم رو ببینیم؟ الان انتخاب 1 فیلم سخت نیست چون آرای هر دو فیلم تا حدودی برابر است.

این دقیقاً همان چیزی است که ما به آن بی نظمی می گوییم، تعداد آرای هر دو فیلم برابر است و ما واقعاً نمی توانیم تصمیم بگیریم که کدام فیلم را تماشا کنیم. اگر آرای «لوسی» 8 و برای «تایتانیک» 2 بود، خیلی راحت‌تر بود. در اینجا به راحتی می‌توان گفت که اکثریت آرا برای «لوسی» است، بنابراین همه این فیلم را تماشا خواهند کرد.

در درخت تصمیم، خروجی بیشتر «بله» یا «خیر» است.

فرمول آنتروپی در زیر نشان داده شده است:

در اینجا ص₊ احتمال کلاس مثبت است

p_- احتمال کلاس منفی است

S زیرمجموعه مثال آموزشی است

چگونه درختان تصمیم از آنتروپی استفاده می کنند؟

اکنون می دانیم که آنتروپی چیست و فرمول آن چیست، سپس باید بدانیم که دقیقاً چگونه در این الگوریتم کار می کند.

آنتروپی اساساً ناخالصی یک گره را اندازه گیری می کند. نجاست درجه تصادفی است; این نشان می دهد که داده های ما چقدر تصادفی هستند. آ زیر تقسیم خالص به این معنی است که یا باید «بله» بگیرید، یا باید «نه» بگیرید.

فرض کنید الف از ویژگی های در ابتدا 8 "بله" و 4 "نه" دارد، پس از اولین تقسیم گره چپ 5 "بله" و 2 "نه" می گیرد در حالی که گره سمت راست 3 "بله" و 2 "نه" می گیرد.

ما اینجا می بینیم که شکاف خالص نیست، چرا؟ زیرا هنوز می‌توانیم برخی از کلاس‌های منفی را در هر دو گره ببینیم. برای ایجاد یک درخت تصمیم باید ناخالصی هر شکاف را محاسبه کنیم و وقتی خلوص 100% باشد آن را به صورت گره برگ می سازیم.

برای بررسی ناخالصی ویژگی 2 و ویژگی 3 ما از فرمول Entropy کمک می گیریم.

منبع تصویر: نویسنده

برای ویژگی 3،

ما به وضوح می‌توانیم از خود درخت ببینیم که گره چپ آنتروپی کم یا خلوص بیشتری نسبت به گره راست دارد، زیرا گره چپ تعداد «بله» بیشتری دارد و در اینجا تصمیم‌گیری آسان است.

همیشه به یاد داشته باشید که هر چه آنتروپی بالاتر باشد، خلوص کمتر و ناخالصی بالاتر خواهد بود.

همانطور که قبلا ذکر شد، هدف یادگیری ماشین کاهش عدم قطعیت یا ناخالصی در مجموعه داده است، در اینجا با استفاده از آنتروپی، ناخالصی یک گره خاص را دریافت می کنیم، نمی دانیم که آنتروپی والد یا آنتروپی یک گره خاص. کاهش یافته است یا خیر

برای این، ما یک معیار جدید به نام "Information gain" آورده ایم که به ما می گوید آنتروپی والد پس از تقسیم آن با برخی ویژگی ها چقدر کاهش یافته است.

به دست آوردن اطلاعات

افزایش اطلاعات کاهش عدم قطعیت را با توجه به برخی ویژگی ها اندازه گیری می کند و همچنین یک عامل تعیین کننده است که کدام ویژگی باید به عنوان گره تصمیم یا گره ریشه انتخاب شود.

این فقط آنتروپی مجموعه داده کامل است - آنتروپی مجموعه داده با توجه به برخی ویژگی ها.

برای درک بهتر این موضوع مثالی را در نظر می گیریم:
فرض کنید کل جمعیت ما در مجموع 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 - نشان دهنده حداقل تعداد نمونه های مورد نیاز برای قرار گرفتن در گره برگ است. هرچه تعداد را بیشتر کنید، احتمال بیش از حد برازش بیشتر می شود.

max_features - به ما کمک می کند تصمیم بگیریم چه تعداد ویژگی را هنگام جستجوی بهترین تقسیم در نظر بگیریم.

برای مطالعه بیشتر در مورد این هایپرپارامترها می توانید آن را بخوانید اینجا کلیک نمایید.

هرس

این روش دیگری است که می تواند به ما کمک کند از زیاده روی کردن جلوگیری کنیم. با بریدن گره ها یا گره های فرعی که قابل توجه نیستند به بهبود عملکرد درخت کمک می کند. شاخه هایی که اهمیت بسیار کمی دارند را حذف می کند.

به طور عمده 2 روش برای هرس وجود دارد:

(I) پیش هرس - می‌توانیم رشد درخت را زودتر متوقف کنیم، به این معنی که اگر گره‌ای اهمیت کمی دارد، می‌توانیم هرس/حذف/برش دهیم. در حالی که رشد می کند درخت.

(II) پس از هرس - یک بار ما درخت در عمق آن ساخته شده است، می توانیم هرس گره ها را بر اساس اهمیت آنها شروع کنیم.

Endnotes

به طور خلاصه، در این مقاله با درختان تصمیم آشنا شدیم. بر چه اساسی درخت گره ها را می شکافد و چگونه می تواند جلوی نصب بیش از حد را بگیرد. چرا رگرسیون خطی در مورد مسائل طبقه بندی کار نمی کند؟

در مقاله بعدی جنگل های تصادفی را توضیح خواهم داد که باز هم یک تکنیک جدید برای جلوگیری از برازش بیش از حد است.
برای بررسی اجرای کامل درختان تصمیم لطفا به من مراجعه کنید گیتهاب مخزن

اگر سوالی دارید در نظرات زیر به من اطلاع دهید.

درباره نویسنده

من دانشجوی مقطع کارشناسی هستم که در حال حاضر در سال آخر رشته آمار (لیسانس آمار) هستم و علاقه زیادی به رشته علوم داده، یادگیری ماشین و هوش مصنوعی دارم. من از غواصی در داده ها برای کشف روندها و سایر بینش های ارزشمند در مورد داده ها لذت می برم. من دائماً در حال یادگیری هستم و انگیزه دارم تا چیزهای جدید را امتحان کنم.

من آماده همکاری و کار هستم.

برای هرچی شک و تردید، در صورت تمایل با من تماس بگیرید پست الکترونیک (ایمیل)

با من در ارتباط باشید لینک و توییتر

رسانه های نشان داده شده در این مقاله متعلق به Analytics Vidhya نیستند و به صلاحدید نویسنده استفاده می شوند.