پیش‌بینی نجات‌یافتگان با روش درخت تصمیم

تغییرات پروژه از تاریخ 1396/11/11 تا حالا
**به نام خداوند بخشنده ی مهربان**

سایت **www.kaggle.com** به عنوان یکی از مشهورترین برگزار کننده های مسابقات، در حوزه ی **پردازش و تحلیل داده** می باشد.
جوایزی که این سایت، برای بهترین تیم های شرکت کننده در نظر می گیرد، گاهی به چندین هزار دلار هم می رسد! 
هدف ما در این پروژه ی هیجان انگیز و بسیار جالب!، بررسی یکی از مسابقات این سایت است که از [اینجا](https://www.kaggle.com/c/titanic) در دسترس می‌باشد.
در این مسابقه، از شرکت کنندگان خواسته شده که با استفاده از اطّلاعات داده شده درباره ی مسافران کشتی آر اِم اِس تایتانیک[^RMS Titanic]، که در مجموعه ی داده‌های[^Dataset] مسابقه ارائه شده، پیش بینی کنند که چه کسی از کشتی تایتانیک جان سالم به در برده است[^Survive]!
در ادامه، ابتدا توضیحاتی راجع به کلّیات موضوع و داده های مسئله داده می شود؛ آن گاه تعدادی از روش هایی را که برای حلّ مسئله مطرح هستند،
برخواهیم شمرد و سپس به بررسی یکی از بهترین روش های حلّ این مسئله خواهیم پرداخت!
![کشتی تایتانیک](https://boute.s3.amazonaws.com/278-vu2vx1tw00qy.png)

# مقدمه
به ندرت کسی پیدا می شود که فیلم تایتانیک[^A 1997 American film directed by James Cameron won 11 Oscars!]  را ندیده باشد و یا داستان غرق شدن این کشتی غول پیکر را نشنیده باشد. در حادثه ی برخورد کشتی بخار بزرگ تایتانیک به کوه یخ، که در تاریخ 15 آوریل 1912، از بندر ساوت همپتون انگلستان به مقصد نیویورک آمریکا در سفر بود، 1514 نفر از 2224 مسافر و خدمه ی کشتی، کشته شدند؛ که یکی از دلایل اصلی آن عدم تعبیه ی قایق نجات، به تعداد لازم بود.
هر چند که می توان شانس را یکی از عوامل تأثیر گذار در نجات یافتن افراد بیان کرد؛ امّا برای برخی افراد، مانند زنان و بچّه ها
و افرادی که در قسمت های با درجه ی[^Class] بالاتر جای داشتند، احتمال بیشتری وجود داشت که نجات پیدا کنند.
هدف ما این است که با استفاده از داده های مسئله که سایت kaggle.com، به صورت فایل های [^Comma-separated values]csv،  در اختیار کاربران قرار داده داده است، و با به کار بردن یکی از تکنیک های یادگیری ماشین به نام درخت تصمیم، پیش بینی کنیم که چه کسانی زنده می مانند.
در شکل زیر، اطّلاعاتِ داده شده و توضیحات آن ها آورده شده است.![شکل 1- اطّلاعات داده شده راجع به مسافران](https://boute.s3.amazonaws.com/278-1MpPa2D.png)
قسمتی از داده ها نیز در شکل پایین، قابل مشاهده می باشند.![شکل 2- قسمتی از داده ها](https://boute.s3.amazonaws.com/278-Untitled2.png)
همان طور که در شکل 2 مشخّص است، برای برخی افراد، بعضی ویژگی ها دارای مقدار نمی باشند؛ امّا طبیعتاً برای هر نفر، باید حداقل یک ویژگی دارای مقدار داشته باشیم.
مجموعه ی داده ها، دارای 819 نمونه می باشد.
مجموعه ی داده شده جهت تست، دارای 418 نمونه است.
در صورتی که یک بررسی اوّلیه بر روی داده ها انجام دهیم، نتایج شکل زیر به دست می آیند.![شکل 3- بررسی اوّلیه](https://boute.s3.amazonaws.com/278-OanANSO.png) 
همان طور که مشاهده می کنید، جنسیت مسافر، در این که نجات پیدا می کند یا خیر، بسیار تأثیر گذار می باشد؛ چنان که 74% زنان زنده ماندند؛ در حالی که کمتر از 19% مردان توانستند نجات پیدا کنند. بعد از جنسیت، عامل جایگاه قرار گیری مسافران نیز بسیار اهمّیت دارد؛ چرا که بیشتر از 96% زنانی که بلیط درجه 1 داشتند، توانستند نجات پیدا کنند. 
این اطّلاعات، یک درک کلّی از شرایط مسئله، در اختیار ما قرار می دهد.

# کارهای مرتبط
در منابع ذکر شده، روش های جنگل تصادفی، درخت تصمیم، شبکه های عصبی، ماشین بردار پشتیبان، Naive Bayes، افزایش شیب دار و... استفاده شده اند.
اِن شاءَ اللّه ما در این پروژه، سعی خواهیم کرد روش درخت تصمیم[^Decision Tree] را در حدّ امکان و قابل فهم بررسی کنیم.
ابتدا کلّیت روش درخت تصمیم را توضیح داده، و سپس این روش را برای مسئله ی داده شده به کار خواهیم برد.

**درخت تصمیم**

درخت تصمیم، یکی از روش های طبقه بندی[^Classify] به شکل یک درخت می باشد که:
1- برگ[^Leave]ها، مشخّص کننده ی ویژگی هدف (در این جا، احتمال زنده ماندن) می باشند.
2- هر یک از گره[^Node]های میانی، نقش یک گره تصمیم گیری بر اساس یک ویژگی را ایفا می کنند که دارای یک زیر درخت، به ازای هر یک از
نتایج تصمیم گیری می باشد.
در این درخت سعی می شود تا با استفاده از انتخاب شروط مناسب در هر گره تصمیم گیری، درختی بسازیم که پیش بینی بهتری ارائه دهد.
نمونه ای از درخت تصمیم گیری را در شکل زیر مشاهده می کنید.![شکل 4- یک نمونه درخت تصمیم](https://boute.s3.amazonaws.com/278-Titanic_Survival_Decison_Tree_SVG.png)
در این شکل، اگر به یکی از برگ های سبز رسیدیم، مسافر را نجات یافته، و در غیر این صورت، غرق شده به حساب می آوریم.
الگوریتم هایی که برای ایجاد درخت تصمیم استفاده می شوند، معمولاً به شکل بالا به پایین کار می کنند؛ به این صورت که در هر مرحله، متغیّری را که به بهترین شکل، مجموعه ی داده ها را تقسیم می کند، انتخاب می کنند.
الگوریتم های مختلف، معیارهای مختلفی از بهترین، ارائه می دهند؛ که برای اطّلاعات بیشتر می توانید به این [پیوند](https://en.wikipedia.org/wiki/Decision_tree_learning) مراجعه کنید.
نویسنده ی مقاله ی مرجع، در این روش، از ویژگی‌های جنسیت، درجه ی مسافر، سن و کرایه[^Fare] استفاده کرده است.
در ابتدا داده‌ها صرفاً بر اساس جنسیت دسته بندی شده‌اند که دقّت 76.79 درصدی حاصل شده است (شکل 5).
![شکل 5- دقّت پیش بینی، با استفاده از ویژگی های مختلف](https://boute.s3.amazonaws.com/278-JJdEhSu.png)
در مرحله ی بعد، هر کدام از شاخه‌های مردان و زنان بر اساس درجه، تقسیم بندی شده اند.
همان طور که در شکل 3 مشخّص است، برای تمام درجات، احتمال زنده ماندن مردان، کمتر از 50% می‌باشد که بدین معنی می‌باشد که
احتمالاً بهتر است نتیجه ی این برگ ها را مرگ در نظر بگیریم.
امّا شرایط برای زنان، به گونه‌ای دیگر است. در شاخه ی زنان، در همه ی درجات، به غیر از درجه ی 3، احتمال زنده ماندن بیشتر از 50% می‌باشد.
اگر نتیجه ی درجه ی 3 را هم زنده ماندن در نظر بگیریم، همان نتیجه ی مرحله ی قبل ( 76.79% ) به دست می آید؛ چرا که باز هم مردان، مرده و
زنان، نجات یافته به حساب می‌آیند.
ولی اگر نتیجه ی این برگ را مرگ در نظر بگیریم، دقّت به 77.27% افزایش می‌یابد.
سپس نوبت به سن می‌رسد. سن، یک مقدار نسبتاً پیوسته دارد؛ بنا بر این تصمیم‌گیریِ چگونگیِ انتخابِ معیارِ تصمیم‌گیری، بسیار مهم می‌باشد.
به صورت کلّی، افراد با سنّ کمتر، احتمال زنده ماندن بیشتری نسبت به افراد مسن تر داشته اند. در مقاله ی منبع، ذکر شده که
به جای این که برای همه‌ی درجه های جنسیت ها در درخت، معیار یکسانی انتخاب شود، هر کدام از درجه‌ها در هر کدام از جنسیت ها را به صورت جداگانه مورد بررسی قرار داده تا معیار مناسبی جهت تقسیم بندی هر کدام بر اساس سن انتخاب کنند. انتخاب این معیار بر این اساس بوده است که اگر افرادی که سنّ کمتری از معیار سنّی دارند و افرادی که سنّ بیشتری از معیار سنّی دارند را طبقه بندی کنیم، خطای طبقه بندی در مجموعه ی داده آموزشی[^Training data]، کمتر باشد.
پس از این کار دقّت به 78.94% افزایش یافت. متأسّفانه، منبع ذکر شده جزئیات بیشتری در رابطه با چگونگی انتخاب معیار‌ها و یا حتّی مقدار دقیق معیار‌ها ذکر نکرده است.

# آزمایش‌ها
**1-3- پیش نیاز**
جهت اجرای کد برنامه که از  [اینجا](https://github.com/AhmadYaghoubi/PredictingTitanicSurvivorsDT) قابل دسترسی است، نیاز به ماژول‌[^Module]هایی می‌باشد که در پیوندِ داده شده، داخلِ فایلِ requirements.txt موجود هستند.
برای نصب ماژول‌ها دو راه وجود دارد:
راه اوّل: همان ابتدا با استفاده از دستور زیر ماژول‌های موجود در فایل را نصب کنید:
pip install –r requirements.txt
البتّه این روش معمولاً به خطا می‌انجامد؛ چرا که بعضی از ماژول‌ها به راحتی قابل نصب نمی باشند.
راه دوم: نرم‌افزار miniconda متناسب با سیستم عامل خود را از [اینجا](http://conda.pydata.org/miniconda.html) دریافت و نصب نمایید.
Conda یک برنامه ی Package Manager می‌باشد که روش سریعی را جهت استفاده از Package ها فراهم می‌آورد.
پس از این که مراحل نصب تمام شد، با استفاده از دستور conda create -n myenv python یک virtual environment بسازید و با دستور
activate myenv، آن را فعّال کنید ( می‌توانید از اسم دلخواه خود به جای myenv استفاده نمایید ).
اکنون با دستور conda install numpy ماژول numpy را نصب کنید.
سایر ماژول ها با استفاده از دستوری که در روش اوّل ذکر شد، قابل نصب می‌باشند.
**2-3- پیش پردازش**
داده‌های مسئله که در سایت مسابقه دریافت شده اند،در github پروژه قابل دسترسی می‌باشند.
برای این که داد‌‌ه‌ها در الگوریتم‌های به کار رفته قابل استفاده باشند، لازم است که یک عملیات پیش‌پردازش بر روی آن ها انجام شود.
برای خواندن و پردازش فایل‌های csv از کتابخانه pandas پایتون استفاده شده است. داده‌های مسئله دارای یک فایل train.csv  می‌باشد و داده های مربوط به test را  از روی داده ی اولیه بدست می آوریم و جهت سادگی کار، داده‌های train.csv را که حاوی اطّلاعات کامل می‌باشند، به دو قسمت، به صورت 30% برای تست و 70% برای یادگیری تقسیم می‌کنیم تا فرایند آزمایش، بصورت آفلاین قابل انجام ‌باشد.
بسیاری از داده‌های داده شده، دارای مقادیر غیر عددی می‌باشند که لازم است جهت کارکرد صحیح روش‌ها، به مقادیر عددی تبدیل شوند.
هم چنین مقادیر بسیاری از سطر‌های جدول دارای مقادیر null می‌باشند که این مقادیر، قابل قبول نمی‌باشند.
ستون cabin را به علّت تعداد زیاد مقادیر null، ستون name و ستون ticket را نیز به این دلیل که برای هر فرد، منحصر به فرد می‌باشد و یافتن روابط در آن ها دشوار می‌باشد از داده‌ها حذف می‌کنیم.
ستون‌های دارای مقادیر غیر عددی یا ستون‌هایی که عدد آن ها نشان دهنده ی مقدار آن ها نمی باشد را نیز به ستون‌هایی، به تعداد مقادیر مختلفی که می‌توانند داشته باشند، تقسیم می‌کنیم؛ 
برای مثال ستون Pclass که می‌تواند دارای مقادیر 1، 2 یا 3 باشد، به سه ستون 1 و 2 و 3 تقسیم می‌شود که برای فردی که در کلاس 3 بوده، این ستون‌ها به ترتیب مقادیر 0 و 0 و 1 خواهند داشت.
تفاوت این پروژه با نسخه ی قبلی در سایت بوته این است که طبق روش هایی که  در تابع get_manipulated_train آمده است برای تعیین سن مسافرانی 
که محتوایی ندارد استفاده از interpolate گفته شده بود که در حال حاضر ابتدا برای این کار مقادیر random بین age_avg-age-std و age_avg+age_std انتخاب می شوند. سپس با توجه به sex, pclass و title از روی داده ی اوّلیه، می توان به نتایج زیر رسید:
![شکل 6](http://uupload.ir/files/in5_screen_shot_2017-12-28_at_7.34.01_am.png)
که از این اطّلاعاتِ در کد، برای تعیین سن های مشخص نشده استفاده می کنیم .
سپس برای بازه های مختلفِ سن و کرایه، مقدار در نظر گرفته شده است که باعث یادگیری بهتر می شود.
برای دقیق تر شدن تعداد اعضای خانوده هر فرد که در کشتی بودند را نیز از روی sibSp,Parch می فهمیم با توجه به تست و مطالب موجود در منابع تنها بودن فرد نیز موثر است که یک ستون دیگر به نام isAlone تعریف کردیم. 
معیار دیگر لقب های هر شخص است که در تصویر زیر تاثیر  مورد بررسی قرار داده شده است :
![](http://uupload.ir/files/fvm_screen_shot_2017-12-28_at_7.55.53_am.png)
ورودی که در نهایت train می شود، به فرمت زیر می شود:
![](http://uupload.ir/files/3kce_screen_shot_2017-12-28_at_8.09.59_am.png)
درخت تصمیم، در قسمت کار‌های مرتبط توضیح داده شد. نتایج، در هر بار اجرا، متفاوت می‌باشند؛ لذا میانگینِ 20 بار اجرا در نظر گرفته شده است.
که همان طور که انتظار می‌رفت، درخت، در عمق‌های زیاد، دچار بیش‌برازش می‌شود.
پیاده سازی این قسمت در فایل  [DecisionTree.py](https://github.com/AhmadYaghoubi/PredictingTitanicSurvivorsDT/tree/master/Phase%202)است.
#بهبود نتایج و کد های مربوطه
در فاز سوم پروژه سعی ما بر این بود که به بهبود کد خود بپردازیم و نتایج را مشاهده و ثبت کنیم.
پیاده سازی این قسمت در [Github](https://github.com/AhmadYaghoubi/PredictingTitanicSurvivorsDT/tree/master/Phase%203) قرار دارد.
**لازم به توضیح است** که هنگام اجرای کد، خودِ کامپایلر پایتون، باید یک فایل به نام decision_tree.csv ایجاد کند؛ که اگر ایجاد نکرد، از خواننده ی محترم درخواست می شود خود به صورت دستی این فایل را ایجاد کند.
ابتدا با یک تست ابتدایی به دیاگرام زیر می رسیم:
![40% افراد زنده می مانند و 60% می میرند.](https://boute.s3.amazonaws.com/278-Untitled.png) 
در تست بعدی ما نمودار زیر را مشاهده خواهیم کرد:
در قسمت چپ تصویر، مشاهده می کنیم که افراد مسن تر، شانس کمتری برای زنده ماندن دارند؛ و قسمت راست تصویر، بیانگر این است که افراد جوان تر، بیشتر زنده مانده اند.
![0 به معنی مرده و 1 به معنی زنده است؛ محور عمودی، نمایانگر سنّ افراد است.](https://boute.s3.amazonaws.com/278-313.png) 
پس از بررسی دیگری، درخواهیم یافت که که 55% مسافران، بلیط درجه 3 ی داشتند؛ 25% افراد، جایگاهشان در قسمت درجه ی 1 و باقی افراد در درجه ی 2 بوده است.
نمودار جالب زیر، بیانگر این است که میانگین سنی مسافران، با درجه ی بلیطشان رابطه عکس دارد؛ بدین معنا که هرچه درجه ی بلیط ها بهتر باشد، میانگین سنّی افراد، بیشتر خواهد بود!!!
![نمودار افقی، بیانگر سن و نمودار عمودی، نمایانگر تراکم جمعیت در هر بازه ی سنّی خاص می باشد. ](https://boute.s3.amazonaws.com/278-316.png)
دیاگرام زیر، بیانگر این است که تقریباً 70% مسافران، از بندر ساوت همپتون سوار کشتی شدند؛ بعد از آن تعدادی از فرانسه، و کمترین تعداد مسافران، مربوط به ایرلند می باشد.
![Q: Queensland (Ireland), S: Southampton, وسط: فرانسه](https://boute.s3.amazonaws.com/278-318.png)
نمودارهای زیر، بیانگر درصد زنده ماندن و مردن در کل و نیز به تفکیک جنسیت است:
![سمت راست: زنان، وسط: مردان، چپ: نمودار کلّی](https://boute.s3.amazonaws.com/278-319.png)
از جمع بندی نمودارهای بالا، نمودار زیر نتیجه گیری می شود:
![تقسیم بندی زنان و مردان، از لحاظ زنده ماندن](https://boute.s3.amazonaws.com/278-320.png)
در نمودار زیر مشاهده می شود که اکثر زنده مانده ها از جایگاه درجه ی 1 و اکثر فوت شده ها از جایگاه درجه ی 3 می باشند و در کل، اکثر افراد مردند. 
![0 برای مردگان و 1 برای افراد زنده](https://boute.s3.amazonaws.com/278-321.png) 
نمودارهای زیر، درصد **مردان** مرده و زنده ی فقیر و ثروتمند را مقایسه می کنند:
![سمت راست: فقرا، سمت چپ: ثروتمندان، 0: مرده، 1: زنده](https://boute.s3.amazonaws.com/278-322.png) 
امّا نمودارهای زیر، درصد **زنان** مرده و زنده ی فقیر و ثروتمند را مقایسه می کنند:
![سمت راست: فقرا، سمت چپ: ثروتمندان، 0: مرده، 1: زنده](https://boute.s3.amazonaws.com/278-325.png)
##درخت تصمیم نهایی
ما در این فاز، عمق درخت تصمیم خود را 2 واحد افزایش دادیم و به حدّاکثر عمق 7 رسیدیم. درخت تصمیم نهایی حاصل از این کد بهبود یافته، در شکل زیر مشاهده می شود:
![درخت تصمیم حاصل از کد بهینه شده ی ما در این پروژه](https://boute.s3.amazonaws.com/278-decision_tree.png)
همان طور که پیش بینی می شد، با افزایش عمق درخت تصمیم، دچار بیش برازش می شویم!
# کارهای آینده
از بین داده های موجود، ارتباطات و نظم های بیشتری بین ستون ها کشف کنیم که منجر به تولید ستون های جدید و یادگیری بهتر شوند.
استفاده از روش‌های دیگر(برای مثال شبکه‌های عصبی) برای حدس زدن سن
راه حلّ درخت تصمیم بسیار مناسب است، امّا با آزمایشات مختلف به نظر می رسد که روش جنگل تصادفی (Random Forest)، گاهی اوقات بهتر از درخت تصمیم عمل می کند؛ بنا بر این خوب است که روی آن روش، سرمایه گذاری بیشتری شود.
برای هر یک از افراد، عمل پیش بینی را با استفاده از روش‌های مختلف انجام داده و پیش بینی‌ای که تعداد بیشتری پیش بینی درست داشته باشد را
انتخاب نماییم.
می توان برای رسمی تر شدن آزمایش ها، به جای این که 30% داده های train شده را به عنوان تست قرار دهیم، نمونه داده های مربوط به تست و train را جدا کنیم. ما در این پروژه، با هدف یادگیری بهتر، با استفاده از نمونه های بیشتر، این کار را انجام ندادیم.

# مراجع
[1]  Induction of Decision Trees, by J.R. QUINLAN, Centre for Advanced Computing Sciences, New South Wales Institute of Technology, Sydney, 2007, Australia

[2]  Prediction of Survivors in Titanic Dataset: A Comparative Study Using Machine Learning Algorithms, Tryambak Chatterjee, Department of Management Studies, NIT Trichy, Tiruchirappalli, Tamilnadu, India

 [3]  Study of Data Mining Algorithm Based on Decision Tree, IEEE
 
[4]  http://adataanalyst.com/kaggle/4-different-ways-predict-survival-titanic-part-3/

[5]  https://www.kaggle.com/sinakhorami/titanic-best-working-classifier/notebook

[6]  http://www.r2d3.us/visual-intro-to-machine-learning-part-1/

[7]  https://av.tib.eu/media/31273

[8]  https://en.wikipedia.org/wiki/Decision_tree

[9]  http://www.boute.ir/iust-ai-94/survived-passengers

[10]  https://pandas.pydata.org/pandas-docs/stable/tutorials.html

# پیوندهای مفید

+ [صفحه این مسابقه](https://www.kaggle.com/c/titanic)

+ [درخت تصمیم](https://en.wikipedia.org/wiki/Decision_tree_learning)

+ [توصیح تصویری درخت تصمیم](http://www.r2d3.us/visual-intro-to-machine-learning-part-1/)

+ [آشنایی با یادگیری ماشین](http://www.toptal.com/machine-learning/machine-learning-theory-an-introductory-primer)

+ [توضیح درخت تصمیم](http://dms.irb.hr/tutorial/tut_dtrees.php)

+ [راهنمای برطرف کردن خطاهای کد برنامه](https://stackoverflow.com/)