Skip to content
กลับไปยังผลการค้นหา

การจัดกลุ่มแบบ K-means

ผู้เสนอ
MacQueen, J. B.; Lloyd, S. P.
ปี
1967 (formalized 1982)
ประเภท
Partitional clustering
กลุ่มวิธี
Machine learning

ข้อความนี้เป็นการแปลด้วยเครื่องและยังไม่ได้รับการตรวจทาน อ่านต้นฉบับภาษาอังกฤษ

ขนาดตัวอักษร

ใช้ทำอะไร?

K-means เป็นอัลกอริทึมการแบ่งกลุ่มแบบไม่มีผู้สอน (unsupervised partitional clustering) แบบคลาสสิกที่แบ่งชุดข้อมูลออกเป็น K กลุ่มที่ไม่ทับซ้อนกัน โดยการกำหนดจุดข้อมูลแต่ละจุดไปยังจุดศูนย์กลาง (centroid) ที่ใกล้ที่สุดซ้ำๆ และปรับปรุงจุดศูนย์กลางให้เป็นค่าเฉลี่ยของจุดที่ถูกกำหนดให้ เป็นหนึ่งในเครื่องมือสำรวจที่ใช้กันอย่างแพร่หลายที่สุดในการเรียนรู้ของเครื่องและการวิเคราะห์ข้อมูล

แนวคิดเบื้องหลังวิธีการ

ลองนึกภาพการวางแม่เหล็ก K อันลงบนแผนที่ของจุดข้อมูล แต่ละจุดจะถูกดึงดูดไปยังแม่เหล็กที่ใกล้ที่สุด จากนั้นแม่เหล็กแต่ละอันจะเคลื่อนไปยังจุดศูนย์กลางแรงโน้มถ่วงของจุดที่มันดึงดูด ทำซ้ำวงจรการดึงและเคลื่อนที่นี้จนกว่าจะไม่มีอะไรเคลื่อนไหว: แม่เหล็กได้พบกลุ่มธรรมชาติ K กลุ่มแล้ว K-means ทำให้แนวคิดนี้เป็นรูปธรรม โดยลดผลรวมกำลังสองของระยะทางจากทุกจุดไปยังศูนย์กลางกลุ่มของมันให้เหลือน้อยที่สุด ซึ่งเรียกว่าผลรวมกำลังสองของระยะทางภายในกลุ่ม (within-cluster sum of squares - WCSS หรือ inertia)

ประวัติศาสตร์

แนวคิด K-means ถูกนำเสนอโดยอิสระโดย MacQueen ในปี 1967 ผู้บัญญัติศัพท์ และทำให้เป็นอัลกอริทึมการทำซ้ำที่มีประสิทธิภาพโดย Stuart Lloyd ที่ Bell Labs ในทศวรรษที่ 1950 (ตีพิมพ์ปี 1982) การปรับปรุงการเริ่มต้นแบบ k-means++ โดย Arthur และ Vassilvitskii ในปี 2007 ได้แก้ไขปัญหาความไวต่อค่าต่ำสุดเฉพาะที่ ปัจจุบัน K-means ยังคงเป็นวิธีการเรียนรู้แบบไม่มีผู้สอนที่เป็นแกนหลัก ซึ่งสอนกันในหลักสูตรวิทยาศาสตร์ข้อมูลเกือบทั้งหมด

ควรใช้เมื่อใด

K-means เหมาะสำหรับการจัดกลุ่มเชิงสำรวจ (exploratory clustering) ของชุดข้อมูลตัวเลขขนาดใหญ่ เมื่อคุณต้องการการแบ่งกลุ่มที่รวดเร็วและปรับขนาดได้ และสะดวกใจที่จะระบุ K ล่วงหน้าหรือค้นหาด้วยวิธีข้อศอกหรือเงา เหมาะสำหรับการแบ่งส่วนลูกค้า (customer segmentation), การบีบอัดรูปภาพ (image compression), การจัดกลุ่มหัวข้อเอกสาร (document topic grouping) และการประมวลผลเบื้องต้นก่อนการเรียนรู้แบบมีผู้สอน (supervised learning) หลีกเลี่ยงหากกลุ่มไม่เป็นทรงกลม มีขนาดหรือความหนาแน่นแตกต่างกันมาก เมื่อคุณลักษณะเป็นประเภท (categorical) หรือลำดับ (ordinal) (ใช้ k-modes หรือ k-prototypes แทน) เมื่อจำนวนกลุ่มไม่เป็นที่ทราบแน่ชัดและไม่สามารถทำการทดลอง K ที่หลากหลายได้ หรือเมื่อข้อมูลมีค่าผิดปกติ (outliers) จำนวนมาก (ใช้ DBSCAN หรือรูปแบบที่ทนทานแทน)

ข้อจำกัดและข้อควรพิจารณา

  • ต้องระบุ K ล่วงหน้า การเลือก K ที่ไม่เหมาะสมจะทำให้เกิดกลุ่มที่ไม่มีความหมาย
  • สมมติว่ากลุ่มเป็นทรงกลม มีขนาดใกล้เคียงกัน กลุ่มที่ยืดออก ผิดปกติ หรือมีสเกลต่างกันจะถูกแบ่งหรือรวมกันอย่างไม่ถูกต้อง
  • ไวต่อค่าผิดปกติ: จุดสุดขีดเพียงจุดเดียวสามารถดึงจุดศูนย์กลางออกห่างจากกลุ่มส่วนใหญ่ได้
  • ทำงานได้กับคุณลักษณะตัวเลขต่อเนื่องเท่านั้น ข้อมูลประเภทต้องใช้อัลกอริทึมอื่น (k-modes)
  • ลู่เข้าสู่ค่าต่ำสุดเฉพาะที่ ผลลัพธ์อาจแตกต่างกันไปในการทำงานแต่ละครั้งด้วย seed สุ่มที่ต่างกัน เว้นแต่จะใช้ k-means++ หรือการเริ่มต้นใหม่หลายครั้ง

เงื่อนไขจากแหล่งที่มาไม่สามารถใช้แทนการทบทวนทางวิทยาศาสตร์ที่เป็นอิสระหรือการตรวจสอบโดยเอนจินวิเคราะห์ได้

จุดแข็ง

  • รวดเร็วและปรับขนาดได้: O(nKdi) ต่อรอบการทำงาน สามารถใช้งานได้กับข้อมูลหลายล้านจุดที่มี K และมิติปานกลาง
  • ง่ายต่อการนำไปใช้ มีให้ใช้งานอย่างแพร่หลายในทุกเฟรมเวิร์ก ML หลัก และอธิบายให้ผู้ที่ไม่มีความรู้ทางเทคนิคเข้าใจได้ง่าย
  • ทำงานได้ดีกับกลุ่มขนาดใหญ่ที่แยกจากกันอย่างชัดเจน เป็นทรงกลมโดยประมาณ และมีขนาดใกล้เคียงกัน
  • การเริ่มต้นแบบ k-means++ ช่วยลดความไวต่อเงื่อนไขเริ่มต้นได้อย่างมากเมื่อเทียบกับการเริ่มต้นแบบสุ่ม
  • กำหนดผลลัพธ์ที่แน่นอนภายใน seed สุ่มที่กำหนด ทำให้ผลลัพธ์สามารถทำซ้ำได้

การประยุกต์ใช้

  • การแบ่งส่วนลูกค้า (Customer segmentation) สำหรับการตลาดและการปรับเปลี่ยนเฉพาะบุคคลตามคุณลักษณะพฤติกรรมหรือข้อมูลประชากร
  • การบีบอัดรูปภาพ (Image compression) โดยการควอนไทซ์สีพิกเซลให้เป็นค่าตัวแทน K ค่า (color quantization)
  • การจัดกลุ่มเอกสารและข้อความ (Document and text clustering) เป็นขั้นตอนในไปป์ไลน์การสร้างแบบจำลองหัวข้อ (topic modeling) หลังจากการแปลงเป็นเวกเตอร์
  • การประมวลผลเบื้องต้นสำหรับการตรวจจับความผิดปกติ (Anomaly detection pre-processing): จุดที่อยู่ห่างจากจุดศูนย์กลางใดๆ เป็นค่าผิดปกติที่อาจเกิดขึ้น
  • ขั้นตอนการเริ่มต้นสำหรับอัลกอริทึมที่ซับซ้อนกว่า เช่น แบบจำลองส่วนผสมแบบเกาส์เซียน (Gaussian mixture models) หรือการจัดกลุ่มแบบลำดับชั้น (hierarchical clustering)
  • การวิเคราะห์การแสดงออกของยีน (Gene expression analysis) เพื่อจัดกลุ่มยีนหรือตัวอย่างที่มีโปรไฟล์การแสดงออกที่คล้ายคลึงกัน

วิธีการทำงาน

วิธีการทำงาน

1

จุดศูนย์กลางกลุ่ม K จุดจะถูกวางไว้ในปริภูมิคุณลักษณะ (feature space) โดยการสุ่มเลือกจุดข้อมูล K จุด (Forgy) หรือโดยกลยุทธ์ k-means++ ที่ชาญฉลาดกว่าซึ่งกระจายจุดศูนย์กลางเริ่มต้นเพื่อลดโอกาสของการเกิดค่าต่ำสุดเฉพาะที่ (local minima) ที่ไม่ดี การเลือกการเริ่มต้นมีความสำคัญ: k-means++ มักจะให้การลู่เข้าที่เร็วกว่าและผลลัพธ์สุดท้ายที่ดีกว่า

2

จุดสังเกตทุกจุดจะถูกกำหนดให้กับกลุ่มที่มีจุดศูนย์กลางใกล้ที่สุดตามระยะทางแบบยุคลิด (Euclidean distance) การกำหนดแบบแข็ง (hard assignment) นี้สร้างการแบ่งข้อมูล K ส่วนที่ไม่ทับซ้อนกัน ตามรูปแบบแล้ว จุด x_i แต่ละจุดจะถูกกำหนดให้กับกลุ่ม c_i = argmin_k ||x_i - mu_k||^2

สูตร
c_i = \arg\min_k \|x_i - \mu_k\|^2
3

จุดศูนย์กลางแต่ละจุดจะถูกคำนวณใหม่เป็นค่าเฉลี่ยเลขคณิตของจุดทั้งหมดที่ถูกกำหนดให้กับกลุ่มนั้นๆ ในปัจจุบัน: mu_k = (1/|C_k|) คูณผลรวมของ x_i ทั้งหมดใน C_k ขั้นตอนนี้รับประกันว่าจุดศูนย์กลางใหม่จะลด WCSS ภายในแต่ละกลุ่มให้เหลือน้อยที่สุดเมื่อพิจารณาจากการกำหนดปัจจุบัน

สูตร
\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_i
4

ขั้นตอนการกำหนดและการปรับปรุงจะสลับกันไปจนกว่าตำแหน่งของจุดศูนย์กลางจะหยุดเปลี่ยนแปลง (หรือเปลี่ยนแปลงน้อยกว่าเกณฑ์ความคลาดเคลื่อนที่กำหนด) หรือถึงจำนวนรอบสูงสุดที่กำหนดไว้ อัลกอริทึมรับประกันว่าจะลู่เข้าสู่ค่าต่ำสุดเฉพาะที่ของ WCSS แต่ไม่จำเป็นต้องเป็นค่าต่ำสุดทั่วโลก (global minimum)

5

คุณภาพของผลลัพธ์จะประเมินด้วย WCSS รวม (inertia) J = ผลรวมของกลุ่มต่างๆ ของผลรวมของจุดที่ถูกกำหนดของ ||x_i - mu_k||^2 การเลือก K เป็นประเด็นแยกต่างหากที่แก้ไขโดยวิธีข้อศอก (elbow method), คะแนนเงา (silhouette scores), หรือสถิติก้าวน้อย (gap statistics) เนื่องจากอัลกอริทึมเองต้องการให้ K ถูกระบุล่วงหน้า

สูตร
J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2

ข้อผิดพลาดที่พบบ่อย

  • การลืมปรับมาตรฐานคุณลักษณะ (standardize features) ก่อนการจัดกลุ่ม - ตัวแปรที่มีสเกลใหญ่จะมีอิทธิพลต่อการคำนวณระยะทาง
  • การเลือก K โดยการตรวจสอบ WCSS ภายในตัวอย่างเพียงอย่างเดียวโดยไม่มีการพล็อตแบบข้อศอก (elbow plot) หรือการตรวจสอบเงา (silhouette validation) ทำให้ได้ K ที่เล็กเกินไปหรือใหญ่เกินไปอย่างไม่มีความหมาย
  • การทำงานเพียงครั้งเดียวและยอมรับผลลัพธ์แรกโดยไม่มีการเริ่มต้นใหม่หลายครั้งเพื่อป้องกันค่าต่ำสุดเฉพาะที่ที่ไม่ดี
  • การรวมตัวแปรประเภทหรือลำดับในเมทริกซ์คุณลักษณะโดยไม่มีการเข้ารหัสที่เหมาะสม หรือเปลี่ยนไปใช้ k-modes
  • การปฏิบัติต่อป้ายกลุ่ม (cluster labels) เสมือนว่าเป็นตัวระบุกลุ่มที่มีความหมายโดยไม่มีการตรวจสอบภายนอก โดยเฉพาะอย่างยิ่งเมื่อกลุ่มไม่ได้แยกจากกันอย่างชัดเจน

คำถามที่พบบ่อย

ฉันจะเลือกจำนวนกลุ่ม K ที่เหมาะสมได้อย่างไร?

เรียกใช้ k-means สำหรับช่วงของค่า K, พล็อตผลรวมกำลังสองของระยะทางภายในกลุ่มเทียบกับ K, และมองหา 'ข้อศอก' ที่อัตราการลดลงช้าลงอย่างรวดเร็ว เสริมด้วยคะแนนเงา (silhouette scores) ซึ่งวัดว่าแต่ละจุดมีความคล้ายคลึงกับกลุ่มของตนเองมากเพียงใดเมื่อเทียบกับกลุ่มข้างเคียง คะแนนเงาเฉลี่ยที่สูงขึ้นบ่งชี้ถึงกลุ่มที่กำหนดได้ดีขึ้น

ทำไมฉันถึงได้ผลลัพธ์ที่แตกต่างกันในแต่ละครั้งที่รัน?

K-means มีความไวต่อการเริ่มต้นและลู่เข้าสู่ค่าต่ำสุดเฉพาะที่ (local minimum) ของ WCSS แทนที่จะเป็นค่าต่ำสุดทั่วโลก (global minimum) ใช้การเริ่มต้นแบบ k-means++ และตั้งค่า seed สุ่มที่แน่นอนเพื่อความสามารถในการทำซ้ำ การรันอัลกอริทึมหลายครั้งด้วย seed ที่แตกต่างกันและเก็บผลลัพธ์ที่มีค่า inertia ต่ำสุดเป็นแนวปฏิบัติที่ดี

K-means ทำงานกับข้อมูลประเภทได้หรือไม่?

ไม่ K-means อาศัยระยะทางแบบยุคลิดและค่าเฉลี่ยของจุดศูนย์กลาง ซึ่งไม่สามารถกำหนดได้สำหรับตัวแปรประเภท สำหรับข้อมูลประเภทล้วนๆ ให้ใช้ k-modes สำหรับข้อมูลผสมระหว่างตัวเลขและประเภท ให้ใช้ k-prototypes

เมื่อใดที่ฉันควรเลือก DBSCAN หรือ GMM แทน K-means?

ใช้ DBSCAN เมื่อกลุ่มมีรูปร่างไม่สม่ำเสมอ หรือคุณต้องการการตรวจจับค่าผิดปกติอัตโนมัติโดยไม่ต้องระบุ K ใช้แบบจำลองส่วนผสมแบบเกาส์เซียน (GMM) เมื่อคุณต้องการการกำหนดกลุ่มแบบอ่อน (probabilistic) หรือกลุ่มที่มีขนาดและทิศทางแตกต่างกัน โดยมีค่าใช้จ่ายเป็นความซับซ้อนในการคำนวณที่สูงขึ้น

ฉันจำเป็นต้องปรับสเกลคุณลักษณะของฉันหรือไม่?

ใช่ เกือบจะเสมอ K-means ใช้ระยะทางแบบยุคลิด ดังนั้นคุณลักษณะที่มีช่วงตัวเลขขนาดใหญ่จะมีอิทธิพลต่อการจัดกลุ่ม ใช้การปรับมาตรฐานแบบ z-score หรือการปรับสเกลแบบ min-max ก่อนการปรับ K-means เว้นแต่คุณลักษณะทั้งหมดจะอยู่ในสเกลเดียวกันอยู่แล้ว

วิธีการที่เกี่ยวข้อง

แหล่งอ้างอิง

  1. Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137.

    เปิดเอกสารอ้างอิง DOI
    คัดลอกแล้ว
  2. MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.

    เปิดเอกสารอ้างอิงสิ่งพิมพ์
    คัดลอกแล้ว