อัลกอริธึม k-means สร้างพารามิเตอร์อินพุต k และแบ่งกลุ่มของอ็อบเจ็กต์ n รายการออกเป็น k คลัสเตอร์ เพื่อให้ความคล้ายคลึงใน intracluster มีขนาดใหญ่ แต่การเปรียบเทียบระหว่างคลัสเตอร์มีค่าต่ำ ความคล้ายคลึงของคลัสเตอร์คำนวณจากค่าเฉลี่ยของวัตถุในกระจุก ซึ่งสามารถมองได้ว่าเป็นเซนทรอยด์หรือจุดศูนย์ถ่วงของคลัสเตอร์
อัลกอริทึม k-means ดำเนินการดังนี้ ขั้นแรก มันสามารถสุ่มเลือก k ของอ็อบเจ็กต์ ซึ่งแต่ละอันกำหนดค่าเฉลี่ยคลัสเตอร์หรือจุดศูนย์กลาง สำหรับวัตถุที่เหลือแต่ละรายการ วัตถุจะถูกสร้างขึ้นไปยังคลัสเตอร์ที่เหมือนกัน ขึ้นอยู่กับระยะห่างระหว่างวัตถุและค่าเฉลี่ยคลัสเตอร์
สามารถคำนวณค่าเฉลี่ยใหม่สำหรับแต่ละคลัสเตอร์ เฟสนี้จะวนซ้ำจนกว่าฟังก์ชันหลักจะมาบรรจบกัน โดยทั่วไป เกณฑ์ข้อผิดพลาดกำลังสองจะแสดงเป็น −
$$\mathrm{E=\displaystyle\sum\limits_{i=1}^k\displaystyle\sum\limits_{p\epsilon C_{i}}|p-m_{i}|^2}$$
โดยที่ E คือผลรวมของความคลาดเคลื่อนกำลังสองสำหรับบางออบเจกต์ในชุดข้อมูล p คือจุดในช่องว่างที่กำหนดวัตถุที่กำหนดและ mi เป็นค่าเฉลี่ยของคลัสเตอร์ Ci (ทั้ง p และ mi มีหลายมิติ) โดยเฉพาะอย่างยิ่งสำหรับวัตถุแต่ละชิ้นในแต่ละกระจุก ระยะห่างจากวัตถุไปยังจุดศูนย์กลางของกระจุกจะเป็นกำลังสอง และระยะทางจะถูกประมาณการ เกณฑ์นี้พยายามสร้างคลัสเตอร์ k ที่เป็นผลลัพธ์ให้มีขนาดกะทัดรัดและเป็นอิสระตามความเหมาะสม
อัลกอริทึม: k หมายถึง − อัลกอริทึม k-mean สำหรับการแบ่งพาร์ติชัน โดยที่ศูนย์กลางของคลัสเตอร์ทุกแห่งถูกกำหนดโดยค่าเฉลี่ยของอ็อบเจ็กต์ในคลัสเตอร์
อินพุต -
k: the number of clusters, D: a data set including n objects.
เอาท์พุต -
A set of k clusters.
วิธีการ -
-
เลือกวัตถุ k จาก D เป็นศูนย์คลัสเตอร์ดั้งเดิมโดยพลการ
-
ซ้ำ
-
(อีกครั้ง)กำหนดแต่ละวัตถุให้กับคลัสเตอร์ที่วัตถุเหมือนกัน ขึ้นอยู่กับค่าเฉลี่ยของวัตถุในคลัสเตอร์;
-
อัปเดตความหมายของคลัสเตอร์ กล่าวคือ คำนวณค่าเฉลี่ยของออบเจ็กต์สำหรับแต่ละคลัสเตอร์
-
จนกว่าจะไม่มีการเปลี่ยนแปลง
ใช้เพื่อเลือกวัตถุสามชิ้นตามอำเภอใจเป็นศูนย์คลัสเตอร์ดั้งเดิมสามแห่งโดยพลการ โดยที่ศูนย์กลางคลัสเตอร์จะแสดงด้วย "+" แต่ละอ็อบเจ็กต์ถูกแจกจ่ายไปยังคลัสเตอร์ขึ้นอยู่กับศูนย์คลัสเตอร์ที่สะดวก
ถัดไป ศูนย์คลัสเตอร์จะได้รับการอัปเดต ค่าเฉลี่ยของแต่ละคลัสเตอร์จะถูกคำนวณใหม่ตามออบเจ็กต์ที่มีอยู่ทั่วไปในคลัสเตอร์ โดยการใช้ศูนย์คลัสเตอร์ใหม่ อ็อบเจ็กต์จะถูกแจกจ่ายไปยังคลัสเตอร์ขึ้นอยู่กับศูนย์กลางคลัสเตอร์ที่อยู่ติดกัน โครงสร้างการกระจายดังกล่าวมีเงาใหม่ที่ล้อมรอบด้วยเส้นโค้งประ
เฟสของการกำหนดอ็อบเจ็กต์แบบวนซ้ำไปยังคลัสเตอร์เพื่อปรับปรุงการแบ่งพาร์ติชันถูกกำหนดเป็นการย้ายตำแหน่งแบบวนซ้ำ ไม่มีการแจกจ่ายซ้ำของวัตถุในคลัสเตอร์ใด ๆ ปรากฏขึ้น ดังนั้นกระบวนการจึงถูกลบออก คลัสเตอร์ที่เป็นผลลัพธ์จะถูกกู้คืนโดยเฟสการทำคลัสเตอร์
