Bisecting K-Means Algorithm
Bisecting K-means algorithm เป็นการขยายง่ายๆ ของ K-means พื้นฐาน ขึ้นอยู่กับแนวคิดง่ายๆ: เพื่อได้ K clusters ให้แบ่งชุดจุดทั้งหมดเป็นสองกลุ่ม เลือกหนึ่งในสองกลุ่มมาแบ่งต่อ ไปเรื่อยๆ จนได้ K clusters
K-means algorithm รับพารามิเตอร์นำเข้า k และแบ่งชุด n objects เป็น k clusters ให้ intracluster similarity สูง แต่ intercluster similarity ต่ำ ความคล้ายคลึงของกลุ่มวัดจากค่าเฉลี่ยของวัตถุในกลุ่ม ซึ่งมองเป็น centroid หรือ center of gravity
ค่าเริ่มต้นสำหรับ means ถูกกำหนดแบบ arbitrary สุ่มหรืออาจใช้ค่าจาก k รายการแรก เกณฑ์การ收敛 (convergence) อาจอิง squared error แต่ไม่จำเป็น ตัวอย่างอัลกอริทึมกำหนดให้ clusters ต่างกัน วิธีหยุดอื่นๆ กำหนดจำนวน iterations คงที่ สูงสุด iterations อาจกำหนดเพื่อให้หยุดแม้ไม่收敛
อัลกอริทึม Bisecting K-Means
- Initialize list of clusters ให้มี cluster เดียวที่มีทุกจุด
- repeat
- Remove a cluster จาก list of clusters
- {ทำ "trial" bisections หลายครั้งของ cluster ที่เลือก}
- for i = 1 to number of trials do
- Bisect the chosen cluster โดยใช้ basic K-means
- end for
- เลือกสองกลุ่มจาก bisection ที่มี total SSE น้อยที่สุด
- Insert สองกลุ่มนี้เข้า list of clusters
- until list of clusters มี K clusters
มีหลายวิธีเลือก cluster ที่จะแบ่ง: เลือก cluster ใหญ่สุด, เลือกที่มี SSE ใหญ่สุด, หรือใช้เกณฑ์ผสมระหว่างขนาดและ SSE การเลือกต่างกันให้ clusters ต่างกัน
สามารถปรับปรุง clusters ที่ได้โดยใช้ centroids ของพวกเขาเป็น centroid เริ่มต้นสำหรับ basic K-means นี่สำคัญ เพราะแม้ K-means รับประกันหา clustering ที่เป็น local minimum ว่าด้วย SSE แต่ใน bisecting K-means ใช้ K-means "ท้องถิ่น" เพื่อแบ่ง single clusters ชุดกลุ่มสุดท้ายจึงไม่เป็น clustering ที่เป็น local minimum ว่าด้วย total SSE
สุดท้าย โดยบันทึก sequence of clusterings ที่ K-means สร้างขณะแบ่ง clusters สามารถใช้ bisecting K-means สร้าง hierarchical clustering ได้อีกด้วย
