جنگل تصادفی
جنگل تصادفی یا جنگلهای تصمیم تصادفی (به انگلیسی: Random forest) یک روش یادگیری ترکیبی برای دستهبندی، رگرسیون میباشد، که بر اساس ساختاری متشکل از شمار بسیاری درخت تصمیم، بر روی زمان آموزش و خروجی کلاسها (کلاسبندی) یا برای پیشبینیهای هر درخت به شکل مجزا، کار میکنند. جنگلهای تصادفی برای درختان تصمیم که در مجموعهٔ آموزشی دچار بیش برازش میشوند، مناسب هستند. عملکرد جنگل تصادفی معمولا بهتر از درخت تصمیم است، اما این بهبود عملکرد تا حدی به نوع داده هم بستگی دارد.
نخستین الگوریتم برای جنگلهای تصمیم تصادفی را «تین کم هو» با بهرهگیری از روش زیرفضاهای تصادفی پدیدآورد. نسخههای بعدی آن توسط لیو بریمن ارتقا یافت.
پیشینه
پژوهشهای «بریمن» روی کار «امیت و گمن» اثر گذاشت، کسانی که پژوهش براساس دسته تصادفی که نود را تقسیم میکند (در مبحث بزرگ شدن تک درخت) ارائه کردند در این روش، پیش از این که هر درخت یا هر گره را جاسازی کنند، جنگلی از درختان بزرگ میشود و گزینش از بین گونهای از درختان که برای گزینش تصادفی زیرفضاهایی از داده آموزش دیدهاند، صورت میگیرد. در پایان ایده بهبود بخشیدن به گرههای تصادفی (که انتخاب هر گره به شکل تصادفی بوده) به جای بهبودی قطعی توسط «دیتریش» بیان شد دستاوردهای دربارهٔ جنگل تصادفی نخستین بار به دست «لئو بریمن» مقاله شد.
این مقاله روشهایی از چگونگی ساخت جنگل بدون کنترل درختها با بهرهگیری از CART را بیان میکند که با متد بگینگ و بهبودی نود تصادفی ترکیب شدهاست. به علاوه، این مقاله بسیاری از نتایج اولیه به دست آمده که شناخته شده بودند و چه آنهایی که به چاپ رسیده بودند را ترکیب میکرد که این ترکیبات پایه و اساس تمرینات امروزی جنگلهای تصادفی را شامل میشود این الگوریتم توسط «لئو بریمن و عادل کالچر» توسعه یافت که جنگل تصادفی نیز جزو دستاوردهای ایشان بود ایده بگینگ برای ساخت مجموعهای از درختهای تصمیم و انتخاب تصادفی نخست توسط «هو» و سپس «امیت و گمان» کامل شد. این تمرینات امروزی عبارتند از:
۱. بهره گرفتن از نقص خارج از کیسه برای تعمیم نقصهای سازماندهی
۲. اهمیت اندازهگیری گونهها و تنوع از طریق جایگشت
همچنین این گزارش نخستین فرجام تئوری برای جنگلهایی که از راه نقص سازماندهی تعمیم یافته بودند را بیان میکند که بستگی به قدرت درختها و ارتباط آنها دارد.
الگوریتم
مقدمات: آموزش درخت تصمیم
درخت تصمیم روش مشهوری برای انواع مختلفی از وظایف یادگیری ماشین به حساب می آید. با این حال در بسیاری موارد دقیق نیستند.
در کل، معمولا درخت تصمیمی که بیش از حد عمیق باشد الگوی دقیق نخواهد داشت: دچار بیش برارزش شده , و دارای سوگیری پایین و واریانس بالا میباشد. جنگل تصادفی روشی است برای میانگین گیری با هدف کاهش واریانس با استفاده از درخت های تصمیم عمیقی که از قسمت های مختلف داده آموزشی ایجاد شده باشند. در این روش معمولا افزایش جزئی سوگیری و از دست رفتن کمی از قابلیت تفسیر اتفاق افتاده اما در کل عملکرد مدل را بسیار افزایش خواهد داد.
به علاوه به کمک انحراف معیار پیشبینیها از درختهای رگرسیون مستقل میتوان تخمینی از عدم قطعیت پیشبینی داشت:
تعداد نمونهها در فرمول بالا (
کیسهگذاری درختان
مجموعه داده را با
برای
- نمونه با جایگزینی از دادهانتخاب کن و این نمونهها را در مجموعه دادهقرار بده. از آنجا که نمونهگیری با جایگزینی صورت میگیرد یک نمونه ممکن است چندین بار انتخاب شود.
- یک درخت تصادفی به اسم بابه روش پایین بساز:
- هر دفعه برای پیدا کردن بهترین متغیر ابتدا یک تعداد مشخصی از متغیرها را کاملا به صورت تصادفی انتخاب کن (مثلا تا،از قبل به مسئله داده شدهاست، و معمولاً با جذر تعداد متغیرها برابر است) و از میان آنها بهترین متغیر را انتخاب کن.
- هر دفعه برای پیدا کردن بهترین متغیر ابتدا یک تعداد مشخصی از متغیرها را کاملا به صورت تصادفی انتخاب کن (مثلا
در مسئله رگرسیون مدل نهائی، میانگین تمامی درختها است یعنی
این نوع ترکیب مدلها جواب بهتری به ما میدهد زیرا گوناگونی و تنوع مدلها را افزایش میدهد بدون این که بایاس را افزایش دهد! این بدین معناست که زمانی که پیشبینی تکی از یک درخت دارای نویز بالایی درون مجموعه دسته آموزش دیده اش باشد، در میانگین بسیاری از درختها این نویز وجود نخواهد داشت. به شکل ساده آموزش درختان به صورت تکی میتواند درختهای در ارتباط قوی تری را ارائه دهد. بوت استرپ کردن نمونه، روشی برای یکپارچهتر کردن درختها با نمایش مجموعه دادههای آموزش دیده گوناگون است.
از کیسهگذاری تا جنگل تصادفی
روندی که گفته شد الگوریتم اصلی بگینگ برای درختان را توصیف میکند. جنگل تصادفی تنها یک اختلاف با این طرح کلی دارد: و آن این که از یک الگوریتم یادگیری درخت اصلاح شدهاستفاده میکند که در هر تقسیم کاندیدها در فرایند یادگیری، زیر مجموعهای تصادفی از ویژگیهای آن را پردازش میکنند. این پردازش گاهی «کیسهگذاری ویژگی» نامیده میشود. دلیل انجام این کار این است که ارتباط درختها در یک نمونه بوت استرپ معمولی را نشان میدهد. اگر یک یا چند ویژگی پیشبینیکنندهها، برای متغیر پاسخ (خروجی هدف) بسیار قوی باشد، این ویژگی در بسیاری از درختهای B که سبب ارتباط آنها میشود، انتخاب خواهد شد. آنالیز چگونگی کارکرد بگینگ و مجموعه دستههای تصادفی، کمک میکند تا بتوان به دقتهای با شرایط گوناگون دست یافت که توسط «هو» نیز ارائه شده بودند.
Extra-Trees
برای برداشتن یک گام دیگر در جهت تصادفیسازی به مدل درختان بینهایت تصادفی یاExtra-trees میرسیم. این مدل نیز مانند جنگل تصادفی از تجمیع تعدادی درخت مستقل استفاده میکند اما با دو تفاوت اساسی: اول آنکه هر درخت توسط تمام دادهٔ آموزش (و نه یک نمونهٔ bootstrap) train میشود و دوم آنکه در مرحلهٔ split کردن مقدار cut-point از یک توزیع احتمالاتی یکنواخت روی دامنهٔ مقادیر ممکن استفاده میشود که این بر خلاف روش مرسوم که استفاده از معیار هایی مانند بهرهٔ اطلاعاتی یا ناخالصی جینی برای تعیین عدد cut-point است. تصادفیسازی این بخش آموزش را تسریع میبخشد.
ویژگان
اهمیت متغیرها
جنگل تصادفی میتواند برای رتبهبندی اهمیت متغیرها در یک رگرسیون یا مسئلهٔ طبقهبندی به کار رود. تکنیکی که در ادامه آمدهاست در مقاله اصلی «بریمن» آورده شده بود و در پکیج R جنگل تصادفی اجرا میشود. نخستین گام در اهمیت اندازهگیری متغیرها در مجموعه دادهها که با
برای اندازهگیری اهمیت
این روش تعیین اهمیت متغیر شامل برخی اشکالات میشود. برای دادهای که شامل متغیرهای بخشبندی شده با سطوح مختلف شمارههاست، جنگل تصادفی به این خاصیتشان بر اساس بالا یا پایین بودن سطح بایاس دارد و هرچه سطح بالاتر باشد بیشتر به سمت آنان سوگیری دارد. متدهایی همانند partial permutations و درختان در حال رشد بیطرف، میتواند برای حل مشکل به کار گرفته شوند. اگر داده شامل گروههایی از ویژگیهای مرتبط به هم با شبیهسازی برای خروجی باشد، در این حالت گروههای کوچک نسبت به گروههای بزرگ برتری دارند.
رابطه با الگوریتم نزدیکترین همسایهها
ارتباط بین جنگل تصادفی و الگوریتم کی-نزدیکترین همسایه (K-NN) در سال ۲۰۰۲ توسط «لین» و «جو» استخراج شد. به نظر میرسد که هردوی آنها میتوانند به عنوان طرح پروزنترین همسایه نامگذاری شوند.
اینها مدلهایی برای ساخت دادههای آموزش دیده {(xi,yi)} هستند که پیشبینیهای تازه y را برای x' با نگاه به همسایگی از نقاط، از طریق تابع وزن به صورت زیر در میآورد:
در اینجا
۱. در k-NN وزنها
۲. در درخت
به سبب این که میانگین جنگل مجموعهای از درختهای
یادگیری بینظارت با جنگل تصادفی
پیشبینیکننده های جنگل تصادفی به طور طبیعی و به عنوان بخشی از فرآیند ساختشان به یک معیار عدم تشابه میان مشاهدات تبدیل میشوند. میتوان یک معیار عدم تشابه جنگل تصادفی را به صورت زیر تعریف کرد: ایدهٔ اصلی این است که از یک پیشبینیکننده جنگل تصادفی استفاده کنیم که میان دادهٔ مشاهدهشده و دادهٔ مصنوعی که به خوبی تولید شده تمایز بگذارد. منظور از دادهٔ مشاهده شده دادهٔ اصلی و بدون برچسب است و دادهٔ ساختگی نیز از یک توزیع مرجع گرفته میشود. یک عدم تشابه جنگل تصادفی میتواند به این علت که نسبت به تبدیل های یکنوا روی ورودی بدون تغییر است و به خوبی از پس دادههای با انواع متغیر مختلط برمیآید و از لحاظ مشاهدات قوی است مورد توجه باشد. این معیار به سادگی از پس تعداد زیادی متغیر نیمهپیوسته برمیآید که این موضوع به دلیل ویژگی ذاتی انتخاب متغیرش است. به طور مثال معیار Addcl 1 به مشارکت متغیر ها بر اساس میزان مستقل بودنشان از دیگر متغیرها وزن میدهد. معیار عدم تشابه جنگل تصادفی در کاربرد های گوناگونی به کار رفتهاست.
KeRF
یک نمونهٔ آموزش
انواع
در انواع دیگری از جنگل های تصادفی از مدل های دیگری به عنوان تخمینگر پایه استفاده میشود. به طور مثال رگرسیون لوجستیک چندجملهای و دستهبند بیز ساده.
مزایا
در میان ابزارهای پشتیبانی تصمیم، درخت تصمیم و دیاگرام تصمیم دارای مزایایی هستند:
۱- فهم ساده: هر انسان با اندکی مطالعه و آموزش میتواند، طریقه کار با درخت تصمیم را بیاموزد.
۲- کار کردن با دادههای بزرگ و پیچیده: درخت تصمیم در عین سادگی میتواند با دادههای پیچیده به راحتی کار کند و از روی آنها تصمیم بسازد.
۳-استفاده مجدد آسان: در صورتی که درخت تصمیم برای یک مسئله ساخته شد، نمونههای مختلف از آن مسئله را میتوان با آن درخت تصمیم محاسبه کرد.
۴- قابلیت ترکیب با روشهای دیگر: نتیجه درخت تصمیم را میتوان با تکنیکهای تصمیمسازی دیگر ترکیب کرده و نتایج بهتری بدست آورد.
معایب
با آنکه جنگلهای تصادفی عموام به دقت بالاتری نسبت به یک درخت تصمیم میرسند, اما آنها ویژگی ذاتی قابلتفسیر بودن موجود در درختهای تصمیم را ندارند. درختهای تصمیم در میان گروه نسبتا کوچکی از مدلهای یادگیری ماشین هستند که به سادگی تفسیر میشوند. تفسیرپذیری یکی از مورداستقبالترین ویژگی های یک مدل است. این مدل ها به توسعهدهندگان این امکان را میدهد که از واقعگرایانه بودن تصمیماتی که مدل میگیرد اطمینان حاصل کنند و همچنین به کاربران اطمینان بیشتری در اعتماد به تصمیمات گرفتهشده توسط مدل را میدهد. به علاوه, در مسائل با متغیر های categorical متعدد, جنگل تصمیم ممکن است نتواند دقت مدل پایه را افزایش دهد. به طور کلی در حالاتی که با افزایش تعداد یک تخمینگر نتوان به دقت بهتری رسید استفاده از آن توجیهی ندارد.
مثال ۱
درخت تصمیم در بهینهسازی مشارکت اوراق بهادار مورد استفاده قرار گیرد. مثال زیر اوراق بهدار ۷ طرح مختلف را نشان میدهد. شرکت ۱۰۰۰۰۰۰۰۰ برای کل سرمایهگذاریها دارد. خطوط پر رنگ نشان دهنده بهترین انتخاب است که موارد ۱، ۳، ۵، ۶ و۷ را در بر میگیرد و هزینهای برابر ۹۷۵۰۰۰۰ دارد و سودی برابر ۱۶۱۷۵۰۰۰ برای شرکت فراهم میکند. مابقی حالات یا سود کمتری دارد یا هزینه بیشتری میطلبد.
مثال ۲
در بازی بیست سؤالی، بازیکن باید یک درخت تصمیم در ذهن خود بسازد که به خوبی موارد را از هم جدا کند تا با کمترین سؤال به جواب برسد. در صورتی بازیکن به جواب میرسد که درخت ساخته شده بتواند به خوبی موارد را از هم جدا کند.
جستارهای وابسته
منابع
- ↑ Piryonesi, S. M.; El-Diraby, T. E. (2020) [Published online: December 21, 2019]. "Data Analytics in Asset Management: Cost-Effective Prediction of the Pavement Condition Index". Journal of Infrastructure Systems. 26 (1). doi:10.1061/(ASCE)IS.1943-555X.0000512.
- ↑ Piryonesi, S. Madeh; El-Diraby, Tamer E. (2020-06). "Role of Data Analytics in Infrastructure Asset Management: Overcoming Data Size and Quality Problems". Journal of Transportation Engineering, Part B: Pavements. 146 (2): 04020022. doi:10.1061/jpeodx.0000175. ISSN 2573-5438.
- ↑ Hastie, Trevor. (2001). The elements of statistical learning : data mining, inference, and prediction : with 200 full-color illustrations. Tibshirani, Robert., Friedman, J. H. (Jerome H.). New York: Springer. ISBN 0-387-95284-5. OCLC 46809224.
- ↑ Ho, Tin Kam (1995). Random Decision Forests (PDF). Proceedings of the 3rd International Conference on Document Analysis and Recognition, Montreal, QC, 14–16 August 1995. pp. 278–282. Archived from the original (PDF) on 17 April 2016. Retrieved 5 June 2016.
- ↑ Ho, Tin Kam (1998). "The Random Subspace Method for Constructing Decision Forests" (PDF). IEEE Transactions on Pattern Analysis and Machine Intelligence. 20 (8): 832–844. doi:10.1109/34.709601. Archived from the original (PDF) on 4 March 2016. Retrieved 29 April 2019.
- ↑ Breiman, Leo (2001). "Random Forests". Machine Learning. 45 (1): 5–32. doi:10.1023/A:1010933404324.
- ↑ Breiman, Leo (2001). "Random Forests". Machine Learning (به انگلیسی). 45 (1): 5–32. doi:10.1023/a:1010933404324. ISSN 0885-6125.
- ↑ Shi, Tao; Seligson, David; Belldegrun, Arie S.; Palotie, Aarno; Horvath, Steve (2005-04). "Tumor classification by tissue microarray profiling: random forest clustering applied to renal cell carcinoma". Modern Pathology: An Official Journal of the United States and Canadian Academy of Pathology, Inc. 18 (4): 547–557. doi:10.1038/modpathol.3800322. ISSN 0893-3952. PMID 15529185.
- ↑ Messina, F. S. (1975-11). "Caesium ion: antagonism to chlorpromazine- and L-dopa- produced behavioural depression in mice". The Journal of Pharmacy and Pharmacology. 27 (11): 873–874. doi:10.1111/j.2042-7158.1975.tb10236.x. ISSN 0022-3573. PMID 1502.
- ↑ Rendić, S.; Kajfez, F.; Zamola, B.; Valles, P.; Mildner, P. (26 ژوئن 1975). "Study of the sporulation of Bacillus thuringiensis var. thuringiensis". Bollettino dell'Istituto Sieroterapico Milanese. 54 (2): 98–104. ISSN 0021-2547. PMID 1076.
- ↑ Piryonesi, Sayed Madeh (2019-11). "The Application of Data Analytics to Asset Management: Deterioration and Climate Change Adaptation in Ontario Roads" (به انگلیسی). ;
- ↑ Y. Yuan and M.J. Shaw, Induction of fuzzy decision trees بایگانیشده در ۱۰ فوریه ۲۰۰۹ توسط Wayback Machine. Fuzzy Sets and Systems ۶۹ (۱۹۹۵), pp. 125–139
منابع
- Sequential decision making with partially ordered preferences Daniel Kikuti, Fabio Gagliardi Cozman , Ricardo Shirota Filho
پیوند به بیرون
- Decision Tree Web Application
- 5 Myths About Decision Tree Analysis in Litigation
- Decision Tree Analysis mindtools.com
- Decision Analysis open course at George Mason University
- Extensive Decision Tree tutorials and examples بایگانیشده در ۳ فوریه ۲۰۱۵ توسط Wayback Machine
- Cha, Sung-Hyuk (2009). "A Genetic Algorithm for Constructing Compact Binary Decision Trees". Journal of Pattern Recognition Research. 4 (1): ۱–۱۳. Archived from the original on 23 May 2017. Retrieved 9 May 2017. ;
- Decision Trees in PMML