یادگیری درخت تصمیم

یادگیری درخت تصمیم (به انگلیسی: Decision tree learning) گروهی از الگوریتم‌های یادگیری ماشین هستند که در طبقه‌بندی آماری کاربرد دارند.[1] درخت‌های تصمیم به گروه الگوریتم‌های یادگیری تحت نظارت تعلق دارند و بیشتر آنها بر اساس حداقل‌سازی کمیتی به نام آنتروپی ساخته می‌شوند. هرچند توابع دیگری هم برای یادگیری درخت تصمیم وجود دارند.[2][3] نمونه‌های قدیمی درخت تصمیم تنها قادر به استفاده از متغیرهای گسسته بودند، اما الگوریتم‌های جدیدتر هردو نوع متغیر گسسته و پیوسته را در یادگیری به کار می‌برند.[2][4] یکی از مزایای مهم الگوریتم درخت تصمیم قابلیت فهم و تفسیر آسان است که محبوبیت این الگوریتم را بالا برده است.[2][5][4] از معایب آن عدم استواری و دقت ناکافی است.[4]

انواع درخت تصمیم

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

متریک‌ها

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

افزایش اطلاعات

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

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

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

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

\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)}}

$=-\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)}}$

یادگیری درخت

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

منابع

Provost, F., & Fawcett, T. (2013). Data Science for Business: What you need to know about data mining and data-analytic thinking. " O'Reilly Media, Inc.".
Piryonesi, S. M.; El-Diraby, T. E. (2020) [Published online: December 21, 2019]. "Data Analytics in Asset Management: Cost-Effective Prediction of the Pavement Condition Index". Journal of Infrastructure Systems. 26 (1). doi:10.1061/(ASCE)IS.1943-555X.0000512.
T. Hastie, R. Tibshirani, and J. Friedman, “The Elements of Statistical Learning,” Bayesian Forecast. Dyn. Model., vol. 1, pp. 1–694, 2009.
«X. Wu et al., "Top 10 algorithms in data mining," Knowl. Inf. Syst., vol. 14, no. 1, pp. 1–37, 2008».
"Piryonesi, S. M., & El-Diraby, T. (2018). Using Data Analytics for Cost-Effective Prediction of Road Conditions: Case of The Pavement Condition Index:[summary report] (No. FHWA-HRT-18-065). United States. Federal Highway Administration. Office of Research, Development, and Technology". Archived from the original on 2 February 2019.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[:2-1] Provost, F., & Fawcett, T. (2013). Data Science for Business: What you need to know about data mining and data-analytic thinking. " O'Reilly Media, Inc.".

[:12-2] Piryonesi, S. M.; El-Diraby, T. E. (2020) [Published online: December 21, 2019]. "Data Analytics in Asset Management: Cost-Effective Prediction of the Pavement Condition Index". Journal of Infrastructure Systems. 26 (1). doi:10.1061/(ASCE)IS.1943-555X.0000512.

[3] T. Hastie, R. Tibshirani, and J. Friedman, “The Elements of Statistical Learning,” Bayesian Forecast. Dyn. Model., vol. 1, pp. 1–694, 2009.

[:1-4] «X. Wu et al., "Top 10 algorithms in data mining," Knowl. Inf. Syst., vol. 14, no. 1, pp. 1–37, 2008».

[:0-5] "Piryonesi, S. M., & El-Diraby, T. (2018). Using Data Analytics for Cost-Effective Prediction of Road Conditions: Case of The Pavement Condition Index:[summary report] (No. FHWA-HRT-18-065). United States. Federal Highway Administration. Office of Research, Development, and Technology". Archived from the original on 2 February 2019.