STING Grid-based Clustering คืออะไร?

STING: Statistical Information Grid Approach

Grid-based clustering methods ใช้ multi-resolution grid data structure Quantize object space เป็น finite number of cells สร้าง grid structure ที่ operations ทั้งหมดสำหรับ clustering ทำงานบนมัน ข้อดี: quick processing time โดยทั่วไป independent ของจำนวน data objects ขึ้นอยู่แค่จำนวน cells ในแต่ละมิติใน quantized space

Grid-based clustering ใช้ multi-resolution grid data structure และใช้ dense grid cells สร้าง clusters มี interesting methods: STING, wave cluster, CLIQUE

STING (Statistical Information Grid)

Spatial area แบ่งเป็น rectangular cells มี various levels of cells corresponding to different resolutions แต่ละ cell ที่ high level แบ่งเป็น multiple smaller cells ใน next lower level Statistical data ของแต่ละ cell คำนวณและเก็บไว้ล่วงหน้า และตอบ queries Specification ของ higher-level cells คำนวณได้ง่ายจาก lower-level cells:

• count, mean, s, min, max
• type of distribution: normal, uniform, เป็นต้น

STING ใช้ hierarchical approach แบ่ง spatial area เป็น rectangular cells คล้าย quadtree Spatial database สแกนครั้งเดียว statistical parameters กำหนดสำหรับแต่ละ cell STING technique มองเป็น hierarchical approach ขั้นแรก: สร้าง hierarchical representation Tree ที่สร้างขึ้นแบ่ง area เป็น quadrants แยกกัน

กระบวนการสร้าง tree แสดงใน algorithm ด้านล่าง แต่ละ cell ใน space สอดคล้องกับ node ใน tree และอธิบายด้วย attribute-independent (count) data และ attribute-dependent (mean, standard deviation, minimum, maximum, distribution) data เนื่องจากจำนวน nodes ใน tree น้อยกว่าจำนวน items ใน database complexity ของ STING BUILD คือ O(n)

Algorithm: STING BUILD

Input: D (data to be placed in hierarchical structure), k (number of desired cells at lowest level)

Output: 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 4^i = k;
// Populate tree from bottom-up
for each item in D do
  determine leaf node j related to 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;