استفاده از معیارهای تخمین پیچیدگی مسائل دسته بندی برای بهبود عملکرد الگوریتم های انتخاب نمونه

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

Keywords:

دسته بند نزدیک ترین همسایه , کاهش نمونه , تخمین پیچیدگی , الگوریتم LPD