جنگل تصادفی

درخت تصمیم روش مشهوری برای انواع مختلفی از وظایف یادگیری ماشین به حساب می آید. با این حال در بسیاری موارد دقیق نیستند.[1][3]

در کل، معمولا درخت تصمیمی که بیش از حد عمیق باشد الگوی دقیق نخواهد داشت: دچار بیش برارزش شده , و دارای سوگیری پایین و واریانس بالا میباشد. جنگل تصادفی روشی است برای میانگین گیری با هدف کاهش واریانس با استفاده از درخت های تصمیم عمیقی که از قسمت های مختلف داده آموزشی ایجاد شده باشند. در این روش معمولا افزایش جزیی سوگیری و از دست رفتن کمی از قابلیت تفسیر اتفاق افتاده اما در کل عملکرد مدل را بسیار افزایش خواهد داد.[1][2]

مجموعه داده را با ${\displaystyle D}$ نمایش میدهیم، ${\displaystyle D=(x_{1},y_{1}),(x_{2},y_{2}),\cdots ,(x_{n},y_{n})}$ و ${\displaystyle B}$ درخت تصادفی با ایجاد ${\displaystyle B}$ داده جدید از ${\displaystyle D}$ ایجاد میکنیم. مدل نهایی با میانگین گرفتن یا رأی‌گیری بین درختان کار می‌کند[7]. جزئیات این الگوریتم ذیلاً آمده است:‌

برای ${\displaystyle B}$ تا ${\displaystyle b=1}$:

• ${\displaystyle n}$ نمونه با جایگزینی از داده ${\displaystyle D}$ انتخاب کن و این نمونه‌ها را در مجموعه داده ${\displaystyle D_{b}}$ قرار بده. از آنجا که نمونه‌گیری با جایگزینی صورت می‌گیرد یک نمونه ممکن است چندین بار انتخاب شود.
• یک درخت تصادفی به اسم ${\displaystyle T_{b}}$ با ${\displaystyle D_{b}}$ به روش پایین بساز:
  • هر دفعه برای پیدا کردن بهترین متغیر ابتدا یک تعداد مشخصی از متغیرها را کاملا به صورت تصادفی انتخاب کن (مثلا ${\displaystyle m}$ تا، ${\displaystyle m}$ از قبل به مسئله داده شده‌است، و معمولاً با جذر تعداد متغیرها برابر است) و از میان آن‌ها بهترین متغیر را انتخاب کن.

در مسئله رگرسیون مدل نهائی، میانگین تمامی درخت‌ها است[7] یعنی ${\displaystyle F(x)={\frac {1}{B}}\sum _{b=1}^{B}T_{b}(x)}$. از طرفی دیگر در مسئله دسته‌بندی یا Classification با رأی‌گیری بین درختان به جواب نهائی می‌رسیم[7].

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

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

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

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

این روش تعیین متغیر با اهمیت، شامل برخی اشکالات می‌شود. برای داده‌ای که شامل متغیرهای بخش‌بندی شده با سطوح مختلف از شماره هاست، جنگل تصادفی به این خاصیتشان اهمیت می‌دهد که دارای چندین سطح هستند. متدهایی همانند partial permutations و درختان در حال رشد بی‌طرف، می‌تواند برای حل مشکل به کار گرفته شوند. اگر داده شامل گروه‌هایی از ویژگی‌های مرتبط به هم با شبیه‌سازی برای خروجی باشد، در این حالت گروه‌های کوچک نسبت به گروه‌های بزرگ برتری دارند.

ارتباط بین جنگل تصادفی و الگوریتم کی-نزدیک‌ترین همسایه (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' به پیچیدگی یک ساختار از درخت بستگی دارد، و همچنین به ساختار یک مجموعه آموزش دیده. «لین» و «جو» نشان دادند که شکل همسایگی ای که جنگل تصادفی از آن بهره گرفته‌است مطابق است با اهمیت محلی از هر ویژگی.