جنگل تصادفی

جنگل‌های تصادفی یا جنگل‌های تصمیم تصادفی (به انگلیسی: Random forest) یک روش یادگیری ترکیبی برای دسته‌بندی، رگرسیون می‌باشد، که بر اساس ساختاری متشکل از شمار بسیاری درخت تصمیم، بر روی زمان آموزش و خروجی کلاس‌ها (کلاس‌بندی) یا برای پیش‌بینی‌های هر درخت به شکل مجزا، کار می‌کنند. جنگل‌های تصادفی برای درختان تصمیم که در مجموعهٔ آموزشی دچار بیش برازش می‌شوند، مناسب هستند.
نخستین الگوریتم برای جنگل‌های تصمیم تصادفی را «تین کم هو» با بهره‌گیری از روش زیرفضاهای تصادفی پدیدآورد.

پیشینه

پژوهش‌های «بریمن» روی کار «امیت و گمن» اثر گذاشت، کسانی که پژوهش براساس دسته تصادفی که نود را تقسیم می‌کند (در مبحث بزرگ شدن تک درخت) ارائه کردند
در این روش، پیش از این که هر درخت یا هر گره را جاسازی کنند، جنگلی از درختان بزرگ می‌شود و گزینش از بین گونه‌ای از درختان که برای گزینش تصادفی زیرفضاهایی از داده آموزش دیده‌اند، صورت می‌گیرد.
در پایان ایده بهبود بخشیدن به گره‌های تصادفی (که انتخاب هر گره به شکل تصادفی بوده) به جای بهبودی قطعی توسط «دیتریش» بیان شد
دستاوردهای دربارهٔ جنگل تصادفی نخستین بار به دست «لئو بریمن» مقاله شد.
این مقاله روش‌هایی از چگونگی ساخت جنگل بدون کنترل درخت‌ها با بهره‌گیری از CART را بیان می‌کند که با متد بگینگ و بهبودی نود تصادفی ترکیب شده‌است.
به علاوه، این مقاله بسیاری از نتایج اولیه به دست آمده که شناخته شده بودند و چه آن‌هایی که به چاپ رسیده بودند را ترکیب می‌کرد که این ترکیبات پایه و اساس تمرینات امروزی جنگل‌های تصادفی را شامل می‌شود
این الگوریتم توسط «لئو بریمن و عادل کالچر» توسعه یافت که جنگل تصادفی نیز جزو دستاوردهای ایشان بود
ایده بگینگ برای ساخت مجموعه‌ای از درخت‌های تصمیم و انتخاب تصادفی نخست توسط «هو» و سپس «امیت و گمان» کامل شد. این تمرینات امروزی عبارتند از:
۱. بهره گرفتن از نقص خارج از کیسه برای تعمیم نقص‌های سازماندهی
۲. اهمیت اندازه‌گیری گونه‌ها و تنوع از طریق جایگشت
همچنین این گزارش نخستین فرجام تئوری برای جنگل‌هایی که از راه نقص سازماندهی تعمیم یافته بودند را بیان می‌کند که بستگی به قدرت درخت‌ها و ارتباط آن‌ها دارد.

آغاز: آموزش درخت تصمیم

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

از کیسه‌گذاری تا جنگل تصادفی

روندی که گفته شد الگوریتم اصلی بگینگ برای درختان را توصیف می‌کند. جنگل تصادفی تنها یک اختلاف با این طرح کلی دارد: و آن این که از یک الگوریتم یادگیری درخت اصلاح شده‌استفاده می‌کند که در هر تقسیم کاندیدها در فرایند یادگیری، زیر مجموعه‌ای تصادفی از ویژگی‌های آن را پردازش می‌کنند. این پردازش گاهی «بگینگ ویژگی» نامیده می‌شود.
دلیل انجام این کار این است که ارتباط درخت‌ها در یک نمونه بوت استرپ معمولی را نشان می‌دهد. اگر یک یا چند ویژگی پیش‌بینی‌کننده‌ها، برای متغیر پاسخ (خروجی هدف) بسیار قوی باشد، این ویژگی در بسیاری از درخت‌های B که سبب ارتباط آن‌ها می‌شود، انتخاب خواهد شد.
آنالیز چگونگی کارکرد بگینگ و مجموعه دسته‌های تصادفی، کمک می‌کند تا بتوان به اکیورسی‌های با شرایط گوناگون دست یافت که توسط «هو» نیز ارائه شده بودند.

درختان افزونه

برای آشنایی با بخشی از سازوکار این درخت‌ها باید دانست که، جنگل تصادفی پیش‌بینی‌کننده به صورت طبیعی اندازه‌گیری‌های بدون برچسب را از بین بدون نظارت‌ها رهبری می‌کند.
این درخت می‌تواند همچنین جنگل تصادفی را بین داده‌های بدون برچسب تعریف کند: به این شکل که ساخت جنگل تصادفی پیش‌بینی‌کننده داده‌های مشاهده شده را از داده‌های مصنوعی مناسب متمایز می‌کند. داده‌های مشاهده شده، داده‌های اصلی بدون برچسب هستند و داده‌های مصنوعی از مرجع توزیع‌ها گرفته می‌شود.
یک جنگل تصادفی می‌تواند جالب به نظر برسد زیرا می‌تواند داده‌های ترکیبی را به خوبی مدیرت کند، و از لحاظ مشاهدات قوی است.
جنگل تصادفی می‌تواند ب سادگی به متمایز کردن شمار زیادی از متغیرهای ناپیوسته از متغیر ذاتی بپردازد. برای مثال، Addcl 1 در جنگل تصادفی بدون تشابه وزن‌ها سهم هر متغیر، به چگونگی وابستگی آن به دیگر متغیرها بستگی دارد.
جنگل تصادفی بدون تشابه در بسیاری از اپلیکیشن‌ها به کار رفته‌است مانند پیدا کردن خوشه‌ای از بیماران برپایهٔ داده‌های نشانگر بافت.

اهمیت متغیرها

جنگل تصادفی می‌تواند برای رتبه‌بندی اهمیت متغیرها در یک رگرسیون یا مشکل کلاس بندی در روش طبیعی آن، به کار رود.
تکنیکی که در ادامه آمده‌است در مقاله اصلی «بریمن» آورده شده بود و در پکیج کردن R جنگل تصادفی اجرا می‌شود.
نخستین گام در اهمیت اندازه‌گیری متغیرها در مجموعه داده‌ها، Dn={(xi,yi)} جای دادن جنگل تصادفی در داده هاست.
در هنگام انجام این فرایند جایگذاری نقص بیرون از کیسه
برای هر داده ضبط می‌شود و به عنوان میانگینی از میان جنگل محسوب می‌گردد.
برای اندازه‌گیری اهمیت j امین ویژگی بعد از آموزش، مقدار jامین ویژگی permuted از میان داده‌های آموزش دیده و نقص خارج از کیسه دوباره روی این مجموعه داده محاسبه خواهد شد.
اهمیت نمره برای j امین ویژگی از روش میانگین‌گیری از تفاوت‌ها در خارج از کیسه قبل و بعد از permutation روی تمام درخت‌ها به دست می‌آید.
این نمره با استانداردسازی انحرافات متفاوت، نرمال‌سازی می‌شود.
ویژگی‌هایی ک مقادیر بسیاری براب این نمره تولید می‌کنند بسیار با اهمیت تر هستند نسبت ب ان ویژگی‌هایی ک مقدار کوچکی تولید می‌کنند.
این روش تعیین متغیر با اهمیت، شامل برخی اشکالات می‌شود.
برای داده‌ای ک شامل متغیرهای بخش‌بندی شده با سطوح مختلف از شماره هاست، جنگل تصادفی ب این خاصیتشان اهمیت می‌دهد ک دارای چندین سطح هستند. متدهایی همانند partial permutations و درختان در حال رشد بی‌طرف، می‌تواند برای حل مشکل به کار گرفته شوند. اگر داده شامل گروه‌هایی از ویژگی‌های مرتبط ب هم با شبیه‌سازی برای خروجی باشد، در این حالت گروه‌های کوچک نسبت ب گروه‌های بزرگ برتری دارند.

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

ارتباط بین جنگل تصادفی و الگوریتم kنزدیک‌ترین همسایه (K-NN) در سال ۲۰۰۲ توسط «لین» و «جو» استخراج شد.
ب نظر می‌رسد ک هردوی آن‌ها می‌توانند به عنوان طرح پروزن‌ترین همسایه نام‌گذاری شوند.
این‌ها مدلهایی برای ساخت داده‌های آموزش دیده {(xi,yi)} هستند ک پیش‌بینی‌های تازه y را برای x' با نگاه ب همسایگی از نقاط، از طریق تابع وزن ب صورت زیر در می‌آورد:
y=Π w(xi,x') yi
در اینجا W(xi,x') وزن غیر منفی از i امین نقطه آموزش دیدهٔ همسایه با نقطه تازه x' است.
برای هر 'x ویژه، ورن باید جمعی با یک باشد. تابع‌های وزن در زیر آورده شده‌اند:
۱. در k-NN وزن‌ها
W(xi,x') = 1/K
هستند، اگر xi یکی از نقاطk ک نزدیکترین ب x' است، در نظر گرفته شود، و درغیر این صورت صفر باشد.
۲. در درخت w(xi,x')=1/k' اگر xi یکی از نقاط k' در برگ یکسان از x' باشد، و در غیر این صورت صفر باشد.
به سبب این ک میانگین جنگل مجموعه‌ای از درخت‌های m را با تابع وزن فردی wj پیش‌بینی می‌کند، پیش‌بینی‌هایش به صورت زیر در می‌آید:
y= 1/m ΠΠ wj(xi,x')yi=Π(1/mΠ wj(xi,x'))yi
این نشان می‌دهد ک کل جنگل یک طرح از دوباره وزن‌گیری همسایه هاست، با وزن‌هایی ک میانگین هر درخت مجزا هستند.
همسایه‌های x' در این تفسیر ویژگی، نقاط xiهایی هستند ک در یک برگ یکسان از x'ها در دست کم یک درخت از جنگل قرار دارند.
در این روش، همسایگی x' به پیچیدگی یک ساختار از درخت بستگی دارد، و همچنین به ساختار یک مجموعه آموزش دیده.
«لین» و «جو» نشان دادند ک شکل همسایگی ای ک جنگل تصادفی از ان بهره گرفته‌است مطابق است با اهمیت محلی از هر ویژگی.

یادگیری بدون آموزگار با جنگل تصادفی

به عنوان بخشی از سازوکار ان‌ها، جنگل تصادفی پیش‌بینی‌کننده ب صورت طبیعی اندازه‌گیری‌های بدون برچسب را میان بدون نظارت‌ها رهبری می‌کند. می‌تواند همچنین جنگل تصادفی را بین داده‌های بدون برچسب تعریف کند: ایده این است ک ساخت جنگل تصادفی پیش‌بینی‌کننده داده‌های مشاهده شده را از داده‌های مصنوعی مناسب متمایز می‌کند. داده‌های مشاهده شده، داده‌های اصلی بدون برچسب هستند و داده‌های مصنوعی از مرجع توزیع‌ها گرفته می‌شود. یک جنگل تصادفی می‌تواند جالب ب نظر برسد زیرا می‌تواند داده‌های ترکیبی را ب خوبی مدیرت کند، و از لحاظ مشاهدات قوی است. جنگل تصادفی می‌تواند ب سادگی ب متمایز کردن شمار زیادی از متغیرهای ناپیوسته از متغیر ذاتی بپردازد. برای مثال، Addcl 1 جنگل تصادفی بدون تشابه وزن‌ها سهم هر متغیر وابسته ب چگونگی وابستگی ان ب دیگر متغیرها بستگی دارد. جنگل تصادفی بدون تشابه در بسیاری از اپلیکیشن‌ها بکار رفته‌است مانندپیدا کردن خوشه‌ای از بیماران برپایهٔ داده‌های نشانگر بافت.

انواع

در میان ابزارهای پشتیبانی تصمیم، درخت تصمیم و دیاگرام تصمیم دارای مزایایی هستند:
۱- فهم ساده:
هر انسان با اندکی مطالعه و آموزش می‌تواند، طریقه کار با درخت تصمیم را بیاموزد.
۲- کار کردن با داده‌های بزرگ و پیچیده:
درخت تصمیم در عین سادگی می‌تواند با داده‌های پیچیده به راحتی کار کند و از روی آن‌ها تصمیم بسازد.
۳-استفاده مجدد آسان:
در صورتی که درخت تصمیم برای یک مسئله ساخته شد، نمونه‌های مختلف از آن مسئله را می‌توان با آن درخت تصمیم محاسبه کرد.
۴- قابلیت ترکیب با روش‌های دیگر:
نتیجه درخت تصمیم را می‌توان با تکنیک‌های تصمیم‌سازی دیگر ترکیب کرده و نتایج بهتری بدست آورد.

مثال ۱

درخت تصمیم در بهینه‌سازی مشارکت اوراق بهادار مورد استفاده قرار گیرد. مثال زیر اوراق بهدار ۷ طرح مختلف را نشان می‌دهد. شرکت ۱۰۰۰۰۰۰۰۰ برای کل سرمایه‌گذاری‌ها دارد. خطوط پر رنگ نشان دهنده بهترین انتخاب است که موارد ۱، ۳، ۵، ۶ و۷ را در بر می‌گیرد و هزینه‌ای برابر ۹۷۵۰۰۰۰ دارد و سودی برابر ۱۶۱۷۵۰۰۰ برای شرکت فراهم می‌کند. مابقی حالات یا سود کمتری دارد یا هزینه بیشتری می‌طلبد.

مثال ۲

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