بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
تحقيق و بررسي الگوريتم C4.5 و ارتقاي آن به روشهاي جديد
چکيده - دسته بندي يکي از موضوعات مهم در حوزه داده کاوي است . اکنون روش هاي دسته بندي گوناگوني از قبيل درختان تصميم ، شبکه هاي عصبي و غيره وجود دارد. که از بين الگوريتم هاي درختان تصميم ، ID3 و C45 تاث رگذارترين الگوريتم ها هستند که بوسيله Quinlan ارائه شده است . C45 نسل بعدي الگوريتم ID3 يباشد که از روشي استنتاجي در درخت تصميم استفاده مي کند و بطور خيلي گسترده استفاده مي شود.در اين مقاله به بررسي الگوريتم C45پرداخته و بهبودهايي بر آن را ارائه خواهيم کرد.
کليد واژه - درخت تصميم ، الگوريتم C45، سود اطلاعات ، نسبت سود، اورفيتينگ .
١- مقدمه
اطلاعات مورد نياز افراد در داده هاي انبوه در دنياي حاضر پنهان شده است . داده کاوي فرايندي است که اطلاعات ارزشمند مخفي در انبوه داده را استخراج مي کند. آناليز داده کاوي شامل قوانين وابسته a، دسته بندي کردن b ، خوشه بنديc و روش هاي ديگر است . و الگوريتم داده کاوي در درخت تصميم dبه عنوان يک روش مهم براي استنتاج درخت تصميم در مجموعه اي از موارد غير عادي و نامرتب است . روش هاي زيادي از ساختار آناليز داده وجود دارد و الگوريتم سريع ID3 که در سال ١٩٧٩ توسط J.Ross.Quinlan يشنهاد شده اولين درخت تصميم تاثيرگذار در فضاي بين المللي است ، که الگوريتم دسته بندي درخت تصميم براساس بينظمي است ، سپس Quinlan نسخه بهبود يافته الگوريتم ID3، يعني C4.5 را در سال ١٩٩3 پيشنهاد ميکند. الگوريتم ID3 شامل ٦٠٠ خط کد پاسکال بود در حاليکه الگوريتم C4.5 حدود ٩٠٠٠ خط کد c دارد. الگوريتم C4.5 از نسبت سود اطلاعات eبراي انتخاب صفات تصميم استفاده مي کند، همچنين تفاوت هاي صفات پيوسته ، رفتار صفات نامعلوم و قوانين ساخت و غيره را اضافه مي کند.C4.5 يک مجموعه داده از صفات مقدا دهي شده اي را ارائه ميدهد که در آن نمونه ها بوسيله مجموعه اي از صفات تشريح شده و به يکي از مجموعه دسته هاي دو به دو متمايز تعلق دارند. C45 بدون در نظر گرفتن نمونه ها، نگاشتي را از مقادير صفات به دسته هايي که ميتوانند به دسته بندي جديد اعمال شوند، ارائه مي دهد. کاربردهاي اصلي درختان تصميم در حوزه داده هاي اسمي يا مطلق بودند اما امروزه آنها گروهي از حوزه ها با صفات عددي، نمادي و ترکيبي را گسترش دادند. بعنوان مثال ، تصميم گيري باليني، ساخت ، آناليز سند، بيوانفورماتيک ، مدلسازي داده فضايي (سيستم هاي اطلاعاتي جغرافيايي )، و عملا هر محدوده اي که مرزهاي تصميم بين دسته ها مي تواند به ازاي تجزيه هاي شبه درخت يا مناطق شناخته شده بوسيله قوانين تسخير شود در حوزه درختان تصميم قرار مي گيرد.
٢- الگوريتم C45
٢-١- ورودي و خروجي هاي C45
ورودي الگوريتم C45 مجموعه اي از داده هاي آموزشي است که هر نمونه (سطر) شامل مقاديري براي يک مجموعه ثابت از صفات (متغيرهاي مستقل ) و همچنين يک صفت دسته (متغير وابسته ) ميباشد. که يک صفت Aa يتواند به صورت پيوسته و يا گسسته بر حسب اينکه مقدار آن عددي يا اسمي است ، باشد. صفت دسته C گسسته بوده و داراي مقادير مي باشد.
هدف الگوريتم C45 اينست که از نمونه هاي آموزشي يک تابع را ياد بگيرد
اين الگوريتم نگاشتي را از مقادير صفات به يک دسته پيش گويي شده ارائه مي دهد.
در اينجا روي درختان تصميم متمرکز مي شويم ، که در آن :
- يک گره برگ با يک مقدار دسته برچسب گذاري مي شود
- يک گره آزمايش که دو يا چند خروجي دارد، که هر کدام به يک زير درخت پيوند خورده اند.
براي دسته بندي يک نمونه با استفاده از درخت تصميم ، يک نشانگر را در بالاي درخت (ريشه ) در نظر ميگيريم :
- اگر نشانگر در يک برگ است ، برچسب مرتبط با آن برگ دسته پيش گويي شده ميباشد.
- اگر نشانگر در يک گره آزمايش است ، خروجي آن آزمايش تعيين شده و نشانگر به بالاي زيردرخت آن خروجي مي رود.
C4.5تعدادي از بهبودها را براي ID3 مي سازد. بعضي از اينها عبارتند از:
. مديريت صفات پيوسته وگسسته : در مرتب سازي مديريت صفات پيوسته ،c4.5 يک مقدار آستانه ميسازد و سپس اين ليست را تقسيم ميکند به اين که مقدار صفت از مقدار آستانه بزرگتر است ، يا کوچکتر است يا مساوي آن است .
. مديريت داده آموزشي با مقادير صفات C4.5 به صفات اجازه ميدهد که مثلاً براي مقادير ازدست رفته علامتدار شوند. مقادير صفات فاقد مقدار در محاسبات سود و بينظمي به راحتي استفاده نمي شوند.
. مديريت صفات با هزينه هاي مختلف
. هرس درخت بعد از ساخت : c4.5 از طريق درخت نمايش داده مي شود آن يکبار ساخته ميشود و تلاش ميشود براي حذف شاخه ها
الگوريتم ID3 مي تواند به صورت زير خلاصه شود:
• همه صفات استفاده نشده و تعداد بينظمي مرتبط با نمونه هاي تست برداشته شود.
• انتخاب صفت براي بينظمي که مينيمم است (يا، به - صورت معادل ، سود اطلاعات ماکزيمم است .)
• ساخت گره هاي شامل اين صفات
٢-٢- شرح الگوريتم C45
C45 يک الگوريتم نيست بلکه مجموعه اي شامل الگوريتم هاي C45، C45 بدون هرس ، و قوانين C45 با ويژگي هاي زياد ميباشد. در اينجا، ابتدا الگوريتم C45 را ارائه مي کنيم و سپس به ويژگي هاي خاص آن مي پردازيم .
C45 درخت تصميم را با استفاده از مجموعه اي از داده ي آموزشي در يک مسير مثل ID3 ، با استفاده از مفهوم اطلاعات بي نظم مي سازد. داده آموزشي يک مجموعه از از نمونه هاي دسته بندي شده است . هر نمونه يک بردار است که صفات يا ويژگي هاي نمونه را نمايش مي دهند. داده آموزشي با يک بردار تکميل مي شود که دسته اي را که هر نمونه به آن تعلق دارد را نشان مي دهد. در هر گره از درخت ، C45 صفتي از داده را که سودمندترين تقسيم کننده مجموعه ي نمونه هايش به زيرمجموعه هايي ميباشد که در داخل يک دسته يا چند دسته قرار ميگيرند، انتخاب مي کند. معيارش سود اطلاعات f نرمال شده (تفاوت در بينظمي )است که از انتخاب يک صفت براي تقسيم داده نتيجه مي شود. صفات با سود اطلاعات خيلي خيلي نرمال براي بوجود آوردن تصميم انتخاب شده است . الگوريتم C45 سپس به کوچکترين زيرليست برمي گردد.
اين الگوريتم موارد اساسي کمي دارد.
- همه ي نمونه ها در ليست به يک دسته تعلق دارند.
وقتي اين اتفاق ميافتد، آن براحتي يک گره برگ براي درخت تصميم براي انتخاب دسته مي سازد.
- هيچکدام از ويژگيها هيچ سود اطلاعاتي را فراهم نمي کنند. در اين مورد، C45 يک نود تصميم برتر براي درخت با استفاده از مقدار مورد انتظار دسته مي سازد.
- به نمونه اي از دسته قبلاً ديده نشده برخورد شده است . دوباره C45 يک نود تصميم برتر براي درخت با استفاده از مقدار مورد انتظار مي سازد.
به صورت شبه کد الگوريتم به صورت زير است :
- موارد اساسي را چک مي کند.
- براي هر صفت a، سود اطلاعات حاصل از تقسيم a را پيدا مي کند.
- به بهترين a اجازه مي دهد که صفتي با بالاترين سود اطلاعات نرمال شده باشد.
- يک گره تصميم که روي بهترين a تقسيم مي شود مي سازد.
- به زير ليست بدست آمده از تقسيم بهترين a بر می گردد، و اين گره ها را به عنوان فرزندان گره اضافه مي کند.
٢-3- درخت تصميم
ساختار درخت تصميم در يادگيري ماشين ، يک مدل پيش بيني کننده مي باشد که حقايق مشاهده شده در مورد يک پديده را به استنتاج هايي در مورد مقدار هدف آن پديده نقش مي کند. تکنيک يادگيري ماشين براي استنتاج يک درخت تصميم از داده ها، يادگيري درخت تصميم ناميده مي شود که يکي از رايج ترين روش هاي داده کاوي است .
هر گره ء داخلي متناظر يک متغير و هر کمان به يک فرزند، نمايانگر يک مقدار ممکن براي آن متغير است . يک گره ء برگ ، با داشتن مقادير متغيرها که با مسيري از ريشه ء درخت تا آن گره ء برگ بازنمايي مي شود، مقدار پيش بيني شده ء متغير هدف را نشان مي دهد. يک درخت تصميم ساختاري را نشان مي دهد که برگ ها نشان دهنده ء دسته بندي و شاخه ها ترکيبات فصلي صفاتي که منتج به اين دسته بندي ها را بازنمايي مي کنند. يادگيري يک درخت مي تواند با تفکيک کردن يک مجموعه ء منبع به زيرمجموعه هايي براساس يک تست مقدار صفت انجام شود. اين فرآيند به شکل بازگشتي در هر زيرمجموعه ء حاصل از تفکيک تکرار مي شود. عمل بازگشت زماني کامل ميشود که تفکيک بيشتر سودمند نباشد يا بتوان يک دسته بندي را به همه ء نمونه هاي موجود در زيرمجموعه ء بدست آمده اعمال کرد.
درختان تصميم قادر به توليد توصيفات قابل درک براي انسان ، از روابط موجود در يک مجموعه ء داده اي هستند و ميتوانند براي وظايف دسته بندي و پيش بيني بکار روند. اين تکنيک به شکل گسترده اي در زمينه هاي مختلف همچون تشخيص بيماري دسته بندي گياهان و استراتژيهاي بازاريابي مشتري بکار رفته است .
اين ساختار تصميم گيري ميتواند به شکل تکنيک هاي رياضي و محاسباتي که به توصيف ، دسته بندي و عام سازي يک مجموعه از داده ها کمک ميکنند نيز معرفي شوند.
داده ها در رکوردهايي به شکل داده مي شوند. با استفاده از متغيرهاي سعي در درک، دسته بندي يا عام سازي متغير وابسته ء Y داريم .
انواع صفات در درخت تصميم به دو نوع صفات دسته اي و صفات حقيقي بوده که صفات دسته اي، صفاتي هستند که دو يا چند مقدار گسسته مي پذيرند (يا صفات سمبليک ) درحالي که صفات حقيقي مقادير خود را از مجموعه ء اعداد حقيقي مي گيرند(صفات پيوسته ).
٢-٤- بازنمايي درخت تصميم
درختان تصميم ، نمونه ها را با مرتب کردن آنها در درخت از گره ء ريشه به سمت گره هاي برگ دسته بندي مي کنند. هر گره ء داخلي در درخت ، صفتي از نمونه را آزمايش مي کند و هر شاخه اي که از آن گره خارج مي شود متناظر يک مقدار ممکن براي آن صفت مي باشد. همچنين به هر گره ء برگ ، يک دسته بندي منتسب مي شود. هر نمونه ، با شروع از گره ريشه ء درخت و آزمايش صفت مشخص شده توسط اين گره و حرکت در شاخه ء متناظر با مقدار صفت داده شده در نمونه ، دسته بندي مي شود. اين فرآيند براي هر زيردرختي که گره ء جديد ريشه ء آن مي باشد تکرار مي شود.
در حالت کلي، درختان تصميم يک ترکيب فصلي از ترکيبات عطفي قيود روي مقادير صفات نمونه ها را بازنمايي مي کنند. هر مسير از ريشه ء درخت به يک ، برگ متناظر با يک ترکيب عطفي صفات تست موجود در آن مسير بوده و خود درخت نيز متناظر با ترکيب فصلي همه ء اين ترکيبات عطفي مي باشد.
٢-٥- انواع آزمايشات
C45 به آزمايشات دودويي محدود نشده است ، و شامل آزمايشات با دو يا چند خروجي نيز مي شود. اگر صفت بولي باشد، آزمايش دو شاخه را بعنوان نتيجه مي دهد. و اگر صفت مطلق باشد، آزمايش چند مقداري است . اما مقادير متفاوت مي توانند بوسيله يک دسته پيش بيني شده براي هر گزينه به داخل يک مجموعه کوچکتر از گزينه ها دسته بندي شوند. اگر صفت عددي است ، در اين صورت دوباره آزمايشات دودويي مقدار و به شکل هستند، که يک آستانه مناسب تعيين شده براي آن صفت است . مقادير ممکن با مرتب سازي مقادير متمايز آن صفت تعيين شده و سپس يک آستانه از بين هر جفت از مقادير مجاور شناسايي مي شود( اگر نمونه ها d مقدار متمايز براي آن صفت دارند، 1-d آستانه انتخاب مي شوند).
٢-٦- معيارهاي انتخاب آزمايش
(چه صفتي بهترين دستهبندي کننده است ؟)
C4.5 از معي رهاي اطلاعاتي علمي از قبيل سود(کاهش در بي نظمي توزيع دسته اي به خاطر اعمال يک آزمايش ) و نسبت سود(يک روش براي اصلاح گرايش سود به آزمايشات مورد علاقه با خروجي هاي زياد) استفاده ميکند. معيار پيش فرض نسبت سود است . در هر نقطه اي از رشد درخت ، آزمايش با بهترين معيار به طور حريصانه انتخاب مي شود.
٢-٧- بي نظمي همگوني نمونه ها را اندازه گيري مي کند.
براي تعريف دقيق سود اطلاعات با تعريف معياري با نام بي نظمي g آغاز مي کنيم که (نا)خالصي يک مجموعه از نمونه ها را مشخص مي کند.
شکل زير در حالي که .p بين صفر و يک تغيير مي کنـد تابع بي نظمي مربوط به يک دسته بندي بولي را نشان مـي دهد.
شکل ١ تابع بي نظمي مربوط به يک دسته بندي بولي
تفسيري از بي نظمي از ديد تئوري اطلاعات آن است که اين عامل حداقل تعداد بيت هاي اطلاعات را که براي کدکردن دسته بندي يک عضو دلخواه S لازم است بيان مي کند. (يعني يک عضو S که به شکل تصادفي با احتمال يکتا انتخاب شده است ). اگر يک باشد، گيرنده مي داند که نمونه انتخاب شده ، مثبت خواهد بود و بنابراين نيازي نيست که هيچ پيامي فرستاده شود و بي نظمي صفر است . از طرف ديگر اگر باشد براي مشخص کردن مثبت يا منفي بودن نمونه انتخاب شده به يک بيت نياز است . اگر باشد مي توان مجموعه اي از پيام ها را به طور متوسط با کمتر از يک بيت براي هر پيام رمزگزاري کرد به شکلي که کدهاي کوتاهتر به مجموعه هاي نمونه هاي مثبت و کدهاي بلندتر به نمونه هاي منفي با احتمال کمتر را منتسب کرد.
٢-٨- سود اطلاعات ، کاهش
موردانتظار در بي نظمي را اندازه گيري مي کند.
هدف استنتاج درخت C45، کاهش اين بي نظمي مي باشد.
با داشتن بي نظمي به عنوان ناخالصي در يک مجموعه داده آموزشي، مي توان معيار موثر بودن يک صفت در دسته بندي داده هاي آموزشي را تعريف نمود. اين معيار، کاهش مورد انتظار در بي نظمي است که با تفکيک کردن نمونه ها برپايه ء اين صفت حاصل مي شود.
سود اطلاعاتي (Gain)S,A يک صفت A مربوط به مجموعه ء داده S به شکل
تعريف مي شود. که (values)A، مجموعه مقادير ممکن براي صفت A است
S يک مجموعه داده کامل را مشخص مي کند.
Sv نيز زير مجموعه اي از مجموعه داده S است که در آن صفت A مقدار v را دارد، مي باشد.
نماد نيز اندازه يک مجموعه داده را نشان مي دهد(بر حسب تعداد نمونه ها).
عمل انتخاب يک صفت جديد و افراز نمونه هاي آموزشي براي هر گره ء فرزند غيرپايانه تکرار مي شود. در اين مرحله ، فقط با استفاده از نمونه هاي آموزشي افراز شده به اين گره عمليات ، ساخت زيردرخت انجام مي شود، بنابراين هر صفت حداکثر يکبار در هر مسيري در درخت ظاهر مي شود.
اين فرآيند براي هر گره برگ جديد تا زماني که يکي از دو شرط زير برقرار شوند تکرار مي شود:
(١) تمام صفت ها تاکنون در اين مسير درخت استفاده شده اند.
(٢) نمونه هاي آموزشي افراز شده به اين گره ء برگ ، همه يک مقدار صفت هدف را دارند. (بي نظمي صفر است )
در حقيقت معيار تقسيم بندي پيش فرض ، نسبت سود است نه سود.
نسبت سود براي يک صفت A به صورت زير تعريف مي شود:
ملاحظه کنيد که (Entropy)A به اطلاعات دسته وابسته نيست و بسادگي توزيع مقادير ممکن صفت a به حساب ميآيد، در حاليکه (Gain)A اطلاعات دسته بحساب مي آيد.(همچنين يادآور ميشويم که همه محاسبات اينجا وابسته به مجموعه داده استفاده شده هستند، اگرچه اين صراحت (وضوح ) در نماد وجود ندارد.).
٢-٩- رشد درخت چطور پايان
