DBSCAN ย่อมาจาก Density-Based Spatial Clustering of Applications with Noise เป็นอัลกอริทึมการจัดกลุ่มตามความหนาแน่น อัลกอริธึมจะเพิ่มพื้นที่ที่มีความหนาแน่นสูงเพียงพอในคลัสเตอร์ และค้นหาคลัสเตอร์ของสถาปัตยกรรมตามอำเภอใจในฐานข้อมูลเชิงพื้นที่ที่มีสัญญาณรบกวน แสดงถึงคลัสเตอร์เป็นกลุ่มสูงสุดของจุดที่เชื่อมต่อกันหนาแน่น
แนวคิดของการจัดกลุ่มตามความหนาแน่นประกอบด้วยคำจำกัดความใหม่จำนวนหนึ่ง ดังนี้ -
-
บริเวณใกล้เคียงภายในรัศมี ε ของวัตถุที่กำหนดเรียกว่า ε บริเวณใกล้เคียงของวัตถุ
-
หาก ε-บริเวณใกล้เคียงของวัตถุมีจำนวนอย่างน้อย MinPts ของวัตถุ วัตถุนั้นจะเรียกว่าวัตถุหลัก
-
จากชุดของวัตถุ D สามารถพูดได้ว่าวัตถุ p สามารถเข้าถึงความหนาแน่นได้โดยตรงจากวัตถุ q ถ้า p อยู่ภายใน ε-neighborhood ของ q และ q เป็นวัตถุหลัก
-
วัตถุ p สามารถเข้าถึงได้จากวัตถุ q ที่เกี่ยวข้องกับ ε และ MinPts ในกลุ่มของวัตถุ D หากมีห่วงโซ่ของวัตถุ p1 ,..., pn โดยที่ p1 =q และ pn =p รวมทั้ง pi +1 เข้าถึงความหนาแน่นได้โดยตรงจาก pi เกี่ยวกับ ε และ MinPts สำหรับ 1 ≤ i ≤ n, pi ε D.
-
วัตถุ p เชื่อมโยงกับความหนาแน่นกับวัตถุ q ที่เกี่ยวข้องกับ ε และ MinPts ในกลุ่มของวัตถุ D หากมีวัตถุ o ε D ที่ทั้ง p และ q สามารถเข้าถึงความหนาแน่นได้จาก o เกี่ยวกับ ε และ MinPts
ความสามารถในการเข้าถึงความหนาแน่นคือการปิดสกรรมกริยาของความสามารถในการเข้าถึงความหนาแน่นโดยตรง และการเชื่อมต่อนี้ไม่สมมาตร มีเพียงวัตถุหลักเท่านั้นที่เข้าถึงความหนาแน่นร่วมกันได้ การเชื่อมต่อความหนาแน่นเป็นความสัมพันธ์ที่สมมาตร
คลัสเตอร์แบบอิงความหนาแน่นคือกลุ่มของออบเจ็กต์ที่เชื่อมต่อกับความหนาแน่นซึ่งมีระดับสูงสุดเกี่ยวกับความสามารถในการเข้าถึงความหนาแน่น แต่ละอ็อบเจ็กต์ที่ไม่รวมอยู่ในคลัสเตอร์ใด ๆ จะถือว่าเป็นสัญญาณรบกวน
DBSCAN ค้นหาคลัสเตอร์โดยการทดสอบ ε-neighborhood ของทุกจุดในฐานข้อมูล หาก ε-บริเวณใกล้เคียงของจุด p มีมากกว่า MinPts คลัสเตอร์ใหม่ที่มี p เป็นออบเจ็กต์หลักจะถูกสร้างขึ้น DBSCAN จะรวบรวมออบเจ็กต์ที่เข้าถึงความหนาแน่นได้โดยตรงจากออบเจ็กต์หลักเหล่านี้ซ้ำๆ กัน ซึ่งสามารถมีการรวมกลุ่มของคลัสเตอร์ที่เข้าถึงความหนาแน่นได้สองสามตัว กระบวนการนี้จะลบเมื่อไม่สามารถแทรกจุดใหม่ลงในคลัสเตอร์ใดๆ ได้
หากใช้ดัชนีเชิงพื้นที่ ความซับซ้อนในการคำนวณของ DBSCAN คือ O(nlogn) โดยที่ n คือจำนวนอ็อบเจ็กต์ฐานข้อมูล ดังนั้นจึงเป็น O (n 2 ). ด้วยการตั้งค่าที่เหมาะสมของพารามิเตอร์ที่ผู้ใช้เป็นตัวแทน ε และ MinPts อัลกอริทึมจะมีประสิทธิภาพในการค้นหาคลัสเตอร์ที่มีรูปร่างตามอำเภอใจ
