FA
All
Articles
Dictionary
Quotes
Map

Wikiwand ❤️ Wikipedia

PrivacyTerms

درخت تصمیم

From Wikipedia, the free encyclopedia

درخت تصمیم
مثال‌هامثال۱مثال ۲مثال ۳کلیاتنمودار درخت تصمیم‌گیریالگوریتم ساخت درخت تصمیم‌گیریمسئله دسته‌بندیمسئله رگرسیونمزایامعایبجستارهای وابستهمنابع
برای درخت تصمیم به عنوان الگوریتم یادگیری ماشین به یادگیری درخت تصمیم رجوع نمائید.

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

Thumb
سابقا نمودارهای درختی به صورت دستنویس بودند.

مثال۱

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

مثال ۲

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

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

مثال ۳

در مجموعه داده گل زنبق، می‌خواهم نوع زنبقی را تخمین بزنم که بردار ویژگی آن 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. گره پایانی: با مثلث مشخص می‌شود.
Thumb

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

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

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

Q l e f t ( θ ) = { ( x i , y i ) ∈ Q | x i , j ≤ t m } Q r i g h t ( θ ) = { ( x i , y i ) ∈ Q | x i , j > t m } {\displaystyle {\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}}} {\displaystyle {\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}}}

حال سؤال اینجاست که کدام بُعد از متغیرهای وابسته و چه آستانه‌ای را باید انتخاب کرد. به زبان ریاضی باید آن θ {\displaystyle \theta } {\displaystyle \theta }یی را انتخاب کرد که ناخالصی داده را کم کند. ناخالصی برحسب نوع مسئله تعریفی متفاوت خواهد داشت، مثلاً اگر مسئله یک دسته‌بندی دوگانه است، ناخالصی می‌تواند آنتراپی داده باشد، کمترین ناخالصی زمانی است که هم Q r i g h t ( θ ) {\displaystyle Q_{right}(\theta )} {\displaystyle Q_{right}(\theta )} و هم Q l e f t ( θ ) {\displaystyle Q_{left}(\theta )} {\displaystyle Q_{left}(\theta )} از یک دسته داشته باشند، یعنی در هر کدام از این دو گِرِه دو نوع دسته وجود نداشته باشد. برای رگرسیون این ناخالصی می‌تواند واریانس متغیر وابسته باشد. از آنجا که مقدار داده در Q l e f t ( θ ) {\displaystyle Q_{left}(\theta )} {\displaystyle Q_{left}(\theta )} و Q r i g h t ( θ ) {\displaystyle Q_{right}(\theta )} {\displaystyle Q_{right}(\theta )} با هم متفاوت است، میانگینی وزن‌دار از هر دو ناخالصی را به شکل پایین محاسبه می‌کنیم.[2] در این معادله N m = | Q | {\displaystyle N_{m}=|Q|} {\displaystyle N_{m}=|Q|}، n l e f t = | Q l e f t ( θ ) | {\displaystyle n_{left}=|Q_{left}(\theta )|} {\displaystyle n_{left}=|Q_{left}(\theta )|} و n r i g h t = | Q r i g h t ( θ ) | {\displaystyle n_{right}=|Q_{right}(\theta )|} {\displaystyle n_{right}=|Q_{right}(\theta )|}:

G ( Q , θ ) = n l e f t N m H ( Q l e f t ( θ ) ) + n r i g h t N m H ( Q r i g h t ( θ ) ) {\displaystyle G(Q,\theta )={\frac {n_{left}}{N_{m}}}H(Q_{left}(\theta ))+{\frac {n_{right}}{N_{m}}}H(Q_{right}(\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 \theta } یی است که ناخالصی را کمینه کند، یعنی θ ∗ = argmin θ ⁡ G ( Q , θ ) {\displaystyle \theta ^{*}=\operatorname {argmin} _{\theta }G(Q,\theta )} {\displaystyle \theta ^{*}=\operatorname {argmin} _{\theta }G(Q,\theta )}. حال همین کار را به صورت بازگشتی برای Q l e f t ( θ ) {\displaystyle Q_{left}(\theta )} {\displaystyle Q_{left}(\theta )} و Q r i g h t ( θ ) {\displaystyle Q_{right}(\theta )} {\displaystyle Q_{right}(\theta )} انجام می‌دهیم. بعضی از گره‌ها را باید به برگ تبدیل کنیم. معیاری که برای تبدیل یک گره به برگ از آن استفاده می‌کنیم، می‌تواند مقداری حداقلی برای N m {\displaystyle N_{m}} {\displaystyle N_{m}} (تعداد داده در یک گره) یا عمق درخت باشد. به قسمی که اگر با دو نیم کردن گِره یکی از معیارها عوض شود، گِره را به دو نیم نکرده آن را تبدیل به یک برگ می‌کنیم. معمولاً این دو پارامتر باعث تنظیم مدل (Regularization) می‌شوند.[2] در ابتدای کار گره شامل تمام داده‌ها می‌شود یعنی Q = D {\displaystyle Q=D} {\displaystyle Q=D}.

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

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

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

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

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

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

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

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

y ¯ m = 1 N m ∑ i ∈ N m y i H ( Q ) = 1 N m ∑ i ∈ N m ( y i − y ¯ m ) 2 {\displaystyle {\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}}} {\displaystyle {\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}}}

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

y ¯ m = 1 N m ∑ i ∈ N m y i H ( Q ) = 1 N m ∑ i ∈ N m | y i − y ¯ m | {\displaystyle {\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}}} {\displaystyle {\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}}}

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

  1. فهم ساده: هر انسان با اندکی مطالعه و آموزش می‌تواند، طریقه کار با درخت تصمیم را بیاموزد.
  2. کار کردن با داده‌های بزرگ و پیچیده: درخت تصمیم در عین سادگی می‌تواند با داده‌های پیچیده به راحتی کار کند و از روی آن‌ها تصمیم بسازد.
  3. استفاده مجدد آسان: در صورتی که درخت تصمیم برای یک مسئله ساخته شد، نمونه‌های مختلف از آن مسئله را می‌توان با آن درخت تصمیم محاسبه کرد.
  4. قابلیت ترکیب با روش‌های دیگر: نتیجه درخت تصمیم را می‌توان با تکنیک‌های تصمیم‌سازی دیگر ترکیب کرده و نتایج بهتری بدست آورد.
  1. مشکل استفاده از درخت‌های تصمیم آن است که به صورت نمایی با بزرگ شدن مسئله بزرگ می‌شوند.
  2. اکثر درخت‌های تصمیم تنها از یک ویژگی برای شاخه زدن در گره‌ها استفاده می‌کنند در صورتی که ممکن است ویژگی‌ها دارای توزیع توأم باشند.
  3. ساخت درخت تصمیم در برنامه‌های داده کاوی، حافظه زیادی را مصرف می‌کند زیرا برای هر گره باید معیار کارایی برای ویژگی‌های مختلف را ذخیره کند تا بتواند بهترین ویژگی را انتخاب کند.
  • تقویت گرادیان
  • جدول تصمیم
  • پیچیدگی درخت تصمیم
  • آنالیز تصمیم
  • درخت
  • گراف تصمیم
  • شبکه تصمیم
  • زنجیره مارکف
  • دیاگرام تصمیم
  • آدابوست
  • Decision Tree Analysis mindtools.com
  • Decision Analysis open course at George Mason University
  • Extensive Decision Tree tutorials and examples
  1. [1]
    Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Second Edition. Springer Series in Statistics (به انگلیسی) (2 ed.). New York: Springer-Verlag.
  2. [2]
    Rokach، Lior؛ Maimon، Oded (۲۰۱۴). Data Mining With Decision Trees: Theory and Applications (ویراست ۲nd). River Edge, NJ, USA: World Scientific Publishing Co. , Inc. شابک ۹۷۸۹۸۱۴۵۹۰۰۷۵.
  3. [3]
    Krzywinski, Martin; Altman, Naomi (2017-07-28). "Points of Significance: Classification and regression trees". Nature Methods (به انگلیسی). Retrieved 2018-12-13.
Edit in WikipediaRevision historyRead in Wikipedia

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

Chrome
Wikiwand for Chrome
Edge
Wikiwand for Edge
Firefox
Wikiwand for Firefox

مثال‌ها

کلیات

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

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

مزایا

معایب

جستارهای وابسته

منابع