home

หน้าแรก
 Computer >> บทช่วยสอนคอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

K-means Clustering (การจัดกลุ่ม K-means) คืออะไร?

K-means clustering เป็น partitioning algorithm ที่นิยมใช้มากที่สุด K-means จัดสรร (reassigns) ข้อมูลแต่ละตัวใน dataset ให้อยู่ในเพียงหนึ่งเดียวของ clusters ใหม่ที่สร้างขึ้น Record หรือ data point จะถูก assign ให้กับ cluster ที่ใกล้ที่สุดโดยใช้ measure of distance หรือ similarity

K-means algorithm รับ input parameter k และแบ่งกลุ่ม n objects เป็น k clusters เพื่อให้ intracluster similarity (ความคล้ายคลึงภายในกลุ่ม) สูง แต่ intercluster similarity (ความคล้ายคลึงระหว่างกลุ่ม) ต่ำ Cluster similarity คำนวณจากค่าเฉลี่ย (mean) ของ objects ใน cluster ซึ่งมองได้เป็น centroid หรือ center of gravity ของ cluster

ขั้นตอนของ K-means Clustering

  • เลือก K initial cluster centroids c1, c2, c3... ck

  • Assign แต่ละ instance x ให้กับ cluster S ที่ centroid ใกล้ x ที่สุด

  • สำหรับแต่ละ cluster คำนวณ centroid ใหม่จาก elements ที่อยู่ใน cluster นั้น

  • ทำซ้ำขั้นตอน (b) จนกว่าจะ converge (ค่าหมดเปลี่ยน)

  • แยก objects (data points) ออกเป็น K clusters

  • Cluster center (centroid) = ค่าเฉลี่ยของ data points ทั้งหมดใน cluster

  • Assign แต่ละ point ให้ cluster ที่ centroid ใกล้ที่สุด (ใช้ distance function)

ค่าเริ่มต้นของ means กำหนดแบบ arbitrary สามารถสุ่มได้ หรือใช้ค่าจาก k input items แรกเอง Convergence criterion อาจอิง squared error แต่ไม่จำเป็น ตัวอย่าง algorithm หยุดเมื่อ assignment ไม่เปลี่ยน clusters อื่นๆ ใช้ fixed number of iterations สามารถกำหนด max iterations เพื่อให้หยุดได้แม้ไม่ converge

Algorithm

Input −

D = {t1 t2 … tn} // Set of elements
k // Number of desired clusters

Output −

K // Set of clusters

K-means algorithm −

  assign initial values for means m1 m2 … mk
  repeat
    assign each item ti to the cluster which has the closest mean
    calculate the new mean for each cluster
  until convergence criteria are met

สุ่มเลือก 3 objects เป็น 3 initial cluster centers (cluster centers แทนด้วย "+") แต่ละ object ถูก assign ให้ cluster ตาม cluster center ที่ใกล้ที่สุด

ต่อมา cluster centers ถูกอัปเดต ค่าเฉลี่ยของแต่ละ cluster คำนวณใหม่จาก objects ปัจจุบัน ด้วย cluster centers ใหม่ objects ถูก redistributed ใหม่ ตาม cluster center ที่ใกล้ที่สุด การ redistribute นี้สร้าง silhouettes ใหม่ที่ล้อมด้วย dashed curves

กระบวนการ iteratively reassigning objects to clusters เพื่อปรับปรุง partitioning เรียกว่า iterative relocation ไม่มี redistribution ใน cluster ใดๆ กระบวนการจึงหยุด Clusters ที่ได้ถูกคืนค่าจาก clustering phase