การจัดกลุ่มแบบลำดับชั้น

การจัดกลุ่มแบบลำดับชั้นคืออะไร?

การจัดกลุ่มแบบลำดับชั้นสร้าง dendrogram โดยรวมสองกลุ่มที่ใกล้ที่สุดซ้ำๆ ไม่ต้องกำหนด K ล่วงหน้า สามารถตัดที่ระดับใดก็ได้

วิธีเชื่อมโยง: เดี่ยว (ระยะต่ำสุด โน้มเอียงเป็นโซ่), สมบูรณ์ (สูงสุด กะทัดรัด), เฉลี่ย, Ward (ลดความแปรปรวน สมดุลที่สุด)

ตารางประวัติการรวมบันทึกระยะทางในแต่ละขั้นตอน การกระโดดใหญ่บ่งชี้ขอบเขตกลุ่มตามธรรมชาติ

Formula: การเชื่อมโยงเดี่ยว (Single linkage): d(A,B) = min{d(a,b) : a∈A, b∈B} การเชื่อมโยงสมบูรณ์ (Complete linkage): d(A,B) = max{d(a,b) : a∈A, b∈B} การเชื่อมโยงเฉลี่ย (Average linkage): d(A,B) = (1/|A||B|) ΣΣ d(a,b) Ward: ΔV = (nₐnᵦ)/(nₐ+nᵦ) ‖μₐ − μᵦ‖²

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

จุด: A(0,0), B(1,0), C(4,0), D(5,0) เดี่ยว: ขั้น 1 A+B (ระยะ=1), ขั้น 2 C+D (1), ขั้น 3 {A,B}+{C,D} (3) ตัดที่ระยะ 2 → 2 กลุ่ม

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

• นักวิจัยที่สำรวจกลุ่มตามธรรมชาติในข้อมูลโดยไม่ต้องผูกมัดกับจำนวนคลัสเตอร์ที่ตายตัว — เดนโดรแกรมเผยโครงสร้างในทุกระดับความละเอียด
• นักชีวสารสนเทศที่จัดคลัสเตอร์โปรไฟล์การแสดงออกของยีนหรือลำดับโปรตีนตามมาตรวัดความคล้ายคลึง
• นักวิจัยตลาดที่จัดกลุ่มสินค้าหรือลูกค้าเป็นอนุกรมวิธานที่มีหมวดหมู่ย่อยซ้อนกัน
• นักวิเคราะห์ข้อมูลที่ต้องเปรียบเทียบว่าวิธี linkage ต่าง ๆ ส่งผลต่อองค์ประกอบและโครงสร้างของคลัสเตอร์อย่างไร

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

• ใช้ single linkage กับข้อมูลที่มีสัญญาณรบกวน — single linkage มีแนวโน้มเกิด 'ปรากฏการณ์ลูกโซ่' ที่จุดสัญญาณรบกวนเชื่อมคลัสเตอร์ที่ต่างกันให้รวมกันก่อนเวลาอันควร; ใช้ Ward หรือ Complete สำหรับงานส่วนใหญ่
• ไม่ปรับมาตรฐานฟีเจอร์ — การจัดคลัสเตอร์แบบลำดับชั้นใช้มาตรวัดระยะทางที่ไวต่อสเกล; ตัวแปรที่มีพิสัยกว้างจะครอบงำผล เว้นแต่ฟีเจอร์ทั้งหมดถูกปรับมาตรฐาน
• เลือกจำนวนคลัสเตอร์โดยไม่ดูรูปแบบระยะทางการรวมกลุ่ม — การตัดตามอำเภอใจให้คลัสเตอร์ที่ไร้ความหมาย; ตรวจสอบเดนโดรแกรมหรือประวัติระยะทางการรวมกลุ่มเพื่อหาจุดแบ่งตามธรรมชาติเสมอ
• ใช้การจัดคลัสเตอร์แบบลำดับชั้นกับชุดข้อมูลขนาดใหญ่มากโดยไม่สุ่มตัวอย่างย่อย — ความซับซ้อนหน่วยความจำ O(n2) และเวลา O(n3) ทำให้ใช้ไม่ได้จริงกับชุดข้อมูลที่เกิน ~10,000 จุด; ใช้ K-Means หรือวิธี mini-batch สำหรับข้อมูลขนาดใหญ่

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

• การกระโดดครั้งใหญ่ของระยะทางการรวมกลุ่มในตารางประวัติการรวม บ่งชี้ขอบเขตคลัสเตอร์ตามธรรมชาติ — คลัสเตอร์ที่อยู่ก่อนการกระโดดครั้งใหญ่คือกลุ่มที่มีความหมาย
• หากวิธี Ward และ Complete linkage ให้คลัสเตอร์ที่คล้ายกัน การจัดกลุ่มนั้นทนทาน; หากต่างกันมาก โครงสร้างคลัสเตอร์อาจคลุมเครือ
• คลัสเตอร์ที่มีขนาดต่างกันมาก (เช่น คลัสเตอร์เดียวมี 90% ของจุดทั้งหมด) อาจบ่งชี้ว่าข้อมูลไม่มีกลุ่มตามธรรมชาติที่ชัดเจน ณ ระดับการตัดนั้น — ลองเปลี่ยนจำนวนคลัสเตอร์

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

• Ward, J. H. (1963), 'Hierarchical Grouping to Optimize an Objective Function', Journal of the American Statistical Association — ที่มาของ Ward Linkage แบบความแปรปรวนต่ำสุด
• Lance & Williams (1967), 'A General Theory of Classificatory Sorting Strategies', The Computer Journal — สูตรเวียนเกิดแบบรวมที่ครอบคลุม Single, Complete และ Average Linkage
• Everitt, Landau, Leese & Stahl, Cluster Analysis (Wiley) — ตำรามาตรฐานเรื่องวิธีจัดกลุ่มแบบรวมตัว (agglomerative) และการตีความ dendrogram

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

ควรใช้วิธีเชื่อมโยงใด?

Ward เป็นค่าเริ่มต้นยอดนิยม — กลุ่มกะทัดรัดและสมดุล หลีกเลี่ยงเดี่ยวเพราะผลกระทบโซ่

ตัด dendrogram ตรงไหน?

หาช่องว่างใหญ่ที่สุดในระยะทางการรวม ใช้ความรู้เฉพาะทาง หรือใช้สัมประสิทธิ์ความไม่สม่ำเสมอ