K-Means Clustering คืออะไร — อัลกอริทึมและหลักการทำงาน

K-means clustering เป็นวิธีจัดกลุ่มข้อมูลเชิงตัวเลขออกเป็น $k$ คลัสเตอร์ ถ้าคุณกำหนดค่า $k$ และใช้เวอร์ชันมาตรฐานที่อิงระยะทางแบบยุคลิด อัลกอริทึมจะทำซ้ำเป็นลูปเดียวกัน คือจัดแต่ละจุดไปยังศูนย์กลางที่ใกล้ที่สุด แล้วขยับศูนย์กลางแต่ละตัวไปยังค่าเฉลี่ยของจุดที่ถูกจัดให้อยู่กับมัน

พูดแบบง่าย ๆ มันพยายามทำให้จุดในกลุ่มเดียวกันอยู่ใกล้กัน และจุดคนละกลุ่มอยู่ห่างกันมากขึ้น วิธีนี้ทำงานได้เร็วและมีประโยชน์มาก แต่จะได้ผลดีเมื่อ “กลุ่ม” เหล่านั้นค่อนข้างกระชับ และการใช้ระยะทางเป็นตัววัดความคล้ายมีความหมายจริง

K-means clustering กำลังปรับอะไรให้ดีขึ้น

ในรูปแบบมาตรฐานที่ใช้ระยะทางแบบยุคลิด k-means พยายามทำให้จุดภายในแต่ละคลัสเตอร์อยู่ใกล้เซนทรอยด์ของคลัสเตอร์นั้นมากที่สุด เป้าหมายที่ใช้กันบ่อยคือ

$$\sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2$$

โดยที่ $C_j$ คือคลัสเตอร์ลำดับที่ $j$ และ $\mu_j$ คือเซนทรอยด์ของคลัสเตอร์นั้น

ค่านี้คือผลรวมกำลังสองภายในคลัสเตอร์ หรือ within-cluster sum of squares ยิ่งค่านี้เล็ก ก็ยิ่งหมายความว่าจุดที่ถูกจัดเข้าคลัสเตอร์เกาะอยู่รอบเซนทรอยด์อย่างแน่นขึ้น

เป้าหมายนี้อธิบายได้ว่าทำไมอัลกอริทึมจึงมีสองส่วน:

• ถ้าเซนทรอยด์ถูกตรึงไว้แล้ว วิธีที่ดีที่สุดคือจัดแต่ละจุดไปยังเซนทรอยด์ที่ใกล้ที่สุด
• ถ้าการจัดจุดถูกตรึงไว้แล้ว เซนทรอยด์ที่ดีที่สุดคือค่าเฉลี่ยของจุดที่ถูกจัดให้อยู่ในคลัสเตอร์นั้น

นี่จึงเป็นเหตุผลว่าทำไมกฎการอัปเดตจึงไม่ได้ถูกตั้งขึ้นแบบสุ่ม ๆ คำว่า "means" ใน k-means หมายถึงค่าเฉลี่ยเลขคณิตจริง ๆ

อัลกอริทึม k-means ทำงานอย่างไร

ลูปที่ใช้โดยทั่วไปสั้นมาก:

1. เลือกเซนทรอยด์เริ่มต้นจำนวน $k$ ตัว
2. จัดแต่ละจุดไปยังเซนทรอยด์ที่ใกล้ที่สุด
3. คำนวณเซนทรอยด์แต่ละตัวใหม่เป็นค่าเฉลี่ยของจุดที่ถูกจัดให้อยู่กับมัน
4. ทำซ้ำจนกว่าการจัดกลุ่มจะไม่เปลี่ยนแล้ว หรือค่าที่ดีขึ้นเพิ่มขึ้นเพียงเล็กน้อยมาก

กระบวนการนี้มักลู่เข้าได้เร็ว แต่ไม่ได้รับประกันว่าจะได้การจัดกลุ่มที่ดีที่สุดเสมอไป เซนทรอยด์เริ่มต้นที่ต่างกันอาจนำไปสู่คำตอบสุดท้ายที่ต่างกันได้ ดังนั้นการตั้งต้นจึงสำคัญ

ตัวอย่าง K-means clustering แบบทีละขั้นตอน

พิจารณาข้อมูลหนึ่งมิติต่อไปนี้:

$$1,\ 2,\ 3,\ 10,\ 11,\ 12$$

สมมติว่าเราต้องการ $k = 2$ คลัสเตอร์ และเริ่มด้วยเซนทรอยด์ที่ $1$ และ $10$ นี่เป็นตัวอย่างที่ดี เพราะเซนทรอยด์จะขยับจริงหลังการอัปเดตรอบแรก

ขั้นที่ 1: จัดจุดไปยังเซนทรอยด์ที่ใกล้ที่สุด

จุด $1, 2, 3$ อยู่ใกล้ $1$ มากกว่า

จุด $10, 11, 12$ อยู่ใกล้ $10$ มากกว่า

ดังนั้นคลัสเตอร์คือ

$$C_1 = \{1,2,3\}, \qquad C_2 = \{10,11,12\}$$

ขั้นที่ 2: อัปเดตเซนทรอยด์

เซนทรอยด์ใหม่ของคลัสเตอร์แรกคือ

$$\mu_1 = \frac{1+2+3}{3} = 2$$

เซนทรอยด์ใหม่ของคลัสเตอร์ที่สองคือ

$$\mu_2 = \frac{10+11+12}{3} = 11$$

เซนทรอยด์ทั้งสองตัวขยับ โดยตัวแรกขยับจาก $1$ ไปเป็น $2$ และตัวที่สองขยับจาก $10$ ไปเป็น $11$

ขั้นที่ 3: จัดกลุ่มอีกครั้ง

ตอนนี้ตรวจสอบเซนทรอยด์ที่ใกล้ที่สุดอีกครั้งโดยใช้ $2$ และ $11$

จุด $1, 2, 3$ ยังอยู่ในคลัสเตอร์แรก และจุด $10, 11, 12$ ยังอยู่ในคลัสเตอร์ที่สอง เพราะการจัดกลุ่มไม่เปลี่ยนอีกแล้ว อัลกอริทึมจึงลู่เข้าแล้ว

นี่เป็นตัวอย่างที่ชัดเจน เพราะข้อมูลแยกออกเป็นสองกลุ่มที่กระชับตามธรรมชาติ ชุดข้อมูลจริงมักยุ่งกว่านี้ และนั่นคือจุดที่ k-means อาจเริ่มทำให้คุณตีความผิดได้

K-means ใช้ได้ดีเมื่อไร

K-means จะทำงานได้ดีที่สุดเมื่อเงื่อนไขต่อไปนี้เป็นจริงโดยประมาณ:

• ฟีเจอร์เป็นข้อมูลเชิงตัวเลข
• ระยะทางแบบยุคลิดเป็นวิธีวัดความคล้ายที่สมเหตุสมผล
• คลัสเตอร์ค่อนข้างกระชับ ไม่ยาวหรือโค้ง
• ฟีเจอร์ถูกสเกลแล้ว เพื่อไม่ให้ตัวแปรหนึ่งมีอิทธิพลเหนือกว่าตัวอื่นมากเกินไป

ถ้าเงื่อนไขเหล่านี้ไม่เป็นจริง ผลลัพธ์อาจยังดูเป็นระเบียบ แต่กลับพลาดโครงสร้างจริงของข้อมูล

ข้อผิดพลาดที่พบบ่อยใน k-means

คิดว่า k-means เป็นวิธีจัดกลุ่มที่ใช้ได้กับทุกกรณี

K-means ทำงานได้ดีที่สุดเมื่อคลัสเตอร์ค่อนข้างกระชับ และค่าเฉลี่ยเป็นตัวแทนที่สมเหตุสมผล มันไม่ใช่ตัวเลือกเริ่มต้นที่ดีสำหรับทุกชุดข้อมูล

มองข้ามการสเกลฟีเจอร์

ถ้าฟีเจอร์หนึ่งมีหน่วยหรือช่วงค่าที่ใหญ่กว่าอีกฟีเจอร์มาก ฟีเจอร์นั้นอาจครอบงำการคำนวณระยะทางได้ การทำ standardization หรือ normalization ของฟีเจอร์มักสำคัญก่อนรัน k-means

คิดว่าคำตอบมีเพียงแบบเดียว

K-means อาจลู่เข้าไปยัง local minima ที่ต่างกันได้จากจุดเริ่มต้นที่ต่างกัน นี่จึงเป็นเหตุผลว่าทำไมจึงมักรันหลายครั้ง หรือใช้วิธีตั้งต้นแบบ k-means++

ใช้กับฟีเจอร์ที่ไม่ใช่ตัวเลข หรือเข้ารหัสมาไม่เหมาะสม

เพราะเซนทรอยด์คือค่าเฉลี่ย k-means แบบมาตรฐานจึงถูกออกแบบมาสำหรับตัวแปรเชิงตัวเลข ถ้าฟีเจอร์เป็นข้อมูลเชิงหมวดหมู่ การหาค่าเฉลี่ยเลขคณิตอาจไม่มีความหมาย

ใช้กับคลัสเตอร์ที่ไม่เป็นทรงกลมหรือไม่กระชับอย่างชัดเจน

ถ้ากลุ่มจริงมีลักษณะยาว โค้ง หรือมีความหนาแน่นต่างกันมาก k-means อาจแยกกลุ่มธรรมชาติหนึ่งออกเป็นสองส่วน หรือรวมสองกลุ่มที่ต่างกันเข้าด้วยกัน วิธีนี้ชอบคลัสเตอร์ที่กระชับและอิงเซนทรอยด์

ลืมว่าค่าผิดปกติสามารถดึงเซนทรอยด์ให้เคลื่อนได้

เพราะเซนทรอยด์คือค่าเฉลี่ย ค่าสุดโต่งสามารถทำให้ตำแหน่งของมันเปลี่ยนไปอย่างเห็นได้ชัด ถ้าข้อมูลของคุณมี outliers ที่สำคัญ ควรตรวจสอบจุดนี้ก่อนเชื่อผลลัพธ์

K-means clustering ถูกใช้ที่ไหน

K-means มักถูกใช้เพื่อการจัดกลุ่มเชิงสำรวจ การแบ่งกลุ่มลูกค้าหรือพฤติกรรม การลดจำนวนสีในภาพ และใช้เป็น baseline แบบรวดเร็วในงาน unsupervised learning

มันมีประโยชน์มากที่สุดเมื่อคุณมีฟีเจอร์เชิงตัวเลข ต้องการโมเดลที่เร็วและเรียบง่าย และคาดว่าคลัสเตอร์จะค่อนข้างกระชับในปริภูมิแบบยุคลิด

ภาพจำง่าย ๆ

ลองนึกภาพว่าคุณปักหมุดที่ขยับได้จำนวน $k$ อันลงบน scatterplot ทุกจุดจะไปเกาะกับหมุดที่ใกล้ที่สุด จากนั้นหมุดแต่ละอันจะเลื่อนไปยังตำแหน่งเฉลี่ยของจุดที่เกาะอยู่กับมัน ทำซ้ำไปเรื่อย ๆ จนหมุดแทบไม่ขยับแล้ว

ภาพนี้ไม่ได้เป็นแค่การเปรียบเทียบเพื่อให้เข้าใจง่ายเท่านั้น แต่มันแทบจะเป็นตัวอัลกอริทึมทั้งหมดเลย

ลองทำโจทย์จัดกลุ่มที่คล้ายกัน

ลองเลือกจุดจำนวนไม่มากบนเส้นจำนวน กำหนด $k = 2$ แล้วทำหนึ่งรอบเต็มของขั้นตอนจัดกลุ่มและอัปเดตด้วยมือ จากนั้นเปลี่ยนเซนทรอยด์เริ่มต้น หรือเพิ่ม outlier หนึ่งจุด แล้วดูว่าผลลัพธ์เปลี่ยนอย่างไร ถ้าอยากลองต่ออีกขั้น ให้ทดลองกับชุดข้อมูลเล็ก ๆ ของคุณเอง แล้วเปรียบเทียบสิ่งที่เกิดขึ้นก่อนและหลังการสเกลฟีเจอร์