مقاله داده کاوی و یادگیری ماشین : مروری بر دسته بندی کننده ها

بخشی از مقاله

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***

داده کاوي و يادگيري ماشين : مروري بر دسته بندي کننده ها

خلاصه

همزمان با عصر اطلاعات ، انقلاب ديجيتالي، استفاده از برخي فناوريها را براي تجزيه و تحليل مقدار زيادي از

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

کلمات کليدي: داده کاوي، يادگيري ماشين ، دسته بندي، دسته بندي کننـده ، يـادگيري جمعـي، ماشـين بـردار پشـتيبان ، درخت تصميم ، جنگل تصادفي، نزديک ترين همسايه ، Bagging،Boosting

١. مقدمه
همزمان با عصر اطلاعات ، انقلاب ديجيتالي، استفاده از برخي فناوريها را براي تجزيه وتحليل مقدار زيادي از اطلاعات ضروري ساخته است . داده کاوي يک فن براي معنا بخشيدن به داده هاي در دسترس است . اين فن در سال هاي اخير بيشتر از گذشته محبوب شده است . داده کاوي مجموعه اي از فنون است که به شخص امکان ميدهد تا وراي داده پردازي معمولي حرکت کند و به استخراج اطلاعاتي که در انبوه داده ها مخفي يا پنهان است کمک ميکند. فرآيند استخراج داده ها، از ابزارهاي تحليلي براي تعيين رابطه ميان داده ها در پايگاه داده هاي بزرگ بهره ميبرد. داده کاوي، دربرگيرنده ي روش هاي يادگيري ماشين ، فن هاي آماري و سيستم پايگاه داده است . هدف در داده کاوي، استخراج اطلاعات از حجم وسيعي از داده ها و انتقال آن ها به شکل قابل فهم براي بشر است [١،٢].
دسته بندي يکي از فن هاي داده کاوي (يادگيري ماشين ) است که داده را به کلاس و گروه پيش بيني شده نگاشت ميکند. اين فن ، تصميم گيري هوشمند را فراهم ميکند و نه تنها براي مطالعه و بررسي نمونه ي موجود به کار ميرود، بلکه رفتار آينده ي همان نمونه را نيز پيش بيني ميکند. دسته بندي شامل دو فاز است : ابتدا فاز آموزش ، که در آن مجموعه ي داده ها تحليل ميشوند و در فاز دوم داده ها آزمايش شده و دقت الگوي دسته بندي حاصل ميشود [٢].



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

٢. دسته بندي کننده هاي مجزا
دسته بندي کننده هاي مجزا، همان دسته بندي کننده هاي معمولي هستند که با يک مکانيسم اجراي مشخص ، کار جداسازي داده ها را انجام ميدهند. ازجمله ي اين دسته بندي کننده ها، ماشين بردار پشتيبان ١ [٣]، نزديک ترين k همسايه
[٤]، درخت تصميم [٥] و جنگل تصادفي [٦] است که در ادامه هر يک را به تفصيل معرفي مينماييم . لازم به ذکر است ، اين دسته بندي کننده ها ميتوانند به عنوان يادگير پايه در دسته بندي کننده هاي جمعي مورد استفاده قرار گيرند (بخش ٣).


٢.١. ماشين بردار پشتيبان
يک جداکننده ي خطي ٢ اغلب به صورت تابع

نشان داده ميشود. زماني که دو کلاس وجود دارد. اگر ٠≤ (f)x باشد، داده به کلاس مثبت نسبت داده ميشود و در غير اين صورت داده به کلاس منفي تعلق دارد.

براي مجموعه اي از نقاط که در آن داده ي ورودي، برچسب کلاس داده و است ، اگر يک جداکننده ي خطي بتوان پيدا کرد که براي تمام iها رابطه ي ٢ برقرار باشد، آنگاه ميتوان اين داده ها را به صورت خطي جدا کرد:

ماشين بردار پشتيبان ، بر اساس طرح دسته بندي بهينه در شرايط جداسازي خطي، توسعه داده شده است و درنهايت به يک مسئله ي برنامه نويسي درجه ي دوم ٣ تبديل خواهد شد. درواقع ، هدف در اين روش دسته بندي، يافتن راه حل بهينه است . اما در مسائل غيرخطي، SVM بايد به يک فضاي ويژگي ٤ با ابعاد بالا منتقل شود. درواقع ، اگر فاصله ي بين دو کلاس به صورت خطي قابل جدا کردن نباشد، از نگاشت به فضاي بالاتر (فضاي ويژگي) براي تفکيک دو کلاس استفاده ميشود. در اين فضا، تابع تمايز خطي ٥ مورد استفاده قرار ميگيرد. اين تابع بيشتر با نام تابع هسته ٦ شناخته ميشود و به اين کار حقه ي هسته ٧ ميگويند. توابع معمول مورداستفاده در SVM، تابع خطي، تابع Polynominal و RBF8
هستند، که دو تابع اخير در فضاي ويژگي مورد استفاده قرار ميگيرند [٧،٨،٩].
در SVM بيشينه کردن حاشيه ي بين دو کلاس مدنظر است . بنابراين ابر صفحه اي را انتخاب ميکند که فاصله ي آن از نزديک ترين داده ها در هر دو طرف جداکننده ي خطي بيشينه باشد. اگر چنين ابر صفحه اي وجود داشته باشد، به عنوان ابر صفحه ي حاشيه ي بيشينه ١ شناخته ميشود. در اين روش دسته بندي، ماشين هاي بردار پشتيبان ، نمونه داده هايي هستند که در ناحيه ي صفحه ي جداکننده ي دو کلاس قرار گرفته اند. در [١٠] نحوه ي جداسازي داده ها توسط
ماشين بردار پشتيبان به صورت زير نشان داده شده است :


شکل ١. نحوه ي جداسازي داده ها با استفاده از ماشين بردار پشتيبان [١٠]
براي ساخت بيشينه ي حاشيه ، دو صفحه ي مرزي موازي با صفحه ي جداکننده رسم کرده ، آن دو را آن قدر از هم دور ميکنيم که به داده ها برخورد کنند. صفحه ي جداکننده اي که بيشترين فاصله را از صفحات مرزي داشته باشد، بهترين جداکننده خواهد بود. درواقع ابر صفحه ي بهينه در SVM، جداکننده اي بين بردارهاي پشتيبان است . در مرحله ي آموزش تنها نقاطي به عنوان مدل يادگيري نگهداري ميشوند که به ابر صفحه نزديک هستند. به اين نقاط بردارهاي پشتيبان گفته ميشود. شکل ٢ نگاشت فضاي ورودي را به فضاي ويژگي نشان ميدهد.


شکل ٢. نگاشت داده به فضاي ويژگي براي دسته بندي غيرخطي در SVM [١١]

بردار ورودي و بردار کلاس ها است و در اينجا وجود هم ترازي ميان دو موجوديت را نشان ميدهد. ضرايب
و ضرايب لاگرانژ هستند. براي آن که فاصله ي ميان دو دسته بيشينه شود، بايد عکس مجذور فاصله را از رابطه ي
زير محاسبه کرد:

اهميت هر ويژگي در مجموعه ي داده با محاسبه ميشود. در اينجا هر k يک ويژگي را نشان ميدهد:

اگر اين مقدار به صفر نزديک باشد، کارايي دسته بندي کننده بدون وجود اين ويژگي تغييري نميکند.
به عبارتي ديگر مقدار نزديک به صفر نشان ميدهد که ويژگي در دسته بندي تعيين کننده نيست .
ماشين بردار پشتيبان ، يک دسته بندي کننده ي نظارت شده است . يادگيري تحت نظارت ، يک روش عمومي در يادگيري ماشين است که در آن به يک سيستم ، مجموعه اي از جفت هاي ورودي_خروجي داده شده و سيستم تلاش ميکند تا بر اساس آن ، تابعي از ورودي به خروجي را فراگيرد. اين يادگيري نيازمند تعدادي داده ي ورودي به منظور آموزش سيستم است [١٢]. در صورت استفاده ي مناسب از آن ، اين الگوريتم قدرت تعميم خوبي خواهد داشت و عليرغم ابعاد زياد از overfitting پرهيز ميکند. دليل ويژگي عموميسازي SVM، همان بيشينه کردن فاصله ي ميان دو دسته ي هم ترازي و عدم هم ترازي است . overfitting حالتي است که دسته بندي کننده فقط بر روي داده هاي آموزشي خوب عمل ميکند، اما عملکرد خوبي در داده هاي تست از خود نشان نميدهد. به بياني ديگر، اگر خروجي يک دسته بندي کننده بر روي داده هاي آموزشي ١٠٠% صحيح باشد و خروجي آن بر روي داده هاي تست داراي ٥٠% صحت باشد، در حقيقت خروجي دسته بندي کننده ميتواند بر روي هردوي آن ها فقط ٧٥% صحيح باشد. اين وضعيت همان overfitting است [١٣].
از ديگر ويژگيهاي SVM انعطاف پذيري در انتخاب يک تابع شباهت است ، اما انتخاب تابع هسته ي مناسب در الگوريتم ماشين بردار پشتيبان ميتواند از نقاط ضعف آن نيز محسوب گردد. انتخاب هسته ي نامناسب ، منجر به کارايي ضعيف و يا عدم اجراي الگوريتم ميگردد [١١]. اين دسته بندي کننده ممکن است در شرايطي که داده ي آموزشي بزرگ باشد، با مشکلاتي چون عدم کارکرد صحيح و افزايش بسيار زياد زمان محاسباتي و حافظه ي لازم براي آموزش و دسته بندي مواجه گردد [١٤].

٢.٢. نزديک ترين k همسايه ها
KNN، يک دسته بندي کننده ي نظارت شده است . اين روش فرض ميکند که داده ها در يک فضاي ويژگي قرار دارند. به طور دقيق تر ميتوان گفت که داده ها را به صورت نقاط داده در يک فضاي متريک در نظر ميگيرد. اين داده ها ميتوانند به صورت بردارهاي چندبعدي باشند. درحالي که که داده ها به شکل نقاط در فضاي ويژگي قرار دارند، مفهومي به نام فاصله ميان آن ها ايجاد ميشود که لزوماً فاصله ي اقليدسي نيست ، اگرچه به طورمعمول اين نوع فاصله مورداستفاده قرار ميگيرد.
هرکدام از داده هاي آموزشي دربردارنده ي يک مجموعه از بردارها و برچسب هاي کلاس هستند که اين برچسب ها مرتبط با هر بردار ميباشند. در ساده ترين حالت ، برچسب هاي کلاس + يا - هستند. درواقع دسته بندي در دو کلاس مثبت و منفي صورت ميگيرد. البته KNN، ميتواند با تعداد دلخواهي از کلاس ها کار کند. هم چنين ، يک عدد k به الگوريتم داده ميشود. اين عدد تصميم ميگيرد که چه تعداد از همسايه ها بر روي کلاس بندي تأثير بگذارند. همسايه ها بر اساس معيار فاصله تعريف ميشوند. به طورمعمول k يک عدد فرد است ، اگر تعداد کلاس ها برابر با دو باشد. اگر 1=k باشد، آنگاه الگوريتم به سادگي الگوريتم نزديک ترين همسايه ناميده ميشود.
با توجه به اين مفروضات اوليه ، دسته بندي با KNN بدين شرح است : در ابتدا نقاط داده براي آموزش و يک داده ي فاقد برچسب براي آزمايش داده ميشود. هدف يافتن برچسب کلاس براي نقطه ي جديد است . الگوريتم با توجه به مقدار k، رفتار متفاوتي نشان ميدهد. در ساده ترين حالت (1=k)، فرض ميشود که X نقطه اي است که بايد برچسب گذاري شود. الگوريتم به جستجوي نزديک ترين نقطه به X ميپردازد. اين حالت ممکن است خطاي زيادي داشته باشد، اما وقتي تعداد نقاط داده کم باشند، از آن استفاده ميشود. اگر تعداد نقاط داده بسيار زياد باشند، شانس بالايي وجود دارد که برچسب X و Y يکي شوند. به عنوان مثال يک سکه را يک ميليون بار پرتاب ميکنيم . اگر نهصد هزار بار شير بيايد، احتمال زيادي وجود دارد که در پرتاب بعدي هم شير بيايد.
به طورکلي در هر فضايي که تعداد کافي از نقاط وجود دارد، اگر نقطه ي x را در نظر بگيريم و نقطه ي y
نزديک ترين همسايه به x باشد. اگر x و y به اندازه ي کافي به هم نزديک باشند، آنگاه ميتوان فرض کرد که احتمال اين که
x و y به يک کلاس متعلق باشند، به شکل عادلانه اي يکسان است . با استفاده از تئوري تصميم گيري، x وy داراي کلاس يکسان هستند.
در حالت دوم که k مقداري بيش از عدد يک را دارد، آنچه انجام ميشود اين است که سعي ميکنيم تا نزديک ترين k همسايه را پيدا کرده و يک رأيگيري اکثريت انجام دهيم . به طورمعمول k عددي فرد است ، زماني که تعداد کلاس ها برابر با دو باشد. به عنوان مثال ، اگر 5=k و سه نمونه براي کلاس C1 و دو نمونه براي کلاس C2 داشته باشيم ، KNN مشخص ميکند که نمونه ي جديد داراي برچسب C1 است . زيرا C1 اکثريت را تشکيل ميدهد. در شرايطي که تعداد کلاس ها بيش از دو باشد نيز، از همين قانون استفاده ميکنيم [١٥].
در اينجا، ميتوان روند اجراي روش KNN و روابط رياضي موجود در فرآيند دسته بندي را، به صورت زير خلاصه
کرد:
١. نمونه هاي آموزشي به عنوان بردارهاي ويژگي بر اساس مدل برداري استاندارد نمايش داده ميشوند.
٢. نمونه ي دسته بندي نشده با بردار ويژگي نشان داده ميشود.
٣. شباهت ميان نمونه ي دسته بندي نشده ي و نمونه هاي آموزشي به صورت زير محاسبه ميشود:

درجايي که ، زاويه ي ميان بردار است و ||d|| طول بردار ميباشد.
٤. نزديک ترين k همسايه هاي نمونه ي دسته بندي نشده ي تعيين ميگردند.
٥. براساس k نزديک ترين همسايه ها، وزن دسته ي کانديد به صورت زير تعيين ميگردد:

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

در تابع دسته بندي، کلاس يا دسته ي k است . اين تابع دو مقدار ميتواند داشته باشد. اگر نمونه ي در
کلاس مورد نظر باشد، مقدار يک به تابع اختصاص داده ميشود. در غير اين صورت ، مقدار تابع دسته بندي صفر است .
٦. براي مقايسه ي وزن هاي هر دسته ، نمونه ي دسته بندي نشده ي به دسته ي با بيشترين وزن ، دسته بندي ميشود.
آن چه در مجموع ميتوان گفت اين است که ، KNN يک الگوريتم يادگيري غير پارامتري ١ و تنبل ٢ است .
غيرپارامتري بودن ، بدين معنا که اين الگوريتم هيچ فرضي براي توزيع داده ي آموزشي درنظر نميگيرد. اين ويژگي در جهان واقعي مفيد است ، زيرا بسياري از داده هاي واقعي (مانند ترکيب گوسي) بر اساس فرضيات تئوري ساخته نشده اند.
ويژگي ديگر KNN، تنبل بودن آن است و اين بدان معناست که KNN از داده ي آموزشي براي هيچ گونه تعميمي استفاده نميکند. به عبارتي ديگر، هيچ فاز آموزشي صريحي وجود ندارد و يا اگر وجود دارد، بسيار کوتاه و سريع است . ويژگي ديگر
KNN عدم تعميم است و معناي آن اين است که اين دسته بندي کننده کل داده ي آموزشي را نگه ميدارد، زيرا تمام داده ها در حين فاز آزمايش مورد نياز هستند. اين ويژگي KNN در مقابل تکنيک SVM قرار ميگيرد، که در آن ميتوان بردارهاي غيرپشتيبان را طي فاز آزمايش ناديده گرفت . بسياري از الگوريتم هاي تنبل و به ويژه KNN، تصميم را بر اساس مجموعه داده ي آموزشي موجود اتخاذ ميکنند، که در بهترين حالت از يک زيررشته از مجموعه ي آموزشي براي تصميم گيري بهره ميبرند. در اينجا يک دوگانگي وجود دارد و آن هم نبود فاز آموزشي (تمريني)، و در مقابل يک فاز آزمايش پرهزينه است . هزينه در اين جا حافظه و زمان ميباشد. در بدترين حالت ، اگر تمام داده هاي آموزشي در تصميم گيري پاياني الگوريتم مورد استفاده قرار گيرند، قطعاً زمان بيشتري صرف اين کار خواهد شد. هم چنين حافظه ي بيشتري براي ذخيره ي تمام داده ي آموزشي مورد نياز است [١٥،١٦،١٧].


٢.٣. درخت تصميم
درخت تصميم ، يک روش يادگيري نظارت شده است ، که به طور معمول براي دسته بندي مورد استفاده قرار ميگيرد. در درخت تصميم ، مجموعه ي داده ها آموزش داده شده و مدل سازي ميشود. بنابراين ، هر زمان که يک نمونه داده ي جديد مورد ارزيابي قرار گيرد، بر اساس مدل ايجاد شده ، دسته بندي خواهد شد [١٨]. هم چنين ، نمونه ها به نحوي دسته بندي ميشوند، که رشد آن ها از ريشه به سمت پايين است . در يک درخت تصميم ، هر گره ي داخلي يا غير برگ با يک ويژگي مشخص ميشود. اين ويژگي، سؤالي را در رابطه با داده ي ورودي مطرح ميکند. براي يافتن بهترين صفت در هر گره ، درنظر گرفتن يک زيرمجموعه ي کوچک از نمونه هاي آموزشي که از آن گره عبور ميکنند، کافي است . در هر گره ي داخلي به تعداد جواب هاي ممکن با اين سؤال ، شاخه وجود دارد، که هر يک با مقدار آن جواب مشخص ميشوند. برگ هاي اين درخت با يک کلاس و يا يک دسته از جواب ها مشخص شده که مقدار نوشته شده در برگ ، خروجي را تشکيل ميدهد.
درخت هاي تصميم مختلفي توسعه داده شده اند. اين الگوريتم ها از لحاظ کارايي داراي دقت و هزينه هاي متفاوتي هستند. بنابراين در يک مسئله ي دسته بندي مهم است که بدانيم کدام الگوريتم براي استفاده بهترين است . يک نوع از اين الگوريتم ID3 [١٩] نام دارد و از قديميترين انواع درخت تصميم به شمار ميآيد. اين الگوريتم با وجود ايجاد يک درخت ساده و مفيد، زمانيکه پيچيدگي افزايش مييابد، با کاهش دقت مواجه ميگردد [٢٠]. از اين رو، الگوريتم درخت تصميم هوشمند٣ [٢١] و الگوريتم C4.5 [٢٢،٢٣] توسعه داده شده اند.
درخت تصميم در زمينه هاي مختلف قابل استفاده است . اين الگوريتم ميتواند به عنوان يک جايگزين در روش هاي آماري براي يافتن داده ها، استخراج متن ، يافتن داده ي ازدست رفته در يک کلاس ، بهبود موتورهاي جستجو و هم چنين در بسياري از برنامه هاي کاربردي در حوزه ي پزشکي مورد استفاده قرار گيرد. در ادامه ، الگوريتم هاي ID3،IDA و 4.5.C را
معرفي مينماييم :

ID3:
ID3 يک الگوريتم يادگيري نظارت شده ١ است . اين الگوريتم تلاش ميکند ويژگيهايي که نمونه هاي يک کلاس را از کلاس هاي ديگر جدا ميکنند، مشخص کند. براي توسعه و فرموله کردن ID3 از تئوري اطلاعات ٢[٢٤] و تشخيص الگو استفاده شده است . يک قابليت کليدي از تئوري اطلاعات ، اصطلاح اطلاعات ٤ است که اغلب يک معناي رياضياتي از آن به عنوان يک کميت قابل اندازه گيري عددي براساس مدل احتمالي ٥ به دست ميآيد. به گونه اي که راه حل بسياري از مشکلات مهم ذخيره سازي و انتقال اطلاعات ميتواند با اين معيار فرموله شود. تابع اندازه گيري اطلاعات ، آنتروپي ٦ نام دارد و به عنوان تابع معيار استفاده ميشود. آنتروپي، ميزان بينظمي يا عدم خالص بودن مجموعه اي از نمونه ها را مشخص ميکند [٢٥].

: IDA
در الگوريتم IDA، معيار واگرايي ٧ به جاي معيار آنتروپي استفاده ميشود. واگرايي به عنوان درجه اي که همه چيز در آن در
حال نوسان است ، تعريف شده است . تفاوت ميان ID3 و IDA را ميتوان در موارد زير خلاصه نمود:
ID3 از روش جستجوي حريصانه استفاده ميکند. در ايجاد درخت هاي سطح پايين تر، ID3 درخت هاي نادرست را در بسياري از موارد توليد ميکند. فرآيند دسته بندي در IDA از نظر محاسباتي دقيق تر از ID3 است . زمان تحليل نيز نشان ميدهد که IDA از نظر محاسباتي کارآمدتر از ID3 ميباشد. روابط وابستگي ميان متغيرها در الگوريتم ID3 درنظر گرفته نميشود، که به طورکلي بدتر از نتيجه ي فرآيند دسته بندي در درخت تصميم است . اين مسئله به طور موفقيت آميزي توسط
IDA رفع شده است . به طور کلي ميتوان نتيجه گرفت که IDA نسبت به ID3، الگوريتمي کارآمدتر و مؤثرتر است [٢٥].

:C4.5
ID3 محدوديت هايي دارد که از جمله ي آن ، حساسيت بيش از حد به ويژگي با مقدار زياد است . براي آن که بتوان از اين الگوريتم يا هر الگوريتم دسته بندي ديگر که شامل تعداد زيادي ويژگي يا مقدار است ، به عنوان عامل جستجو در اينترنت بهره برد، بايد بر اين محدوديت غلبه کرد. اين مسئله توسط C4.5 حل شده است . C4.5، نسخه ي توسعه يافته ي الگوريتم
ID3 محسوب ميشود.
راه حل C4.5 براي غلبه بر مشکل ذکرشده ، استفاده از يک معيار به نام بهره اطلاعات ٨[٢٦] است . بهره اطلاعات يک ويژگي عبارت است از مقدار کاهش آنتروپي که به وسيله ي جداسازي نمونه ها از طريق اين ويژگي حاصل ميشود. اين معيار به شکل (X|I)Y نشان داده ميشود که در آن ، X ويژگي داده شده و Y ويژگي کلاس است . اين معيار سبب کاهش عدم اطمينان در مورد مقدار Y ميشود، هنگاميکه مقدار X مشخص باشد. عدم اطمينان نسبت به مقدار Y، توسط آنتروپي (H)Y، محاسبه ميشود. بنابراين ، عدم اطمينان نسبت به مقدار Y، وقتي مقدار X مشخص باشد، با آنتروپي مشروط (X|H)Y تعيين ميگردد:

اين محاسبه ، به خودي خود، چيز جديدي توليد نميکند. با اين حال ، به ما اجازه ميدهد که يک نرخ بهره را
محاسبه کنيم . اين نرخ ، به شکل زير تعريف ميشود:
در اين فرمول ، (H)X، آنتروپي نمونه هاي وابسته به ويژگي X است . با استفاده از نرخ بهره به جاي آنتروپي مشروط
ساده ، واکنش ها و حساسيت هاي درخت تصميم در مقابل ويژگيهاي با مقدارهاي زياد و متمايز کاهش مييابد [٢٧].
اگر بخواهيم الگوريتم C4.5 را با دو نسخه ي ديگر درخت تصميم مقايسه کنيم ، ميتوان تفاوت آن ها را در موارد
زير خلاصه کرد :

C4.5 توسعه اي از ID3 محسوب ميشود، که ميتواند مقدارهاي غيرقابل دسترس ، محدوده ي مقادير ويژگيهاي پيوسته ، هرس درختان تصميم و غيره را محاسبه نمايد. در اين الگوريتم با تخمين احتمالات نتايج ممکن مختلف ، ميتوانيم مواردي که در آن ها مقدار ويژگيها نامشخص است ، را دسته بندي کنيم . الگوريتم ID3 داراي اشکالات خاصي است . اين الگوريتم فقط ميتواند بر روي داده هاي اسمي ١ عمل کند. هم چنين ، ID3 قادر به برخورد با مجموعه داده هاي داراي نويز نيست و ممکن است الگوريتم در اين شرايط نتواند قوي باشد. از امتيازات C4.5 اين است که برخلاف ID3، در شرايط داراي نويز خوب عمل ميکند. اجتناب از مسئله ي overfitting و برخورد با ويژگيهاي از دست رفته ٢ از ديگر ويژگيهاي C4.5 است . هم چنين اين الگوريتم ميتواند به درختان در تبديل شدن به قواعد کمک نمايد [٢٥].
در مقابل IDA ميتوان گفت که ، C4.5 از اين الگوريتم نيز بهتر عمل ميکند. C4.5 با ويژگيهاي پيوسته کار ميکند، در حاليکه IDA فقط به ويژگيهاي گسسته ميپردازد. از اين رو، C4.5 را ميتوان در بسياري از شرايط واقعي زندگي مورد استفاده قرار داد. الگوريتم C4.5 هم ميتواند به ويژگيهاي گسسته بپردازد و همان اندازه در مقابل ويژگيهاي پيوسته خوب عمل کند. C4.5 يک حد آستانه ايجاد کرده و سپس ليست ويژگيها را به دو دسته تقسيم ميکند. يکي آن هايي که مقدارشان از حد آستانه بيشتر و ديگري آن هايي که مقدارشان کمتر يا مساوي با حد آستانه است . در حال حاضر، j48 پياده سازي جاوا از درخت تصميم C4.5 است [٢٨].

٢.٤. جنگل تصادفي
در سال ٢٠٠١ ميلادي، بريمن ٣ مفهوم جنگل هاي تصادفي را بر پايه ي تئوري bagging معرفي نمود [٥]. يک جنگل تصميم گيري، گروهي از درخت هاي تصميم مختلف است که به شکل موازي عمل ميکنند. Random Forest مفهومي متفاوت از Boosting را ارائه ميکند، اگرچه هر دو از روش يادگيري گروهي بهره ميبرند. تفاوت اين دو دسته بندي کننده در اين است که در جنگل تصادفي، هر درخت ، داده ها را به طور کاملاً مستقل از ديگر درخت ها دسته بندي ميکند، در حالي که در Boosting هر دسته بندي کننده ي پايه از طريق بهبود نتيجه ي به دست آمده از همتاي قبلي خود، به ايجاد نتيجه ي نهايي بهتر کمک ميکند. بريمن پيشنهاد کرد که تصادفي عمل کردن را در هنگام انتخاب مجموعه ي ويژگيها و نمونه داده هاي آموزشي در فرآيند دسته بندي اعمال کنيم . او دليل خود را عدم نياز به همه ي ويژگيها در ايجاد نتيجه ي درست دانست . به گفته ي او حتي در برخي موارد استفاده از همه ي ويژگيها منجر به کاهش صحت و دقت در نتيجه ي نهايي ميشود.
جنگل تصادفي يکي از تکنيک هاي يادگيري ماشين نظارت شده است . اين الگوريتم ، از درخت تصميم به عنوان دسته بنديکننده ي پايه استفاده ميکند. در اين فرآيند درخت هاي تصميم چندگانه ساخته ميشوند. تصادفي عمل کردن در Random Forest به دو شکل انجام ميشود: اول ، نمونه گيري تصادفي، يعني همان روشي که در Bagging به کار گرفته ميشود. دوم ، انتخاب تصادفي ويژگيهاي ورودي، براي توليد درخت هاي تصميم پايه ي مجزا. قدرت اين درخت هاي مجزا و همبستگي ميان آن ها، يک مسئله ي کليدي در RF است و خطاي تعميم دسته بندي کننده از آن ناشي ميشود
يک جنگل تصادفي، مجموعه اي از دسته بندي کننده ها با ساختار درخت است و به شکل زير نشان داده ميشود:

بردارهاي توزيع تصادفي مستقل هستند و هر درخت يک رأي واحد براي دسته بندي توليد ميکند. در اين روش ، هر درخت تصميم از يک بردار تصادفي ايجاد ميشود. براي يک نمونه ي جديد، نمونه به هر درخت جنگل داده شده و هر درخت يک رأي درباره ي کلاس نمونه توليد ميکند. پيشگويي کلاس براي نمونه ي جديد با جمع آوري رأيهاي تمام
درخت ها و سپس رأيگيري اکثريت ١ انجام ميشود. اين فرآيند را ميتوان به صورت زير تعريف کرد [٢٩]:
١. ايجاد نمونه هاي از داده هاي اصلي که اين کار به شکل تصادفي و با جايگذاري از داده هاي

اصلي انجام ميگردد. در اين جا، و نمونه ها به طور تصادفي از D به دست ميآيند. حال اين نمونه ها، مجموعه ي آموزشي را تشکيل داده و با داشتن يک الگوريتم درخت تصميم ، درخت