کاربر:MohammadAliOlama/تجمیع بوت استرپ

از ویکی‌پدیا، دانشنامهٔ آزاد

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

شرح تکنیک[ویرایش]

روش Bagging یک تکنیک بازنمونه‌گیری(Resampling) است که از روی یک مجموعه آموزشی با سایز به تعداد ، دیتاست آموزشی جدید هر کدام با سایز ایجاد کند. این روش به طور یکنواخت و با جایگزینی شروع به نمونه برداری از میکند. با نمونه گیری با جایگزینی، ممکن است برخی از مشاهدات در هر یک از ها، چندین بار تکرار شود . اگر ، به ازای n های بزرگ، انتظار می رود مجموعه حدود از نمونه های منحصر به فرد D را شامل شود.( به طور دقیق‌تر، احتمال اینکه یک نمونه خاص در هیچ کدام از بار نمونه‌برداری برداشته نشود برابر است با و در نتیجه میتوان نتیجه گرفت که دیتاست بوت‌استرپ شده، تقریبا شامل 63 درصد از داده های یکتای دیتاست اصلی است.) [۱] این نوع نمونه به نمونه بوت استرپ معروف است. نمونه برداری با جایگزینی تضمین می کند که هر بوت استرپ مستقل از همتایان خود است، زیرا در هنگام نمونه برداری به نمونه های انتخابی قبلی بستگی ندارد. سپس، m مدل‌ بر روی m نمونه‌ای که در مرحله قبل توضیح داده شد، برازش می‌شوند و آموزش میبینند. و با میانگین‌گیری خروجی (برای رگرسیون) یا رای اکثریت (برای طبقه‌بندی) ترکیب می‌شوند.(منظور از رای اکثریت این است که خروجی مدل های مختلف را نگاه میکنیم. از آنجا که تعداد خروجی های ممکن در مسئله طبقه‌بندی محدود و متناهی است، بنابراین میتوان به ازای هر کلاسی، تعداد مدل هایی که خروجی آنها برابر آن کلاس بوده است را به دست آوریم. سپس کلاسی که اکثریت رای را داشته باشد به عنوان خروجی نهایی کل مدل در نظر میگیریم.)

تصویری برای مفهوم bagging

فرآیند الگوریتم[ویرایش]

سه نوع مجموعه داده در جمع آوری بوت استرپ وجود دارد که مجموعه داده های اصلی، داده‌های بوت استرپ و داده‌های خارج از کیسه(Out-of-bag) هستند. در بخش های زیر، نحوه‌ی ساخت مجموعه بوت‌استرپ و مجموعه خارج از کیسه توضیح داده میشود.

ایجاد مجموعه داده بوت استرپ[ویرایش]

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

Bootstrap Example

فرض کنید مجموعه داده اصلی(گروه سمت چپ) یک گروه متشکل از 12 نفر باشد. نام این افراد امیلی، جسی، جورج، کنستانتین، لکسی، تئودور، جان، جیمز، ریچل، آنتونی، الی و جمال هستند.

با نمونه‌گیری تصادفی از نام‌ها، فرض کنید مجموعه داده‌های بوت استرپ ما(گروه سمت راست) دارای جیمز، الی، کنستانتین، لکسی، جان، کنستانتین، تئودور، کنستانتین، آنتونی، لکسی، کنستانتین و تئودور باشد. در این مورد، نمونه بوت استرپ شامل چهار نمونه تکراری برای کنستانتین ، و دو نمونه تکراری برای لکسی و تئودور است.

ایجاد مجموعه داده خارج از کیسه[ویرایش]

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

Complete Example

اهمیت مجموعه داده خارج از کیسه این است که مدل ما چون این داده ها را از قبل ندیده و درباره آنها اطلاعاتی ندارد، میتوان از آنها استفاده کرد و دقت مدل را روی انها سنجید.

اهمیت[ویرایش]

از آنجا که برای آزمایش دقت الگوریتم "جنگل تصادفی" از مجموعه های بوت‌استرپ و خارج از کیسه استفاده میشود، ایجاد مجموعه داده های بوت استرپ و خارج از کیسه بسیار مهم است.(دلیل این ماجرا این است که ما برای تولید جنگل تصادفی، نیاز به تعدادی درخت داریم. هر درخت نیز نیاز به یک مجموعه داده آموزشی دارد. از انجا که معمولا به مجموعه آموزشی بسیار بزرگ دسترسی نداریم که برای هر مدل، مجموعه داده واقعا مجزا تولید کنیم، بنابراین سعی میکنیم با روش های بازنمونه‌گیری، از مجموعه داده آموزشی موجود مجموعه های داده متنوعی ایجاد کنیم و هر یک را در اختیار یکی از مدل ها قرار دهیم.) معمولا هرچه تعداد مدل های ما نیز بیشتر شود، دقت مدل نهایی ما نیز بیشتر میشود. مثلا، مدلی که 50 درخت را با استفاده از مجموعه داده های بوت استرپ/خارج از کیسه تولید می کند، نسبت به زمانی که 10 درخت تولید می کند، دقت بهتری خواهد داشت.

ایجاد درختان تصمیم(Decision Tree)[ویرایش]

مرحله بعدی الگوریتم، شامل تولید یک مجموعه از درخت‌های تصمیم از مجموعه داده بوت استرپ است. به این منظور، الگوریتم ما هر ویژگی(feature) را بررسی می‌کند و مشخص می‌کند که حضور یا عدم حضور آن ویژگی در درخت ما، برای چند نمونه نتیجه مثبت یا منفی به همراه دارد. سپس از این اطلاعات برای محاسبه یک ماتریس سردرگمی (Confusion Matrix) استفاده می‌شود که در صورت استفاده به‌عنوان طبقه‌بندی‌کننده، مثبت‌های درست(True Positives)، مثبت‌های کاذب(False positives)، منفی‌های درست(True Negatives) و منفی‌های کاذب(False Negatives) را در یک جدول نمایش میدهد. سپس این ویژگی های مختلف، بر اساس معیارهای طبقه بندی مختلف بر اساس ماتریس های سردرگمی آنها رتبه بندی می شوند.(برای اطلاعات بیشتر به این لینک مراجعه کنید.) برخی از معیارهای رایج عبارتند از تخمین "صحت مثبت" (که به صورت اختلاف تعداد مثبت‌های کاذب و مثبت‌های درست محاسبه میشود.) و اطلاعات به دست آمده (Information Gain). سپس از این اطلاعات استفاده میکنیم و نمونه ها را به دو دسته (آنهایی که ویژگی مورد نظر را دارند و آنهایی که ندارند) تقسیم میکنیم و همین فرایند را یک مرحله جلو میبریم.

مثلا شکل زیر یک درخت تصمیم با عمق دو را نشان می دهد که برای طبقه بندی داده ها استفاده می شود.

Decision Tree Depth 2

این فرآیند به صورت بازگشتی آنقدر در سطوح متوالی درخت تکرار میشود تا درخت به عمق مورد نظر ما برسد. در انتهای درخت، نمونه هایی که دارای ویژگی نهایی هستند، به عنوان "دسته‌ی مثبت" طبقه بندی می شوند و نمونه هایی که فاقد آن ویژگی باشند، به عنوان دسته‌ی منفی طبقه بندی می شوند. [۲] سپس از این درخت ها به عنوان پیش بینی کننده برای طبقه بندی داده های جدید استفاده می شود.

جنگل های تصادفی[ویرایش]

در این بخش، به معرفی روش دیگری میپردازیم که مقدار بیشتری تنوع در ساختن درخت ها ایجاد میکند. در این حالت، علاوه بر این که هر درخت از یک مجموعه بوت‌استرپ از داده‌ها استفاده کند، از بین تمام ویژگی های منحصربه‌فرد موجود نیز، فقط تعداد اندک(اما ثابتی) از ویژگی ها را درنظر می‌گیرد و درخت را با توجه به آنها میسازد. در نتیجه این حرکت‌ها، درخت های متنوع‌تر و تصادفی‌تری ساخته میشوند. اگر این فرایند را بارها تکرار کنیم، هر بار یک درخت تصادفی تولید میشود که در نهایت همه آنها در کنار هم، منجر به یک جنگل تصادفی می‌شود که دارای مزایای متعددی نسبت به یک تک درخت تصمیم گیری است (که در آن هیچ فرایند تصادفی‌ای وجود ندارد). در یک جنگل تصادفی، هر درخت، برحسب ویژگی هایی که بر پایه انها ساخته شده، یک نمونه خاص را به عنوان "نمونه‌ مثبت" یا "نمونه منفی" طبقه بندی میکند. در نهایت، آن نمونه بر اساس "رای اکثریت" به عنوان "نمونه‌ مثبت" یا "نمونه منفی" طبقه بندی می شود. مثالی از این روند، در نمودار زیر آورده شده است، جایی که چهار درخت در یک جنگل تصادفی در مورد اینکه آیا بیمار دارای جهش‌های A، B، F و G سرطان دارد یا خیر، رأی می دهند. از آنجایی که سه درخت از چهار درخت رای مثبت می دهند، بیمار به عنوان کسی که سرطان دارد، طبقه بندی می‌شود!

جنگل‌های تصادفی به دلیل خصوصیت‌هایی که دارند، یکی از دقیق‌ترین الگوریتم‌های داده‌کاوی در نظر گرفته می‌شوند، احتمال کمتری برای بیش‌برازش روی داده‌های خود دارند و حتی برای مجموعه‌ داده های بزرگ نیز با سرعت و به صورت کارآمد اجرا می‌شوند. [۳]

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

بهبود جنگل های تصادفی و بوت‌استرپ[ویرایش]

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

  1. حداکثر عمق درختان را مشخص کنید: به جای اینکه اجازه دهید جنگل تصادفی شما تا زمانی که تمام گره ها خالص شوند، ادامه یابد، بهتر است آن را در یک نقطه خاص قطع کنید تا شانس بیش‌برازش را کاهش دهید.
  2. مجموعه داده را هرس کنید: استفاده از یک مجموعه داده بسیار بزرگ ممکن است نتایجی را ایجاد کند که کمتر نشان‌دهنده داده‌های ارائه‌شده باشد(نسبت به مجموعه‌ای کوچک‌تر که دقیق‌تر نشان‌دهنده چیزی است که روی آن تمرکز شده است.).
  3. در مورد دقت یا سرعت تصمیم بگیرید: بسته به نتایج مورد نظر، افزایش یا کاهش تعداد درختان در جنگل می تواند کمک کننده باشد. افزایش تعداد درختان به طور کلی نتایج دقیق تری ارائه می دهد اما سرعت کاهش می‌یابد، در حالی که کاهش تعداد درختان نتایج سریع تر اما با دقت کمتر ارائه می دهد.
مزایا و معایب جنگل های تصادفی و Bagging در مقایسه با درخت تصمیم
مزایا معایب
آماده سازی آسان داده ها.

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

جنگل‌های تصادفی نسبت به یک تک‌درخت‌ تصمیم‌گیری یا سایر الگوریتم‌ها دارای پیچدگی پیاده‌سازی بیشتری هستند. به این دلیل که آنها اقدامات اضافی را برای bagging و همچنین عملیات بازگشتی به منظور تولید یک جنگل کامل انجام می‌دهند که اجرای آن را پیچیده می‌کند. در نتیجه، به قدرت محاسباتی و منابع محاسباتی بسیار بیشتری نیاز دارد.
جنگل‌ها که از درخت‌های تصمیم‌گیری متعدد تشکیل شده‌اند، می‌توانند با دقت بیشتری نسبت به یک تک‌درخت تصمیم‌گیری، پیش‌بینی کنند. برای آموزش داده ها در مقایسه با درخت تصمیم، به زمان بسیار بیشتری نیاز دارد. داشتن یک جنگل بزرگ می تواند به سرعت شروع به کاهش سرعت اجرای برنامه کند، زیرا باید داده های بسیار بیشتری را طی کند، حتی اگر هر درخت از مجموعه کوچکتری از نمونه ها و ویژگی ها استفاده کند.
با داده های غیر خطی به خوبی کار می کند. از آنجایی که اکثر الگوریتم‌های مبتنی بر درخت از تقسیم‌های خطی استفاده می‌کنند، استفاده از مجموعه‌ای از درختان بهتر از استفاده از یک تک درخت روی داده‌هایی که دارای ویژگی‌های غیرخطی هستند (یعنی اکثر توزیع‌های دنیای واقعی) کار می‌کند. خوب کار کردن با داده های غیر خطی یک مزیت بزرگ است زیرا سایر تکنیک های داده کاوی مانند تک درخت های تصمیم گیری نیز این کار را انجام نمی دهند. تک‌درخت تصمیم‌گیری بسیار ساده تر از یک جنگل تصادفی قابل تفسیر است. روی یک درخت می توان با دست (توسط یک انسان) پیشروی کرد که منجر میشود یک درک "قابل توضیح" از آنچه که درخت واقعا انجام میدهد برای تحلیلگر به وجود بیاید(چون مسیر نتیجه گیری برای هر داده را میتواند مشاهده کند.). با افزایش تعداد درختان(مثلا در جنگل تصادفی) این بررسی اگر غیرممکن نباشد، بسیار دشوارتر می‌شود.
خطر بیش‌برازش کمتر است و حتی در مجموعه داده های بزرگ به طور موثر اجرا می شود. [۴] این نتیجه استفاده جنگل تصادفی از bagging در ارتباط با انتخاب ویژگی تصادفی است. فراتر از محدوده داده های آموزشی را پیش بینی نمی کند. این یک عیب است زیرا در حالی که bagging اغلب اوقات مؤثر است،اما همه داده ها در نظر گرفته نمی شوند، بنابراین نمی تواند کل یک مجموعه داده را پیش بینی کند.
جنگل تصادفی با دقت و سرعت بالایی کار می کند. [۵] جنگل های تصادفی به دلیل استفاده از مجموعه داده های کوچکتر بسیار سریعتر از درختان تصمیم هستند. برای ایجاد مجدد نتایج خاص، باید سبد(seed) تصادفی دقیق مورد استفاده برای تولید مجموعه‌های بوت استرپ را ذخیره و بررسی کنید. این کار ممکن است هنگام جمع آوری داده ها برای تحقیق یا در یک کلاس داده کاوی مهم باشد. استفاده از سبدهای تصادفی برای جنگل‌های تصادفی ضروری است.

الگوریتم (طبقه بندی)[ویرایش]

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

برای طبقه بندی، یک مجموعه آموزشی مانند و m نمونه‌ی بوت استرپ ورودی بگیرید. یک طبقه بندی کننده مانند به عنوان خروجی نهایی ایجاد کنید [۶]

  1. مجموعه‌ی آموزشی جدید مانند از روی (با جایگذاری) ایجاد کنید.
  2. طبقه بند از روی مجموعه ساخته میشود.
  3. در نهایت، طبقه بند با استفاده از مجموعه‌ی طبقه بندهای قبلی که ایجاد کرده‌ایم( های مرحله قبلی) روی مجموعه داده‌های اصلی ایجاد می شود. سودوکد زیر این فرایند را نشان می‌دهد :
for i =1 to m{
    D' = bootstrap sample from D(sample with replacement)
    Ci = fit a tree on D'
}
C*(x) = argmax #{i:Ci(x)=y}         (most often predicted label y)
         y∈Y

مثال: داده های ازون[ویرایش]

برای نشان دادن اصول اولیه Bagging، تحلیلی در مورد رابطه بین ازون و دما ارائه شده است (داده‌‌ها از Rousseeuw و Leroy, سال 1986، تجزیه و تحلیل انجام شده در زبان برنامه‌نویسی R ).

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

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

مزایا و معایب[ویرایش]

مزایا:

  • تعداد زیادی از یادگیرندگان ضعیف معمولاً در کل مجموعه عملکرد بهتری از یک یادگیرنده دارند و اضافه برازش کمتری دارند
  • واریانس را در یادگیرنده ضعیف با سوگیری کم با واریانس بالا حذف می کند [۷]
  • می تواند به صورت موازی انجام شود، زیرا هر بوت استرپ جداگانه می تواند قبل از ترکیب به تنهایی پردازش شود [۸]

معایب:

  • برای یادگیرنده ضعیف با تعصب زیاد، کیسه کردن نیز سوگیری بالایی را در مجموع خود حمل می کند [۷]
  • از دست دادن قابلیت تفسیر یک مدل
  • بسته به مجموعه داده می تواند از نظر محاسباتی گران باشد

تاریخچه[ویرایش]

مفهوم Bagging از مفهوم بوت‌استرپ مشتق میشود که توسط بردلی افرون توسعه داده شد. [۹] تجمیع بوت استرپ(Bagging) توسط لئو بریمن پیشنهاد شد که اصطلاح اختصاری "bagging" ( bootstrap aggregating ) را نیز ابداع کرد. بریمن در سال 1994 مفهوم Bagging را برای بهبود طبقه‌بندی با ترکیب طبقه‌بندی مجموعه‌های آموزشی که به‌طور تصادفی تولید می‌شوند، توسعه داد. [۱۰]

همچنین ببینید[ویرایش]

منابع[ویرایش]

  1. Aslam, Javed A.; Popa, Raluca A.; and Rivest, Ronald L. (2007); On Estimating the Size and Confidence of a Statistical Audit, Proceedings of the Electronic Voting Technology Workshop (EVT '07), Boston, MA, August 6, 2007. More generally, when drawing with replacement n′ values out of a set of n (different and equally likely), the expected number of unique draws is .
  2. "Decision tree learning", Wikipedia (به انگلیسی), 2021-11-29, retrieved 2021-11-29
  3. "Random forests - classification description". www.stat.berkeley.edu. Retrieved 2021-12-09.
  4. Team, Towards AI. "Why Choose Random Forest and Not Decision Trees – Towards AI — The World's Leading AI and Technology Publication" (به انگلیسی). Retrieved 2021-11-26.
  5. "Random Forest". Corporate Finance Institute (به انگلیسی). Retrieved 2021-11-26.
  6. Bauer, Eric; Kohavi, Ron (1999). "An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting, and Variants". Machine Learning. 36: 108–109. doi:10.1023/A:1007515423169.
  7. ۷٫۰ ۷٫۱ "What is Bagging (Bootstrap Aggregation)?". CFI. Corporate Finance Institute. Retrieved December 5, 2020.
  8. Zoghni, Raouf (September 5, 2020). "Bagging (Bootstrap Aggregating), Overview". The Startup.
  9. Efron, B. (1979). "Bootstrap methods: Another look at the jackknife". The Annals of Statistics. 7 (1): 1–26. doi:10.1214/aos/1176344552.
  10. Breiman, Leo (September 1994). "Bagging Predictors" (PDF). Technical Report. Department of Statistics, University of California Berkeley. Retrieved 2019-07-28.

خواندن بیشتر[ویرایش]