Manhattan Distance क्या है?

दूरी मेट्रिक्स ऐसे आवश्यक उपकरण हैं जो यह मापने में मदद करते हैं कि अंतरिक्ष में वस्तुएँ या बिंदु एक-दूसरे से कितनी दूर हैं। ये मेट्रिक्स मशीन लर्निंग, रोबोटिक्स और भू-स्थानिक सूचना प्रणालियों सहित कई क्षेत्रों में बड़ी भूमिका निभाते हैं। दूरी को मापकर हम पैटर्न पहचान, डेटा क्लस्टरिंग और स्थानिक विश्लेषण जैसे कार्य कर सकते हैं, जो लाभ-उद्यमों और शोधकर्ताओं दोनों के लिए महत्वपूर्ण हैं। 

Manhattan distance, जिसे L1 distance या taxicab distance भी कहा जाता है, ग्रिड-जैसे मार्गों में या बहुआयामी स्थानों में बिंदुओं के बीच दूरी निकालने का एक विशेष रूप से उपयोगी उपाय है। यहाँ हम इसके गणितीय आधार के साथ-साथ Python और R में Manhattan distance को लागू करने के तरीके भी देखेंगे। 

"Manhattan distance." Dall-E द्वारा छवि।

ध्यान रखें, Manhattan distance दूरी मेट्रिक्स के व्यापक विषय का केवल एक हिस्सा है, जो बार-बार विभिन्न क्षेत्रों में सामने आता है। दूरी-आधारित लर्निंग में विशेषज्ञ बनने के लिए, अपनी पसंदीदा भाषा के अनुसार हमारे Designing Machine Learning Workflows in Python या Cluster Analysis in R पाठ्यक्रम पर विचार करें। 

Manhattan Distance की परिभाषा

Manhattan distance एक मेट्रिक है जिसका उपयोग ग्रिड-जैसे मार्ग में दो बिंदुओं के बीच दूरी निर्धारित करने के लिए किया जाता है। Euclidean distance के विपरीत, जो दो बिंदुओं के बीच सबसे छोटा सीधा रेखीय मार्ग मापती है, Manhattan distance बिंदुओं के निर्देशांकों के बीच परम अंतर (absolute differences) का योग मापती है। इसे "Manhattan distance" इसलिए कहा जाता है क्योंकि, Manhattan की ग्रिड-जैसी सड़कों पर चलने वाली टैक्सी की तरह, इसे ग्रिड लाइनों के साथ ही चलना पड़ता है। 

गणितीय रूप से, n-आयामी स्थान में दो बिंदुओं के बीच Manhattan distance उनके कार्तीय निर्देशांकों के परम अंतरों का योग है। 

Manhattan distance के सूत्र में absolute value फ़ंक्शन शामिल होता है, जो किसी भी ऋणात्मक अंतर को धनात्मक में बदल देता है। दूरी की गणना के लिए यह महत्वपूर्ण है, क्योंकि यह सुनिश्चित करता है कि सभी दूरी माप गैर-ऋणात्मक हों, और यात्रा की दिशा की परवाह किए बिना वास्तविक स्केलर दूरी को दर्शाएँ।

Manhattan Distance की गणना और दृश्यांकन

जैसा कि हमने कहा, Manhattan distance दो बिंदुओं के अनुरूप निर्देशांकों के परम अंतरों का योग करके निकाली जाती है। अब 2D और 3D स्थान के उदाहरणों से इसे समझते हैं।

2D उदाहरण

दो बिंदुओं पर विचार करें: A(1, 1) और B(4, 5):

1. |x₁ - x₂| = |1 - 4| = 3 की गणना करें
2. |y₁ - y₂| = |1 - 5| = 4 की गणना करें
3. परिणाम जोड़ें: 3 + 4 = 7

अतः, A और B के बीच Manhattan distance 7 इकाई है। 

दो वेक्टरों की Manhattan distance। लेखक द्वारा छवि।

इस 2D ग्रिड में, आप देख सकते हैं कि Manhattan distance वही मार्ग अनुसरण करती है जो एक टैक्सी लेगी—बिंदु A से बिंदु B तक केवल क्षैतिज और ऊर्ध्वाधर दिशा में चलकर।

3D उदाहरण

अब, 3D स्थान में दो बिंदुओं पर विचार करें: A(1, 2, 3) और B(4, 5, 6):

1. |x₁ - x₂| = |1 - 4| = 3 की गणना करें
2. |y₁ - y₂| = |2 - 5| = 3 की गणना करें
3. |z₁ - z₂| = |3 - 6| = 3 की गणना करें
4. परिणाम जोड़ें: 3 + 3 + 3 = 9

इन 3D बिंदुओं के बीच Manhattan distance 9 इकाई है।

Euclidean distance से तुलना

जहाँ Manhattan distance ग्रिड लाइनों के साथ मार्ग को मापती है, वहीं Euclidean distance दो बिंदुओं के बीच सीधी दूरी मापती है, यानी जैसा कि कहते हैं, "सीधे आसमान के रास्ते।" 

हमारे 2D उदाहरण के लिए:

• Manhattan distance: 7 इकाई
• Euclidean distance: √((1-4)^² + (1-5)^²) = 5 इकाई

यहाँ Manhattan और Euclidean दूरी के बीच दृश्य तुलना है: 

Manhattan distance बनाम Euclidean distance। लेखक द्वारा छवि।

Euclidean स्थान में, Euclidean distance हमेशा Manhattan distance से कम या उसके बराबर होती है। 

Manhattan distance और Euclidean distance में से चयन

Manhattan distance विशेष रूप से निम्न परिस्थितियों में उपयोगी है:

1. गति ग्रिड-जैसे मार्गों तक सीमित हो (जैसे, शहर की ब्लॉक सड़कों, सर्किट बोर्ड लेआउट)।
2. तिरछी (diagonal) चाल की अनुमति न हो या वह अधिक महंगी हो।
3. आप मशीन लर्निंग में उच्च-आयामी डेटा के साथ काम कर रहे हों, जहाँ यह Euclidean distance की तुलना में संगणकीय रूप से अधिक कुशल हो सकती है।
4. आप विभाज्य (discrete) या क्रमिक (ordinal) डेटा में अंतरों का विश्लेषण कर रहे हों।

इसके विपरीत, Euclidean distance तब अधिक उपयुक्त है जब:

1. आप खुले स्थानों में भौतिक दूरी माप रहे हों।
2. आप निरंतर (continuous) डेटा के साथ काम कर रहे हों, जहाँ तिरछी चालें समान रूप से मान्य हैं।

Manhattan Distance के उपयोग

Manhattan distance का उपयोग कंप्यूटर विज्ञान, डेटा विश्लेषण और भू-स्थानिक प्रौद्योगिकी के विभिन्न क्षेत्रों में होता है। यहाँ कुछ प्रमुख क्षेत्र हैं जहाँ Manhattan distance विशेष रूप से उपयोगी है।

पाथफाइंडिंग एल्गोरिदम (जैसे, A* algorithm) 

ग्रिड-आधारित परिवेशों में, Manhattan distance दो बिंदुओं के बीच दूरी का आकलन करने के लिए एक त्वरित और प्रभावी हेयुरिस्टिक प्रदान करती है। यह A* एल्गोरिदम में विशेष रूप से उपयोगी है, जहाँ क्षैतिज और ऊर्ध्वाधर दिशाओं तक सीमित गति के परिदृश्यों में यह खोज को लक्ष्य की ओर अधिक कुशलता से निर्देशित करने में मदद करती है। शहर की सड़कों में रूटिंग, भूलभुलैया-सुलझाने वाले एल्गोरिदम और कुछ प्रकार के वीडियो गेम AI पाथफाइंडिंग के बारे में सोचें। 

क्लस्टरिंग तकनीकें (जैसे, K-Means clustering) 

Manhattan distance का उपयोग क्लस्टरिंग एल्गोरिदम में दूरी मेट्रिक के रूप में किया जा सकता है, विशेषकर उच्च-आयामी डेटा के साथ। K-Means क्लस्टरिंग में, Euclidean distance के स्थान पर Manhattan distance का उपयोग बेहतर परिणाम दे सकता है, खासकर विरल (sparse) उच्च-आयामी डेटा या बाह्य मानों (outliers) की उपस्थिति में। साथ ही, यह पाठ वर्गीकरण और दस्तावेज़ क्लस्टरिंग में अक्सर पसंद की जाती है क्योंकि यह विरल वेक्टर स्पेस में प्रभावी होती है। व्यक्तिगत आयामों में अत्यधिक मानों के प्रति Manhattan distance की कम संवेदनशीलता कुछ डेटासेट में अधिक संतुलित क्लस्टरिंग परिणाम दे सकती है।

छवि पहचान 

Manhattan distance का उपयोग पिक्सेल मानों या फीचर वेक्टरों की तुलना करने में किया जा सकता है। यह विशेष रूप से टेम्पलेट मिलान (template matching) में उपयोगी है, जहाँ आप किसी बड़े चित्र के भीतर किसी छोटे चित्र की आवृत्तियों को ढूँढना चाहते हैं। यह चेहरे की पहचान प्रणालियों, वीडियो स्ट्रीम में ऑब्जेक्ट डिटेक्शन, या बड़े इमेज डेटाबेस में पैटर्न मिलान में भी मूल्यवान है, जहाँ गति महत्वपूर्ण होती है और Euclidean distance की तुलना में थोड़ी सटीकता में कमी अक्सर नगण्य होती है।

आउटलायर पहचान 

Manhattan distance का उपयोग ऐसे डेटा बिंदुओं की पहचान के लिए किया जा सकता है जो किसी डेटासेट में अन्य से काफी भिन्न हों, क्योंकि यह Euclidean distance की तुलना में व्यक्तिगत आयामों में अत्यधिक मानों के प्रति कम संवेदनशील होती है। यह गुण इसे विसंगति (anomaly) पहचान प्रणालियों में उपयोगी बनाता है, जैसे धोखाधड़ी का पता लगाना या नेटवर्क सुरक्षा। उदाहरण के लिए, वित्तीय प्रणालियों में Manhattan distance किसी एकल विशेषता में अत्यधिक मानों से अत्यधिक प्रभावित हुए बिना असामान्य लेनदेन पैटर्न की पहचान करने में मदद कर सकती है, जिससे संभावित रूप से कम गलतियाँ होती हैं।

Geographic Information Systems (GIS) 

GIS अनुप्रयोगों में, Manhattan distance ग्रिड-जैसे सड़क नेटवर्क के साथ गति का मॉडल बना सकती है, जिससे यह शहरी नियोजन और लॉजिस्टिक्स के लिए उपयोगी बनती है। इसका उपयोग स्थान-आवंटन (location-allocation) समस्याओं में होता है, जैसे किसी शहर में कुल यात्रा दूरी को न्यूनतम करते हुए सुविधाओं के इष्टतम स्थान निर्धारित करना। Manhattan distance का उपयोग स्थानिक विश्लेषण कार्यों में भी किया जा सकता है, जैसे सड़कों या नदियों जैसी रैखिक विशेषताओं के चारों ओर बफर ज़ोन बनाना। शहरी योजनाकार सार्वजनिक सेवाओं की पहुँच का विश्लेषण करने के लिए Manhattan distance का उपयोग कर सकते हैं, जबकि लॉजिस्टिक्स कंपनियाँ शहरों में डिलीवरी मार्गों को अनुकूलित करने के लिए इसका सहारा ले सकती हैं।

Manhattan Distance के गणितीय गुण

Manhattan distance में कई महत्वपूर्ण गणितीय गुण होते हैं जो इसे विशेष रूप से उपयोगी बनाते हैं। आइए दो प्रमुख पहलुओं को समझें: इसका मीट्रिक स्पेस गुण और आउटलायर के प्रति इसकी दृढ़ता।

मीट्रिक स्पेस गुण

Manhattan distance एक सच्चा मीट्रिक है, यानी यह मीट्रिक स्पेस में दूरी फ़ंक्शन के लिए आवश्यक सभी चार शर्तों को पूरा करती है:

1. अऋणात्मकता (Non-negativity): किसी भी दो बिंदुओं के बीच दूरी हमेशा अऋणात्मक होती है। d(x, y) ≥ 0 सभी x और y के लिए।
2. अभेद्यताओं की समानता (Identity of indiscernibles): किसी बिंदु और स्वयं के बीच दूरी शून्य होती है, और यदि दो बिंदुओं के बीच दूरी शून्य है, तो वे वही बिंदु हैं। d(x, y) = 0 तभी और केवल तभी जब x = y।
3. सममिति (Symmetry): बिंदु A से बिंदु B तक की दूरी, B से A तक की दूरी के समान होती है। d(x, y) = d(y, x) सभी x और y के लिए।
4. त्रिभुज असमता (Triangle inequality): दो बिंदुओं के बीच दूरी हमेशा उन बिंदुओं और किसी तीसरे बिंदु के साथ दूरियों के योग से कम या उसके बराबर होती है। d(x, z) ≤ d(x, y) + d(y, z) सभी x, y, और z के लिए।

cosine distance के विपरीत, जो त्रिभुज असमता को संतुष्ट नहीं करती, Manhattan distance का इन सभी गुणों का पालन करना इसे विभिन्न गणितीय और संगणकीय अनुप्रयोगों में उपयोगी बनाता है। उदाहरण के लिए:

• अनुकूलन (optimization) एल्गोरिदम में, त्रिभुज असमता का उपयोग खोज स्थान को कुशलतापूर्वक छांटने (prune) के लिए किया जा सकता है।
• metric trees जैसे डेटा स्ट्रक्चर में, ये गुण तेज़ nearest-neighbor खोजों को संभव बनाते हैं।
• मशीन लर्निंग में, दूरी मेट्रिक्स पर निर्भर एल्गोरिदम (जैसे k-nearest neighbors) सैद्धांतिक गारंटी और कुशल इम्प्लीमेंटेशन के लिए इन गुणों का लाभ उठा सकते हैं।

आउटलायर के प्रति बेहतर भेदभाव 

अपनी रैखिक योग विधि के कारण, Manhattan distance अक्सर Euclidean distance की तुलना में आउटलायर का बेहतर भेदभाव प्रदान करती है, जो अंतरों का वर्ग करती है। यह अंतर इसलिए उत्पन्न होता है क्योंकि Manhattan distance प्रत्येक आयाम में परम अंतरों को स्वतंत्र रूप से जोड़ती है, जिससे किसी एकल आयाम में बड़े अंतर के भारी प्रभाव को कम किया जा सके।

2D स्थान में दो बिंदुओं पर विचार करें: A(0, 0) और B(10, 0)। अब एक आउटलायर बिंदु C लें, जिसके निर्देशांक (0, 100) हैं:

• A और C के बीच Manhattan distance: |0 - 0| + |0 - 100| = 100
• A और C के बीच Euclidean distance: √((0 - 0)^² + (0 - 100)^²) = 100
• B और C के बीच Manhattan distance: |10 - 0| + |0 - 100| = 110
• B और C के बीच Euclidean distance: √((10 - 0)^² + (0 - 100)^²) ≈ 100.5

आउटलायर के साथ Manhattan बनाम Euclidean distance। लेखक द्वारा छवि

इस उदाहरण में, Manhattan distance AC और BC की दूरियों में स्पष्ट अंतर दर्शाती है, जबकि Euclidean distance y-निर्देशांक में आउटलायर के प्रभाव के कारण उन्हें लगभग समान दिखाती है।

यह गुण Manhattan distance को विशेष रूप से निम्न में उपयोगी बनाता है:

1. उच्च-आयामी स्थान, जहाँ आउटलायर सामान्य होते हैं, जैसे छवि संसाधन (image processing) या पाठ विश्लेषण।
2. क्लस्टरिंग एल्गोरिदम, जहाँ आप क्लस्टर सेंट्रॉइड्स पर आउटलायर के प्रभाव को कम करना चाहते हैं।
3. विसंगति पहचान प्रणालियाँ, जहाँ आप आउटलायर की पहचान करना चाहते हैं, बिना उनकी महत्ता को अनावश्यक रूप से बढ़ाए।

व्यक्तिगत आयामों में अत्यधिक मानों के प्रति कम संवेदनशील होने के कारण, Manhattan distance कई वास्तविक दुनिया के डेटासेट—विशेषकर शोरयुक्त या अपूर्ण डेटा वाले—में असमानता का अधिक संतुलित माप प्रदान कर सकती है।

Python और R में Manhattan Distance

यहाँ, हम Python और R का उपयोग करके Manhattan distance की गणना करने के तरीके देखेंगे। प्रत्येक उदाहरण कस्टम फ़ंक्शन से लेकर लाइब्रेरी मेथड तक अलग-अलग दृष्टिकोणों को दर्शाएगा।

Python उदाहरण

Python Manhattan distance निकालने के कई तरीके प्रदान करता है। आइए दो विभिन्न विधियाँ देखें।

1. NumPy arrays का उपयोग करके गणना:

import numpy as np
point_a_np = np.array([1, 1, 1])
point_b_np = np.array([4, 5, 6])
distance_numpy = np.sum(np.abs(point_a_np - point_b_np))
print(f"Manhattan distance (NumPy): {distance_numpy}")संचालित द्वारा

आउटपुट: 

Manhattan distance (NumPy): 12संचालित द्वारा

यह विधि सीधे NumPy arrays का उपयोग करती है, जो विशेष रूप से बड़े डेटासेट के साथ काम करते समय या जब आप पहले से ही अपने विश्लेषण में NumPy arrays का उपयोग कर रहे हों, तब बहुत कुशल हो सकती है।

2. SciPy की cityblock() फ़ंक्शन का उपयोग करके गणना: 

from scipy.spatial.distance import cityblock
point_a = (1, 1, 1)
point_b = (4, 5, 6)
distance_scipy = cityblock(point_a, point_b)
print(f"Manhattan distance (SciPy): {distance_scipy}")संचालित द्वारा

आउटपुट:

Manhattan distance (SciPy): 12संचालित द्वारा

SciPy cityblock() फ़ंक्शन प्रदान करता है, जो Manhattan distance की गणना करता है। यह तरीका सीधा और कुशल है, विशेषकर जब आप अपने प्रोजेक्ट में SciPy के साथ काम कर रहे हों। 

R उदाहरण

R भी Manhattan distance निकालने के कई तरीके प्रदान करता है। आइए दो अलग-अलग दृष्टिकोण देखें।

1. कस्टम फ़ंक्शन बनाना

manhattan_distance <- function(x1, y1, x2, y2) {
  abs(x1 - x2) + abs(y1 - y2)
}
# Example points 
point1 <- c(3, 5) # (x1, y1) 
point2 <- c(1, 9) # (x2, y2) 
# Calculate Manhattan distance between point1 and point2 
distance <- manhattan_distance(point1[1], point1[2], point2[1], point2[2]) 
print(paste("Manhattan distance (custom function):", distance))संचालित द्वारा

आउटपुट:

"Manhattan distance (custom function): 6"संचालित द्वारा

इस उदाहरण में, हम manhattan_distance नाम का एक कस्टम फ़ंक्शन बनाते हैं। यह फ़ंक्शन इनपुट के रूप में दो बिंदुओं के निर्देशांक लेता है और उनके संबंधित निर्देशांकों के परम अंतरों को जोड़कर Manhattan distance निकालता है।

2. stats लाइब्रेरी का उपयोग

point_a <- c(1, 1, 1)
point_b <- c(4, 5, 6)
distance_builtin <- stats::dist(rbind(point_a, point_b), method = "manhattan")
print(paste("Manhattan distance:", distance_builtin))संचालित द्वारा

आउटपुट: 

"Manhattan distance: 12"संचालित द्वारा

दूसरे उदाहरण में, हम stats पैकेज के dist() फ़ंक्शन का उपयोग Manhattan distance की गणना के लिए करते हैं। जब आप मैट्रिस या कई बिंदुओं से निपट रहे हों, तो यह दृष्टिकोण प्रक्रिया को काफी सरल बना देता है।

निष्कर्ष

Manhattan distance का महत्व इसकी सादगी, संगणकीय दक्षता और कुछ परिदृश्यों में आउटलायर के प्रति इसकी दृढ़ता में निहित है। Euclidean distance के विपरीत, Manhattan distance अक्सर ग्रिड-आधारित प्रणालियों में अधिक सहज परिणाम देती है और विशेषकर उच्च-आयामी स्थानों में गणना के लिए अधिक कुशल हो सकती है। 

इसके अलावा, Manhattan distance और अन्य दूरी मेट्रिक्स का उपयोग विविध स्थानों पर होता है। हमारे Designing Machine Learning Workflows in Python पाठ्यक्रम, जिसमें दूरी-आधारित लर्निंग पर एक अध्याय शामिल है, और Cluster Analysis in R पाठ्यक्रम, जो वर्गीकरण और आयामीय न्यूनीकरण के लिए दूरी-आधारित मेट्रिक्स का उपयोग करता है, के अतिरिक्त, आप हमारा Anomaly Detection in Python पाठ्यक्रम भी देख सकते हैं, जो आउटलायर डिटेक्शन और फीचर स्केलिंग के लिए दूरी मेट्रिक्स का उपयोग करता है।  

ध्यान रखें, दूरी मेट्रिक का चुनाव आपके एल्गोरिदम के प्रदर्शन और परिणामों पर महत्वपूर्ण प्रभाव डाल सकता है। यह समझकर कि Manhattan distance का उपयोग कब और कैसे करना है, आप अपने डेटा साइंस टूलकिट में एक शक्तिशाली उपकरण जोड़ रहे हैं। प्रयोग करते रहें, सीखते रहें, और दूरी-आधारित एल्गोरिदम के साथ संभावनाओं की सीमाएँ आगे बढ़ाते रहें!