แนวทางของ Graph-based Clustering
กระบวนการรวมชุดวัตถุทางกายภาพหรือนามธรรมเป็นชั้นเรียนของวัตถุเดียวกัน เรียกว่า clustering กลุ่มคือชุดวัตถุข้อมูลที่คล้ายกันภายในกลุ่มเดียวกัน และแตกต่างจากวัตถุในกลุ่มอื่น กลุ่มข้อมูลมองรวมเป็นหนึ่งกลุ่มในหลายแอปพลิเคชัน Cluster analysis เป็นกิจกรรมสำคัญของมนุษย์
Clustering ช่วยระบุ outliers ค่าที่คล้ายกันจัดเป็นกลุ่ม ค่าที่อยู่นอกกลุ่มเรียกว่า outliers เทคนิคจัดกลุ่มมอง data tuples เป็น objects แบ่ง objects เป็นกลุ่ม เพื่อ objects ในกลุ่มเดียวกัน "similar" และ objects ในกลุ่มอื่น "dissimilar" มักนิยามในรูปแบบว่า objects "close" กันในพื้นที่ ตาม distance function
แนวทางต่างๆ ของ Graph-based Clustering
- Sparsify proximity graph เก็บเฉพาะ link ของวัตถุกับ nearest neighbors ช่วยจัดการ noise และ outliers และใช้ graph partitioning algorithms ที่มีประสิทธิภาพสำหรับ sparse graphs ได้
- Similarity measure based on shared nearest neighbors นิยาม similarity ระหว่างสองวัตถุจากจำนวน nearest neighbors ที่ร่วมกัน วิธีนี้ขึ้นกับการสังเกตว่า วัตถุและ nearest neighbors มักอยู่ใน class เดียวกัน ช่วยแก้ปัญหา high dimensionality และ clusters ที่ density เปลี่ยนแปลง
- Core objects and growing clusters around them ใน graph-based clustering จำเป็นต้องนำแนวคิด density มาบน proximity graph หรือ sparsified proximity graph คล้าย DBSCAN การสร้างกลุ่มรอบ core objects นำไปสู่แนวทางจัดกลุ่มที่ค้นพบกลุ่มรูปร่างและขนาดต่างกันได้
- ใช้ข้อมูลใน proximity graph เพื่อตัดสินใจรวมกลุ่มอย่างซับซ้อน รวมสองกลุ่มก็ต่อเมื่อ cluster ผลลัพธ์จะมีลักษณะคล้ายกับสองกลุ่มต้นทาง
- เริ่มจาก sparsification of proximity graphs รองรับตัวอย่างสองวิธีที่อิงแนวทางนี้: MST (คล้าย single link clustering) และ Opossum
- Hierarchical clustering algorithm ใช้ self-similarity 決定ว่าควรรวมกลุ่มหรือไม่ นิยาม Shared Nearest Neighbor (SNN) similarity (ขนาด similarity ใหม่) และเรียนรู้ Jarvis-Patrick clustering algorithm ที่ใช้ similarity นี้
