การจัดกลุ่มแบบ
K-means
Clustering
K-means คือ
หนึ่งในอัลกอริทึมเทคนิคการเรียนรู้โดยไม่มีผู้สอนที่ง่ายที่สุด
เพราะเป็นการแก้ปัญหาการจัดกลุ่มที่รู้จักกันทั่วไป โดยอัลกอริทึม K-Means จะตัดแบ่ง (Partition) วัตถุออกเป็น K กลุ่ม โดยแทนแต่ละกลุ่มด้วยค่าเฉลี่ยของกลุ่ม ซึ่งใช้เป็นจุดศูนย์กลาง (centroid) ของกลุ่มในการวัดระยะห่างของข้อมูลในกลุ่มเดียวกัน
ในขั้นแรกของการจัดกลุ่มโดยการหาค่าเฉลี่ยแบบเคย์ต้องกำหนดจำนวนกลุ่ม (K) ที่ต้องการ และกำหนดจุดศูนย์กลางเริ่มต้นจำนวน K จุด
สิ่งสำคัญในการกำหนดจุดศูนย์กลางเริ่มต้นของแต่ละกลุ่มนี้ ควรจะถูกกำหนดด้วยวิธีที่เหมาะสม
เพราะตำแหน่งจุดศูนย์กลางเริ่มต้นที่แตกต่างกันทำให้ได้ผลลัพธ์สุดท้ายแตกต่างกัน
ดังนั้นในทางที่ดีควรจะกำหนดจุดศูนย์กลางนี้ให้หางจากจุดศูนย์กลางอื่นๆ ขั้นตอนต่อไปคือสร้างกลุ่มข้อมูลและความสัมพันธ์กับจุดศูนย์กลางที่ใกล้มากที่สุด
โดยแต่ละจุดจะถูกกำหนดไปยังจุดศูนย์กลางที่ใกล้เคียงที่สุดจนครบหมดทุกจุด
และคำนวณจุดศูนย์กลางใหม่ โดยการหาค่าเฉลี่ยทุกวัตถุที่อยู่ในกลุ่ม
หากจุดศูนย์กลางในแต่ละกลุ่มถูกเปลี่ยนตำแหน่ง
จะได้จุดมีความสัมพันธ์กับกลุ่มใหม่และใกล้กับจุดศูนย์กลางใหม่
ทำซ้ำแบบนี้ไปเรื่อย ๆ จะสังเกตเห็นว่าผลลัพธ์จากการทำซ้ำแบบนี้ทำให้จุดศูนย์กลางเปลี่ยนตำแหน่งทุกรอบ
จนกระทั่งจุดศูนย์กลางจำนวน K จุด
ไม่มีการเปลี่ยนแปลงจึงจะสิ้นสุดกระบวนการ
2.**อัลกอริทึมการจัดกลุ่มโดย K-means
1.
กำหนดจำนวนกลุ่ม K กลุ่ม
และกำหนดจุดศูนย์กลางเริ่มต้นจำนวน K จุด
2. นำวัตถุทั้งหมดจัดเข้ากลุ่มที่มีจุดศูนย์กลางที่อยู่ใกล้วัตถุนั้นมากที่สุด
โดยคำนวณจากการวัดระยะห่างระหว่างจุดที่น้อยที่สุด
3.
คำนวณจุดศูนย์กลาง K จุดใหม่
โดยหาจากค่าเฉลี่ยทุกวัตถุที่อยู่ในกลุ่ม
4.
ทำซ้ำในข้อ 2.
จนกระทั่งจุดศูนย์กลางไม่เปลี่ยนแปลง
รูป (a) เป็นการจัดกลุ่มในขั้นตอนแรกโดยที่กำหนดจำนวนกลุ่ม
3 กลุ่ม และกำหนดจุดศูนย์กลางเริ่มต้น ซึ่งใช้สัญลักษณ์ + แทนจุดศูนย์กลางของแต่ละกลุ่มทั้ง 3 กลุ่ม จากนั้นวัตถุจะถูกกำหนดให้เข้ากลุ่มที่มีจุดศูนย์กลางอยู่ใกล้วัตถุนั้นมากที่สุดแสดงได้ดังรูป
(b) จุดศูนย์กลางมีการเปลี่ยนแปลงและเกิดความสัมพันธ์ระหว่างวัตถุกับจุดศูนย์กลางใหม่
และจัดวัตถุให้เข้ากลุ่มที่มีจุดศูนย์กลางอยู่ใกล้กับวัตถุนั้นมากที่สุดดังรูป (c) ทำซ้ำเช่นนี้ไปเรื่อย ๆ จนกระทั่งจุดศูนย์กลางไม่เปลี่ยนแปลงจึงจะได้ผลลัพธ์สุดท้ายดังรูป
(d)