وبلاگ شخصی علیرضا پاک گوهر

3-12- رگرسیون درختی CART

طبقه‌بندي داده‌ها يک فرآيند دو مرحله‌اي است:

در مرحله اول يک مدل ساخته‌مي‌شود که مجموعه‌اي از طبقه هاي داده‌اي يا مفاهيم را مشخص مي‌کند. اين مرحله را مرحله يادگيري‌[1] گوييم که در آن يک الگوريتم طبقه‌بندي يک مدل را با تحليل يک مجموعه آموزشي[2] که مجموعه‌اي از مؤلفه‌هاي پايگاه است مي سازد و برچسب طبقه ‌هاي مربوط به اين مؤلفه‌ها را مشخص مي‌کند. يک مؤلفه X با يک بردار صفت  نمايش داده مي‌شود. فرض مي شود که هر مؤلفه به يک طبقه  از پيش تعريف شده متعلق است و طبقه  با يک صفت که به آن صفت برچسب طبقه  مي‌گوييم مشخص مي‌شود. مجموعه آموزشي به صورت تصادفي از پايگاه انتخاب مي شود.

در مرحله دوم، يادگيري از طريق يک تابع y=f(X)انجام مي‌شود که مي‌تواند برچسب  طبقه  هر مؤلفه X از پايگاه را پيش بيني کند. اين تابع به صورت قواعد طبقه‌بندي، درخت‌هاي تصميم گيري يا فرمول‌هاي رياضي است. (قديمي، يوحنا؛ عباسي، علي)

آنچه ما در اينجا براي طبقه‌بندي بررسي مي‌کنيم طبقه بندي با درختان تصميم‌گيري[3] است.

3-12-1- درخت تصميم چيست؟

يک درخت معمولا تشکيل شده از ريشه[4]، شاخه ها[5]، گره ها[6] (جايي که شاخه ها منشعب مي شوند)، و برگها[7]. درختهاي تصميم هم بصورت مشابه تشکيل شده اند از گره ها که با دايره نشان داده مي شوند و شاخه ها که با پاره خطهاي اتصال بين گره ها نشان داده مي شوند. درخت تصميم را به منظور سادگي در رسم، معمولا از چپ براست يا از بالا به پايين رسم مي کنند بطوريکه ريشه در بالا قرار بگيرد. گره اول را ريشه مي گويند. انتهاي يک زنجيره " ريشه – شاخه – گره -... گره " را يک "برگ" مي نامند. از هر يک از گره هاي داخلي (يعني هر گره اي که برگ نباشد)، دو يا چند شاخه ديگر مي توانند منشعب شوند. هر گره مربوط به يک خصوصيت معين مي باشد و شاخه ها به معناي بازه اي از مقادير هستند. اين بازه هاي مقادير بايد بخشهاي مختلف مجموعه مقادير معلوم براي خصوصيتها را به‌دست دهند.

  هنگامي که دقيقا دو شاخه از يک گره داخلي منشعب شوند (چنين درختي را درخت دوحالته[8] مي گويند)، همانطور که در شکل 1 نشان داده شده، هر يک از اين دو شاخه مي تواند نماينده يک عبارت درست يا غلط برحسب خصوصيات معلوم باشد.

شکل 1

  هر مقدار Y به يکي از گره هاي پاياني درخت (برگها) منتسب مي شود. در مورد مسئله تشخيص الگو، مقدار داده شده بصورت يک کلاس معين مي باشد و در مورد آناليز رگرسيون اين مقدار بصورت يک عدد حقيقي است.

با استفاده از يک درخت تصميم مي توانيم براي هر يک از مشاهدات X يک مقدار پيش بيني شده Y را پيدا کنيم. براي اين منظور از ريشه درخت آغاز مي کنيم، خصوصيات مربوط به ريشه را در نظر مي گيريم و تعيين مي کنيم که مقدار مشاهده شده براي خصوصيت معلوم به کدام شاخه تعلق دارد. آنگاه گره اي را در نظر مي گيريم که شاخه مورد نظر به آن مي رسد. اين کار را براي اين گره نيز انجام مي دهيم و به همين صورت ادامه مي دهيم تا به يک برگ برسيم. مقدار Y_S منتسب به برگ S ام مقدار پيش بيني شده براي X خواهد بود. بنابراين، درخت تصميم مدل وابستگي T را براي Y از X  بصورت Y=T(X) بدست مي دهد.

درختهاي تصميمي که در يک مسئله آناليز رگرسيون در نظر گرفته مي شوند، درختهاي رگرسيون ناميده مي شوند.

  درخت تصميم بايد يکپارچه باشد، يعني در مسير از ريشه تا يک برگ، نبايد بازه هاي تغيير در نظر گرفته نشده وجود داشته باشد. براي مثال .

  مي توان خصوصيات زير را براي درختهاي تصميم شناسايي نمود.

توسط درختهاي تصميم مي توان خصوصيات کمي و خصوصيات کيفي را بطور همزمان پردازش کرد.

بنابراين درخت تصميم نشان دهنده يک مدل منطقي از پديده مورد تحقيق مي باشد.

نقيصه درختهاي تصميم در واقع اين است که در موردي که تمام خصوصيتها کمي باشند، درختهاي تصميم تخمينهاي غير دقيقي را از جواب نهايي به دست مي دهند. براي مثال يک درخت رگرسيون که در شکل 3 نشان داده شده، تقريباً تخمين ثابتي را از تابع رگرسيون ارائه مي کند. از طرف ديگر، امکان جبران اين کمبود به وسيله افزايش تعداد برگها، يعني با کاهش طول "پاره خطها" يا "مرحله ها" وجود دارد.

  يک درخت تصميم با M برگ را در نظر بگيريد. اين درخت تصميم نتيجه تجزيه فضاي خصوصيات به M زيرمنطقه غير همپوشان E¹ تا E^M است بصورتي که زيرمنطقه E^S نشان دهنده برگ S ام (شکل4) مي باشد. هر زير منطقه چگونه شکل گرفته است؟

شکل 3

E^s به صورت حاصلضرب دکارتي   تعريف شده که در آن E^s_j  تصوير E^s بر روي j امين خصوصيت است.  E^s_j در مسير بعدي به دست مي آيد. اگر خصوصيت X_j   در مسير از ريشه به S امين برگ اصلا اتفاق نيافتد، آنگاه E^s_j با بازه اي از تعريفات خصوصيت X_j  طلاقي خواهد نمود. در غير اينصورت، E^s_j   برابر با سطح مشترک بين تمام زيرمنطقه هاي خصوصيت X_j مي باشد که در مسير ريشه تا S امين برگ قرار دارند.

شکل 4

  فرض کنيد که برخي مشاهدات بصورت   را داشته باشيم که هر يک از اين مشاهدات (برحسب X) به يکي از زير مجموعه هاي در نظر گرفته شده مربوط باشد. يعني، . مجموعه داده هاي مربوط به E^S را DATA^S مي ناميم، و تعداد مشاهدات را با N^S نشان مي دهيم. فرض کنيد N^S_i تعداد مشاهدات از DATA^S باشد که به کلاس i ام تعلق دارد که به مسئله تشخيص الگو PRP شهرت دارد. (پاك‌گوهر، 1385)

3-12-2-  ساخت درخت تصميم

  روش تشکيل دادن يک درخت تصميم از داده هاي آماري را ساختن درخت نيز مي گويند. در اين قسمت با برخي روشهاي ساخت درخت و نيز روشهاي تعيين کيفيت درختها آشنا مي شويم.

  براي هر منظور خاص در تحليل آماري تعداد بسيار زيادي از انواع درختهاي تصميم وجود دارد که بسياري از آنها حتي شناخته نشده اند. يک سئوال وجود دارد: کدام درخت بهترين است و چگونه آنرا پيدا کنيم. براي پاسخ به قسمت اول، روشهاي مختلف تعريف پارامترهايي را در نظر مي گيريم که کيفيت درخت را تعيين مي کنند. از نظر تئوري، مي توانيم خطاي مورد انتظار در پيش بيني را به عنوان پارامتر پايه در نظر بگيريم. به هرحال درعمل اين قانون هنوز به عنوان اصل شناخته نشده است. بنابراين فقط مي توانيم کيفيت را با توجه به مجموعه اي از مشاهدات که به ما داده شده تخمين بزنيم. (پاك‌گوهر، عليرضا، 1385)

پارامترهاي کيفيت يک درخت

  فرض کنيم يک درخت تصميم و نمونه اي از N شيئ داريم. امکان انتخاب دو نوع اصلي از پارامترها توضيح دهنده کيفيت يک درخت وجود دارد. نوع اول پارامترهاي دقت هستند و نوع دوم پارامترهاي پيچيدگي درخت.

  پارامترهاي دقت يک درخت را مي توان با کمک نمونه تعريف کرد و کيفيت تقسيم اشياء در کلاسهاي مختلف (در مورد يک مسئله تشخيص)، يا اندازه بزرگي خطا (در مورد يک مسئله آناليز رگرسيون) را تعيين نمود.

  عدد نسبي (فراواني) خطاها به معناي کسري از اشياء است که توسط درخت بطور اشتباه به يک کلاس نسبت داده شده:

که در آن

که در آن نيز K تعداد کلاسها مي باشد.

واريانس نسبي براي يک درخت تصميم را مي توان از فرمول زير محاسبه نمود :

که در آن    واريانس باقيمانده است،

واريانس اوليه بصورت :

تعريف مي شود و داريم :

 پارامترهاي پيچيدگي خصوصيات شکل درخت را تعيين مي کنند و به نمونه بستگي ندارند.

  براي مثال، پارامترهاي پيچيدگي يک درخت به صورت تعداد برگهاي درخت، تعداد گره هاي داخلي آن و بيشترين طول مسير از ريشه تا يک برگ مي باشند.

  همچنين مي توان از طول يک مسير خارجي استفاده نمود که به صورت تعداد شاخه هايي تعريف مي شود که يک درخت کامل را تشکيل مي دهند.

  پارامترهاي پيچيدگي و دقت با هم داراي پيوستگي داخلي هستند: به عنوان يک قانون مي توان گفت درختي که پيچيده تر باشد داراي دقت بيشتري است (در درختي که هر برگ آن نماينده يک شيئ باشد بيشترين ميزان دقت وجود دارد).

  اگر ديگر شرايط يکسان باشند، درختي که پيچيدگي کمتري داشته باشد، ترجيح داده مي شود. چنين درختي مدل ساده تري از پديده مورد تحقيق را بدست مي دهد و تفسيرهاي بعدي (توضيح مدل) را آسان مي کند. علاوه بر اين، از تحقيقات تئوري چنين بر مي آيد که در صورت کوچک بودن اندازه نمونه (در مقايسه با تعداد خصوصيات) درختهايي که بيش از حد پيچيده باشند ناپايدار هستند يعني داراي تعداد خطاهاي بيشتري براي مشاهدات جديد خواهند بود.

  از طرف ديگر، روشن است که يک درخت خيلي ساده نيز امکان رسيدن به پيش بيني خوبي را فراهم نمي کند. بنابراين، در انتخاب بهترين درخت تصميم بايد به يک "توافق" معيني بين پارامترهاي دقت و پيچيدگي برسيم.

  براي رسيدن به چنين توافقي مثلا مي توانيم از اين شرط براي کيفيت استفاده کنيم:  که در آن p  يک پارامتر دقت و a يک پارامتر معلوم هستند. بهترين درخت با توجه به اين شرط بايد داراي کمترين مقدار Q باشد.

  از روشي که در آن بيشترين پيچيدگي مجاز براي درخت تعيين مي شود، بطور همزان با جستجوي دقيقترين درخت هم مي توان استفاده نمود.(همان منبع)

تخميني از کيفيت بر روي يک نمونه کنترل

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

  در يک مسئله تشخيص، تحت شرايط مستقل بودن مشاهدات، فراواني خطاها از توزيع دو جمله اي بدست مي آيد. بنابراين، با دانستن تعداد خطاها در نمونه کنترل مي توان بازه اطميناني را پيدا کرد که به احتمال معيني تعداد خطاهاي کلاس بندي اشتباه به آن بازه تعلق دارد. (همان منبع)

  روشهاي ساخت درخت تصميم

  روشهاي موجود (چندين روش وجود دارد) را مي توان به دو گروه اصلي تقسيم نمود. گروه اول شامل روشهايي براي ساختن درخت با ميزان بهينگي صريح (با توجه به شرط کيفيت درخت)، و گروه دوم شامل روشهاي ساخت درخت با ميزان تقريبي بهينگي مي شوند.

  مسئله جستجو بدنبال درخت بهينه مي تواند به مسئله برنامه ريزي گسسته (discrete programming) يا انتخاب از ميان تعداد محدود (ولي بسيار بزرگ) منجر شود. اين از اين حقيقت ناشي مي شود که براي يک نمونه آموزشي محدود، تعداد محدودي حالت شاخه ها (شکل زير) براي هر خصوصيت وجود دارد.

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

  اجازه بدهيد تمام اعمال پايه بر روي درخت تصميم را در نظر بگيريم. روشهاي ساخت درخت شامل توالي رشته اي از اين اعمال خواهد بود. (همان منبع)

عمل شاخه بندي (تقسيم)

  عمل شاخه بندي  پايه ساخت درخت است. يک گره از درخت و يک خصوصيت X_j را در نظر مي گيريم. فرض کنيد بازه تعريف اين خصوصيت به تعداد L_j زير مجموعه تقسيم شود (در زير روشهاي انتخاب چنين زير مجموعه هايي خواهد آمد). در مورد خصوصيتهاي کمي، اين زير مجموعه ها گروهي از زير بازه هاي مجزا هستند، در مورد خصوصيتهاي کيفي، زير مجموعه اي از مقادير، و در مورد داده هاي خصويات ترتيبي زير مجموعه هايي شامل مقادير همسايه مي باشند.

  فرض کنيد به هر يک از اين زير مجموعه ها يک شاخه نسبت دهيم که از گره فعلي (مادر) به سمت يک گره جديد که (فرزند) ناميده مي شود امتداد مي يابد. بنابراين، گره به تعداد L_j  گره جديد "منشعب" شده ("تقسيم شده") است (شکل5).

شکل 5

  توجه کنيد که براي درختهاي باينري L_j هميشه برابر با 2 است. اگر L_j براي يک درخت هميشه برابر با 3 باشد آن درخت را "سه گانه" مي ناميم. اگر L_j  هميشه برابر با 4 باشد يک درخت "چهارگانه" خواهيم داشت.

  چگونه بازه اي از تعريف را تقسيم کنيم؟ مجموعه اي از مشاهدات را براي گره مورد نظر بدست مي آوريم و مقادير X_j را براي اين مشاهدات در نظر مي گيريم.

شکل 6

  يک خصوصيت کمي را در نظر بگيريد. در اين مورد، مرزها در وسط بازه هاي بين مقادير همسايه قرار دارند و تقسيم با توجه به اين مرزها صورت مي گيرد (شکل 6).

  براي مثال در شکل 7 (مقادير مشاهده شده براي خصوصيات با Ä  نشان داده شده اند) براي يک درخت باينري (دوحالته) مي توان شرايط زير را براي تقسيم در نظر گرفت: X_j < 0.5  يا X_j >= 0.5   و  X_j  < 1.5   يا  X_j >= 1.5. اگر خصوصيت کيفي باشد، آنگاه تقسيمات بر حسب مقادير خصوصيت صورت مي گيرد. براي مثال، اگر X_j به معناي يک کشور باشد مي توان شرايط تقسيم بندي زير را در نظر گرفت: } کانادا، مکزيک، امريکاX_j Î {    يا   } برزيل، آرژانتين X_j Î {

شکل 7

  در موردي که تعداد مقادير زياد باشد تعداد شرايط تقسيم بندي بيش از حد زياد مي شود. بنابراين براي تسريع فرايند ساخت درخت، تمام شرايط را در نظر نمي گيريم بلکه از برخي از آنها استفاده مي کنيم (براي مثال، "کانادا" X_j =    يا    "کانادا" X_j ¹).

  در مورد خصوصيات ترتيبي، شرايط تقسيم شامل مقادير ترتيبي هستند. براي مثال، اگر X_j  درجه نظامي باشد، تقسيم بندي مي تواند بصورت [ گروهبان يکم – سرباز ] X_j Π  يا   [سرگرد- ستوان ] X_j Π باشد.

  براي خصوصيتهاي کيفي يا ترتيبي مواردي مي تواند وجود داشته باشد (هنگاميکه اندازه نمونه مشاهدات کوچک است) که مجموعه مقادير مشاهدات خصوصيت انجام شده براي يک گره تنها قسمتي از کل بازه تعريف مقادير خصوصيت را در بر بگيرد. در چنين مواردي لازم است که بقيه مقادير را به يک شاخه جديد نسبت دهيم. تا در پيش بيني نمونه کنترل که داراي چنين مقداري باشد بتوانيم تعيين کنيم که اين مقدار به کدام شاخه تعلق دارد. براي مثال، ممکن است مقادير معلوم را با توجه به بيشترين تعداد مشاهدات به شاخه ها نسبت دهيم. (همان منبع)

عمل تعريف درجه توافق براي شاخه بندي گره (قانون توقف)

  يک گره آزاد (گره اي که شاخه اي از آن منشعب نشده) را در درخت در نظر بگيريد، که مشخص نيست آيا اين گره يک برگ است يا اينکه بايد شاخه بندي شود. زير مجموعه مشاهدات مربوط به اين گره را در نظر مي گيريم. گره ها را به دو دسته تقسيم مي کنيم: اول آنکه اين مقادير همگن باشند، يعني اساسا متعلق به يک کلاس باشند (مسئله تشخيص الگو RP). يا اينکه واريانس Y آنها به اندازه کافي کوچک باشد (مسئله آناليز رگرسيون RA). موردي که در آن مقدار خصوصيت براي تمام مشاهدات يکسان باشد نيز به اين مورد مربوط مي شود. دوم آنکه تعداد مشاهدات کافي نباشد.

گره اي که داراي شرايط شاخه بندي نباشد يک برگ ناميده مي شود.

  براي تعريف درجه توافق مي توان پارامترهاي زير را تعريف نمود: خطاي مجاز براي گره (مسئله PR)، واريانس مجاز (مسئله RA) و آستانه براي مشاهدات کيفي. (همان منبع)

الگوريتم درخت‌هاي تصميم گيري

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

عملکرد الگوريتم فوق به شرح ذيل است:

· الگوريتم با پارامترهاي D، attribute_list، Attribute_selection_method فراخواني مي‌شود. D در واقع يک بخش[9] داده‌اي است. در ابتدا D شامل مجموعه آموزشي و برچسب طبقه ‌هاي متناظر با آنها است. Attribute list فهرستي از صفات موجود در مؤلفه‌ها است.  Attribute_selection_methodيک روال ابتکاري[10] است که بهترين صفت را براي جداکردن مؤلفه‌ها براساس طبقه ها مي‌دهد. اين متد از يک معيار انتخاب صفت مانند information gain يا gini index استفاده مي کند که در ادامه شرح داده مي شود. 

·  درخت در گام اول با يک گره تنهاي N که کل مجموعه آموزشي داده ها را نشان مي دهد ايجاد مي شود.

· اگر مؤلفه‌هاي D همه از يک طبقه  باشند گره N يک برگ خواهد بود و با آن طبقه  برچسب مي خورد(گام 2 و 3). گام 4 و 5 شرايط خاتمه هستند که در ادامه شرح داده مي شوند.

· در غير اين صورت Attribute_selection_method فراخواني مي‌شود تا معيار شکاف[11] را مشخص کند. معيار شکاف مشخص مي‌کند که کدام صفت بايد در گره N مورد آزمون قرار گيرد. معيار شکاف همچنين بيان مي‌کند که چه شاخه‌هايي بايد از گره N با توجه به آزمون مربوطه، خارج شوند. به عبارت ديگر معيار شکاف، صفت يا نقطه شکاف را تعيين مي‌کند. نقطه شکاف، D را به يکسري بخش تبديل مي‌کند. اين بخش ها بايد تا حد ممکن خالص[12] باشند به اين معني که همه مؤلفه هاي موجود در يک بخش بايد مربوط به يک طبقه  باشند.(Jiawei Han and Micheline Kamber,2001)

· گره N با معيار شکاف برچسب مي‌خورد(گام 7). يک شاخه از گره N به هر يک از خروجي‌هاي معيار شکاف مي رود. مؤلفه‌هاي D متناظراً بخش ‌بندي مي‌شوند(گام10و11).

·  الگوريتم فرايند مشابهي را به صورت بازگشتي در هر يک از بخش ‌هاي حاصل شده دنبال مي‌کند(گام 14).

·  بخش بندي بازگشتي در صورتي که يکي از شرايط زير بوجود آيد متوقف مي‌شود:

1. اگر تمام مؤلفه ها در بخش D متعلق به يک طبقه  باشند(گام 2 و 3).

2. صفتي براي بخش ‌بندي بيشتر وجود نداشته باشد(گام 4).در اين حالت گره N به يک برگ تبديل مي شود و برچسب طبقه  آن طبقه  متداول در D خواهد بود.

3. مؤلفه اي براي يک شاخه وجود نداشته باشد، در واقع اگر يکي از بخش ‌هاي D مانند D_j تهي باشد(گام 12). در اين موارد يک برگ با برچسب طبقه  متداول در D ايجاد مي شود(گام 13).(Jiawei Han and Micheline Kamber,2001)

معيارهاي انتخاب صفت:

معيارهاي مختلفي براي تعيين صفتي که شکاف بايد بر اساس آن انجام شود وجود دارد مانند:

·  بهره اطلاعاتي[13]

·  نسبت بهره[14]

·  شاخص جيني[15]

ما در اينجا تنها به معرفي بهره اطلاعاتي مي‌پردازيم.

بهره اطلاعاتي:

اطلاعات مورد نياز براي طبقه بندي يک مؤلفه در D برابر:

است که در آن p_i احتمال آن است که يک مؤلفه دلخواه در D متعلق به طبقه C_i باشد که اين احتمال به صورت |D|/|C_i,D| تخمين زده مي‌شود(|D| و | C_i,D | تعداد مؤلفه‌ها در D و C_i,D را نشان مي‌دهد). تعداد طبقه هاي موجود  m است. در واقع(Info D)همان آنتروپي يا بي نظمي[16] مي‌باشد.

فرض مي‌کنيم صفت A داراي v مقدار متمايز به صورت {a₁,a₂,…,a_v} باشد يا به عبارت ديگر A  يک صفت گسسته باشد. اگر بخواهيم D را بر حسب صفت A بشکافيم v بخش يا زيرمجموعه مانند {D₁,D₂,…,D_v} حاصل مي شود که در آن D_j شامل مؤلفه‌هايي از D است که مقدار صفت A در آنها برابر a_j است. اگر فرض کنيم که D در گره‌اي چون N قرار داشته باشد آنگاه اين بخش‌ها متناظر با شاخه‌هايي هستند که از N خارج مي‌شوند. اطلاعات مورد نياز براي طبقه‌بندي يک مؤلفه از D بر حسب صفت A برابر:

است. عبارت |D_j|/|D| در واقع وزن بخش j  را نشان مي‌دهد.

اطلاعات حاصل از انشعاب بر حسب صفت A را به صورت زير تعريف مي‌کنيم:

هر چه مقدار بهره صفتA (Gain(A)) بيشتر باشد يا به عبارت ديگر هر چه InfoA(D))) کمتر باشد صفت A به عنوان صفت شکاف انتخاب مي شود.(Jiawei Han and Micheline Kamber,2001)