درخت‌های تصمیم
اسلاید 1: درخت های تصمیم
اسلاید 2: درخت های تصميم درخت‌هاي تصميم ابزار قدرتمند و درعين حال رايجي هم براي دسته بندی و هم برای پيش‌بيني هستند. جذابيت روش‌هاي درخت مبنا بيش از هرچيز به اين واقعيت برمي‌گردد كه درخت‌هاي تصميم نمايانگر قوانين مي‌باشند. به راحتي مي‌توان قوانین را به زبان فارسی و یا هر زبان دیگری در آورد تا براي همگان قابل فهم باشند. همچنین مي‌توان آنها را به زبان قابل دسترسی پایگاه داده ها مانند SQL درآورد و مثلا اطلاعات يك گروه خاص را استخراج نمود.درخت تصميم براي بررسي داده ها برای کسب بينش بهتر درباره روابط موجود بين تعداد زيادي از متغیرهای ورودي کاندیدا شده برای یک متغیر هدف نيز مفيد مي‌باشد. ازآنجايي كه درخت تصميم بررسي داده و مدلسازي را باهم تركيب مي‌كند، گام اوليه قدرتمندي در فرآيند مدلسازي به شمار می روند حتی هنگامی که برای تهیه مدل نهايي از برخي تکنیکهای دیگر استفاده شود.
اسلاید 3: معمولاً بين صحت مدل و شفافيت مدل توازن وجود دارد. دربرخي كاربردها، صحت دسته بندی يا پيش‌بيني تنها مسئله مهم است، اگر مثلاً يك شركت پست مستقیم مدلي را دراختيار داشته باشد که با استفاده از آن بتوان به درستی پيش‌بيني کرد که کدامیک از مشتریان بالقوه احتمالاً به پیشنهاد عرضه شده پاسخ خواهند داد، آنگاه شايد براي اين شركت اهميتي نداشته باشد چرا و چگونه مدل پيش‌بيني‌كننده عمل مي‌كند. درساير شرايط، توانايي بیان علت يك تصمیم حیاتی است. براي مثال، در غرامت‌هاي بیمه، برخي ممانعت‌هاي قانوني دربرابر تبعيضها براساس متغیرهای خاصی وجود دارد. شايد يك شركت بيمه در وضعيتي قرار بگيرد كه مجبور شود به دادگاه ثابت كند هيچگونه تبعيض غيرقانوني در دادن یا ندادن خسارت به افراد مرتكب نشده است. همچنين بیشتر اين پذیرفته شده است كه وام دهنده و وام گیرنده بدانند كه بر اساس سيستم رايانه‌اي با اعطاي وام موافقت نشده است (مثلاً درمواردي كه محاسبات رايانه‌اي نشان دهد درآمد ماهيانه متقاضي كمتر از سطح لازم است یا آنکه ظرفيت وام گيرندگان پرشده است) تا اينكه بفهمند تصميم‌گيري درباره عدم اعطاي وام توسط يك شبكه عصبي هوشمند بدون هيچگونه توضیحی در مورد عملکردش صورت گرفته است.
اسلاید 4: درخت تصميم چيست ؟ درخت تصميم‌گيري ساختاري است كه براي تقسيم مجموعه‌اي بزرگ از داده های جمع‌آوري شده به مجموعه‌هاي كوچكتر زنجيره‌وار داده ها بواسطه يك سري قوانين ساده تصميم‌گيري به كار مي‌رود. در هر تقسيم‌بندي متوالي، اعضاي مجموعه های حاصل بيش از پيش به همدیگر مشابه می شوند. تقسيم‌بندي موجودات زنده براساس قلمروها، سلسله مراتب پيدايش، دسته ها، نظام تولد، خانواده، جنسيت و گونه ها كه در دهه 1730 توسط گياه‌شناس سوئدي كارل لينوس ابداع شد نمونه خوبي دراين زمينه است. در قلمروي حیوانات چنانچه موجود زنده‌اي داراي ستون فقرات باشد جزو دسته مهره داران قرار مي‌گيرد. از ديگر ويژگي‌هاي مهره داران براي تقسيم‌بندي آنها به پرندگان، پستانداران، خزندگان و غيره استفاده مي‌شود. اين دسته بندی آنقدر ادامه مي‌يابد تا در پايين‌ترين رده‌بندي، اعضای يك گونه هم ازنظر شکل شناسی و هم توانايي زاد و ولد و پرورش بچه های خود بهم شبيه باشند.
اسلاید 5: يك مدل درخت تصميم‌گيري از مجموعه ای از قوانين براي تقسيم جمعيت ناهمگن وسيعي به گروه‌هاي كوچكتر و همگن تر با توجه به يك متغیر هدف خاص تشکیل شده است. شايد تهیه درخت تصميم‌گيري مشابه مدل كارل لينوس كه به صورت دستي آماده شده طاقت فرسا باشد و شايد اين كار به طور خودكار با اعمال برخي الگوريتم‌هاي درخت تصميم‌گيري دريك مجموعه مدل حاوي داده‌هاي از قبل دسته بندی شده انجام شود. معمولاً متغیر هدف، دسته ای است و از مدل درخت تصميم‌گيري استفاده می شود تا احتمال تخصیص داده های موجود به هر کدام از دسته ها محاسبه شود یا برای دسته بندی داده ها با تخصیص آن به محتمل ترین دسته به کاررود. همچنين مي‌توان از درخت‌هاي تصميم‌گيري براي برآورد مقدار متغیرهای پیوسته استفاده كرد هرچند كه تکنیک های مناسبتری نيز براي انجام اين كار وجود دارد. درخت تصميم چيست ؟
اسلاید 6: دسته بندی آنهايي كه با بازي بيست سؤالي آشناهستند خوب مي‌دانند چگونه يك درخت تصميم، داده‌ها را دسته بندی مي‌كند. دراين بازي یک بازيكن، مكان ، شخص، يا شيئی خاص را كه براي ديگر شركت‌كنندگان آشنا است درنظر مي‌گيرد ولي وي سرنخی به ديگران در این رابطه نمي‌دهد. بقيه بازیكنان سعي مي‌كنند با طرح يك سري سؤالات و گرفتن پاسخ بله يا خير آن را حدس بزنند. يك بازيكن خوب به ندرت نياز به پرسيدن همه بيست سوال مجاز در بازي دارد تا از اولين سؤال خود که درجيب جا مي‌شود؟ به پاسخ اصلي برج میلاد برسد.يك درخت تصميم نیز یک سری و زنجيره از این سوالات را مطرح می کند. همچون بازي بيست سؤالي، پاسخ به اولين سؤال تعيين كننده سوال بعدي است. سؤالات اوليه به ایجاد گروههای بسیار گسترده ای با اعضای فراوان کمک می کند و سؤالات بعدی اين گروههای گسترده را به مجموعه‌هاي کوچکتر و كوچكتری محدود مي‌كند. اگر سؤالات به خوبی انتخاب شوند آنگاه با یک سری محدود از سئوالات می توان به دسته بندی صحیح داده های ورودی پرداخت.
اسلاید 7: بازي بيست سؤالي نشان دهنده فرآيند استفاده از یک درخت براي گنجاندن امتیاز یا دسته ای در داده ها است. يك سابقه اطلاعاتي در گره ريشه قرار مي‌گيرد. دراينجا براي تعيين اينكه بعداً اطلاعات درج شده به كدام ريشه نونهال پيوند مي‌خورد يك آزمايش صورت مي‌گيرد. الگوريتم‌هاي گوناگوني براي انتخاب آزمايش اوليه وجود دارد اما هدف همه آنها يكي است و آن چیزی نیست جز انتخاب آزمايشي كه بتواند بين دسته های هدف بهترين تمايز را قايل شود. اين فرآيند آنقدر تكرار مي‌شود تا يك سابقه اطلاعاتي به يك گره برگ برسد. تمام اطلاعاتی كه به یک برگ در درخت تبدیل مي‌شوند به طريقي مشابه دسته بندی مي‌شوند و يك مسيرمنحصر به فرد از ريشه به برگ وجود خواهد داشت. چنين مسيري نشانگر یک قانون به كاررفته در دسته بندی سوابق اطلاعاتي است. شاید برگ‌هاي گوناگون دارای دسته بندی های مشابهي باشند هرچند كه هر برگ به علت متفاوتي دسته بندی را انجام می دهد. به عنوان مثال درختي كه ميوه جات و سبزيجات را براساس رنگ آن میوه یا سبزی دسته بندی می کند، برگ درخت تصمیم سیب و گوجه فرنگي و گيلاس می تواند رنگ قرمز را پیش بینی کند هر چند احتیاطهایی را هم باید در نظر داشت چراكه سيب‌هاي سبز، گوجه فرنگي‌هاي زرد و گيلاس‌هاي سياه رنگ هم وجود دارد. دسته بندی
اسلاید 8: درخت تصميم‌گيري موجود در شكل 1-6 فهرست گیرندگان احتمالی يك كاتالوگ خريد كالا را به صورت محتمل (1) و غیر محتمل (2) برای سفارش دادن پس از فرستادن کاتالوگ جدید دسته بندی می کند.اين درخت براساس قواعد رايج در چرخه های داده كاوي تنظيم شده است بطوري كه ريشه‌ها در بالا و برگ‌ها در پايين واقع شده اند. درسمت راست فوقاني هر گره یک شماره قراردارد و دسته پيش بيني شده هركدام درمركز درج شده است. قوانين تصميم‌گيري براي تقسيم هر گره روي خطوطي كه هر گره را به نونهالان خود وصل مي‌كند چاپ شده است. تقسيم در گره ريشه‌اي که سفارشات مادام العمر نام دارد صورت گرفته است و شاخه سمت چپ به مشترياني اختصاص یافته که شش سفارش یا کمتر داشته اند و شاخه سمت راست به مشتریانی با 7 سفارش و بيشتر تعلق گرفته است.هر داده ای كه به گره‌ها ي برگي 19 ، 14 ، 16 ، 17 يا 18 برسد با عنوان متحمل به پاسخگویی دسته بندی می شود چرا که دسته پيش‌بيني شده دراين مورد یک است. مسيرهاي منتهي به اين گره‌هاي برگي قوانين درخت را بیان می کنند. به عنوان مثال، قانون مربوط به برگ 19 از این قرار است: اگر مشتري بيش از 5/6 سفارش داشته باشد و كمتر از 765 روز از آخرين سفارش وی بگذرد، احتمالا به کاتالوگ پاسخ خواهد داد.
اسلاید 9: شايد خوانندگان هوشيار متوجه شوند كه برخي تقسيم‌هاي درخت تصميم در ظاهر تغییري نمی کنند. مثلاً گره‌هاي 17 و 18 براساس تعداد سفارشاتي كه شامل سفارشاتي از دسته خوراكي‌ها است متمايز شده اند. اما هر دو گره به عنوان پاسخ دهنده تعیین شده اند. علت این مسئله آن است كه گذشته از بالاتر بودن احتمال پاسخ در گره 18 نسبت به گره 17، احتمال پاسخ در هر دو مورد بيش از حدي است كه براي طبقه‌بندي يك سابقه اطلاعاتي به عنوان پاسخ دهنده تعيين شده است. اين مدل به عنوان یک دسته بندی کننده فقط دو خروجي صفر و يك دارد. اين دسته بندی دوگانه، اطلاعات سودمندي را نادیده می گیرد كه مبحث جديد ما درباره استفاده از درخت‌هاي تصميم برای تهيه امتیازات و احتمالات است.
اسلاید 10: امتيازدهي شكل 2-6 تصويري از همان درخت تصميم‌گيري شكل 1-6 است كه از يك آرايه درختي ديگر با وضعيت اصلاح شده استفاده شده است به طوريكه اينك درخت با اطلاعات بيشتر يعني درصد اطلاعات در دسته یک در هر گره حاشيه نويسي شده است. حال به وضوح مي‌توان ديد كه اين درخت يك پايگاه اطلاعاتي حاوي نيمي‌از پاسخ دهنده ها و نيمي‌از غیر پاسخ دهنده ها را نشان مي‌دهد چرا كه گره ريشه‌اي داراي نسبت 50 درصد است. اين وضعيت دريك مجموعه آموزشي براي يك مدل پاسخگویی با متغیر هدف دوگانه رايج است. در شكل 1-6 هر گره با بيش از 50 درصد پاسخ دهنده ها با عدد یک نشان داده شده است كه شامل گره‌هاي 17 و 18 نيز مي‌شود. شكل 2-6 تفاوت بين اين گره‌ها را روشن مي‌سازد. در گره 17 به ميزان 8/52 درصد سوابق اطلاعاتي نمايانگر واكنش است حال آنكه در گره 18 اين رقم به 9/66 درصد مي‌رسد. معلوم است كه يك سابقه اطلاعاتي در گره 18 بيشتر مي‌تواند نمايانگر يك پاسخ دهنده باشد تا يك سابقه داده در گره 17. از نسبت اطلاعات در دسته دلخواه مي‌توان به عنوان يك امتياز استفاده کرد كه اغلب از دسته بندی صرف مفيدتر است. براي يك نتیجه دوگانه، دسته بندی فقط مي‌تواند داده ها را به دو گروه تقسيم كند ولی يك امتياز به داده ها امکان مي‌دهد تا اطلاعات را از محتمل ترین تا کم احتمال ترین افراد برای عضویت در دسته دلخواه مرتب کرد.
اسلاید 11: دربسياري از كاربردها به دست آوردن يك امتياز كه قادر به رتبه بندي يك فهرست باشد كافي خواهد بود. اين دستاورد نيز براي انتخاب بالاترين درصد N براي ارسال کاتالوگ پستي و براي محاسبه صعود در ابعاد گوناگون فهرست كفايت خواهد كرد. اما در برخي كاربردها، علم به اينكه احتمال پاسخگویی A از B بيشتر است كافي نخواهد بود. ما می خواهیم درباره احتمال پاسخ گویی توسط A بیشتر بدانیم. با فرض اينكه احتمالت قبلي يك پاسخ را بدانيم آنگاه با آن مي‌توانيم احتمال واکنش ناشي از امتياز به دست آمده از داده‌هایی را که براي تهیه درخت تصميم‌گيري نمونه گیری شده اند محاسبه کنیم. يا اينكه مي‌توانيم مدل را برای داده‌هاي از پيش دسته بندی شده‌اي كه داراي توزيع پاسخ ها و منعكس‌كننده آمار واقعي جمعيت است بكار ببریم. اين روش با استفاده از نسبتهای دسته ها، در برگ‌هاي درخت امتیازاتی را ايجاد مي‌كند كه این احتمال را نشان می دهد که اطلاعات استخراج شده از يك جمعیت مشابه، عضو دسته مزبور باشد. امتيازدهي
اسلاید 12: تخمین فرض كنيد كه يك سؤال مهم تجاری به جاي آنكه عبارت: چه کسی پاسخ خواهد داد؟ عبارت: مقدار سفارش بعدي مشتري چقدر خواهد بود؟ باشد. با استفاده از درخت تصميم‌گيري مي‌توان به اين سؤال نيز پاسخ داد. فرض كنيد مقدار سفارش يكي از متغیرهای موجود در مجموعه مدل از پيش دسته بندی شده باشد آنگاه مقدار ميانگين سفارش درهر برگ را مي‌توان به عنوان مقدار سفارش تخمین زده شده براي هرگونه سابقه اطلاعاتي دسته بندی نشده‌اي به کار برد که معيارهاي آن برگ را رعایت کند. حتي اين امكان وجود دارد كه از يك متغیر هدفمند عددی برای تهیه درخت استفاده كرد. چنين درختي را درخت تخمین زننده مي‌نامند. به جاي افزايش خلوص يك متغیردسته ای، هر تقسيم انجام شده در درخت براي كاهش واریانس ارقام متغیر هدف درهر گره نونهال انتخاب مي‌شود.این حقیقت که از درختان مي‌توان براي تخمین مقادير پیوسته استفاده كرد ایده خوبي نيست. از يك تخمین زننده درخت تصميم مي‌توان به تعداد برگهای موجود در درخت براي ايجاد مقادير ناپیوسته استفاده نمود. بمنظور تخمین يك متغیر پیوسته، استفاده از يك تابع پیوسته ارجحيت دارد. مدل‌هاي رگرسیون و شبكه‌هاي عصبي عموماً براي انجام تخمین ها مناسب ترند.
اسلاید 13: درختان با اشکال متفاوتی وجود دارند درخت موجود در شکل 1-6 از نوع دوگانه با ابعاد غیر یکسان است و به عبارتي هر گره غيربرگي داراي دو نونهال است و برگ‌هاي آن درفواصل مساوي از ريشه نيستند. دراين مورد هر گره نمايانگر يك سؤال بله يا خير است كه پاسخ به آن تعيين مي‌كند يك سابقه اطلاعاتی بايد كداميك از دو مسير را طي كند تا به مرحله بعدي درخت برسد. از آنجايي كه هرگونه تقسيم چند مسیری را مي‌توان به عنوان يك سري تقسيمات دوگانه بيان نمود نياز واقعي به درختاني با عوامل شاخه ساز بیشتر نيست. با اين حال بسياري از ابزارهای داده‌كاوي قادر به ايجاد درخت‌هايي با بيش از دو شاخه‌اند. براي مثال، برخي الگوريتم‌هاي درخت تصميم با ايجاد يك شاخه براي هر دسته، متغیرهای دسته ای را تقسيم مي‌كنند كه اين منجر به درختاني با تعداد مختلف شاخه ها در گره هاي گوناگون مي‌شود. شكل 3-6 نشاندهنده درختي است كه از هردو نوع تقسيم‌بندي سه مسیری و دو مسیری برای همان مسئله دسته بندی که در درخت موجود در شکلهای 1-6 و 2-6 به کار رفته استفاده مي‌كند.لازم به ذکر است که رابطه‌اي بين تعداد شاخه‌هاي مجاز براي هر گره و تعداد دسته ها در متغیر هدف وجود ندارد. يك درخت دوگانه (يعني درختي با تقسيم دوشاخه اي) را مي‌توان براي دسته بندی اطلاعات به هر تعداد دسته و يك درخت با تقسيم چندگانه را مي‌توان براي طبقه‌بندي يك متغیر هدف دوگانه به كار برد.
اسلاید 14: يك درخت تصميم چگونه تهیه می شود با اينكه گونه‌هاي زيادي از الگوريتم‌هاي درخت تصميم وجود دارد ولي همه آنها از روند مشابهی پيروي مي‌كنند که آن عبارت است از تقسيم مكرر داده‌ها به گروه‌هاي کوچك و كوچكتر به نحوي كه با توجه به متغیر هدف هر نسل جدید گره‌ها خالص تر از پيشينيان خود است. در بخش عمده اين مبحث ما يك متغیر دسته ای و دوگانه هدف مثل پاسخ دهنده / غیر پاسخ دهنده را مدنظر قرار مي‌دهيم. اين مسئله باعث تسهیل توضیحات بدون از بین رفتن محتوا می شود.
اسلاید 15: يافتن محل تقسيمات درابتداي فرآيند با يك مجموعه آموزشي شامل داده های از قبل دسته بندی شده سروكار داريم كه همان مقدار متغیر هدف براي تمام موارد است. هدف این فرآیند تهیه درختي است كه یک دسته را (یا احتمال عضویت در هر دسته) به زمینه هدف اطلاعات جدید براساس ارقام متغیرهای ورودی اختصاص می دهد.اين درخت با تقسيم داده ها در هرگره براساس یک زمینه ورودی مجزا تهیه می شود. لذا دراولين اقدام بايد تصمیم گرفت کدامیک از زمینه های ورودی می تواند بهترين تقسيم را انجام دهد. بهترين تقسيم به بهترين جداكننده داده ها به صورت گروه‌هايي گفته می شود كه در آن يك دسته در هر گروه نقش غالب را داشته باشد. اين اندازه گیری برای ارزيابي يك تقسيم بالقوه را خلوص مي‌نامند. در همه این روشهای اندازه گیری خلوص، خلوص كم يعني اينكه مجموعه، حاوی توزيعی از نماینده دسته هاست (بسته به گره والد) درحالي كه خلوص زياد يعني اينكه اعضاي يك دسته مجزا غالب هستند. بهترين تقسيم تقسیمی است که باعث افزايش ميزان خلوص داده ها مي‌شود. در يك تقسیم خوب، گره‌هاي هم اندازه ايجاد مي‌شود يا حداقل گره هایی با تعداد داده های بسيار كم بوجود نمي‌آيد.در شکل 4-6 به آسانی می توان این مطالب را به صورت عینی مشاهده نمود و برخی از تقسیمات خوب و بد در اینجا ارائه شده است.
اسلاید 16: شکل 4- 6 : یک تقسيم خوب باعث افزايش خلوص تمام نونهالان مي‌گردد.
اسلاید 17: اولين تقسيم، نامطلوب است چرا كه در خلوص هیچ افزایشی حاصل نشده است. جمعيت اوليه حاوي تعداد مساوي از هردو نوع اشکال است که پس از تقسيم‌بندي نیز باز همين وضعيت در نونهال ديده مي‌شود. تقسيم دومي نيز نامطلوب است چرا که عليرغم افزايش جزئی خلوص، گره خالص اعضاي كمي‌دارد و خلوص نونهال بزرگتر نسبت به والد خود افزايش بسیار كمي‌يافته است. اما تقسيم‌بندي آخر مطلوب است چرا كه نونهال‌هايي تقريباً يك اندازه و با خلوص بسيار بيشتري نسبت به والد خود ايجاد شده اند.الگوريتم‌هاي درخت سازي طاقت فرسا هستند. در آنها هر متغیر ورودي به نوبت برداشته مي‌شود و افزايش خلوص آنها كه از هر تقسيم‌بندي ایجاد شده توسط آن متغیر اندازه گیری مي‌شود. پس از بررسی تمام متغیرهای ورودي، آن متغیری که بهترین تقسيم را فراهم مي‌سازد براي تقسيم اوليه انتخاب و دو يا چند نونهال ایجاد میشود. اگر امکان هيچگونه تقسیمی نباشد (به دليل تعداد خيلي كم داده ها) يا اگر با تقسیم ها هیچ بهبودي حاصل نشود آنگاه آن الگوريتم به پايان رسيده است و همين گره تبديل به گره برگي مي‌شود. در غیر اینصورت الگوریتم تقسیم را انجام می دهد و روی هر نونهال این عمل را تکرار می کند. يافتن محل تقسيمات
اسلاید 18: تقسيمات براساس تأثير آنها بر خلوص گره از نظر متغیر هدف ارزيابي مي‌شوند. اين بدان معنی است که انتخاب معیار تقسیم مناسب بستگي به نوع متغیر هدف و نه به نوع متغیر ورودي دارد. برای يك متغیر هدف دسته ای، آزمایشهایی نظير جینی ، بهره اطلاعاتي و مربع کای مناسب است، صرف نظر از اينكه متغیر ورودي که تقسیم را ارائه کرده عددی باشد يا دسته ای. به همين ترتيب با داشتن يك متغیر عددی پیوسته، آزمايشي نظير كاهش واریانس يا تست F براي ارزيابي تقسيم مناسب است صرفنظر از اينكه متغیر ورودي که تقسیم را ارائه کرده دسته ای باشد يا عددی. يافتن محل تقسيمات
اسلاید 19: تقسیم متغیر ورودی عددی وقتي به دنبال يك تقسيم دوگانه در يك متغیر ورودي عددی هستیم هر مقداري كه متغیر در مجموعه آموزشی به خود می گیرد به عنوان رقم کاندیدا براي آن تقسيم در نظر گرفته می شود.تقسيمات در يك متغیر عددی به شكل X<N خواهند بود. تمام داده ها كه مقدار X (متغیر تقسيم‌بندي) در آنها كمتر از مقدار ثابت N مي‌باشد به يك نونهال فرستاده مي‌شود و تمام داده ها كه مقدار X آنها بيش از N یا مساوی آن باشد به نونهال ديگري ارسال مي‌شود.پس از هر تقسيم‌بندي آزمايشي، هر گونه افزايش درخلوص كه از تقسيم ناشي شده است (در صورت وجود) اندازه‌گيري می شود. وقتي درخت تصميم امتيازدهي شد تنها استفاده‌اي كه از ورودي‌هاي عددی می شود مقايسه مقادير آنها با نقاط تقسيم بندي است. این ارقام هرگز در وزن‌ها ضرب و يا با هم جمع نمي‌شوند در حالی كه دربسياري از انواع دیگر مدل‌ها این اعمال انجام می شود. از این ویژگی نتيجه مهمي حاصل مي‌شود كه آن عدم حساسيت درخت‌هاي تصميم نسبت به مشاهدات پرت و یا توزیع چوله متغیرهای عددی است زیرا درخت فقط از رتبه‌هاي مقادير عددی و نه از مقادير مطلق آنها استفاده مي‌كند.
اسلاید 20: تقسيم متغیر ورودي دسته ای ساده ترين الگوريتم براي تقسيم‌بندي يك متغیر ورودي دسته ای تنها ايجاد يك شاخه جديد براي هر دسته ای است كه تابع دسته ای مي‌تواند برگزيند. لذا اگر از رنگ به عنوان بهترين براي تقسيم گره ريشه استفاده شود و مجموعه آموزشي شامل داده هایی باشد كه مقادير قرمز، نارنجي، زرد، سبز، آبي، نیلی و بنفش را به خود بگیرد آنگاه هفت گره در سطح بعدي درخت وجود خواهد داشت. از اين رويكرد در برخي بسته‌هاي نرم افزاري استفاده مي‌شود اما اغلب نتايج ضعیفی به همراه دارد. شاخه بندي های زیاد، جمعيت داده های آموزشی موجود در هر گره در پايين ترين سطح درخت را به سرعت كاهش مي‌دهد و به اين ترتيب تقسیمات بعدی کمتر قابل اعتماد می شوند.يك رويكرد رايج ديگر گروه بندي دسته ها یی است كه به صورت انفرادي نتايج مشابهي را پيش‌بيني مي‌كنند. درنگاهي دقيق تر اگر دو دسته متغیرهای ورودي به توزيع دسته های متغیر خروجي كه تفاوت بارزي با هم ندارند بپردازند دو دسته را مي‌توان باهم ادغام كرد. آزمايش متعارف براي تشخیص وجود تفاوت بارز توزيع‌ها باهم، تست مربع کای است.
اسلاید 21: تقسيم با وجود مقادیر گمشده يكي از جالب‌ترين نكات درخت‌هاي تصميم توانايي آنها در مدیریت مقادیر گمشده در هر دو زمینه ورودی عددی یا دسته ای با در نظر گرفتن مقدار گمشده در شاخه مخصوص خود است. اين رويكرد براي حذف داده های داراي مقادیر گمشده يا براي تخصیص مقادیر جایگزین مقادیر گمشده ترجیح داده می شود. حذف داده ها با مقادیر گمشده معمولا باعث بوجودآمدن يك مجموعه آموزشي تحریف شده میگردد چراكه احتمالاً داده های دارای مقادیر گمشده، نمونه ای تصادفی از جمعيت نیستند. جايگزيني مقادیر گمشده با مقادير جایگزین تخصیصی نیز اين خطر را دربردارد كه اطلاعات مهم متاثر از يك مقدار گمشده در مدل نادیده گرفته شود. موارد بسياري ديده شده است كه مقدار گمشده خود مقدار پيش‌بيني‌كننده بوده است. لازم به ذکر است که درخت‌هاي تصميم مي‌توانند تقسيم‌بندي‌هايي را براساس مقادیر گمشده يك متغیر ورودي انجام دهند. تهی بودن يك مقدار اغلب مي‌تواند ارزش پيش‌بيني کننده ای داشته باشد لذا در حذف اطلاعات حاوي مقادیر گمشده يا جايگزينی آنها با مقادير تخصیصی عجله نكنيد.با اينكه بيشتر مواقع تخصیص مقدار تهی به عنوان يك دسته جداگانه بسيار ارزشمند است اما حداقل يك رويكرد جايگزين توسط يك نرم افزار داده‌كاوي ارائه شده است. هرگره تعدادي قانون تقسيم‌بندي ممكن را ذخیره میکند که هر کدام براساس یک زمینه ورودی متفاوت مدون شده اند. وقتي به يك مقدار تهی در زمینه ای كه بهترين تقسيم‌ها را فراهم مي‌سازد برخورد شود نرم افزار از تقسيم‌بندي جانشین برمبناي بهترين متغیر ورودي موجود بعدي استفاده مي‌كند.
اسلاید 22: رشد درخت کاملتقسيم اوليه، دو يا چند گره نونهال راايجاد مي‌كند كه هركدام به روشی مشابه گره ريشه تقسيم مي‌شوند. دراينجا نيز تمام زمینه های اطلاعات ورودي به عنوان تقسيم كننده های نامزد به حساب می آیند حتی زمینه هایی که قبلاً برای تقسیمات استفاده شده اند. با این وجود، زمینه هایی که فقط يك مقدار را به خود مي‌گيرند در نظر گرفته نمی شوند چرا كه راهي كه بتوان از طریق آنها براي ايجاد يك تقسيم استفاده كرد وجود ندارد. يك زمینه دسته ای كه به عنوان تقسيم‌گر در سطح بالای درخت به كار رفته احتمالاً به سرعت تك مقداری خواهد شد. بهترين تقسيم براي هر کدام از زمینه های باقيمانده تعيين مي‌شود. وقتي که دیگر تقسیمی که خلوص يك گره داده شده را افزایش دهد یافت نشود يا وقتي تعداد داده های يك گره به مقدار حداقل از پیش تعیین شده برسد و يا اگر ابعاد درخت به حد از پيش تعیین شده ای برسد آنگاه جستجوي تقسيم براي آن شاخه متوقف شده و گره به عنوان یک گره برگ برچسب مي‌خورد.سرانجام وقتی امكان يافتن تقسيم بندي‌هاي بيشتري در هيچ جاي درخت وجود نداشته باشد درخت تصمیم کامل ساخته شده است. همانطور كه خواهيم ديد اين درخت كامل معمولاً درختي نيست كه به بهترين شيوه يك مجموعه جديد از داده ها را دسته بندی مي‌كند
اسلاید 23: الگوريتم‌هاي ساخت درخت تصميم با تلاش در يافتن آن متغیر ورودي شروع می شوند كه بهترين تقسيم‌بندي داده‌ها را درميان گروههای دلخواه انجام مي‌دهد. در همه سطوح بعدی درخت، زيرمجموعه‌هاي ايجاد شده در تقسيم‌بندي قبلي براساس هر قانوني كه در مورد آنها بهتر عمل مي‌كند تقسيم مي‌شوند. رشد درخت ادامه مي‌يابد تا جايي كه ديگر نتوان راه‌هاي بهتری برای تقسيم بيشتر داده های ورودي پيدا كرد. اگر رابطه كاملاً تعيين‌كننده‌اي بين متغیرهای ورودي و متغیر هدف وجود داشته باشد اين تقسيم بندي بازگرا درنهايت منجر به يك درخت با برگ‌هاي كاملاً خالص میشود. تهیه نمونه‌هایي از اين گونه آسان است اما ايجاد اين ساختار در كاربردهاي بازاريابي يا مدیریت ارتباط با مشتری چندان اتفاق نمي‌افتد. داده های رفتار مشتري تقريباً هيچگاه حاوي چنین روابط شفاف و تعيين‌كننده ای بين ورودي‌ها و خروجي‌ها نيست. اين حقيقت كه دو مشتري ازنظر متغیرهای ورودي موجود داراي مشخصات دقيقاً يكساني باشند متضمن بروز رفتار یکسان از جانب آنها نيست. بطور مثال يك درخت تصميم براي مدل پاسخ به يك كاتالوگ ممکن است شامل برگي باشد كه نمايانگر زنان بالاي 50 سال سن با سه بار يا بيشتر خرید در طول يك سال گذشته و مجموع خرید بالاي یکصد و پنجاه هزار تومان باشد. مشترياني كه به اين برگ مي‌رسند معمولاً آميزه‌اي از پاسخ دهنده ها و غیر پاسخ دهنده ها هستند. اگر برگ مزبور داراي برچسب پاسخ دهنده باشد آنگاه درصد غیر پاسخ دهنده ها به عنوان نرخ خطاي اين برگ محسوب می شود. نسبت سهم پاسخ دهنده ها در اين برگ به سهم پاسخ دهنده های کل جامعه را صعود در این برگ می نامند. رشد درخت کامل
اسلاید 24: وضعيتي كه در آن احتمال كشف قوانين تعيين كننده وجود دارد زماني است كه الگوهاي موجود در داده‌ها منعکس کننده قوانين تجاری باشند. اين حقيقت در قالب یک مثال از یک شركت توليدكننده موتورهاي ديزل توضیح داده می شود. در این شرکت يك مدل درخت تصميم براي پيش‌بيني اينكه كدام تقاضای استفاده از خدمات گارانتی تأييد می شود تهیه گردید. بر اساس روال موجود در آن شركت، به برخي تقاضاها به صورت خودكار و بدون بررسی بیشتر وجهی پرداخت می شد. نتايج چشمگيري حاصل شد بگونه ایکه مدل تهیه شده براي داده‌هاي قبلاً آزمايش نشده صد درصد دقيق بود. به عبارت دیگر، مدل، قوانين دقيقي را کشف کرد كه شركت براي دسته بندی تقاضاها بكار مي‌برد. در اين مورد، تکنیک شبكه عصبي با چنین موفقیتی عمل نمی کرد. البته كشف قوانين آشنا در تجارت شايد چندان مفيد نباشد اما زيربنايي براي ساخت درخت‌هاي تصميم در حل مشكلات قانون مدار خواهد بود. بسياري از حوزه‌ها از فرآيندهاي ژنتيكي گرفته تا صنعتي درواقع داراي قوانين زيربنايي هستند هرچند كه اين قوانين به لحاظ داده‌هاي درهم ريخته شايد بسيار پيچيده و مبهم باشند. انتخاب درخت‌هاي تصميم هنگامي‌كه قوانين زيربنايي وجود دارد گزينه‌اي طبيعي خواهد بود. رشد درخت کامل
اسلاید 25: اندازه‌گيري کارآیی درخت تصميم‌گيري در نگرشي كلي، کارآیی يك درخت تصميم‌گيري هم از روي اعمال آن بر يك مجموعه آزمايشي ( كه از داده های آن در ساخت درخت استفاده نشده است) و مشاهده درصد دسته بندی صحیح تعیین میشود. اين دستاورد، نرخ خطاي دسته بندی درخت را به صورت كلي فراهم مي‌كند ولي بايد به كيفيت هر يك از شاخه‌هاي درخت نیز توجه نمود. هر مسير در درخت نمايانگر يك قانون است و برخي قوانين بهتر از سايرين مي‌باشند. در هر گره اعم از گره برگي يا شاخه اي مي‌توان موارد زير را اندازه گيري نمود:تعداد داده های ورودي به گرهنسبت داده ها در هر دستهچگونگی طبقه‌بندي داده ها اگر گره از نوع برگي باشد.درصد دسته بندی صحيح داده ها در آن گرهواریانس توزيع بين مجموعه آموزشي و آزمايشي مسئله مهم دراينجا درصد دسته بندی صحيح داده های هر گره می باشد. باكمال تعجب گاهي يك گره در سطح بالای درخت، دسته بندی بهتري را درمجموعه آزمايشي انجام مي‌دهد تا گره‌هايي در سطح پايين تر.
اسلاید 26: آزمایش های انتخاب بهترين تقسيم اندازه‌گيري‌هاي متفاوتي براي ارزيابي تقسيمات بالقوه وجود دارد. الگوريتم‌هاي تهیه شده در حوزه یادگیری ماشيني بر افزايش خلوص نتایج ناشي از يك تقسيم تأکید دارند حال آنكه تمرکز الگوريتم‌هاي تهیه شده در جوامع آماری به تفاوت آماري بين توزيعات گره‌هاي نونهال می باشد. اغلب بکارگیری شاخص‌هاي تقسيم‌بندي متفاوت، منجر به تولید درخت‌هايي می شوند كه اگرچه دارای ظاهری كاملاً متفاوتند ولی در عملکرد مشابه هم هستند. دليلش اين است كه معمولاً انواع مختلف تقسیم ها با عملكردهايي بسيار مشابه وجود دارند. اندازه های خلوص متفاوت منجر به انتخاب نامزدهاي گوناگون مي‌شود اما از آنجايي كه تمام اين اندازه گیری ها براي بدست‌آوردن ايده یکسانی تلاش مي‌كنند مدل‌هاي حاصل شده رفتاري مشابه دارند.
اسلاید 27: خلوص و پراكندگي هر دو عبارت كاهش در پراكندگي حاصل از تقسیم و افزايش خلوص حاصل از تقسیم به ايده‌اي یکسانی اشاره دارند. اندازه خلوص که دامنه آن از صفر (زماني كه هیچ دو موردی در نمونه در دسته یکسانی نباشند) تا یک (زماني كه تمام موارد در نمونه در یک دسته قرار گیرند) است را مي‌توان باكسر كردن آن از عدد یک تبديل به مفهوم عکس آن یعنی اندازه پراكندگي كرد. برخي از اندازه گیریها که براي ارزيابي تقسيم‌بندي‌هاي درخت تصميم گيري استفاده می شوند كمترين امتياز را به يك گره خالص و برخی دیگر بالاترين امتياز را به آن میدهند. تمامي‌اين موارد به عنوان اندازه های خلوص در نظر گرفته شده و هدف، بهينه‌سازي خلوص با به حداقل يا حداكثر رساندن اندازه انتخاب شده است. شكل 5-6 يك تقسيم خوب را نشان مي‌دهد. گره والد حاوي تعداد مساوي نقاط تيره و روشن است. نونهال سمت چپ حاوي نه نقطه روشن و يك نقطه تيره و نونهال سمت راست برعکس داراي نه نقطه تيره و يك نقطه روشن است. واضح است که خلوص افزايش يافته است، اما چگونه مي‌توان اين افزايش را اندازه گیری نمود؟ و چطور مي‌توان اين تقسیم را با ساير تقسیمات مقايسه كرد؟ براي اين كار نياز به یک تعريف رسمي از خلوص است.
اسلاید 28: شكل 5-6: يك تقسيم خوب در متغیر دسته ای دوگانه باعث افزايش خلوص مي‌گردد.
اسلاید 29: اندازه گیری خلوص براي ارزيابي تقسيمات اندازه گیری خلوص براي ارزيابي تقسيمات در متغیرهای توابع هدف شامل موارد زیر می باشد:جینی (به نام پراكندگي جمعیت نيز خوانده مي‌شود) آنتروپی (به نام بهره اطلاعاتي نيز خوانده مي‌شود)نسبت بهره اطلاعاتيآزمون مجذور مربع کایوقتي متغیر هدف از نوع عددی باشد يك رويكرد ممكن، حذف آن و استفاده از يكي از اقدامات فوق است. با این وجود دو اقدام رایج براي اهداف عددی وجود دارد: كاهش واریانسآزمون Fتوجه داشته باشید كه انتخاب روش مناسب اندازه گیری خلوص بستگي به دسته ای و یا عددی بودن متغیر هدف دارد. از آنجا که نوع متغیر ورودي اهميتي ندارد، تمامي يك درخت براساس روش یکسان اندازه گیری خلوص تهیه مي‌شود. تقسیم نشان داده شده در نمودار 5-6 را مي‌توان با يك متغیر ورودي عددی و يا با يك متغیر دسته ای تهیه نمود که خلوص نونهالان، صرفنظر از نوع تقسیم، يكسان مي‌باشد.
اسلاید 30: جینی یا پراكندگي جمعیت يك شاخص رايج تقسيم‌بندي جینی نام دارد كه از نام كورادو جینی، متخصص آمار و اقتصاددان ايتاليايي گرفته شده است. اين اندازه گیری كه توسط زيست شناسان و بوم شناسان نيز براي مطالعه پراكندگي جمعيت استفاده مي‌شود احتمال قرارگیری دو مورد انتخاب شده تصادفی از یک جمعیت یکسان را در يك دسته نشان می دهد. براي يك جمعيت خالص، اين احتمال برابر یک مي‌باشد. اندازه گیری جینی يك گره، به صورت ساده مجموع مربع نسبتهای دسته ها مي‌باشد. براي تقسيم نشان‌داده شده در شكل 5-6 جمعيت والد داراي تعداد مساوي از نقاط روشن و تيره است. يك گره با تعداد مساوي از هريك از دو دسته، داراي امتياز است كه قابل انتظار است چرا که شانس انتخاب یک دسته دو دفعه به صورت تصادفی با امکان جایگزینی، يك از دو خواهد بود. امتياز جینی براي هر گره به وجود آمده خواهد بود. يك گره كاملاً خالص داراي امتيازجینی یک خواهد بود. گره‌اي که متوازن است داراي امتياز جینی 0.5 خواهد بود. براي محاسبه تأثير يك تقسيم، امتياز جینی هر گره نونهال را محاسبه کرده و در نسبت اطلاعات كه به آن گره مي‌رسند ضرب كرده و سپس اعداد حاصل را باهم جمع می کنیم. در این مورد، ازآنجايي كه داده ها بطور مساوي درون دو گره حاصل از اين تقسيم قرار مي‌گيرند و هر گره داراي امتياز جینی مساوی است لذا امتياز تقسيم انجام شده مساوي امتياز هر يك از دو گره است.
اسلاید 31: كاهش آنتروپی يا بهره اطلاعاتي بهره اطلاعاتي از يك ايده زيركانه براي تعريف خلوص استفاده مي‌كند. اگر يك برگ كاملاً خالص باشد آنگاه دسته های اين برگ را مي‌توان به راحتي اینگونه توصیف كرد که همگي آنها در يك دسته جاي می گیرند. از طرف دیگر، اگر يك برگ داراي نا خالصی بالايي باشد آنگاه توصیف آن بسیار مشکل خواهد بود. تئوری اطلاعات كه بخشي از علوم رايانه‌اي است براي اين وضعيت اندازه ای به نام آنتروپي ایجاد کرده است. در تئوری اطلاعات، آنتروپی اندازه میزان بی نظمی يك سیستم است. می توان گفت که كه تعداد بيت‌هاي رايانه‌اي مورد نياز براي توصیف يك موقعیت يا نتیجه خاص بستگي به اندازه مجموعه نتایج ممکن دارد. می توان آنتروپی را به عنوان اندازه تعداد سوالات بلي/خير مورد نياز براي تعيين وضعيت سیستم در نظر گرفت. اگر 16 وضعيت احتمالي وجود داشته باشد، نياز به ضريب log2(16) يا چهار بيت براي شمارش آنها يا شناسايي يكي از آنها خواهد بود. اطلاعات اضافی باعث كاهش تعداد سؤالات مورد نياز براي تعيين وضعيت سیستم خواهد شد لذا بهره اطلاعاتي به معناي همان كاهش آنتروپی مي‌باشد. از هر دو لفظ براي توصیف الگوريتم‌هاي درخت تصميم استفاده می شود.
اسلاید 32: آنتروپی يك گره خاص يك درخت تصميم عبارت است از جمع نسبتهای داده های متعلق به يك دسته خاص براي تمام دسته هایی كه در گره نشان داده شده اند كه در لگاريتم پايه دو آن نسبت ضرب شده است (در واقع اين مجموع را معمولاً در 1- ضرب می کنند تا عددي مثبت به دست آيد). آنتروپی يك تقسيم بصورت ساده از مجموع آنتروپی تمام گره‌هاي ناشي از تقسیم که بوسیله نسبت داده های هر گره وزن دهی شده است به دست می آید. هنگامي‌كه از كاهش آنتروپی به عنوان يك شاخص تقسيم‌بندي استفاده شود، الگوريتم به دنبال تقسیمی می گردد که آنتروپی را تا بیشترین میزان کاهش دهد (یا اطلاعات را افزایش دهد). براي يك متغیر هدف دوگانه نظير آنچه در شکل 5-6 آمده، فرمول بكار رفته براي آنتروپی يك گره عبارت است از : (احتمال نقاط روشن log2 × احتمال نقاط روشن) + (احتمال نقاط تیره log2 × احتمال نقاط تیره) × 1-دراين مثال، احتمال نقاط تیره و احتمال نقاط روشن هردو 0.5 هستند و با قرار دادن 0.5 در فرمول آنتروپی، رابطه زیر به دست می آید:{(0.5) log2 0.5 + (0.5) log2 0.5} × 1- كاهش آنتروپی يا بهره اطلاعاتي
اسلاید 33: اولين عبارت براي نقاط روشن و عبارت دوم براي نقاط تيره است اما ازآنجايي كه تعداد نقاط روشن و تيره مساوي هستند عبارت به صورت (0.5) log2 × 1- ساده می شود که جواب 1+ به دست می آید.حال سوال اینجا است که آنتروپی گره‌هاي ناشي از تقسيم چقدر است؟ يكي از آنها داراي یک نقطه تيره و نه نقطه روشن است درحالي كه ديگري داراي نه نقطه تيره و يك نقطه روشن مي‌باشد. به وضوح می توان دید که هر دو داراي سطح آنتروپی یکسانی هستند، یعنی:0.47 = 0.14 + 0.33 = {(0.9) log2 0.9 + (0.1) log2 0.1} × 1- براي محاسبه کل آنتروپی سیستم پس از تقسیم، آنتروپی هر گره را در نسبت داده هایی که به آن گره رسیده اند ضرب کرده و همه آنها را با هم جمع کرده و متوسط آن را محاسبه نمایید. در اين مثال، هر گره جديد نيمي‌از داده ها را به دست مي‌آورد به طوري كه آنتروپی کل همانند آنتروپی هر گره 0.47 است. مجموع كاهش آنتروپی يا بهره اطلاعاتي حاصل از تقسيم نيز 0.53 خواهد شد. اين شاخصی است كه براي مقايسه اين تقسیم با ساير نامزدها بكار مي‌رود. كاهش آنتروپی يا بهره اطلاعاتي
اسلاید 34: نسبت بهره اطلاعاتي اندازه گیری آنتروپی تقسيم زماني به مشكل بر می خورد كه با يك روش تقسيم‌بندي همراه شود که با متغیرهای ورودي دسته ای با ایجاد شاخه جدیدی برای هر مقدار سروکار داشته باشد. همين مورد درباره برنامه ID3 پيش آمد که يك ابزار درخت تصميم است که توسط محقق استراليايي جی راس كوئينلن در دهه 1980 تهیه شد و به صورت بخشي از بسیاری از بسته های نرم افزاري تجاري داده‌كاوي درآمد. مشكل در اينجا کاهش تعداد دسته های نمایش داده شده در هر گره و متعاقب آن کاهش آنتروپی است كه صرفاً از شكستن مجموعه داده‌هاي بزرگتر به زيرمجموعه‌هاي كوچكتر ناشي مي‌شود. كاهش آنتروپی که مربوط به تعداد شاخه‌ها باشد را اطلاعات نهادي يك تقسيم‌بندي مي‌نامند. ( به یاد داشته باشید که آنتروپی به عنوان مجموع تمام شاخه‌هاي احتمالات هر شاخه ضرب در لوگاريتم پايه 2 آن احتمال تعريف مي‌شود). براي يك تقسيم تصادفیn مسيری، احتمال هر شاخه 1/n مي‌باشد. لذا آنتروپی ناشي از تقسیمی که یک تقسيم n مسيری باشد، عبارت ساده n×1/n log(1/n) يا log(1/n) خواهد بود.
اسلاید 35: به خاطر اطلاعات نهادي تقسيمات چندمسيري، درخت‌هاي تصميم ساخته شده با استفاده از شاخص تقسيم‌بندي كاهش آنتروپی بدون هرگونه اصلاح درزمينه اطلاعات نهادي مربوط به تقسيم، پربرگ و بار مي‌شوند. درخت‌هاي پربرگ با تقسيمات متعدد چندمسيری مطلوب نيستند چراكه اين تقسيمات به تعداد کم داده ها در هر گره منجر شده و مدل‌هاي حاصله از اين طريق ناپايدار خواهند بود.براي برخورد با اين مشكل، C5 و ساير مشتقات ID3 كه زماني از بهره اطلاعاتي استفاده مي‌كردند اينك به خاطر تقسيم پيشنهادي اطلاعات نهادي كه منحصراً مرتبط با تعداد شاخه‌هاي ساخته شده به عنوان شاخص ارزيابي تقسيمات پيشنهاد شده مي‌باشد از نسبت کل بهره اطلاعاتي استفاده مي‌كنند. اين آزمايش از گرايش به درخت‌هاي بسيار پربرگ كه در بسته‌هاي نرم افزاري قبلی درخت تصميم مشكل به حساب مي‌آمد پيشگيري خواهد كرد. نسبت بهره اطلاعاتي
اسلاید 36: آزمون مربع کای آزمون مربع کای (X2)، آزمون معنی داری آماري است که توسط آمارشناس انگليسي كارل پيرسون در سال 1900 بوجود آمد. اين آزمون به عنوان مجموع مربع های تفاوتهای استاندارد شده بین فراوانیهای مورد انتظار و مشاهده شده برخی وقایع در نمونه های ناپیوسته چندگانه تعريف شده است. به بيان ديگر، اين آزمون اندازه ای برای این احتمال است که تفاوت مشاهده شده بين نمونه‌ها صرفا اتفاقی است. هنگامي‌كه براي اندازه گيري خلوص تقسیم های درخت تصميم از اين آزمون استفاده شود، مقادير بالای مربع کای به معناي آن است كه تغییرات معنی دار بوده و به صورت اتفاقی و بر اساس شانس حاصل نشده است.
نقد و بررسی ها
هیچ نظری برای این پاورپوینت نوشته نشده است.