CURE (Clustering Using Representatives) คืออะไร?

CURE (Clustering Using REpresentatives)

CURE ย่อมาจาก Clustering Using REpresentatives เป็นอัลกอริทึมจัดกลุ่มที่ใช้หลายเทคนิคเพื่อสร้างแนวทางที่จัดการชุดข้อมูลขนาดใหญ่, outliers, และกลุ่มที่มีสถาปัตยกรรม non-spherical และขนาด non-uniform ได้ CURE นิยามกลุ่มโดยใช้ representative points หลายจุดจากกลุ่ม

จุดเหล่านี้จะจับ geometry และ architecture ของกลุ่ม จุด representative แรกเลือกเป็นจุดที่ไกลที่สุดจากศูนย์กลางของกลุ่ม ส่วนจุดที่เหลือเลือกให้อยู่ไกลที่สุดจากจุดที่เลือกไปแล้วทั้งหมด วิธีนี้ทำให้ representative points กระจายตัวได้ดี จำนวนจุดที่เลือกเป็นพารามิเตอร์ แต่พบว่าค่า 10 หรือมากกว่าทำงานได้ดี

หลังเลือก representative points แล้ว จะยุบ (shrink) พวกมันเข้าหาศูนย์กลางด้วยตัวคูณ α นี่ช่วยลดผลกระทบของ outliers ซึ่งโดยนิยามอยู่ไกลจากศูนย์กลาง จึงถูกยุบมากกว่า ตัวอย่าง: representative point ที่ห่างจากศูนย์กลาง 10 หน่วย จะยุบ 3 หน่วย (α=0.7) ส่วนจุดที่ห่าง 1 หน่วย ยุบแค่ 0.3 หน่วย

การกำจัด Outliers ใน CURE

CURE ใช้ประโยชน์จากลักษณะเฉพาะของ hierarchical clustering เพื่อกำจัด outliers ที่สองจุดในกระบวนการจัดกลุ่ม:

1. ขั้นแรก: ถ้ากลุ่มเติบโตช้า อาจหมายถึงประกอบด้วย outliers ส่วนใหญ่ เพราะ outliers อยู่ไกลจากอื่นๆ จะไม่ถูกรวมกับจุดอื่นบ่อย ขั้นนี้มักเกิดเมื่อจำนวนกลุ่มเป็น 1/3 ของจำนวนจุดเริ่มต้น
2. ขั้นที่สอง: เมื่อจำนวนกลุ่มอยู่ในอันดับของ K (จำนวนกลุ่มที่ต้องการ) กลุ่มเล็กๆ จะถูกกำจัด

การเร่งความเร็ว CURE

เนื่องจาก worst-case complexity ของ CURE คือ O(m² log m) จึงไม่สามารถใช้กับชุดข้อมูลขนาดใหญ่ได้โดยตรง CURE ใช้สองวิธีเร่งความเร็ว:

1. 取 random sample แล้วทำ hierarchical clustering บน sample points ตามด้วย final pass ที่กำหนดจุดที่เหลือในชุดข้อมูลให้กับ cluster ที่มี representative point ใกล้ที่สุด
2. ถ้า sample ที่ต้องการใหญ่เกินไป ใช้วิธีที่สอง: partition sample data และจัดกลุ่มจุดในแต่ละ partition แล้วตามด้วย clustering ของ intermediate clusters และ final pass กำหนดทุกจุดให้ cluster