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

در این پروژه سعی خواهید کرد که یکی از مسابقات سایت Kaggle.com که از طریق این [لینک](https://www.kaggle.com/c/titanic) قابل دسترسی می‌باشد را بررسی کنید. در این مسابقه از شرکت کنندگان خواسته شده که با استفاده از اطلاعات داده شده درباره مسافران کشتی تایتانیک که در مجموعه داده‌های مسابقه ارایه شده پیش‌بینی کنند که چه کسی از تایتانیک جان سالم به در برده است. 
# مقدمه

# کارهای مرتبط

# آزمایش‌ها**بِسمِ اللّهِ الرَّحمنِ الرَّحیم**

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

# مقدمه
در حادثه ی برخورد کشتی بخار بزرگ تایتانیک به کوه یخ، که در تاریخ 15 آوریل 1912، از بندر ساوت همپتون انگلستان به مقصد نیویورک آمریکا در سفر بود، 1514 نفر از 2224 مسافر و خدمه ی کشتی، کشته شدند؛ که یکی از دلایل اصلی آن عدم تعبیه ی قایق نجات، به تعداد لازم بود.
هر چند که می توان شانس را یکی از عوامل تأثیر گذار در نجات یافتن افراد بیان کرد؛ امّا برای برخی افراد، مانند زنان و بچّه ها
و افرادی که در قسمت های با درجه ی بالاتر جای داشتند، احتمال بیشتری وجود داشت که نجات پیدا کنند.
داده های مسئله، به صورت فایل های [^Comma-separated values]csv،  در اختیار کاربران قرار داده شده اند.
در شکل زیر ، اطّلاعاتِ داده شده و توضیحات آن ها آورده شده است.![شکل 1- اطّلاعات داده شده راجع به مسافران](https://boute.s3.amazonaws.com/278-1MpPa2D.png)
قسمتی از داده ها نیز در شکل پایین، قابل مشاهده می باشند.![شکل 2- قسمتی از داده ها](https://boute.s3.amazonaws.com/278-4wCqrcS.png)
همان طور که در شکل 2 مشخّص است، برای برخی افراد، بعضی ویژگی ها، دارای مقدار نمی باشند.
مجموعه ی داده ها، دارای 819 نمونه می باشد.
مجموعه ی داده شده جهت تست، دارای 418 نمونه است.
در صورتی که یک بررسی اوّلیه بر روی داده ها انجام دهیم، نتایج شکل زیر به دست می آیند.![شکل 3- بررسی اوّلیه](https://boute.s3.amazonaws.com/278-OanANSO.png) 
همان طور که مشاهده می کنید، جنسیت مسافر، در این که نجات پیدا می کند یا خیر، بسیار تأثیر گذار می باشد؛ چنان که 74% زنان زنده ماندند؛ در حالی که تنها 18% مردان توانستند نجات پیدا کنند.
این اطّلاعات، یک درک کلّی از شرایط مسئله، در اختیار ما قرار می دهد.

# کارهای مرتبط
در منابع ذکر شده، روش های جنگل تصادفی، درخت تصمیم، شبکه های عصبی، ماشین بردار پشتیبان، 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 درصدی حاصل شده است (شکل3).
در مرحله ی بعد، هر کدام از شاخه‌های مردان و زنان بر اساس درجه، تقسیم بندی شده اند.
همان طور که در شکل 3 مشخّص است، برای تمام درجات، احتمال زنده ماندن مردان، کمتر از 50% می‌باشد که بدین معنی می‌باشد که
احتمالاً بهتر است نتیجه ی این برگ ها را مرگ در نظر بگیریم.
امّا شرایط برای زنان، به گونه‌ای دیگر است. در شاخه زنان، در همه ی درجات، به غیر از درجه ی 3، احتمال زنده ماندن بیشتر از 50% می‌باشد.
اگر نتیجه ی کلاس 3 را هم زنده ماندن در نظر بگیریم، همان نتیجه ی مرحله ی قبل ( 76.79% ) به دست می آید؛ چرا که باز هم مردان، مرده و
زنان، نجات یافته به حساب می‌آیند.
ولی اگر نتیجه ی این برگ را مرگ در نظر بگیریم، دقّت به 77.27% افزایش می‌یابد.
سپس نوبت به سن می‌رسد. سن، یک مقدار نسبتاً پیوسته دارد؛ بنا بر این تصمیم‌گیریِ چگونگیِ انتخابِ معیارِ تصمیم‌گیری، بسیار مهم می‌باشد.
به صورت کلّی، افراد با سنّ کمتر، احتمال زنده ماندن بیشتری نسبت به افراد مسن تر داشته اند. در مقاله ی منبع، ذکر شده که
به جای این که برای همه‌ی درجه های جنسیت ها در درخت، معیار یکسانی انتخاب شود، هر کدام از درجه‌ها در هر کدام از جنسیت ها را به صورت جداگانه مورد بررسی قرار داده تا معیار مناسبی جهت تقسیم بندی هر کدام بر اساس سن انتخاب کنند. انتخاب این معیار بر این اساس بوده است که اگر افرادی که سنّ کمتری از معیار سنّی دارند و افرادی که سنّ بیشتری از معیار سنّی دارند را طبقه بندی کنیم، خطای طبقه بندی در مجموعه ی داده آموزشی[^Training data]، کمتر باشد.
پس از این کار دقّت به 78.94% افزایش یافت. متأسّفانه منبع ذکر شده جزئیات بیشتری در رابطه با چگونگی انتخاب معیار‌ها و یا حتّی مقدار دقیق معیار‌ها ذکر نکرده است.

# آزمایش‌ها
**1-3- پیش نیاز**
جهت اجرای کد برنامه که از  [لینک](https://github.com/AhmadYaghoubi/PredictingTitanicSurvivorsDT)قابل دست رسی است، نیاز به ماژول‌هایی می‌باشد که در فایل 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 از روی داده اولیه می توان به نتایجی رسید که از این اطلاعات در کد برای تعیین سن های مشخص نشده استفاده می کنیم .
سپس برای بازه های مختلف سن و کرایه مقدار در نظر گرفته شده است که باعث یادگیری بهتر می شود.
برای دقیق تر شدن تعداد اعضای خانوده هر فرد که در کشتی بودند را نیز از روی sibSp,Parch می فهمیم با توجه به تست و مطالب موجود در منابع تنها بودن فرد نیز موثر است که یک ستون دیگر به نام isAlone تعریف کردیم. 
معیار دیگر لقب های هر شخص است که در تصویر زیر تاثیر 
**3-3- روش درخت تصمیم**
درخت تصمیم، در قسمت کار‌های مرتبط توضیح داده شد. نتایج، در هر بار اجرا، متفاوت می‌باشند؛ لذا میانگینِ 20 بار اجرا در نظر گرفته شده است.
نتایجِ به دست آمده، در جدول زیر آورده شده:
![شکل 5- نتایج آزمایش درخت تصمیم](https://boute.s3.amazonaws.com/278-UhxVsqc.png)
همان طور که انتظار می‌رفت، درخت، در عمق‌های زیاد، دچار بیش‌برازش می‌شود.
پیاده سازی این قسمت در فایل [DecisionTree.py](https://github.com/AhmadYaghoubi/PredictingTitanicSurvivorsDT/blob/master/First-Second_Fase/DecisionTree.py) آورده شده است.

# کارهای آینده

# مراجع

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

+ [صفحه این مسابقه](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/)

+ [روشnaive bayes](http://scikit-learn.org/stable/modules/naive_bayes.html)

+ [توضیحnaive-bayes به زبان ساده](https://stackoverflow.com/questions/10059594/a-simple-explanation-of-naive-bayes-classification/20556654#20556654)

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

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

+ [جنگل تصادفی](https://en.wikipedia.org/wiki/Random_forest)

+ [آشنایی با شبکه‌های عصبی](http://andrew.gibiansky.com/blog/machine-learning/machine-learning-neural-networks/)