کلاس بندی و پيش بينی

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

در زمينه کلاس­بندی تحقيقات زيادی انجام شده و روش­های زيادی برای ساخت و بهبود مدل­ها ارائه شده است. در ادامه اين قسمت روش­ها و مفاهيمی که در زمينه کلاس­بندی در اين تحقيق استفاده شده­اند، شرح داده می­شوند.

1-2-2-1- ماشين بردار پشتيبانی[1]

الگوريتم SVMاوليه در 1963 توسط وپنيک[2]ابداع شدو در سال 1995 توسط وپنيک و کورتس[3]برای حالت غيرخطی تعميم داده شد. الگوريتم SVM،جزء الگوريتم­های تشخيص الگو دسته بندی می­شود.از الگوريتم SVM، در هر جايی که نياز به تشخيص الگو يا دسته بندی اشياء در کلاس­های خاص باشد مي­توان استفاده کرد. اين روش با فرض اينکه دسته­ها به صورت خطی جدايی پذير هستند، به دنبال اَبُرصفحه­ای با حداکثر حاشيه[4] که بتواند دسته­ها را جدا کند، است. در مسائلی که داده­ها به صورت خطی جداپذير نباشند، داده­ها به فضايی با ابعاد بيشتر نگاشت پيدا می­کنند تا بتوان آن­ها را در اين فضای جديد به صورت خطی جدا نمود. SVMدر حالت پايه يک روش کلاس­بندی کننده دو کلاسه است، اما تحقيقات و پياده سازی­ها مختلفی برروی آن برای حل مسائل دارای بيش از دو کلاس نيز انجام شده است (12).

1-2-2-2- بگينگ[5]

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

1-2-2-3- جنگل تصادفی[6]

جنگل تصادفی مجموعه­ای متشکل از درختان تصميم است. يک جنگل­ تصادفی معمولاً از ده­ها يا صدها درخت تصميم ساخته شده است. در اين روش برای تعيين نتايج نهايی پيش­بينی از بگينگ (يا بوستينگ[7] که بگينگ وزندار است) استفاده می­شود. اين روش بر خلاف حالت استفاده از يک درخت تصميم حساسيت به نويز پايينی دارد و مدل پايدارتری را ارئه می­دهد. اين روش از نظر کارايی با کلاس­بندی کننده­های غيرخطی مانند شبکه­های عصبی مصنوعی و SVMدر رقابت است.

در اين روش هر درخت تصميم گيری با زيرمجموعه­ای از داده­های آموزش ساخته می­شود؛ اين زيرمجموعه­ها به صورت تصادفی همراه با جايگذاری انتخاب می­شوند. واضح است که برخی از داده­ها بيشتر از يک بار در اين مجموعه­ها ظاهر می­شوند و برخی از داده­ها اصلاً انتخاب نمی­شوند. به طور کلی تقريباً دو سوم داده­ها در مجموعه­های آموزش ظاهر می­شوند و تقريباً يک سوم آن­ها انتخاب نمی­شوند. سپس با استفاده از هر يک از مجموعه داده­های آموزش يک درخت تصميم ساخته می­شود و همانطور که پيش از اين نيز اشاره شد، رأی­گيری به روش بگينگ نتيجه پيش­بينی در اين روش را مشخص می­کند (11).

1-2-2-4- اعتبار متقاطع[8]

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

اما در روش “اعتبار متقاطع” تعداد ثابتی دسته[9] يا بخش بندی برای داده­ها در نظر گرفته می­شود. به عنوان مثال n برای تعداد بخش­ها انتخاب می­شود. سپس داده­ها به n بخش تقريباً مساوی تقسيم می­شوند و در هر مرحله يک بخش برای تست و ديگر بخش­ها برای آموزش استفاده می­شوند و اين کار n بار تکرار خواهد شد. در نتيجه هر داده دقيقاً يک مرتبه به عنوان تست استفاده شده است. در نهايت ميانگين خطای n مرحله به عنوان خطای کلی در نظر گرفته می­شود.

عموماً از n=10 برای اعتبار متقاطع استفاده می­شود. آزمايشاتی که روی حجم انبوهی از مجموعه داده­ها با الگوريتم­های آموزش مختلف انجام شده نشان داده است که n=10 عددی مناسب برای دست يافتن به مقدار تقريبی بهترين خطا است، البته تعدادی مدارک نظری نيز برای مناسب بودن n=10 نيز وجود دارد. با توجه به انتخاب تصادفی دسته­ها، يک مرتبه انجام اعتبار متقاطع ممکن است، دقتی که کاملاً قابل اعتماد باشد را ارائه نکند، بنابراين بهتر است که انجام اعتبار متقاطع چندين بار تکرار شود (12).

1-2-2-5- اعتبار متقاطع نگه­داشتن يکی[10]

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

[1] Support Vector Machines (SVM)

[2]Vapnik Vladimir

[3]Cortes Corinna

[4] Maximum margin

[5]Bagging

[6] Random Forest

[7]Boosting

[8]Cross-Validation

[9] Folds

[10]Leave-One-Out