جنگل تصادفی — پیش‌بینی قهرمان جام جهانی ۲۰۱۸ با استفاده از الگوریتم‌های یادگیری ماشین

داده‌کاوی به اکتشاف الگو و روندهای منظم و پنهان در میان داده‌های بزرگ و توزیع یافته گفته می‌شود. این فرایند اکتشافی با استفاده از الگوریتم‌های مختلف ریاضی صورت می‌پذیرد. از جمله آن‌ها، الگوریتم جنگل تصادفی است که یک الگوریتم یادگیری ماشین بسیار قدرتمند محسوب می‌شود. در واقع ارتباط عمیقی بین یادگیری ماشین و داده‌کاوی وجود دارد. در این نوشته ابتدا معرفی کوتاهی از این الگوریتم خواهیم داشت و بلوک‌های سازنده و شیوه عمل آن را توضیح می‌دهیم. سپس به معرفی پژوهشی خواهیم پرداخت که «آندریاس گرول» (Andreas Groll) و همکارانش در آن با استفاده از همین الگوریتم به پیش‌بینی قهرمان جام جهانی 2018 روسیه پرداخته‌اند. این محققان در مقاله خود به معرفی و مقایسه روش‌های جنگل تصادفی، رگرسیون و نیز رتبه‌بندی پرداخته و در نهایت با بررسی تکنیک‌های گوناگون دریافته‌اند که بهترین روش، استفاده از الگوریتم جنگل تصادفی به همراه نسخه خاصی از روش رتبه‌بندی برای تخمین توانایی‌های تیم‌ها است.

جنگل تصادفی

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

فیلم آموزش درخت تصمیم در یادگیری ماشین (رایگان) در فرادرس

کلیک کنید

شاید عبارت «درخت تصمیم» برایتان غریب باشد، ولی ما همگی به طور روزمره از آن استفاده می‌کنیم. برای مثال فرض کنید می‌خواهیم حدس بزنیم که دمای هوای امروز چند درجه خواهد بود؟ تصور کنید بازه‌ای بین 10- تا 40+ درجه را در نظر داریم. به این منظور ابتدا باید بدانیم که در چه موقع از سال قرار داریم. اگر اینک فصل تابستان باشد، بازه مذکور به صورت 20 تا 40 درجه سانتی‌گراد در می‌آید. همچنین شاید لازم باشد ابتدا بدانیم که بیشینه دمای امروز چقدر خواهد بود تا در مرحله بعد بتوانیم حدس بزنیم در این ساعت معین از روز، چه محدوده دمایی برای هوا می‌توانیم پیش‌بینی نماییم. مثلاً اگر اینک ساعت 8 صبح باشد، احتمالاً بازه دمای پیش‌بینی شده به صورت 20+ تا 25+ خواهد بود. به طوری که می‌بینید در طی یک فرایند مرحله‌ای با طرح سؤال‌های مختلف، بازه پیش‌بینی خود را اصلاح کرده و دقت آن را افزایش دادیم. همه این مراحل «درخت تصمیم» نامیده می‌شوند.

جنگل تصادفی چگونه عمل می‌کند؟

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

پیش‌بینی جام جهانی با استفاده از جنگل تصادفی

در این بخش به مرور پژوهشی که قهرمان و نتایج بازی‌های جام جهانی را پیش بینی کرده، می‌پردازیم. ابتدا داده‌های مورد استفاده معرفی شده‌اند. سپس روش‌های مختلف معرفی و دقت آنها مقایسه شده است. در نهایت نتیجه شبیه‌سازی و جمع‌بندی ارائه می‌شود.

داده‌ها

آندریاس گرول و همکارانش در مقاله پژوهشی خود برای پیش‌بینی قهرمان مسابقات جام جهانی 2018 اقدام به گردآوری داده‌های مختلفی نموده‌اند. این داده‌ها شامل اطلاعاتی در مورد عملکرد اخیر تیم‌ها و عوامل دیگر بوده که در ادامه مورد اشاره قرار گرفته‌اند:

• عوامل اقتصادی
  • سرانه تولید ناخالص داخلی
  • جمعیت
• عوامل ورزشی
  • احتمال ODDSET (این احتمال از تبدیل آمار ارائه شده از سوی سازمان شرط‌بندی دولت آلمان به احتمال برد تیم‌ها به دست آمده است)
  • رتبه‌بندی در فهرست فیفا
• مزیت میزبانی
  • میزبانی
  • قاره مربوطه
  • عضویت در کنفدراسیون میزبان (کشورهایی که در کنفدراسیون فوتبال میزبان عضو هستند)
• عوامل مرتبط با ساختار تیم
  • بیشینه و بیشینه ثانویه تعداد بازیکن‌های هم‌تیمی در تیم باشگاهی
  • میانگین سنی
  • تعداد بازیکنانی که در لیگ اروپا بازی می‌کنند
  • تعداد لژیونرها
• عوامل مرتبط با مربی تیم
  • در مورد مربیان تیم‌ها سن ایشان و مدتی که تیم را در اختیار داشته‌اند به عنوان متغیرهای تأثیر گذار انتخاب شده‌اند. در صورتی که ملیت مربی و تیم یکی بود، آن نیز به عنوان یک «متغیر ظاهری» (Dummy Variable) تعریف شده است.

در مجموع 16 متغیر به دست آمده که داده‌هایشان برای هر یک از تیم‌ها گردآوری شده است.

روش پیش‌بینی

جنگل تصادفی

در تحقیق گرول و همکاران، از درخت‌های تصمیم و همچنین جنگل تصادفی برای پیش‌بینی نتایج هر یک از بازی‌های جام جهانی استفاده شده. به این منظور متغیرهای پیش‌بین که در بخش قبلی اشاره کردیم محاسبه شده و با استفاده از تابع ctree در بسته party زبان R درخت رگرسیون شکل گرفته است.

فیلم آموزش پیش بینی با الگوریتم های یادگیری ماشین در پایتون – پیش بینی نارسایی قلبی در فرادرس

کلیک کنید

در تصویر زیر درخت رگرسیون داده‌های نمونه جام‌های جهانی 2002 تا 2014 ارائه شده. تعداد گل‌ها به عنوان متغیر پاسخ و متغیرهای تعریف شده در بخش داده‌ها به عنوان پیش‌بین استفاده شده‌اند.

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

شاید از خود بپرسید که نقش هر یک از متغیرهای پیش‌بین در مدل کلی الگوریتم به چه صورت بوده است؟ باید در پاسخ گفت که برخلاف درختان رگرسیون، نمایش دیداری جنگل تصادفی کار دشواری است. هر پیش‌بین ممکن است تأثیر متفاوتی داشته باشد و یا کلاً هیچ تأثیری نداشته باشد. برای مشاهده تأثیر هر متغیر از مفهومی به نام «اهمیت پیش‌بین» (variable importance) استفاده می‌کنیم. اهمیت پیش‌بین یک متغیر، به طور معمول به وسیله پیمایش جداگانه هر یک از پیش‌بین‌ها در مشاهدات خارج از کیسه (out of bag) هر درخت تعیین می‌شود.

در نمودار زیر میزان اهمیت هر یک از متغیرهای پیش‌بین که با روش فوق به دست آمده است را مشاهده می‌کنید. این داده‌ها مربوط به جام‌های جهانی 2002 تا 2014 هستند.

در زبان R دو نسخه تا حدودی متفاوت از جنگل‌های رگرسیون وجود دارند. نسخه اول، الگوریتم جنگل تصادفی کلاسیک است که در بسته ranger ارائه شده. نسخه دوم، در تابع cforest از بسته party پیاده‌سازی شده است. در این نسخه درختان منفرد استفاده شده‌اند که پیشنهاد آن به صورت مفهوم تداخل شرطی درخت‌ها از سوی هوثورن (Hothorn) و همکاران (2006) بوده است. مزیت اصلی این تداخل شرطی درخت‌ها، آن است که از سوگیری انتخابی در مواردی که متغیرهای کمکی مقیاس‌های متفاوتی دارند، اجتناب می‌کند. در تحقیق‌های قبلی مشخص شده که قدرت پیش‌بینی cforest از بسته party بالا‌تر بوده است. به همین دلیل در این مقاله نیز از همین روش بهره گرفته شده.

رگرسیون

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

برای مدل‌سازی رگرسیون این تورنمنت از رابطه زیر استفاده شده:

که در آن Y_ijk نشان دهنده امتیاز تیم i در برابر تیم j در تورنمنت k است. خصوصیات متریک هر دو تیم رقیب در بردارهای p-بُعدی x_ik و x_jk لحاظ شده که در آن z_ik و z_jk متغیرهای ظاهری برای متغیرهای کمکی دسته‌ای میزبانی، قاره، کنفدراسیون و ملیت مربی هستند. برای این متغیرها معنی ندارد که بین مقادیر متناظر، اختلافی ایجاد شود. به علاوه بتا بردار پارامتر است که تأثیرات خطی همه اختلاف‌های متغیرهای کمکی متریک را اندازه‌گیری می‌کند و گاما و دلتا به ترتیب تأثیرات متغیرهای ظاهری متناظر با تیم‌ها و رقبایشان را اندازه‌گیری می‌کنند. در تحقیقات قبلی مشخص شده که این ساختار پیش‌بین، بهترین عملکرد رگرسیونی را داشته است. اگرچه عملکرد آن نسبت به جنگل تصادفی معرفی شده در بخش قبل تا حدی پایین‌تر بوده.

روش‌های رتبه‌بندی

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

مدل رتبه‌بندی پواسونی مستقل شباهت زیادی به مدل رگرسیون پواسونی دارد که قبلاً توضیح دادیم. اگر M مسابقه داشته باشیم که n تیم با هم برگزار کرده باشند، در این صورت:

که Y_ijm نشان دهنده تعداد گل‌های ثبت شده از سوی تیم i در برابر تیم j در مسابقه m است. λ_ijm تعداد گل‌های مورد انتظار برای تیم i در این مسابقه و r_i و r_j شاخص قدرت تیم i و j هستند.

گرول و همکارانش در محاسبات خود تمام مسابقات 8 سال گذشته تیم‌ها را گردآوری کرده‌اند. بهترین مدل و بهترین پارامتر نیمه‌عمر بر پایه عملکرد پیش‌بینی مدل‌ها روی داده‌های بین‌المللی از سال 2002 تا 2017 انتخاب شده است. همان‌طور که در جدول زیر مشاهده می‌شود، مدل پواسون دو متغیره با نیمه‌عمر 3 ساله به عنوان بهترین مدل رتبه‌بندی بر اساس امتیاز احتمالاتی رتبه میانگین انتخاب شده. در این جدول عملکرد پیش‌بینی مدل‌های پواسونی دو متغیره با مقادیر نیمه‌عمر حدود 1، 2، 3، 4 و 5 سال مقایسه شده‌اند. بهترین مدل کمترین امتیاز احتمالاتی رتبه (RPS) را دارد. RPS نشان دهنده ساختار ترتیبی پاسخ‌ها است و از آنجا که معیار خطا محسوب می‌شود، هر چه پایین تر باشد، مدل تطابق بهتری دارد.

ترکیب روش‌ها

در این بخش به مقایسه سه رویکرد متفاوت پرداخته شده که در بخش‌های قبلی معرفی شدند. به این منظور از رویه عمومی زیر بر روی داده‌های سال‌های 2002 تا 2014 استفاده شده است.

1. مجموعه داده‌های تمرینی شامل سه دوره از چهار دوره جام جهانی (سال‌های 2002 تا 2014) هستند.
2. هر یک از روش‌ها بر روی داده‌های تمرینی به کار گرفته شده.
3. ترک کردن جام جهانی بر اساس هر یک از روش‌های پیش‌بینی اندازه‌گیری شد.
4. مراحل 1 تا 3 فوق طوری تکرار شدند که در هر دوره جام جهانی، تیم یک بار آن را ترک کند.
5. پیش‌بینی‌ها با نتایج واقعی بر روی همه روش‌های پیش‌بینی مقایسه شدند.

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

در جدول زیر می‌توانید مقایسه روش‌های پیش‌بینی، تعداد دقیق گل‌ها و تفاضل گل را بر مبنای خطای میانگین مربعات ببینید:

بنابراین مشخص شده که بهترین مدل برای پیش‌بینی قهرمان جام جهانی ترکیب الگوریتم جنگل تصادفی با تخمین توانایی‌های کافی تیم است که از روش رتبه‌بندی به دست می‌آید. این توانایی‌ها بر اساس مدل پواسون دو متغیره با نیمه‌عمر 3 سال اندازه‌گیری شده‌اند. همه بازی‌های ملی که تیم‌ها از 2006/06/13 تا 2018/06/06 انجام داده بودند که بالغ بر 700 بازی بود، برای تخمین مورد استفاده قرار گرفته‌اند.

نتیجه پیش‌بینی

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

بدین ترتیب کل این تورنمنت شبیه‌سازی و این کار 100،000 بار تکرار شده است. بر اساس شبیه‌سازی‌ها برای هر یک از 32 تیم شرکت کننده، احتمال رسیدن به مرحله حذفی و در نهایت بردن جام قهرمانی به دست آمده است. این نتایج در جدول زیر جمع‌بندی شده‌اند.

مشاهده می‌کنیم که بر اساس الگوریتم جنگل تصادفی، اسپانیا بیشترین شانس برد جام را با 17.8 درصد دارد. پس از آن آلمان، برزیل، فرانسه و بلژیک قرار دارند.

در جدول فوق می‌بینیم که هیچ تیمی غالب نیست؛ ولی چند تیم هستند که شانس خوبی دارند. علاوه بر احتمال کلی قهرمانی جام جهانی، در جدول زیر محاسبات جالب دیگری برای مراحل منفرد درون تورنمنت ارائه شده است. برای مثال می‌بینیم که تیم‌های اسپانیا و آلمان تقریباً شانس برابری برای رسیدن به مرحله یک هشتم نهایی دارند. با این‌که اسپانیا دست‌کم به احتمال 73.1 درصد به یک‌چهارم نهایی می‌رسد؛ اما آلمان تنها 58.0 درصد این احتمال را دارد. بدیهی است که آلمان برخلاف اسپانیا به احتمال بیشتر در مرحله یک هشتم با رقیب قدرتمندتری مواجه خواهد شد. در حالتی که این دو تیم به مرحله یک هشتم برسند، آلمان احتمالاً با یکی از تیم‌های برزیل، سوئیس، صربستان یا کاستاریکا مواجه خواهد شد؛ در حالی که اسپانیا با یکی از تیم‌های اروگوئه، روسیه، عربستان سعودی یا مصر مواجه می‌شود. در مراحل بعدی شانس قهرمانی آلمان به‌تدریج با اسپانیا برابر می‌شود.

محتمل‌ترین حالت برای تورنمنت جام جهانی

در نهایت بر اساس 100،000 شبیه‌سازی، محتمل‌ترین حالت نیز محاسبه شده است. در محاسبات گرول و همکاران از میان هشت گروه، حالتی که در نهایت بیشترین احتمال دارد ارائه شده که می‌توانید در جدول زیر مشاهده کنید. بدیهی است که اختلاف‌هایی در احتمال‌های پیش‌بینی شده وجود دارد. با این‌که در مورد گروه B و گروه G احتمال پیش‌بینی‌ها به ترتیب 38.5 و 38.1 درصد است، اما این پیش‌بینی‌ها در مورد گروه‌های دیگر احتمال پایین‌تری را نشان می‌دهند.

همچنین محتمل‌ترین حالت برای مرحله حذفی در شکل زیر ارائه شده است. حالتی که بیشترین احتمال را برای مرحله یک هشتم نهایی دارد به طور مستقیم از تیم‌های حائز شرایط صعود از مرحله مقدماتی به دست آمده. برای بازی‌های بعدی احتمالات مربوط به دو تیم رقیب برای صعود به مرحله بعدی بررسی شده‌اند.

بر اساس محتمل‌ترین سناریو برای این تورنمنت آلمان باید به جای اسپانیا قهرمان جام جهانی باشد. با این حال در این مورد نیز بدیهی است که با وجود تیم سوئیس، آلمان باید در مرحله یک هشتم با تیم قوی‌تری نسبت به اسپانیا مواجه شود. با این‌که آلمان‌ها در این مورد شانس برد بیشتری دارند؛ ولی احتمال صعود آن‌ها به یک‌چهارم نهایی همچنان در حد 61 درصد است. با این‌که بر اساس سناریوی دارای بیشترین احتمال برای مرحله حذفی، آلمان‌ها در همه مراحل با بازی‌های سختی مواجه خواهند بود؛ اما بر اساس پیش‌بینی‌، آن‌ها به بازی فینال رسیده و از عنوان قهرمانی خود دفاع می‌کنند. در هر صورت در مرحله قبلی مشخص شد که شانس قهرمانی اسپانیا بیشتر از آلمان است.

نتیجه‌گیری

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

اگر به این نوشته علاقه‌مند بودید، موارد زیر نیز احتمالاً مورد توجه شما قرار می‌گیرد:

• گنجینه آموزش های یادگیری ماشین و داده کاوی
• مهم‌ترین الگوریتم‌های یادگیری ماشین (به همراه کدهای پایتون و R)
• پیش‌بینی نتایج فوتبال با استفاده از اکسل
• آموزش یادگیری ماشین با مثال‌های کاربردی
• آموزش یادگیری ماشین (Machine Learning) با پایتون (Python)

==