الگوریتم KNN

الگوریتم طبقه بندی KNN

 

 هنگام تلاش براي حل مسائل جديد، افراد معمولاً به راه­‌حل­‌هاي مسائل مشابه که قبلاً حل شده‌­اند مراجعه مي­‌کنند. k نزديکترين همسايه (k-NN) يک تکنيک طبقه­‌بندي است که از نسخه‌ه­اي از اين متد استفاده مي‌­کند. در اين روش تصميم‌­گيري اينکه يک نمونه جديد در کدام کلاس قرار گيرد با بررسي تعدادي (k) از شبيه­‌ترين نمونه­‌ها يا همسايه‌­ها انجام مي­‌شود. در بين اين  k نمونه، تعداد نمونه­‌ها براي هر کلاس شمرده مي‌­شوند، و نمونه جديد به کلاسي که تعداد بيشتري از همسايه‌­ها به آن تعلق دارند نسبت داده مي­‌شود. شکل زیر محدوده همسايگي نمونه N را نشان مي­‌دهد. در اين محدوده، بيشتر همسايه­‌ها در کلاس X  قرار گرفته‌­اند.

 

الگوریتم طبقه بندی knn

 

اولين کار براي استفاده از  k-NN يافتن معياري براي شباهت يا فاصله بين صفات در داده‌­ها و محاسبه آن است. در حالي که اين عمل براي داده‌­های عددي آسان است، متغيرهاي دست‌ه­ای نياز به برخورد خاصي دارند. هنگامي که فاصله بين نمونه­‌هاي مختلف را توانستيم اندازه گيريم، مي­توانيم مجموعه نمونه­‌هايي که قبلاً طبقه‌­بندي شده‌­اند را به عنوان پايه دسته­‌بندي نمونه­‌هاي جديد استفاده کنيم.

 فاصله بين دو نمونه ( Y=( y1,……,yn و ( X=( x1,…..,xnبا استفاده از فاصله اقليدسي بصورت زير محاسبه مي­‌شود:   

 

الگوریتم طبقه بندی knn

 

k-NN بار محاسباتي زيادي را روي کامپيوتر قرار مي­دهد زيرا زمان محاسبه بصورت فاکتوريلي از تمام نقاط افزايش مي­‌يابد. درحالي­‌که بکار بردن درخت تصميم يا شبکه عصبي براي يک نمونه جديد فرايند سريعي است، k-NN نياز به محاسبه جديدي براي هر نمونه جديد دارد. براي افزايش سرعت k-NN معمولاً تمام داده‌­ها در حافظه نگه­داري مي­‌شوند.

فهم مدل­هاي k-NN هنگامي که تعداد متغيرهاي پيش­بيني کننده کم است بسيار ساده است. آن­ها هم­چنين براي ساخت مدل­‌هايي مانند متن که شامل انواع داده غير استاندارد هستند، بسيار مفيدند. تنها نياز براي انواع داده جديد وجود يک معيار مناسب شباهت است. 

 

تهیه کننده: مهندس محمد طالبی
منبع