K-Means Clustering

Understanding K-Means Clustering

• เพื่อเข้าใจการจัดกลุ่มแบบ K-Means Clustering

Theory

• โดยทั่วไปจะใช้เรื่องในเข้ามาจัดการเป็นอย่างปกมาก

T-shirt size problem

• โดยการจะทำเสื้อยืดนั้น บริษัทจะต้องผลิตรูปแบบและขนาดที่แตกต่างกันเพื่อตอบสนองผู้บริโภคโดยจะทำให้เหมาะสมกับผู้คนทุกๆ ไซต์โดยโดยจะยกตัวอย่างกราฟด้านล่างนี้

• และบริษัทนั้นไม่สามารถสร้างเสื้อยืดที่มีขนาดทุกๆขนาดได้ แต่จะแบ่งออกเป็น คนตัวเล็ก คนตัวขนาดกลาง คนตัวใหญ่ และจะสามารถผลิตแค่ 3 Size เพื่อให้พอดีทุกคน ในการจัดกลุ่มแบบนี้สามารถทำผ่าน K-Means Clustering ได้โดยวิธีที่ดีที่สุดคือ 3 Size และหากไม่เป็นเช่นนั้น สามารถแบ่งกลุ่มเพิ่มได้อีก อาจจะ 5 size ดูที่รูปภาพ

หลักการทำงาน

• ขั้นตอนวิธี (algorithm) ของกระบวนการที่เกิดซ้ำแล้วซ้ำอีก นั้นจะสามารถอธิบายโดย step-by-step ในการช่วยงานด้าน image โดยวิิธีคือ

ขั้นตอนที่ 1

• Algorithm จะสุ่มเลือกสอง centroids คือ C1 และ C2

ขั้นตอนที่ 2

• จะคำนวณระยะห่างจากจุดแต่ละจุดของ centroids หากข้อมูลที่ทดสอบนั้น ใกล้ชิด C1 แล้วข้อมูลจะใส่ชื่อกำกับว่า '0' หากข้อมูลที่ทดสอบ ใกล้กับ C2 จะใส่ชื่อกำกับว่า '1' หากมี Centroid มากขึ้นก็จะใส่ชื่อเพิ่มลำดับไปเรื่อยๆ

• ในกรณณีที่จะใส่ให้กับ '0' นั้นเป็นสีแดง และใส่สีให้กับ '1' เป็นสีฟ้า

ขั้นตอนที่ 3

• ต่อไปจะเป็นการคำนวณค่าเฉลี่ยของจุดสีฟ้าและจุดสีแดงที่แยกจากกัน โดย new centroid = C1 และ C2
  • และนำข้อมูลใหม่นี้ไปทำเหมือนกันกับ ขั้นตอนที่สอง

Final Step

• ใน Step นี้ เมื่อทำ ขั้นตอนที่ 2-3 เสร็จแล้วจะวนทำซ้ำจนกว่าทั้ง centroids จะแปรสภาพไปยังจุดคงที่ * โดยจุดเหล่านั้นเป็นผลรวมของระยะทางระหว่างข้อมูลการทดสอบและ centroids ที่สอดคล้องกันขอพวกมันนั้น จะมีขั้นต่ำเท่าไหร่ หรือ เพียงแค่ผลรวมของระยะทางเท่านั้น โดย

C1↔Red_Points and C2↔Blue_Points คือค่าต่ำสุด ดังสูตร

• • โดยผลลัพธ์ คือ