STING গ্রিড-ভিত্তিক ক্লাস্টারিং কি?

গ্রিড-ভিত্তিক ক্লাস্টারিং পদ্ধতিগুলি একটি মাল্টি-রেজোলিউশন গ্রিড ডেটা কাঠামো ব্যবহার করে। এটি বস্তুর ক্ষেত্রগুলিকে একটি সীমিত সংখ্যক কোষে পরিমাপ করে যা একটি গ্রিড কাঠামো তৈরি করে যার উপর ক্লাস্টারিংয়ের জন্য সমস্ত ক্রিয়াকলাপ বাস্তবায়িত হয়। পদ্ধতির সুবিধা হল এর দ্রুত প্রক্রিয়াকরণের সময়, যা সাধারণত ডেটা অবজেক্টের সংখ্যা থেকে স্বাধীন, এখনও পরিমাপকৃত স্থানের প্রতিটি মাত্রার একাধিক কোষের উপর নির্ভর করে।

গ্রিড-ভিত্তিক ক্লাস্টারিং একটি মাল্টি-রেজোলিউশন গ্রিড ডেটা স্ট্রাকচার ব্যবহার করে এবং ক্লাস্টার তৈরি করতে ঘন গ্রিড কোষ ব্যবহার করে। STING, ওয়েভ ক্লাস্টার এবং CLIQUE বেশ কয়েকটি আকর্ষণীয় পদ্ধতি রয়েছে।

স্টিং - একটি পরিসংখ্যানগত তথ্য গ্রিড পদ্ধতি। স্থানিক এলাকাটি আয়তক্ষেত্রাকার কোষে বিভক্ত। রেজোলিউশনের বিভিন্ন পদ্ধতির সাথে সংশ্লিষ্ট কোষের বিভিন্ন স্তর রয়েছে। উচ্চ স্তরের প্রতিটি কোষ পরবর্তী নিম্ন স্তরে একাধিক ছোট কোষে বিভক্ত হয়। প্রতিটি কক্ষের পরিসংখ্যানগত ডেটা গণনা করা হয় এবং আগে থেকে সংরক্ষণ করা হয় এবং প্রশ্নের উত্তর দিতে পারে। উচ্চ-স্তরের কোষগুলির স্পেসিফিকেশন নিম্ন-স্তরের কোষগুলির স্পেসিফিকেশন থেকে সহজভাবে গণনা করা যেতে পারে:

• গণনা, গড়, s, মিন, সর্বোচ্চ
• বন্টনের প্রকার-স্বাভাবিক, ইউনিফর্ম, ইত্যাদি।

পরিসংখ্যানগত তথ্য গ্রিড-ভিত্তিক পদ্ধতি (STING) একটি চতুষ্কোণ গাছের মতো আয়তক্ষেত্রাকার কোষগুলিতে স্থানিক এলাকাকে ভাগ করার জন্য একটি শ্রেণিবদ্ধ পদ্ধতি অনুসরণ করে। স্থানিক ডাটাবেস একবার স্ক্যান করা হয় এবং প্রতিটি কক্ষের জন্য পরিসংখ্যানগত পরামিতি নির্ধারণ করা হয়। 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;