3 डी एल्गोरिथ्म क्लस्टरिंग

Question

समस्या कथन: मैं निम्नलिखित समस्या है:

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

लक्ष्य: एक एल्गोरिथ्म है कि कई प्रोसेसर के लिए अच्छी तरह से बड़े पैमाने और एक छोटे स्मृति आवश्यकता है सकते हैं खोजने के लिए।

विचार: गैर-समान वितरण के कारण इस तरह की समस्या के लिए सामान्य स्थानिक अपघटन पर्याप्त नहीं है। अनियमित स्थानिक अपघटन जो समान रूप से बिंदुओं की संख्या को विभाजित करती है, हमें समस्या में मदद कर सकती है। मैं वास्तव में सराहना करता हूं कि अगर कोई इस समस्या को हल करने के तरीके पर कुछ रोशनी डाल सकता है।

Answer 1

मेरे पास आपके लिए कोई निश्चित उत्तर नहीं है, लेकिन मेरे पास एक ऐसे दृष्टिकोण के लिए एक सुझाव है जो समाधान प्रदान कर सकता है।

मुझे लगता है कि यह locality-sensitive hashing की जांच करने लायक है। मुझे लगता है कि अंक को समान रूप से विभाजित करना और फिर प्रत्येक सेट में इस तरह के एलएसएच को लागू करना आसानी से समानांतर होना चाहिए। यदि आप अपने हैशिंग एल्गोरिदम को डिज़ाइन करते हैं जैसे कि बाल्टी आकार R के संदर्भ में परिभाषित किया गया है, तो ऐसा लगता है कि बाल्टी में विभाजित बिंदुओं के दिए गए सेट के लिए, आपके मानदंडों को पूरा करने वाले बिंदु पूरी बाल्टी में मौजूद होने की संभावना है।

स्थानीय स्तर पर इस प्रदर्शन के बाद, शायद आप एक कदम वार ढंग से LSH एल्गोरिथ्म के विभिन्न समानांतर रन से स्थानिक बाल्टी गठबंधन करने के लिए नक्शे-को कम शैली रणनीति किसी तरह का आवेदन कर सकते हैं, इस तथ्य का इस्तेमाल कर रही है कि आप शुरू कर सकते हैं पूरी बाल्टी को छूटकर अपनी समस्या स्थान के कुछ हिस्सों को बाहर करने के लिए। जाहिर है आपको किनारे के मामलों के बारे में सावधान रहना होगा जो अलग-अलग बाल्टी फैलते हैं, लेकिन मुझे संदेह है कि विलय के प्रत्येक चरण में, आप अलग-अलग बाल्टी आकार/ऑफसेट्स को लागू कर सकते हैं जैसे कि आप इस प्रभाव को हटा दें (उदाहरण के लिए स्थानिक रूप से बराबर बाल्टी विलय करना, साथ ही साथ आसन्न बाल्टी के रूप में)। मेरा मानना ​​है कि इस विधि का उपयोग स्मृति आवश्यकताओं को छोटा रखने के लिए किया जा सकता है (यानी आपको किसी भी पल में अंक से ज्यादा स्टोर करने की आवश्यकता नहीं है, और आप हमेशा छोटे (आईएसएच) सबसेट पर काम कर रहे हैं)।

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

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

Answer 2

यहां समाधान के कुछ संभावित भाग हैं। प्रत्येक चरण, पर विभिन्न विकल्प हैं जो एनक्लस्टर पर निर्भर होंगे, डेटा कितनी तेजी से बदलता है, और आप किन तरीकों से क्या करना चाहते हैं।

3 चरण: मात्रा, बॉक्स, के-साधन।

1) मात्रा: XYZ समन्वय इनपुट को 8 बिट्स, कहने के लिए अलग करें, एक्स, वाई, जेड के 2^8 प्रतिशत अलग से ले कर। यह पूरे प्रवाह को विस्तार से ज्यादा नुकसान पहुंचाएगा। आप कर सकते थे तरह सभी 1G अंक, या सिर्फ एक यादृच्छिक 1M, पाने के लिए 8 बिट x0 < x1 < ... x256, Y0 < y1 < ... y256, z0 < z1 < ... z256 2 के साथ ^ (30-8) अंक प्रत्येक सीमा में। फ्लोट एक्स -> 8 बिट एक्स मानचित्र करने के लिए, अनियंत्रित बाइनरी खोज तेजी से — देखें बेंटले, मोती पी। 95.

जोड़ा गया: Kd trees अलग आकार के बक्से में किसी भी बिंदु बादल विभाजित है, ~ Leafsize के साथ प्रत्येक अंक — ज्यादा X Y Z ऊपर के रूप में विभाजित करने की तुलना में बेहतर। लेकिन afaik आपको केवल अपना पहला केडी ट्री कोड रोल करना होगा, केवल पहले 16 एम बॉक्स को विभाजित करने के लिए, और केवल अंक ही रखें, अंक नहीं।

2) बॉक्स: प्रत्येक 3 डी बॉक्स में 0 अंकों की संख्या गिनें, [xj .. xj + 1, yj .. yj + 1, zj .. zj + 1]। औसत बॉक्स में 2^(30-3 * 8) अंक होंगे; वितरण इस बात पर निर्भर करेगा कि डेटा कितना गड़बड़ है। यदि कुछ बक्से बहुत बड़े हैं या बहुत अधिक अंक प्राप्त करते हैं, तो आप ए) उन्हें 8, बी में विभाजित कर सकते हैं b) प्रत्येक बॉक्स में अन्य बिंदुओं के केंद्र को ट्रैक करें, बस अन्य जगहों पर मध्यबिंदु लें।

3) K-means clustering 2^(3 * 8) बॉक्स केंद्रों पर। (गूगल समांतर "कश्मीर का अर्थ है" -> 121k हिट।) यह आपके त्रिज्या आर पर कश्मीर उर्फ ​​Ncluster पर दृढ़ता से निर्भर करता है, यह भी एक किसी न किसी दृष्टिकोण एक heap के साथ कह 27 * Ncluster बक्से के विकसित करने के लिए किया जाएगा अधिकांश अंक, फिर अपने त्रिज्या बाधा के अधीन सबसे बड़ा ले लो। भी Color quantization देखें (मैं एक Minimum spanning tree साथ शुरू करने के लिए, तो कश्मीर समूहों प्राप्त करने के लिए K-1 सबसे लंबे समय तक लिंक निकालें। की तरह)।

मैं शुरुआत से एक पैरामीटर, यहां 8, एनबीटी बनाउंगा।

आपका एनक्लस्टर क्या है?

जोड़ा गया: यदि आपके अंक समय पर चल रहे हैं, तो collision-detection-of-huge-number-of-circles पर SO पर देखें।

Answer 3

बस एक विचार। दूरी < आर

इस प्रकार के ग्राफ का निर्माण स्थानिक अपघटन के समान होता है जब अंक के बीच दिए गए बिंदुओं और किनारों के साथ एक ग्राफ बनाएं। ग्राफ़ में स्थानीय खोज के साथ आपके प्रश्नों का उत्तर दिया जा सकता है। सबसे पहले अधिकतम डिग्री के साथ शिखर होते हैं, दूसरा अधिकतम डिग्री शिखर के अधिकतम अनकनेक्टेड सेट की खोज कर रहा है।

मुझे लगता है कि ग्राफ और खोज का निर्माण समानांतर बनाया जा सकता है। इस दृष्टिकोण में बड़ी स्मृति आवश्यकता हो सकती है। डोमेन को विभाजित करना और छोटे संस्करणों के लिए ग्राफ के साथ काम करना स्मृति की आवश्यकता को कम कर सकता है।

Answer 4

ऑक्ट्री का उपयोग करें। एक सीमित मूल्य डोमेन के साथ 3 डी डेटा के लिए जो विशाल डेटा सेट के लिए बहुत अच्छी तरह से स्केल करता है।

ऐसे इलाके संवेदनशील हैशिंग के रूप में ऊपर उल्लिखित तरीकों में से कई ज्यादा उच्च आयामी स्वरूप जहां समझदारी से अब और विभाजित नहीं कर सकते के लिए बनाया गया अनुमानित संस्करण हैं।

प्रत्येक स्तर पर 8 डिब्बे में विभाजित (डी = 3 के लिए 2^डी) बहुत अच्छी तरह से काम करता है। और चूंकि आप सेल में बहुत कम अंक होने पर रोक सकते हैं, और एक गहरे पेड़ का निर्माण कर सकते हैं जहां बहुत से अंक हैं जो आपकी आवश्यकताओं को अच्छी तरह फिट कर सकते हैं।

अधिक जानकारी के लिए विकिपीडिया देखें:

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

वैकल्पिक रूप से, आप एक आर-वृक्ष बनाने की कोशिश कर सकते हैं। लेकिन आर-पेड़ संतुलन करने की कोशिश करता है, जिससे सबसे घने क्षेत्रों को ढूंढना मुश्किल हो जाता है। आपके विशेष कार्य के लिए, यह ऑक्टिक के वास्तव में उपयोगी है! आर-पेड़ पेड़ की गहराई को हर जगह बराबर रखने में बहुत मेहनत करता है, ताकि प्रत्येक बिंदु लगभग एक ही समय में पाया जा सके। हालांकि, आप केवल घने क्षेत्रों में दिलचस्पी रखते हैं, जो कि अभी भी वास्तविक बिंदुओं को देखने के बिना अक्टूबर के सबसे लंबे रास्ते पर पाए जाएंगे!

Answer 5

मैं एक ऑक्टेट का उपयोग करने का सुझाव भी दूंगा। विशाल 3 डी बिंदु बादलों से निपटने में OctoMap ढांचा बहुत अच्छा है। यह सभी बिंदुओं को सीधे स्टोर नहीं करता है, लेकिन प्रत्येक नोड (उर्फ 3 डी बॉक्स) के अधिभोग घनत्व को अद्यतन करता है। पेड़ के निर्माण के बाद, आप उच्च घनत्व वाले नोड को खोजने के लिए एक सरल इटरेटर का उपयोग कर सकते हैं। यदि आप नोड्स के अंदर बिंदु घनत्व या वितरण मॉडल करना चाहते हैं, तो ऑक्टोमैप को अपनाने में बहुत आसान है।

Here आप देख सकते हैं कि इसे प्लानर मॉडल का उपयोग करके बिंदु वितरण मॉडल के लिए कैसे बढ़ाया गया था।