คลัสเตอร์แบบ K-means คืออะไร

ดังที่ได้กล่าวไว้ก่อนหน้านี้ อัลกอริทึมการจัดกลุ่มจำนวนมากไม่สามารถปรับขนาดให้เข้ากับชุดข้อมูลที่ใช้ในแมชชีนเลิร์นนิง ซึ่งมักจะมีตัวอย่างหลายล้านรายการ ตัวอย่างเช่น อัลกอริทึมการจัดกลุ่มตามลําดับชั้นแบบรวมกลุ่มหรือแบบแยกกลุ่มจะพิจารณาคู่จุดทั้งหมดและมีความซับซ้อนของ $O(n^2 log(n))$ และ $O(n^2)$ตามลําดับ

หลักสูตรนี้มุ่งเน้นที่ K-Means เนื่องจากปรับขนาดเป็น $O(nk)$โดยที่ $k$เป็นจํานวนคลัสเตอร์ที่ผู้ใช้เลือก อัลกอริทึมนี้จะจัดกลุ่มจุดเป็น$k$ คลัสเตอร์โดยลดระยะทางระหว่างจุดแต่ละจุดกับจุดศูนย์กลางของคลัสเตอร์ (ดูรูปที่ 1)

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

อัลกอริทึมการจัดกลุ่ม K-means

อัลกอริทึมจะทําตามขั้นตอนต่อไปนี้

1. ระบุค่าประมาณเริ่มต้นสำหรับ $k$ซึ่งจะแก้ไขได้ในภายหลัง ในตัวอย่างนี้ เราจะเลือก $k = 3$

2. เลือก $k$ จุดศูนย์กลางแบบสุ่ม

   

   รูปที่ 1: K-Means ในการเริ่มต้น

3. กําหนดแต่ละจุดให้กับจุดศูนย์กลางมวลที่ใกล้ที่สุดเพื่อรับ $k$ คลัสเตอร์เริ่มต้น

   

   รูปที่ 2: คลัสเตอร์เริ่มต้น

4. สําหรับคลัสเตอร์แต่ละกลุ่ม ให้คํานวณจุดศูนย์กลางมวลใหม่โดยนําค่าเฉลี่ยของตําแหน่งจุดทั้งหมดในคลัสเตอร์ รูปที่ 4 แสดงการเปลี่ยนแปลงของตําแหน่งจุดศูนย์กลาง

   

   รูปที่ 3: ศูนย์กลางมวลที่คำนวณใหม่

5. กำหนดจุดแต่ละจุดใหม่เป็นจุดศูนย์กลางใหม่ที่อยู่ใกล้ที่สุด

   

   รูปที่ 4: คลัสเตอร์หลังจากการมอบหมายใหม่

6. ทําซ้ำขั้นตอนที่ 4 และ 5 โดยคํานวณจุดศูนย์กลางและสมาชิกคลัสเตอร์อีกครั้งจนกว่าจุดจะไม่เปลี่ยนคลัสเตอร์อีก ในกรณีที่เป็นชุดข้อมูลขนาดใหญ่ คุณสามารถหยุดอัลกอริทึมก่อนการบรรจบได้โดยอิงตามเกณฑ์อื่นๆ

เนื่องจากในตอนแรกระบบจะเลือกตำแหน่งจุดศูนย์กลางแบบสุ่ม K-Means จึงอาจให้ผลลัพธ์ที่แตกต่างกันอย่างมากในการเรียกใช้ครั้งต่อๆ ไป วิธีแก้ปัญหานี้คือให้เรียกใช้ K-Means หลายครั้ง แล้วเลือกผลลัพธ์ที่เมตริกคุณภาพดีที่สุด (เราจะอธิบายเมตริกคุณภาพในภายหลังในหลักสูตรนี้) คุณต้องใช้ K-Means เวอร์ชันขั้นสูงเพื่อเลือกตำแหน่งจุดศูนย์กลางเริ่มต้นที่ดีกว่า

แม้ว่าไม่จําเป็นต้องเข้าใจคณิตศาสตร์อย่างละเอียด แต่สำหรับผู้ที่สนใจ เราสามารถอธิบายได้ว่า K-Means เป็นกรณีพิเศษของอัลกอริทึมการเพิ่มค่าคาดหวังสูงสุด ดูเนื้อหาบรรยายเกี่ยวกับหัวข้อนี้จาก UPenn