ความหมายของ STING
STING ย่อมาจาก Statistical Information Grid (กริดข้อมูลสถิติ) STING เป็นวิธีการจัดกลุ่มแบบกริด หลายระดับความละเอียด (grid-based multiresolution clustering method) ที่พื้นที่เชิงพื้นที่ (spatial area) ถูกแบ่งเป็นเซลล์สี่เหลี่ยมผืนผ้า (rectangular cells) มีหลายระดับของเซลล์สี่เหลี่ยมผืนผ้าที่สอดคล้องกับหลายระดับความละเอียด (resolution) และเซลล์เหล่านี้สร้างโครงสร้างลำดับชั้น (hierarchical structure) เซลล์แต่ละตัวในระดับสูงถูกแบ่งเพื่อสร้างเซลล์หลายตัวในระดับต่ำกว่าถัดไป
ข้อมูลสถิติในเซลล์กริด
ข้อมูลสถิติเกี่ยวกับแอตทริบิวต์ในแต่ละเซลล์กริด (รวมถึงค่าเฉลี่ย mean, ค่าสูงสุด max, และค่าต่ำสุด min) ถูกคำนวณล่วงหน้า (precomputed) และจัดเก็บ พารามิเตอร์สถิติของเซลล์ระดับสูงสามารถคำนวณได้อย่างง่ายดายจากพารามิเตอร์ของเซลล์ระดับต่ำ
พารามิเตอร์เหล่านี้ประกอบด้วย – พารามิเตอร์อิสระจากแอตทริบิวต์ (attribute-independent parameter) คือ count และพารามิเตอร์ที่ขึ้นอยู่กับแอตทริบิวต์ (attribute-dependent parameters) คือ mean, stdev (standard deviation), min (minimum), max (maximum); และประเภทการกระจาย (distribution type) ที่ค่าแอตทริบิวต์ในเซลล์ปฏิบัติตาม เช่น normal, uniform, exponential, หรือ none (หากการกระจายไม่ทราบ)
เมื่อระเบียนถูกโหลดเข้าฐานข้อมูล พารามิเตอร์ count, mean, stdev, min, และ max ของเซลล์ระดับล่าง (bottom-level cells) ถูกคำนวณโดยตรงจากระเบียน ค่าของการกระจาย (distribution) สามารถกำหนดโดยผู้ใช้หากประเภทการกระจายทราบล่วงหน้า หรือได้จากการทดสอบสมมติฐาน (hypothesis tests) เช่น การทดสอบ χ2
ประเภทการกระจายของเซลล์ระดับสูงสามารถประเมินได้จากส่วนใหญ่ของประเภทการกระจายของเซลล์ระดับต่ำที่เทียบเท่า ร่วมกับขั้นตอนการกรองเกณฑ์ (threshold filtering procedure) หากการกระจายของเซลล์ระดับต่ำขัดแย้งกันและล้มเหลวในการทดสอบเกณฑ์ ประเภทการกระจายของเซลล์ระดับสูงจะถูกตั้งเป็น none
ข้อดีของวิธีการจัดกลุ่มแบบกริด
วิธีการจัดกลุ่มแบบกริดใช้โครงสร้างข้อมูลกริดหลายระดับความละเอียด (multi-resolution grid data structure) มันทำให้พื้นที่วัตถุ (object space) เป็นควอนตัม (quantizes) เป็นเซลล์จำนวนมากที่สร้างโครงสร้างกริดที่บางดำเนินการสำหรับการจัดกลุ่มถูกนำไปใช้ ข้อดีของวิธีนี้คือเวลาประมวลผลรวดเร็ว (quick processing time) ซึ่งโดยทั่วไปเป็นอิสระจากจำนวนวัตถุข้อมูล (data objects) ยังคงขึ้นอยู่กับเพียงจำนวนเซลล์ในแต่ละมิติในพื้นที่ที่ถูกควอนตัม
ตัวอย่างของแนวทางแบบกริด รวมถึง STING (สำรวจข้อมูลสถิติที่จัดเก็บในเซลล์กริด), WaveCluster (จัดกลุ่มวัตถุโดยใช้วิธีการแปลงเวฟเลต wavelet transform approach), และ CLIQUE (นิยามวิธีแบบกริดและความหนาแน่น grid-and density-based method สำหรับการจัดกลุ่มในพื้นที่ข้อมูลมิติสูง)
ข้อได้เปรียบของ STING
เป็นแนวทางอิสระจากคิวรี่ (query-independent approach) เนื่องจากข้อมูลสถิติมีอยู่โดยอิสระจากคิวรี่
เป็นคำอธิบายทั่วไปของข้อมูลในแต่ละเซลล์กริด ซึ่งสามารถใช้ช่วยตอบคิวรี่จำนวนมากได้
ประสิทธิภาพทางคอมพิวตะเป็นข้อได้เปรียบหลัก STING ผ่านฐานข้อมูลเพราะคำนวณพารามิเตอร์ตัวเลขของเซลล์ ดังนั้น ความซับซ้อนของเวลาในการสร้างคลัสเตอร์คือ O(n) โดย n คือจำนวนวัตถุทั้งหมด
หลังจากสร้างโครงสร้างลำดับชั้นแล้ว เวลาประมวลผลคิวรี่คือ O(g) โดย g คือจำนวนเซลล์กริดทั้งหมดที่ระดับต่ำสุด ซึ่งโดยทั่วไปน้อยกว่า n
เนื่องจาก STING ต้องการแนวทางหลายระดับความละเอียดสำหรับการวิเคราะห์การจัดกลุ่ม คุณภาพของ STING clustering ขึ้นอยู่กับรายละเอียด (granularity) ของระดับต่ำสุดของโครงสร้างกริด หากรายละเอียดละเอียดมาก ค่าของการประมวลผลจะเพิ่มขึ้นอย่างมาก อย่างไรก็ตาม หากระดับล่างของโครงสร้างกริดรุนแรงเกินไป (too coarse) อาจลดคุณภาพของการวิเคราะห์การจัดกลุ่ม
STING ไม่จัดการความสัมพันธ์เชิงพื้นที่ระหว่างลูกและเซลล์เพื่อนบ้านของพวกเขาสำหรับการพัฒนาเซลล์ผู้ปกครอง (parent cell) ผลคือ รูปร่างของคลัสเตอร์ที่ได้เป็น isothetic คือ ขอบเขตคลัสเตอร์บางส่วนเป็นแนวนอนหรือแนวตั้ง และไม่พบขอบเขตแนวทแยง (diagonal boundary) สิ่งนี้อาจลดคุณภาพและความแม่นยำของคลัสเตอร์ 儘管เวลาประมวลผลของเทคนิคเร็ว
