ดังที่กล่าวไว้ก่อนหน้านี้ อัลกอริทึมคลัสเตอร์จำนวนมากไม่ปรับขนาดให้เหมาะกับชุดข้อมูล ในแมชชีนเลิร์นนิง ซึ่งมักจะมีตัวอย่างหลายล้านรายการ ตัวอย่างเช่น อัลกอริทึมการจัดกลุ่มแบบลำดับชั้นหรือการแบ่งแบบซ้อนจะพิจารณาทุกคู่ และมีความซับซ้อน \(O(n^2 log(n))\) และ \(O(n^2)\) ตามลำดับ
หลักสูตรนี้มุ่งเน้นที่ k-mean เนื่องจากปรับขนาดเป็น \(O(nk)\)โดยที่ \(k\) คือจำนวนคลัสเตอร์ที่ผู้ใช้เลือก อัลกอริทึมนี้จะจัดกลุ่มคะแนนเป็น \(k\) คลัสเตอร์โดยการลดระยะห่างระหว่างจุดแต่ละจุดและระยะห่าง เซนทรอยด์ของคลัสเตอร์ (ดูรูปที่ 1)
ดังนั้น k-means จะถือว่าข้อมูลมีประสิทธิภาพเนื่องจากข้อมูลประกอบด้วยตัวเลขคร่าวๆ และพยายามหาคลัสเตอร์ที่ตรงกับ การกระจาย แต่ข้อมูลในชีวิตจริงจะมีค่าผิดปกติ (Outlier) และคลัสเตอร์ที่อิงตามความหนาแน่น และอาจไม่ตรงกับสมมติฐานที่อยู่เบื้องหลัง k-mean
อัลกอริทึมคลัสเตอร์ k-means
อัลกอริทึมจะทำตามขั้นตอนต่อไปนี้
ระบุการคาดเดาเบื้องต้นสำหรับ \(k\)ซึ่งแก้ไขได้ในภายหลัง สำหรับกรณีนี้ ตัวอย่างเช่น เราจะเลือก \(k = 3\)
สุ่มเลือก \(k\) เซนทรอยด์
วันที่ 
รูปที่ 1: k-means ในการเริ่มต้น กำหนดแต่ละจุดให้กับเซนทรอยด์ที่ใกล้ที่สุดเพื่อรับ \(k\) คลัสเตอร์เริ่มต้น
วันที่ 
ภาพที่ 2: คลัสเตอร์เริ่มต้น สำหรับแต่ละคลัสเตอร์ ให้คำนวณจุดศูนย์กลางใหม่โดยใช้อันดับเฉลี่ยของ ทุกจุดในคลัสเตอร์ ลูกศรในรูปที่ 4 แสดงการเปลี่ยนแปลงใน ตำแหน่งเซนทรอยด์
วันที่ 
ภาพที่ 3: เซนทรอยด์ที่คำนวณใหม่ กำหนดแต่ละจุดให้กับเซนทรอยด์ใหม่ที่ใกล้ที่สุด
วันที่ 
ภาพที่ 4: คลัสเตอร์หลังจากการมอบหมายใหม่ ทำขั้นตอนที่ 4 และ 5 ซ้ำ โดยคำนวณเซนทรอยด์และสมาชิกภาพของคลัสเตอร์อีกครั้ง จุดไม่เปลี่ยนคลัสเตอร์อีกต่อไป ในกรณีของชุดข้อมูลขนาดใหญ่ คุณจะทำสิ่งต่อไปนี้ได้ หยุดอัลกอริทึมก่อนที่จะบรรจบกันตามเกณฑ์อื่นๆ
เนื่องจากตำแหน่งเซนทรอยด์ถูกเลือกแบบสุ่มในตอนแรก k-means สามารถ ให้ผลลัพธ์ที่แตกต่างกันอย่างมากในการเรียกใช้ต่อเนื่อง เพื่อแก้ไขปัญหานี้ โจทย์ ให้เรียกใช้ k-means หลายครั้งและเลือกผลลัพธ์ที่มีคุณภาพดีที่สุด เมตริกต่างๆ (เราจะอธิบายเมตริกคุณภาพภายหลังในหลักสูตรนี้) คุณจะต้องมี k-means เวอร์ชันขั้นสูงเพื่อเลือกตำแหน่งจุดศูนย์กลางเริ่มต้นที่ดีขึ้น
แม้ว่าความเข้าใจในคณิตศาสตร์อย่างลึกซึ้งจะไม่เป็นสิ่งจำเป็น แต่สำหรับคนที่ ที่อยากรู้อยากเห็น k-means เป็นกรณีพิเศษของ อัลกอริทึมการเพิ่มการคาดการณ์ โปรดดู บันทึกการบรรยายในหัวข้อนี้จาก UPenn