การทำคลัสเตอร์ DBSCAN: แบ่งมันสำหรับฉัน

ยินดีต้อนรับกลับสู่โลกที่ฉันไม่รู้ว่าทำไมฉันถึงคลั่งไคล้อัลกอริทึมนี้เพราะฉันเข้าใจโดยสัญชาตญาณโดยสัญชาตญาณ ตอนนี้เราใช้เครื่องสร้างเสียงที่ซับซ้อน เรียนรู้อัลกอริทึมและแบ่งออกเป็นขั้นตอนง่ายๆ โดยใช้ภาพประกอบที่สนุกสนาน

วันนี้เราจะจัดการกับอัลกอริธึมการจัดกลุ่มอื่นที่เรียกว่าDBSCAN ( การจัดกลุ่มแอปพลิเคชันเชิงพื้นที่ตามความหนาแน่นด้วยเสียงรบกวน ) เพื่อให้เข้าใจ DBSCAN ได้ดีขึ้น โปรดดูบทความK-MeansและHierarchical clustering ก่อน

ตามชื่อที่แนะนำ DBSCAN ระบุคลัสเตอร์ตามความหนาแน่นของจุด กลุ่มมักจะอยู่ในพื้นที่ที่มีความหนาแน่นสูงและค่าผิดปกติมักจะอยู่ในพื้นที่ที่มีความหนาแน่นต่ำ ข้อได้เปรียบหลัก 3 ประการของการใช้งาน (อ้างอิงจากผู้บุกเบิกอัลกอริทึม นี้ ) คือต้องการความรู้โดเมนขั้นต่ำ สามารถค้นพบคลัสเตอร์ที่มีรูปร่างตามอำเภอใจ และมีประสิทธิภาพสำหรับฐานข้อมูลขนาดใหญ่

ตอนนี้เรามีบทนำแล้ว เรามาเริ่มส่วนที่สนุกกันดีกว่า ทำความเข้าใจจริงๆ ว่าสิ่งนี้ทำงานอย่างไร สมมติว่าข้อมูลดิบของเรามีลักษณะดังนี้:

สิ่งแรกที่ต้องทำคือนับจำนวนจุด ที่ ใกล้เคียงกับแต่ละจุด เรากำหนดความใกล้ชิดนี้โดยการวาดวงกลมที่มีรัศมีหนึ่งรอบ ( eps ) รอบจุดหนึ่ง และจุดอื่น ๆ ที่อยู่ในวงกลมนี้เรียกว่าใกล้กับจุดแรก ตัวอย่างเช่น เริ่มด้วยจุดสีชมพูนี้แล้ววาดวงกลมรอบๆ

เราเห็นว่าจุดนี้ทับซ้อนกันทั้งหมดหรือบางส่วนกับอีก 7 จุด ดังนั้นเราจึงบอกว่าจุดสีชมพูใกล้เคียงกับ 7 จุด

รัศมีของวงกลมเรียกว่าepsเป็นพารามิเตอร์แรกในอัลกอริทึม DSBCAN ที่เราต้องกำหนด เราต้องกำหนดeps ให้ เหมาะสม เพราะหากเราเลือกค่าที่น้อยเกินไป ข้อมูลส่วนใหญ่จะไม่จับกลุ่มกัน ในทางกลับกัน หากเราเลือกค่าที่มากเกินไป คลัสเตอร์จะรวมกันและจุดข้อมูลจำนวนมากจะอยู่ในคลัสเตอร์เดียวกัน โดยทั่วไป แนะนำให้ใช้ค่าeps ที่น้อยกว่า

พิจารณาจุดสีน้ำเงินนี้ เราเห็นว่ามันอยู่ใกล้ 3 จุดเพราะวงกลมที่มีรัศมีepsทับอีก 3 จุด

ในทำนองเดียวกันสำหรับคะแนนที่เหลือทั้งหมด เราจะนับจำนวนคะแนนปิด เมื่อทำเช่นนั้นแล้ว เราต้องตัดสินใจว่าคะแนนใดเป็นคะแนนหลักและคะแนนใดเป็นคะแนนที่ไม่ใช่คะแนนหลัก

นี่คือที่มาของพารามิเตอร์ตัวที่สองของอัลกอริทึม - minPointsเราใช้minPointsเพื่อระบุว่าจุดใดเป็นCore Pointหรือไม่ สมมติว่าเราตั้งค่าminPointsเป็น 4 แล้วเราจะบอกว่า point เป็นCore Pointหากมีอย่างน้อย 4 point ใกล้เคียงกับมัน หากน้อยกว่า 4 จุดใกล้กับจุดใดจุดหนึ่ง จะถือว่าเป็นจุดที่ไม่ใช่แกนหลัก

ตามกฎทั่วไปminPoints ≥จำนวนมิติในชุดข้อมูล + 1 ค่าที่มากขึ้นมักจะดีกว่าสำหรับชุดข้อมูลที่มีสัญญาณรบกวน ค่าขั้นต่ำสำหรับminPointsจะต้องเป็น 3 แต่ยิ่งชุดข้อมูลของเรามีขนาดใหญ่ ค่า minPoints ก็จะยิ่งมากขึ้นเท่านั้น

ตัวอย่างเช่น ตั้งค่าminPointsเป็น 4 จากนั้นเราสามารถพูดได้ว่าจุดสีชมพูคือCore Pointเนื่องจากมีจุดใกล้เคียงอย่างน้อย 4 จุด แต่จุดสีน้ำเงินคือจุดที่ไม่ใช่แกนเนื่องจากมีเพียง 3 จุดที่อยู่ใกล้ .

ในที่สุด เมื่อใช้กระบวนการข้างต้น เราสามารถระบุได้ว่าจุดที่ไฮไลท์ต่อไปนี้คือCore Points...

…และที่เหลือคือคะแนนที่ไม่ใช่คอร์

ตอนนี้ เราสุ่มเลือกCore Pointและกำหนดให้กับคลัสเตอร์แรก ที่นี่ เราสุ่มเลือกจุดและกำหนดให้กับคลัสเตอร์สีน้ำเงิน

ต่อไปCore Pointsที่อยู่ใกล้กับคลัสเตอร์สีน้ำเงิน หมายความว่าจะซ้อนทับวงกลมที่มีรัศมีeps …

…ทั้งหมดถูกเพิ่มเข้าไปในคลัสเตอร์สีน้ำเงิน:

จากนั้นCore Pointsใกล้กับคลัสเตอร์สีน้ำเงินที่กำลังเติบโตจะถูกเพิ่มเข้าไป ด้านล่าง เราเห็นว่า 2 Core Pointsและ 1 Non-Core Pointอยู่ใกล้กับคลัสเตอร์สีน้ำเงิน แต่เราเพิ่ม 2 Core Pointsให้กับคลัสเตอร์เท่านั้น

ในที่สุดCore Points ทั้งหมด ที่อยู่ใกล้กับคลัสเตอร์สีน้ำเงินที่กำลังเติบโตจะถูกเพิ่มเข้าไปและข้อมูลจะมีลักษณะดังนี้:

ต่อไป เราเพิ่มจุดที่ไม่ใช่คอร์ ทั้งหมด ใกล้กับคลัสเตอร์สีน้ำเงินเข้าไป ตัวอย่างเช่น จุดที่ไม่ใช่แกนหลัก 2 จุดเหล่านี้อยู่ใกล้กับคลัสเตอร์สีน้ำเงิน ดังนั้นจึงถูกเพิ่มเข้าไป:

อย่างไรก็ตาม เนื่องจากไม่ใช่Core Points เรา จึงไม่ใช้สิ่งเหล่านี้เพื่อขยายคลัสเตอร์สีน้ำเงินอีกต่อไป นั่นหมายความว่าNon-Core Point อื่นๆ ที่ใกล้กับNon-Core Point 1 จะไม่ถูกเพิ่มในคลัสเตอร์สีน้ำเงิน

ซึ่งแตกต่างจากCore Pointsตรงที่Non-Core Pointsสามารถเข้าร่วมคลัสเตอร์เท่านั้นและไม่สามารถใช้เพื่อขยายเพิ่มเติมได้

หลังจากเพิ่มNon-Core Pointsทั้งหมดแล้ว เราก็สร้างคลัสเตอร์สีน้ำเงินเสร็จแล้วและมีลักษณะดังนี้:

ขณะนี้เนื่องจากไม่มีCore Points ที่เหลือ อยู่ใกล้เคียงกับคลัสเตอร์แรก เราจึงเริ่มกระบวนการสร้างคลัสเตอร์ใหม่ ขั้นแรก เราสุ่มเลือกCore Point (ที่ไม่ได้อยู่ในคลัสเตอร์) และกำหนดให้กับคลัสเตอร์สีเหลือง ที่สองของเรา

จากนั้นเราจะเพิ่มจุดหลัก ทั้งหมด ใกล้กับคลัสเตอร์สีเหลือง และใช้จุดเหล่านั้นเพื่อขยายคลัสเตอร์เพิ่มเติม

จากนั้นเพิ่มจุดที่ไม่ใช่คอร์ที่อยู่ใกล้กับคลัสเตอร์สีเหลืองเข้าไป หลังจากดำเนินการแล้ว ข้อมูลของเราที่มี 2 คลัสเตอร์จะมีลักษณะดังนี้:

เราทำกระบวนการสร้างคลัสเตอร์นี้ซ้ำไปเรื่อยๆ จนกว่าเราจะไม่เหลือCore Points ในกรณีของเรา เนื่องจากCore Pointsทั้งหมดถูกกำหนดให้กับคลัสเตอร์ เราจึงสร้างคลัสเตอร์ใหม่เสร็จแล้ว สุดท้ายคะแนนที่ไม่ใช่แกนหลักที่เหลืออยู่ซึ่งไม่ใกล้เคียงกับคะแนนหลักและไม่ได้เป็นส่วนหนึ่งของคลัสเตอร์ใดๆ จะเรียกว่าค่าผิดปกติ

และเช่นเดียวกับที่เราสร้าง 2 กลุ่มของเรา และพบค่าผิดปกติ และออกมาอีกด้านที่ไม่เสียหาย

อาจมีคนถามว่าทำไม DBSCAN ถึง K-Means หรือการทำคลัสเตอร์แบบลำดับชั้น

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

นั่นคือทั้งหมดสำหรับวันนี้ โปรดอย่าลังเลที่จะติดต่อกับฉันทางLinkedInหรือส่งอีเมลถึงฉันที่[email protected]เพื่อส่งคำถามและคำแนะนำสำหรับอัลกอริทึมอื่น ๆ ที่คุณต้องการให้แสดง!