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

در این پست می‌خواهم با یک مثال ساده نحوه‌ی عملکرد الگوریتم درخت تصمیم(Decision Tree) را که یکی از الگوریتم‌های مهم در یادگیری ماشین برای طبقه‌بندی است را توضیح بدهم.

اگر بخواهم به ساده‌ترین شکل این الگوریتم را در یک جمله توصیف کنم، باید بگویم این الگوریتم شبیه بازی ۲۰ سوالی می‌باشد. ما در طول حل مساله یک گراف درخت رسم می‌کنیم که گره‌های میانی آن سوال‌ها هستند و گره‌های برگ آن خروجی طبقه‌بندی را مشخص می‌کنند. یک گراف ساده را که یک الگوریتم درخت تصمیم را نشان می‌دهد بررسی می‌کنیم. فرض کنید می‌خواهیم زنده ماندن یا نبودن مسافران کشتی تایتانیک را پیش‌بینی کنیم. برای این‌کار گراف درخت تصمیم را بر اساس سوالات زیر به این صورت رسم می‌کنیم. سوال اول: آیا مسافر کشتی مرد بوده است یا زن؟ اگر زن بوده است، احتمالا نجات پیدا کرده و زنده مانده است. اگر مسافر مرد بوده آیا سن او بیشتر از ۹/۵ سال بوده است؟ اگر بالای ۹/۵ سال بوده است احتمالا جان سالم به در نبرده و زنده نمانده است. ولی اگر کمتر از ۹/۵ سال سن داشته است، آیا بیشتر از ۲ خواهر یا برادر داشته است؟ اگر بیشتر داشته است احتمالا زنده نمانده است، ولی اگر کم‌تر از ۲ خواهر یا برادر داشته است احتمالا جان سالم به در برده است و زنده مانده است. شکل زیر گراف درخت تصمیم را برای این مساله نشان می‌دهد.

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

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

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

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

همانطور که در شکل بالا مشخص است، بعد از اولین تقسیم دو مجموعه داده داریم که در یکی فقط جنسیت زن و در دیگری فقط جنسیت مرد وجود دارد. به همین دلیل در هر مجموعه داده دیگر ستون جنسیت دارای اطلاعات ارزشمندی نیست و آن را با رنگی متفاوت مشخص کرده‌ایم. حال مرحله‌ی دوم را همانند مرحله‌ی اول ولی این بار برای هر دو مجموعه داده انجام می‌دهیم. یعنی در هر دو مجموعه داده به دنبال ویژگی می‌گردیم که بیشترین information gain را داشته باشد. در مجموعه داده مربوط به زن‌ها هیچ ویژگی وجود ندارد که بتواند با یک حداقل دقت مناسب طبقه‌بندی را انجام دهد.(اکثر داده‌ها دارای لیبل زنده بودن می‌باشد) بنابراین فرآیند تقسیم برای مجموعه داده‌ی زن‌ها در این مرحله متوقف می‌شود و اولین برگ گراف در اینجا تولید می‌شود و آن برگ نشان‌دهنده زنده بودن می‌باشد. ولی در مجموعه داده‌ی مربوط به مردها ویژگی سن دارای حداقل دقت طبقه‌بندی و دارای بیشترین information gain می‌باشد. یعنی اگر ویژگی سن را بر اساس مقادیر کوچکتر از ۹/۵ سال و بزرگ‌تر از ۹/۵ سال دسته‌بندی کنیم، می‌توانیم با دقت خوبی طبقه‌بندی را انجام دهیم. در شکل زیر بخشی از مجموعه داده‌های مردان را بعد از تقسیم بر اساس سن مشاهده می‌کنیم.

فرآیند پیدا کردن ویژگی با بیشترین information gain را دوباره برای هر دو مجموعه داده‌ی بالا انجام می‌دهیم. این فرآیند را برای مجموعه داده‌های بدست آمده تا زمانی ادامه می‌دهیم که یا دیگر ویژگی با information gain خوب وجود نداشته باشد( مانند مجموعه داده‌ی مربوط به زن‌ها) یا اینکه دیگر ویژگی جدیدی وجود نداشته باشد و همه ویژگی ها را بررسی کرده باشیم. و به این ترتیب برگ‌های گراف بر اساس لیبل بدست آمده در هر مجموعه داده را مشخص می‌کنیم. در این مساله خاص نتیجه نهایی درخت تصمیم همانند شکل اول خواهد بود که دوباره آن را در زیر آورده‌ایم.

حال سوالی که پیش می‌آید این است که این information gain مربوط به هر ویژگی چگونه محاسبه می‌شود؟ روش‌های آماری وجود دارد که با محاسبات ریاضی این مقادیر را بدست می‌آورند که هدف من در اینجا توضیح ریاضی آن نیست. برای کسانی که علاقه‌مند به یادگیری حل ریاضی آن هستند، کتاب‌های مرجع زیادی وجود دارد. ولی کسانی که می‌خواهند از این الگوریتم‌ها استفاده کنند و به دنبال یادگیری حل ریاضی آن نیستند، کتابخانه‌هایی در زبان‌های برنامه نویسی مانند پایتون وجود دارد که تمامی این محاسبات را برای آن‌ها انجام می‌دهد. یکی از این کتاب‌خانه‌ها scikit learn می‌باشد که برای زبان برنامه‌نویسی پایتون است و کار شما را برای کار با این الگوریتم بسیار راحت کرده است. سعی می‌کنم در پست بعدی یک مثال عملی با زبان پایتون و نحوه‌ی استفاده از الگوریتم درخت تصمیم را به کمک کتابخانه scikit learn توضیح بدهم.