بهبود زمان تست الگوریتم k هارمونیک نزدیک ترین همسایه مبتنی بر بردارهای متوسط محلی چندتایی با حذف داده های آموزشی غیرضرور

یکی از ساده ترین و رایج ترین تکنیک های طبقه بندی، الگوریتمk نزدیک ترین همسایه (knn) می باشد که به دلیل پیاده سازی آسان، محبوبیت زیادی یافته است اما این روش دارای مشکلاتی از قبیل حساسیت زیاد به داده های پرت، حساسیت زیاد به پارامتر تعداد همسایگی و زمان تست بالا می باشد. یکی از جدیدترین تکنیک های طبقه بندی، الگوریتم k هارمونیک نزدیک ترین همسایه مبتنی بر بردارهای متوسط محلی چندتایی (mlm-khnn) است که با هدف غلبه بر حساسیت زیاد به داده های پرت و پارامتر تعداد همسایگی پیشنهاد شده است. متاسفانه، روش mlm-khnn نیز همچون روش knn دارای زمان تست بالاست، زمان تست mlm-khnn وابسته به تعداد داده های آموزشی است. در این مقاله، مدلی برای کاهش تعداد داده های آموزشی ارائه می شود به نحوی که حتی الامکان، صحت طبقه بندی کاهش نیابد. به بیان دقیقتر، در این مدل، یک داده آموزشی حذف می شود اگر حذف آن، تاثیر چندانی در صحت طبقه بندی داده های آموزشی به روش mlm-khnn نداشته باشد. البته مدل پیشنهادی، مدل غیرخطی صفر و یک است که حل دقیق آن، دشوار و زمانبر است. لذا، روشی هیوریستیک برای حل تقریبی این مدل، ارائه می شود. آزمایشات انجام شده بر روی 11 مجموعه داده واقعی از مخزن uci بیانگر این است که زمان تست روش پیشنهادی به نحو چشمگیری نسبت به الگوریتم mlm-khnn بهبود می یابد بدون آنکه صحت طبقه بندی آن، کاهش قابل ملاحظه ای را تجربه کند.