در این پروژه سعی خواهم کرد که یکی از مسابقات سایت Kaggle.com که از طریق این لینک قابل دسترسی می‌باشد را بررسی کنیم. در این مسابقه از شرکت کنندگان خواسته شده که با استفاده از اطلاعات داده شده درباره مسافران کشتی تایتانیک که در مجموعه داده‌¹های مسابقه ارایه شده پیشبینی کنند که چه کسی از تایتانیک جان سالم بدر برده است. در ادامه ابتدا توضیحاتی راجع به داده‌های مسئله داده می‌شود سپس تعدادی از روش‌‌هایی که برای حل مسئله مطرح هستند بررسی خواهند شد.

۱. مقدمه

در حادثه برخورد کشتی تایتانیک به کوه یخ 1502 نفر از 2224 مسافر و خدمه کشتی کشته شدند که یکی از دلایل آن عدم تعبیه قایق نجات به تعداد لازم بود.
هرچند که می‌توان شانس را یکی از عوامل تاثیرگذار در نجات یافتن افراد بیان کرد اما برای برخی افراد مانند زنان و بچه‌ها و افرادی که در قسمت‌های با درجه² بالاتر جای داشتند احتمال بیشتری وجود داشت که نجات پیدا کنند.
داده‌های مسأله بصورت فایل‌های csv ³ در اختیار کاربران قرار داده شده اند. در شکل زیر اطلاعات داده شده و توضیحات آنها آورده شده است.

قسمتی از داده‌ها:

همانطور که در شکل مشخص می‌باشد برای برخی افراد بعضی ویژگی‌ها دارای مقدار نمی‌باشند.
مجموعه داده‌ها دارای 819 نمونه می‌باشد.
مجموعه داده شده جهت تست نیز دارای 418 نمونه است.
در صورتی که یک بررسی اولیه بر روی داده‌ها انجام دهیم نتایج زیر بدست می‌آیند.

همانطور که مشاهده می‌کنید جنسیت مسافر در نجات یافتن وی بسیار تاثیر گذار می‌باشد چنانکه 74 درصد زنان زنده ماندند در حالی که تنها 18 درصد مردان نجات پیدا کردند. این اطلاعات درک کلی از شرایط مسئله در اختیار ما قرار می‌دهند.

۲. کارهای مرتبط

در منابع ذکر شده روش‌های Naïve Bayes، Decision Tree، Random Forest استفاده شده اند که سعی خواهیم کرد هر یک را در حد امکان قابل درک بررسی کنیم. برای هر روش پیشنهادی در ابتدا راجع به کلیت روش توضیح داده شده سپس روش را برای مسئله داده شده بکار خواهیم برد.

۲.۱. [1]روش Naïve Bayes

در این روش از قوانین احتمال شرطی جهت رسیدن به احتمال زنده ماندن یک فرد استفاده می‌کنیم.

(احتمال outcome به شرطی که شرط evidence محقق شده باشد)
بنابراین زمانی که بخواهیم احتمال زنده ماندن (outcome) را بر اساس یک ویژگی در فرد محاسبه کنیم این رابطه به کمک ما خواهد آمد.
برای مثال می‌خواهیم محاسبه کنیم که اگر شخصی زن باشد
احتمال زنده ماندن آن چه قدر است. اگر p(s) را احتمال رنده ماندن در نظر بگیریم:

که مقادیر (P(s) ، P(female | s و(P(female قابل محاسبه می‌باشند. برای مثال (P(female|s (احتمال زن بودن به شرط زنده ماندن) نمایان‌گر ان است که چند درصد نجات یافتگان زن می‌باشند که با استفاده از اطلاعات مسئله به سادگی قابل محاسبه می‌باشد.
حال اگر بخواهیم چند شرط را در نظر بگیریم رابطه بالا به شکل زیر در می‌آید:

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

همانطور که از جدول بالا مشخص می‌باشد فقط با در نظر گرفتن جنسیت افراد دقت 76.79 درصد به دست آمده است. این در حالی است که اضافه کردن ویژگی‌های دیگر نتنها نتایج را بهبود نبخشیده بلکه در مواردی باعث کاهش آن شده است. این موضوع به خاطر تاثیر بسیار زیاد جنسیت می‌باشد. اگر سایر ویژگی‌ها را بدون جنسیت در نظر بگیریم دقت 65.79 درصدی حاصل می‌شود که نمایانگر این موضوع می‌باشد که اگرچه این ویژگی‌‌ها به اندازه جنسیت موثر نمی‌باشند اما همچنان در احتمال زنده ماندن فرد تاثیرگذارند.

۲.۲. درخت تصمیم⁴[1,2]

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

1. برگ ها مشخص کننده‌ی ویژگی هدف(در اینجا احتمال زنده ماندن) می‌باشند.

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

   

   
   در این شکل اگر به یکی از برگ‌های سبز رسیدیم مسافر را نجات‌یافته و در غیر این صورت غرق شده به حساب می آوریم.
   الگوریتم‌هایی که برای ایجاد درخت تصمیم استفاده می‌شوند معمولا بشکل بالا به پایین کار می‌کنند به این صورت که در هر مرحله متغیری را که به بهترین شکل مجموعه داده ها را تقسیم می‌کند انتخاب می‌کند. الگوریتم‌های مختلف معیار‌های مختلفی از بهترین ارایه می‌دهند که برای اطلاعات بیشتر می‌توانید به این لینک مراجعه نمایید.
   نویسنده مقاله مرجع در این روش از ویژگی‌های جنسیت، درجه مسافر، سن و کرایه⁶ استفاده کرده است. در ابتدا داده‌ها صرفا بر اساس جنسیت دسته بندی شده‌اند که دقت 76.79 درصدی حاصل شده است(شکل3). که همانطور که انتظار می‌رفت با نتایج بدست آمده ار روش اول همخوانی دارد چراکه با این شرط هر دو روش به شکلی یکسان با داده برخورد می‌کنند(یعنی مردان را مرده و زنان را نجات یافته به حساب می‌آورند).
   در مرحله بعد هرکدام از شاخه‌های مردان و زنان براساس درجه تقسیم بندی شده اند. همانطور که در شکل3 مشخص است برای تمام درجات احتمال زنده ماندن مردان کمتر از 50% می‌باشد که بدین معنی می‌باشد احتمالا بهتر است نتیجه این برگ ها را مرگ در نظر بگیریم. اما شرایط برای زنان بگونه‌ای دیگر است. در شاخه زنان در همه درجات به غیر از درجه 3 احتمال زنده ماندن بیشتر از 50% می‌باشد. اگر نتیجه کلاس 3 را هم زنده ماندن در نظر بگیریم همان نتیجه مرحله قبل(76.79%) بدست می آید چراکه باز هم مردان مرده و زنان نجات یافته به حساب می‌آیند. ولی اگر نتیجه این برگ را مرگ در نظر بگیریم دقت به (77.27%) افزایش می‌یابد.
   سپس نوبت به سن می‌رسد. سن یک مقدار نسبتا پیوسته دارد نبابراین تصمیم‌گیری چگونگی انتخاب معیار تصمیم‌گیری بسیار مهم می‌باشد. بصورت کلی افراد با سن کمتر احتمال زنده ماندن بیشتری نسبت به افراد مسن تر داشته اند. در مقاله منبع ذکر شده که بجای اینکه برای همه‌ی درجه های جنسیت ها در درخت، معیار یکسانی انتخاب شود هر کدام از درجه‌ها در هرکدام از جنسیت را بصورت جداگانه مورد بررسی قرار داده تا معیار مناسبی جهت تقسیم بندی هرکدام بر اساس سن انتخاب کنند. انتخاب این معیار براین اساس بوده است که اگر افرادی که سن کمتری از معیار سنی دارند و افرادی که سن بیشتری از معیار سنی دارند را طبقه بندی کنیم خطای طبقه بندی در مجموعه داده آموزشی⁷ کمتر باشد. پس از این کار دقت به 78.94% افزایش یافت.متاسفانه منبع ذکر شده جزئیات بیشتری در رابطه با چگونگی انتخاب معیار‌ها و یا حتی مقدار دقیق معیار‌ها ذکر نکرده است.

۲.۳. جنگل تصادفی⁸[3,2]

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

حال مسافری زنی که جایگاهی در درجه یک دارد و در (Southampton(s سوار کشتی شده است را در نظر بگیرید. دو درخت اول و سوم فرد را نجات‌یافته طبقه‌بندی می‌کنند در حالی که درخت دوم مرگ مسافر را پیشبینی می‌نماید.بنابراین نجات یافتن به عنوان نتجه بازگردانده می شود در این روش سعی می‌شود که درخت تا حد امکان عمیق شود ولی از آنجایی که روش رشد درخت‌ها مشابه یکدیگر است لازم است که روش‌هایی جهت بوجود آوردن تصادف ¹⁰ استفاده شوند.
اولین روش استفاده از کیسه بندی¹¹ می‌باشد که از تکنیک Bootstrap aggregating استفاده می‌کند. در این روش بر روی داده‌های ورودی یک نمونه‌گیری با جایگذاری انجام می‌شود البته به گونه‌ای که واریانس کاهش داده شده تا دقت اگوریتم‌های یادگیری ماشینی افزایش یابد. برای مثال تابع sample در زبان R در مقاله ذکر شده است.

sample(1:10, replace = TRUE)
3 1 9 1 7 10 10 2 2 9

همانطور که مشخص می‌باشد نمونه برگردانده شده همچنان دارای 10 عنصر می‌باشد ولی بعضی از عناصر آن تکراری می‌باشند. در این روش بطور میانگین 37% عناصر از ارایه ورودی حذف می‌شوند. بدین صورت درخت‌‌‌هایی که از این ورودی ها ایجاد می‌شوند با هم اندکی متفاوت رشد خواهند کرد ولی همچنان عوامل تاثیر گذاری مانند جنسیت به احتمال زیاد به عنوان اولین معیار تقسیم‌بندی استفاده خواهد شد. برای اینکه این مشکل نیز حل شود از روش دیگری برای ایجاد تصادف استفاده می‌شود. در این روش بجای استفاده از تمام ویژگی‌های موجود به عنوان معیار تصمیم‌گیری از تعداد محدودی از آنها (معمولا ریشه دوم تعداد ویژگی‌‌ها که در اینجا 10 می‌باشد استفاده می‌شود که عدد 3 را برای این مسئله نتیجه می‌دهد) استفاده می‌شود بدین صورت که در هر گره تصمیم گیری مجموعه متفاوتی از ویژگی‌ها جهت انتخاب ارایه میشوند می‌شوند. برای مثال برای یک درخت،اجازه انتخاب از بین سن، درجه،جنسیت برای اولین معیار تقسیم بندی (root) داده می‌شود در حالی که برای درختی دیگر اجازه انتخاب از بین سن ، تعداد اعضاء خانواده و محل سوار شدن داده می‌شود بنابراین بسیاری از درختان امکان انتخاب جنسیت به عنوان اولین معیار نخواهند داشت. همین روال برای سایر گره های تصمیم گیری طی می شود. بنابراین درخت‌های متفاوت تری تولید خواهند شد. با استفاده از این دو روش مجموعه‌ای از درختان متفاوت خواهیم داشت که برای هر ورودی پس از دادن آن به همه عنوان ورودی همه درخت ها پاسخی که بیشترین تعداد را داشته باشد برخواهیم گزید. در مقاله مربوطه برای پیشبینی سن افرادی که سن آنها ذکر نشده در زبان R با استفاده از کسانی که سن آنها در داده‌ها آورده شده است و با استفاده از تابع rpart یک درخت تصیمیم با هدف پیشبینی سن ایجاد شده که برای پیشبینی سن افراد فاقد این ویژگی استفاده شده است. پس از جایگذاری سن‌های پیشبینی شده، در زبان R و با استفاده از تابع randomForest ، تعداد 2000 درخت تصادفی ایجاد کرده است. در نهایت نتایجی که از این روش بدست آمده اند دارای دقت 81.342% درصد می‌باشند.
نتایج بدست آمده از روش‌های ذکر شده در شکل زیر مقایسه شده است.

۳. آزمایش‌ها

۴. کارهای آینده

۵. مراجع

[1]Eric Lam,Chongxuan Tang.(2015).Titanic – Machine Learning From Disaster
[2]Xiaodong Yang .(2015).Titanic – Machine Learning From Disaster
[3]Kunal Vyas, Zeshi Zheng, Lin Li.(2015).Titanic - Machine Learning From Disaster

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

• صفحه این مسابقه

• درخت تصمیم

• توصیح تصویری درخت تصمیم

• روشnaive bayes

• توضیحnaive-bayes به زبان ساده

• آشنایی با یادگیری ماشینی

• توضیح درخت تصمیم

• جنگل تصادفی