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

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