کنفرانس بین المللی محاسبات نرم

صفحه اصلی / پنجمین کنفرانس بین المللی محاسبات نرم

مروری بر الگوریتم های مختلف KNN توسعه یافته

نویسندگان :

هادی محمدی¹ فاطمه عمرانی² فرشته رضائی³

1- دانشگاه پیام نور 2- دانشگاه پیام نور 3- دانشگاه پیام نور

کلمات کلیدی :

الگوریتم KNN توسعه یافته،الگوریتم وزن دهی hubness و فازی،الگوریتم خوشه بندی تک گذر مقید،سناریوی چند برچسبی با انتخاب نمونه اولیه برای الگوریتم KNN

چکیده :

در دنیای امروزی در کاربردهایی مانند دسته‌بندی متن یا پیش‌بینی بارش در پیش‌بینی وضعیت شیء جدید، تشخیص اینکه با توجه به داده‌های بزرگ فعلی داده ورودی جدید چه وضعیتی خواهد داشت، بسیار مهم است. بدین منظور یکی از تکنیک‌های مهم داده‌کاوی به نام دسته‌بندی (classification) استفاده می‌شود. در این مقاله الگوریتم KNN (K نزدیک ترین همسایه) مورد بررسی قرار گرفته‌است و مروری کلی از اینکه تاکنون از چه روش‌هایی برای بهبود این الگوریتم استفاده شده‌است، انجام گرفته‌است. الگوریتم KNN در عین سادگی، بی پارامتر بودن و کارائی دسته‌بندی بالا، دارای اشکالاتی مانند زمان پیچیدگی محاسباتی بالا، نسبتاٌ گران بودن دسته‌بندی شی جدید، حساسیت به انتخاب مقدار K و حساسیت نسبت به نویز است. لذا این الگوریتم باید توسعه یابد. الگوریتم‌های KNN توسعه‌ یافته مختلف که در این مقاله مورد بررسی قرار گرفته‌اند به دو دسته مهم تقسیم می‌شوند: 1- طراحی الگوریتم‌های سریع برای جستجوی k نزدیکترین همسایه شی جدید در کوتاه‌ترین زمان. 2- انتخاب برخی نمونه‌های نماینده از نمونه های یادگیری اولیه یا حذف برخی از نمونه‌های یادگیری اولیه. بدین منظور در این مقاله الگوریتم‌هایی مانند درخت k-d، درخت k-d تصادفی، درخت R-tree ، درهم‌ساز حساس به محل (LSH)، WKNN ، DWKNN ، الگوریتم وزن‌دهی Exponential ، الگوریتم خوشه‌بندی تک گذر مقید(INNTC) و سناریوی چند برچسبی با استفاده از انتخاب نمونه اولیه پرداخته شده‌است و با یکدیگر مقایسه شده‌اند. نتایج حاکی از عملکرد خوب برخی از الگوریتم‌ها است. الگوریتم مبتنی بر درخت تصادفی در زمان جستجو بهبود ایجاد می‌کند. الگوریتم KNN مبتنی بر خوشه‌بندی وزن دار، الگوریتم خوشه‌بندی تک گذر مقید، الگوریتم مبتنی بر سناریوی انتخاب نمونه اولیه در دسته بندی چند برچسبی موفق هستند و روش وزن‌دهی Hubness و فازی با کاهش نمونه آزمایشی باعث بهبود الگوریتم KNN می باشد.