การทำคลัสเตอร์แบบลำดับชั้นแบบ Agglomerative เป็นวิธีการทำคลัสเตอร์จากล่างขึ้นบน โดยที่คลัสเตอร์มีคลัสเตอร์ย่อย ซึ่งมีคลัสเตอร์ย่อยตามลำดับ เป็นต้น โดยเริ่มด้วยการค้นหาทุกอ็อบเจ็กต์ในคลัสเตอร์ จากนั้นจึงรวมคลัสเตอร์อะตอมเหล่านี้เป็นคลัสเตอร์ที่สูงขึ้นและสูงขึ้นจนมีบางอ็อบเจ็กต์ ในคลัสเตอร์เดียวหรือจนกว่าจะต้องมีเงื่อนไขการยกเลิกที่แน่นอน วิธีการจัดกลุ่มแบบลำดับชั้นหลายวิธีใช้กับประเภทนี้ มีความชัดเจนเฉพาะในคำอธิบายของความคล้ายคลึงระหว่างคลัสเตอร์เท่านั้น
ตัวอย่างเช่น วิธีการที่เรียกว่า AGNES (Agglomerative Nesting) ต้องการเทคนิคแบบลิงก์เดียวและดำเนินการดังนี้ พิจารณาว่ามีกลุ่มของวัตถุวางอยู่ในรูปสี่เหลี่ยมผืนผ้า ในขั้นต้น แต่ละอ็อบเจ็กต์จะอยู่ในคลัสเตอร์ของตัวเอง ดังนั้นคลัสเตอร์จะถูกรวมทีละขั้นตอนตามหลักการบางอย่างที่เกี่ยวข้องกับการรวมคลัสเตอร์ที่มีระยะห่างแบบยุคลิดขั้นต่ำระหว่างวัตถุที่ใกล้ที่สุดในคลัสเตอร์
การจัดกลุ่มตามลำดับชั้นจะแสดงแบบกราฟิกโดยใช้ไดอะแกรมคล้ายต้นไม้ที่เรียกว่า dendrogram ซึ่งแสดงทั้งการเชื่อมโยงคลัสเตอร์และคลัสเตอร์ย่อยและลำดับที่คลัสเตอร์รวมกัน (มุมมองการรวมกลุ่ม) หรือการแยก (มุมมองที่แตกแยก)
อัลกอริธึมการจัดกลุ่มแบบลำดับชั้นพื้นฐาน
-
คำนวณเมทริกซ์ความใกล้เคียง หากจำเป็น
-
ซ้ำ
-
รวมสองคลัสเตอร์ที่ใกล้เคียงที่สุดเข้าด้วยกัน
-
รีเฟรชเมทริกซ์ความใกล้เคียงเพื่อสะท้อนถึงความใกล้ชิดระหว่างคลัสเตอร์ใหม่และคลัสเตอร์เริ่มต้น
-
จนกว่าจะเหลือเพียงคลัสเตอร์เดียว
โดยทั่วไปแล้วความใกล้ชิดของคลัสเตอร์ถูกกำหนดด้วยประเภทของคลัสเตอร์เฉพาะ ตัวอย่างเช่น เทคนิคการจัดกลุ่มแบบลำดับชั้นแบบรวมกลุ่มหลายแบบ รวมถึง MIN, MAX และ Group Average มาจากมุมมองของคลัสเตอร์แบบกราฟ
MIN กำหนดความใกล้ชิดของคลัสเตอร์ว่าใกล้เคียงระหว่างจุดสองจุดที่ปิดซึ่งอยู่ในหลายคลัสเตอร์ หรือโดยใช้วิธีกราฟ ซึ่งเป็นขอบที่สั้นที่สุดในบรรดา 2 โหนดในชุดย่อยต่างๆ ของโหนด
หรืออีกทางหนึ่ง MAX จะใช้ความใกล้ชิดระหว่างจุดที่ไกลที่สุด 2 จุดที่ไกลที่สุดในหลายคลัสเตอร์เพื่อให้เป็นความใกล้ชิดของคลัสเตอร์หรือใช้วิธีกราฟ ซึ่งเป็นขอบสูงสุดระหว่างสองโหนดในชุดย่อยที่แตกต่างกันของโหนด
แนวคิดอัลกอริธึมการจัดกลุ่มแบบลำดับชั้นเชิงแนวคิดที่นำเสนอต้องมีเมทริกซ์ความใกล้เคียง สิ่งนี้จำเป็นต้องมีคลังเก็บของ $\mathrm{\frac{1}{2}m^2}$ proximities (เมื่อพิจารณาว่าเมทริกซ์ความใกล้เคียงมีความสมมาตร) โดยที่ m คือจุดข้อมูลหลายจุด พื้นที่ที่จำเป็นในการดูแลติดตามคลัสเตอร์เป็นสัดส่วนกับหลายคลัสเตอร์ ซึ่งเท่ากับ m-1 ไม่รวมคลัสเตอร์ซิงเกิลตัน ดังนั้น ความซับซ้อนของพื้นที่ทั้งหมดคือ $\mathrm{O(m^2)}$.
การวิเคราะห์อัลกอริธึมการจัดกลุ่มแบบลำดับชั้นแบบ agglomerative พื้นฐานนั้นง่ายเช่นกันเกี่ยวกับความซับซ้อนในการคำนวณ $\mathrm{O(m^2)}$ ต้องใช้เวลาในการคำนวณเมทริกซ์ความใกล้เคียง หลังจากขั้นตอนนั้น มีการวนซ้ำ m - 1 ที่มีขั้นตอนที่ 3 และ 4 เนื่องจากมีคลัสเตอร์ m อยู่ที่จุดเริ่มต้น และคลัสเตอร์สองคลัสเตอร์จะรวมกันระหว่างการวนซ้ำทุกครั้ง
