อัลกอริทึม Grid-Based Clustering
Grid (กริด) เป็นวิธีมีประสิทธิภาพจัดระเบียบชุดข้อมูล โดยเฉพาะในมิติต่ำ แนวคิดคือแบ่งค่าที่เป็นไปได้ของแต่ละแอตทริบิวต์เป็นช่วงติดต่อกันหลายช่วง สร้างชุดของ grid cells ทุกวัตถุจะตกอยู่ใน grid cell ที่ช่วงแอตทริบิวต์ตรงกับค่าของวัตถุ
วัตถุสามารถกำหนดให้ grid cells ได้ในหนึ่งผ่านของเรคคอร์ด และข้อมูลเกี่ยวกับแต่ละ cell รวมถึงจำนวนจุดใน cell ก็สามารถรวบรวมพร้อมกันได้
มีหลายวิธีทำ clustering ด้วย grid แต่วิธีส่วนใหญ่อิงตามความหนาแน่น (density-based) อัลกอริทึม grid-based clustering ดังนี้:
- กำหนดชุดของ grid cells
- กำหนดวัตถุให้ cells ที่เหมาะสม และคำนวณ density ของแต่ละ cell
- กำจัด cells ที่มี density ต่ำกว่า threshold r ที่กำหนด
- สร้าง clusters จาก contiguous set ของ dense cells
การกำหนด Grid Cells
เป็นขั้นตอนพื้นฐาน แต่ก็ unclear ที่สุด เพราะมีหลายวิธีแบ่งค่าที่เป็นไปได้ของแต่ละแอตทริบิวต์เป็นช่วงติดต่อกัน สำหรับ continuous attributes วิธีหนึ่งคือแบ่งเป็น equal-width intervals ถ้าใช้วิธีนี้กับทุกแอตทริบิวต์ grid cells ทุกอันจะมี volume เท่ากัน และ density ของ cell นิยามง่ายว่าเป็นจำนวนจุดใน cell
Density of Grid Cells (ความหนาแน่นของ Grid Cells)
นิยาม density ของ grid cell = จำนวนจุด / ปริมาตรของพื้นที่ กล่าวคือ จำนวนจุดต่อหน่วยพื้นที่ ไม่ว่ามิติของพื้นที่จะเป็นเท่าไร
Forming Clusters from Dense Grid Cells (สร้าง Clusters จาก Dense Grid Cells)
สร้าง clusters จาก adjacent dense cells ค่อนข้างง่าย มีปัญหาบางอย่าง เช่น ต้องนิยามว่า adjacent cells คืออะไร วิธี clustering มีข้อเสียบางอย่าง ที่แก้ได้โดยทำให้อัลกอริทึมซับซ้อนขึ้นเล็กน้อย ตัวอย่าง: มี partly empty cells บนขอบเขตของ cluster น่าจะเป็น
สามารถปรับปรุง basic grid-based clustering โดยใช้ข้อมูลมากกว่าแค่ density บางกรณี เรคคอร์ดมีทั้ง spatial และ non-spatial attributes กล่าวคือ มีแอตทริบิวต์บางตัวอธิบายตำแหน่งวัตถุในเวลาหรือพื้นที่ ส่วนอีกบางตัวอธิบายลักษณะอื่นของวัตถุ
ตัวอย่าง: บ้าน มีทั้ง location และ characteristics อื่นๆ เช่น ราคา หรือพื้นที่ใช้สอย ตารางฟุต เนื่องจาก spatial (หรือ temporal) autocorrelation วัตถุใน cell เฉพาะจะมีค่าใกล้เคียงกันสำหรับแอตทริบิวต์อื่นๆ
