วิธีการแบบลำดับชั้นคืออะไร?

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

การรวมคลัสเตอร์จะขึ้นอยู่กับระยะห่างระหว่างคลัสเตอร์ การวัดระยะห่างระหว่างกระจุกที่ใช้อย่างกว้างๆ มีดังนี้ โดยที่ mi คือค่าเฉลี่ยของคลัสเตอร์ Ci, ni คือจำนวนจุดใน Ci และ |p – p’| คือระยะห่างระหว่างจุดสองจุด p และ p'.

ประเภทของวิธีการจัดกลุ่มตามลำดับชั้น

วิธีการจัดกลุ่มตามลำดับชั้นมีสองประเภทดังต่อไปนี้ -

Agglomerative Hierarchical Clustering (AHC) − AHC เป็นวิธีการทำคลัสเตอร์จากล่างขึ้นบน โดยที่คลัสเตอร์มีคลัสเตอร์ย่อย ซึ่งจะมีคลัสเตอร์ย่อย เป็นต้น โดยเริ่มด้วยการค้นหาแต่ละอ็อบเจ็กต์ในคลัสเตอร์ จากนั้นจึงรวมคลัสเตอร์อะตอมเหล่านี้เป็นกลุ่มที่ใหญ่ขึ้นและใหญ่ขึ้นจนกระทั่งมีอ็อบเจ็กต์ทั้งหมด อยู่ในคลัสเตอร์เดียวหรือจนกว่าจะเป็นไปตามเงื่อนไขการเลิกจ้างที่เฉพาะเจาะจง วิธีการจัดกลุ่มแบบลำดับชั้นส่วนใหญ่จะใช้กับประเภทนี้ มีความชัดเจนเฉพาะในคำจำกัดความของความคล้ายคลึงระหว่างคลัสเตอร์เท่านั้น

ตัวอย่างเช่น วิธีการที่เรียกว่า AGNES (Agglomerative Nesting) ใช้เทคนิค single-link และทำงานดังนี้ พิจารณาว่ามีชุดของวัตถุอยู่ในรูปสี่เหลี่ยมผืนผ้า เดิมที แต่ละอ็อบเจ็กต์จะอยู่ในคลัสเตอร์ของตัวเอง จากนั้นคลัสเตอร์จะรวมกันทีละขั้นตอนตามหลักการบางอย่าง รวมถึงการรวมคลัสเตอร์ที่มีระยะห่างแบบยุคลิดต่ำสุดในบรรดาวัตถุที่อยู่ใกล้ที่สุดในกระจุก

Divisive Hierarchical Clustering (DHC) − DHC เป็นวิธีจากบนลงล่างและมักใช้น้อยกว่า มันทำงานในลักษณะเดียวกันกับการรวมกลุ่มแบบรวมกลุ่มแต่ในทิศทางตรงกันข้าม วิธีนี้เริ่มต้นด้วยคลัสเตอร์เดียวรวมถึงออบเจ็กต์ทั้งหมด จากนั้นจึงแยกคลัสเตอร์ที่เป็นผลลัพธ์ตามลำดับจนกว่าจะเหลือเพียงคลัสเตอร์ของออบเจ็กต์เดียวหรือจนกว่าจะเป็นไปตามเงื่อนไขการสิ้นสุดที่เฉพาะเจาะจง รวมทั้งได้จำนวนคลัสเตอร์ที่ต้องการหรือระยะห่างระหว่างคลัสเตอร์ที่ใกล้ที่สุดสองคลัสเตอร์อยู่เหนือ ระยะเกณฑ์เฉพาะ

วิธีการแบ่งแยกโดยทั่วไปไม่สามารถเข้าถึงได้และไม่ค่อยได้ใช้เนื่องจากความยากลำบากในการสร้างการตัดสินใจที่ถูกต้องในการแบ่งในระดับสูง DIANA (Divisia Analysis) เป็นตัวอย่างหนึ่งของวิธีการจัดกลุ่มแบบลำดับชั้นแบบแบ่งกลุ่ม มันทำงานในลำดับที่ตรงกันข้าม เดิมที อ็อบเจ็กต์ทั้งหมดจะอยู่ในคลัสเตอร์เดียว ดังนั้นคลัสเตอร์จึงถูกแบ่งตามหลักการบางประการ ซึ่งรวมถึงการแยกกระจุกตามระยะทางแบบยุคลิดสูงสุดระหว่างวัตถุที่อยู่ใกล้เคียงที่สุดในกระจุก