การจัดกลุ่ม DBSCAN

การจัดกลุ่ม DBSCAN คืออะไร?

DBSCAN จัดกลุ่มจุดที่อยู่ใกล้กันและทำเครื่องหมายจุดในพื้นที่ความหนาแน่นต่ำเป็นค่าผิดปกติ ไม่ต้องกำหนดจำนวนกลุ่มล่วงหน้า

สองพารามิเตอร์: epsilon (eps) — ระยะทางสูงสุดของเพื่อนบ้าน; minSamples — จำนวนจุดขั้นต่ำสำหรับบริเวณหนาแน่น จุดแบ่งเป็น: แกน ขอบ สัญญาณรบกวน

มีประสิทธิภาพสำหรับความหนาแน่นที่หลากหลาย รูปร่างไม่นูน และสัญญาณรบกวนมาก แต่มีข้อจำกัดเมื่อความหนาแน่นของกลุ่มต่างกันมาก

Formula: จุดแกนกลาง: |N_eps(p)| ≥ minSamples จุดขอบ: |N_eps(p)| < minSamples แต่อยู่ภายในระยะ eps จากจุดแกนกลาง สัญญาณรบกวน: ไม่ใช่ทั้งจุดแกนกลางและจุดขอบ N_eps(p) = {q : dist(p,q) ≤ eps}

ตัวอย่างการคำนวณ

จุด: (1,1), (1.1,1.2), (0.9,0.8), (5,5), (5.1,5.2), (4.9,4.8), (10,10) eps=1.0 minSamples=2 กลุ่ม 1: 3 จุด กลุ่ม 2: 3 จุด สัญญาณรบกวน: (10,10)

เมื่อใดควรใช้เครื่องคำนวณนี้

• นักวิทยาศาสตร์ข้อมูลที่ทำการตรวจหาความผิดปกติ ซึ่งต้องระบุค่าผิดปกติอย่างชัดเจนว่าเป็นจุดสัญญาณรบกวนแยกจากคลัสเตอร์
• นักวิเคราะห์เชิงพื้นที่ที่จัดคลัสเตอร์ข้อมูลภูมิศาสตร์ (เช่น จุดอาชญากรรมหนาแน่น ตำแหน่งจัดส่ง) ซึ่งรูปร่างคลัสเตอร์ไม่ปกติและไม่ทราบจำนวนกลุ่มล่วงหน้า
• นักวิจัยที่วิเคราะห์ข้อมูลที่มีสัญญาณรบกวนตามธรรมชาติ ซึ่งการบังคับให้ทุกจุดเข้าคลัสเตอร์ (อย่างที่ K-Means ทำ) จะบิดเบือนการวิเคราะห์
• วิศวกรที่จัดกลุ่มค่าจากเซนเซอร์ซึ่งก่อรูปแบบที่ไม่เป็นทรงกลม (วงแหวน จันทร์เสี้ยว ทรงยาว) ที่ K-Means ตรวจจับไม่ได้

ข้อผิดพลาดที่ควรหลีกเลี่ยง

• ตั้งค่า epsilon ใหญ่เกินไป — จะรวมคลัสเตอร์ที่ต่างกันให้กลายเป็นหนึ่งเดียว; ใช้กราฟ k-distance หาค่า eps ที่เหมาะสมตรงจุดหักของเส้นโค้ง
• ตั้งค่า epsilon เล็กเกินไป — จะจำแนกจุดส่วนใหญ่เป็นสัญญาณรบกวนและพบคลัสเตอร์น้อยหรือไม่พบเลย; หากข้อมูลส่วนใหญ่ถูกระบุเป็นสัญญาณรบกวน eps น่าจะเล็กเกินไป
• ไม่ปรับสเกลฟีเจอร์ก่อนจัดคลัสเตอร์ — DBSCAN ใช้ระยะทางแบบยุคลิด ฟีเจอร์ที่มีสเกลใหญ่กว่าจึงครอบงำการคำนวณระยะทาง; ปรับมาตรฐานฟีเจอร์ทั้งหมดก่อน
• ใช้ DBSCAN เมื่อคลัสเตอร์มีความหนาแน่นต่างกันมาก — ค่า eps เดียวไม่สามารถรองรับทั้งคลัสเตอร์หนาแน่นและเบาบางพร้อมกันได้; พิจารณาใช้ HDBSCAN หรือ OPTICS แทน

วิธีตีความผลลัพธ์

• จุดสัญญาณรบกวน (ที่ระบุเป็นค่าผิดปกติ) คือจุดข้อมูลในบริเวณความหนาแน่นต่ำ — อาจเป็นความผิดปกติจริง ความคลาดเคลื่อนจากการวัด หรือข้อมูลช่วงรอยต่อระหว่างคลัสเตอร์
• จำนวนคลัสเตอร์ถูกกำหนดโดยอัตโนมัติจากข้อมูลและพารามิเตอร์ ไม่ได้ระบุล่วงหน้า — นี่คือข้อได้เปรียบสำคัญเหนือ K-Means
• หากอัลกอริทึมพบเพียงคลัสเตอร์เดียวหรือจำแนกทุกอย่างเป็นสัญญาณรบกวน ให้ลองปรับ eps และ minSamples — พารามิเตอร์ต้องจูนให้เข้ากับโครงสร้างความหนาแน่นของข้อมูลคุณ

มาตรฐานและเอกสารอ้างอิง

• Ester, Kriegel, Sander & Xu (1996), 'A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise', Proc. KDD-96 — บทความ DBSCAN ต้นฉบับ
• Schubert, Sander, Ester, Kriegel & Xu (2017), 'DBSCAN Revisited, Revisited', ACM Transactions on Database Systems — แนวทางสมัยใหม่เรื่องการเลือกพารามิเตอร์และฮิวริสติก k-distance

คำถามที่พบบ่อย

เลือก eps และ minSamples อย่างไร?

minSamples: มักจะ 2×จำนวนมิติ eps: วาดกราฟระยะ k-เพื่อนบ้านใกล้สุด เลือกที่จุด 'เข่า'

เมื่อไหร่ใช้ DBSCAN แทน K-Means?

เมื่อไม่ทราบจำนวนกลุ่ม รูปร่างไม่สม่ำเสมอ หรือมีสัญญาณรบกวนมาก K-Means เร็วกว่าสำหรับกลุ่มทรงกลม