K-Mean ที่แบ่งครึ่งคืออะไร?

อัลกอริธึม K-mean แบบแบ่งครึ่งเป็นการพัฒนาอย่างง่ายของอัลกอริทึม K-mean พื้นฐานที่ขึ้นอยู่กับแนวคิดง่ายๆ เช่น การหาคลัสเตอร์ K แยกชุดของบางจุดออกเป็นสองคลัสเตอร์ เลือกคลัสเตอร์ใดคลัสเตอร์หนึ่งเพื่อแยก ฯลฯ จนกว่าจะมีการสร้างคลัสเตอร์ K

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

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

อัลกอริทึมของการแบ่งครึ่ง K-Mean ซึ่งมีดังต่อไปนี้ -

• เริ่มต้นรายการคลัสเตอร์เพื่อรวมคลัสเตอร์ เช่น จุดทั้งหมด

• ซ้ำ

• ลบคลัสเตอร์ออกจากรายการคลัสเตอร์

• {ใช้สองส่วน "ทดลอง" หลายส่วนของคลัสเตอร์ที่เลือก}

• สำหรับ i :1 ถึงจำนวนการทดลองทำ

• แบ่งกลุ่มที่เลือกโดยใช้ค่าเฉลี่ย K พื้นฐาน

• สิ้นสุดสำหรับ

• เลือกสองคลัสเตอร์จากสองส่วนที่มี SSE รวมน้อยที่สุด

• แทรกสองคลัสเตอร์นี้ลงในเอกสารของคลัสเตอร์

• จนกว่าเอกสารของคลัสเตอร์จะมีคลัสเตอร์ K

มีหลายวิธีในการเลือกคลัสเตอร์ที่จะแยก สามารถเลือกคลัสเตอร์สูงสุดในแต่ละขั้นตอน เลือกคลัสเตอร์ที่มี SSE ที่ใหญ่ที่สุด หรือใช้องค์ประกอบตามขนาดและ SSE หลายตัวเลือกส่งผลให้คลัสเตอร์ต่างกัน

มันสามารถชี้แจงคลัสเตอร์ที่ส่งออกได้โดยใช้เซนทรอยด์เป็นเซนทรอยด์ดั้งเดิมสำหรับอัลกอริธึม K-mean พื้นฐาน นี่เป็นสิ่งสำคัญเพราะแม้ว่าอัลกอริธึม K-mean จะปลอดภัยในการค้นหาคลัสเตอร์ที่กำหนดค่าต่ำสุดในพื้นที่ที่เกี่ยวข้องกับ SSE แต่ในการแบ่งครึ่ง K-means นั้นใช้อัลกอริทึม K-means "ในเครื่อง" นั่นคือเพื่อแบ่งกลุ่มเดี่ยว ดังนั้น ชุดสุดท้ายของคลัสเตอร์จึงไม่ได้กำหนดคลัสเตอร์ที่เป็นค่าขั้นต่ำในเครื่องที่เกี่ยวข้องกับ SSE ทั้งหมด

สุดท้าย การบันทึกชุดของการจัดกลุ่มที่สร้างเป็นคลัสเตอร์แบบ K-mean bisects ก็อาจจำเป็นต้องแบ่งค่า K-mean ออกเป็นสองส่วนเพื่อสร้างคลัสเตอร์แบบลำดับชั้น