ความหมายของ DBSCAN
DBSCAN ย่อมาจาก Density-Based Spatial Clustering of Applications with Noise (การจัดกลุ่มเชิงพื้นที่แบบอิงความหนาแน่นของแอปพลิเคชันพร้อม Noise) เป็นอัลกอริทึมการจัดกลุ่มแบบอิงความหนาแน่น (density based clustering algorithm) อัลกอริทึมขยายพื้นที่ (grows regions) ที่มีความหนาแน่นพอสมควร (sufficiently high density) เข้าสู่คลัสเตอร์ และค้นพบคลัสเตอร์ที่มีสถาปัตยกรรมสุ่ม (arbitrary architecture) ในฐานข้อมูลเชิงพื้นที่ที่มี noise มันแทนคลัสเตอร์เป็นกลุ่มสูงสุด (maximal group) ของจุดที่เชื่อมต่อโดยความหนาแน่น (density-connected points)
นิยามพื้นฐานของ Density-based Clustering
บริเวณเคียงภายในรัศมี ε ของวัตถุที่กำหนด เรียกว่า ε-neighborhood ของวัตถุนั้น
หาก ε-neighborhood ของวัตถุรวมวัตถุอย่างน้อยจำนวนขั้นต่ำ MinPts วัตถุนั้นเรียกว่า core object (วัตถุแกน)
ให้เซตของวัตถุ D สามารถกล่าวได้ว่า วัตถุ p เป็น directly density-reachable (เข้าถึงได้โดยตรงผ่านความหนาแน่น) จากวัตถุ q หาก p อยู่ภายใน ε-neighborhood ของ q และ q เป็น core object
วัตถุ p เป็น density-reachable (เข้าถึงได้ผ่านความหนาแน่น) จากวัตถุ q เกี่ยวกับ ε และ MinPts ในกลุ่มวัตถุ D หากมีโซ่วัตถุ p1,..., pn ที่ p1 = q และ pn = p รวมถึง pi+1 เป็น directly density-reachable จาก pi เกี่ยวกับ ε และ MinPts สำหรับ 1 ≤ i ≤ n, pi ∈ D
วัตถุ p เป็น density-connected (เชื่อมต่อผ่านความหนาแน่น) กับวัตถุ q เกี่ยวกับ ε และ MinPts ในกลุ่มวัตถุ D หากมีวัตถุ o ∈ D ที่ทำให้ p และ q ทั้งคู่เป็น density-reachable จาก o เกี่ยวกับ ε และ MinPts
Density reachability เป็น transitive closure ของ direct density reachability และความสัมพันธ์นี้เป็น asymmetric (ไม่สมมาตร) มีเพียง core objects เท่านั้นที่เป็น mutually density reachable (เข้าถึงได้ผ่านความหนาแน่นร่วมกัน) Density connectivity เป็น symmetric relation (ความสัมพันธ์สมมาตร)
Density-based cluster (คลัสเตอร์แบบอิงความหนาแน่น) คือ กลุ่มของวัตถุ density-connected ที่เป็น maximal เกี่ยวกับ density-reachability วัตถุแต่ละตัวที่ไม่รวมในคลัสเตอร์ใดๆ ถูกมองว่าเป็น noise
การทำงานของ DBSCAN
DBSCAN ค้นหาคลัสเตอร์โดยการทดสอบ ε-neighborhood ของทุกจุดในฐานข้อมูล หาก ε-neighborhood ของจุด p รวมถึง MinPts มากกว่า คลัสเตอร์ใหม่กับ p เป็น core object จะถูกสร้าง DBSCAN รวบรวมวัตถุ directly density-reachable จาก core objects เหล่านี้ซ้ำๆ ซึ่งอาจรวมการรวม (merge) ของคลัสเตอร์ density-reachable หลายๆ ตัว กระบวนการสิ้นสุดเมื่อไม่มีจุดใหม่ที่สามารถเพิ่มเข้าไปในคลัสเตอร์ใดๆ ได้
หากใช้ spatial index ความซับซ้อนทางคอมพิวตะของ DBSCAN คือ O(n log n) โดยที่ n คือจำนวนวัตถุฐานข้อมูล ดังนั้นเป็น O(n2) ด้วยการตั้งค่าพารามิเตอร์ที่ผู้ใช้แทน ε และ MinPts ที่เหมาะสม อัลกอริทึมมีประสิทธิภาพในการค้นพบคลัสเตอร์ที่มีรูปร้างตามใจชอบ (arbitrary-shaped clusters)
