กระบวนการแบ่งกลุ่มด้วย Kmean

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

วิธีการแบ่งกลุ่มข้อมูล (data clustering) มีหลายหลาก แต่ที่รู้จักกัน เนื่องด้วยความง่ายต่อการทำความเข้าใจ และผลที่ได้ก็พอจะนำไปใช้งานได้ก็เห็นจะมีในตลาดอยู่ 2 วิธี ได้แก่ วิธีแบ่งกลุ่มแบบลำดับขั้น (Hierachy) กับ วิธีแบ่งกลุ่มโดยการแบ่งเป็นส่วนๆ อย่าง k-mean และในกรณีข้อมูลเยอะๆ เราก็ควรจะเลือกวิธีแบ่งแบบแบ่งส่วนมาพิจารณาก่อน เพราะรวดเร็วกว่าการแบ่งส่วนอย่างเป็นลำดับ  ดังนั้นวันนี้จะกล่าวถึงการแบ่งแบบ k-mean ก่อน

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

1. กำหนดค่าจำนวนกลุ่มข้อมูลที่ต้องการแบ่ง (set k) ก็คือ จำนวนข้อมูลทั้งหมดที่จะนำมาแบ่งสรรออกเป็นกลุ่มๆ นั้นต้องการแบ่งเป็น k กลุุ่ม

2. กำหนดตำแหน่งเริ่มต้น โดยสุ่มกลุ่มข้อมูลเพื่อใช้เป็นค่า centriod เริ่มต้นของกลุ่ม สุ่มมาจำนวนเท่ากับค่ากลุ่มที่ต้องการ

3. กระบวนการจัดหมวดหมู่ ด้วยการตรวจสอบทุกค่าในข้อมูลทั้งหมดว่าข้อมูลใดมีค่าใกล้เคียงกับค่า centroid ใด แล้วให้จัดเข้าอยู่ในกลุ่มเดียวกัน

4. คำนวนค่า centriod โดยภายหลังข้อมูลทุกตัวถูกจัดเข้ากลุ่มแล้ว ให้คำนวณหา centriod ของกลุ่มใหม่

5. ตรวจดูเงื่อนไข โดยทำซ้ำในหัวข้อที่ 3 และ 4 ไปจนกระทั่งไม่มีการเปลี่ยนตำแหน่งของกลุ่ม (กลุ่มคงที่) หรือ จนกระทั่งเข้าถึงค่าสูงสุดของปริมาณข้อมูลที่มี หรือ ผลรวมทั้งหมดของระยะห่างสำหรับข้อมูลคลัสเตอร์ปัจจุบันน้อยกว่าทุกครั้งที่ผ่านมา

หมายเหตุ สำหรับหัวข้อ 3 ผมไม่ขอกำหนดวิธีลงไปว่าจะหาค่าที่เรียกว่า “ใกล้เคียง” ออกมายังไง เพราะทำได้หลายวิธีแล้วแต่เราจะคิดว่ามันดี เช่น นำมาลบออกจากกันเฉยๆ หรือลบออกก่อนแล้วนำมายกกำลังสอง หรือจะด้วยวิธีอะไรก็สุดแล้วแต่ เพียงแค่ต้องการระยะห่างของข้อมูลกับค่ากลางของกลุ่มก็เท่านั้น แต่วิธีที่นิยมคือ  SQUARED Euclidean (sqEuclidean) มีสมการง่ายคือ       หรือเราจะเอาแบบ Euclidean ก็ใช้สมการแบบนี้   

ว่ากันมาเยอะไม่เห็นภาพ งั้นลองมาดูตัวอย่างกัน

สมมุติว่าเรามีภาพเป็นข้อมูล RGB อยู่ 5 ภาพ ตามด้านล่างนี้

       

และเราต้องการจัดแบ่งกลุ่มออกมา 3 กลุ่ม มาดูสิว่า กลุ่มไหนประกอบด้วยภาพใดบ้าง

ขั้นแรก เอาข้อมูลมาเรียงกันก่อน

                     

ขั้นสอง สุ่มเดาๆ แบ่งกลุ่มของเราออกมา 3 กลุ่ม โดยจะขอจัดแบบเดาๆ ให้ข้อมูลภาพที่ 1 กับ 2 เป็นกลุ่มเดียวกัน และภาพ 3 กับ 4 เป็นกลุ่มเดียวกัน ส่วนภาพที่ 5 เป็นอีกกลุ่ม แค่นี้ก็ครบ 3 กลุ่มแล้ว นำไปใส่เป็นตาราง Cluster

ใช้ภาพที่ 1,2 เป็นภาพแรกของกลุ่ม 1 (C1)

C1 = (ภาพ 1 + ภาพ 2)/2

ใช้ภาพที่ 3,4 เป็นภาพแรกของกลุ่ม 2 (C2)

C2 = (ภาพ 3+ ภาพ 4)/2

ใช้ภาพที่ 3 เป็นภาพแรกของกลุ่ม 3 (C3) 

ขั้นที่ 3 เริ่มกระบวนการจัดหมวดหมู่

เราจะเริ่มจากภาพที่ 1 ก่อนเลย ให้หาผลรวมระยะห่างโดยการเอาข้อมูล RGB ของภาพไปลบออกจากข้อมูลแต่ละ Cluster ในที่นี้ผมใช้สมการ Euclidean เป็นตัววัด เช่น นำไปวัดระยะกับ C1 ก็ ระยะห่าง euclidean = รากที่สองของ[(102-124.5)²+(61-81)²+(56-70.5)² ] = 33.4141

มองหาค่าผลรวมระยะห่างที่น้อยที่สุดเป็นผู้ชนะ

ทำเช่นเดียวกันกับภาพที่เหลือทั้ง 4 ภาพ

ต่อด้วยแบ่งจากภาพ 2

ต่อด้วยแบ่งจากภาพ 3

ต่อด้วยแบ่งจากภาพ 4

ต่อด้วยแบ่งจากภาพ 5

ได้กลุ่มของภาพ จากรอบการคำนวณที่ 1 นี้ ดังนี้

ปรับค่า Centroid ใหม่

C1 = [(102+147+70)/3  (61+101+75)/3  (56+85+111)/3] = [106.3333  79.0000  84.0000]

C2  = [109  182  187]

C3  = [69  56  30]

หากจะคำนวณรอบใหม่ก็เอาค่า centroid ใหม่นี้ไปใช้เป็นค่ากลางเริ่มต้นแทนกลุ่มค่ากลางที่เราสุ่มมาใช้ก่อนหน้า โดยตรวจสอบเงื่อนไขว่าตรงกับอย่างใดอย่างหนึ่งที่กล่าวไว้ในขั้นตอนที่ื 5 หรือไม่ จึงจะสิ้นสุดการแบ่งกลุ่มครับ