بخشی از پاورپوینت
اسلاید 2 :
Decision Tree
اسلاید 3 :
فهرست مطالب
مقدمه
درخت تصمیم
نمایش درخت تصمیم
معرفي درخت تصميم گيري و برخي تعاريف مورد نياز
الگوریتم های ساخت Decision Tree
يادگيری روش ID3 یا Iterative Dichotomiser 3
مثال بازی تنیس
معایب و مزایای درخت تصمیم گیری
کاربرد درخت هاي تصميم گيري
معرفی نرم افزار
اسلاید 4 :
مقدمه
ساختار درخت تصمیم در یادگیری ماشین، یک مدل پیش بینی کننده می باشد که حقایق مشاهده شده در مورد یک پدیده را به استنتاج هایی در مورد مقدار هدف آن پدیده نقش می کند. تکنیک یادگیری ماشین برای استنتاج یک درخت تصمیم از داده ها، یادگیری درخت تصمیم نامیده می شود که یکی از رایج ترین روش های داده کاوی است.
درختان تصمیم قادر به تولید توصیفات قابل درک برای انسان، از روابط موجود در یک مجموعه داده ای هستند و می توانند برای وظایف دسته بندی و پیش بینی بکار روند. این تکنیک به شکل گسترده ای در زمینه های مختلف همچون تشخیص بیماری ،دسته بندی گیاهان و استراتژی های بازاریابی مشتری بکار رفته است.
اسلاید 5 :
درخت تصمیم
درختها درهوش مصنوعی برای نمایش مفاهیم مختلفی نظیر ساختار جملات، معادلات، حالات بازی، و غیره استفاده میشود.
یادگیری درخت تصمیم روشی برای تقریب توابع هدف با مقادیر گسسته است. این روش نسبت به نویز داده هامقاوم بوده وقادر است ترکیب فصلی گزاره های عطفی را یاد بگیرد.
این روش جزو مشهورترین الگوریتمهای یادگیری استقرائی است که بصورت موفقیت آمیزی در کاربردهای مختلف بکار گرفته شده است.
اسلاید 6 :
نمایش درخت تصمیم
درخت تصمیم درختی است که در آن نمونه ها را به نحوی دسته بندی میکند که از ریشه به سمت پائین رشد میکنند و در نهایت به گره های برگ میرسد:
هر گره داخلی یاغیر برگ (non leaf) با یک ویژگی (attribute) مشخص میشود. این ویژگی سوالی را در رابطه با مثال ورودی مطرح میکند.
درهر گره داخلی به تعداد جوابهای ممکن با این سوال شاخه (branch) وجود دارد که هر یک با مقدار آن جواب مشخص میشوند.
برگهای این درخت با یک کلاس و یا یک دسته از جوابها مشخص میشوند.
علت نامگذاری آن به درخت تصمیم این است که این درخت فرایند تصمیم گیری برای تعیین دسته یک مثال ورودی را نشان میدهد.
اسلاید 7 :
معرفي درخت تصميم گيري و برخي تعاريف مورد نياز
ميانگين تعداد لايهها از ريشه تا گرههاي پاياني را عمق متوسط ميناميم.
ميانگين تعداد گرههاي مياني در هر سطح درخت عرض متوسط درخت ناميده ميشود.
اگر دو گره داخلي حداقل داراي يك كلاس مشترك باشند در اين حالت گفته ميشود كه كلاسها داراي روي هم افتادگي (Overlap) هستند.
اسلاید 8 :
معرفي درخت تصميم گيري و برخي تعاريف مورد نياز
نمايي از يك درخت تصميم گيري:
اسلاید 9 :
نحوه نمایش درخت تصمیم
ارتباط مستقیمی بین درخت تصمیم ونمایش توابع منطقی وجود دارد.درواقع هردرخت تصمیم ترکیب فصلی گزاره های عطفی است
مسیر از ریشه به برگ ترکیب عطفی (AND)از ویژگی ها را مشخص نموده و خوددرخت ترکیب فصلی(OR) این ترکیبات را میسازد.
اسلاید 11 :
الگوریتم های ساخت Decision Tree
الگوریتم ID3
1986 – Quinlan
بالا به پايين
پايه بسياري از الگوريتم هاي يادگيري درخت
جستجوي حريصانه اي را براي درخت تصميم گيري بهينه انجام مي دهد
الگوریتم C4.5
1993 – Quinlan
حاصل اعمال برخي بهبودها در الگوريتم ID3 (كار با داده هاي پيوسته، كار با ويژگي هاي بدون مقدار و . )
الگوریتم C5
الگوریتم Bagging
الگوریتم Boostering
اسلاید 12 :
روش ID3 (Iterative Dichotomiser 3)
در این الگوریتم درخت تصمیم از بالا به پائین ساخته میشود. این الگوریتم با این سوال شروع میشود: کدام ویژگی باید در ریشه درخت مورد آزمایش قرار گیرد؟
برای یافتن جواب از یک آزمون آماری استفاده میشود تا مشخص گردد هر کدام تا چه حد قادر است به تنهائی مثالهای آزمایشی را دسته بندی کند.
با انتخاب این ویژگی، برای هر یک از مقادیر ممکن آن یک شاخه ایجاد شده و مثالهای آموزشی بر اساس ویژگی هر شاخه مرتب میشوند. سپس عملیات فوق برای مثالهای قرار گرفته در هر شاخه تکرار میشوند تا بهترین ویژگی برای گره بعدی انتخاب شود.
این الگوریتم یک جستجوی حریصانه است که در آن انتخاب های قبلی هرگز مورد بازبینی قرار نمیگیرند.
اسلاید 14 :
آنتروپی(Entropy)
میزان خلوص (بی نظمی یا عدم خالص بودن) مجموعه ای از مثالها را مشخص می کند. اگر مجموعه S شامل مثالهای مثبت و منفی از یک مفهوم هدف باشد آنتروپی S نسبت به این دسته بندی بولی بصورت زیر تعریف می شود
P⊕ نسبت مثالهای مثبت در S و P⊝ درصد مثالهای منفی در آن است. در تمام محاسبات شامل بی نظمی 0log0 را صفر تعریف می کنیم
Entropy(S) ≡ - P⊕ log2 P⊕ - P⊝ log2 P⊝
مثال: فرض کنید S مجموعه ای از 14 مثال یک مفهوم بولی که حاوی 9 مثال مثبت و 5 مثال منفی است. [-5، +9]
بی نظمی S مربوط به این دسته بندی بولی از این قرار می باشد:
Entropy ([9+, 5-]) = -(9/14) log2 (9/14) - (5/14) log2 (5/14) = 0.940
اسلاید 15 :
بهره اطلاعات(Information Gain)
بهره اطلاعات یک ویژگی عبارت است از مقدار کاهش آنتروپی که بواسطه جداسازی مثالها از طریق این ویژگی حاصل میشود.
بعبارت دیگر بهره اطلاعات Gain(S,A) برای یک ویژگی نظیر A نسبت به مجموعه مثالهای S بصورت زیر تعریف میشود:
که در آن Values(A) مجموعه همه مقدار ویژگی های A بوده و SV زیرمجموعه ای از S است که برای آن A دارای مقدار V است.
در تعریف فوق عبارت اول مقدار آنتروپی داده ها و عبارت دوم مقدار آنتروپی مورد انتظار بعد از جداسازی داده هاست.
مثال: S مجموعه ای از روزهای مثال –آموزشی تشریح شده توسط صفات شامل Wind که مقادیر Weak و Strong دارد می باشد. S حاوی 14 مثال [9+,5-] است که در شش مثال مثبت و دو مثال منفی آن Wind=Weak و در بقیه Wind=Strong است. نفع اطلاعات مربوط به مرتب کردن 14 مثال ابتدایی بوسیلهء صفت Wind به شکل زیر محاسبه می شود
