อัลกอริธึมการทำคลัสเตอร์แบบรวมกลุ่มคืออะไร?

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

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

วิธีการ K-means ในการทำคลัสเตอร์เริ่มต้นด้วยจำนวนคลัสเตอร์คงที่และจัดสรรข้อมูลทั้งหมดลงในหลายคลัสเตอร์นั้น แนวทางอีกประเภทหนึ่งดำเนินการโดยการรวมกลุ่ม วิธีการเหล่านี้เริ่มต้นด้วยจุดข้อมูลทุกจุดที่สร้างคลัสเตอร์ของตัวเอง และค่อยๆ รวมเข้าเป็นกลุ่มที่สูงขึ้นและสูงขึ้นเรื่อยๆ จนกว่าจะรวมจุดทั้งหมดไว้ในคลัสเตอร์ขนาดใหญ่กลุ่มเดียว

กระบวนการแรกคือการสร้างเมทริกซ์ความคล้ายคลึงกัน เมทริกซ์ความคล้ายคลึงกันคือตารางของระยะทางที่ฉลาดเป็นคู่หรือระดับความคล้ายคลึงกันระหว่างกระจุก ในขั้นต้น เมทริกซ์ความคล้ายคลึงกันจะรวมระยะห่างแบบคู่ระหว่างระเบียนคู่เดียว

เร็กคอร์ดมีความคล้ายคลึงกันหลายอย่าง เช่น ระยะทางแบบยุคลิด มุมระหว่างเวกเตอร์ และอัตราส่วนของการเชื่อมต่อกับฟิลด์หมวดหมู่ที่ไม่สัมพันธ์กัน

อาจดูเหมือนว่าด้วยคลัสเตอร์ดั้งเดิม N จุดสำหรับจุดข้อมูล N การคำนวณการวัด N2 จำเป็นต่อการสร้างตารางระยะทาง หากการวัดความคล้ายคลึงกันเป็นเมตริกระยะทางจริง ต้องใช้เพียงครึ่งเดียวเท่านั้นเนื่องจากเมตริกระยะทางจริงบางตัวปฏิบัติตามวิธีที่ Distance(X, Y) =Distance(Y, X)

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

ขณะนี้มีกลุ่ม N – 1 และ N – 1 แถวในเมทริกซ์เดียวกัน สามารถทำซ้ำขั้นตอนการผสาน N – 1 ครั้ง ดังนั้นข้อมูลบางส่วนจึงอยู่ในคลัสเตอร์ขนาดใหญ่ที่เท่ากัน การทำซ้ำแต่ละครั้งจะรับรู้ว่าคลัสเตอร์ใดรวมกันและระยะห่างระหว่างกัน ข้อมูลนี้สามารถกำหนดวิธีการจัดกลุ่มที่จะใช้ได้