ความหมายของ K-means
K-means algorithm รับพารามิเตอร์อินพุท k และแบ่งกลุ่มของ n วัตถุเป็น k คลัสเตอร์ เพื่อให้ intracluster similarity (ความคล้ายคลึงภายในคลัสเตอร์) สูง แต่ intercluster similarity (ความคล้ายคลึงระหว่างคลัสเตอร์) ต่ำ ความคล้ายคลึงของคลัสเตอร์คำนวณเกี่ยวกับค่าเฉลี่ย (mean value) ของวัตถุในคลัสเตอร์ ซึ่งสามารถมองเป็น centroid (จุดศูนย์กลาง) หรือ center of gravity ของคลัสเตอร์
ขั้นตอนของอัลกอริทึม
K-means algorithm ดำเนินการดังนี้: ขั้นแรก เลือก k วัตถุจากข้อมูลแบบสุ่ม (randomly) แต่ละตัวนิยาม cluster mean หรือ center เริ่มต้น สำหรับวัตถุที่เหลือทั้งหมด วัตถุจะถูกมอบหมายให้กับคลัสเตอร์ที่คล้ายที่สุด (most similar) ขึ้นอยู่กับระยะทางระหว่างวัตถุและ cluster mean
คำนวณ mean ใหม่สำหรับแต่ละคลัสเตอร์ ขั้นตอนนี้วนซ้ำ (iterates) จนกว่า criterion function จะ收敛 (converges) โดยทั่วไป square-error criterion แทนด้วย:
$$\mathrm{E=\displaystyle\sum\limits_{i=1}^k\displaystyle\sum\limits_{p\epsilon C_{i}}|p-m_{i}|^2}$$
โดยที่ E คือ ผลรวมของ square error สำหรับวัตถุทั้งหมดในชุดข้อมูล p คือ จุดในพื้นที่ที่แทนวัตถุที่กำหนด และ mi คือ mean ของคลัสเตอร์ Ci (ทั้ง p และ mi เป็นหลายมิติ) โดยเฉพาะ สำหรับแต่ละวัตถุในแต่ละคลัสเตอร์ ระยะทางจากวัตถุไปยังศูนย์กลางคลัสเตอร์ของมันถูกยกกำลังสอง และระยะทางถูกประมาณค่า เกณฑ์นี้พยายามทำให้ k คลัสเตอร์ที่ได้เป็น compact (กระชับ) และ separated (แยกจากกัน) มากที่สุดเท่าที่เป็นไปได้
อัลกอริทึม K-means
Input: k: จำนวนคลัสเตอร์, D: ชุดข้อมูลที่มี n วัตถุ
Output: เซตของ k คลัสเตอร์
Method:
เลือก k วัตถุจาก D แบบสุ่ม (arbitrarily) เป็น cluster centers เริ่มต้น;
repeat (ทำซ้ำ)
(re)assign แต่ละวัตถุไปยังคลัสเตอร์ที่วัตถุคล้ายที่สุด ขึ้นอยู่กับค่าเฉลี่ยของวัตถุในคลัสเตอร์;
อัปเดต cluster means คือ คำนวณค่าเฉลี่ยของวัตถุสำหรับแต่ละคลัสเตอร์;
until no change (จนกว่าจะไม่มีการเปลี่ยนแปลง);
ใช้การเลือก 3 วัตถุแบบสุ่มเป็น 3 cluster centers เริ่มต้น โดย cluster centers แทนด้วย "+" แต่ละวัตถุถูกแจกจ่ายไปยังคลัสเตอร์ขึ้นอยู่กับ cluster center ที่สะดวก (convenient) ที่สุด
ต่อมา cluster centers ถูกอัปเดต ค่าเฉลี่ยของแต่ละคลัสเตอร์คำนวณใหม่ตามวัตถุที่มีอยู่ในคลัสเตอร์ โดยใช้ cluster centers ใหม่ วัตถุถูกแจกจ่ายใหม่ไปยังคลัสเตอร์ขึ้นอยู่กับ cluster center ที่ใกล้ที่สุด การแจกจ่ายใหม่นี้สร้าง silhouettes ใหม่ที่ล้อมรอบด้วยเส้นโค้งขีด (dashed curves)
ขั้นตอนการมอบหมายวัตถุไปยังคลัสเตอร์ซ้ำๆ เพื่อปรับปรุงการแบ่งพาร์ติชัน เรียกว่า iterative relocation (การย้ายที่ซ้ำๆ) ไม่มีการแจกจ่ายวัตถุในคลัสเตอร์ใดๆ เปลี่ยนแปลง และกระบวนการสิ้นสุด คลัสเตอร์ที่ได้ถูกคืนค่าโดยขั้นตอนการจัดกลุ่ม
