بایگانی برچسب برای: Decision Tree

درخت تصمیم قسمت 2

آموزش عمومی پردازش تصویر و بینایی ماشین, آموزش های عمومی هوش مصنوعی

Decision Tree (درخت تصمیم) چیست؟

Decision Tree مفهومی است که اگر در نظر دارید تا تصمیم پیچیده‌ای بگیرید و یا می‌خواهید مسائل را برای خودتان به بخش‌های کوچک‌تری تقسیم کرده تا به شکل بهتری قادر به حل آن‌ها گردیده و ذهن‌تان را سازمان‌دهی کنید، می‌توانید از آن استفاده نمایید. در این پست قصد داریم تا همه چیز را در مورد درخت‌های تصمیم‌گیری مورد بررسی قرار دهیم؛ از جمله اینکه این مفهوم چه هست، چه‌طور مورد استفاده قرار می‌گیرد و همچنین چگونه می‌توانیم دست به ایجاد یک درخت تصمیم‌گیری بزنیم.

آشنایی با مفهوم Decision Tree (درخت تصمیم)

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

یک درخت تصمیم‌گیری به طور معمول با یک نُود اولیه‌ شروع می‌شود که پس از آن پیامد‌های احتمالی به صورت شاخه‌هایی از آن منشعب شده و هر کدام از آن پیامد‌ها به نُود‌های دیگری منجر شده که آن‌ها هم به نوبهٔ خود شاخه‌هایی از احتمالات دیگر را ایجاد می‌کنند که این ساختار شاخه‌شاخه سرانجام به نموداری شبیه به یک درخت مبدل می‌شود. در درخت تصمیم‌گیری سه نوع Node (گِره) مختلف وجود دارد که عبارتند از:

– نُود‌های تصادفی – نُود‌های تصمیم‌گیری – نُود‌های پایانی

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

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

چه‌طور می توان اقدام به کشیدن یک Decision Tree کرد؟

به منظور ترسیم یک درخت تصمیم، ابتدا وسیله و ابزار مورد نظرتان را انتخاب کنید (می‌توانید آن را با قلم و کاغذ یا وایت‌برد کشیده یا اینکه می‌توانید از نرم‌افزار‌های مرتبط با این کار استفاده کنید.) فارغ از اینکه چه ابزاری انتخاب می‌کنید، می‌بایست به منظور ترسیم یک درخت تصمیم اصولی، مراحل زیر را دنبال نمایید:

۱- کار با تصمیم اصلی آغاز کنید که برای این منظور از یک باکس یا مستطیل کوچک استفاده کرده، سپس از آن مستطیل به ازای هر راه‌حل یا اقدام احتمالی خطی به سمت راست/چپ کشیده و مشخص کنید که هر خط چه معنایی دارد.

۲- نُود‌‌های تصادفی و تصمیم‌گیری را به منظور شاخ و برگ دادن به این درخت، به طریق پایین رسم کنید:

ـ اگر تصمیم اصلی دیگری وجود دارد، مستطیل دیگری رسم کنید. ـ اگر پیامدی قطعی نیست، یک دایره رسم کنید (دایره‌ها نمایانگر نُود‌های تصادفی هستند.) ـ اگر مشکل حل شده، آن را فعلاً خالی بگذارید.

از هر نُود تصمیم‌گیری، راه‌های احتمالی را منشعب کنید به طوری که برای هر کدام از نُود‌های تصادفی، خطوطی کشیده و به وسیله‌ٔ آن خطوط پیامد‌های احتمالی را نشان دهید و اگر قصد دارید گزینه‌های پیش‌ روی خود را به صورت عددی و درصدی آنالیز کنید، احتمال وقوع هر کدام از پیشامد‌ها را نیز یادداشت کنید.

۳- به بسط این درخت ادامه دهید تا زمانی که هر خط به نقطه‌ٔ پایانی برسد (یعنی تا جایی که انتخاب‌های دیگری وجود نداشته و پیامد‌های احتمالی دیگری برای در نظر گرفتن وجود نداشته باشد.) در ادامه، برای هر پیشامد احتمالی یک مقدار تعیین کنید که این مقدار می‌تواند یک نمرهٔ فرضی یا یک مقدار واقعی باشد. همچنین به خاطر داشته باشید که برای نشان دادن نقاط پایانی، از مثلث استفاده کنید.

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

مثالی از پروسهٔ تجزیه و تحلیل Decision Tree با محاسبهٔ سود یا مقدار مورد انتظار از هر انتخاب در درخت مد نظر خود، می‌توانید ریسک را به حداقل رسانده و احتمال دستیابی به یک پیامد یا نتیجهٔ مطلوب و مورد انتظار را بالا ببرید. به منظور محاسبهٔ سود مورد انتظار یک گزینه، تنها کافی است هزینهٔ تصمیم را از مزایای مورد انتظار آن کسر کنید (مزایای مورد انتظار برابر با مقدار کلی تمام پیامد‌هایی است که می‌توانند از یک انتخاب ناشی شوند که در چنین شرایطی هر مقدار در احتمال پیشامد ضرب شده است.) برای مثالی که در تصاویر بالا زده‌ایم، بدین صورت این مقادیر را محاسبه خواهیم کرد:

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

هنگامی که از درخت تصمیم‌تان به همراه یک مدل احتمالی استفاده می‌کنید، می‌توانید از ترکیب این دو برای محاسبهٔ احتمال شرطی یک رویداد، یا احتمال پیشامد آن اتفاق با در نظر گرفتن رخ دادن دیگر اتفاقات استفاده کنید که برای این منظور، همان‌طور که در تصویر فوق مشاهده می‌شود، کافی است تا از رویداد اولیه شروع کرده، سپس مسیر را از آن رویداد تا رویداد هدف دنبال کنید و در طی مسیر احتمال هر کدام از آن رویداد‌ها را در یکدیگر ضرب نمایید که بدین ترتیب می‌توان از یک درخت تصمیم به شکل یک نمودار درختی سنتی بهره برد که نشانگر احتمال رخداد رویداد‌های خاص (مثل دو بار بالا انداختن یک سکه) می‌باشد.

آشنایی با برخی مزایا و معایب Decision Tree

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

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

کاربرد Decision Tree در حوزه‌ٔ ماشین لرنینگ و دیتا ماینینگ

از درخت تصمیم می‌توان به منظور ایجاد مُدل‌های پیش‌بینی خودکار استفاده کرد که در حوزه‌ٔ یادگیری ماشینی، استخراج داده و آمار کاربردی هستند. این روش که تحت عنوان Decision Tree Learning شناخته می‌شود، به بررسی مشاهدات در مورد یک آیتم به جهت پیش‌بینی مقدارش می‌پردازد و به طور کلی، در چنین درخت تصمیمی، نُود‌ها نشان‌دهنده‌ٔ دیتا هستند نَه تصمیمات. این نوع درخت‌ها همچنین تحت عنوان Classification Tree نیز شناخته می‌شوند به طوری که هر شاخه در برگیرنده‌ٔ مجموعه‌ای از ویژگی‌ها یا قوانین طبقه‌بندی دیتا است و مرتبط با یک دستهٔ خاص می‌باشد که در انتهای هر شاخه یافت می‌شود.

این دست قوانین که تحت عنوان Decision Rules شناخته می‌شوند قابل بیان به صورت جملات شرطی می‌باشند (مثلاً اگر شرایط ۱ و ۲ و ۳ محقق شوند، با قطعیت می‌توان گفت که X نتیجه‌ای همچون Y برخواهد گرداند.) هر مقدار دادهٔ اضافی به مدل کمک می‌کند تا دقیق‌تر پیش‌بینی کند که مسئلهٔ مورد نظر به کدام مجموعه از مقادیر متعلق می‌باشد و این در حالی است که از این اطلاعات بعداً می‌توان به عنوان ورودی در یک مدل تصمیم‌گیری بزرگ‌تر استفاده کرد.

درخت‌های تصمیم‌گیری که پیامد‌های محتمل پی‌درپی و بی‌نهایت دارند، Regression Tree نامیده می‌شوند. به طور کلی، متدهای کاربردی در این حوزه به صورت زیر دسته‌بندی می‌شوند:

– Bagging: در این متد با نمونه‌سازی مجدد دیتای سورس، چندین درخت ایجاد شده سپس با برداشتی که از آن درختان می‌شود، تصمیم نهایی گرفته شده یا نتیجهٔ‌ نهایی به دست می‌آید.

– Random Forest: در این متد طبقه‌بندی از چندین درخت تشکیل شده که به منظور افزایش نرخ کلاسیفیکیشن طراحی شده‌اند.

– Boosted: درخت‌هایی از این جنس می‌توانند برای رگرسیون مورد استفاده قرار گیرند.

– Rotation Forest: در این متد، همگی درخت‌ها توسط یک به اصطلاح Principal Component Analysis با استفاده از بخشی از داده‌های تصادفی آموزش داده می‌شوند.

درخت تصمیم‌گیری زمانی مطلوب تلقی می‌شود که نشان‌دهنده‌ٔ بیشترین دیتا با حداقل شاخه باشد و این در حالی است که الگوریتم‌هایی که برای ایجاد درخت‌های تصمیم‌گیری مطلوب طراحی شده‌اند شامل CART ،ASSISTANT ،CLS و ID31415 می‌شوند. در واقع، هر کدام از این متد‌ها باید تعیین کنند که بهترین راه برای تقسیم داده در هر شاخه کدام است که از متد‌های رایجی که بدین منظور استفاده می‌شوند می‌توان به موارد زیر اشاره کرد:

– Gini Impurity – Information Gain – Variance Reduction

استفاده از درخت‌های تصمیم‌گیری در یادگیری ماشینی چندین مزیت عمده دارد من‌جمله هزینه یا بهای استفاده از درخت به منظور پیش‌بینی داده با اضافه کردن هر به اصطلاح Data Point کاهش می‌یابد و این در حالی است که از جمله دیگر مزایایش می‌توان به موارد زیر اشاره کرد:

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

اما Decision Tree در ML معایبی نیز دارا است که از جملهٔ مهم‌ترین آن‌ها می‌توان به موارد زیر اشاره کرد:

– حین مواجه با داده‌های طبقه‌بندی شده با سطوح مختلف، داده‌های حاصله تحت‌تأثیر ویژگی‌ها یا صفاتی که بیشترین شاخه را دارند قرار می‌گیرد. – در صورت رویارویی با پیامد‌های نامطمئن و تعداد زیادی پیامد بهم مرتبط، محاسبات ممکن است خیلی پیچیده شود. – ارتباطات بین نُود‌ها محدود به AND بوده حال آنکه یک Decision Graph این اجازه را به ما می‌دهند تا نُود‌هایی داشته باشیم که با OR به یکدیگر متصل شده‌اند.

سپتامبر 8, 2019/0 دیدگاه /توسط daliri

درخت تصمیم قسمت 1

آموزش عمومی پردازش تصویر و بینایی ماشین, آموزش های عمومی هوش مصنوعی

درخت تصمیم گیری (Decision Tree) یک ابزار برای پشتیبانی از تصمیم است که از درخت‌ها برای مدل کردن استفاده می‌کند. درخت تصمیم به‌طور معمول در تحقیق‌ها و عملیات مختلف استفاده می‌شود. به‌طور خاص در آنالیز تصمیم، برای مشخص کردن استراتژی که با بیشترین احتمال به هدف برسد بکار می‌رود. استفاده دیگر درختان تصمیم، توصیف محاسبات احتمال شرطی است.

کلیات

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

۱-گره تصمیم: به‌طور معمول با مربع نشان داده می‌شود.

۲-گره تصادفی: با دایره مشخص می‌شود.

۳-گره پایانی: با مثلث مشخص می‌شود.

Manual decision tree — Traditionally, decision trees have been created manually

نمودار درخت تصمیم گیری

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

مکان‌های مورد استفاده

درخت تصمیم، دیاگرام تصمیم و ابزارها و روش‌های دیگر مربوط به آنالیز تصمیم به دانشجویان دوره لیسانس در مدارس تجاری و اقتصادی و سلامت عمومی و تحقیق در عملیات و علوم مدیریت، آموخته می‌شود.

یکی دیگر از موارد استفاده از درخت تصمیم، در علم داده‌کاوی برای classification است.

الگوریتم ساخت درخت تصمیم‌گیری

مجموع داده‌ها را با $D$ نمایش می‌دهیم، یعنی $D=(x_{1},y_{1}),\cdots ,(x_{i},y_{i}),\cdots ,(x_{n},y_{n})$ ، به قسمی که $x_{i}\in R^{d}$ و $y_{i}\in R$ . درخت تصمیم‌گیری سعی میکند بصورت بازگشتی داده‌ها را به قسمی از هم جدا کند که در هر گِرِه متغیرهای مستقلِ $y$ به هم نزدیک شده همسان شوند. هر گِره زیر مجموعه ای از داده هاست که بصورت بازگشتی ساخته شده است. به طور دقیقتر در گره $m$ اگر داده ما $Q$ باشد سعی میکنیم یک بُعد از متغیرهایی وابسته را به همراه یک آستانه انتخاب کنیم و داده‌ها را برحسب این بُعد و آستانه به دو نیم تقسیم کنیم، به قسمی که بطور متوسط در هر دو نیم متغیرهای مستقل یا $y$ خیلی به هم نزدیک و همسان شده باشند. این بعد و آستانه را $\theta =(j,t_{m})$ می‌نامیم. دامنه $j$ برابر است با $[1,\cdots ,d]$ و $t_{m}$ یک عدد صحیح است. $Q$ برحسب $\theta =(j,t_{m})$ به دو بخش $Q_{left}(\theta )$ و $Q_{right}(\theta )$ به شکل پایین تقسیم می شود:

${\begin{aligned}Q_{left}(\theta )=&\{(x_{i},y_{i})\in Q\,|\,x_{i,j}\leq t_{m}\}\\Q_{right}(\theta )=&\{(x_{i},y_{i})\in Q\,|\,x_{i,j}>t_{m}\}\\\end{aligned}}$

حال سؤال اینجاست که کدام بُعد از متغیرهای وابسته و چه آستانه‌ای را باید انتخاب کرد. به زبان ریاضی باید آن $\theta$ یی را انتخاب کرد که ناخالصی داده را کم کند. ناخالصی برحسب نوع مسئله تعریفی متفاوت خواهد داشت، مثلا اگر مسئله یک دسته‌بندی دوگانه است، ناخالصی می‌تواند آنتراپی داده باشد، کمترین ناخالصی زمانی است که هم $Q_{right}(\theta )$ و هم $Q_{left}(\theta )$ از یک دسته داشته باشند، یعنی در هر کدام از این دو گِرِه دو نوع دسته وجود نداشته باشد. برای رگرسیون این ناخالصی می تواند واریانس متغیر وابسته باشد. از آنجا که مقدار داده در $Q_{left}(\theta )$ و $Q_{right}(\theta )$ با هم متفاوت است میانگینی وزن‌دار از هر دو ناخالصی را به شکل پایین محاسبه می‌کنیم. در این معادله $N_{m}=|Q|$ ، $n_{left}=|Q_{left}(\theta )|$ و $n_{right}=|Q_{right}(\theta )|$ :

$G(Q,\theta )={\frac {n_{left}}{N_{m}}}H(Q_{left}(\theta ))+{\frac {n_{right}}{N_{m}}}H(Q_{right}(\theta ))$

هدف در اینجا پیدا کردن آن $\theta$ یی است که ناخالصی را کمینه کند، یعنی $\theta ^{*}=\operatorname {argmin} _{\theta }G(Q,\theta )$ . حال همین کار را بصورت بازگشتی برای $Q_{left}(\theta )$ و $Q_{right}(\theta )$ انجام می‌دهیم. بعضی از گره ها را باید به برگ تبدیل کنیم، معیاری که برای تبدیل یک گره به برگ از آن استفاده می‌کنیم می‌تواند مقداری حداقلی برای $N_{m}$ (تعداد داده در یک گره) و یا عمق درخت باشد به قسمی که اگر با دو نیم کردن گِره یکی از معیارها عوض شود، گِره را به دو نیم نکرده آنرا تبدیل به یک برگ میکنیم. معمولا این دو پارامتر باعث تنظیم مدل (Regularization) می‌شوند. در ابتدای کار گره شامل تمام داده‌ها می‌شود یعنی $Q=D$ .

مسئله دسته‌بندی

اگر مسئله ما دسته‌بندی باشد و $y_{i}\in [1,\cdots ,K]$ باشد تابع ناخالصی برای گره $Q$ میتواند یکی از موارد پایین باشد، در این معادله‌ها $p_{mk}=1/N_{m}\sum _{(x_{i},y_{i})\in Q}I(y_{i}=k)$

ناخالصی گینی: $H(Q)=\sum _{k}p_{mk}(1-p_{mk})$

ناخالصی آنتروپی: $H(Q)=-\sum _{k}p_{mk}\log(p_{mk})$

ناخالصی خطا: $H(Q)=1-\max(p_{mk})$

مسئله رگرسیون

در مسئله رگرسیون ناخالصی می‌تواند یکی از موارد پایین باشد:

میانگین خطای مربعات:

${\begin{aligned}{\begin{aligned}{\bar {y}}_{m}={\frac {1}{N_{m}}}\sum _{i\in N_{m}}y_{i}\\H(Q)={\frac {1}{N_{m}}}\sum _{i\in N_{m}}(y_{i}-{\bar {y}}_{m})^{2}\end{aligned}}\end{aligned}}$

میانگین خطای قدر مطلق:

${\begin{aligned}{\begin{aligned}{\bar {y}}_{m}={\frac {1}{N_{m}}}\sum _{i\in N_{m}}y_{i}\\H(Q)={\frac {1}{N_{m}}}\sum _{i\in N_{m}}|y_{i}-{\bar {y}}_{m}|\end{aligned}}\end{aligned}}$

مزایا

در میان ابزارهای پشتیبانی تصمیم، درخت تصمیم و دیاگرام تصمیم دارای مزایای زیر هستند:

۱- فهم ساده: هر انسان با اندکی مطالعه و آموزش می‌تواند، طریقه کار با درخت تصمیم را بیاموزد.

۲- کار کردن با داده‌های بزرگ و پیچیده: درخت تصمیم در عین سادگی می‌تواند با داده‌های پیچیده به راحتی کار کند و از روی آن‌ها تصمیم بسازد.

۳-استفاده مجدد آسان: در صورتی که درخت تصمیم برای یک مسئله ساخته شد، نمونه‌های مختلف از آن مسئله را می‌توان با آن درخت تصمیم محاسبه کرد.

۴- قابلیت ترکیب با روش‌های دیگر: نتیجه درخت تصمیم را می‌توان با تکنیک‌های تصمیم‌سازی دیگر ترکیب کرده و نتایج بهتری بدست آورد.

معایب

۱- مشکل استفاده از درخت‌های تصمیم آن است که به صورت نمایی با بزرگ شدن مسئله بزرگ می‌شوند. ۲- اکثر درخت‌های تصمیم تنها از یک ویژگی برای شاخه زدن در گره‌ها استفاده می‌کنند در صورتی که ممکن است ویژگی‌ها دارای توزیع توأم باشند. ۳- ساخت درخت تصمیم در برنامه‌های داده کاوی حافظه زیادی را مصرف می‌کند زیرا برای هر گره باید معیار کارایی برای ویژگی‌های مختلف را ذخیره کند تا بتواند بهترین ویژگی را انتخاب کند.

سپتامبر 7, 2019/0 دیدگاه /توسط daliri