K-means clustering เป็นอัลกอริธึมการแบ่งพาร์ติชันที่ใช้บ่อยที่สุด K-means จะกำหนดข้อมูลใหม่ในชุดข้อมูลให้กับกลุ่มใหม่ที่สร้างขึ้นเพียงกลุ่มเดียว บันทึกหรือจุดข้อมูลถูกกำหนดให้กับคลัสเตอร์ที่ใกล้ที่สุดโดยใช้การวัดระยะทางหรือความคล้ายคลึงกัน
อัลกอริธึม k-means สร้างพารามิเตอร์อินพุต k และแบ่งกลุ่มของอ็อบเจ็กต์ n รายการออกเป็น k คลัสเตอร์ เพื่อให้ความคล้ายคลึงใน intracluster มีขนาดใหญ่ แต่การเปรียบเทียบระหว่างคลัสเตอร์มีค่าต่ำ ความคล้ายคลึงของคลัสเตอร์คำนวณจากค่าเฉลี่ยของวัตถุในกระจุก ซึ่งสามารถมองได้ว่าเป็นเซนทรอยด์หรือจุดศูนย์ถ่วงของคลัสเตอร์
มีขั้นตอนต่อไปนี้ที่ใช้ในการจัดกลุ่ม K-means -
-
สามารถเลือก K คลัสเตอร์เริ่มต้น centroid c1 , c2 , c3 …. . . ck .
-
สามารถกำหนดอินสแตนซ์ x แต่ละรายการในคลัสเตอร์ S ที่มีเซนทรอยด์ใกล้กับ x มากที่สุด
-
สำหรับแต่ละคลัสเตอร์ ให้คำนวณเซนทรอยด์ใหม่โดยพิจารณาจากองค์ประกอบที่อยู่ในคลัสเตอร์นั้น
-
ไปที่ (b) จนกว่าคอนเวอร์เจนซ์จะเสร็จสิ้น
-
สามารถแยกวัตถุ (จุดข้อมูล) ออกเป็นคลัสเตอร์ K ได้
-
ใช้สำหรับคลัสเตอร์ center (centroid) =ค่าเฉลี่ยของจุดข้อมูลทั้งหมดในคลัสเตอร์
-
สามารถกำหนดแต่ละจุดให้กับคลัสเตอร์ที่มีเซนทรอยด์อยู่ใกล้ที่สุด (โดยใช้ฟังก์ชันระยะทาง)
ค่าดั้งเดิมสำหรับวิธีการได้รับอนุญาตโดยพลการ สิ่งเหล่านี้สามารถกำหนดแบบสุ่มหรืออาจใช้ค่าจากรายการอินพุต k รายการแรกด้วยตนเอง องค์ประกอบการบรรจบกันสามารถอ้างอิงจากความคลาดเคลื่อนกำลังสอง แต่ไม่จำเป็นต้องเป็นเช่นนั้น ตัวอย่างเช่น อัลกอริทึมถูกกำหนดให้กับคลัสเตอร์ต่างๆ เทคนิคการเลิกจ้างอื่น ๆ ได้ล็อคจำนวนการวนซ้ำคงที่ สามารถรวมจำนวนครั้งสูงสุดได้เพื่อให้แน่ใจว่าการช็อปปิ้งจะไม่มีการบรรจบกัน
อัลกอริทึม
ป้อนข้อมูล −
D = {t1 t2 … tn} // Set of elements
k // Number of desired clusters ผลผลิต −
K // Set of clusters
อัลกอริทึม K-mean −
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
ใช้เพื่อเลือกวัตถุสามชิ้นตามอำเภอใจเป็นศูนย์คลัสเตอร์ดั้งเดิมสามแห่งโดยพลการ โดยที่ศูนย์กลางคลัสเตอร์จะแสดงด้วย "+" แต่ละอ็อบเจ็กต์ถูกแจกจ่ายไปยังคลัสเตอร์ขึ้นอยู่กับศูนย์กลางคลัสเตอร์ที่สะดวก
ถัดไป ศูนย์คลัสเตอร์จะได้รับการอัปเดต ค่าเฉลี่ยของแต่ละคลัสเตอร์จะถูกคำนวณใหม่ตามออบเจ็กต์ที่มีอยู่ทั่วไปในคลัสเตอร์ โดยใช้ศูนย์คลัสเตอร์ใหม่ อ็อบเจ็กต์จะถูกแจกจ่ายไปยังคลัสเตอร์โดยขึ้นอยู่กับศูนย์กลางของคลัสเตอร์ที่อยู่ติดกัน โครงสร้างการกระจายดังกล่าวมีเงาใหม่ที่ล้อมรอบด้วยเส้นโค้งประ
ขั้นตอนของการสร้างอ็อบเจ็กต์ซ้ำไปยังคลัสเตอร์เพื่อปรับปรุงการแบ่งพาร์ติชั่นถูกกำหนดให้เป็นการย้ายตำแหน่งซ้ำ ไม่มีการแจกจ่ายอ็อบเจ็กต์ในคลัสเตอร์ใดๆ ที่ปรากฏขึ้น ดังนั้นกระบวนการจึงถูกลบออก คลัสเตอร์ที่เป็นผลลัพธ์จะถูกกู้คืนโดยเฟสการทำคลัสเตอร์
