کاربر:MohammadAliOlama/تجمیع بوت استرپ: تفاوت میان نسخهها
اولین تغییر |
دومین تغییر برچسبها: افزودن فضای خالی زیاد ویرایشگر دیداری |
||
خط ۱: | خط ۱: | ||
'''تجمیع بوتاسترپ (Bootstrap Aggregating)''' که به آن '''bagging''' نیز میگویند یک روش در یادگیری ماشینی است که برای بهبود پایداری و دقت الگوریتمهای [[یادگیری ماشینی]] مورد استفاده در [[طبقهبندی آماری]] و [[تحلیل رگرسیون|رگرسیون]] طراحی شده است. این روش همچنین به کاهش [[واریانس]] کمک میکند و به جلوگیری از [[بیشبرازش]] کمک می کند. اگرچه این روش معمولاً برای روش های [[یادگیری درخت تصمیم|درخت تصمیم]] استفاده می شود، اما می توان آن را با هر نوع روشی استفاده کرد. Bagging را میتوان یک شکل خاص از [[یادگیری جمعی|روش میانگین گیری مدل]] دانست. |
'''تجمیع بوتاسترپ (Bootstrap Aggregating)''' که به آن '''bagging''' نیز میگویند یک روش در یادگیری ماشینی است که برای بهبود پایداری و دقت الگوریتمهای [[یادگیری ماشینی]] مورد استفاده در [[طبقهبندی آماری]] و [[تحلیل رگرسیون|رگرسیون]] طراحی شده است. این روش همچنین به کاهش [[واریانس]] کمک میکند و به جلوگیری از [[بیشبرازش]] کمک می کند. اگرچه این روش معمولاً برای روش های [[یادگیری درخت تصمیم|درخت تصمیم]] استفاده می شود، اما می توان آن را با هر نوع روشی استفاده کرد. Bagging را میتوان یک شکل خاص از [[یادگیری جمعی|روش میانگین گیری مدل]] دانست. |
||
شرح تکنیک |
|||
روش Bagging که یک تکنیک بازنمونهگیری(Resampling) است که از روی یک مجموعه آموزشی با سایز <math>D</math> به تعداد n دیتاست آموزشی جدید <math>D_i</math> هر کدام با سایز <math>n'</math> ایجاد کند. این روش به [[توزیع احتمال|طور یکنواخت]] و [[نمونهگیری آماری|با جایگزینی]] شروع به نمونه برداری از<math>D</math> میکند. با نمونه برداری با جایگزینی، ممکن است برخی از مشاهدات در هر یک از <math>D_i</math>ها، چندین بار تکرار شود . اگر <math>n' = n</math> ، به ازای ''n های'' بزرگ، انتظار می رود مجموعه <math>D_i</math> حدود <math>(1 - \frac{1}{e}) \thickapprox 0.63</math> از نمونه های منحصر به فرد ''D'' را شامل شود. <ref>Aslam, Javed A.; Popa, Raluca A.; and Rivest, Ronald L. (2007); [http://people.csail.mit.edu/rivest/pubs/APR07.pdf ''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 <math>n(1 - e^{-n'/n})</math>.</ref> این نوع نمونه به نمونه [[بوتاسترپینگ (آمار)|بوت استرپ]] معروف است. نمونه برداری با جایگزینی تضمین می کند که هر بوت استرپ مستقل از همتایان خود است، زیرا در هنگام نمونه برداری به نمونه های انتخابی قبلی بستگی ندارد. سپس، ''m'' مدل بر روی ''m'' نمونهای که در مرحله قبل توضیح داده شد، برازش میشوند و آموزش میبینند. و با میانگینگیری خروجی (برای رگرسیون) یا رای اکثریت (برای طبقهبندی) ترکیب میشوند. |
|||
Bagging منجر به "بهبود رویه های ناپایدار" می شود، <ref name=":0">{{Cite journal|last=Breiman|first=Leo|author-link=Leo Breiman|year=1996|title=Bagging predictors|journal=[[Machine Learning (journal)|Machine Learning]]|volume=24|issue=2|pages=123–140|citeseerx=10.1.1.32.9399|doi=10.1007/BF00058655}}</ref> که به عنوان مثال،شامل [[شبکه عصبی مصنوعی|شبکه های عصبی مصنوعی]] ، [[یادگیری درخت تصمیم|درختان طبقه بندی و رگرسیون]] ، و انتخاب زیر مجموعه در [[رگرسیون خطی]] می شود.<ref name=":1">{{Cite journal|last=Breiman|first=Leo|date=September 1994|title=Bagging Predictors|url=https://www.stat.berkeley.edu/~breiman/bagging.pdf|journal=Technical Report|publisher=Department of Statistics, University of California Berkeley|access-date=2019-07-28}}</ref> از طرف دیگر، این روش میتواند عملکرد روشهای پایدار مانند K-نزدیکترین همسایهها(K-Nearest Neighbors) را به میزان کمی کاهش دهد. |
|||
فرآیند الگوریتم |
|||
شرایط کلیدی |
|||
سه نوع مجموعه داده در جمع آوری بوت استرپ وجود دارد. اینها '''مجموعه داده های اصلی، دادههای بوت استرپ و دادههای خارج از کیسه(Out-of-bag) هستند.''' در بخش های زیر، نحوهی ساخت مجموعه بوتاسترپ و مجموعه خارج از کیسه توضیح داده میشود. |
|||
ایجاد مجموعه داده بوت استرپ |
|||
مجموعه داده بوت استرپ با انتخاب تصادفی اشیا از مجموعه داده اصلی ساخته می شود. همچنین،انداره این مجموعه، '''باید به اندازه مجموعه داده اصلی باشد.''' با این حال، مجموعه داده بوتاسترپ می تواند دارای اشیاء تکراری نیز باشد. در شکل زیر، مثال ساده ای از عملکرد بوتاسترپ نشان داده شده است : |
|||
فرض کنید '''مجموعه داده اصلی(گروه سمت چپ)''' یک '''گروه متشکل از 12 نفر باشد.''' این افراد '''امیلی، جسی، جورج، کنستانتین، لکسی، تئودور، جان، جیمز، ریچل، آنتونی، الی و جمال هستند.''' |
|||
با نمونهگیری تصادفی از نامها، فرض کنید '''مجموعه دادههای بوت استرپ ما(گروه سمت راست)''' دارای '''جیمز، الی، کنستانتین، لکسی، جان، کنستانتین، تئودور، کنستانتین، آنتونی، لکسی، کنستانتین و تئودور''' باشد. در این مورد، نمونه بوت استرپ شامل چهار نمونه تکراری برای '''کنستانتین''' ، و دو نمونه تکراری برای '''لکسی''' و '''تئودور''' است. |
|||
ایجاد مجموعه داده خارج از کیسه |
|||
مجموعه داده خارج از کیسه '''نشان دهنده افرادی از مجموعه داده اصلی هستند که در مجموعه داده بوت استرپ قرار نگرفتهاند.''' در این مورد، نمونه های باقی مانده مجموعه داده اصلی که در روند بوتاسترپ انتخاب نشدند عبارتند از '''امیلی، جسی، جورج، ریچل و جمال.''' |
|||
اهمیت |
|||
از آنجا که برای آزمایش دقت الگوریتم "جنگل تصادفی" از مجموعه های بوتاسترپ و خارج از کیسه استفاده میشود، ایجاد مجموعه داده های بوت استرپ و خارج از کیسه بسیار مهم است.(دلیل این ماجرا این است که ما معمولا به مجموعه آموزشی بسیار بزرگ دسترسی نداریم که برای هر مدل، مجموعه داده واقعا مجزا تولید کنیم، بنابراین سعی میکنیم از مجموعه داده آموزشی موجود، مجموعه های متنوعی ایجاد کنیم.) به عنوان مثال، مدلی که 50 درخت را با استفاده از مجموعه داده های بوت استرپ/خارج از کیسه تولید می کند، نسبت به زمانی که 10 درخت تولید می کند، دقت بهتری خواهد داشت. از آنجایی که الگوریتم، چندین درخت و بنابراین مجموعه داده های متعدد تولید می کند، احتمال اینکه یک شی از مجموعه داده های بوت استرپ خارج شود کم است. چند بخش بعدی در مورد نحوه عملکرد الگوریتم جنگل تصادفی با جزئیات بیشتر صحبت می کند. |
|||
ایجاد درختان تصمیم(Decision Tree) |
|||
مرحله بعدی الگوریتم، شامل تولید یک مجموعه از [[درخت تصمیم|درختهای تصمیم]] از مجموعه داده بوت استرپ است. به ایت منظور، الگوریتم ما هر ویژگی را بررسی میکند و مشخص میکند که حضور یا عدم حضور آن ویژگی، برای چند نمونه نتیجه مثبت یا منفی به همراه دارد. سپس از این اطلاعات برای محاسبه یک [[ماتریس درهمریختگی|ماتریس سردرگمی]](Confusion Matrix) استفاده میشود که در صورت استفاده بهعنوان طبقهبندیکننده، مثبتهای درست، مثبتهای کاذب، منفیهای درست و منفیهای کاذب را در یک جدول نمایش میدهد. سپس این ویژگی های مختلف، بر [[یادگیری درخت تصمیم|اساس معیارهای طبقه بندی]] مختلف بر اساس ماتریس های سردرگمی آنها رتبه بندی می شوند. برخی از معیارهای رایج عبارتند از تخمین "صحت مثبت" (که به صورت اختلاف تعداد مثبتهای کاذب و مثبتهای درست محاسبه میشود.) و [[کسب اطلاعات (درخت تصمیم)|اطلاعات به دست آمده]] (Information Gain). سپس از این ویژگیها برای تقسیم نمونهها به دو مجموعه استفاده میشود: آنهایی که دارای ویژگی برتر هستند و آنهایی که ندارند. |
|||
مثلا شکل زیر یک درخت تصمیم با عمق دو را نشان می دهد که برای طبقه بندی داده ها استفاده می شود. |
|||
این فرآیند به صورت بازگشتی آنقدر در سطوح متوالی درخت تکرار میشود تا درخت به عمق مورد نظر ما برسد. در انتهای درخت، نمونه هایی که دارای ویژگی نهایی هستند، به عنوان "دستهی مثبت" طبقه بندی می شوند و نمونه هایی که فاقد آن ویژگی باشند، به عنوان دستهی منفی طبقه بندی می شوند. <ref name=":2">{{Citation|title=Decision tree learning|date=2021-11-29|url=https://en.wikipedia.org/w/index.php?title=Decision_tree_learning&oldid=1057681416|journal=Wikipedia|language=en|access-date=2021-11-29}}</ref> سپس از این درخت ها به عنوان پیش بینی کننده برای طبقه بندی داده های جدید استفاده می شود. |
|||
چنگل های تصادفی |
|||
در این بخش، به معرفی روش دیگری میپردازیم که مقدار بیشتری تنوع در ساختن درخت ها ایجاد میکند. در این حالت، علاوه بر این که هر درخت از یک مجموعه بوتاسترپ از دادهها استفاده کند، از بین تمام ویژگی های منحصربهفرد موجود نیز، فقط تعداد اندک(اما ثابتی) از ویژگی ها را درنظر میگیرد و درخت را با توجه به آنها میسازد. در نتیجه این حرکتها، درخت های متنوع تری ایجاد میشوند. اگر این فرایند را بارها تکرار کنیم، هر بار یک درخت تولید میشود که در نهایت همه آنها در کنار هم، منجر به یک [[جنگل تصادفی]] میشود که دارای مزایای متعددی نسبت به یک تک درخت تصمیم گیری است (که در آن هیچ فرایند تصادفیای وجود ندارد). در یک جنگل تصادفی، هر درخت، برحسب ویژگی هایی که بر پایه انها ساخته شده، یک نمونه خاص را به عنوان "نمونه مثبت" یا "نمونه منفی" طبقه بندی میکند. در نهایت، آن نمونه بر اساس "اکثریت آراء" به عنوان "نمونه مثبت" یا "نمونه منفی" طبقه بندی می شود. مثالی از این روند، در نمودار زیر آورده شده است، جایی که چهار درخت در یک جنگل تصادفی در مورد اینکه آیا بیمار دارای جهشهای A، B، F و G سرطان دارد یا خیر، رأی می دهند. از آنجایی که سه درخت از چهار درخت رای مثبت می دهند، بیمار به عنوان کسی که سرطان دارد، طبقه بندی میشود! |
|||
جنگلهای تصادفی به دلیل خصوصیتهایی که دارند، یکی از دقیقترین الگوریتمهای دادهکاوی در نظر گرفته میشوند، احتمال کمتری دارد که بر روی داده های خود، [[بیشبرازش]] کنند، و حتی برای مجموعه داده های بزرگ نیز با سرعت و به صورت کارآمد اجرا میشوند. <ref>{{Cite web|title=Random forests - classification description|url=https://www.stat.berkeley.edu/~breiman/RandomForests/cc_home.htm|accessdate=2021-12-09|website=www.stat.berkeley.edu}}</ref> |
|||
چندین فاکتور مهم برای طراحی جنگل تصادفی وجود دارد. اگر درختان در جنگل های تصادفی خیلی عمیق باشند، به دلیل اختصاصی بودن بیش از حد ممکن است بیش از حد درختان رخ دهد. اگر جنگل خیلی بزرگ باشد، الگوریتم ممکن است به دلیل افزایش زمان اجرا کمتر کارآمد شود.به عنوان یک جزء جدایی ناپذیر از جنگل های تصادفی، bagging برای الگوریتم های طبقه بندی بسیار مهم است و یک عنصر حیاتی برای ایجاد تنوع است که امکان افزایش دقت را در هنگام تجزیه و تحلیل داده های جدید فراهم می کند. |
|||
بهبود جنگل های تصادفی و Bagging |
|||
در حالی که تکنیکهای توصیفشده در بالا از [[جنگل تصادفی|جنگلهای تصادفی]] و Bagging استفاده میکنند، تکنیکهای خاصی وجود دارد که میتوان از آنها استفاده کرد تا زمان اجرا و رایگیری بهبود یابد ودقت پیشبینی و عملکرد کلی نیز افزایش یابد. نکات زیر برای ایجاد یک جنگل تصادفی کارآمد، موثر هستند: |
|||
# حداکثر عمق درختان را مشخص کنید: به جای اینکه اجازه دهید جنگل تصادفی شما تا زمانی که تمام گره ها خالص شوند، ادامه یابد، بهتر است آن را در یک نقطه خاص قطع کنید تا شانس بیشبرازش را کاهش دهید. |
|||
# مجموعه داده را هرس کنید: استفاده از یک مجموعه داده بسیار بزرگ ممکن است نتایجی را ایجاد کند که کمتر نشاندهنده دادههای ارائهشده باشد(نسبت به مجموعهای کوچکتر که دقیقتر نشاندهنده چیزی است که روی آن تمرکز شده است.). |
|||
# در مورد دقت یا سرعت تصمیم بگیرید: بسته به نتایج مورد نظر، افزایش یا کاهش تعداد درختان در جنگل می تواند کمک کننده باشد. افزایش تعداد درختان به طور کلی نتایج دقیق تری ارائه می دهد اما سرعت کاهش مییابد، در حالی که کاهش تعداد درختان نتایج سریع تر اما با دقت کمتر ارائه می دهد. |
|||
{| class="wikitable" |
|||
|+مزایا و معایب جنگل های تصادفی و Bagging |
|||
!مزایا |
|||
!معایب |
|||
|- |
|||
|آماده سازی آسان داده ها. |
|||
داده ها با ایجاد یک مجموعه بوت استرپ و تعداد معینی درخت تصمیم برای ساختن یک جنگل تصادفی که از انتخاب ویژگی نیز استفاده می کند، همانطور که در بخش جنگلهای تصادفی ذکر شد، آماده می شود. |
|||
|جنگلهای تصادفی نسبت به درختهای تصمیمگیری تنها یا سایر الگوریتمها دارای پیچدگی پیادهسازی بیشتری هستند. دلیل آن این است که آنها اقدامات اضافی را برای bagging و همچنین عملیات بازگشتی به منظور تولید یک جنگل کامل انجام میدهند که اجرای آن را پیچیده میکند. به همین دلیل، به قدرت محاسباتی و منابع محاسباتی بسیار بیشتری نیاز دارد. |
|||
|- |
|||
|جنگلها که از [[درخت تصمیم|درختهای تصمیمگیری]] متعدد تشکیل شدهاند، میتوانند با دقت بیشتری نسبت به تک درختان پیشبینی کنند. |
|||
|برای آموزش داده ها در مقایسه با درختان تصمیم به زمان بسیار بیشتری نیاز دارد. داشتن یک جنگل بزرگ می تواند به سرعت شروع به کاهش سرعت اجرای برنامه کند، زیرا باید داده های بسیار بیشتری را طی کند، حتی اگر هر درخت از مجموعه کوچکتری از نمونه ها و ویژگی ها استفاده کند. |
|||
|- |
|||
|با داده های غیر خطی به خوبی کار می کند. از آنجایی که اکثر الگوریتمهای مبتنی بر درخت از تقسیمهای خطی استفاده میکنند، استفاده از مجموعهای از درختان بهتر از استفاده از یک تک درخت روی دادههایی که دارای ویژگیهای غیرخطی هستند (یعنی اکثر توزیعهای دنیای واقعی) کار میکند. خوب کار کردن با داده های غیر خطی یک مزیت بزرگ است زیرا سایر تکنیک های داده کاوی مانند تک درخت های تصمیم گیری نیز این کار را انجام نمی دهند. |
|||
|بسیار ساده تر از یک جنگل تصادفی قابل تفسیر است. روی یک درخت می توان با دست (توسط یک انسان) پیشروی کرد که منجر میشود یک درک "قابل توضیح" از آنچه که درخت واقعا انجام میدهد برای تحلیلگر بشود. با افزایش تعداد درختان(مثلا در جنگل تصادفی) این بررسی اگر غیرممکن نباشد، بسیار دشوارتر میشود. |
|||
|- |
|||
|خطر [[بیشبرازش]] کمتر است و حتی در مجموعه داده های بزرگ به طور موثر اجرا می شود. <ref>{{Cite web|last=Team|first=Towards AI|title=Why Choose Random Forest and Not Decision Trees – Towards AI — The World's Leading AI and Technology Publication|url=https://towardsai.net/p/machine-learning/why-choose-random-forest-and-not-decision-trees,%20https://towardsai.net/p/machine-learning/why-choose-random-forest-and-not-decision-trees|accessdate=2021-11-26|language=en-US}}</ref> این نتیجه استفاده جنگل تصادفی از bagging در ارتباط با انتخاب ویژگی تصادفی است. |
|||
|فراتر از محدوده داده های آموزشی را پیش بینی نمی کند. این یک عیب است زیرا در حالی که bagging اغلب اوقات مؤثر است،اما همه داده ها در نظر گرفته نمی شوند، بنابراین نمی تواند کل یک مجموعه داده را پیش بینی کند. |
|||
|- |
|||
|جنگل تصادفی با دقت و سرعت بالایی کار می کند. <ref>{{Cite web|title=Random Forest|url=https://corporatefinanceinstitute.com/resources/knowledge/other/random-forest/|accessdate=2021-11-26|website=Corporate Finance Institute|language=en-US}}</ref> جنگل های تصادفی به دلیل استفاده از مجموعه داده های کوچکتر بسیار سریعتر از درختان تصمیم هستند. |
|||
|برای ایجاد مجدد نتایج خاص، باید سبد(seed) تصادفی دقیق مورد استفاده برای تولید مجموعههای بوت استرپ را ذخیره و بررسی کنید. این کار ممکن است هنگام جمع آوری داده ها برای تحقیق یا در یک کلاس داده کاوی مهم باشد. استفاده از سبدهای تصادفی برای جنگلهای تصادفی ضروری است. |
|||
|} |
|||
الگوریتم (طبقه بندی) |
|||
برای طبقه بندی، یک [[آموزش، اعتبارسنجی و مجموعههای آزمایشی|مجموعه آموزشی]] مانند <math>D</math> و m نمونهی بوت استرپ ورودی بگیرید. یک طبقه بندی کننده مانند <math>C^*</math> به عنوان خروجی نهایی ایجاد کنید <ref name="Bauer">{{Cite journal|last=Bauer|first=Eric|last2=Kohavi|first2=Ron|date=1999|title=An Empirical Comparison of Voting Classification Algorithms: Bagging, Boosting, and Variants|journal=Machine Learning|volume=36|pages=108–109|doi=10.1023/A:1007515423169|doi-access=free}}</ref> |
|||
# <math>m</math> مجموعهی آموزشی جدید مانند <math>D_i</math> از روی <math>D</math> (با جایگذاری) ایجاد کنید. |
|||
# طبقه بند <math>C_i</math> از روی مجموعه<math>D_i</math> ساخته میشود. |
|||
# در نهایت، طبقه بند <math>C^*</math> با استفاده از مجموعهی طبقه بندهای قبلی که ایجاد کردهایم( <math>C_i</math> های مرحله قبلی) روی مجموعه دادههای اصلی <math>D</math> ایجاد می شود. سودوکد زیر این فرایند را نشان میدهد : |
|||
<syntaxhighlight> |
|||
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 |
|||
</syntaxhighlight>مثال: داده های ازون |
|||
برای نشان دادن اصول اولیه Bagging، تحلیلی در مورد رابطه بین [[ازون (مولکول)|ازون]] و دما ارائه شده است (دادهها از [[پیتر روسیو|Rousseeuw]] و Leroy{{نیازمند شفافسازی|date=May 2021}} (1986)، تجزیه و تحلیل انجام شده در زبان برنامهنویسی [[آر (زبان برنامهنویسی)|R]] ). |
|||
به نظر می رسد رابطه بین دما و ازن در این مجموعه داده، بر اساس نمودار پراکندگی، غیرخطی باشد. برای توصیف ریاضی این رابطه، هموار کننده های [[رگرسیون محلی|LOESS]] (با پهنای باند 0.5) استفاده می شود. به جای ساختن یک هموارکننده واحد برای مجموعه دادههای کامل، 100 نمونه [[بوتاسترپینگ (آمار)|بوت استرپ]] ایجاد شد. هر مجموعه نمونه، از یک زیرمجموعه تصادفی از داده های اصلی تشکیل شده است و شباهتی از توزیع و تنوع مجموعه اصلی را حفظ می کند. به ازای هر نمونه بوت استرپ، یک هموارکننده LOESS ایجاد میشود. سپس این 100 هموارکننده مختلف، پیشبینیهای خود را روی دادهها انجام میدهد.در شکل زیر خطوط سیاه نشان دهنده این پیش بینی های اولیه است. این خطوط خیلی به یکدیگر شبیه نیستند و تمایل دارند تا نقاط مجموعه داده خودشان را بیش از حد تطبیق دهند. |
|||
با در نظر گرفتن میانگین 100 هموارکننده، که هر کدام مربوط به زیرمجموعه ای از مجموعه داده های اصلی است، به یک پیش بینی کننده کیسهشده (خط قرمز) می رسیم.(انگار که نتیجه همه 100 هموار کننده را در یک کیسه ریخته باشیم!) |
|||
مزایا و معایب |
|||
مزایا: |
|||
* تعداد زیادی از یادگیرندگان ضعیف معمولاً در کل مجموعه عملکرد بهتری از یک یادگیرنده دارند و اضافه برازش کمتری دارند |
|||
* واریانس را در یادگیرنده ضعیف [[تعصب (آمار)|با سوگیری کم با]] واریانس بالا حذف می کند <ref name=":3">{{Cite web|url=https://corporatefinanceinstitute.com/resources/knowledge/other/bagging-bootstrap-aggregation/|title=What is Bagging (Bootstrap Aggregation)?|publisher=Corporate Finance Institute|website=CFI|accessdate=December 5, 2020}}</ref> |
|||
* می تواند به [[رایانش موازی|صورت موازی]] انجام شود، زیرا هر بوت استرپ جداگانه می تواند قبل از ترکیب به تنهایی پردازش شود <ref>{{Cite web|url=https://medium.com/swlh/bagging-bootstrap-aggregating-overview-b73ca019e0e9|title=Bagging (Bootstrap Aggregating), Overview|last=Zoghni|first=Raouf|publisher=The Startup|date=September 5, 2020}}</ref> |
|||
معایب: |
|||
* برای یادگیرنده ضعیف با تعصب زیاد، کیسه کردن نیز سوگیری بالایی را در مجموع خود حمل می کند <ref name=":32">{{Cite web|url=https://corporatefinanceinstitute.com/resources/knowledge/other/bagging-bootstrap-aggregation/|title=What is Bagging (Bootstrap Aggregation)?|publisher=Corporate Finance Institute|website=CFI|accessdate=December 5, 2020}}</ref> |
|||
* از دست دادن قابلیت تفسیر یک مدل |
|||
* بسته به مجموعه داده می تواند از نظر محاسباتی گران باشد. |
|||
تاریخچه |
|||
مفهوم Bagging از مفهوم بوتاسترپ مشتق میشود که توسط بردلی افرون توسعه داده شد. <ref name=":8">{{Cite journal|last=Efron|first=B.|author-link=Bradley Efron|year=1979|title=Bootstrap methods: Another look at the jackknife|journal=[[The Annals of Statistics]]|volume=7|issue=1|pages=1–26|doi=10.1214/aos/1176344552|doi-access=free}}</ref> تجمیع بوت استرپ(Bagging) توسط [[لئو بریمن]] پیشنهاد شد که اصطلاح اختصاری "bagging" ( '''b'''ootstrap '''agg'''regat'''ing''' ) را نیز ابداع کرد. بریمن در سال 1994 مفهوم Bagging را برای بهبود طبقهبندی با ترکیب طبقهبندی مجموعههای آموزشی که بهطور تصادفی تولید میشوند، توسعه داد. <ref name=":12">{{Cite journal|last=Breiman|first=Leo|date=September 1994|title=Bagging Predictors|url=https://www.stat.berkeley.edu/~breiman/bagging.pdf|journal=Technical Report|publisher=Department of Statistics, University of California Berkeley|access-date=2019-07-28}}</ref> |
نسخهٔ ۲۲ دسامبر ۲۰۲۲، ساعت ۱۹:۵۱
تجمیع بوتاسترپ (Bootstrap Aggregating) که به آن bagging نیز میگویند یک روش در یادگیری ماشینی است که برای بهبود پایداری و دقت الگوریتمهای یادگیری ماشینی مورد استفاده در طبقهبندی آماری و رگرسیون طراحی شده است. این روش همچنین به کاهش واریانس کمک میکند و به جلوگیری از بیشبرازش کمک می کند. اگرچه این روش معمولاً برای روش های درخت تصمیم استفاده می شود، اما می توان آن را با هر نوع روشی استفاده کرد. Bagging را میتوان یک شکل خاص از روش میانگین گیری مدل دانست.
شرح تکنیک
روش Bagging که یک تکنیک بازنمونهگیری(Resampling) است که از روی یک مجموعه آموزشی با سایز به تعداد n دیتاست آموزشی جدید هر کدام با سایز ایجاد کند. این روش به طور یکنواخت و با جایگزینی شروع به نمونه برداری از میکند. با نمونه برداری با جایگزینی، ممکن است برخی از مشاهدات در هر یک از ها، چندین بار تکرار شود . اگر ، به ازای n های بزرگ، انتظار می رود مجموعه حدود از نمونه های منحصر به فرد D را شامل شود. [۱] این نوع نمونه به نمونه بوت استرپ معروف است. نمونه برداری با جایگزینی تضمین می کند که هر بوت استرپ مستقل از همتایان خود است، زیرا در هنگام نمونه برداری به نمونه های انتخابی قبلی بستگی ندارد. سپس، m مدل بر روی m نمونهای که در مرحله قبل توضیح داده شد، برازش میشوند و آموزش میبینند. و با میانگینگیری خروجی (برای رگرسیون) یا رای اکثریت (برای طبقهبندی) ترکیب میشوند.
Bagging منجر به "بهبود رویه های ناپایدار" می شود، [۲] که به عنوان مثال،شامل شبکه های عصبی مصنوعی ، درختان طبقه بندی و رگرسیون ، و انتخاب زیر مجموعه در رگرسیون خطی می شود.[۳] از طرف دیگر، این روش میتواند عملکرد روشهای پایدار مانند K-نزدیکترین همسایهها(K-Nearest Neighbors) را به میزان کمی کاهش دهد.
فرآیند الگوریتم
شرایط کلیدی
سه نوع مجموعه داده در جمع آوری بوت استرپ وجود دارد. اینها مجموعه داده های اصلی، دادههای بوت استرپ و دادههای خارج از کیسه(Out-of-bag) هستند. در بخش های زیر، نحوهی ساخت مجموعه بوتاسترپ و مجموعه خارج از کیسه توضیح داده میشود.
ایجاد مجموعه داده بوت استرپ
مجموعه داده بوت استرپ با انتخاب تصادفی اشیا از مجموعه داده اصلی ساخته می شود. همچنین،انداره این مجموعه، باید به اندازه مجموعه داده اصلی باشد. با این حال، مجموعه داده بوتاسترپ می تواند دارای اشیاء تکراری نیز باشد. در شکل زیر، مثال ساده ای از عملکرد بوتاسترپ نشان داده شده است :
فرض کنید مجموعه داده اصلی(گروه سمت چپ) یک گروه متشکل از 12 نفر باشد. این افراد امیلی، جسی، جورج، کنستانتین، لکسی، تئودور، جان، جیمز، ریچل، آنتونی، الی و جمال هستند.
با نمونهگیری تصادفی از نامها، فرض کنید مجموعه دادههای بوت استرپ ما(گروه سمت راست) دارای جیمز، الی، کنستانتین، لکسی، جان، کنستانتین، تئودور، کنستانتین، آنتونی، لکسی، کنستانتین و تئودور باشد. در این مورد، نمونه بوت استرپ شامل چهار نمونه تکراری برای کنستانتین ، و دو نمونه تکراری برای لکسی و تئودور است.
ایجاد مجموعه داده خارج از کیسه
مجموعه داده خارج از کیسه نشان دهنده افرادی از مجموعه داده اصلی هستند که در مجموعه داده بوت استرپ قرار نگرفتهاند. در این مورد، نمونه های باقی مانده مجموعه داده اصلی که در روند بوتاسترپ انتخاب نشدند عبارتند از امیلی، جسی، جورج، ریچل و جمال.
اهمیت
از آنجا که برای آزمایش دقت الگوریتم "جنگل تصادفی" از مجموعه های بوتاسترپ و خارج از کیسه استفاده میشود، ایجاد مجموعه داده های بوت استرپ و خارج از کیسه بسیار مهم است.(دلیل این ماجرا این است که ما معمولا به مجموعه آموزشی بسیار بزرگ دسترسی نداریم که برای هر مدل، مجموعه داده واقعا مجزا تولید کنیم، بنابراین سعی میکنیم از مجموعه داده آموزشی موجود، مجموعه های متنوعی ایجاد کنیم.) به عنوان مثال، مدلی که 50 درخت را با استفاده از مجموعه داده های بوت استرپ/خارج از کیسه تولید می کند، نسبت به زمانی که 10 درخت تولید می کند، دقت بهتری خواهد داشت. از آنجایی که الگوریتم، چندین درخت و بنابراین مجموعه داده های متعدد تولید می کند، احتمال اینکه یک شی از مجموعه داده های بوت استرپ خارج شود کم است. چند بخش بعدی در مورد نحوه عملکرد الگوریتم جنگل تصادفی با جزئیات بیشتر صحبت می کند.
ایجاد درختان تصمیم(Decision Tree)
مرحله بعدی الگوریتم، شامل تولید یک مجموعه از درختهای تصمیم از مجموعه داده بوت استرپ است. به ایت منظور، الگوریتم ما هر ویژگی را بررسی میکند و مشخص میکند که حضور یا عدم حضور آن ویژگی، برای چند نمونه نتیجه مثبت یا منفی به همراه دارد. سپس از این اطلاعات برای محاسبه یک ماتریس سردرگمی(Confusion Matrix) استفاده میشود که در صورت استفاده بهعنوان طبقهبندیکننده، مثبتهای درست، مثبتهای کاذب، منفیهای درست و منفیهای کاذب را در یک جدول نمایش میدهد. سپس این ویژگی های مختلف، بر اساس معیارهای طبقه بندی مختلف بر اساس ماتریس های سردرگمی آنها رتبه بندی می شوند. برخی از معیارهای رایج عبارتند از تخمین "صحت مثبت" (که به صورت اختلاف تعداد مثبتهای کاذب و مثبتهای درست محاسبه میشود.) و اطلاعات به دست آمده (Information Gain). سپس از این ویژگیها برای تقسیم نمونهها به دو مجموعه استفاده میشود: آنهایی که دارای ویژگی برتر هستند و آنهایی که ندارند.
مثلا شکل زیر یک درخت تصمیم با عمق دو را نشان می دهد که برای طبقه بندی داده ها استفاده می شود.
این فرآیند به صورت بازگشتی آنقدر در سطوح متوالی درخت تکرار میشود تا درخت به عمق مورد نظر ما برسد. در انتهای درخت، نمونه هایی که دارای ویژگی نهایی هستند، به عنوان "دستهی مثبت" طبقه بندی می شوند و نمونه هایی که فاقد آن ویژگی باشند، به عنوان دستهی منفی طبقه بندی می شوند. [۴] سپس از این درخت ها به عنوان پیش بینی کننده برای طبقه بندی داده های جدید استفاده می شود.
چنگل های تصادفی
در این بخش، به معرفی روش دیگری میپردازیم که مقدار بیشتری تنوع در ساختن درخت ها ایجاد میکند. در این حالت، علاوه بر این که هر درخت از یک مجموعه بوتاسترپ از دادهها استفاده کند، از بین تمام ویژگی های منحصربهفرد موجود نیز، فقط تعداد اندک(اما ثابتی) از ویژگی ها را درنظر میگیرد و درخت را با توجه به آنها میسازد. در نتیجه این حرکتها، درخت های متنوع تری ایجاد میشوند. اگر این فرایند را بارها تکرار کنیم، هر بار یک درخت تولید میشود که در نهایت همه آنها در کنار هم، منجر به یک جنگل تصادفی میشود که دارای مزایای متعددی نسبت به یک تک درخت تصمیم گیری است (که در آن هیچ فرایند تصادفیای وجود ندارد). در یک جنگل تصادفی، هر درخت، برحسب ویژگی هایی که بر پایه انها ساخته شده، یک نمونه خاص را به عنوان "نمونه مثبت" یا "نمونه منفی" طبقه بندی میکند. در نهایت، آن نمونه بر اساس "اکثریت آراء" به عنوان "نمونه مثبت" یا "نمونه منفی" طبقه بندی می شود. مثالی از این روند، در نمودار زیر آورده شده است، جایی که چهار درخت در یک جنگل تصادفی در مورد اینکه آیا بیمار دارای جهشهای A، B، F و G سرطان دارد یا خیر، رأی می دهند. از آنجایی که سه درخت از چهار درخت رای مثبت می دهند، بیمار به عنوان کسی که سرطان دارد، طبقه بندی میشود!
جنگلهای تصادفی به دلیل خصوصیتهایی که دارند، یکی از دقیقترین الگوریتمهای دادهکاوی در نظر گرفته میشوند، احتمال کمتری دارد که بر روی داده های خود، بیشبرازش کنند، و حتی برای مجموعه داده های بزرگ نیز با سرعت و به صورت کارآمد اجرا میشوند. [۵]
چندین فاکتور مهم برای طراحی جنگل تصادفی وجود دارد. اگر درختان در جنگل های تصادفی خیلی عمیق باشند، به دلیل اختصاصی بودن بیش از حد ممکن است بیش از حد درختان رخ دهد. اگر جنگل خیلی بزرگ باشد، الگوریتم ممکن است به دلیل افزایش زمان اجرا کمتر کارآمد شود.به عنوان یک جزء جدایی ناپذیر از جنگل های تصادفی، bagging برای الگوریتم های طبقه بندی بسیار مهم است و یک عنصر حیاتی برای ایجاد تنوع است که امکان افزایش دقت را در هنگام تجزیه و تحلیل داده های جدید فراهم می کند.
بهبود جنگل های تصادفی و Bagging
در حالی که تکنیکهای توصیفشده در بالا از جنگلهای تصادفی و Bagging استفاده میکنند، تکنیکهای خاصی وجود دارد که میتوان از آنها استفاده کرد تا زمان اجرا و رایگیری بهبود یابد ودقت پیشبینی و عملکرد کلی نیز افزایش یابد. نکات زیر برای ایجاد یک جنگل تصادفی کارآمد، موثر هستند:
- حداکثر عمق درختان را مشخص کنید: به جای اینکه اجازه دهید جنگل تصادفی شما تا زمانی که تمام گره ها خالص شوند، ادامه یابد، بهتر است آن را در یک نقطه خاص قطع کنید تا شانس بیشبرازش را کاهش دهید.
- مجموعه داده را هرس کنید: استفاده از یک مجموعه داده بسیار بزرگ ممکن است نتایجی را ایجاد کند که کمتر نشاندهنده دادههای ارائهشده باشد(نسبت به مجموعهای کوچکتر که دقیقتر نشاندهنده چیزی است که روی آن تمرکز شده است.).
- در مورد دقت یا سرعت تصمیم بگیرید: بسته به نتایج مورد نظر، افزایش یا کاهش تعداد درختان در جنگل می تواند کمک کننده باشد. افزایش تعداد درختان به طور کلی نتایج دقیق تری ارائه می دهد اما سرعت کاهش مییابد، در حالی که کاهش تعداد درختان نتایج سریع تر اما با دقت کمتر ارائه می دهد.
مزایا | معایب |
---|---|
آماده سازی آسان داده ها.
داده ها با ایجاد یک مجموعه بوت استرپ و تعداد معینی درخت تصمیم برای ساختن یک جنگل تصادفی که از انتخاب ویژگی نیز استفاده می کند، همانطور که در بخش جنگلهای تصادفی ذکر شد، آماده می شود. |
جنگلهای تصادفی نسبت به درختهای تصمیمگیری تنها یا سایر الگوریتمها دارای پیچدگی پیادهسازی بیشتری هستند. دلیل آن این است که آنها اقدامات اضافی را برای bagging و همچنین عملیات بازگشتی به منظور تولید یک جنگل کامل انجام میدهند که اجرای آن را پیچیده میکند. به همین دلیل، به قدرت محاسباتی و منابع محاسباتی بسیار بیشتری نیاز دارد. |
جنگلها که از درختهای تصمیمگیری متعدد تشکیل شدهاند، میتوانند با دقت بیشتری نسبت به تک درختان پیشبینی کنند. | برای آموزش داده ها در مقایسه با درختان تصمیم به زمان بسیار بیشتری نیاز دارد. داشتن یک جنگل بزرگ می تواند به سرعت شروع به کاهش سرعت اجرای برنامه کند، زیرا باید داده های بسیار بیشتری را طی کند، حتی اگر هر درخت از مجموعه کوچکتری از نمونه ها و ویژگی ها استفاده کند. |
با داده های غیر خطی به خوبی کار می کند. از آنجایی که اکثر الگوریتمهای مبتنی بر درخت از تقسیمهای خطی استفاده میکنند، استفاده از مجموعهای از درختان بهتر از استفاده از یک تک درخت روی دادههایی که دارای ویژگیهای غیرخطی هستند (یعنی اکثر توزیعهای دنیای واقعی) کار میکند. خوب کار کردن با داده های غیر خطی یک مزیت بزرگ است زیرا سایر تکنیک های داده کاوی مانند تک درخت های تصمیم گیری نیز این کار را انجام نمی دهند. | بسیار ساده تر از یک جنگل تصادفی قابل تفسیر است. روی یک درخت می توان با دست (توسط یک انسان) پیشروی کرد که منجر میشود یک درک "قابل توضیح" از آنچه که درخت واقعا انجام میدهد برای تحلیلگر بشود. با افزایش تعداد درختان(مثلا در جنگل تصادفی) این بررسی اگر غیرممکن نباشد، بسیار دشوارتر میشود. |
خطر بیشبرازش کمتر است و حتی در مجموعه داده های بزرگ به طور موثر اجرا می شود. [۶] این نتیجه استفاده جنگل تصادفی از bagging در ارتباط با انتخاب ویژگی تصادفی است. | فراتر از محدوده داده های آموزشی را پیش بینی نمی کند. این یک عیب است زیرا در حالی که bagging اغلب اوقات مؤثر است،اما همه داده ها در نظر گرفته نمی شوند، بنابراین نمی تواند کل یک مجموعه داده را پیش بینی کند. |
جنگل تصادفی با دقت و سرعت بالایی کار می کند. [۷] جنگل های تصادفی به دلیل استفاده از مجموعه داده های کوچکتر بسیار سریعتر از درختان تصمیم هستند. | برای ایجاد مجدد نتایج خاص، باید سبد(seed) تصادفی دقیق مورد استفاده برای تولید مجموعههای بوت استرپ را ذخیره و بررسی کنید. این کار ممکن است هنگام جمع آوری داده ها برای تحقیق یا در یک کلاس داده کاوی مهم باشد. استفاده از سبدهای تصادفی برای جنگلهای تصادفی ضروری است. |
الگوریتم (طبقه بندی)
برای طبقه بندی، یک مجموعه آموزشی مانند و m نمونهی بوت استرپ ورودی بگیرید. یک طبقه بندی کننده مانند به عنوان خروجی نهایی ایجاد کنید [۸]
- مجموعهی آموزشی جدید مانند از روی (با جایگذاری) ایجاد کنید.
- طبقه بند از روی مجموعه ساخته میشود.
- در نهایت، طبقه بند با استفاده از مجموعهی طبقه بندهای قبلی که ایجاد کردهایم( های مرحله قبلی) روی مجموعه دادههای اصلی ایجاد می شود. سودوکد زیر این فرایند را نشان میدهد :
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 را برای بهبود طبقهبندی با ترکیب طبقهبندی مجموعههای آموزشی که بهطور تصادفی تولید میشوند، توسعه داد. [۱۳]
- ↑ 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 .
- ↑ Breiman, Leo (1996). "Bagging predictors". Machine Learning. 24 (2): 123–140. CiteSeerX 10.1.1.32.9399. doi:10.1007/BF00058655.
- ↑ Breiman, Leo (September 1994). "Bagging Predictors" (PDF). Technical Report. Department of Statistics, University of California Berkeley. Retrieved 2019-07-28.
- ↑ "Decision tree learning", Wikipedia (به انگلیسی), 2021-11-29, retrieved 2021-11-29
- ↑ "Random forests - classification description". www.stat.berkeley.edu. Retrieved 2021-12-09.
- ↑ 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.
- ↑ "Random Forest". Corporate Finance Institute (به انگلیسی). Retrieved 2021-11-26.
- ↑ 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.
- ↑ "What is Bagging (Bootstrap Aggregation)?". CFI. Corporate Finance Institute. Retrieved December 5, 2020.
- ↑ Zoghni, Raouf (September 5, 2020). "Bagging (Bootstrap Aggregating), Overview". The Startup.
- ↑ "What is Bagging (Bootstrap Aggregation)?". CFI. Corporate Finance Institute. Retrieved December 5, 2020.
- ↑ Efron, B. (1979). "Bootstrap methods: Another look at the jackknife". The Annals of Statistics. 7 (1): 1–26. doi:10.1214/aos/1176344552.
- ↑ Breiman, Leo (September 1994). "Bagging Predictors" (PDF). Technical Report. Department of Statistics, University of California Berkeley. Retrieved 2019-07-28.