ทำความรู้จักกับ Mean Shift Clustering

พอพูดถึงการจัดกลุ่มข้อมูล (Clustering) อัลกอริธึ่มที่คนส่วนใหญ่นึกถึงก็น่าจะเป็น k-means clustering ซึ่งโดยตัวมันเองแล้วเป็นอัลกอริธึ่มที่เข้าใจได้ง่าย มีประสิทธิภาพ ใช้กันแพร่หลาย แต่ก็มีข้อเสียอย่างหนึ่งคือเราจำเป็นต้องรู้จำนวนของกลุ่มข้อมูล (จำนวน cluster) หรือค่า k ก่อน บทความนี้จะมาแนะนำอัลกอรึธึ่มสำหรับการจัดกลุ่มข้อมูลอีกตัวหนึ่งแบบคร่าวๆ ที่มีชื่อว่า Mean shift ครับ

ข้อแตกต่างระหว่าง Mean shift กับ k-means

ที่เห็นได้ชัดๆ คือ

  1. Mean shift เป็น density-based clustering ส่วน k-means เป็น centroid-based clustering กล่าวคือ Mean shift จะใช้คอนเซปของ kernel density estimation (KDE) ในการหาตัวแทนกลุ่มของข้อมูล หรือ centroid ในขณะที่ k-means จะใช้ค่าเฉลี่ยระหว่างจุดกับ centroid ในการขยับ centroid ไปเรื่อยๆ
  2. Mean shift ไม่จำเป็นต้องรู้จำนวนกลุ่มของข้อมูลก่อน ส่วน k-means จำเป็นที่ต้องรู้ก่อน แต่ Mean shift ก็มีค่า parameter ที่เราต้องปรับเองตามการใช้งานครับ เค้าเรียกกันว่า kernel bandwidth

หลักการทำงานของ Mean shift

  1. ให้จุดทุกจุดเป็น cluster ของตัวมันเองก่อนเลย ถ้ามี 10 จุดข้อมูล ก็แปลว่าเรามี 10 clusters ก่อนเลยครับ
  2. ให้เราเลือก kernel ที่เหมาะสมกับข้อมูล ซึ่งโดยปกติแล้วจะเป็นฟังก์ชั่น Gaussian ครับ ตามสูตรของ Gaussian แล้ว เราจะได้ว่า kernel bandwidth ของเราคือ standard deviation นั่นเอง 😀
  3. คัดลอกจุดทุกจุดเก็บไว้ก่อนเป็น 2 ชุดข้อมูล แล้วนำจุดทุกจุดในชุดข้อมูลใดข้อมูลหนึ่ง ผมเรียกว่าเป็นข้อมูลชุดที่ 1 กับข้อมูลชุดที่ 2 ละกัน แล้วทำไมต้องแยกเป็น 2 ชุด? นี่เป็นเหตุผลทางด้านการเขียนโปรแกรมล้วนๆ ครับ 😛
  4. เสร็จแล้วเราจะมา estimate กับจุดทุกจุดในข้อมูลชุดที่ 2 โดยใช้ kernel ที่เราเลือกมากับจุดทุกจุดในข้อมูลชุดที่ 1 ครับ หรือพูดง่ายๆ ว่าเราใช้จุดทุกจุดในการอัพเดท cluster แต่ละ cluster ครับ ซึ่งจุดแต่ละจุดในข้อมูลชุดที่ 2 จะถูก estimate แล้วจะค่อยๆ เลื่อนเข้าสู่จุด convergence หรือจุดสูงสุดของ Gaussian (นึกภาพระฆังคว่ำ) แล้วเราอัพเดท cluster อย่างไรล่ะ? ขอยกไปอธิบายคร่าวๆ ต่อด้านล่าง
  5.  หลังจากที่ converge แล้ว ถ้าข้อมูลของเรามีการกระจายตัวหน้าตาแบบมี 3 ระฆังคว่ำ (หรือ 3 clusters) จุดข้อมูลของเราก็จะย้ายไปสู่จุดสูงสุดของ 3 ระฆังคว่ำนั้นโดยอัตโนมัติเองครับ
  6. ท้ายที่สุดคือการ assign จุดเหล่านั้นว่าควรจะอยู่ cluster ไหน ยังจำข้อมูลที่เราคัดลอกไว้ในข้อ 3 ได้ใช่ไหมครับ? เราก็เอาจุดเหล่านั้นมาทีละจุด เทียบระยะห่างระหว่างจุดสูงสุดของระฆังคว่ำที่เราได้มา จุดไหนใกล้ก็ assign จุดนั้นให้เข้าไปกับระฆังอันนั้นครับเป็นอันเสร็จสิ้น!

สำหรับการ shift หรืออัพเดทค่า mean (เป็นเหตุผลที่เค้าเรียกว่า mean shift) ทำได้โดยใช้เทคนิค gradient ascent ครับ ซึ่งจริงๆ คือ gradient descent แต่แค่มีทิศตรงข้าม ลองดูสมการในรูป 1 ด้านล่างนี้ครับ เป็นรูปจากงานวิจัยของ Dorin Comaniciu กับ Peter Meer

Mean Shift Term
รูป 1: พจน์ของ mean shift

สมการที่ 17 นี้เป็นพจน์ของ mean shift ครับ ซึ่งเราสามารถนำเอาส่วนที่ผมตีกรอบเส้นประสีแดงมาเป็นค่า mean ที่โดน shift แล้ว ส่วนฟังก์ชั่น g ในทีนี้ก็คือ kernel ของเรานั่นเอง ซึ่งในงานวิจัยนี้เค้าพิสูจน์ว่ามันเพียงพอสำหรับการ converge ลองตามไปอ่านกันดูนะครับ math เยอะสะใจดี >_<

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

เท่าที่ผมเห็นส่วนใหญ่เค้าจะเอา Mean shift clustering ไปใช้ในงานพวก image processing หรือ เอาคอนเซปไปใช้กับ people tracking ครับ จะไม่ค่อยเห็นมาใช้กับงาน data mining สักเท่าไหร่

ใครสนใจอยากเอาโค้ดไปลองรันเล่น เชิญที่ GitHub ของ mattnedrich ครับ ใช้ Python เขียนน่าจะเข้าใจได้ไม่ยากครับ 😛

ถ้าใครมีข้อเสนอแนะเพิ่มเติม ขอเชิญมาร่วมแบ่งปันนะครับ

Author: zkan

Soon to be a newbie data scientist. I ♥ machine learning, computer vision, robotics, image processing, data visualization, and data analytics.

2 thoughts on “ทำความรู้จักกับ Mean Shift Clustering”

  1. ขั้นที่ 3 ไม่ค่อย clear คับ จากขั้นที่ 1 ถ้าเรามี 10 จุดเราก็มี 10 cluster แต่ละ cluster ก็มี mean vector และ bandwidth แล้วเรา update mean vector ยังไงเอ่ย และ cluster ที่ไม่มีสมาชิกจะหายไปได้อย่างไร

  2. ขอบคุณมากครับ (-/\-) ผมลองแก้ไขเนื้อหาตามที่คุยกันเรียบร้อยแล้วครับ แอบเอาสมการจากเปเปอร์ mean shift มาช่วยเสริมเผื่อคนอื่นเข้ามาแล้วสงสัย แหะๆ

Leave a Reply

Your email address will not be published. Required fields are marked *