STING ग्रिड-आधारित क्लस्टरिंग क्या है?

STING ग्रिड-आधारित क्लस्टरिंग

ग्रिड-आधारित क्लस्टरिंग विधियां एक मल्टी-रिज़ॉल्यूशन ग्रिड डेटा संरचना का उपयोग करती हैं। यह ऑब्जेक्ट क्षेत्रों को सेल्स की एक सीमित संख्या में परिमाणित करता है जो एक ग्रिड संरचना बनाते हैं जिस पर क्लस्टरिंग के लिए सभी ऑपरेशन लागू किए जाते हैं। इस विधि का लाभ इसका त्वरित प्रसंस्करण समय है, जो आमतौर पर डेटा ऑब्जेक्ट्स की संख्या से स्वतंत्र होता है, फिर भी क्वांटाइज़्ड स्पेस में प्रत्येक आयाम में सेल्स की संख्या पर निर्भर करता है।

ग्रिड-आधारित क्लस्टरिंग मल्टी-रिज़ॉल्यूशन ग्रिड डेटा संरचना का उपयोग करता है और क्लस्टर्स बनाने के लिए घने ग्रिड सेल्स का उपयोग करता है। कई दिलचस्प विधियां हैं STING, वेव क्लस्टर, और CLIQUE।

STING (सांख्यिकीय सूचना ग्रिड दृष्टिकोण)

STING - एक सांख्यिकीय सूचना ग्रिड दृष्टिकोण। स्थानिक क्षेत्र को आयताकार सेल्स में विभाजित किया जाता है। विभिन्न रिज़ॉल्यूशन विधियों से मेल खाने वाले सेल्स के विभिन्न स्तर हैं। उच्च स्तर पर प्रत्येक सेल को अगले निचले स्तर में कई छोटे सेल्स में विभाजित किया जाता है। प्रत्येक सेल का सांख्यिकीय डेटा पहले से गणना और संग्रहीत किया जाता है और क्वेरी का उत्तर दे सकता है। उच्च-स्तरीय सेल्स का विनिर्देश निचले-स्तरीय सेल्स के विनिर्देश से सरलता से गणना किया जा सकता है:

काउंट, माध्य, s, न्यूनतम, अधिकतम
वितरण का प्रकार - सामान्य, समान, आदि।

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

ट्री बनाने की प्रक्रिया नीचे दिए गए एल्गोरिदम में दिखाई गई है। स्पेस में प्रत्येक सेल ट्री में एक नोड से मेल खाता है और विशेषता-स्वतंत्र (काउंट) डेटा और विशेषता-निर्भर (माध्य, मानक विचलन, न्यूनतम, अधिकतम वितरण) डेटा दोनों के साथ वर्णित है। चूंकि ट्री में नोड्स की संख्या डेटाबेस में आइटम्स की संख्या से कम है, STING BUILD की जटिलता O(n) है।

एल्गोरिदम

इनपुट

D // पदानुक्रमित संरचना में रखे जाने वाला डेटा
k // निम्नतम स्तर पर वांछित सेल्स की संख्या

आउटपुट

T // ट्री STING BUILD एल्गोरिदम
// ऊपर-नीचे से एक खाली ट्री बनाएं
T = डेटा मानों के साथ आरंभ रूट नोड;
// प्रारंभ में केवल रूट नोड
i = 1;
दोहराएं
  लेवल i में प्रत्येक नोड के लिए
    4 चाइल्ड नोड्स बनाएं प्रारंभिक मानों के साथ;
  i = i + 1;
जब तक 4^i = k;
// नीचे-ऊपर से ट्री भरें
D में प्रत्येक आइटम के लिए
  आइटम की स्थिति से संबंधित लीफ नोड j निर्धारित करें;
  आइटम में विशेषता मानों के आधार पर j के मान अपडेट करें;
  i := log₄(k);
  दोहराएं
    i := i - 1;
    लेवल i में प्रत्येक नोड j के लिए
      इसके 4 बच्चों में विशेषता मानों के आधार पर j के मान अपडेट करें;
  जब तक i = 1;