روش نزدیکترین همسایه مسأله دیگری را پیش می آورد و آن یافتن روش قابل اطمینانی برای اندازه گیری فاصله یک نمونه از نمونه های دیگر است. بدون شک، باید میزانی را برای اندازه گیری فاصله ها انتخاب کنیم که بتواند شباهت نمونه ها را در فضای هندسی طرح نشان دهد.

  • فاصله همینگ۲

ابتدایی ترین نوع فاصله که به علت سادگی کاربرد گسترده ای دارد میزان فاصله همینگ است. برای دوبردار :

X= (x1, x2,…)

Y=(y1, y2,…)

فاصله همینگ با محاسبه اختلاف هر عنصر از یک بردار و عنصر متناظر آن در بردار دیگر و جمع قدر مطلق اختلاف ها به دست می آید. فرمول زیر فاصله همینگ را تعریف می کند:

( \xi – yi\)                                               H=

فاصله همینگ اغلب برای مقایسه بردارهای صفر و یک به کار می رود. شاید روشن باشد که این فاصله در واقع تعداد بیتهایی را که در و بردار متفاوت اند نشان می دهد. درحقیقت فاصله همینگ را می توان از طریق تابع یا حذفی (xor) به دست آورد. زیرا

xi xor yi برابر است با \ xi – yi\

  • فاصله اقلیدسی۱

یکی از متداول ترین میزان های فاصله، فاصله اقلیدسی است، فرض کنید در صفحه مختصات قائم دو بردار(x,y) را داشته باشیم و بخواهیم فاصله اقلیسی (d(x-y)) آن دو را محاسه کنیم.

فاصله اقلیدسی این دو بردار کوتاه ترین فاصله بین آن هاست و با فرمول زیر به دست می آید.

D(x,y) euc =

در حالی که n تعداد ابعاد بردار است.

در مثال دو بعدی که در شکل ۳-۳ نشان داده شده است این فاصله برابر است با

D(x,y) euc =

برای تعیین فاصله اقلیسی در واقع از قضیه معروف فیثاغورث برای محاسبه وتر مثلث استفاده می شود. در حالت خاص که بردارها از نوع صفر ویک باشند فاصله اقلیدسی در واقع برابر جذر فاصله همینگ خواهد بود. فاصله اقلیدسی به علت سادگی محاسه کاربرد گسترده ای دارد و همان طور که گفته شد در بردارهای صفر ویک فاصله اقلیدسی به حالت خاصی تقلیل می یابد که از نظر ریاضی برابر با جذر فاصله همینگ است.

 

شکل۳-۳ فاصله اقلیدسی

  • فاصله شهری۱(فاصله منتهن)

صورت ساده تری از فاصله اقلیدسی فاصله شهری است. در این نوع فاصله به جای جذر مربع اختلافات از قدر مطلق اختلافات استفاده می شود.

Dcb =

نتیجه این عمل صرف نظر از سرعت بیشتر محاسباتی نسبت به فاصله اقلیدسی این است که نقاط هم فاصله از یک بردار تماماً بر یک مربع واقع می گردند در صورتی که در حالت فاصله اقلیدسی نقاط هم فاصله از بردار بر یک دایره واقع می گردند. این امر در شکل۳-۴ نشان داده شده است.

در این شکل دایره محدوده نقاطی را نشان می دهد که از بردار مورد نظر ما فاصله اقلیدسی یکسانی دارند. حال اگر از فاصله شهری استفاده شود نقاط واقع بر مربع همگی اندازه فاصله مساوی خواهند داشت .

روشن است که این عمل در محاسبه فاصله ها تا اندازه ای خطا دارد اما این میزان کاهش دقت در مقابل

 

شکل ۳-۴ فاصله شهری.

 

افزایش سرعت محاسبات ممکن است قابل قبول باشد.

  • فاصله مربعی۱٫

فاصله اقلیدسی را می توان باز ساده تر کرد که البته با خطای بیشتری همره خواهد بود. این نوع فاصله را فاصله مربعی می گتویند، شکل ۳-۵ فاصله مربعی را نشان می دهد. در واقع فاصله مربعی دو بردار بزرگترین اختلاف بین عناصر متناظر بردارها خواهد بود.

Dsq = max \xi-yi\

این فاصله مجدداً محدوده مربع شکلی را حول بردار مورد نظر تشکیل می دهد. اندازه این مربع ازمحدوده

مربع فاصله شهری بیشتتر است و در نتیجه میزان غیر دقیق تری می باشد. مجدداً از این میزان خطا

شکل ۳-۵ فاصله مربعی

آنچه در بالا آمد نگاه مختصری به انواع میان های فاصله بود گرچه این فهرست به هیچ وجه کامل نیست. مقصود بیان این نکته بود که روشهای متعددی برای اندازه گیری درجه نزدیکی وشباهت بردارها وجود دارد. در بخش بعدی مجدداً تابع ممیز را مورد بحث قرار داده واز محدوده های تصمیم برای جدا کردن بردارها استفاده

۱ _distance metrice     ۲ _Hamming distance

۱ _Euclidean distance

۱ –city block distance

  1. _square distance