अक्षांश/देशांतर बिंदुओं को कैसे समूहित करें जो एक दूसरे के लिए 'करीबी' हैं?

मेरे पास उपयोगकर्ता के अक्षांश/देशांतर बिंदुओं का डेटाबेस है और मैं 'करीबी' बिंदुओं को एक साथ समूहबद्ध करने की कोशिश कर रहा हूं। 'बंद' सापेक्ष है, लेकिन अब के लिए यह ~ 500 फीट लगता है।अक्षांश/देशांतर बिंदुओं को कैसे समूहित करें जो एक दूसरे के लिए 'करीबी' हैं?

पहले ऐसा लगता था कि मैं केवल उन पंक्तियों से समूह कर सकता हूं जिनके पास पहले 3 दशमलव स्थानों (लगभग 300x300 बॉक्स) के लिए समान अक्षांश/देशांतर है, यह समझते हुए कि यह भूमध्य रेखा से दूर जाने के बाद बदलता है)।

हालांकि, यह विधि काफी कम लगती है। 'निकटता' प्रत्येक दशमलव स्थान का प्रतिनिधित्व करने की दूरी से काफी अलग नहीं हो सकता है। यह ध्यान में नहीं रखता है कि दो स्थानों में तीसरे (या किसी भी) दशमलव स्थान में अलग-अलग अंक हो सकते हैं, लेकिन फिर भी उस स्थान के भीतर हो सकते हैं जो स्थान प्रदर्शित करता है (33.1239 और 33.1240)।

मैंने उस स्थिति पर भी ध्यान दिया है जहां प्वाइंट ए, और प्वाइंट सी प्वाइंट बी (लेकिन एक दूसरे नहीं) दोनों 'करीबी' हैं - क्या उन्हें एक साथ समूहीकृत किया जाना चाहिए? यदि हां, तो क्या होता है जब प्वाइंट डी सी (और कोई अन्य बिंदु) इंगित करने के लिए 'बंद' होता है - इसे भी समूहीकृत किया जाना चाहिए। निश्चित रूप से मुझे वांछित व्यवहार निर्धारित करना है, लेकिन या तो कैसे लागू किया जाएगा?

क्या कोई मुझे सही दिशा में इंगित कर सकता है कि यह कैसे किया जा सकता है और विभिन्न तरीकों/दृष्टिकोणों का उपयोग कैसे किया जा सकता है?

मुझे लगता है कि मुझे कुछ स्पष्ट याद आ रही है।

वर्तमान में डेटा एक MySQL डेटाबेस है, जो एक PHP अनुप्रयोग द्वारा उपयोग किया जाता है; हालांकि, अगर मैं इसे पूरा करने में महत्वपूर्ण भूमिका निभाता हूं तो मैं अन्य स्टोरेज विधियों के लिए खुला हूं। यहाँ।

स्रोत

2010-12-03 Tim Lytle

शायद यहां कुछ जानकारी हो सकती है: http://en.wikipedia.org/wiki/Geodatabase –

नहीं। कोई भी आपको सही दिशा में इंगित नहीं कर सकता है जबतक कि आप यह नहीं बताते कि आपका लक्ष्य क्या है। आप अंक क्यों समूहित करना चाहते हैं? – Unreason

@ यूरेनसन - थोड़ा और विस्तार, अंक उपयोगकर्ताओं के 'फ़्लैगिंग' को कुछ स्थानों का प्रतिनिधित्व करते हैं, धारणा यह है कि यदि एकाधिक उपयोगकर्ताओं ने एक-दूसरे के निकट फ़्लैग किए गए स्थान को ध्वजांकित किया है, तो इसे केवल एक स्थान के रूप में गिना जाना चाहिए।हालांकि, एक दूसरे के ~ 500 फीट के भीतर लेट/लम्बे बिंदु को समूहित करने का निर्दिष्ट लक्ष्य बहुत विशिष्ट लगता है, और पहले ही सूचनात्मक उत्तर उत्पन्न कर चुका है। –

दो बिंदुओं के बीच दूरी निर्धारित करने के कई तरीके हैं, लेकिन 2-डी ग्राफ पर बिंदुओं को प्लॉट करने के लिए आप शायद Euclidean distance चाहते हैं। (x1, y1) अपना पहला बिंदु का प्रतिनिधित्व करता है और अपने दूसरे (x2, y2) प्रतिनिधित्व करता है, दूरी

d = sqrt((x2-x1)^2 + (y2-y1)^2)

समूह के बारे में

है, तो आप 2-डी में किसी प्रकार का उपयोग करने के लिए इसका मतलब यह निर्धारित करने के लिए कैसे "बंद" बातें एक दूसरे से कर रहे हैं चाहते हो सकता है।

x(mean) = (x1+x2+x3)/3 
y(mean) = (y1+y2+y3)/3

फिर आप देख सकते हैं कि करीब प्रत्येक यह है कि क्या यह निर्धारित करने के केंद्र के लिए है: उदाहरण के लिए, आप तीन अंक, (x1, y1), (x2, y2), (x3, y3) है, तो आप इन तीन अंक के केंद्र सरल औसत से पा सकते हैं "क्लस्टर" का हिस्सा होना चाहिए।

तरीके, जो सभी के एक clustering algorithm किसी भिन्न रूप का उपयोग एक समूहों को परिभाषित कर सकते की एक संख्या हैं। मैं अब भीड़ में हूं और संक्षेप में समय नहीं है, लेकिन लिंक और एल्गोरिदम देखें, और उम्मीद है कि अन्य लोग अधिक जानकारी प्रदान करने में सक्षम होंगे। सौभाग्य!

स्रोत

2010-12-03 19:42:06 eykanal

किसी भी विचार को समूहबद्ध करने के लिए दृष्टिकोण को बड़ी संख्या में अंक का उपयोग करके कार्यान्वित किया जाएगा? –

हाँ, मैं उम्मीद कर रहा था कि आप यह नहीं पूछेंगे :) बहुत सारे परिष्कृत क्लस्टरिंग एल्गोरिदम हैं, और मैं कुछ को प्रतिबिंबित करने के लिए पोस्ट अपडेट करूंगा। – eykanal

दूरी कहानी का केवल एक हिस्सा है। (0,0) और आर = "दूरी" में केंद्र के साथ एक सर्कल पर स्थित अंकों की एक अनंत संख्या हो सकती है। और वे एक-दूसरे से बहुत दूर हो सकते हैं। आपको कोण भी निर्धारित करना चाहिए। बेशक कुछ क्लस्टरिंग एल्गोरिदम उस समस्या का असली जवाब है। –

अगर मैं इसे हल कर रहा था, तो मैं एक ग्रिड से शुरू करूंगा। प्रत्येक बिंदु को ग्रिड पर एक वर्ग में रखें। घनी आबादी वाले ग्रिड की तलाश करें। यदि आसन्न ग्रिड आबादी नहीं हैं, तो आपके पास एक सभ्य समूह है।

यदि आपके पास घनी आबादी वाले ग्रिड हैं, तो आप हमेशा प्रत्येक ग्रिड के केंद्र में एक सर्कल छोड़ सकते हैं और सर्कल एरिया बनाम (सर्कल में अंक की संख्या * कुछ ट्यूनेबल वेट) के लिए अनुकूलित कर सकते हैं। सही नहीं है, लेकिन आसान है। बेहतर समूह अधिक जटिल अनुकूलन समस्याएं हैं।

स्रोत

2010-12-03 19:42:20 patros

शायद ओवरकिल, लेकिन मुझे लगता है कि यह clustering problem: दूरी measure निर्धारित करेगा कि दो तत्वों की समानता की गणना कैसे की जाती है। यदि आप एक कम अनुभवहीन समाधान की कोशिश Data Mining: Practical Machine Learning Tools and Techniques, और प्रयोग Weka या Orange

स्रोत

2010-12-03 19:52:29

कुछ प्रयोग विधि आप अपने प्रश्न के परिणाम की एक अनुमानित सेट प्राप्त करने के लिए में उल्लिखित के समान है, तो छीलना कि उचित गणना करके नीचे सेट अनुमानित की जरूरत है। यदि आप अपना ग्रिड आकार चुनते हैं (यानी आप अपने समन्वय को कितना गोल करते हैं) सही ढंग से, आप कम से कम एक स्वीकार्य स्तर पर किए जाने वाले काम को कम करने की उम्मीद कर सकते हैं, हालांकि आपको यह समझना है कि वह ग्रिड आकार क्या है।

उदाहरण के लिए, earthdistance PostgreSQL के लिए एक्सटेंशन (एक्स, वाई, जेड) कार्तीय समन्वय करने के लिए अक्षांश/देशांतर जोड़े परिवर्तित करने, एक समान क्षेत्र के रूप में पृथ्वी मॉडलिंग से काम करता है। PostgreSQL में एक परिष्कृत इंडेक्सिंग सिस्टम है जो इन समन्वय, या उनके चारों ओर के बक्से को आर-पेड़ों में अनुक्रमित करने की अनुमति देता है, लेकिन आप इसके साथ कुछ भी उपयोगी बना सकते हैं जो अभी भी उपयोगी है।

यदि आप अपना (एक्स, वाई, जेड) ट्रिपल और राउंड ऑफ लेते हैं- यानी कुछ कारकों से गुणा करें और पूर्णांक के लिए छंटनी करें- तब आपके पास तीन पूर्णांक होते हैं जिन्हें आप "बॉक्स नाम" बनाने के लिए संयोजित कर सकते हैं, जो एक पहचानता है बिंदु "

यदि आप कुछ लक्ष्य बिंदु के एक्स किमी के भीतर सभी बिंदुओं को खोजना चाहते हैं, तो आप उस बिंदु के चारों ओर सभी" बॉक्स नाम "उत्पन्न करते हैं (एक बार जब आप अपना परिवर्तित कर लेते हैं एक बिंदु (x, y, z) ट्रिपल के साथ लक्ष्य बिंदु, यह आसान है) और उन सभी बक्से को खत्म करें जो पृथ्वी की सतह को घुमाते नहीं हैं (चालक, लेकिन प्रत्येक कोने में x^2+y^2+z^2=R^2 सूत्र का उपयोग आपको बताएगा) आप समाप्त होते हैं बक्से लक्ष्य बिंदुओं की एक सूची के साथ-साथ बस उन बॉक्सों में से किसी एक से मेल खाने वाले सभी बिंदुओं की खोज हो सकती है, जो आपको कुछ अतिरिक्त वापस भी लाएंगी अंक। तो एक अंतिम चरण के रूप में आपको अपने लक्षित बिंदु की वास्तविक दूरी की गणना करने और कुछ को खत्म करने की आवश्यकता है (फिर से, यह कार्टेशियन समन्वय में काम करके और अपने लक्ष्य को महान-चक्र दूरी त्रिज्या को दूरस्थ दूरी में परिवर्तित करके बढ़ाया जा सकता है)।

यह सुनिश्चित करने के लिए चारों ओर झुकाव नीचे आता है कि आपको बहुत सारे बॉक्स खोजना नहीं है, लेकिन साथ ही साथ कई अतिरिक्त अंक भी नहीं लाएंगे। मुझे कई अलग-अलग ग्रिड पर प्रत्येक बिंदु को इंडेक्स करने में उपयोगी पाया गया है (उदाहरण के लिए 1 किमी, 5 किमी, 25 किमी, 125 किमी आदि के संकल्प)। आदर्श रूप में आप केवल एक बॉक्स खोजना चाहते हैं, याद रखें कि जैसे ही आपका लक्षित त्रिज्या आपके ग्रिड आकार से अधिक हो जाता है, कम से कम 27 तक फैलता है।

मैंने इस तकनीक का उपयोग SQL डेटाबेस में गणना करने के बजाय लुसीन का उपयोग करके एक स्थानिक अनुक्रमणिका बनाने के लिए किया है। यह काम करता है, यद्यपि इसे स्थापित करने के लिए कुछ झुकाव है, और सूचकांक उत्पन्न करने में कुछ समय लगता है और काफी बड़ा है। सभी समन्वयों को पकड़ने के लिए आर-पेड़ का उपयोग करना एक बहुत अच्छा दृष्टिकोण है, लेकिन अधिक कस्टम कोडिंग लेगा- इस तकनीक को मूल रूप से केवल एक तेज हैश-टेबल लुकअप की आवश्यकता होती है (इसलिए शायद सभी नोएसक्यूएल डेटाबेस के साथ अच्छी तरह से काम करेगा इन दिनों क्रोध, और एक एसक्यूएल डेटाबेस में भी प्रयोग योग्य होना चाहिए)।

स्रोत

2010-12-03 21:03:53 araqnid

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

स्रोत

2011-07-08 09:38:22

अक्षांश/देशांतर बिंदुओं को कैसे समूहित करें जो एक दूसरे के लिए 'करीबी' हैं?

उत्तर

संबंधित मुद्दे