स्ट्रीमिंग डेटा के लिए हिस्टोग्राम अनुमान

Question

यह प्रश्न एक answered here का थोड़ा सा विस्तार है। मैं this paper की धारा 2.1 में पाए गए हिस्टोग्राम अनुमान के संस्करण को फिर से कार्यान्वित करने पर काम कर रहा हूं, और मैं इस प्रक्रिया को फिर से शुरू करने से पहले अपने सभी बतखों को एक पंक्ति में प्राप्त करना चाहता हूं। पिछली बार, मैंने boost::multi_index का उपयोग किया था, लेकिन प्रदर्शन सबसे बड़ा नहीं था, और मैं std::set की बाल्टी डालने/जटिलता की संख्या में लॉगरिदमिक से बचना चाहता हूं। हिस्टोग्राम की संख्या के कारण मैं उपयोग कर रहा हूं (यादृच्छिक जंगल में एक यादृच्छिक पेड़ के प्रति पत्ती नोड प्रति वर्ग प्रति फ़ीचर), कम्प्यूटेशनल जटिलता जितनी संभव हो सके स्थिर के करीब होनी चाहिए।

हिस्टोग्राम को लागू करने के लिए उपयोग की जाने वाली एक मानक तकनीक में बिन संख्या में इनपुट वास्तविक मान मैपिंग शामिल है। इसे पूरा करने के लिए, एक विधि है:

1. आकार एन की एक मानक सी सरणी शुरू करें, जहां एन = डिब्बे की संख्या; और
2. कुछ कारक और फर्श द्वारा इनपुट मान (वास्तविक संख्या) को गुणा करें जिसके परिणामस्वरूप सी सरणी में इसकी अनुक्रमणिका प्राप्त होती है।

यह समान बिन आकार के साथ हिस्टोग्राम के लिए अच्छी तरह से काम करता है, और यह काफी कुशल है। हालांकि, उपरोक्त लिंक किए गए पेपर की धारा 2.1 एक समान बिन आकार के बिना एक हिस्टोग्राम एल्गोरिदम प्रदान करता है।

एक और मुद्दा यह है कि केवल एक वास्तविक कारक इनपुट वास्तविक मूल्य को एक कारक द्वारा गुणा करना और परिणामस्वरूप उत्पाद का उपयोग करके सूचकांक नकारात्मक संख्याओं में विफल रहता है। इसे हल करने के लिए, मैंने सरणी में कहीं भी '0' बिन की पहचान करने पर विचार किया। यह बिन 0.0 पर केंद्रित होगा; इसके ऊपर/नीचे दिए गए डिब्बे की गणना उसी मल्टीप्ली-एंड-फर्श विधि का उपयोग करके की जा सकती है, जिसमें मामूली संशोधन किया गया है कि फ़्लोर किए गए उत्पाद को दो में जोड़ा जा सकता है या आवश्यकतानुसार दो से घटाया जा सकता है।

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

तो यही वह जगह है जहां मैं अभी अटक गया हूं, इस प्रमुख प्रश्न की ओर अग्रसर है: लागू करने का सबसे अच्छा तरीका क्या है एक हिस्टोग्राम स्ट्रीमिंग डेटा स्वीकार कर रहा है और प्रत्येक नमूना को समान आकार के डिब्बे में संग्रहीत कर रहा है?

Answer 1

चार चर रखें।

int N; // assume for simplicity that N is even 
int count[N]; 
double lower_bound; 
double bin_size; 

एक नया नमूना x आता है, गणना double i = floor(x - lower_bound)/bin_size। यदि i >= 0 && i < N, तो count[i] वृद्धि करें। यदि i >= N, तो x - lower_bound < N * bin_size तक बार-बार bin_size को दोगुना करें। प्रत्येक दोगुनी पर, गणना समायोजित करें (एकाधिक दोगुनी के लिए sparsity का शोषण करके इसे अनुकूलित करें)। क्योंकि हम lower_bound कम करने के लिए और साथ ही bin_size वृद्धि (फिर से, विरलता के लिए अनुकूलित या एक कदम में गिना जाता है समायोजित) की जरूरत है

for (int j = 0; j < N/2; j++) count[j] = count[2 * j] + count[2 * j + 1]; 
for (int j = N/2; j < N; j++) count[j] = 0; 

मामले i < 0, जटिल काम है।

while (lower_bound > x) { 
    lower_bound -= N * bin_size; 
    bin_size += bin_size; 
    for (int j = N - 1; j > N/2 - 1; j--) count[j] = count[2 * j - N] + count[2 * j - N + 1]; 
    for (int j = 0; j < N/2; j++) count[j] = 0; 
} 

असाधारण मामलों महंगे हैं लेकिन प्रारंभिक बिन आकार पर अपने डेटा की श्रेणी में केवल समय की एक लघुगणक संख्या होती हैं।

आप फ्लोटिंग प्वाइंट में यह लागू करते हैं तो ध्यान रखें कि फ्लोटिंग प्वाइंट संख्या वास्तविक संख्या नहीं हैं और lower_bound -= N * bin_size जैसे बयानों (इस मामले में अगर N * bin_sizelower_bound तुलना में काफी छोटा है) गलत व्यवहार कर सकता है। मैं अनुशंसा करता हूं कि bin_size हर समय रेडिक्स (आमतौर पर दो) की शक्ति हो।