การจัดกลุ่มแบบ K-Means

การจัดกลุ่มแบบ K-means แบ่งข้อมูลออกเป็นจำนวนกลุ่มที่กำหนดไว้ โดยลดผลรวมกำลังสองของระยะห่างภายในกลุ่มไปยังจุดศูนย์กลางของกลุ่มให้เหลือน้อยที่สุด

Definition

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

Scope

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

Core questions

• จะแบ่งข้อมูลเพื่อลดการกระจายตัวภายในกลุ่มได้อย่างไร?
• เหตุใดอัลกอริทึมจึงลู่เข้าสู่จุดเหมาะสมที่สุดเฉพาะที่เท่านั้น และจะบรรเทาปัญหานี้ได้อย่างไร?
• จะเลือกจำนวนกลุ่มได้อย่างไร?
• วิธีการนี้มีข้อสมมติฐานเกี่ยวกับรูปร่างและขนาดของกลุ่มอย่างไรบ้าง?

Key theories

การลดผลรวมกำลังสองภายในกลุ่มให้เหลือน้อยที่สุด

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

ความไวต่อจุดเหมาะสมที่สุดเฉพาะที่

เนื่องจากวัตถุประสงค์ไม่เป็นนูน (non-convex) อัลกอริทึมจึงลู่เข้าสู่ค่าต่ำสุดเฉพาะที่ที่ขึ้นอยู่กับจุดศูนย์กลางเริ่มต้น ซึ่งกระตุ้นให้มีการเริ่มต้นใหม่หลายครั้งและการเลือกจุดเริ่มต้นอย่างระมัดระวัง

Clinical relevance

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

History

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

Debates

ข้อสมมติฐานโดยนัยของ k-means

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

Key figures

• James MacQueen
• Stuart Lloyd

Seminal works

• hastie2009
• everitt2011
• macqueen1967

Frequently asked questions

เหตุใด k-means จึงให้ผลลัพธ์ที่แตกต่างกันในการรันแต่ละครั้ง?

วัตถุประสงค์ของมันไม่เป็นนูน ดังนั้นอัลกอริทึมจึงลู่เข้าสู่จุดเหมาะสมที่สุดเฉพาะที่ที่ขึ้นอยู่กับจุดศูนย์กลางเริ่มต้นแบบสุ่ม การรันหลายครั้งและเก็บผลลัพธ์ที่ดีที่สุดจึงเป็นแนวปฏิบัติมาตรฐาน

จะเลือกจำนวนกลุ่ม k ได้อย่างไร?

หลักการทั่วไปได้แก่ จุดหักศอก (elbow) ในผลรวมกำลังสองภายในกลุ่ม, สถิติช่องว่าง (gap statistic), และความกว้างของภาพเงาเฉลี่ย (average silhouette width) แม้ว่าจะไม่มีวิธีใดที่แน่นอน และความรู้เฉพาะทางมักจะช่วยในการตัดสินใจเลือก