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

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

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

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

• गिनती, माध्य, s, न्यूनतम, अधिकतम
• वितरण का प्रकार-सामान्य, वर्दी, आदि।

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

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

एल्गोरिदम

इनपुट

D // Data to be placed in the hierarchical structure
k // Number of desired cells at the lowest level

आउटपुट

T // Tree
STING BUILD algorithm
// Create an empty tree from top-down
   T = root node with data values initialized; // Initially only root node
   i = 1;
   repeat
      for each node in level i do
      create 4 children nodes with initial values;
   i = i +1;
   until 4i = k;
   // Populate tree from bottom-up for each item in D do
   determine leaf node j related to the position of D;
   update values of j based on attribute values in item;
   i := log4(k);
   repeat
   i: = i - 1;
   for each node j in level i do
update values of j based on attribute values in its 4 children;
until i = 1;