درخت تصمیم گیری تحولی: وقتی یادگیری ماشین از علم زیست‌شناسی الهام می‌گیرد

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

برای نمونه قطار پرسرعت ژاپنی Shinkansen را در نظر بگیرید که با سرعت ۳۰۰ کیلومتر بر ساعت یکی از سریع‌­ترین قطارهای جهان به شمار می‌­رود. در زمان طراحی این قطار، مهندسان به یک مشکل جدی برخوردند و آن صدای بسیار بلند قطار بود که به دلیل جابجایی سریع جریان هوای جلوی قطار ایجاد می­‌شد؛ این صدا به قدری زیاد بود که می­‌توانست به بعضی از تونل­‌ها آسیب وارد کند.

مهندسان برای حل این مسئله از یک منبع غیرمعمول استفاده کردند: مرغ ماهی‌­خوار kingfisher! این پرنده یک نوک بلند و کشیده دارد که او را قادر می­‌سازد با کمترین سروصدا درون آب شیرجه بزند.

بدین ترتیب با طراحی مجدد قطار به شکل این پرنده مهندسان توانستند مشکل صدای بلند قطار را از بین ببرند، علاوه بر این مصرف برق قطار را ۱۵% کاهش و سرعت آن را ۱۰% افزایش دهند.

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

در این مقاله روی درخت‌­های تصمیم تمرکز خواهیم داشت.

درخت­‌های تصمیم­‌گیری رده‌­بند classifierهایی هستند که از الگوریتم­‌های تحولی Evolutionary algorithms استفاده می­‌کنند. این الگوریتم­‌ها متکی بر مکانیزم‌­هایی الها‌‌م­‌گرفته از فرآیند تحول طبیعی هستند که به ساخت درخت‌­های تصمیم با عملکردی خوب و قوی منجر می‌شوند. بعد از مطالعه­ این متن قادر خواهید بود به این سؤالات پاسخ دهید:

• درخت تصمیم چیست؟
• چطور از الگوریتم‌­های تحولی برای ساخت یک درخت تصمیم استفاده کنیم؟
• عملکرد درخت­‌های تصمیم تحولی در مقایسه با سایر رده‌­بندها چگونه است؟

دیتاست

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

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

۱- درخت تصمیم چیست؟

درخت تصمیم به رده­‌بندی گفته می­‌شود که بر یک گردش­کار Flow-chart شبه درخت مبتنی است. مدل زیربنایی درختِ تصمیم با یادگیری چند قانون تصمیم­‌گیری ساده که از ویژگی­‌های داده‌­ها استنباط شده‌­اند،­ مشاهدات را رده‌­بندی می‌­کند.

نمودار پایین نمونه­‌ای از یک درخت تصمیم را نشان می­‌دهد که بر روی داده­‌های نظرسنجی مذکور و با استفاده از ماژول درخت تصمیم Sickit-learn آموزش داده شده است.

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

درخت­‌های تصمیم کاربرد زیادی در مسائل رده­‌بندی دارند، زیرا از مزایای متعددی برخوردارند از جمله:

• ذات تفسیرپذیر interpretable و قابل درکی comprehensible دارند که به استدلال آدمی شبیه است؛
• قابلیت کار با داده‌­های عددی numerical و دسته‌­ای categorial را دارند؛
• به صورت هرمی تجزیه‌پذیر Hierarchical decomposition هستند که باعث می­‌شود از متغیرها استفاده­ بهتری داشته باشند.

اکثر الگوریتم­‌هایی که به منظور ساخت یک درخت تصمیم به کار برده می­‌شوند بر یک راهکار پارتیشن‌­بندی بالا به پایین بازگشتی حریصانه A greedy top-down recursive partitioning strategy متکی هستند.

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

معیارهایی که برای تعیین بهترین راه تولید آزمون در گره‌­ها و شاخه­‌ها وجود دارند، برای هر الگوریتم متفاوت هستند. متداول­‌ترین معیارها کسب اطلاعات Information gain (یا آنتروپی) و ناخالصی جینی Gini impurity هستند. این دو مورد مربوط به اندازه­‌گیری ناخالصی می­‌باشند، بدین معنی که زمانی که همه­ نمونه­‌های یک گره به یک رده تعلق داشته باشند، مقدار آن‌­ها برابر صفر است و وقتی یک توزیع­ یکسان A uniform class distribution داریم به حداکثر مقدار خود می­‌رسند.

اما این استراتژی دو مشکل بزرگ دارد:

1. ممکن است به راهکارهای زیربهینه ختم شود؛
2. می‌­تواند درخت‌­هایی با پیچیدگی بیش از حد تولید کند که قابلیت تعمیم از داده‌­های آموزشی به سایر داده‌­ها را ندارند و در نتیجه منجر به مشکل بیش‌­برازش overfitting می‌­شوند.

به منظور فائق آمدن بر این مشکلات چندین راهکار بیان شده است:

• تکنیک هرس pruning: ابتدا یک درخت تصمیم به صورت کامل ( یعنی تا زمانی که همه­ نمونه­‌های یک برگ به یک رده تعلق داشته باشند) ساخته می­‌شود. سپس با حذف گره‌­ها یا درختچه‌­های اضافی و غیرمعنی­‌دار اندازه­ درخت را کاهش می­‌دهیم.
• درخت­‌های گروهی Ensemble trees: درخت­‌های متفاوت ساخته می­‌شوند و رده­‌بندی نهایی بر اساس قانونی خاص که در اغلب موارد یک طرح رأی­‌گیری Voting scheme است انجام می‌­گیرد. توجه داشته باشید که این تکنیک منجر به از دست رفتن فهم‌پذیری درختان تصمیم می­‌شود.

با توجه به آن­چه گفته شد دریافتیم لازم است گزینه­‌های دیگر را هم برای تولید درخت­‌های مدل بررسی کنیم. در همین راستا اخیراً الگوریتم‌­های تحولی (EAs) توجه زیادی را به خود جلب کرده‌­اند.

این الگوریتم­‌ها به جای جستجوی محلی، یک جستجوی کلی در فضای راهکارهای داوطلب Candidate solutions انجام می‌­دهند. در نتیجه نسبت به روش‌­های حریصانه بهتر می‌­توانند با درهم‌­کنش‌های ویژگی‌ها Feature interactions کار کنند.

حال نحوه­ کار این الگوریتم‌­ها را با هم مشاهده می‌­کنیم.

۲- چطور از الگوریتم‌های تحولی برای ساخت یک درخت تصمیم استفاده کنیم؟

الگوریتم­‌های تحولی، الگوریتم­‌های اکتشافی Search heuristics محسوب می­‌شوند و از مکانیزم­‌هایی استفاده می‌­کنند که الهام­‌گرفته از تحول زیستی در طبیعت هستند.

در این پارادایم هر فرد individual یا هر جمعیت نشان‌­دهنده یک راهکار داوطلب برای یک مسئله خاص است. هر فرد توسط یک مقدار شایستگی Fitness value ارزیابی می‌­شود (مقدار تناسب کیفیت فرد را به عنوان یک راهکار می­‌سنجد). بنابراین اولین جمعیت معمولاً به صورت اتفاقی تعریف شده و سپس در جهت نواحی بهتری از فضا تحول می‌­یابد.

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

علاوه بر این، جمعیت نیز خود دست‌خوش فرآیندهای خاصی می­‌شود که الهام­‌گرفته از ژنتیک هستند؛ همچون:

• تقاطع crossover و جهش mutation یا مکانیزم­‌های از ترکیب recombination: اطلاعات دو فرد با هم ترکیب شده و به فرزندانشان offspring منتقل می­‌شود.
• جهش: تغییرات کوچک و اتفاقی روی افراد اعمال می­‌شود.

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

درخت‌­های تصمیم مبتنی بر الگوریتم‌­های تحولی جایگزین خوبی برای تکنیک­‌های متداول کنونی به شمار می‌­روند؛ زیرا:

• به عنوان تکنیک­‌های جستجو تصادفی Randomized search techniques می‌­توانند از مینیموم (کمینه­) محلی
  Local minima (که راهبرد پارتیشن‌­بندی بالا به پایین حریصانه بازگشتی ایجاد می­‌کنند) دوری کنند؛
• قابلیت درک درختان تصمیم نقطه­ مقابل روش‌­های گردآوری Ensemble methods است؛
• به جای بهینه­‌سازی تنها یک معیار، می‌­توانند چندین هدف گردآوری شده را در مقدار تناسب به کار ببرند.

۲.۱. جمعیت اولیه

در بحث درختان تصمیم تحولی، درخت را به منزله­ فرد (در تحول طبیعی) در نظر می­‌گیریم. اولین جمعیت از درخت‌هایی تشکیل شده که به صورت تصادفی تولید شده‌­اند.

درخت­‌های تصادفی بدین طریق تولید می­‌شوند:

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

• اگر فرزندان تقسیم (یا شاخه‌­شاخه) شوند، الگوریتم به صورت تصادفی ویژگی‌­ها را انتخاب کرده و مقادیر را تقسیم می­‌کند.
• اگر گره، گره­ نهایی (برگ) باشد، یک برچسب رده به صورت تصادفی اختصاص داده می­‌شود.

۲.۲. معیار برازش

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

بدین ترتیب می‌­توان یک تابع برازش Fitness function تعریف کرد که بین این دو معیار (صحت پیش­‌بینی و اندازه درخت) تعادل ایجاد می‌­کند:

Fitness = α۱ f1 + α۲ f2

در این معادله:

• f1 میزان صحت مجموعه­ آموزشی است؛
• f2 اندازه­ فرد را از نظر عمق درخت جریمه می­‌کند؛
• α۱ و α۲ پارامترهایی انتخابی هستند.

۲.۳. انتخاب

برای انتخابِ والدینی که قرار است نسل بعدی را به وجود آورند، چندین راهکار وجود دارد که رایج‌­ترین آن­ها عبارت­ند از:

• انتخاب بر اساس تابع برازش Fitness proportionate selection یا انتخاب بر اساس چرخ رولت Roulette wheel selection: از میزان شایستگی هر فرد در مقایسه با جمعیت استفاده می‌­کنیم تا احتمال انتخاب را مشخص نماییم.
• انتخاب بر اساس تورنمنت Tournament selection: از میان نمونه‌­ای تصادفی از جمعیت، افرادی که بالاترین مقدار تناسب را دارند به عنوان والد انتخاب می­‌کنیم.
• الیتیسم elitism: افرادی که بالاترین مقادیر تناسب را دارند مستقیماً به نسل بعدی منتقل می­‌شوند. این روش اطمینان حاصل می­‌کند که موفق‌­ترین افراد در مدل باقی بمانند.

توجه داشته باشید که یک فرد می‌­تواند چندین بار انتخاب شود و بدین ترتیب قادر باشد ژن خود را به فرزندانش منتقل کند.

۲.۴.  تقاطع

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

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

۲.۵.  جهش

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

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

۲.۶. معیار توقف

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

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

۳-عملکرد درخت‌های تصمیم تحولی در مقایسه با سایر رده‌بندها چگونه است؟

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

۳.۱. یک آزمایش ساده

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

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

دیتاست استفاده شده بزرگ بود و بیش از ۱۰۰ هزار خط داشت. آن­چه باید در مورد دیتاست بدانید:

• اطلاعات حقیقی در مورد مسافران و سفر آن­‌ها را در برمی­‌گرفت: جنسیت و سن مسافر، نوع مسافر (وفادار/همیشگی یا خیر)، نوع سفر (شخصی یا کاری)، رده­ پرواز (بیزینس کلاس، اکو، اکو پلاس) و مسافت پرواز.
• شامل سطح رضایت مسافران از این خدمات می­‌شد: خدمات وای­فای درون پرواز، زمان پرواز از مبدأ و رسیدن به مقصد، آسانی رزرو آنلاین، موقعیت گیت، پذیرایی، بوردینگ آنلاین، راحتی صندلی­‌ها، سرگرمی طول پرواز، خدمات حین پرواز، امکانات مربوط به جای پا جلوی صندلی، بار و بسته­‌بندی، خدمات سوار شدن و تمیزی.

متغیر هدف سطح رضایت مشتریان است که به صورت «راضی» و «ناراضی یا خنثی» مشخص می­‌شود.

روش­‌شناسی

در این قسمت خلاصه‌­ای از گام­‌هایی که طی شد را مشاهده می­‌کنید:

1. پیش­-پردازش Pre-processing  داده­‌ها: تبدیل متغیرهای دسته‌ای Categorial variables به متغیرهای نشانگر Indicator variables. تقسیم داده­‌های دیتاست به زیرمجموعه­‌های آموزشی و آزمایشی.
2. مدل­‌سازی و آزمون: آموزش مدل­‌های مدنظر با استفاده از زیرمجموعه آموزشی و اندازه‌­گیری مدل­‌ها با استفاده از زیرمجموعه­ آزمایشی (اعتباریابی).
3. مقایسه­ عملکرد مدل‌­ها.

رویکرد درخت تصمیم تحولی (EDT) تنها با مدل­‌های درخت-محور Tree-based (درخت تصمیم یا DT و جنگل تصادفی Random forest یا RF) و با محدودیت لایه­‌ای ۳، مقایسه شد. همچنین اندازه­ جمعیت EDT و تعداد برآوردکننده­‌های estimator RF روی ۱۰ تنظیم شدند تا مقایسه‌‌ای پایا از زمان محاسباتی آن­‌ها انجام شود.

یافته‌ها

یافته‌­های این آزمایش را می­‌‎توانید در این نمودار ببینید.

در این شرایط، عملکرد EDT به دو الگوریتم دیگر یادگیری ماشین بسیار نزدیک بود.

با این‌­حال مدل EDT یک مزیت برجسته دارد و آن ارائه یک درخت تصمیم واحد است:

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

در قسمت پایین بهترین درخت تصمیم انتخاب شده از بین جمعیت EDT به نمایش گذاشته شده است، در شرایطی که الگوریتم با حداکثر عمق (لایه­) ۲ آموزش دیده است.

۳.۲.یک اعتباریابی تجربی و عمومی‌تر از رویکرد EDT

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

از آن­جایی که در این آزمایش تنها از یک دیتاست استفاده شده، نمی‌­توان همه­ احتمالات (همچون اثر تعداد رده­‌های متغیر هدف، یا اثر تعداد ویژگی‌­ها و مشاهدات یا موارد دیگر) را در نظر گرفت.

در دومین مقاله‌ای که در قسمت منابع می‌بینید، نویسندگان با استفاده از دیتاست‌­های حقیقی UCI عملکرد یک رویکرد EDT را با روش‌­های دیگر یادگیری ماشین مقایسه کردند.

دیتاست این مقاله

جدول زیر به صورت خلاصه دیتاست را توصیف می­‌کند:

همانطور که می­‌بینید دیتاست­‌ها از نظر تعداد مشاهدات، ویژگی‌­ها و رده‌­های هدف تفاوت چشم‌گیری با هم دارند.

دشوارترین دیتاست اولین مورد است، زیرا تعداد رده‌­های بیشتر و تعداد مشاهدات محدودتری دارد.

روش‌شناسی

در این قسمت با روش­ پژوهشی نویسندگان (به منظور مقایسه­ عملکرد EDT با الگوریتم‌­های کلاسیک یادگیری ماشینی) بیشتر آشنا خواهید شد:

• مدل EDT با این ابرپارامترها Hyperparameter آموزش دیده شده است: تعداد نسل‌­های ۵۰۰، اندازه­ جمعیت ۴۰۰، احتمال تقاطع/ جهش ۶/۰.۴، و روش انتخاب تصادفی با رویکرد الیتیسم.
• عملکرد مدل­‌ها با استفاده از اعتباریابی متقاطع Cross-validation ۵×۲ اندازه­‌گیری شد.

یافته‌ها

همان‌طور که نویسندگان بیان کرده‌­اند از جدول بالا دو نکته­ کلیدی می­‌توان استنباط کرد:

1. در تقریباً تمامی موارد عملکرد الگوریتم­‌های درخت-محور از عملکرد الگوریتم‌­های دیگر یادگیری ماشینی بهتر است. این یافته را می‌­توان این‌طور توجیه کرد که درخت­‌های تصمیم ذاتاً توانایی بیشتری در انتخاب مهم­ترین ویژگی‌­ها دارند. علاوه بر این مدل­‌های قانون-محور Rule-based models با دیتاست‌های خاص تطابق بیشتری دارند، به ویژه زمانی که مدل‌سازی رابطه­ بین هدف و ویژگی کار دشواری است.
2. نتایج به دست آمده در دیتاست abalone ضعیف هستند. زیرا متغیر هدف ۲۸ رده و در عین حال مشاهدات بسیار کمی (تنها ۲۱۰) دارد. با این­‌حال، مدل EDT بالاترین صحت را در این دیتاست به دست آورده است که خود حاکی از توانایی آن در کار با دیتاست‌­های دشوار و پرهیز از بیش‌­تطبیقی است.

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