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

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

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

مقدمه

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

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

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

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

${\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 که تنها قادر به یادگیری بر اساس متغیرهای گسسته‌است.^[4]
• C4.5 که قابلیت یادگیری از هردوی متغیرهای گسسته و پیوسته را دارد.^[4][5]

متریک‌ها

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

ناخالصی جینی

شاخص تنوع جینی^[7] در الگوریتم 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)}}}$

یادگیری درخت

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

کاربردها

مزایا

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

معایب

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

منابع

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.".
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.{{cite journal}}: نگهداری CS1: url-status (link)
3. T. Hastie, R. Tibshirani, and J. Friedman, “The Elements of Statistical Learning,” Bayesian Forecast. Dyn. Model. , vol. 1, pp. 1–694, 2009.
4. «X. Wu et al. , "Top 10 algorithms in data mining," Knowl. Inf. Syst. , vol. 14, no. 1, pp. 1–37, 2008».
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.
6. Quinlan, J. R. (1986). "Induction of decision trees" (PDF). Machine Learning. 1: 81–106. doi:10.1007/BF00116251. S2CID 189902138.
7. "Growing Decision Trees". MathWorks. MathWorks.