درخت تصمیم

مثال۱

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

مثال ۲

فرض کنید نمرات پارسال یک استاد به همکلاسی‌ها را داریم و می‌خواهیم قبول یا مردود شدن خود را تخمین بزنیم؛ بنابراین یک جدول می‌کشیم که در آن ویژگی‌هایی که همه همکلاسی‌ها دارند و برای ما مشخص هستند را فهرست می‌کنیم؛ ویژگی‌هایی مانند جنسیت، تأهل و اشتغال را می‌آوریم؛ بنابراین چنین نتیجه می‌شود:

• مؤنث => ۹۰ درصد قبول (برگ)
• مذکر => ۵۰ درصد مردود (تعیین‌کننده نیست (از لحاظ آماری همگن است)، پس تصمیم را می‌شکنیم)
• مذکر + اشتغال => ۶۰ درصد مردود (تقریباً همگن)
• مذکر + اشتغال + تأهل => ۸۵ درصد قبول (برگ)
• مذکر + اشتغال + مجرد => ۷۰ درصد مردود (برگ (چون ویژگی دیگری نداریم))

مثال ۳

در مجموعه داده گل زنبق، می‌خواهم نوع زنبقی را تخمین بزنم که بردار ویژگی آن x است؛ بنابراین در متلب:

clear all
load fisheriris ;% بارگیری مجموعه‌داده گل زنبق
iris_tree = fitctree(meas,species); % ایجاد درخت تصمیم
view(iris_tree,'mode','graph') % توضیح نمودار
x=[6 3 1.5 .3]; % زنبق من
disp(predict(iris_tree,x)) % نتیجه تصمیم

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

1. گره تصمیم: به‌طور معمول با مربع نشان داده می‌شود.
2. گره تصادفی: با دایره مشخص می‌شود.
3. گره پایانی: با مثلث مشخص می‌شود.

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

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

مجموع داده‌ها را با ${\displaystyle D}$

حال سؤال اینجاست که کدام بُعد از متغیرهای وابسته و چه آستانه‌ای را باید انتخاب کرد. به زبان ریاضی باید آن ${\displaystyle \theta }$

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

هدف در اینجا پیدا کردن آن ${\displaystyle \theta }$

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

اگر مسئله ما دسته‌بندی باشد و ${\displaystyle y_i\in [1,\cdots ,K]}$

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

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

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

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

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

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

${\displaystyle \begin{array}{r}\begin{array}{r}{\overline{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-{\overline{y}}_m{)}^2\end{array}\end{array}}$

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

${\displaystyle \begin{array}{r}\begin{array}{r}{\overline{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-{\overline{y}}_m|\end{array}\end{array}}$

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

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

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

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

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

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