Agglomerative Hierarchical Clustering (การจัดกลุ่มแบบลำดับชั้นแบบรวม - Bottom-up)
Agglomerative Hierarchical clustering เป็นแนวทางจัดกลุ่มแบบ bottom-up ที่กลุ่มมี sub-clusters ซึ่งต่อไปก็มี sub-clusters อีก ต่างเริ่มต้นโดยวางทุกวัตถุในกลุ่มของตัวเอง แล้วรวม atomic clusters เหล่านี้เป็นกลุ่มใหญ่ขึ้นเรื่อยๆ จนกว่าทุกวัตถุจะอยู่ในกลุ่มเดียว หรือจนถึงเงื่อนไขหยุดที่กำหนด หลายวิธี hierarchical clustering ใช้ประเภทนี้ แตกต่างกันเพียงแค่นิยาม similarity ระหว่างกลุ่ม
ตัวอย่าง: AGNES (Agglomerative Nesting)
วิธี AGNES ใช้เทคนิค single-link ทำงานดังนี้: สมมติมีกลุ่มวัตถุวางในสี่เหลี่ยม เริ่มต้นแต่ละวัตถุอยู่ในกลุ่มของตัวเอง แล้วรวมกลุ่มทีละขั้นตอน ตามหลักการรวมกลุ่มที่มีระยะทางยุคลิดน้อยที่สุดระหว่างวัตถุที่ใกล้ที่สุดในกลุ่ม
Hierarchical clustering แสดงผลเป็นแผนภาพต้นไม้เรียกว่า dendrogram แสดงทั้งความสัมพันธ์ cluster-subcluster และลำดับที่กลุ่มถูกรวม (agglomerative view) หรือแยก (divisive view)
อัลกอริทึม Agglomerative Hierarchical Clustering แบบพื้นฐาน
- คำนวณ proximity matrix หากจำเป็น
- repeat
- รวมสองกลุ่มที่ใกล้ที่สุด
- ปรับ proximity matrix ให้สะท้อน proximity ระหว่างกลุ่มใหม่และกลุ่มเดิม
- until มีเพียงหนึ่งกลุ่มเหลืออยู่
Cluster proximity มักนิยามด้วยประเภทกลุ่มเฉพาะ เช่น หลายเทคนิค agglomerative hierarchical clustering เช่น MIN, MAX, Group Average มาจากมุมมองกราฟของกลุ่ม
MIN นิยาม cluster proximity เป็น proximity ระหว่างสองจุดที่ใกล้ที่สุดในกลุ่มต่างกัน หรือในมุมมองกราฟ คือ edge สั้นที่สุดระหว่างสองโหนดใน subset ของโหนดที่ต่างกัน
MAX ใช้ proximity ระหว่างสองจุดที่ไกลที่สุดในกลุ่มต่างกัน เป็น cluster proximity หรือในมุมมองกราฟ คือ edge ยาวที่สุดระหว่างสองโหนดใน subset ที่ต่างกัน
อัลกอริทึม agglomerative hierarchical clustering แบบพื้นฐานต้องการ proximity matrix ต้องการพื้นที่จัดเก็บ ½ m² proximities (สมมติ matrix symmetric) โดย m คือจำนวนจุดข้อมูล พื้นที่สำหรับติดตามกลุ่มสัมพันธ์กับจำนวนกลุ่ม คือ m-1 ไม่นับ singleton clusters ดังนั้น space complexity รวมเป็น O(m²)
การวิเคราะห์ time complexity: O(m²) สำหรับคำนวณ proximity matrix หลังจากนั้นมี m-1 iterations (เพราะเริ่มต้น m clusters และรวมสองกลุ่มต่อ iteration) แต่ละ iteration ใช้เวลา O(m) สำหรับหาค่าเล็กที่สุดและปรับ matrix รวม time complexity = O(m²)
