چگونه یک فرد مشابه را پیدا کنم؟ (بخش اول)

در گذشته یکی از چالش های موجود در دنیای کامپیوتر یافتن تشابه بین افراد یا محصولات بوده است.

فرض کنید سه نفر با نام های x1 و x2 و x3 نوشابه های شرکت پپسی و کوکاکولا را نوشیده اند. این سه نفر پس از نوشیدن نوشابه ها به هر کدام بنا به سلیقه خود امتیازی داده اند. به عنوان مثال شخص x1 به پپسی امتیاز 4 و به کوکاکولا امتیاز 5 را داده است.

حال اگر شخص y که به پپسی امتیاز 2 و به کوکاکولا 4 را داده است، بخواهیم بفهیم به کدام یک از افراد x1 و x2 و x3 شبیه است، باید چه محاسباتی را انجام دهیم؟

برای پاسخ به این سوال الگوریتم های گوناگونی ارائه شده است. یکی از پایه ای ترین و ساده ترین الگوریتم ها برای انجام این کار استفاده از روش manhattan distance است.

قبل از استفاده از روش منهاتن بیایید اطلاعات مثال بالا را در فضای دو بعدی نیز مشاهده نماییم.

با استفاده از استدلال شهودی از تصاویر بالا می توانید بگوییم شخص x1 به y نزدیک تر است.

اما کامپیوتر چگونه می تواند این نزدیکی را تشخیص دهد؟

براساس روش manhattan distance می توانید فاصله هر نقطه را نسبت به y بدست آورید و هر کدام که فاصله کم تری داشته باشد را شناسایی نمایید.

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

در فرمول فوق x معرف امتیاز نوشابه پپسی است و y معرف امتیاز نوشابه کوکاکولا است.

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

مجموعه نقاط را در متغییر points می‌ریزیم. به عنوان مثال شخص x1 به پپسی امتیاز 4 و به کوکاکولا امتیاز 5 را داده است. شخص x2 و ...

با استفاده از کد زیر شخص y را از بقیه نقاط (اشخاص) جدا می کنیم.

• متغییر target_x مشخص کننده امتیاز شخص y به نوشابه پپسی است.
• متغییر target_y مشخص کننده امتیاز شخص y به نوشابه کوکاکولا است.

مجموعه نقاط پس از جداسازی شخص y به شرح زیر است :

حال می توانید با استفاده از فرمول منهتن فاصله هر شخص را نسبت به شخص y بدست آورید.

در نتیجه :

همانطور که در نتیجه بالا بدست آمده است، شخص x1 به شخص y نزدیک تر است. به عبارتی شخص x1 به شخص y شبیه تر است.

از همراهیتان صمیمانه سپاسگزارم...

نویسنده : ابوالفضل وکیلی