درخت تصمیم چیست؟ رازهای یک ابزار قدرتمند!
درخت تصمیم یه الگوریتم یادگیریِ با نظارت (supervised) و غیرپارامتریک هست که هم برای کارهای دسته‌بندی (classification) و هم رگرسیون (regression) استفاده می‌شه. این الگوریتم یه ساختار سلسله‌مراتبی و درختی داره که از گره ریشه (root node)، شاخه‌ها (branches)، گره‌های داخلی (internal nodes) و گره‌های برگ (leaf nodes) تشکیل شده.
یه درخت تصمیم با یه گره ریشه شروع می‌شه که هیچ شاخه ورودی نداره. بعد، شاخه‌های خروجی از گره ریشه به گره‌های داخلی می‌رسن که بهشون گره‌های تصمیم (decision nodes) هم می‌گن. هر دو نوع گره بر اساس ویژگی‌های موجود، داده‌ها رو ارزیابی می‌کنن تا زیرمجموعه‌های همگنی بسازن. این زیرمجموعه‌های نهایی با گره‌های برگ یا گره‌های پایانی (terminal nodes) نشون داده می‌شن. گره‌های برگ، تمام نتایج ممکن توی مجموعه داده رو نمایندگی می‌کنن.
مثلاً فرض کنید می‌خواید ببینید که امروز برای موج‌سواری برید یا نه. می‌تونید از قوانین تصمیم‌گیری زیر برای انتخاب استفاده کنید:
این ساختار فلوچارت-مانند، نمایش قابل فهمی از فرآیند تصمیم‌گیری ایجاد می‌کنه و به گروه‌های مختلف توی یه سازمان اجازه می‌ده تا بهتر درک کنن که یه تصمیم چرا و چطور گرفته شده.
یادگیری درخت تصمیم از استراتژی «تقسیم و غلبه» (divide and conquer) استفاده می‌کنه و با یه جستجوی حریصانه (greedy search) سعی می‌کنه بهترین نقاط تقسیم رو توی درخت پیدا کنه. این فرآیند تقسیم به صورت بازگشتی و از بالا به پایین تکرار می‌شه تا وقتی که همه یا بیشتر رکوردها تحت برچسب‌های کلاسی مشخصی دسته‌بندی بشن.
اینکه آیا همه نقاط داده به عنوان مجموعه‌های همگن دسته‌بندی می‌شن یا نه، تا حد زیادی به پیچیدگی درخت تصمیم بستگی داره. درخت‌های کوچیک‌تر راحت‌تر می‌تونن به گره‌های برگ خالص (pure leaf nodes) برسن، یعنی گره‌هایی که همه داده‌های توشون فقط به یک کلاس تعلق دارن. اما هر چی درخت بزرگ‌تر می‌شه، حفظ این خلوص سخت‌تر می‌شه و معمولاً باعث می‌شه داده‌های خیلی کمی توی هر زیردرخت قرار بگیرن. به این پدیده تکه‌تکه شدن داده (data fragmentation) می‌گن و اغلب می‌تونه منجر به بیش‌برازش (Overfitting) بشه.
در نتیجه، درخت‌های تصمیم تمایل به درخت‌های کوچیک دارن که این موضوع با اصل صرفه‌جویی در «تیغ اوکام» (Occam’s Razor) همخونی داره؛ یعنی «موجودیت‌ها نباید بیش از حد ضرورت تکثیر شوند.» به عبارت دیگه، درخت‌های تصمیم فقط در صورت لزوم باید پیچیدگی رو اضافه کنن، چون ساده‌ترین توضیح اغلب بهترینه. برای کاهش پیچیدگی و جلوگیری از بیش‌برازش، معمولاً از «هرس کردن» (pruning) استفاده می‌شه؛ این فرآیندیه که شاخه‌هایی رو که بر اساس ویژگی‌های کم‌اهمیت تقسیم شدن، حذف می‌کنه. بعدش می‌شه برازش (fit) مدل رو از طریق فرآیند اعتبارسنجی متقابل (cross-validation) ارزیابی کرد.
یه راه دیگه که درخت‌های تصمیم می‌تونن دقتشون رو حفظ کنن، تشکیل یه مدل گروهی (ensemble) از طریق الگوریتم جنگل تصادفی (random forest) هست. این دسته‌بند نتایج دقیق‌تری رو پیش‌بینی می‌کنه، مخصوصاً وقتی که درخت‌های تکی با هم همبستگی نداشته باشن.
انواع درخت‌های تصمیم
الگوریتم هانت (Hunt’s algorithm) که توی دهه ۱۹۶۰ برای مدل‌سازی یادگیری انسان در روانشناسی توسعه داده شد، پایه و اساس خیلی از الگوریتم‌های محبوب درخت تصمیم رو تشکیل می‌ده، مثل این موارد:
– ID3: توسعه این الگوریتم به راس کویینلن (Ross Quinlan) نسبت داده می‌شه و مخفف «Iterative Dichotomiser 3» هست. این الگوریتم از آنتروپی (entropy) و بهره اطلاعاتی (information gain) به عنوان معیار برای ارزیابی تقسیم‌های کاندید استفاده می‌کنه. بخشی از تحقیقات کویینلن روی این الگوریتم در سال ۱۹۸۶ رو می‌تونید اینجا پیدا کنید.
– C4.5: این الگوریتم نسخه جدیدتری از ID3 محسوب می‌شه که اون هم توسط کویینلن توسعه داده شده. C4.5 می‌تونه از بهره اطلاعاتی یا نسبت بهره (gain ratios) برای ارزیابی نقاط تقسیم در درخت‌های تصمیم استفاده کنه.
– CART: این اصطلاح مخفف «classification and regression trees» (درختان طبقه‌بندی و رگرسیون) هست و توسط لئو بریمن (Leo Breiman) معرفی شد. این الگوریتم معمولاً از ناخالصی جینی (Gini impurity) برای شناسایی ویژگی ایده‌آل برای تقسیم استفاده می‌کنه. ناخالصی جینی اندازه‌گیری می‌کنه که یه ویژگی انتخاب شده به صورت تصادفی، چند وقت یکبار اشتباه دسته‌بندی می‌شه. موقع ارزیابی با ناخالصی جینی، هر چی مقدار کمتر باشه، ایده‌آل‌تره.
چطور بهترین ویژگی رو در هر گره انتخاب کنیم؟
با اینکه راه‌های مختلفی برای انتخاب بهترین ویژگی در هر گره وجود داره، دو روش بهره اطلاعاتی (information gain) و ناخالصی جینی (Gini impurity) به عنوان معیارهای تقسیم محبوب برای مدل‌های درخت تصمیم عمل می‌کنن. این دو روش به ما کمک می‌کنن تا کیفیت هر شرط آزمون رو ارزیابی کنیم و بفهمیم چقدر خوب می‌تونه نمونه‌ها رو توی یک کلاس دسته‌بندی کنه.
آنتروپی و بهره اطلاعاتی
توضیح بهره اطلاعاتی بدون صحبت در مورد آنتروپی یکم سخته. آنتروپی مفهومی از نظریه اطلاعاته که ناخالصی مقادیر نمونه رو اندازه‌گیری می‌کنه. با فرمول زیر تعریف می‌شه، که در اون:
- S مجموعه داده‌ای هست که آنتروپی براش محاسبه می‌شه.
- c کلاس‌های موجود در مجموعه S رو نشون می‌ده.
- p(c) نسبت تعداد نقاط داده متعلق به کلاس c به کل نقاط داده در مجموعه S رو نشون می‌ده.
مقادیر آنتروپی می‌تونن بین ۰ و ۱ باشن. اگه همه نمونه‌های مجموعه داده S به یک کلاس تعلق داشته باشن، آنتروپی برابر با صفر می‌شه. اگه نصف نمونه‌ها توی یه کلاس و نصف دیگه توی کلاس دیگه‌ای باشن، آنتروپی به بیشترین مقدار خودش یعنی ۱ می‌رسه. برای انتخاب بهترین ویژگی برای تقسیم و پیدا کردن درخت تصمیم بهینه، باید از ویژگی‌ای استفاده کرد که کمترین مقدار آنتروپی رو داشته باشه.
بهره اطلاعاتی تفاوت آنتروپی قبل و بعد از تقسیم بر اساس یه ویژگی مشخص رو نشون می‌ده. ویژگی‌ای که بیشترین بهره اطلاعاتی رو داشته باشه، بهترین تقسیم رو ایجاد می‌کنه، چون بهترین عملکرد رو در دسته‌بندی داده‌های آموزشی بر اساس کلاس هدفشون داره. بهره اطلاعاتی معمولاً با فرمول زیر نمایش داده می‌شه،
- a یک ویژگی یا برچسب کلاس خاص رو نشون می‌ده.
- Entropy(S) آنتروپی مجموعه داده S هست.
- |Sv|/|S| نسبت مقادیر در Sv به تعداد کل مقادیر در مجموعه داده S رو نشون می‌ده.
بذارید با یه مثال این مفاهیم رو جا بندازیم. فرض کنید مجموعه داده فرضی زیر رو داریم:
برای این مجموعه داده، آنتروپی ۰.۹۴ هست. این عدد با پیدا کردن نسبت روزهایی که «تنیس بازی کنیم؟» جوابش «بله» بوده (یعنی ۹/۱۴) و نسبت روزهایی که جوابش «نه» بوده (یعنی ۵/۱۴) محاسبه می‌شه. بعد، این مقادیر رو توی فرمول آنتروپی که بالاتر گفتیم قرار می‌دیم.
آنتروپی (تنیس) = -(۹/۱۴) log2(۹/۱۴) – (۵/۱۴) log2 (۵/۱۴) = ۰.۹۴
حالا می‌تونیم بهره اطلاعاتی رو برای هر کدوم از ویژگی‌ها جداگانه حساب کنیم. مثلاً، بهره اطلاعاتی برای ویژگی «رطوبت» (Humidity) به این شکل می‌شه:
بهره (تنیس، رطوبت) = (۰.۹۴)-(۷/۱۴)*(۰.۹۸۵) – (۷/۱۴)*(۰.۵۹۲) = ۰.۱۵۱
برای یادآوری،
- ۷/۱۴ نسبت مقادیری رو نشون می‌ده که رطوبت «زیاد» بوده به کل مقادیر رطوبت. توی این مثال، تعداد روزهایی که رطوبت «زیاد» بوده با تعداد روزهایی که رطوبت «نرمال» بوده، برابره.
- ۰.۹۸۵ آنتروپی زمانی هست که رطوبت = «زیاد»
- ۰.۵۹۲ آنتروپی زمانی هست که رطوبت = «نرمال»
بعد، محاسبه بهره اطلاعاتی رو برای هر ویژگی دیگه‌ای که توی جدول بالا بود تکرار می‌کنیم و اون ویژگی‌ای که بالاترین بهره اطلاعاتی رو داره به عنوان اولین نقطه تقسیم توی درخت تصمیم انتخاب می‌کنیم. توی این مثال، ویژگی «وضعیت هوا» (outlook) بیشترین بهره اطلاعاتی رو تولید می‌کنه. از اینجا به بعد، این فرآیند برای هر زیردرخت تکرار می‌شه.
ناخالصی جینی
ناخالصی جینی، احتمال طبقه‌بندی اشتباه یه نقطه داده تصادفی از مجموعه داده‌ست، اگه قرار بود بر اساس توزیع کلاس در کل مجموعه داده برچسب‌گذاری بشه. مثل آنتروپی، اگه مجموعه S خالص باشه (یعنی همه اعضاش به یک کلاس تعلق داشته باشن)، ناخالصی اون صفره. این معیار با فرمول زیر نشون داده می‌شه:
مزایا و معایب درخت‌های تصمیم
با اینکه درخت‌های تصمیم می‌تونن توی موارد مختلفی استفاده بشن، معمولاً الگوریتم‌های دیگه عملکرد بهتری نسبت بهشون دارن. با این حال، درخت‌های تصمیم به طور خاص برای کارهای داده‌کاوی (data mining) و کشف دانش (knowledge discovery) خیلی مفید هستن. بیاید در ادامه مزایا و چالش‌های کلیدی استفاده از درخت‌های تصمیم رو بیشتر بررسی کنیم:
مزایا
- تفسیر راحت: منطق بولین (Boolean) و نمایش بصری درخت‌های تصمیم، درک و فهم اون‌ها رو آسون‌تر می‌کنه. ماهیت سلسله‌مراتبی یه درخت تصمیم همچنین باعث می‌شه به راحتی ببینیم کدوم ویژگی‌ها مهم‌ترن؛ چیزی که همیشه توی الگوریتم‌های دیگه مثل شبکه‌های عصبی (neural networks) واضح نیست.
- نیاز کم به آماده‌سازی داده‌ها: درخت‌های تصمیم ویژگی‌هایی دارن که اون‌ها رو نسبت به بقیه دسته‌بندها انعطاف‌پذیرتر می‌کنه. این الگوریتم می‌تونه انواع مختلف داده (مثلاً مقادیر گسسته یا پیوسته) رو مدیریت کنه و مقادیر پیوسته رو می‌شه با استفاده از آستانه‌ها (thresholds) به مقادیر دسته‌ای تبدیل کرد. علاوه بر این، می‌تونه با مقادیر گمشده (missing values) هم کار کنه که این موضوع برای دسته‌بندهای دیگه‌ای مثل Naïve Bayes می‌تونه مشکل‌ساز باشه.
- انعطاف‌پذیری بیشتر: از درخت‌های تصمیم می‌شه هم برای کارهای دسته‌بندی و هم رگرسیون استفاده کرد که این باعث می‌شه نسبت به الگوریتم‌های دیگه انعطاف‌پذیرتر باشن. همچنین به روابط پنهان بین ویژگی‌ها حساس نیستن؛ این یعنی اگه دو تا متغیر همبستگی بالایی داشته باشن، الگوریتم فقط یکی از اون‌ها رو برای تقسیم انتخاب می‌کنه.
معایب
- مستعد بیش‌برازش (Overfitting): درخت‌های تصمیم پیچیده تمایل به بیش‌برازش دارن و روی داده‌های جدید به خوبی تعمیم پیدا نمی‌کنن. می‌شه با فرآیندهای پیش‌هرس (pre-pruning) یا پس‌هرس (post-pruning) از این سناریو جلوگیری کرد. پیش‌هرس زمانی که داده کافی وجود نداره، رشد درخت رو متوقف می‌کنه، در حالی که پس‌هرس بعد از ساخت درخت، زیردرخت‌هایی با داده‌های ناکافی رو حذف می‌کنه.
- تخمین‌گرهایی با واریانس بالا: تغییرات کوچیک توی داده‌ها می‌تونه یه درخت تصمیم کاملاً متفاوت ایجاد کنه. بگینگ (Bagging)، یا همون میانگین‌گیری از تخمین‌ها، می‌تونه روشی برای کاهش واریانس درخت‌های تصمیم باشه. اما این رویکرد هم محدودیت‌های خودشو داره چون ممکنه به پیش‌بینی‌کننده‌هایی با همبستگی بالا منجر بشه.
- هزینه بیشتر: با توجه به اینکه درخت‌های تصمیم در حین ساخت از رویکرد جستجوی حریصانه استفاده می‌کنن، آموزش اون‌ها در مقایسه با الگوریتم‌های دیگه می‌تونه پرهزینه‌تر باشه.
پاسخی بگذارید