یادگیری درخت تصمیم - ویکی‌پدیا، دانشنامهٔ آزاد

یادگیری درخت تصمیم (به انگلیسی: Decision tree learning) گروهی از الگوریتم‌های یادگیری ماشین هستند که در طبقه‌بندی آماری کاربرد دارند.^[۱] درخت‌های تصمیم به گروه الگوریتم‌های یادگیری تحت نظارت تعلق دارند و بیشتر آنها بر اساس حداقل‌سازی کمیتی به نام آنتروپی ساخته می‌شوند. هرچند توابع دیگری هم برای یادگیری درخت تصمیم وجود دارند.^[۲][۳] نمونه‌های قدیمی درخت تصمیم تنها قادر به استفاده از متغیرهای گسسته بودند، اما الگوریتم‌های جدیدتر هردو نوع متغیر گسسته و پیوسته را در یادگیری به کار می‌برند.^[۲][۴] یکی از مزایای مهم الگوریتم درخت تصمیم قابلیت فهم و تفسیر آسان است که محبوبیت این الگوریتم را بالا برده‌است.^[۲][۵][۴] از معایب آن عدم استواری و دقت ناکافی است.^[۴]

مقدمه[ویرایش]

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

یادگیری ماشین و داده‌کاوی
موضوع‌ها طبقه‌بندی آماری خوشه‌بندی تحلیل رگرسیون روش تشخیص ناهنجاری یادگیری قانون وابستگی یادگیری تقویتی پیش بینی ساختاریافته مهندسی ویژگی یادگیری ویژگی یادگیری ماشین برخط یادگیری نیمه‌نظارتی یادگیری بی‌نظارت Learning to rank Grammar induction
یادگیری با نظارت (طبقه‌بندی آماری • تحلیل رگرسیون) یادگیری درخت تصمیم Ensembles (تکنیک بگینگ, بوستینگ، جنگل تصادفی) k-NN رگرسیون خطی دسته‌بندی کننده بیز ساده شبکه‌های عصبی مصنوعی رگرسیون لجستیک پرسپترون ماشین بردار مرتبط (RVM) ماشین بردار پشتیبانی
خوشه‌بندی کاهش و خوشه‌بندی ترازمند و بازکردی با بهره‌گیری از رده‌بندی خوشه‌بندی سلسله‌مراتبی خوشه‌بندی کی-میانگین الگوریتم امید ریاضی–بیشینه کردن DBSCAN OPTICS انتقال میانگین
کاهش ابعاد تحلیل عاملی CCA تحلیل مؤلفه‌های مستقل آنالیز افتراقی خطی فاکتورگیری نامنفی ماتریس تحلیل مؤلفه‌های اصلی t-SNE
پیش‌بینی ساختاریافته مدل‌های گرافیکی (شبکه‌های بیزی، میدان تصادفی شرطی، مدل پنهان مارکف)
روش تشخیص ناهنجاری الگوریتم کی-نزدیکترین همسایه فاکتور پرتی محلی
شبکه عصبی مصنوعی خودرمزگذار یادگیری عمیق پرسپترون چندلایه RNN ماشین بولتزمن محدود شده ترانسفورمر بینایی SOM شبکه عصبی پیچشی
یادگیری تقویتی کیو-یادگیری SARSA یادگیری تفاوت زمانی
نظریه Bias-variance dilemma نظریه یادگیری محاسباتی Empirical risk minimization Occam learning یادگیری احتمالا تقریبا صحیح Statistical learning VC theory
حوزه‌های یادگیری ماشین NIPS ICML ML JMLR ArXiv:cs.LG
ن ب و

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

روند ایجاد درخت تصمیم از تقسیم کردن مجموعه تمام داده‌های در دسترس (که در واقع ریشه درخت را تشکیل می‌دهند)، به زیر مجموعه‌هایی (که به هر گره فرزند تبدیل می‌شوند) است. شرایط تقسیم کردن داده‌های هر گره به گره‌های فرزند آن براساس یک شرط تقسیم‌بندی در هر گره داخلی خواهد بود. تقسیم کردن هر گره بدست آمده به گره‌های فرزند آن در یک روند بازگشتی انجام خواهد گرفت که به آن تقسیم‌بندی بازگشتی نیز گفته خواهد شد. این تقسیم‌بندی تا زمانی ادامه پیدا خواهد کرد که داده‌های در هر گره برگ متعلق به یک کلاس باشند یا زمانی که دیگر ویژگی‌ای برای تقسیم گردن داده‌های در یک گره وجود نداشته باشد. به این فرایند القای درخت تصمیم از بالا به پایین^[۶] گفته می‌شود که یک مثال از الگوریتمی حریصانه است.

داده‌های در درخت تصمیم به‌طور معمول به شکل زیر هستند:

${\displaystyle ({\textbf {x}},Y)=(x_{1},x_{2},x_{3},...,x_{k},Y)}$

که ${\displaystyle Y}$ متغیر مستقل و همان متغیر هدف است و بردار ${\displaystyle {\textbf {x}}}$ یک بردار ${\displaystyle k}$ بعدی است که شامل مقدار ویژگی‌های ${\displaystyle x_{1},x_{2},...,x_{k}}$ است.

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

انواع درخت تصمیم[ویرایش]

• ID3 که تنها قادر به یادگیری بر اساس متغیرهای گسسته‌است.^[۴]
• C4.5 که قابلیت یادگیری از هردوی متغیرهای گسسته و پیوسته را دارد.^[۴][۵]

متریک‌ها[ویرایش]

درخت‌های تصمیم ممکن است متریک‌های متفاوتی برای یادگیری استفاده کنند. از رایج‌ترین این متریک‌ها می‌توان به آنتروپی (یا افزایش اطلاعات) و شاخص جینی اشاره کرد.^[۱][۲]

ناخالصی جینی[ویرایش]

شاخص تنوع جینی^[۷] در الگوریتم CART (درخت طبقه‌بندی و رگرسیون) برای ایجاد درخت تصمیم استفاده می‌شود. ناخالصی جینی (نام‌گذاری شده بعد از ریاضی‌دان ایتالیایی کورادو جینی) اندازه‌گیری می‌کند که با چه احتمالی یک عنصر از یک مجموعه می‌تواند به اشتباه برچسب‌گذاری (دسته‌بندی) شود اگر که دسته‌بندی عناصر در مجموعه به‌طور تصادفی براساس یک توزیع احتمال انجام شده باشد. ناخالصی جینی را می‌توان با جمع کردن احتمال‌های ${\displaystyle p_{i}}$ برای یک عنصر که برچسب ${\displaystyle i}$ برای آن انتخاب شده در احتمال دسته‌بندی اشتباه آن که برابر است با ${\displaystyle \sum _{k\neq i}p_{k}=1-p_{i}}$ کمترین مقدار ممکن برای این متریک برابر صفر است که در این حالت تمام المان‌های در یک مجموعه به یک کلاس تعلق دارند.

برای اینکه مقدار ناخالصی جینی را برای یک مجموعه از المان‌ها با ${\displaystyle J}$ کلاس که که ${\displaystyle i\in \{1,2,...,J\}}$ و ${\displaystyle p_{i}}$ نسبتی از داده‌ها باشد که با برچسب i در این مجموعه برچسب زده شده‌اند:

${\displaystyle \operatorname {I} _{G}(p)=\sum _{i=1}^{J}\left(p_{i}\sum _{k\neq i}p_{k}\right)=\sum _{i=1}^{J}p_{i}(1-p_{i})=\sum _{i=1}^{J}(p_{i}-p_{i}^{2})=\sum _{i=1}^{J}p_{i}-\sum _{i=1}^{J}p_{i}^{2}=1-\sum _{i=1}^{J}p_{i}^{2}}$

افزایش اطلاعات[ویرایش]

افزایش اطلاعات (به انگلیسی: Information gain) یکی از متریک‌های یادگیری درخت تصمیم است که بر اساس آنتروپی بوده و به شکل زیر فرموله می‌شود:

${\displaystyle \mathrm {H} (T)=\operatorname {I} _{E}\left(p_{1},p_{2},...,p_{J}\right)=-\sum _{i=1}^{J}{p_{i}\log _{2}p_{i}}}$

که در آن ${\displaystyle p_{1},p_{2},...}$ کسرهایی هستند که مجموعشان برابر با ۱ است و نشانگر درصدهای هر کلاس در گره فرزند پس از تقسیم هستند.

بدین ترتیب افزایش اطلاعات حاصل در سیستم از تقسیم یک گره به صورت تفریق آنتروپی سیستم پیش و پس از تقسیم (یعنی آنتروپی والد منهای آنتروپی فرزند) به شکل زیر محاسبه می‌شود:

$${\displaystyle \overbrace {IG(T,a)} ^{\text{Information Gain}}=\overbrace {\mathrm {H} (T)} ^{\text{Entropy (parent)}}-\overbrace {\mathrm {H} (T|a)} ^{\text{Weighted Sum of Entropy (Children)}}}$$

${\displaystyle =-\sum _{i=1}^{J}p_{i}\log _{2}{p_{i}}-\sum _{a}{p(a)\sum _{i=1}^{J}-\Pr(i|a)\log _{2}{\Pr(i|a)}}}$

یادگیری درخت[ویرایش]

یادگیری درخت به این شکلست که ابتدا متغیری که بیشترین تغییر در آنتروپی را ایجاد می‌کند (یا بیشترین افزایش اطلاعات را دارد) انتخاب می‌شود و مجموعه داده بر اساس این متغیر تقسیم می‌شود. سپس همین عمل برای هرکدام از زیرمجموعه‌های ایجاد شده تکرار می‌شود و تا جایی ادامه پیدا می‌کند که زیرمجموعه‌های بدست آمده از حداقلی از خلوص برخوردار باشند.^[۱] بنابراین ترتیب متغیرها در ساختار یک درخت تصمیم نشانگر میزان اطلاعات نهفته در آنهاست.^[۲]

کاربردها[ویرایش]

مزایا[ویرایش]

• درک و تفسیر ساده است. افراد پس از توضیح مختصر می‌توانند مدل‌های درخت تصمیم را درک کنند. درختان همچنین می‌توانند به صورت گرافیکی به گونه ای نمایش داده شوند که تفسیر آنها برای افراد غیر متخصص آسان باشد.
• قادر به رسیدگی به داده‌های عددی و مقوله ای است. سایر تکنیک‌ها معمولاً در تجزیه و تحلیل مجموعه داده‌هایی که فقط یک نوع متغیر دارند، تخصصی می‌شوند. (به عنوان مثال، قوانین رابطه را می‌توان فقط با متغیرهای اسمی استفاده کرد، در حالی که شبکه‌های عصبی را می‌توان فقط با متغیرهای عددی یا مقوله‌هایی که به مقادیر ۰–۱ تبدیل شده‌اند استفاده کرد) درختان تصمیم اولیه فقط قادر به مدیریت متغیرهای طبقه‌بندی بودند، اما نسخه‌های جدیدتر، مانند به عنوان C4.5، این محدودیت را ندارند.
• نیاز به آماده‌سازی داده‌های کمی دارد. سایر تکنیک‌ها اغلب به نرمال سازی داده‌ها نیاز دارند. از آنجایی که درختان می‌توانند پیش‌بینی کننده‌های کیفی را اداره کنند، نیازی به ایجاد متغیرهای ساختگی نیست.
• از یک جعبه سفید یا جعبه باز استفاده می‌کند. اگر یک موقعیت معین در یک مدل قابل مشاهده باشد، توضیح این شرط به راحتی با منطق بولی توضیح داده می‌شود. در مقابل، در مدل جعبه سیاه، توضیح نتایج معمولاً به سختی قابل درک است، برای مثال با یک شبکه عصبی مصنوعی.
• امکان اعتبارسنجی مدل با استفاده از آزمون‌های آماری. این امر باعث می‌شود که قابلیت اطمینان مدل در نظر گرفته شود.
• رویکرد ناپارامتریک که هیچ فرضی در مورد داده‌های آموزشی یا باقیمانده‌های پیش‌بینی نمی‌کند. به عنوان مثال، هیچ فرضیات توزیعی، استقلال، یا واریانس ثابت وجود ندارد.
• با مجموعه داده‌های بزرگ عملکرد خوبی دارد. مقادیر زیادی از داده‌ها را می‌توان با استفاده از منابع محاسباتی استاندارد در زمان معقول تجزیه و تحلیل کرد.
• تصمیم‌گیری انسانی را بیشتر از سایر رویکردها منعکس می‌کند. این می‌تواند هنگام مدل‌سازی تصمیمات/رفتار انسانی مفید باشد.
• مقاوم در برابر هم خطی بودن، به ویژه تقویت کننده.
• در انتخاب ویژگی خود ساخته‌است. از ویژگی‌های نامربوط اضافی کمتر استفاده می‌شود تا بتوان آنها را در اجراهای بعدی حذف کرد. سلسله مراتب صفات در درخت تصمیم نشان دهنده اهمیت صفات است. این بدان معنی است که ویژگی‌های بالا آموزنده‌ترین هستند.
• درختان تصمیم می‌توانند هر تابع بولی را تقریب بزنند، به عنوان مثال. XOR.

معایب[ویرایش]

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

منابع[ویرایش]