درخت‌های تصمیم

صفحه 1:
خت های در 

صفحه 2:
درخت های تصمیم درخت‌های تصمیم ابزار قدرتمند و درعین حال رایجی هم برای دسته بندی و هم برای پیش‌بینی = جذابیت روش‌های درخت مبنا بیش از هرچیز به این واقعیت برمی‌گردد که درخت‌های تصمیم نمیانگر قوانین می‌باشند.به راحتی می‌توان قوانین را به زبان فارسی و یا هر زبان دیگری در آورد تا برای همگان قلبل فهم باشند. همچنین می‌توان آنها را به زبان قلبل دسترسى يايكاه داده ها مانند 6) درآورد و مثلا اطلاعات یک گروه خاص ر استخراج نمود. درخت تصمیم برای بررسی داده ها برای کسب بینش بهتر درباره رولبط موجود بین تعداد زیادی از ‎clot‏ ورودی كاتدينا شله برای یک متفر هدف در مقيد مرياضد أراتجلين كه درجت تسميم بررسی داده و مدلسازی را باهم ترکیب می‌کند. گام اولیه قدرتمندی در فرآیند مدلسازی به شمار می روند حتی هنگامی که برای تهیه مدل نهایی از برخی تکنیکهای دیگر استفاده شود. 

صفحه 3:
معمولاً بین صحت مدل و شفافیت مدل توازن وجود دارد. دربرخی کارپردهاء. صحت دسته بندی یا پیش‌بینی تنها مسئله مهم است.لگر مثلاً یک شرکت پست مستقیم مدلی را دراختیار داشته باشد که با استفاده از آن بتوان به درستی پیش‌بینی کرد که کدامیک از مشتریان بالقوه احتمالاً به پیشنهاد عرضه شده پاسخ خواهند داد آنگاه شلید برای لین شرکت اهمیتی نداشته باشد چرا و چگونه مدل پیش‌بین ی کننده عمل میکند. درسایر شرلیط. توانلیی بیان علت یک تصمیم حیلتی است. برای مثال. در غرامت‌های بیمه. برخی ممائعت‌های قانینی دربرابر تبعیضها براساس متفیرهای خاصی وجود دارد. شاید یک شرکت بیمه در وضعیتی قرار بگیرد که مجبور شود به دادگاه ثلبت کند هیچگهنه تبعیض غیرقانینی در دادن یا ندادن ارت به افراد مرتکب نشده ۱ چنین بیشتر این پذیرفته شده است که وام دهنده و وام گیرنده بدانند که پر اساس سیستم رایانه‌ای با اعطای وام موافقت نشده است (مثلاً درمواردی که محاسبات رایانه‌ای نشان دهد درآمد ماهیلنه متقاضی کمتر از سطح لازم است یا آنکه ظرفیت وام گیرندگان پرشده است) تا اینکه بفهمند تصمیم‌گیری درباره عدم اعطای وام توسط یک شبکه عصبی هوشمند بدون هیچگونه توضیحی در مورد عملکردش صورت گرفته است. 

صفحه 4:
درخ مد یم ۰ درخت تصمیم‌گیری ساختاری است که برای تفسیم مجموعه‌ای بزرگ از داده های جمع‌آوری شده به مجموعه‌های کوچکتر زنجیرهوار داده ها بواسطه یک سری قوانین ساده تصمیم‌گیری به كار می‌رود. در هر تقسیم‌بندی متوالی, اعضای مجموعه های حاصل بیش از پیش به همدیگر مشابه می شوند. تقسیم‌بندی موجودات زنذه براساس قلمروهاه سلسله مراقب پیفلیش» دسته كا نظام ‎aly‏ خانواده. جنسیت و گوله ها که در دهه ۱۷۲۰ توس گیاه‌گناس سوثه‌ی ‎ee eS‏ در قلمروی حیوانات چنانچه موجود زنده‌ای دارای ستون فقرات باشد جزو دسته مهره داران قرار می‌گیرد. از دیگر ویژگی‌های مهره داران برای تقسیم‌بندی آنها به پرندگان» پستتعاران. خرن گان و عیره استفاده می‌شود لین دسته بندى اتقدر ادامة مى يليد تادر پایین‌ترین رده‌بندی. اعضای یک گونه هم ازنظر شکل شناسی و هم توانلیی زاد و ولد و ‎eee‏ 

صفحه 5:
درخ مد یم ۰ یک مدل درخت تصمیم‌گیری از مجموعه ای از قوانین برای تقسیم جمعیت ناهمگن وسیعی به گروه‌های کوچکتر و همگن تر با توجه به یک متفیر هدف خاص تشکیل شده است. شلید تهیه درخت تصميم كيرى مشلبه مدل كارل لينوس كه به سورت دستى آماده شده طلقت قرما باشد و شليد اين كار به طور خودكار با اعمال برخى الكوريتمهاى درخت تصميمكيرى دريك مجموعه مدل حاوى داده‌های از قبل دسته بندی شده انجام شود. معمولاً متفیر هدف. دسته ای است و از مدل درخت تصمیم‌گیری استفاده می شود تا لحتمال تخصیص داده های موجود به هر کدام از دسته ها محاسبه شود یا برای دسته بندی داده ها با تخصیص آن به محتمل ترین دسته به کاررود. همچنین می‌توان از درخت‌های تصمیم‌گیری برای برآورد مقدلر متفیرهای پیوسته استفاده کرد هرچند که تکنیک های مناسبتری نیز برای انجام این کار وجود دلرد. 

صفحه 6:
دسته بندی آنهای که با باری بست سوالی آشناه ند حوب میداند گنه یک درخت تصميم. داله‌ها رأ ‎is en ant‏ درابی بازی یک پاریکن. كان ‎٠‏ شحس. با قینی خاس را که برای بكر شرکت‌کنندگان آشنا است درنظر می‌گیرد ولی وی سرنخی به ديكران در اين رابطه نمی‌دهد. بقیه بازیکنان سعی می‌کنند با طرح یک سری سوالات و گرفتن پاسخ بله یا خیر ن را حدس بزنند. یک بازيكن خوب به ندرت نیز به پرسیدن همه بيست سوال مجاز در بازى دارد ا از اولين سؤال خود كه "درجيب جا مىشود؟" به ياسخ اصلى "برج میلاد" برسد. يك درخت تصميم نيز يك سرى و زنجيره از اين سوالات را مطرح مى كند. همجون بازى بيست سوالی. پاسخ بهاولین سوال تعیین کننده سوال بعدی است. سوالات اولیه به ايجاد كروههاى بسيار گسترده ای‌با اعضای فراوان کمک می کند و سوالات بعدی لین گروههای گسترده را به مجموعه‌های کوچکتر و کوچکتری محدود می‌کند.اگر سوالات به خوبی انتخاب شوند آنگاه با یک سری محدود از سئوالات می توان به دسته بندی صحیح داده های ورودی پرداخت. 

صفحه 7:
‎ee‏ یت ‏بازی بیست سوالی نشان دهنده فرآیند استفاده از یک درخت برای گنجاندن امتیاز یا دسته ای در داده ها است. یک سابقه اطلاعلتی در گره ريشه قرار می‌گیرد. دراینجا برای تعیین اینکه بعدا اطلاعات درج شده به کدام ريشه نونهال پییند می‌خورد یک آزمایش صورت می‌گیرد. الگوریتم‌های گوناگونی برای انتخاب آزمایش اولیه وجود دارد اما هدف همه آنها یکی است و آن چیزی نیست جز انتخاب آزمایشی که بتولند بین دسته های هدف بهترین تملیز را قلیل شود. لین فرآیند آنقدر تکرار می‌شود تا يك سابقه اظلاعلتى به يك "ره برك برسد نمام اطلاعلتى كد به يك يرى فر درختت تبديل مىشوند به طریقی مشابه دسته بندی می‌شوند و یک مسیرمنحصر به فرد از ريشه به برگ وجود خواهد داشت. ‏چنین مسیری نشانگر یک قانون به کاررفته در دسته بندی سوابق اطلاعاتی است. ‏شلید برگ‌های گوناگون دارای دسته بندی های مشابهی باشند هرچند که هر برگ به علت متفاوتی دسته بندی را انسام می دهد به صنوان مثال درحتی که میوه جات و سبریحات را بران اس رنگ آن میوه یا سبزی دسته بندی می کند. برگ درخت تصمیم سیب و گوجه فرنگی و گیلاس می تواند رنگ قرمز را پیش بینی کند هر چند احتیاطهلیی را هم بلید در نظر داشت چراکه سيبهاى سبزه گوجه فرنگی‌های زرد و گیلاس‌های سیاه رنگ هم وجود دارد. 

صفحه 8:
درخت تصمیم‌گیری موجود در شکل ۶-۱ فهرست گیرندگان احتمللی یک کاتالوگ خرید کالا را به صورت محتمل (۱) و غیر محتمل (۲) برای سفارش دادن پس از فرستادن کاتالوگ جدید دسته بندی می کند. این درخت براساس قواعد رایج در چرخه های داده کاوی تنظیم شده است بطوری که ریشه‌ها در بالا و برگ‌ها در پایین واقع شده اند. درسمت راست فوقانی هر گره یک شماره قراردارد و دسته پیش شده هرکدلم درمرکز درج شده است. قوانین تصمیم‌گیری برای تقسیم هر گره روی خطوطی که هر گره رل به نونهالان خود وصل می‌کند چاپ شده است. تقسیم در گره ریشه‌ای که "سفارشات مادام العمر" نام دارد صورت گرفته است و شاخه سمت چپ به مشتریلنی اختصاص يافته كه شش سفارش یا کمتر داشته اند و شاخه سمت راست به مشتریانی با ۷ سفارش و بیشتر تعلق گرفته است. هر داده ای که به گره‌ها ی برگی ۰۱۹ ۰۱۴ ۰۱۶ ۱۷ یا ۱۸ برسد با عنوان متحمل به پاسخگویی دسته بندی می شود چرا که دسته پیش‌بینی شده دراین مورد یک است. مسیرهای منتهی به اين گره‌های برگی قوانین درخت را بیان می کنند. به عنوان مثال. قانون مربوط به برك 11 از اين قرار است: "اگر مشتری بیش از ۵/۶ سفارش داشته باشد و کمترلز ۷۶۵ روز از آخرین سفارش وی بگذرد. احتمالا به کاتالوگ پاسخ خواهد داد." 

صفحه 9:
* شلید خوانندگان هوشیار متوجه شهند که برخی تفسیم‌های درخت تصمیم در ظاهر ری نمی ند متا کرههای ۷ و ۷ تراسا تاد سهارسای که سابل سفارشاتی از دسته خورای‌ها است متمایر شده اند. آما هر دو گره به عنوان پاسخ عبین شده اند. علت این مسئله لن است که گذشته از بالاتر بودن احتمال پاسخ در گره ۱۸ نسبت به گره ۱۷ احتمال پاسخ در هر دو مورد بیش از حدی است که برای طبقه‌بندی یک سابقه اطلاعاتی به عنوان پاسخ دهنده تعیین شده است. این مدل به عنوان یک دسته بندی کننده فقط دو خروجی صفر و یک دارد. لین دسته ‎coy‏ دوگانه. اطلاعات سودمندی را نادیده می گیرد که مبحث جدید ما درباره استفاده از درخت‌های تصمیم برای تهیه امتیازات و احتمالات است. 

صفحه 10:
امتیازدهی *_ شکل ۶۲ تصویری از همان درخت تصمیم‌گیری شکل ۶-۱ است که از یک آرلیه درختی دیگر با وضعیت اصلاح شده استفاده شده است به طوریکه اینک درخت با اطلاعات بیشتر یعنی درصد اطلاعات در دسته یک در هر گره حاشیه نویسی شده است. حال به وضوح می‌توان دید که این درخت یک پایگاه اطلاعاتی حاوی نیمی‌از پاسخ دهنده ها و نیمی‌از غیر پاسخ دهنده ها را نشان می‌دهد چرا که گره ریشهلی دارای نسبت ۵۰ درصد است. لین وضعیت دریک مجموعه آموزشی برای یک مدل پاسخگویی با متفیر هدف دوگانه رلیج است. در شکل ۶-۱ هر گره با بیش از ۵۰ درصد پاسخ دهنده ها با عدد یک نشان داده شده است که شامل گره‌های ۱۷ و ۱۸ نیز می‌شود. شکل ۶-۲ تفاوت بین لین گره‌ها را روشن می‌سازد. در گره ۱۷ جه میزان ۸/۵۳ درصد سوایق اطلاعلتی نمایانگر واکتش است حال آنکه در گره ۱۸ این رقم به ۹/۶۶ درصد می‌رسد. معلوم است که یک سابقه اطلاعلتی در گره ۱۸ بیشتر می‌تولند نمایانگر یک پاسخ دهنده باشد تا یک سابقه داده در گره ۱۷ از نسبت اطلاعات در دسته دلخواه می‌تولن به عنوان یک امتیاز لستفاده کرد که اغلب از دسته بندی صرف مفیدتر است. برلی یک نتبجه دوگلنه. دسته بندی فقط می‌تولند داده ها رابه دو گروه تقسیم کند ولی یک امتیاز به داده ها امکان می‌دهد تا اطلاعات را از محتمل ترین تا کم احتمال ترین افراد برای عضویت در دسته دلخواه مرتب کرد. 

صفحه 11:
امتیازدهی پسیاری از کاربردها به دست آوردن یک امتیاز که قادر به رتبه بندی یک فهرست باشد کافی خواهد بود. این دستاورد نیز برای انتخاب بالاترین درصد 0) برای ارسال کانالوگ پستی و برای محاسبه صعود در ابعاد گوناگون فهرست کفایت خواهد کرد. آما در برخی کاربردهاء علم به اینکه احتمال پاسخگویی 69 از 60 بیشتر است کافی نخواهد بود. ما می خواهیم درباره احتمال پاسخ گهیی توسط 9) بیشتر بدانیم. با فرض اینکه احتمللت قبلی یک پاسخ را بدانیم آنگاه با آن می‌توانيم احتمال واکنش ناشی از امتیاز به دست آمده از داده‌هلیی را که برای تهیه درخت تصمیم‌گیری نمونه گیری شده لند محاسبه کنیم. یا اینکه می‌توانیم مدل را برای داده‌های از پیش دسته بندی شده‌ای که دارای توزیع پاسخ ها و منعکس‌کننده آمار واقمی جمعیت است ‎JS‏ ببریم: لین روش با استفاده از نسبتهای دسته هاء در برگ‌های درخت امتیازاتی را ایجاد می‌کند که اين احتمال را تشان می دهد که اطلاعات استخراج شده از یک جمعیت مشایه عضو دسته مزبور باشد. 

صفحه 12:
Cae فرض کنید که یک سوال مهم تجاری به جای آنکه عبارت: " چه کسی پاسخ خواهد داد؟" عبارت: "مقدار سفارش بعدی مشتری چقدر خواهد بود؟ " باشد. با استفاده از درخت تصمیم‌گیری می‌توان به اين سؤال نيز پاسخ داد. فرض کنید مقدار سفارش یکی از متفیرهای موجود در مجموعه مدل از پیش دسته بندی شده باشد آنگاه مقدار میانگین سفارش درهر برگ را می‌توان به عنوان مقدار سفارش تخمین زده شده برای هرگونه سابقه اطلاعلتی دسته بندی نشده‌ای به کار پرد که معیارهای آن برگ را رعلیت کند. حتی لین امکان وجود دارد که از یک متغیر هدفمند عددی برای تهیه درخت استفاده کرد. چنین درختی را درخت تخمین زننده می‌نامند. به جای اقزلیش خلوص یک متفیردسته ای» هر تقسیم انجام شده در درخت برای کاهش واربانس ارقام متخیر هدف درهر گره نونهال انتخاب می۵ لین حقیقت که از درختان می‌توان برای تخمین مقادیر پیوسته استفاده کرد ایده خوبی نیست. از یک تخمین زننده درخت تصمیم می‌توان به تعداد برگهای موجود در درخت برای ایجاد مقادیر ناپیوسته استفاده نمود. بمنظور تخمین یک متغیر پیوسته, استفاده از یک تابع پیوسته ارجحیت دارد. مدل‌های رگرسیون و شبکه‌های عصبی عموماً ‎ly‏ انجام تخمین ها مناسب ترند. 

صفحه 13:
درختان با اشکال متفاوتی وجود دارند دیخت موجود در شکل ۶-۱ از نوع دوگلنه با ابماد غیر یکسان است وبه عبارتی هر گره غیربرگی دارای دو تونهال است و برگ‌های ّن درفواصل مساوى از ريشه نيستند. درلين مويد هر كره نمايانكر يك سوال بله یا خير اسث كه ياسخ به لن تعيين مىكند يك سابقه اطلاعاتى بايد كداميك از دو مسير را طى كند تا به مرحله بعدی درخت پرسد. از آنجایی که هرگونه تقسیم چند مسیری وا می‌توان به عنوان یک سری تقسیمات دوگانه بیان نمود نیز واقعی به درختلنی با عوامل شاخه ساز بیشتر نیست. با لین حال بسیاری از ابزارهای داده‌کایی قادر به ایجاد درخت‌هایی با بیش از دو شاخه‌ند. برای مثال» برخی الگوریتم‌های درخت تصمیم با ایجاد یک شاخه برای هر دسته. متفیرهای دسته ای را تقسیم می‌کنند که لين منجر به درختلنی با تعداد مختلف شاخه ها در گره های گوناگون می‌شود. شکل ۶۳ نشاندهنده درختی است که از هردو نوع تقسیم‌بندی سه مسیری و در مسیری برای همان مسئله دسته بندی که در درخت موجود در شکلهای ۶-۱ و ۶-۲ به کار رفته استفاده م ىكند. لازم به ذكر است كه رابطداى بين تعداد شاخه‌های مجاز برای هر گره و تعداد دسته ها در متغير هدف وجود ندارد. يك درخت دوكلنه (يعنى درختى با تقسيم دوشاخه اى) را مىتوان براى دسته بندى اطلاعات به هر تعداد دسته و يك درخت با تقسيم جندكانه را مىتوان براى طبقهبندى يك متغير هدف دوكانه به كار برد. 

صفحه 14:
یک درخت تصمیم چگونه تهیه می شود * با اينکه گونه‌های زیادی از الگوریتم‌های درخت تصمیم وجود دارد ولی همه آنها از روند مشابهی پیروی می‌کنند که آن عبارت است از تقسیم مکرر داده‌ها به گروه‌های کوچک و کوچکتر به نحوی که با توجه به متغیر هدف هر نسل جدید گره‌ها خللص تر از پیشینیان خود است. در بخش عمده لين مبحث ما يك متغير دسته ای و دوگانه هدف مثل پاسخ دهنده / غیر پاسخ دهنده را مدنظر قرار می‌دهیم. اين مسئله باعث تسهیل توضیحات بدون از بین رفتن محتوا می شود. 

صفحه 15:
یافتن محل تقسیمات درابتدای فرآیند با یک مجموعه آموزشی شامل داده های از قبل دسته بندی شده سروکار داریم که همان مقدار متفیر هدف برای تمام موارد است. هدف این قرآیند تهیه درختی است که یک دسته را (يا احتمال عضویت در هر دسته) به زمینه هدف اطلاعات جدید برلساس ارقام متغیرهای ورودی اختصاص می دهد. ورودی مجزا تهیه می شود. لذا دراولین این درخت با تم داده ها در هرکره براساس عک رم اقدام بلید تصمیم گرفت کدامیک از زمینه های ورودی می تولند بهترین تقسیم را انجام دهد. بهترین تقسیم به بهترین جداکننده داده هابه صورت گروه‌هلیی گفته مي شود که در لن یک دسته در هر گروه نقش غالب را داشته باشد. لذن اتنازة اقترى براى أرزناتق بك تقسيم بالقوه را خاوض موتامتك در هنة أبن روشهاي کات و خلوصء. خلوص كم يعنى اينكه مجموعه. حاوى توزيعى از نماينده دسته هاست (بسته به كره والد) درحللى كه خلوص زياد يعنى اينكه اعضاى يك دسته مجزا غللب هستند. بهترين تقسيم تقسيمى است كه باعث افزليش ميزان خلوص دلده ها مىشود. در یک تقسیم خوب. گره‌های هم اندازه ایجاد مىشود يا حداقل كره هايى با تعداد داده هاى بسيار كم بوجود نمی‌آید. در شكل 2-5 به آسانى مى توان اين مطللب را به صورت عينى مشاهده نمود و برخى از تقسيمات خوب و بد در اينجا ارلئه شده است. 

صفحه 16:
.شکل > 6 : یک تقسیم خوب باعث افزایش خلوص تمام نونهالان مي‌گردد 

صفحه 17:
یافتن محل تقسیمات * اولین تقسیم, نامطلوب است چرا که در خلوص هیچ افزایشی حاصل نشده است. جمعیت اولیه حاوی تعداد مساوی از هردو نوع اشکال است که پس از تقسیم‌بندی نیز باز همین وضعیت در نونهال دیده می‌شود. تقسیم دومی نیز نامطلوب است چرا که علیرغم افزایش جزثی خلوص, گره خالص اعضای کمی‌دارد و خلوص نونهال بزرگتر نسبت به وللد خود افزایش بسیار کمی‌یافته است. اما تقسیم‌بندی آخر مطلوب است چرا که نونهال‌هلیی تقریبً یک اندلزه وبا خلوص بسیار بیشتری نسبت به والد خود ایجاد شده اند. *_الگوریتم‌های درخت سازی طاقت فرسا هستند. در آنها هر متفیر ورودی به نوبت برداشته می‌شود و فزایش خلوص آنها که از هر تقسی‌بندی ایجاد شده توسط آن متفیر اندزه گیری می‌شود. پس از بررسی تمام متفیرهای ورودی. آن متفیری که بهترین تقسیم را فراهم می‌سازد برای تقسیم اولیه نتخاب و دو پا چند نونهال ایجاد ميشود.اگرامکان هبچکینهتقسیمی نباشد (به دلل تعداد خیلی کم داده ها) یا اگر با تقسیم ها هیچ بهبودی حاصل نشود آنگاه آن الگوریتم به پایان رسیده است و همین گره تبدیل به گره برگی می‌شود. در غیر اینصورت الگوریتم تقسیم را انجام می دهد و روی هر نونهال اين عمل را تكرار مى كند. 

صفحه 18:
یافتن محل تقسیمات یمات براساس تأثیر آنها بر خلوص گره از نظر متغیر هدف ارزیلبی می‌شوند. این بدان معنی است که انتخاب معیار تقسیم مناسب بستگی به نوع متعیر هدف ونه به نوع متغير ورودی دارد. برای یک متفیر هدف دسته ای آزمایشهایی نظیر جینی ۰ بهره اطلاعاتی و مربع کای مناسب است. صرق نظر از اینکه متغیر ورودی که تقسیم را رکه کرده عددی باشد با دسته ای.به همین ترتیب با داشتن یک متغیر عددی پیوسته. آزمایشی نظیر کاهش واریانس با تست برای ارویابی تقسیم متاسب است صرفنظر از اینکه متفیر ورودی که نسم را له کرده دسته ای باشه با عددی. شن 

صفحه 19:
تقسیم متغیر ورودی عددی وقتی به دنبال یک تفسیم دوگلنه در یک متفیر ورودی عددی هستیم هر مقداری که متفیر در مجموعه ‎ees none el‏ کدی راك أن تقس ‎Boe SS Ee‏ تقسیمات در یک متغیر عددی به شکل ‎X<D‏ خواهند بود. تمام داده ها که مقدار 6ا (متغیر تقسیم‌بندی) در آنها کمتر از مقدار ثلبت (1) می‌باشد به یک نونهال فرستاده می‌شود و تمام داده ها كه مقدار ا آنها بیش از (0) یا مساوی آن باشد به نونهال دیگری ارسال می‌شوا يس از هر تتسيويندى ازمايشي هر ينه افزليش درخلوص که از تقسیم ناشی شنه است (در مورت وجود) اندازهكيرى مى شود. وقتى درخت تصميم امتيازدهى شد تنها استفادماى كه از ورودىهاى عددى مى شود مقايسه مقادير آنها اذ تتسيم يندى اسك ادن أرقام هركز در وزنها شرب و ياعا هم جمع تموشيند در خالى كه درسیاری از انواع ديكر مدلها لين اعمال انجام مى شود. از لين ويزكى نتيجه مهمى حاصل مىشود كه كن عدم حساسيت درختهاى تصميم نسبت يه مشاهدات برت وا توزيع چوله متغیرهای عددی است زیرا درخت فقط از رتبه‌های مقادیر عددى و نه از مقادير مطلق آنها استفاده مىكند. 

صفحه 20:
تقسیم متغیر ورودی دسته ای ساده ترین الگوریتم برای تقسیم‌بندی یک متفیر ورودی دسته ای تنها ایجاد یک شاخه جدید برای هر دسته ای است که تلبع دسته ای می‌تواند برگزیند. لذا اگر از رنگ به عنوان بهترین برای تقسیم گره ريشه استفاده شود و مجموعه آموزشی شامل داده هلیی باشد که مقادیر قرمز. نارنجی» زرد. سبز آبی. نیلی و بنفش را به خود بگیرد آنگاه هفت گره در سطح بعدی درخت وجود خواهد داشت. از این رویکرد در برخی بسته‌های نرم افزاری استفاده می‌شود اما اغلب نتلیج ضعیفی به همراه دارد. شاخه بندی های زیاد. جمعیت داده های آموزشی موجود در هر گره در پایین ترین سطح درخت را به سرعت کاهش می‌دهد و به این ترتیب تقسیمات بعدی کمتر قابل اعتماد می شوند. * یک رویکرد رلیچ دیگر گروه بندی دسته ها یی است که به صورت انفرادی نتلیج مشابهی را پیش‌بینی می‌کنند. درنگاهی دقیق تر اگر دو دسته متفیرهای ورودی به توزیع دسته های متفیر خروجی که تفاوت بارزی با هم ندارندبپردزند دو دسته را می‌توان باهم ادغام کرد. آزمایش متعارف برای تشخیص ‎ee‏ تت مريع كاى أصمته 

صفحه 21:
‎ne me 1‏ تقسيم با وجود مقادبر كمشده ‏یکی از جالبترين نكات درخت‌های تصميم توائيى آنها در مديريت مقادير كمشده در هر دو زمينه ورودى عندى يا ‎amis‏ ار کل مقادیر گمشده یا برای تخصیص مقادیر جایگزین مقادیر گمشده ترجیح داده مى شود. حذف داده ها با مقادیر گمشده معمولا باعث بوجودآمدن یک مجموعه آموزشی تحریف شده میگردد چراکه احتمالاً داده های دارای مقادیر گمشده. نمونه ای تصادفی از جمعیت نیستند. جایگزینی مقادیر گمشده با مقادیر جایگزین تخصیصی نیز لين خطر را دربردارد که اطلاعات مهم متلثر از یک مقدار گمشده در مدل نادیده گرفته شود. موارد بسیاری دیده شده است" ‎Gall eee ree ee ‏لازم جه ذکر است که درخت‌های تصمیم می‌توانند تقسیم‌بندی‌هایی را براساس مقادیر گمشده یک متفیر ورودی انجام دهند. تهی بودن یک مقدار اغلب می‌تواند ارزش پیش‌بینی کننده ای داشته باشد لذا در حذف اطلاعات حاوی مقادیر گمشده یا جایگزینی آنها با مقادیر تخصیصی عجله نکنید. ‏با اینکه بیشتر مواقع تخصیص مقدار تهی به عنوان یک دسته جداگلنه بسیار ارزشمند است اما حداقل یک رویکرد. جایگزین توسط یک نرم فزار داده‌کاوی ره شده است, هرگره تعدادی قانون تقسیم‌بندی ممکن را ذخیره میکند که هر کدام براساس یک زمینه ورودی متفاوت مدون شده اند. وقتی به یک مقدار تهی در زمینه ای که بهترین تفسیم‌ها را فراهم می‌سازد برخورد شود نرم افزار از تفسیم‌بندی جانشین برمبنای بهترین متفیر ورودی موجود. بعدی استفاده می‌کند. 

صفحه 22:
رشد درخت کامل تقسيم اوليه. دو يا جند كره نونهال راايجاد مىكند كه هركدام به روشى مشابه كره ريشه تقسيم مى شوند. دراينجا نيز تمام زمينه هاى اطلاعات ورودى به عنوان تقسيم كننده هاى نامزد به حساب مى آيند حتى زمينه هليى كه قبلاً برای تقسیمات استفاده شده اند. با این وجود. زمینه هلیی که فقط یک مقدار را به خود می‌گیرند در نظر گرفته نمی شوند چرا که راهی که بتوان از طریق آنها برای ایجاد یک تقسیم استفاده کرد وجود ندارد. یک زمینه دسته ای که به عنوان تقسیم‌گر در سطح بالای درخت به کار رفته احتمالاً به سرعت تک مقداری خواهد شد. بهترین تقسیم برای هر کدام از زمینه های باقیمانده تعیین می‌شود. وقتی که دیگر نقسیمی که خلوص یک گره داده شده را افزلیش دهد یافت نشود یا وقتی تعداد داده های یک گره به مقدار حداقل از پیش تعیین شله برسد و یا اگر ابعاد درخت به حد از پیش تعبین شده ای برسد آنگاه جستجوی تقسیم برای آن شاخه متوقف شده و كره به عنوان يك كره يرك برجسب می‌خورد سرانجام وقتى امكان يافتن تقسيم بندىهاى بيشترى در هيج جاى درخت وجود نداشته باشد درخت تصميم کامل ساخته شده است. همانطور كه خواهيم ديد اين درخت كامل معمولاً فرختى نيبت كه به بهترين شيوة يك مجموعه جدید از داده ها را دسته بندی می‌کند 

صفحه 23:
رشد درخت کامل الگوریتم‌های ساخت درخت تصمیم با تلاش در یافتن آن متفیر ورودی شروع می شوند که بهترین تقسیم‌بندی داده‌ها را درمیان گروههای دلخواه انجام می‌دهد. در همه سطوح بعدی درخت. زیرمجموعه‌های ایجاد شده در تقسیم‌بندی قبلی براساس هر قانونی که در مورد آنها بهتر عمل می‌کند تقسیم می‌شوند. رشد درخت ادامه می‌بلبد تا جلیی که دیگر نتوان راه‌های بهتری برای تقسیم بیشتر داده های ورودی پیدا کرد. اگر رابطه کاملاً تعیین‌کننده‌ای بین متفيرهاي ورودی و متغیر هدف وجود داشته باشد این تقسیم بندی بازگرا درنهایت منجر به یک درخت با برگ‌های کاملاً خالص ميشود. * تهیه نمونههليى از لين گينه آسان است اما ايجاد لين ساختار در کاربردهای بازاریلبی یا مدیریت ارتباط با مشتری چندان اتفاق نمی‌افتد. داده های رفتار مشتری تقریباً هیچگاه حاوی چنین رولبط شفاف و تعیین‌کننده ای بين ورودی‌ها و خروجی‌ها نیست. لین حقیقت که دو مشتری ازنظر متفیرهای ورودی موجود دارای مشخصات دقیقاً یکسانی باشند متضمن بروز رفتار یکسان از جلنب آنها نیست. بطور مثال یک درخت تصمیم برای مدل باسخ به یک کاتالوک ممکن است شامل برگی باشد که نمايانكر زنن بلای ۵۰ سال سن با سه بار يا بيشتر خريد در طول یک سال گذشته و مجموع خرید بالای یکصد و پنجاه هزار تومان باشد. مشتریانی که به این برگ می‌رسند. معمولاً آمیزه‌ای از پاسخ دهنده ها و غیر پاسخ دهنده ها هستند. اگر برگ مزبور دارای برچسب " پاسخ دهنده" باشد آنگاه درصد غیر پاسخ دهنده ها به عنوان "نرخ خطای" این برگ محسوب می شود. نسبت سهم پاسخ دهنده ها در این برگ به سهم پاسخ دهنده های کل جامعه را صعود در این برگ می نامند. 

صفحه 24:
رشد درخت کامل وضعیتی که در آن احتمال کشف قوانین تعیین کننده وجود دارد زمانی است که الگوهای موجود در داده‌ها متعکس کننده قوالین تجاری باشند. لین حقیقت در قللب یک مثال از یک شرکت تولیدکننده موتورهای دیزل توضیح داده می شود. در لین شرکت یک مدل درخت تصمیم برای پیش‌بینی اینکه کدام تقاضای استفاده از خدمات كارانتى تأييد مى شود تهیه گردید. بر اساس روال موجود در آن شرکت. به برخی تقاضاها به صورت خودکار و بدون بررسی بیشتر وجهی پرداخت می شد. نتایج چشمگیری حاصل شد بگونه ايکه مدل تهيه شده برای داده‌های قبلاًآزمایش نشده صد درصد دقیق بود. به عبارت دیگر, مدل, قوانین دقیقی را کشف کرد که شرکت برای دسته بندی تقاضاها بکار می‌برد. در این مورد. تکنیک شبکه عصبی با چنین موفقیتی عمل نمی کرد. البته کشف قوانین آشنا در تجارت شاید چندان مفید نباشد اما زیربنایی برای ساخت درخت‌های تصمیم در حل مشکلات قانون مدار خواهد بود. بسیاری از حوزه‌ه از فرآیندهای ژنتیکی گرفته تا صنعتی دروقع داراى قوانين زيربنليى هستند هرجند كه اين قوانین به لحاظ داده‌های درهم ريخته شلید بسیار پیچیده و مبهم باشند. انتخاب درخت‌های تصمیم هنگامی‌که قوائین زیربنایی وجود دارد گزینهای طبیعی خواهد بود. 

صفحه 25:
اندازه گیری کار آبی درخت تصمیم گیری در نگرشی کلی, کارآیی یک درخت تصمیم‌گیری هم از روی اعمال آن بر یک مجموعه آزمایشی ( که از داده های آن در ساخت درخت استفاده نشده است) و مشاهده درصد دسته بندی صحیح تعیین ميشود. لین دستاورده نرخ خطای دسته بندی درخت رابه صورت کلی فراهم می‌کند ولی باید به کیفیت هر یک از شاخه‌های درخت نیز توجه نمود. هر مسیر در درخت نمایانگر یک قانون است و برخی قوانین بهتر از سایرین ath در هر گرهاعم از گرهبرگی یا شاخه ای می‌تون موارد زیر را اندزه گیری نمود - تعداد داده های ورودی به گره نسیت داده ها در هر دسته چگونگی طبقه‌بندی داده ها اگر گره از نوع برگی باشد. درصد دسته بندی صحیح داده ها در آن گره واریانس توزیع بین مجموعه آموزشی و آزمایشی مسئله مهم دراینجا درصد دسته بندی صحیح دا های هر گره می باشد. باکمال تعجب گاهی یک گره در سطح بالای درخت. دسته بندی بهتری را درمجموعه آزمایشی انجام می‌دهد تا گره‌هایی در سطح پایین تر 

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

صفحه 27:
خلوص و پراکندگی هر دو عبارت کاهش در پراکندگی حاصل از تقسیم و افزایش خلوص حاصل از تقسیم به ایده‌ای یکسانی اشاره دارتد. انداره حلوص که دامته لن از صفر (زمانی که هیچ دو موردی در نموله در دسته یکسانی تباشند) تا یک (زملنی که تمام مورد در نمونه در یک دسته قرار گییند) است را می‌توان باکسر کردن آن از عدد یک تبدیل به مقهوم عکس آن يعنى اندازه براكندكى كرد. برخى از اندازه كيريها كه براى ارزيلبى تقسيمبندىهاى درخت تصمیم كيرى استقاده مىا شهند كمترين امتباز را به يك كره عللس و برخی ديكر بالاترين ‎GCE Ci jel‏ تمامی‌این موارد به عنوان اندازه های خلوص در نظر گرفته شده و هدف. بهینه‌سازی خلوص با به حداقل یا حداکثر رساندن اندازه انتخاب شده است. شکل ۶-۵ یک تقسیم خوب را نشان می‌دهد. گره ولد حاوی تعداد مساوی نقاط تیره و روشن است. نونهال سمت چپ حاوی نه نقطه روشن و یک نقطه تیره و نونهال سمت راست برعکس دارای نه نقطه تیره و یک نقطه روشن است. واضح است که خلوص افزایش یافته است. اما چگینه می‌توان این افزایش را اندازه گیری نمود؟ و چطور مىتوان اين تقسیم را با سایر تقسیمات مقایسه کرد؟ برای این کار نیاز به یک تعریف رسمی از خلوص است. 

صفحه 28:
شكل ه-1: یک تقسیم خوب در متفیر دسته ای دوگانه باعث افزایش خلوص می‌گردد. 

صفحه 29:
اندازه گیری خلوص برای ارزیابی تقسیمات اندازه كيرى خلوص براى ارزيابى تقسيمات در متغيرهاى توابع هدف شامل موارد زير مى باشد: - جينى (به نام پراکندگی جمعیت لیز خوانده می‌شود) آنتروپی (به نام بهره اطلاعاتی نیز خوانده می‌شود) = نسبت بهره اطلاعاتی - آزمون مجذور مربع کای - وقتی متفیر هدف از نوع عددی باشد یک رویکرد ممکن» حذف آن و استفاده از یکی از اقدامات فوق با این وجود دو اقدام رایج برای اهداف عددی وجود دارد: = کاهش واریانس - آزمون ۴ توچه اداشته باشید که ‎let‏ رعش متاس, اننازه گیری حلوص بت به دسته ای و با عددی بو عتفیر هدف دارد. از آنجا كه نوع متفیر ورودى اهميتى ندارد. تمامى يك درخت براساس روش یکسان اندازه گیری خلوص تهیه می‌شود. تقسیم نشان داده شده در نمودار ۶-۵ را مىتوان جا يك متغير ورودی عددی و یا با یک متفیر دسته ای تهیه نمود که خلوص نونهالان. صرف‌نظ از نوع تقسیم. یکسان می‌باشد. 

صفحه 30:
جینی ‎b‏ پراکندگی جمعیت یک شاخص رایج تقسیم‌بندی جینی نام درد که از نام کورادو جینی, متخصص آمار و اقتصاددان ایتالایی گرفته شده است. لین اندازه گیری که توسط زیست شناسان و بوم شناسان نیز برای مطالعه پراکندگی جمعیت استفاده می‌شود احتمال قرارگیری ده مورد انتخاب شده تصادفی از یک جمعیت یکسان را در یک دسته نشان می دهد. این احتمال برابر یک می‌باشد. برای یک جمعیت خالس اندازه گیری جیتی یک گرم به صورت ساده مجموع مریع نسبتهای دسته ها می‌باشد. برای تقسیم نشان‌داده شده در شکل ۶-۵ جمعیت وللد دارای تعداد مساوی از نقاط روشن و تیره است. یک گره با تعداد مساوی از هریک از دو دسته, دارای امتیاز /۰< ۲۰/۵ ۰/۵ است که قابل انتظار است چرا که شانس انتخاب یک دسته دو دفعه به صورت تصادفی با امکان جایگزینی, یک از دو خواهد بود. امتیاز جینی برای هر کره به وجود آمده خواهد بود. یک گره کاملاً خللص دارای امتیازجینی یک خواهد بود. گره‌ای که متوازن است دارای امتیاز جینی ۰۵ خواهد بود. براى محاسبه تأثير يك تقسیم. امتیاز جینی هر گره نونهال را محاسبه کرده و در نسبت اطلاعات که به آن گره می‌رسند ضرب کرده و سپس اعداد حاصل را باهم جمع می کنیم. در این مورده ازآنجایی که داده ها بطور مساوی درون دو گره حاصل از این تقسیم قرارمی‌گیرند و هر گره دارایامتیاز جینی مساوی است لذاامتیاز تقسیم انجام شده مساوی امتیاز هر یک از دو گره است. 

صفحه 31:
کاهش آنتروپی پا بهره اطلاعاتی بهره اطلاعاتی از یک ایده زیر کلنه برای تعریف خلوص استفاده می‌کند. اگر یک برگ کاملاً خللص باشد آنگاه دسته های لین برگ را می‌توان به راحتی اینگینه توصیف کرد که همگی آنها در یک دسته جای می گيرند. از طرف ديكر. اگر یک برگ دارای نا خالصی بالایی باشد آنگاه توصیف آن بسیار مشکل خواهد بود. تثوری اطلاعات که بخشی از علوم راینه‌ای است برای این وضعیت اندازه ای به نام آنتروپی ایجاد کرده است. در تعوری اطلاعات. آنتروپی انازه میزان بی نظلمی یک سیستم است. می توان گفت که که تعداد بیت‌های راینه‌ای مورد نیاز برای توصیف یک موقعیت یا نتیجه خاص بستگی به اندازه مجموعه نتایج ممکن دارد. می نوان آنتروپی رابه عنون اندازه تعداد سوالات بلیاخیر مورد نیز برای تعبین وضعیت سیستم در نظر گرفت. اگر ۱۶ وضعیت احتمالی وجود داشته باشد. نیاز به ضریب (16)بی یا چهار بیت بای شمارش آنها یا شناسایی یکی از آنها خواهد بود.اطلاعات اضافی باعث کاهش تعداد سوالات مورد نیاز برای تعیین وضعیت سیستم خواهد شد لذا بهره اطلاعاتی به معنای همان کاهش آنتروپی می‌باشد. از هر دو لفظ برای توصیف الگوریتم‌های درخت تصمیم استفاده می شود. 

صفحه 32:
کاهش آنتروپی یا بهره اطلاعاتی وپی يك گره خاص يك درخت تصمیم عبارت است از جمع نسبتهای داده های متعلق به يك دسته خاص براي تمام دسته هایی که در گره نشان داده شده اند که در لگاریتم پایه دو آن نسبت ضرب شده است (در واقع اين مجموع را معمولاً در 6- ضرب می کنند تا عددي مثبت به دست آید). آنتروپی يك تقسیم بصورت ‎ryt ee)‏ تعام كرعهاي ناشي از اقسيم كه بوسيله نسيت داده هلى هر كره وزن دمی شذة است به دست می آید. هنگامي‌که از کاهش آنتروپی به عنوان يك شاخص تقسيميندي استفاده شودء الكوريتم به دنبال تقسیمی می گردد که آنتروپی را تا بیشترین میزان کاهش دهد (یا اطلاعات را افزایش دهد). براي يك متغیر هدف دوگانه نظیر آنچه در شکل 0-0 آمده» فرمول بکار رفته براي آنتروپی يك گره عبارت است از : (احتمال نقاط روشن ,پا * احتمال نقاط روشن) + (احتمال نقاط تیره ,با * احتمال نقاط تیره) ۷ - مثال» احتمال نقاط تيره و احتمال نقاط روشن هردو 0.() هستند و با قرار دادن 40.60 در فرمول وپی» رابطه زیر به دست می آید: (0۵.5) 0 بط (.0) + 0.5 بسا *- 

صفحه 33:
کاهش آنتروپی یا بهره اطلاعاتی ۰ _ اولین عبارت براي نقاط روشن و عبارت دوم براي نقاط تیره است اما ازآنجايي که تعداد نقاط روشن و تیره مساوي هستند عبارت به صورت (0.()) 4 * ,پا ساده می شود که جواب 6+ به دست می آید. * حال سوال اينجا است که آنتروپی گره‌هايناشي از تقسيم چقدر است؟ يكي از نا داراي یک نقطه تيره و نه نقطه روشن است درحالي که ديگري داراي نه نقطه تیره و يك نقطه روشن مي‌باشد. به وضوح می توان ديد كه هر دو داراي سطع أنترويى يكسانى فستلد» يعنى: -0 زدي‎ 0.6 + )©.04( ‏يدا‎ O.4 (0.9)} = 0.95 + 0.06 - 0.6 ‎Same ۰‏ کل آنتروپی سیستم پس از تقسیم؛ أنتروبى هر كره را در نسبت داده هايى كه به آن كره اند ضرب کرده و همه آنها را با هم جمع کرده و متوسط أن را محاسبه نمایید. در اين مثال» هر ‎Sys ares‏ داده ها را به دست مي‌آورد به طوري که آنتروپی کل همانند آنتروپی هر گره .0 است. مجموع کاهش آنتروپی یا بهره اطلاعاتي حاصل از تقسیم نیز 00.() خواهد شد. اين شاخصی است که براي مقایسه این تقسیم با سایر نامزدها بکار مي‌رود. ‎ ‎ 

صفحه 34:
اندازه گیری آنتروبی تقسیم زمانی به مشکل بر می خورد که با یک روش تقسیم‌یندی همراه شود که با متفیرهای ورودی دسته ای با ایجاد شاخه جدیدی برای هر مقدار سروکار داشته باشد. همین مورد درباره برنامه 06 پیش آمد که یک ابزار درخت تصمیم است که توسط محقق استرالیایی جی راس کوئیتلن در دهه 1۹۸۰ تهیه شد وبه صورت بخشی از بسیاری از بسته های نرم فزاری تجاری داده‌کاوی درآمد. مشکل در اینجا کاهش تعداد دسته های نملیش داده شده در هر گره و متعاقب ٌن کاهش آنتروپی است که صرفاً از شکستن مجموعه دادههاى بزركتر به زيرمجموعههاى كوجكتر ناشى مىشود. وبى كه مربوط به تعداد شاخه‌ها باشد را اطلاعات نهادی یک تقسیم‌بندی می‌نامند. ( به یاد داشته باشید که آنتروپی به عنوان مجموع تمام شاخه‌های احتمالات هر شاخه ضرب در لوگاریتم پایه ۲ آن احتمال تعریف می‌شود) برای یک نقسیم تصادفی» مسبری, احتمال هر شاحه ۱ می‌باشد للا آنتروپی ناشی از تقسیمی که یک تقسیم ۷ مسیری باشد. عبارت ساده (/۲,)61 /۷*1 یا (61/9)ا خواهد بود. 

صفحه 35:
نسبت بهر ه اطلاعا ‎oS‏ ‏* به خاطر اطلاعات نهادی تقسیمات جندمسمریی درخت‌های تصمیم ساخته شده با استفاده از شاخص تتسیمبتدی کاهش انترويى بدون هركونه اصلاح درزمينه اطلاعات نهادى مربوط به تقسيم» يريرك و بار مى شوند. درختهاى بربرك ما تقسيمات متعدد جتدمسيرى مطلوب نیستند جراكه لين تقسيمات به تعناد كم خاده ها در هر ‎jetta eS‏ شده.و مدلهاى حاصله از اين طريق تابايدار شواهتد بود ‎ly‏ برخورد با لین مشکل. 6) و سایر مشتقات 106 که زملنی از بهره اطلاعلتی استفاده می‌کردند اینک به خاطر تقسیم پیشنهادی اطلاعات نهادی که منحصراً مرتبط با تعداد شاخه‌های ساخته شده به عنوان شاخص ارزیلبی تقسیمات پیشنهاد شده می‌باشد از نسبت کل بهره اطلاعلتی استفاده م ىكتند. لين آزمليش از كرليش به درخت‌های بسیار پربرگ که در بسته‌های نرم افزاری قبلی درخت تصمیم مشکل به حساب می‌آمد پیشگیری خواهد کرد. ‎ ‎ 

صفحه 36:
آزمون مربع کای آزمون مربع کای (*06. آزمون معنی داری آماری است که توسط آمارشناس انگلیسی کارل پیرسون در سال ۱۹۰۰ بوجود آمد. ‎coil‏ آزمون به عنوان مجموع مربع های تفاوتهای استانتارد شده بين فراوانهای مورد انتظار و مشاهته شفه برحی وقایم در نموند های نا یوسته جندگنه تریف شده استه به بیان دیگر. لین آزمون اندازه ای برای لین احتمال است که تفاوت مشاهده شده بین نمونه‌ها صرفا انفاقی است. هنگامی که برای اندازه گبری خلوص تعسیم های درخت تصمیم از این آزمون استفاده شود. مقادیر بالای مربع کای به معنای لن است که تغییرات معنی دار بوده و به صورت اتفافی و بر ‎ee ee toe‏ 

صفحه 37:


صفحه 38:


صفحه 39:


صفحه 40:


صفحه 41:


درخت های تصمیم درخت های تصميم • درخت‌هاي تصميم‌ ابزار قدرتمند و درعين حال رايجي هم براي دسته بندی و هم برای پيش‌بيني هستند. • جذابيت روش‌هاي درخ ت مبنا بيش از هرچيز ب ه اي ن واقعيت برمي‌گردد ك ه درخت‌هاي تصمي ‌م نمايانگر قوانين مي‌باشند .به راحتي مي‌توان قوانین را به زبان فارسی و یا هر زبان دیگری در آورد تا براي همگان قابل فهم باشند .همچنین مي‌توان آنها را به زبان قابل دسترسی پایگاه داده ها مانند SQLدرآورد و مثال اطالعات يك گروه خاص را استخراج نمود. • درخت تصميم‌ براي بررسي داده ها برای کسب بينش بهتر درباره روابط موجود بين تعداد زيادي از متغیرهای ورودي کاندیدا شده برای یک متغیر هدف نيز مفيد مي‌باشد .ازآنجايي كه درخت تصمي ‌م بررسي داده و مدلسازي را باهم تركيب مي‌كند ،گام اوليه قدرتمندي در فرآيند مدلسازي به شمار می روند حتی هنگامی که برای تهیه مدل نهايي از برخي تکنیکهای دیگر استفاده شود. • معموالً بين صحت مدل و شفافيت مدل توازن وجود دارد .دربرخي كاربردها ،صحت دسته بندی يا پيش‌بيني تنها مسئله مهم است ،اگر مث ً ال يك شركت پست مستقیم مدلي را دراختيار داشته باشد که با استفاده از آن بتوان به درستی پيش‌بيني کرد که کدامیک از مشتریان بالقوه احتماالً به پیشنهاد عرضه شده پاسخ خواهند داد ،آنگاه شايد براي اين شركت اهميتي نداشته باشد چرا و چگونه مدل پيش‌بيني‌كننده عمل مي‌كند. • درساير شرايط ،توانايي بیان علت يك تصمیم حیاتی است .براي مثال ،در غرامت‌هاي بیمه ،برخي ممانعت‌هاي قانوني دربرابر تبعيضها براساس متغیرهای خاصی وجود دارد .شايد يك شركت بيمه در وضعيتي قرار بگيرد كه مجبور شود به دادگاه ثابت كند هيچگونه تبعيض غيرقانوني در دادن یا ندادن خسارت به افراد مرتكب نشده است .همچنين بیشتر اين پذیرفته شده است كه وام دهنده و وام گیرنده بدانند كه بر اساس سيستم رايانه‌اي با اعطاي وام موافقت نشده است (مث ً ال درمواردي كه محاسبات رايانه‌اي نشان دهد درآمد ماهيانه متقاضي كمتر از سطح الزم است یا آنکه ظرفيت وام گيرندگان پرشده است) تا اينكه بفهمند تصميم‌گيري درباره عدم اعطاي وام توسط يك شبكه عصبي هوشمند بدون هيچگونه توضیحی در مورد عملکردش صورت گرفته است. درخت تصميم‌ چيست ؟ • درخت تصميم‌گيري ساختاري است كه براي تقسيم مجموعه‌اي بزرگ از داده های جمع‌آوري شده به مجموعه‌هاي كوچكتر زنجيره‌وار داده ها بواسطه يك سري قوانين ساده تصميم‌گيري به كار مي‌رود. • در هر تقسيم‌بندي متوالي ،اعضاي مجموعه های حاصل بيش از پيش به همدیگر مشابه می شوند .تقسيم‌بندي موجودات زنده براساس قلمروها ،سلسله مراتب پيدايش ،دسته ها ،نظام تولد ،خانواده ،جنسيت و گونه ها كه در دهه 1730توسط گياه‌شناس سوئدي كارل لينوس ابداع شد نمونه خوبي دراين زمينه است. • در قلمروي حیوانات چنانچه موجود زنده‌اي داراي ستون فقرات باشد جزو دسته مهره داران قرار مي‌گيرد .از ديگر ويژگي‌هاي مهره داران براي تقسيم‌بندي آنها به پرندگان، پستانداران ،خزندگان و غيره استفاده مي‌شود .اين دسته بندی آنقدر ادامه مي‌يابد تا در پايين‌ترين رده‌بندي ،اعضای يك گونه هم ازنظر شکل شناسی و هم توانايي زاد و ولد و پرورش بچه های خود بهم شبيه باشند. درخت تصميم‌ چيست ؟ • يك مدل درخت تصميم‌گيري از مجموعه ای از قوانين براي تقسيم جمعيت ناهمگن وسيعي به گروه‌هاي كوچكتر و همگن تر با توجه به يك متغیر هدف خاص تشکیل شده است .شايد تهیه درخت تصميم‌گيري مشابه مدل كارل لينوس كه به صورت دستي آماده شده طاقت فرسا باشد و شايد اين كار به طور خودكار با اعمال برخي الگوريتم‌هاي درخت تصميم‌گيري دريك مجموعه مدل حاوي داده‌هاي از قبل دسته بندی شده انجام شود. • معموالً متغیر هدف ،دس ته ای اس ت و از مدل درخ ت تص ميم‌گيري اس تفاده م ی شود تا احتمال تخصیص داده های موجود به هر کدام از دسته ها محاسبه شود یا برای دسته بندی داده ها با تخصیص آن به محتمل ترین دسته به کاررود .همچنين مي‌توان از درخت‌هاي تصميم‌گيري براي برآورد مقدار متغیرهای پیوسته استفاده كرد هرچند كه تکنیک های مناسبتری نيز براي انجام اين كار وجود دارد. دسته بندی • آنهايي كه با بازي بيست سؤالي آشناهستند خوب مي‌دانند چگونه يك درخت تصميم‌ ،داده‌ها را دس ته بندی مي‌كند .دراي ن بازي یک بازيكن ،مكان ،شخ ص ،ي ا شيئ ی خاص را ك ه براي ديگر شركت‌كنندگان آشنا است درنظر مي‌گيرد ولي وي سرنخی به ديگران در این رابطه نمي‌دهد .بقيه بازیكنان سعي مي‌كنند با طرح يك سري سؤاالت و گرفتن پاسخ بله يا خير آن را حدس بزنند .يك بازيكن خوب به ندرت نياز به پرسيدن همه بيست سوال مجاز در بازي دارد تا از اولين سؤال خود که "درجيب جا مي‌شود؟" به پاسخ اصلي "برج میالد" برسد. • يك درخت تصميم‌ نیز یک سری و زنجيره از این سواالت را مطرح می کند .همچون بازي بيست سؤالي ،پاسخ به اولين سؤال تعيين كننده سوال بعدي است .سؤاالت اوليه به ایجاد گروههای بسیار گسترده ای با اعضای فراوان کمک می کند و سؤاالت بعدی اين گروههای گسترده را به مجموعه‌هاي کوچکتر و كوچكتری محدود مي‌كند .اگر سؤاالت به خوبی انتخاب شوند آنگاه با یک سری محدود از سئواالت می توان به دسته بندی صحیح داده های ورودی پرداخت. دسته بندی • بازي بيست سؤالي نشان دهنده فرآيند استفاده از یک درخت براي گنجاندن امتیاز یا دسته ای در داده ها است .يك سابقه اطالعاتي در گره ريشه قرار مي‌گيرد .دراينجا براي تعيين اينكه بعدا ً اطالعات درج شده به كدام ريشه نونهال پيوند مي‌خورد يك آزمايش صورت مي‌گيرد .الگوريتم‌هاي گوناگوني براي انتخاب آزمايش اوليه وجود دارد اما هدف همه آنها يكي است و آن چیزی نیست جز انتخاب آزمايشي كه بتواند بين دسته های هدف بهترين تمايز را قايل شود .اين فرآيند آنقدر تكرار مي‌شود تا يك سابقه اطالعاتي به يك گره برگ برسد .تمام اطالعاتی كه به یک برگ در درخت تبدیل مي‌شوند به طريقي مشابه دسته بندی مي‌شوند و يك مسيرمنحصر به فرد از ريشه به برگ وجود خواهد داشت. چنين مسيري نشانگر یک قانون به كاررفته در دسته بندی سوابق اطالعاتي است. • شاید برگ‌هاي گوناگون دارای دسته بندی های مشابهي باشند هرچند كه هر برگ به علت متفاوتي دسته بندی را انجام می دهد .به عنوان مثال درختي كه ميوه جات و سبزيجات را براساس رنگ آن میوه یا سبزی دسته بندی می کند ،برگ درخت تصمیم سیب و گوجه فرنگي و گيالس می تواند رنگ قرمز را پیش بینی کند هر چند احتیاطهایی را هم باید در نظر داشت چراكه سيب‌هاي سبز، گوجه فرنگي‌هاي زرد و گيالس‌هاي سياه رنگ هم وجود دارد. • درخت تصميم‌گيري موجود در شكل 6-1فهرست گیرندگان احتمالی يك كاتالوگ خريد كاال را به صورت محتمل ( )1و غیر محتمل ( )2برای سفارش دادن پس از فرستادن کاتالوگ جدید دسته بندی می کند. • اين درخت براساس قواعد رايج در چرخه های داده كاوي تنظيم شده است بطوري كه ريشه‌ها در باال و برگ‌ها در پايين واقع شده اند .درسمت راست فوقاني هر گره یک شماره قراردارد و دسته پيش بيني شده هركدام درمركز درج شده است .قوانين تصميم‌گيري براي تقسيم هر گره روي خطوطي كه هر گره را به نونهاالن خود وصل مي‌كند چاپ شده است .تقسيم در گره ريشه‌اي که "سفارشات مادام العمر" نام دارد صورت گرفته است و شاخه سمت چپ به مشترياني اختصاص یافته که شش سفارش یا کمتر داشته اند و شاخه سمت راست به مشتریانی با 7سفارش و بيشتر تعلق گرفته است. • هر داده ای كه به گره‌ها ي برگي 17 ، 16 ، 14 ، 19يا 18برسد با عنوان متحمل به پاسخگویی دسته بندی می شود چرا که دسته پيش‌بيني شده دراين مورد یک است .مسيرهاي منتهي به اين گره‌هاي برگي قوانين درخت را بیان می کنند .به عنوان مثال ،قانون مربوط به برگ 19از این قرار است" :اگر مشتري بيش از 5/6سفارش داشته باشد و كمتر از 765روز از آخرين سفارش وی بگذرد، احتماال به کاتالوگ پاسخ خواهد داد". • شايد خوانندگان هوشيار متوجه شوند كه برخي تقسيم‌هاي درخت تصميم‌ در ظاهر تغییري نم ی کنند .مث ً ال گره‌هاي 17و 18براس اس تعداد س فارشاتي ك ه شامل سفارشاتي از دسته خوراكي‌ها است متمايز شده اند .اما هر دو گره به عنوان پاسخ دهنده تعیین شده اند .علت این مسئله آن است كه گذشته از باالتر بودن احتمال پاسخ در گره 18نسبت به گره ،17احتمال پاسخ در هر دو مورد بيش از حدي است كه براي طبقه‌بندي يك سابقه اطالعاتي به عنوان پاسخ دهنده تعيين شده است .اين مدل به عنوان یک دسته بندی کننده فقط دو خروجي صفر و يك دارد .اين دسته بندی دوگان ه ،اطالعات س ودمندي را نادیده می گیرد كه مبحث جدي د ما درباره استفاده از درخت‌هاي تصميم‌ برای تهيه امتیازات و احتماالت است. امتيازدهي • • • شكل 6-2تصويري از همان درخت تصميم‌گيري شكل 6-1است كه از يك آرايه درختي ديگر با وضعيت اصالح شده اس تفاده شده است به طوريكه اينك درخ ت با اطالعات بيشتر يعني درصد اطالعات در دسته یک در هر گره حاشيه نويسي شده است. حال به وضوح مي‌توان ديد كه اين درخت يك پايگاه اطالعاتي حاوي نيمي‌از پاسخ دهنده ها و نيمي‌از غیر پاسخ دهنده ها را نشان مي‌دهد چرا كه گره ريشه‌اي داراي نسبت 50درصد است .اين وضعيت دريك مجموعه آموزشي براي يك مدل پاسخگویی با متغیر هدف دوگانه رايج است .در شكل 6-1هر گره با بيش از 50درصد پاسخ دهنده ها با عدد یک نشان داده شده است كه شامل گره‌هاي 17و 18 نيز مي‌شود .شكل 6-2تفاوت بين اين گره‌ها را روشن مي‌سازد .در گره 17به ميزان 8/52درصد سوابق اطالعاتي نمايانگر واكنش است حال آنكه در گره 18اين رقم به 9/66درصد مي‌رسد .معلوم است كه يك سابقه اطالعاتي در گره 18بيشتر مي‌تواند نمايانگر يك پاسخ دهنده باشد تا يك سابقه داده در گره .17 از نسبت اطالعات در دسته دلخواه مي‌توان به عنوان يك امتياز استفاده کرد كه اغلب از دسته بندی صرف مفيدتر است .براي يك نتیجه دوگانه ،دسته بندی فقط مي‌تواند داده ها را به دو گروه تقسيم كند ولی يك امتياز به داده ها امکان مي‌دهد تا اطالعات را از محتمل ترین تا کم احتمال ترین افراد برای عضویت در دسته دلخواه مرتب کرد. امتيازدهي • دربسياري از كاربردها به دست آوردن يك امتياز كه قادر به رتبه بندي يك فهرست باشد كافي خواهد بود .اين دستاورد نيز براي انتخاب باالترين درصد Nبراي ارسال کاتالوگ پستي و براي محاسبه صعود در ابعاد گوناگون فهرست كفايت خواهد كرد. • اما در برخي كاربردها ،علم به اينكه احتمال پاسخگویی Aاز Bبيشتر است كافي نخواهد بود .ما می خواهیم درباره احتمال پاسخ گویی توسط Aبیشتر بدانیم .با فرض اينكه احتمالت قبلي يك پاسخ را بدانيم آنگاه با آن مي‌توانيم احتمال واکنش ناشي از امتياز به دست آمده از داده‌هایی را که براي تهیه درخت تصميم‌گيري نمونه گیری شده اند محاسبه کنیم .يا اينكه مي‌توانيم مدل را برای داده‌هاي از پيش دسته بندی شده‌اي كه داراي توزيع پاسخ ها و منعكس‌كننده آمار واقعي جمعيت است بكار ببریم. • اين روش با استفاده از نسبتهای دسته ها ،در برگ‌هاي درخت امتیازاتی را ايجاد مي‌كند كه این احتمال را نشان می دهد که اطالعات استخراج شده از يك جمعیت مشابه ،عضو دسته مزبور باشد. تخمین • فرض كنيد كه يك سؤال مهم تجاری به جاي آنكه عبارت " :چه کسی پاسخ خواهد داد؟" عبارت: "مقدار سفارش بعدي مشتري چقدر خواهد بود؟" باشد .با استفاده از درخت تصميم‌گيري مي‌توان به اين سؤال نيز پاسخ داد .فرض كنيد مقدار سفارش يكي از متغیرهای موجود در مجموعه مدل از پيش دسته بندی شده باشد آنگاه مقدار ميانگين سفارش درهر برگ را مي‌توان به عنوان مقدار سفارش تخمین زده شده براي هرگونه سابقه اطالعاتي دسته بندی نشده‌اي به کار برد که معيارهاي آن برگ را رعایت کند .حتي اين امكان وجود دارد كه از يك متغیر هدفمند عددی برای تهیه درخت استفاده كرد .چنين درختي را درخت تخمین زننده مي‌نامند .به جاي افزايش خلوص يك متغیردسته ای ،هر تقسيم انجام شده در درخت براي كاهش واریانس ارقام متغیر هدف درهر گره نونهال انتخاب مي‌شود. • این حقیقت که از درختان مي‌توان براي تخمین مقادير پیوسته استفاده كرد ایده خوبي نيست .از يك تخمین زننده درخت تصميم‌ مي‌توان به تعداد برگهای موجود در درخت براي ايجاد مقادير ناپیوسته استفاده نمود .بمنظور تخمین يك متغیر پیوسته ،استفاده از يك تابع پیوسته ارجحيت دارد .مدل‌هاي رگرسیون و شبكه‌هاي عصبي عموماً براي انجام تخمین ها مناسب ترند. درختان با اشکال متفاوتی وجود دارند • • • درخت موجود در شکل 6-1از نوع دوگانه با ابعاد غیر یکسان است و به عبارتي هر گره غيربرگي داراي دو نونهال است و برگ‌هاي آن درفواصل مساوي از ريشه نيستند .دراين مورد هر گره نمايانگر يك سؤال بله يا خير است كه پاسخ به آن تعيين مي‌كند يك سابقه اطالعاتی بايد كداميك از دو مسير را طي كند تا به مرحله بعدي درخت برسد. از آنجايي كه هرگونه تقسيم چند مسیری را مي‌توان به عنوان يك سري تقسيمات دوگانه بيان نمود نياز واقعي به درختاني با عوامل شاخه ساز بیشتر نيست .با اين حال بسياري از ابزارهای داده‌كاوي قادر به ايجاد درخت‌هايي با بيش از دو شاخه‌اند .براي مثال ،برخي الگوريتم‌هاي درخت تصميم‌ با ايجاد يك شاخه براي هر دسته ،متغیرهای دسته ای را تقسيم مي‌كنند كه اين منجر به درختاني با تعداد مختلف شاخه ها در گره هاي گوناگون مي‌شود .شكل 6-3نشاندهنده درختي است كه از هردو نوع تقسيم‌بندي سه مسیری و دو مسیری برای همان مسئله دسته بندی که در درخت موجود در شکلهای 6-1و 6-2به کار رفته استفاده مي‌كند. الزم به ذکر است که رابطه‌اي بين تعداد شاخه‌هاي مجاز براي هر گره و تعداد دسته ها در متغیر هدف وجود ندارد .يك درخت دوگانه (يعني درختي با تقسيم دوشاخه اي) را مي‌توان براي دسته بندی اطالعات به هر تعداد دسته و يك درخت با تقسيم چندگانه را مي‌توان براي طبقه‌بندي يك متغیر هدف دوگانه به كار برد. يك درخت تصميم‌ چگونه تهیه می شود • با اينكه گونه‌هاي زيادي از الگوريتم‌هاي درخت تصميم‌ وجود دارد ولي همه آنها از روند مشابهی پيروي مي‌كنند که آن عبارت است از تقسيم مكرر داده‌ها به گروه‌هاي کوچك و كوچكتر به نحوي كه با توجه به متغیر هدف هر نسل جدید گره‌ها خالص تر از پيشينيان خود است .در بخش عمده اين مبحث ما يك متغیر دسته ای و دوگانه هدف مثل پاسخ دهنده /غیر پاسخ دهنده را مدنظر قرار مي‌دهيم .اين مسئله باعث تسهیل توضیحات بدون از بین رفتن محتوا می شود. يافتن محل تقسيمات • • • • درابتداي فرآيند با يك مجموعه آموزشي شامل داده های از قبل دسته بندی شده سروكار داريم كه همان مقدار متغیر هدف براي تمام موارد است .هدف این فرآیند تهیه درختي است كه یک دسته را (یا احتمال عضویت در هر دسته) به زمینه هدف اطالعات جدید براساس ارقام متغیرهای ورودی اختصاص می دهد. اين درخت با تقسيم داده ها در هرگره براساس یک زمینه ورودی مجزا تهیه می شود .لذا دراولين اقدام بايد تصمیم گرفت کدامیک از زمینه های ورودی می تواند بهترين تقسيم را انجام دهد .بهترين تقسيم به بهترين جداكننده داده ها به صورت گروه‌هايي گفته می شود كه در آن يك دسته در هر گروه نقش غالب را داشته باشد. اين اندازه گیری برای ارزيابي يك تقسيم بالقوه را خلوص مي‌نامند .در همه این روشهای اندازه گیری خلوص ،خلوص كم يعني اينكه مجموعه ،حاوی توزيعی از نماینده دسته هاست (بسته به گره والد) درحالي كه خلوص زياد يعني اينكه اعضاي يك دسته مجزا غالب هستند .بهترين تقسيم تقسیمی است که باعث افزايش ميزان خلوص داده ها مي‌شود .در يك تقسیم خوب ،گره‌هاي هم اندازه ايجاد مي‌شود يا حداقل گره هایی با تعداد داده های بسيار كم بوجود نمي‌آيد. در شکل 6-4به آسانی می توان این مطالب را به صورت عینی مشاهده نمود و برخی از تقسیمات خوب و بد در اینجا ارائه شده است. .شکل : 6 -4یک تقسيم خوب باعث افزايش خلوص تمام نونهاالن مي‌گردد يافتن محل تقسيمات • اولين تقسيم ،نامطلوب است چرا كه در خلوص هیچ افزایشی حاصل نشده است .جمعيت اوليه حاوي تعداد مساوي از هردو نوع اشکال است که پس از تقسيم‌بندي نیز باز همين وضعيت در نونهال ديده مي‌شود .تقسيم دومي ‌نيز نامطلوب است چرا که عليرغم افزايش جزئی خلوص ،گره خالص اعضاي كمي‌دارد و خلوص نونهال بزرگتر نسبت به والد خود افزايش بسیار كمي‌يافته است .اما تقسيم‌بندي آخر مطلوب است چرا كه نونهال‌هايي تقريباً يك اندازه و با خلوص بسيار بيشتري نسبت به والد خود ايجاد شده اند. • الگوريتم‌هاي درخت سازي طاقت فرسا هستند .در آنها هر متغیر ورودي به نوبت برداشته مي‌شود و افزايش خلوص آنها كه از هر تقسيم‌بندي ایجاد شده توسط آن متغیر اندازه گیری مي‌شود .پس از بررسی تمام متغیرهای ورودي ،آن متغیری که بهترین تقسيم را فراهم مي‌سازد براي تقسيم اوليه انتخاب و دو يا چند نونهال ایجاد میشود .اگر امکان هيچگونه تقسیمی نباشد (به دليل تعداد خيلي كم داده ها) يا اگر با تقسیم ها هیچ بهبودي حاصل نشود آنگاه آن الگوريتم به پايان رسيده است و همين گره تبديل به گره برگي مي‌شود .در غیر اینصورت الگوریتم تقسیم را انجام می دهد و روی هر نونهال این عمل را تکرار می کند. يافتن محل تقسيمات • تقسيمات براساس تأثير آنها بر خلوص گره از نظر متغیر هدف ارزيابي مي‌شوند .اين بدان معنی است که انتخاب معیار تقسیم مناسب بستگي به نوع متغیر هدف و نه به نوع متغیر ورودي دارد. • برای يك متغیر هدف دسته ای ،آزمایشهایی نظير جینی ،بهره اطالعاتي و مربع کای مناسب است ،صرف نظر از اينكه متغیر ورودي که تقسیم را ارائه کرده عددی باشد يا دسته ای .به همين ترتيب با داشتن يك متغیر عددی پیوسته ،آزمايشي نظير كاهش واریانس يا تست Fبراي ارزيابي تقسيم مناسب است صرفنظر از اينكه متغیر ورودي که تقسیم را ارائه کرده دسته ای باشد يا عددی. تقسیم متغیر ورودی عددی • وقتي به دنبال يك تقسيم دوگانه در يك متغیر ورودي عددی هستیم هر مقداري كه متغیر در مجموعه آموزشی به خود می گیرد به عنوان رقم کاندیدا براي آن تقسيم در نظر گرفته می شود. • تقس يمات در ي ك متغیر عددی ب ه شكل X<Nخواهن د بود .تمام داده ه ا ك ه مقدار ( Xمتغیر تقسيم‌بندي) در آنها كمتر از مقدار ثابت Nمي‌باشد به يك نونهال فرستاده مي‌شود و تمام داده ها كه مقدار Xآنها بيش از Nیا مساوی آن باشد به نونهال ديگري ارسال مي‌شود. • پس از هر تقسيم‌بندي آزمايشي ،هر گونه افزايش درخلوص كه از تقسيم ناشي شده است (در صورت وجود) اندازه‌گيري می شود. • وقتي درخت تصميم‌ امتيازدهي شد تنها استفاده‌اي كه از ورودي‌هاي عددی می شود مقايسه مقادير آنها با نقاط تقسيم بندي است .این ارقام هرگز در وزن‌ها ضرب و يا با هم جمع نمي‌شوند در حالی كه دربسياري از انواع دیگر مدل‌ها این اعمال انجام می شود .از این ویژگی نتيجه مهمي حاصل مي‌شود‌كه آن عدم حساسيت درخت‌هاي تصميم نسبت به مشاهدات پرت و یا توزیع چوله متغیرهای عددی است زیرا درخت فقط از رتبه‌هاي مقادير عددی و نه از مقادير مطلق آنها استفاده مي‌كند. تقسيم‌ متغیر ورودي دسته ای • ساده ترين الگوريتم براي تقسيم‌بندي يك متغیر ورودي دسته ای تنها ايجاد يك شاخه جديد براي هر دسته ای است كه تابع دسته ای مي‌تواند برگزيند .لذا اگر از رنگ به عنوان بهترين براي تقسيم گره ريشه استفاده شود و مجموعه آموزشي شامل داده هایی باشد كه مقادير قرمز ،نارنجي ،زرد ،سبز، آبي ،نیلی و بنفش را به خود بگیرد آنگاه هفت گره در سطح بعدي درخت وجود خواهد داشت .از اين رويكرد در برخي بسته‌هاي نرم افزاري استفاده مي‌شود اما اغلب نتايج ضعیفی به همراه دارد. شاخه بندي های زیاد ،جمعيت داده های آموزشی موجود در هر گره در پايين ترين سطح درخت را به سرعت كاهش مي‌دهد و به اين ترتيب تقسیمات بعدی کمتر قابل اعتماد می شوند. • يك رويكرد رايج ديگر گروه بندي دسته ها یی است كه به صورت انفرادي نتايج مشابهي را پيش‌بيني مي‌كنند .درنگاهي دقيق تر اگر دو دسته متغیرهای ورودي به توزيع دسته های متغیر خروجي كه تفاوت بارزي با هم ندارند بپردازند دو دسته را مي‌توان باهم ادغام كرد .آزمايش متعارف براي تشخیص وجود تفاوت بارز توزيع‌ها باهم ،تست مربع کای است. تقسيم‌ با وجود مقادیر گمشده • يكي از جالب‌ترين نكات درخت‌هاي تصميم‌ توانايي آنها در مدیریت مقادیر گمشده در هر دو زمینه ورودی عددی یا دسته ای با در نظر گرفتن مقدار گمشده در شاخه مخصوص خود است .اين رويكرد براي حذف داده های داراي مقادیر گمشده يا براي تخصیص مقادیر جایگزین مقادیر گمشده ترجیح داده می شود .حذف داده ها با مقادیر گمشده معموال باعث بوجودآمدن يك مجموعه آموزشي تحریف شده میگردد چراكه احتماالً داده های دارای مقادیر گمشده ،نمونه ای تصادفی از جمعيت نیستند .جايگزيني مقادیر گمشده با مقادير جایگزین تخصیصی نیز اين خطر را دربردارد كه اطالعات مهم متاثر از يك مقدار گمشده در مدل نادیده گرفته شود .موارد بسياري ديده شده است كه مقدار گمشده خود مقدار پيش‌بيني‌كننده بوده است. • الزم به ذکر است که درخت‌هاي تصميم مي‌توانند تقسيم‌بندي‌هايي را براساس مقادیر گمشده يك متغیر ورودي انجام دهند .تهی بودن يك مقدار اغلب مي‌تواند ارزش پيش‌بيني کننده ای داشته باشد لذا در حذف اطالعات حاوي مقادیر گمشده يا جايگزينی آنها با مقادير تخصیصی عجله نكنيد. • با اينكه بيشتر مواقع تخصیص مقدار تهی به عنوان يك دسته جداگانه بسيار ارزشمند است اما حداقل يك رويكرد جايگزين توسط يك نرم افزار داده‌كاوي ارائه شده است .هرگره تعدادي قانون تقسيم‌بندي ممكن را ذخیره میکند که هر کدام براساس یک زمینه ورودی متفاوت مدون شده اند .وقتي به يك مقدار تهی در زمینه ای كه بهترين تقسيم‌ها را فراهم مي‌سازد برخورد شود نرم افزار از تقسيم‌بندي جانشین برمبناي بهترين متغیر ورودي موجود بعدي استفاده مي‌كند. رشد درخت کامل • تقسيم اوليه ،دو يا چند گره نونهال راايجاد مي‌كند كه هركدام به روشی مشابه گره ريشه تقسيم مي‌شوند .دراينجا نيز تمام زمینه های اطالعات ورودي به عنوان تقسيم كننده‌ های نامزد به حساب می آیند حتی زمینه هایی که قب ً ال برای تقسیمات استفاده شده اند .با این وجود ،زمینه هایی که فقط يك مقدار را به خود مي‌گيرند در نظر گرفته نمی شوند چرا كه راهي كه بتوان از طریق آنها براي ايجاد يك تقسيم استفاده كرد وجود ندارد. • يك زمینه دسته ای كه به عنوان تقسيم‌گر در سطح باالی درخت به كار رفته احتما ًال به سرعت تك مقداری خواهد شد .بهترين تقسيم براي هر کدام از زمینه های باقيمانده تعيين مي‌شود .وقتي که دیگر تقسیمی که خلوص يك گره داده شده را افزایش دهد یافت نشود يا وقتي تعداد داده های يك گره به مقدار حداقل از پیش تعیین شده برسد و يا اگر ابعاد درخت به حد از پيش تعیین شده ای برسد آنگاه جستجوي تقسيم براي آن شاخه متوقف شده و گره به عنوان یک گره برگ برچسب مي‌خورد. • سرانجام وقتی امكان يافتن تقسيم بندي‌هاي بيشتري در هيچ جاي درخت وجود نداشته باشد درخت تصمیم کامل ساخته شده است .همانطور كه خواهيم ديد اين درخت كامل معمو ًال درختي نيست كه به بهترين شيوه يك مجموعه جديد از داده ها را دسته بندی مي‌كند رشد درخت کامل • الگوريتم‌هاي ساخت درخت تصميم‌ با تالش در يافتن آن متغیر ورودي شروع می شوند كه بهترين تقسيم‌بندي داده‌ها را درميان گروههای دلخواه انجام مي‌دهد .در همه سطوح بعدی درخت ،زيرمجموعه‌هاي ايجاد شده در تقسيم‌بندي قبلي براساس هر قانوني كه در مورد آنها بهتر عمل مي‌كند تقسيم مي‌شوند. • رشد درخت ادامه مي‌يابد تا جايي كه ديگر نتوان راه‌هاي بهتری برای تقسيم بيشتر داده های ورودي پيدا كرد. اگر رابطه كام ً ال تعيين‌كننده‌اي بين متغیرهای ورودي و متغیر هدف وجود داشته باشد اين تقسيم بندي بازگرا درنهايت منجر به يك درخت با برگ‌هاي كام ً ال خالص میشود. • تهیه نمونه‌هایي از اين گونه آسان است اما ايجاد اين ساختار در كاربردهاي بازاريابي يا مدیریت ارتباط با مشتری چندان اتفاق نمي‌افتد .داده های رفتار مشتري تقريباً هيچگاه حاوي چنین روابط شفاف و تعيين‌كننده ای بين ورودي‌ها و خروجي‌ها نيست .اين حقيقت كه دو مشتري ازنظر متغیرهای ورودي موجود داراي مشخصات دقيقاً يكساني باشند متضمن بروز رفتار یکسان از جانب آنها نيست .بطور مثال يك درخت تصميم‌ براي مدل پاسخ به يك كاتالوگ ممکن است شامل برگي باشد كه نمايانگر زنان باالي 50سال سن با سه بار يا بيشتر خرید در طول يك سال گذشته و مجموع خرید باالي یکصد و پنجاه هزار تومان باشد .مشترياني كه به اين برگ مي‌رسند معموالً آميزه‌اي از پاسخ دهنده ها و غیر پاسخ دهنده ها هستند .اگر برگ مزبور داراي برچسب " پاسخ دهنده" باشد آنگاه درصد غیر پاسخ دهنده ها به عنوان "نرخ خطاي" اين برگ محسوب می شود .نسبت سهم پاسخ دهنده ها در اين برگ به سهم پاسخ دهنده های کل جامعه را صعود در این برگ می نامند. رشد درخت کامل • وضعيتي كه در آن احتمال كشف قوانين تعيين كننده وجود دارد زماني است كه الگوهاي موجود در داده‌ها منعکس کننده قوانين تجاری باشند .اين حقيقت در قالب یک مثال از یک شركت توليدكننده موتورهاي ديزل توضیح داده می شود .در این شرکت يك مدل درخت تصميم‌ براي پيش‌بيني اينكه كدام تقاضای استفاده از خدمات گارانتی تأييد می شود تهیه گردید .بر اساس روال موجود در آن شركت ،به برخي تقاضاها به صورت خودكار و بدون بررسی بیشتر وجهی پرداخت می شد. • نتايج چشمگيري حاصل شد بگونه ایکه مدل تهیه شده براي داده‌هاي قب ً ال آزمايش نشده صد درصد دقيق بود .به عبارت دیگر ،مدل ،قوانين دقيقي را کشف کرد كه شركت براي دسته بندی تقاضاها بكار مي‌برد .در اين مورد، تکنیک شبكه عصبي با چنین موفقیتی عمل نمی کرد .البته كشف قوانين آشنا در تجارت شايد چندان مفيد نباشد اما زيربنايي براي ساخت درخت‌هاي تصميم‌ در حل مشكالت قانون مدار خواهد بود. • بسياري از حوزه‌ها از فرآيندهاي ژنتيكي گرفته تا صنعتي درواقع داراي قوانين زيربنايي هستند هرچند كه اين قوانين به لحاظ داده‌هاي درهم ريخته شايد بسيار پيچيده و مبهم باشند .انتخاب درخت‌هاي تصميم‌ هنگامي‌كه قوانين زيربنايي وجود دارد گزينه‌اي طبيعي خواهد بود. اندازه‌گيري کارآیی درخت تصميم‌گيري • در نگرشي كلي ،کارآیی يك درخت تصميم‌گيري هم از روي اعمال آن بر يك مجموعه آزمايشي ( كه از داده های آن در ساخت درخت استفاده نشده است) و مشاهده درصد دسته بندی صحیح تعیین میشود. • اين دستاورد ،نرخ خطاي دسته بندی درخت را به صورت كلي فراهم مي‌كند ولي بايد به كيفيت هر يك از شاخه‌هاي درخت نیز توجه نمود .هر مسير در درخت نمايانگر يك قانون است و برخي قوانين بهتر از سايرين مي‌باشند. • در هر گره اعم از گره برگي يا شاخه اي مي‌توان موارد زير را اندازه گيري نمود: – تعداد داده های ورودي به گره – نسبت داده ها در هر دسته – چگونگی طبقه‌بندي داده ها اگر گره از نوع برگي باشد. – درصد دسته بندی صحيح داده ها در آن گره – واریانس توزيع بين مجموعه آموزشي و آزمايشي • مسئله مهم دراينجا درصد دسته بندی صحيح داده های هر گره می باشد .باكمال تعجب گاهي يك گره در سطح باالی درخت ،دسته بندی بهتري را درمجموعه آزمايشي انجام مي‌دهد تا گره‌هايي در سطح پايين تر. آزمایش 8های انتخاب بهترين تقسيم • اندازه‌گيري‌هاي متفاوتي براي ارزيابي تقسيمات بالقوه وجود دارد .الگوريتم‌هاي تهیه شده در حوزه یادگیری ماشين ي بر افزاي ش خلوص نتایج ناش ي از ي ك تقس يم تأکید دارن د حال آنكه تمرکز الگوريتم‌هاي تهیه شده در جوامع آماری به تفاوت آماري بين توزيعات گره‌هاي نونهال می باشد. • اغلب بکارگیری شاخص‌هاي تقسيم‌بندي متفاوت ،منجر به تولید درخت‌هايي می شوند كه اگرچه دارای ظاهری كام ً ال متفاوتند ولی در عملکرد مشابه هم هستند .دليلش اين است كه معموالً انواع مختلف تقسیم ها با عملكردهايي بسيار مشابه وجود دارند. • اندازه های خلوص متفاوت منجر به انتخاب نامزدهاي گوناگون مي‌شود اما از آنجايي كه تمام اين اندازه گیری ها براي بدس ت‌آوردن ايده‌ یکسانی تالش مي‌كنند مدل‌هاي حاصل شده رفتاري مشابه دارند. خلوص و پراكندگي • هر دو عبارت كاهش در پراكندگي حاصل از تقسیم و افزايش خلوص حاصل از تقسیم به ايده‌اي یکسانی اشاره دارند .اندازه خلوص که دامنه آن از صفر (زماني كه هیچ دو موردی در نمونه در دسته یکسانی نباشند) تا یک (زماني كه تمام موارد در نمونه در یک دسته قرار گیرند) است را مي‌توان باكسر كردن آن از عدد یک تبديل به مفهوم عکس آن یعنی اندازه‌پراكندگي كرد .برخي از اندازه گیریها که براي ارزيابي تقسيم‌بندي‌هاي درخت تصميم گيري استفاده می شوند كمترين امتياز را به يك گره خالص و برخی دیگر باالترين امتياز را به آن میدهند. تمامي‌اين موارد به عنوان اندازه های خلوص در نظر گرفته شده و هدف ،بهينه‌سازي خلوص با به حداقل يا حداكثر رساندن اندازه انتخاب شده است. • شكل 6-5يك تقسيم خوب را نشان مي‌دهد .گره والد حاوي تعداد مساوي نقاط تيره و روشن است .نونهال سمت چپ حاوي نه نقطه روشن و يك نقطه تيره و نونهال سمت راست برعکس داراي نه نقطه تيره و يك نقطه روشن است .واضح است که خلوص افزايش يافته است ،اما چگونه مي‌توان اين افزايش را اندازه گیری نمود؟ و چطور مي‌توان اين تقسیم را با ساير تقسیمات مقايسه كرد؟ براي اين كار نياز به یک تعريف رسمي‌ از خلوص است. شكل :6-5يك تقسيم خوب در متغیر دسته ای دوگانه باعث افزايش خلوص مي‌گردد. اندازه گیری خلوص براي ارزيابي تقسيمات • اندازه گیری خلوص براي ارزيابي تقسيمات در متغیرهای توابع هدف شامل موارد زیر می باشد: – جینی (به نام پراكندگي جمعیت نيز خوانده مي‌شود) – آنتروپی (به نام بهره اطالعاتي نيز خوانده مي‌شود) – نسبت بهره اطالعاتي – آزمون مجذور مربع کای – وقتي متغیر هدف از نوع عددی باشد يك رويكرد ممكن ،حذف آن و استفاده از يكي از اقدامات فوق است. با این وجود دو اقدام رایج براي اهداف عددی وجود دارد: – كاهش واریانس – آزمون F • توجه داشته باشید كه انتخاب روش مناسب اندازه گیری خلوص بستگي به دسته ای و یا عددی بودن متغیر هدف دارد .از آنجا که نوع متغیر ورودي اهميتي ندارد ،تمامي ‌يك درخت براساس روش یکسان اندازه گیری خلوص تهیه مي‌شود .تقسیم نشان داده شده در نمودار 6-5را مي‌توان با يك متغیر ورودي عددی و يا با يك متغیر دسته ای تهیه نمود که خلوص نونهاالن ،صرف‌نظر از نوع تقسیم ،يكسان مي‌باشد. جینی یا پراكندگي جمعیت • يك شاخص رايج تقسيم‌بندي جینی نام دارد كه از نام كورادو جینی ،متخصص آمار و اقتصاددان ايتاليايي گرفته شده است .اين اندازه گیری كه توسط زيست شناسان و بوم شناسان نيز براي مطالعه پراكندگي جمعيت استفاده مي‌شود احتمال قرارگیری دو مورد انتخاب شده تصادفی از یک جمعیت یکسان را در يك دسته نشان می دهد. براي يك جمعيت خالص ،اين احتمال برابر یک مي‌باشد. • اندازه گیری جینی يك گره ،به صورت ساده مجموع مربع نسبتهای دسته ها مي‌باشد‌‌.براي تقسيم نشان‌داده‌شده در شكل 6-5جمعيت والد داراي تعداد مساوي از نقاط روشن و تيره است .يك گره با تعداد مساوي از هريك از است كه قابل انتظار است چرا که شانس انتخاب یک دسته دو دو دسته ،داراي امتياز دفعه به صورت تصادفی با امکان جایگزینی ،يك از دو خواهد بود .امتياز جینی براي هر گره به وجود آمده خواهد بود .يك گره كام ً ال خالص داراي امتيازجینی یک خواهد بود .گره‌اي که متوازن است داراي امتياز جینی 0.5 خواهد بود. • براي محاسبه تأثير يك تقسيم ،امتياز جینی هر گره نونهال را محاسبه کرده و در نسبت اطالعات كه به آن گره مي‌رسند ضرب كرده و سپس اعداد حاصل را باهم جمع می کنیم .در این مورد ،ازآنجايي كه داده ها بطور مساوي درون دو گره حاصل از اين تقسيم قرار مي‌گيرند و هر گره داراي امتياز جینی مساوی است لذا امتياز تقسيم انجام شده مساوي امتياز هر يك از دو گره است. كاهش آنتروپی يا بهره اطالعاتي • بهره اطالعاتي از يك ايده زيركانه براي تعريف خلوص استفاده مي‌كند .اگر يك برگ كام ً ال خالص باشد آنگاه دسته های اين برگ را مي‌توان به راحتي اینگونه توصیف كرد که همگي آنها در يك دسته جاي می گیرند .از طرف دیگر ،اگر يك برگ داراي نا خالصی بااليي باشد آنگاه توصیف آن بسیار مشکل خواهد بود. • تئوری اطالعات كه بخشي از علوم رايانه‌اي است براي اين وضعيت اندازه ای به نام آنتروپي ایجاد کرده است .در تئوری اطالعات ،آنتروپی اندازه میزان بی نظمی يك سیستم است .می توان گفت که كه تعداد بيت‌هاي رايانه‌اي مورد نياز براي توصیف يك موقعیت يا نتیجه خاص بستگي به اندازه مجموعه نتایج ممکن دارد .می توان آنتروپی را به عنوان اندازه تعداد سواالت بلي/خير مورد نياز براي تعيين وضعيت سیستم در نظر گرفت .اگر 16وضعيت احتمالي وجود داشته باشد ،نياز به ضريب ) log2(16يا چهار بيت براي شمارش آنها يا شناسايي يكي از آنها خواهد بود .اطالعات اضافی باعث كاهش تعداد سؤاالت مورد نياز براي تعيين وضعيت سیستم خواهد شد لذا بهره اطالعاتي به معناي همان كاهش آنتروپی مي‌باشد .از هر دو لفظ براي توصیف الگوريتم‌هاي درخت تصميم‌ استفاده می شود. كاهش 8آنتروپی يا بهره اطالعاتي • آنتروپی يك گره خاص يك درخت تصميم‌ عبارت است از جمع نسبتهای داده های متعلق به يك دسته خاص براي تمام دسته هایی كه در گره نشان داده شده اند كه در لگاريتم پايه دو آن نسبت ضرب شده است (در واقع اين مجموع را معموالً در -1ضرب می کنند تا عددي مثبت به دست آيد) .آنتروپی يك تقسيم بصورت ساده از مجموع آنتروپی تمام گره‌هاي ناشي از تقسیم که بوسیله نسبت داده های هر گره وزن دهی شده است به دست می آید .هنگامي‌كه از كاهش آنتروپی به عنوان يك شاخص تقسيم‌بندي استفاده شود ،الگوريتم به دنبال تقسیمی می گردد که آنتروپی را تا بیشترین میزان کاهش دهد (یا اطالعات را افزایش دهد). • براي يك متغیر هدف دوگانه نظير آنچه در شکل 6-5آمده ،فرمول بكار رفته براي آنتروپی يك گره عبارت است از : (احتمال نقاط روشن × log2احتمال نقاط روشن) ( +احتمال نقاط تیره × log2احتمال نقاط تیره) × -1 • دراين مثال ،احتمال نقاط تیره و احتمال نقاط روشن هردو 0.5هستند و با قرار دادن 0.5در فرمول آنتروپی ،رابطه زیر به دست می آید: {(-1 × }log2 0.5 + (0.5) log2 0.5 )0.5 • كاهش 8آنتروپی يا بهره اطالعاتي • اولين عبارت براي نقاط روشن و عبارت دوم براي نقاط تيره است اما ازآنجايي كه تعداد نقاط روشن و تيره مساوي هستند عبارت به صورت ( -log2 × 1 )0.5ساده می شود که جواب +1به دست می آید. • حال سوال اینجا است که آنتروپی گره‌هاي ناشي از تقسيم چقدر است؟ يكي از آنها داراي یک نقطه تيره و نه نقطه روشن است درحالي كه ديگري داراي نه نقطه تيره و يك نقطه روشن مي‌باشد .به وضوح می توان دید که هر دو داراي سطح آنتروپی یکسانی هستند ،یعنی: -1 × }log2 0.9 + (0.1) log2 0.1 )0.9({ = 0.33 + 0.14 = 0.47 • براي محاسبه کل آنتروپی سیستم پس از تقسیم ،آنتروپی هر گره را در نسبت داده هایی که به آن گره رسیده اند ضرب کرده و همه آنها را با هم جمع کرده و متوسط آن را محاسبه نمایید .در اين مثال ،هر گره جديد نيمي‌از داده ها را به دست مي‌آورد به طوري كه آنتروپی کل همانند آنتروپ ی هر گره 0.47است .مجموع كاهش آنتروپی يا بهره اطالعاتي حاصل از تقسيم نيز 0.53خواهد شد .اين شاخصی است كه براي مقايسه اين تقسیم با ساير نامزدها بكار مي‌رود. نسبت بهره اطالعاتي • ش تقسيم‌بندي همراه شود که با اندازه گیری آنتروپی تقسيم زماني به مشكل بر می خورد كه با يك رو ‌ متغیرهای ورودي دسته ای با ایجاد شاخه جدیدی برای هر مقدار سروکار داشته باشد .همين مورد درباره برنامه ID3پيش آمد که يك ابزار درخت تصميم است که توسط محقق استراليايي جی راس كوئينلن در دهه 1980 تهیه شد و به صورت بخشي از بسیاری از بسته های نرم افزاري تجاري داده‌كاوي درآمد .مشكل در اينجا کاهش تعداد دسته های نمایش داده شده در هر گره و متعاقب آن کاهش آنتروپی است كه صرفاً از شكستن مجموعه داده‌هاي بزرگ‌تر به زيرمجموعه‌هاي كوچك‌تر ناشي مي‌شود. • كاهش آنتروپی که مربوط به تعداد شاخه‌ها باشد را اطالعات نهادي يك تقسيم‌بندي مي‌نامند ( .به یاد داشته باشید که آنتروپی به عنوان مجموع تمام شاخه‌هاي احتماالت هر شاخه ضرب در لوگاريتم پايه 2آن احتمال تعريف مي‌شود) .براي يك تقسيم تصادفی nمسيری ،احتمال هر شاخه n/1مي‌باشد .لذا آنتروپی ناشي از تقسیمی که یک تقسيم nمسيری باشد ،عبارت ساده ) n×1/n log(1/nيا ) log(1/nخواهد بود. نسبت بهره اطالعاتي • ب ه خاط ر اطالعات نهادي تقس يمات چندمس يري ،درخت‌هاي تص ميم‌ س اخته شده ب ا اس تفاده از شاخص تقسيم‌بندي كاهش آنتروپی بدون هرگونه اصالح درزمينه اطالعات نهادي مربوط به تقسيم ،پربرگ و بار مي‌شوند. درخت‌هاي پربرگ با تقسيمات متعدد چندمسيری مطلوب نيستند چراكه اين تقسيمات به تعداد کم داده ها در هر گره منجر شده و مدل‌هاي حاصله از اين طريق ناپايدار خواهند بود. • براي برخورد با اين مشكل C5 ،و ساير مشتقات ID3كه زماني از بهره اطالعاتي استفاده مي‌كردند اينك به خاطر تقسيم پيشنهادي اطالعات نهادي كه منحصرا ً مرتبط با تعداد شاخه‌هاي ساخته شده به عنوان شاخص ارزيابي تقسيمات پيشنهاد شده مي‌باشد از نسبت کل بهره اطالعاتي استفاده مي‌كنند .اين آزمايش از گرايش به درخت‌هاي بسيار پربرگ كه در بسته‌هاي نرم افزاري قبلی درخت تصميم‌ مشكل به حساب مي‌آمد پيشگيري خواهد كرد. آزمون مربع کای • آزمون مربع کای ( ،)X2آزمون معنی داری آماري است که توسط آمارشناس انگليسي كارل پيرسون در سال 1900بوجود آمد .اين آزمون به عنوان مجموع مربع های تفاوتهای استاندارد شده بین فراوانیهای مورد انتظار و مشاهده شده برخی وقایع در نمونه های ناپیوسته چندگانه تعريف شده است. به بيان ديگر ،اين آزمون اندازه ای برای این احتمال است که تفاوت مشاهده شده بين نمونه‌ها صرفا اتفاقی است .هنگامي‌كه براي اندازه گيري خلوص تقسیم های درخت تصميم از اين آزمون استفاده شود ،مقادير باالی مربع کای به معناي آن است كه تغییرات معنی دار بوده و به صورت اتفاقی و بر اساس شانس حاصل نشده است.