के बीच न्यूनतम दूरी का अनुमान लगाएं मैं लाखों 50-1000 आयामी बिंदुओं के लिए एक agglomerative, नीचे अप क्लस्टरिंग एल्गोरिदम डिजाइन कर रहा हूँ। मेरे एल्गोरिदम के दो हिस्सों में, मुझे अंक के दो समूहों की तुलना करने और दो समूहों के बीच अलगाव का निर्णय लेने की आवश्यकता है। सटीक दूरी पीयू-पी 2 के सभी जोड़े पर ली गई न्यूनतम यूक्लिडियन दूरी है जहां क्लस्टर सी 1 और पी 2 से पी 1 लिया जाता है क्लस्टर सी 2 से लिया जाता है। यदि सी 1 में एक्स अंक हैं और सी 2 में वाई अंक हैं तो इसके लिए एक्स * वाई दूरी माप की आवश्यकता होती है।दो क्लस्टर
मैं वर्तमान में एक तरीका है कि X + Y मापन की आवश्यकता में इस दूरी का अनुमान:
- क्लस्टर सी 1 के केन्द्रक Ctr1 का पता लगाएं।
- क्लस्टर सी 2 में बिंदु पी 2 खोजें जो सीआरटी 1 के सबसे नज़दीक है। (वाई तुलना।)
- पी 1 के निकटतम सी 1 में बिंदु पी 1 खोजें। (एक्स तुलना)।
- पी 1 से पी 2 की दूरी क्लस्टर सी 1 और सी 2 के बीच की दूरी का अनुमानित उपाय है। यह वास्तविक मूल्य पर ऊपरी बाध्य है।
समूहों मोटे तौर पर गोलाकार रहे हैं, यह बहुत अच्छी तरह से काम करता है। मेरा टेस्ट डेटा एलीस्पोसाइड गाऊशियन क्लस्टर से बना है, इसलिए यह बहुत अच्छी तरह से काम करता है। हालांकि, अगर क्लस्टर में अजीब, गुना, मोटा आकार होता है, तो इससे खराब परिणाम मिल सकते हैं। मेरे प्रश्न हैं:
क्या कोई एल्गोरिदम है जो एक्स + वाई दूरी माप से भी कम का उपयोग करता है और औसत मामले में अच्छी सटीकता उत्पन्न होती है?
या
वहाँ एक एल्गोरिथ्म है कि (मेरे जैसे) X + Y दूरी माप का उपयोग करता है लेकिन बेहतर खान से सटीकता उद्धार है?
(मैं "95 सी # में इस प्रोग्रामिंग रहा हूँ, लेकिन छद्म कोड में एक एल्गोरिथ्म का एक विवरण या किसी अन्य भाषा ठीक है। कृपया आर या मैटलैब से विशेष पुस्तकालय कार्यों के लिए संदर्भ से बचें। संभाव्य की गारंटी देता है के साथ एक एल्गोरिथ्म % संभावना है कि दूरी कम से कम मूल्य के 5% के भीतर है "स्वीकार्य है)
नोट:। मैं सिर्फ हालांकि नहीं उच्च आयामों के लिए जरूरी इस संबंधित सवाल है, जो एक समान समस्या पर चर्चा करता पाया,। Given two (large) sets of points, how can I efficiently find pairs that are nearest to each other?
नोट: मैं सिर्फ पता चला कि इस bichromatic निकटतम-जोड़ी समस्या कहा जाता है।
संदर्भ के लिए, यहाँ समग्र एल्गोरिथ्म क्लस्टरिंग का एक सिंहावलोकन है:
पहले पास एक स्थान-पूर्ति वक्र (हिल्बर्ट वक्र) का उपयोग छोटे समूहों में गहनतम क्षेत्रों समेकित। यह बहिष्कारों को याद करता है और अक्सर आसन्न समूहों को विलय करने में असफल रहता है जो एक दूसरे के बहुत करीब हैं। हालांकि, यह एक विशेषता अधिकतम लिंक-दूरी खोजता है। इस विशेषता दूरी से कम से अलग सभी बिंदुओं को एक साथ क्लस्टर किया जाना चाहिए। इस चरण में क्लस्टर को अपने लक्ष्य के रूप में पूर्वनिर्धारित संख्या नहीं है।
दूसरा पास समूहों को एक साथ संयोजन अगर उनकी न्यूनतम दूरी अधिकतम लिंकेज दूरी से भी कम है द्वारा एकल लिंकेज ढेर प्रदर्शन करती है। यह पदानुक्रमित क्लस्टरिंग नहीं है; यह विभाजन आधारित है। सभी क्लस्टर जिनकी न्यूनतम दूरी एक दूसरे से कम है, इस अधिकतम लिंक-दूरी से कम हो जाएगी। इस चरण में क्लस्टर को अपने लक्ष्य के रूप में पूर्वनिर्धारित संख्या नहीं है।
तीसरे पास अतिरिक्त एकल लिंकेज ढेर करता है, सब आपस में क्लस्टर दूरी छंटाई और केवल समूहों के संयोजन जब तक समूहों की संख्या समूहों की एक पूर्वनिर्धारित लक्ष्य संख्या के बराबर होती। यह कुछ आउटलाइजर्स को संभालता है, जो केवल बड़े क्लस्टर के साथ आउटलेटर्स को मर्ज करने के लिए पसंद करता है। यदि कई आउटलाइर्स (और आमतौर पर हैं) हैं, तो यह क्लस्टर को लक्ष्य में कम करने में असफल हो सकता है।
चौथा पास निकटतम बड़े क्लस्टर के साथ सभी शेष आउटलायर को जोड़ता है, लेकिन अन्य बड़े समूहों के साथ विलय करने के लिए कोई बड़ा क्लस्टर नहीं होता है। (यह उनकी बाहरी कारकों के कारण उन दोनों के बीच एक पतली श्रृंखला के गठन की वजह से गलती से विलय कर दिया जा रहा है दो आसन्न समूहों से बचाता है।)
क्या आपने कुछ ऐसा करने की कोशिश की [that] (https://en.wikipedia.org/wiki/Closest_pair_of_points_problem)? – Borbag
नहीं! यह समस्या के "नाम" को जानने में मदद करता है! धन्यवाद! मैं लेख पढ़ूंगा। लेख में –
दिलचस्प एल्गोरिदम। हालांकि, डी (आयामों की संख्या) पर पुनर्संरचनात्मक विभाजन और एल्गोरिदम की निर्भरता एक समस्या है, क्योंकि मेरे लिए, डी अक्सर के (से समूहों की संख्या) से अधिक होता है। मैं इसे आगे पढ़ूंगा। –