بخشی از مقاله
مقايسه روش هاي Bagging و Boosting براي دسته بندي داده ها
چکيده
در اين مقاله دقت روش هاي Bagging و Boosting براي دسته بندي داده ها با توجه به معيار "دقت " مقايسه شده است . تاثير عواملي مانند اندازه مجموعه داده ، تعداد صفات دودويي و عددي و درصد داده استفاده شده براي آزمون در شرايط استقلال مجموعه داده از مسئله خاص ، مورد بررسي قرار گرفته است .
نتايج بدست آمده بيانگر آن است که در اکثر موارد بهتر از روش ديگر عمل مي نمايد. براي يک داده خاص روش ها در دو حالت بررسي شده است . يک حالت زماني است که داده آموزشي و داده آزمايشي يکي باشند و حالت ديگر ٣٠% از داده آزمايشي و ٧٠% آموزشي باشد.
کلمات کليدي
Bagging و Boosting ، مجموعه داده ها، داده هاي آموزشي، داده هاي آزمايشي
١. مقدمه
اگر اندازه داده آموزش در مقايسه با بعد داده ها کوچک باشد، داده آموزش اغلب ممکن است توزيع واقعي داده را نمايش ندهد. لذا مدل طبقه بندي که بر طبق اين داده آموزشي ساخته ميشود ، ممکن است تحت تاثير قرار گرفته و اختلاف ١ بزرگي پيدا کند. در نتيجه اين طبقه بنديکننده ضعيف کارايي ضعيفي خواهد داشت . به منظور بهتر کردن طبقه بنديکننده ضعيف توسط تثبيت کردن تصميمش ، روش هايي از قبيل تنظيم ٢ يا تزريق اختلال ٣ استفاده ميشود. روش ديگر براي بهبود طبقه بنديکننده ضعيف ، استفاده از ترکيب طبقه بندي کننده هايي که از نسخه هاي تعديل شده ٤ داده آموزشي اصلي ٥ بدست آمده (مثلا توسط نمونه گيري ٦ يا وزن دهي٧) ، ميباشد. اين روش در روش باد کردن ٨ و ترقي دادن ٩ پياده سازي ميشود. در روش باد کردن ، هر شخصي از داده آموزشي نمونه برداري مي کند، خودراه انداز١٠ مستقل تصادفي مولد داده آموزشي را کپي ميکند ١١، بر روي هر يک از اين داده آموزشي که توسط خودراه انداز بوجود آمده يک طبقه بندي کننده ميسازد و آن ها را توسط حداکثر آراي ١٢ ساده در قانون تصميم نهايي جمع مي کند١٣. در روش بادکردن ، طبقه بندي کننده ها بر روي نسخه هاي وزن دهي شده داده آموزشي ساخته ميشوند، که به طور پي در پي در الگوريتم بدست آورده مي شوند. در ابتدا ، تمام اشياء به وزن هاي مساوي دارند، و اولين طبقه بنديکننده بر اساس اين مجموعه داده ساخته مي شود. سپس وزن ها بر طبق کارايي طبقه بنديکننده تغيير داده مي شوند. شيهاي طبقه بنديشده نادرست وزن هاي بيشتري ميگيرند و طبقه بنديکننده بعدي بر روي داده آموزشي مجدد وزن دهي شده اعمال مي شود. در اين روش يک ترتيبي از مجموعه هاي آموزش و طبقه بندي کننده ها بدست آورده ميشود، که سپس توسط حداکثر رايگيري ساده يا وزن دهي شده در تصميم نهايي ترکيب ميشوند.
٢. بگينگ
بگينگ (متراکم شدن خودکار) توسط لئو بريمن در سال ١٩٩٤ پيشنهاد شد که براي بهبود دادن رده بندي توسط ترکيب کردن رده بندي هاي مجموعه هاي آموزشي به طور تصادفي توليد شده ، ميباشد.
اين روش يک يک متا الگوريتم ميباشد که براي بهبود دادن يادگيري ماشين رده بندي و مدل هاي پسرفتي بر حسب پايداري و دقت رده بندي مي- باشد. اين روش همچنين واريانس را کاهش داده و به دوري از اورفيتينگ کمک مي کند. اگر چه اين روش معمولا در دخت تصميم به کار مي رود اما مي تواند در هر نوع مدل استفاده شود. بگينگ يک حالت مخصوص از روند مدل ميانگين مي باشد.
يک مجموعه آموزشي استاندارد D به اندازه n را فرض کنيد، بگينگ توسط نمونه گيري به طور يکنواخت و با جايگزيني مثال ها از D،m مجموعه آموزشي جديد Di با اندازه توليد مي شود. نمونه گيري با جايگزيني اين امکان را مي دهد که بعضي از مثال ها امکان تکرار در هر Di را داشته باشند. اگر 'n =n باشد لذا براي n بزرگ ، مجموعه Di انتظار داشتن %٦٣.٢ از مثال هاي بيهمتاي D را دارد و بقيه مثال ها تکراري مي باشند. اين نوع نمونه گيري به عنوان نمونه گيري خورراه انداز شناخته مي شود. m مدل براي استفاده کردن m نمونه هاي خودکار بالا گنجانيده شده و اين مدل ها توسط متوسط گيري خروجي (براي پسرفت ) يا راي گيري (براي رده بندي) ترکيب ميشوند.
از آنجاييکه اين روش چندين پيشگويي کننده را ميانگين ميگيرد، لذا براي بهبود مثال هاي خطي مفيد نميباشد.
٣. بوستينگ
بوستينگ يک متا الگوريتم يادگيري ماشين براي اجراي يادگيري نظارت شده مي باشد. بوستينگ بر سوال مطرح شده توسط کيرنز بنا شده است : آيا يک مجموعه يادگيرنده هاي ضعيف ميتواند يک يادگيرنده واحد قوي بسازد؟ يک يادگيرنده ضعيف يک رده بندي کننده اي تعريف مي شود که فقط اندکي با رده بندي صحيح همبسته است . در حقيقت ، يک يادگيرنده قوي يادگيرنده اي است که به طور دلخواهانه همبسته ي خوبي با رده بندي صحيح دارند.
پاسخ مثبت به سوال کيرنز يک انشعاب هاي مهم در يادگيري ماشين و آمار دارد.
٣. ١. الگوريتم هاي بوستينگ
تا موقعي که بوستينگ به صورت الگوريتمي تحميل نشود، اکثر الگوريتم هاي بوستينگ عبارتند از به طور تکراري ياد گرفتن رده بندي کننده هاي ضعيف نسبت به توزيع و اضافه کردن آن ها به رده بندي کننده قوي نهايي . موقعي که آن ها اضافه ميشوند، نوعا در بعضي روش هايي وزن دهي مي شوند که معمولا با دقت يادگيرنده ضعيف مرتبط است . بعد از اضافه کردن يک يادگيرنده ضعيف ، داده دوباره وزن دهي مي شود: مثال هايي که اشتباه رده - بندي شوند وزن بيشتري بدست آورده و مثال هايي که به درستي رده بندي شوند وزن از دست مي دهند (بعضي الگوريتم هاي بوستينگ عملا وزن مثال - هاي مکررا نادرست رده بندي شده را کاهش مي دهند مانند بوست توسط اکثريت و بوست خرمايي). بنابراين ، يادگيرنده هاي ضعيف آينده بيشتر بر مثال هايي تمرکز ميکند که يادگيرنده هاي ضعيف قبلي به نادرستي رده بندي کردند.
تعداد الگوريتم هاي بوستينگ زيادي وجود دارد. الگوريتم هاي اصيل ، پيشنهاد شده توسط رابر اسچاپير (فرموله کردن درجه اکثريت بازگشتي ) و يوآو فروند (بوست توسط اکثريت )، انطباق پذير نبودند و نتوانستند فايده ي کاملي از يادگيرنده هاي ضعيف بگيرند.
فقط الگوريتم هايي که در قاعده يادگيري محتملا تقريبا صحيح الگويتم هاي بوستينگ قابل اثبات هستند، الگوريتم هاي بوستينگ مي باشند.
الگوريتم هاي ديگر که در روح با الگوريتم هاي بوستينگ شبيه هستند گاهي اوقات "الگوريتم هاي اهرمي " ناميده ميشوند، هرچند آن ها گاهي اوقات نادرست الگوريتم هاي بوستينگ صدا زده ميشوند.
٣. ٢. آدابوست
آدابوست ، مختصر شده از بوستينگ انطباقي، يک الگوريتم ياد ماشين هست ، توسط يوآو فروند و رابرت اسچاپير به شکل قاعده درآورده شد. آن يک متا الگوريتم ميباشد و مي تواند در ترکيب با تعداد زيادي الگوريتم هاي يادگيري براي بهبود کاراييشان استفاده شود. آدابوست تا حدي وقف پذير است که ساخت رده بنديکننده هاي بعدي براي آن نمونه هايي که توسط رده بندي کننده هاي قبلي نادرست رده بندي شدند تنظيم شود. آدابوست به داده هاي نويزدار و بخش مجزا حساس مي باشد. در غير اينصورت ، آن در مسائل اورفيتينگ حساسيت کمتري نسبت به الگوريتم هاي يادگيري ديگر دارد.
آدابوست مکررا در سريهاي گرد کردن يک رده بنديکننده ضعيف ناميده مي شود. براي هر فراخواني يک توزيع وزن هاي Dt بروز رساني ميشود که اهميت مثال ها را براي رده بندي در مجموعه داده مشخص مي کند. در هر گرد کردن ، وزن هاي هر مثالي که به نادرستي رده بندي شده افزايش مي يابد (يا به طور جايگزين ، وزن هاي هر مثالي که به درستي رده بندي شده کاهش مي يابد)، به طوريکه رده بنديکننده جديد بيشتر بر روي اين مثال ها رده بندي ميکند.
