ویرگول
ورودثبت نام
AliFallahi
AliFallahiآنچنان رفتم كه خود می خواستم
AliFallahi
AliFallahi
خواندن ۴ دقیقه·۶ سال پیش

عدم شباهت در داده‌های عددی: معیار فاصله مینکوفسکی

عدم شباهت در داده‌های عددی: معیار فاصله مینکوفسکی
عدم شباهت در داده‌های عددی: معیار فاصله مینکوفسکی


Dissimilarity of Numeric Data: Minkowski Distance

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

  • فاصله اقلیدسی (Euclidean distance)
  • فاصله منهتن (Manhattan distance)
  • فاصله مینکوفسکی (Minkowski distance)

پیش از معرفی عناوین بالا، بهتر است یادآور شویم که به طور معمول قبل از محاسبه عدم شباهت، مرحله نرمال‌سازی داده‌ها (Data Normalization) انجام می‌شود. منظور از نرمال‌سازی، تغییر بازه عددی داده‌های موجود، به بازه‌ای کوچک‌تر و محدودتر مثل [1, 1- ] و یا [1.0, 0.0 ] است. به عنوان مثال داده‌های مربوط به ارتفاع چند ساختمان که می‌تواند به در قالب متر و یا اینچ بیان شود و یا معدل‌های کیفی چند دانش‌آموز که به صورت مجموعه‌ای از اعداد نرمال‌شده در لیست نمایش داده می‌شود.


چرا از نرمال‌سازی استفاده می‌کنیم؟

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


فاصله اقلیدسی (Euclidean distance)

رایج‌ترین معیارهای محاسبه فاصله، فاصله اقلیدسی (Euclidean distance) و یا مسیر مستقیمی است که یک کلاغ بین مبدا و مقصد پرواز می‌کند (as the crow flies).

فاصله اقلیدسی بین دو نقطه p و q به صورت زیر محاسبه می‌شود:

فرمول محاسبه فاصله اقلیدسی
فرمول محاسبه فاصله اقلیدسی


در واقع برای محاسبه فاصله اقلیدسی، ما طبق قضیه فیثاغورت، وتر مثلث قائم الزاویه به وجود آمده را محاسبه می کنیم.

Euclidean distance in R2 مثالی از فاصله اقلیدسی در فضای دو بعدی
Euclidean distance in R2 مثالی از فاصله اقلیدسی در فضای دو بعدی

https://en.wikipedia.org/wiki/Euclidean_distance


فاصله مهنتن (Manhattan distance)

یکی دیگر از رایج‌ترین معیارهای محاسبه فاصله، فاصله مهنتن (Manhattan distance) است. این فاصله برگرفته از فاصله بین بلوک‌های ساختمانی در شهرها است (City block distance).

فاصله مهتن بین دو نقطه p و q به صورت زیر محاسبه می‌شود:

فرمول محاسبه فاصله منهتن Manhattan distance
فرمول محاسبه فاصله منهتن Manhattan distance
مثالی از معیار فاصله منهتن
مثالی از معیار فاصله منهتن

فاصله منهتن، به عنوان فاصله راننده تاکسی (taxi driver) نیز شناخته می شود. براساس مثال بالا، یک راننده تاکسی برای حرکت از نقطه بنفش (مبدا) به نقطه صورتی (مقصد) 4 بلوک به سمت چپ و سپس 3 بلوک به سمت بالا حرکت می کند.

ویژگی‌های مهم فاصله اقلیدسی و منهتن

هر دو معیار سنجش عدم شباهت، فاصله اقلیدسی و فاصله منهتن دارای ویژگی‌های ریاضیاتی زیر هستند:

همیشه مثبت بودن (Non-negativity): مقدار فاصله بین دو نقطه p و q همیشه مقداری مثبت، و بزرگ‌تر و مساوی صفر است. d(i,j) >= 0

اصل این‌همانی تمیزناپذیرها (Identity of indiscernibles): فاصله هر شیء از خودش صفر است. d(i,i) = 0

تقارن (Symmetry): معیار فاصله، دارای مقداری متقارن است.

d(i,j) = d(j,i)

اصل نابرابری مثلث (Triangle inequality): مطابق قضیه نابرابری مثلثی، در ریاضیات، در هر مثلث اندازه هر ضلع از مجموع اندازه دو ضلع دیگر کوچکتر است.

d(i,j) <= d(i,k) + d(k,j)

در مورد محاسبه میزان عدم شباهت، طبق قضیه نابرابری مثلثی، میزان فاصله مستقیم از شی i به شی j، نمی‌تواند بزرگتر از زمانی باشد که در حرکت از i به سمت j یک مسیر انحرافی به k نیز طی شده است.

مطابق این قضیه، همچنین اندازه هر ضلع از تفاضل اندازه دوضلع دیگر بزرگتر است.

معیاز اندازه‌گیری که هرتمامی موارد گفته شده بالا را پوشش دهد، به عنوان متریک (metric) شناخته می‌شود. لازم به ذکر است که ویژگی همیشه مثبت بودن (Non-negativity)، به صورت ضمنی در سه ویژگی بعدی نیز وجود دارد.


مثالی از فاصله اقلیدسی و منهتن

مطابق آنچه تاکنون گفته شد، چنانچه نقطه x1 دارای مختصات (1,2) و نقطه x2 دارای مختصات (3,5) باشد، فاصله اقلیدسی و منهتن برای این دو نقطه به صورت زیر محاسبه می‌شود:

Euclidean distance:

Manhattan distance: 2 + 3 = 5

مثالی از فاصله اقلیدسی و منهتن و مینکوفسکی
مثالی از فاصله اقلیدسی و منهتن و مینکوفسکی


فاصله مینکوفسکی (Minkowski distance)

فاصله مینکوفسکی حالت کلی از فاصله‌های اقلیدسی و منهتن است.

فرمول معیار فاصله مینکوفکسی Minkowski distance
فرمول معیار فاصله مینکوفکسی Minkowski distance


در این فرمول h عددی حقیقی و بزرگتر از 1 است. h >= 1

فاصله‌هایی از این دست در برخی منابع به صورت Lp نیز نشان داده می‌شود که منظور از p همان h است.

در فرمول ارایه شده، چنانچه مقدار h=1 در نظر گرفته شود، نتیجه همان فاصله منهتن و در صورتیکه h=2 باشد، فاصله اقلیدسی خواهد بود.


فاصله اقلیدسی وزن‌دار (weighted Euclidean distance)

در فرمول فاصله اقلیدسی، اگر مقدار وزن را با توجه به میزان اهمیت هر یک از مقادیر عددی، در فرمول لحاظ کنیم، فاصله اقلیدسی وزن‌دار (weighted Euclidean distance) به دست می‌آید.

فرمول محسابه فاصله اقلدیدسی وزن دار
فرمول محسابه فاصله اقلدیدسی وزن دار

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


فاصله سوپریمم(Supremum distance)

فاصله سوپریمم حالت کلی از فاصله مینکوفسکی است در زمانی که h به سمت بی‌نهایت میل می‌کند. با استفاده از فاصله سوپریمم، می‌توان حداکثر فاصله بین دو شی را محاسبه نمود.

فرمول فاصله سوپریمم به صورت زیر است و در حالت L بینهایت، با نام uniform norm نیز شناخته می‌شود.

فرمول محاسبه فاصله سوپریمم
فرمول محاسبه فاصله سوپریمم


مثالی از فاصله سوپریمم

چنانچه نقطه x1 دارای مختصات (1,2) و نقطه x2 دارای مختصات (3,5) باشد، بیشترین فاصله (تفاوت) بین دو نقطه مذکور در این مثال، 5 - 2 = 3 مقدار سوپریمم فاصله بین دو شی است.

۶
۰
AliFallahi
AliFallahi
آنچنان رفتم كه خود می خواستم
شاید از این پست‌ها خوشتان بیاید