Scipy.spatial.KDTree में `leafsize` को समझना

Question

समस्या का विवरण:

मेरे पास एक 3 डी स्थान में 150k अंक हैं, जो कि मैट्रिक्स में उनके निर्देशांक के साथ मैट्रिक्स में संग्रहीत हैं [150k, 3]।

मैं किसी दिए गए बिंदु के सभी पड़ोसियों को खोजना चाहता हूं pजो एक दायरे के भीतर हैं r। और मैं इसे सबसे सटीक तरीके से करना चाहता हूं।

मुझे अपना leafsizeपैरामीटर कैसे चुनना चाहिए ?

from scipy.spatial import KDTree
import numpy as np

pts = np.random.rand(150000,3)

T1 = KDTree(pts, leafsize=20)
T2 = KDTree(pts, leafsize=1)

neighbors1= T1.query_ball_point((0.3,0.2,0.1), r=2.0)
neighbors2= T2.query_ball_point((0.3,0.2,0.1), r=2.0)

np.allclose(sorted(neighbors1), sorted(neighbors2))
True

Answer 1

फ़ंक्शन query_ball_pointखोज ट्री के किसी भी संस्करण के लिए अंकों का सही सेट लौटाएगा। leafsizeपैरामीटर क्वेरी, केवल परिणाम के प्रदर्शन के परिणामों को प्रभावित नहीं करता है।

एक ही डेटा के लिए नीचे दिखाए गए दो पेड़ों की कल्पना करें (लेकिन अलग-अलग लीकेज पैरामीटर) और एक प्रश्न लाल घेरे के अंदर सभी बिंदुओं को खोज रहा है।

दोनों स्थितियों में, कोड केवल दो बिंदुओं को लौटाएगा जो लाल सर्कल के अंदर स्थित हैं। यह सर्कल को चौराहे वाले पेड़ के सभी बक्से में सभी बिंदुओं की जांच करके किया जाता है। यह प्रत्येक मामले में एक अलग राशि (यानी, अलग-अलग प्रदर्शन) की ओर जाता है। बाएं पेड़ (एक बड़ी छलाँग के अनुसार) के लिए, एल्गोरिथ्म को यह जांचना होगा कि 13 अंक सर्कल के अंदर हैं (ऊपरी चौराहे बॉक्स में 6 और निचले चौराहे बॉक्स में 7)। सही पेड़ में (जिसमें पत्तों का आकार छोटा होता है), केवल तीन बिंदुओं को संसाधित किया जाता है (ऊपरी चौराहे वाले बॉक्स में और दो निचले चौराहे वाले बॉक्स में)।

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