درخت تصمیم (Decision Tree) چیست و چه کاربردی دارد؟

درخت تصمیم (Decision Tree) یکی از ابزارها و تکنیک‌هایی است که در مهارت‌های داده‌کاوی بسیار پر کاربرد است. زمانی که حجم داده‌ها بسیار بالا باشد این تکنیک می‌تواند به کمک شما بیاید.

به وفور اتفاق می‌افتد که مدیران پروژه و تحلیلگران کسب‌وکار از این تکنیک کمک بگیرند. این تکنیک در استاندارد PMBOK نیز شرح داده شده است.

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

آشنایی با داده­‌کاوی و کشف دانش در پایگاه­‌های داده

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

داده­‌کاوی یعنی چه؟

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

کاربرد داده­‌کاوی

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

روش­‌های داده­‌کاوی یا دیتامایننیگ

روش‌های اصلی داده‌کاوی به دو دسته توصیفی (Description) و پیش­بینانه (Prediction) تقسیم می‌شوند. خوشه­‌بندی (Clustering) از معروف­ترین روش‌­های توصیفی و دسته­بندی از پر اهمیت‌­ترین روش­‌های پیش­بینانه می‌­باشد. شکل زیر یک نمای کلی از طبقه‌بندی روش­‌های داده­‌کاوی را نمایش می­‌دهد.

در روش خوشه­‌بندی، داده‌ها بر اساس اصل حداکثر کردن شباهت داخل گروه‌ها و حداقل کردن شباهت بین گروه‌ها، خوشه‌بندی یا گروه‌بندی می‌شوند مانند شکل زیر. مثال خوشه‌بندی می‌تواند کشف زیرگروه‌های همگن مصرف‌کنندگان در یک پایگاه داده‌های بازاریابی باشد.

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

برخی روش‌های متداول دسته‌بندی عبارتند از درخت تصمیم، دسته‌بندی بیزی، شبکه عصبی (Neural Network) که در مطالب دیگری در وبلاگ PMPiran به آن‌ها خواهیم پرداخت.

درخت تصمیم یا Decision Tree

یکی از پرکاربردترین الگوریتم­‌های داده­‌کاوی، الگوریتم درخت تصمیم است. در داده­‌کاوی، درخت تصمیم یک مدل پیش­بینی کننده است به طوری که می­‌تواند برای هر دو مدل رگرسیون و طبقه‌­ای مورد استفاده قرار گیرد. زمانی که درخت برای کارهای طبقه‌­بندی استفاده می‌­شود، به عنوان درخت طبقه­‌بندی (Classification Tree) شناخته می‌­شود و هنگامی که برای فعالیت‌­های رگرسیونی به کار می‌­رود درخت رگرسیون (Regression Decision Tree)نامیده می­شود.

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

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

اجزای اصلی درخت تصمیم

برگ (Leaf Nodes): گره­‌هایی که تقسیم‌­های متوالی در آنجا پایان می‌­یابد. برگ‌­ها با یک کلاس مشخص می­‌شوند.

ریشه (Root Node): منظور از ریشه، گره آغازین درخت است.

شاخه (Branches): در هر گره داخلی به تعداد جواب‌­های ممکن شاخه ایجاد می‌­شود.

معیارهای انتخاب مشخصه برای انشعاب درخت تصمیم

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

سه معیار انتخاب مشخصه شناخته شده عبارتند از:

• Information gain
• Gain ratio
• Gini index

هرس کردن درخت تصمیم

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

در برخی الگوریتم­‌های ایجاد درخت، هرس کردن جزئی از الگوریتم محسوب می‌­شود. در حالی که در برخی دیگر، تنها برای رفع مشکل بیش برازش از هرس کردن استفاده می­‌شود.

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

دو رویکرد رایج برای هرس درخت به شرح ذیل وجود دارد:

• پیش­‌هرس (Pre pruning)

در این رویکرد یک درخت به وسیله توقف‌­های مکرر در مراحل اولیه ساخت درخت، هرس می‌­شود. به محض ایجاد یک توقف گره به برگ تبدیل می­‌شود.

• هرس پسین (Post pruning)

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

اندازه درخت

درخت تصمیم که پیچیدگی کم­تری داشته باشد قابل بیان و روشن است. بنابراین پیچیدگی درخت تاثیر مهمی بر روی صحت آن می‌گذارد.

معمولا پیچیدگی درخت توسط یکی از معیارهای زیر اندازه­گیری می­شود:

• تعداد کل گره‌­ها
• تعداد کل برگ­‌ها
• عمق درخت و تعداد مشخصه‌­های به کار رفته

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

الگوریتم‌­های شایع برای برقراری درخت تصمیم

• ID3

یکی از الگوریتم‌­های بسیار ساده درخت تصمیم که در سال 1986 توسط Quinlan مطرح شده است. اطلاعات به دست آمده به عنوان معیار تفکیک به کار می­‌رود. این الگوریتم هیچ فرایند هرس کردن را به کار نمی­‌برد و مقادیر اسمی و مفقوده را مورد توجه قرار نمی­‌دهد.

• C4.5

این الگوریتم درخت تصمیم، تکامل یافته ID3 است که در سال 1993 توسط Quinlan  مطرح شده است.

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

• CART

برای برقراری درخت­‌های رگرسیون و دسته‌­بندی از این الگوریتم استفاده می­‌شود. در سال 1984توسط Breiman و همکارانش ارائه شده است. نکته حائز اهمیت این است که این الگوریتم درخت­‌های باینری ایجاد می­‌کند به طوری که از هر گره داخلی دو لبه از آن خارج می­‌شود و درخت­‌های بدست آمده توسط روش اثربخشی هزینه، هرس می­‌شوند.

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

• CHID

این الگوریتم درخت تصمیم به جهت در نظرگرفتن مشخصه­‌های اسمی در سال 1981 توسط Kass طراحی شده است. الگوریتم برای هر مشخصه ورودی یک جفت مقدار که حداقل تفاوت را با مشخصه هدف داشته باشد، پیدا می­‌کند.

ارزیابی مدل

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

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

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

1. درخت تصمیم بدیهی است و نیاز به توصیف ندارد.
2. هر دو مشخصه اسمی و عددی را می‌­تواند مورد توجه قرار دهد.
3. نمایش درخت تصمیم به اندازه کافی برای نشان دادن هرگونه طبقه‌­بندی غنی است.
4. مجموعه داده‌­هایی که ممکن است دارای خطا باشند را در نظر می‌­گیرد.
5. مجموعه داده­‌هایی که دارای مقادیر مفقوده هستند را شامل می­‌شود.
6. درخت­‌های تصمیم روش­‌های ناپارامتری را نیز مورد توجه قرار می­‌دهد.

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

یک نمونه درخت تصمیم

نمونه درخت تصمیم در حوزه پزشکی:

درخت زیر تشخیص بی­ اختیاری ادراری زنان با مشخصه­‌های کلینیکی و سیستوسکوپی را نشان می‌­دهد. این درخت تصمیم، مدل “تصمیم یار تشخیص بی اختیاری ادراری زنان” نامیده شده است.

قواعد استخراج شده از درخت تصمیم فوق

1. IF Stress Incontinency: a & Urge Incontinency : d THEN Type of Incontinence: U
2. IF Stress Incontinency: a & Urge Incontinency : a b c & APR : b THEN Type of Incontinence: U
3. IF Stress Incontinency: a& Urge Incontinency : a b c & APR : a &Frequency: a b THEN Type of Incontinence: N
4. IF Stress Incontinency: a & Urge Incontinency : a b c & APR : a &Frequency: c & Infrequent Voluntary Voiding: b THEN Type of Incontinence: U
5. IF Stress Incontinency: a & Urge Incontinency : a b c & APR : a &Frequency: c & Infrequent Voluntary Voiding: a THEN Type of Incontinence: N
6. IF Stress Incontinency: b c d & nycturia: b c & Frequency : a THEN Type of Incontinence : M
7. IF Stress Incontinency: b c d & nycturia: b c & Frequency : b c & Incomplete Empting Sensation: b THEN Type of Incontinence: M
8. IF Stress Incontinency: b c d & nycturia: b c & Frequency : b c & Incomplete Empting Sensation: a THEN Type of Incontinence: U
9. IF Stress Incontinency: b c d & nycturia: a d & Suprapubicpain: b THEN Type of Incontinence: U
10. IF Stress Incontinency: b c d & nycturia: a d & Suprapubicpain: a & Urge Incontinency :c d & Infrequent Voluntary Voiding :b THEN Type of Incontinence: M
11. IF Stress Incontinency: b c d & nycturia: a d & Suprapubicpain: a & Urge Incontinency :d & Infrequent Voluntary Voiding :a THEN Type of Incontinence: M
12. IF Stress Incontinency: b c d & nycturia: a d & Suprapubicpain: a & Urge Incontinency :c & Infrequent Voluntary Voiding :a THEN Type of Incontinence: S
13. IF Stress Incontinency: b c & nycturia: a d & Suprapubicpain: a & Urge Incontinency: a b & Infrequent Voluntary Voiding :b THEN Type of Incontinence: M

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

پرکاربردترین نرم­‌افزارهای درخت تصمیم

زمانی­که بخواهید از نرم‌­افزار برای دسته‌بندی نمونه‌ها به روش الگوریتم درخت تصمیم استفاده کنید می­‌توانید از نرم‌­افزارهای زیر بهره‌­مند شوید.

• R
• SPSS Modeler
• MATLAB
• SAS JMP
• Clementine
• Python

برای مطالعات بیشتر

با مطالعه مقالات زیر می­‌توانید در مورد داده­‌کاوی، درخت تصمیم و نرم­‌افزار  R اطلاع بیشتری کسب کنید.

Chapman, Hall . (2010).”Data Mining with R Learning with Case Studies” , Luis Torgo. LIACC-FEP , University of Porto. R. Campo Alegre, 823 – 4150.

Han, Jiawei ., Kamber, Micheline. (2006). “Data Mining: Concepts and Techniques”, Morgan Kaufmann Publishers,2.

جمع‌بندی

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