การแบ่งกลุ่มข้อมูลแบบเคมีน

การแบ่งกลุ่มข้อมูลแบบเคมีน (อังกฤษ: k-means clustering ) เป็นวิธีหนึ่งในวิธีการแบ่งเวกเตอร์ (vector quantization) ที่มีรากฐานมาจากการประมวลผลสัญญาณ วิธีนี้เป็นที่นิยมสำหรับการแบ่งกลุ่มข้อมูล (cluster analysis) ในการทำเหมืองข้อมูล (data mining) การแบ่งกลุ่มข้อมูลแบบเคมีนใช้สำหรับการแบ่งการสังเกตจำนวน n สิ่งเป็น k กลุ่ม โดยแต่ละการสังเกตจะอยู่ในกลุ่มที่มีค่าเฉลี่ย(ที่ใช้เป็นแม่แบบ)ใกล้เคียงกันที่สุด โดยวิธีนี้จะเป็นการแบ่งพื้นที่ข้อมูลไปเป็นแผนภาพโวโรนอย
วิธีการจัดกลุ่มนี้อยู่ในกลุ่มความซับซ้อนของปัญหาเอ็นพีแบบยาก (NP-hard) แต่อย่างไรเราสามารถนำขั้นตอนวิธีแบบศึกษาสำนึก (heuristic algorithm) มาใช้หาจุดศูนย์กลางของกลุ่มข้อมูลจากการลู่เข้าได้อย่างมีประสิทธิภาพ ซึ่งจะเหมือนกับขั้นตอนวิธีหาค่าคาดหมายสูงสุด (expectation-maximization algorithm) สำหรับโมเดลแบบผสม (Mixture Model) ของการแจกแจงปรกติ (Gaussian distribution) เนื่องจากทั้งสองขั้นตอนวิธีจะใช้แนวทางกระทำซ้ำการกลั่นกรอง (iterative refinement approach) นอกจากนี้ ทั้งสองขั้นตอนวิธียังใช้จุดศูนย์กลางของคลัสเตอร์สร้างแบบจำลองข้อมูล อย่างไรก็ตาม การแบ่งกลุ่มข้อมูลแบบเคมีนมีแนวโน้มจะได้คลัสเตอร์ผลลัพธ์ที่มีตำแหน่งขอบเขตใกล้เคียงกัน ในขณะที่ขั้นตอนวิธีหาค่าคาดหมายสูงสุดนั้นยอมให้คลัสเตอร์ผลลัพธ์มีรูปร่างที่แตกต่างกันได้
ขั้นตอนวิธีนี้ไม่มีอะไรเกี่ยวข้องกับวิธีการค้นหาเพื่อนบ้านใกล้สุด (k-nearest neighbor) ซึ่งเป็นเทคนิคการเรียนรู้ของเครื่อง (machine learning) ที่เป็นที่นิยมอีกอย่างหนึ่ง

คำอธิบาย

สมมติให้มีเซตของการสังเกต (x₁, x₂, …, xₙ) โดยแต่ละการสังเกตเป็นเวกเตอร์ค่าจริงใน d มิติ การแบ่งกลุ่มข้อมูลแบบเคมีนจะตัดแบ่งการสังเกตจำนวน n ครั้งให้เป็นข้อมูลจำนวน k ชุด (โดยที่ k น้อยกว่าหรือเท่ากับ n) ในเซต S = {S₁, S₂, …, Sₖ} ที่จะทำให้ค่าผลบวกกำลังสองภายในคลัสเตอร์ (within-cluster sum of squares; WCSS) มีค่าน้อยที่สุด. หรือพูดได้อีกอย่างว่า จุดประสงค์ของการแบ่งกลุ่มข้อมูลแบบเคมีนคือการหาผลลัพธ์ต่อไปนี้:
โดยที่ μᵢ เป็นค่าเฉลี่ยของจุดใน Sᵢ.

ประวัติ

คำศัพท์ "k-means" ได้ถูกระบุใช้ครั้งแรกโดย James MacQueen ในปี พ.ศ. 2510, แม้ว่าแนวคิดเริ่มแรกจะเป็นของ Hugo Steinhaus ซึ่งเกิดขึ้นในปี พ.ศ. 2500. และขั้นตอนวิธีมาตรฐานนั้นก็ถูกเสนอขึ้นในปี พ.ศ. 2500 โดย Stuart Lloyd เพื่อเป็นเทคนิคสำหรับการกล้ำรหัสของพัลส์ (pulse-code modulation) อย่างไรก็ตามขั้นตอนวิธีไม่ได้ถูกเผยแพร่ออกไปจาก Bell Labs จนกระทั่งปี พ.ศ. 2525 ในปี พ.ศ. 2508 E.W.Forgy ได้ตีพิมพ์วิธีเดียวกันนี้เช่นกัน จึงทำให้บางครั้งวิธีนี้ถูกกล่าวถึงในชื่อ Lloyd-Forgy นอกจากนี้ได้มีการตีพิมพ์แบบฉบับที่มีการพัฒนาขึ้นไป โดย Hartigan and Wong ในปี พ.ศ. 2518/2522

วิธีการกำหนดค่าตั้งต้น

โดยทั่วไปแล้ว จะใช้วิธีของ Forgy และวิธีการตัดแบ่งแบบสุ่ม (Random Partition) เป็นวิธีการกำหนดค่าตั้งต้น วิธีของ Forgy คือการเลือกข้อมูลการสังเกต k อย่างขึ้นมาแบบสุ่ม จากข้อมูลทั้งหมด แล้วใช้เป็นค่าเฉลี่ยเริ่มต้น ส่วนการตัดแบ่งข้อมูลแบบสุ่มนั้นจะเริ่มต้นด้วยการสุ่มจัดข้อมูลการสังเกตแต่ละอันไปอยู่ในกลุ่มใดๆ และจากนั้นจะทำการปรับค่าตามขั้นตอนที่กล่าวไปแล้ว ดังนั้นค่าเฉลี่ยเริ่มต้นที่ได้จาการปรับค่าจะเป็นจุดเซนทรอยด์ (centroid) ของข้อมูลการสังเกตในแต่ละคลัสเตอร์ที่สร้างขึ้นมาแบบสุ่มนั่นเอง วิธีของ Forgy มีแนวโน้มที่จะกระจายค่าเฉลี่ยเริ่มต้น ในขณะที่การตัดแบ่งข้อมูลแบบสุ่มจะเลือกค่าเริ่มต้นที่ใกล้กับจุดกึ่งกลางของข้อมูลทั้งหมด นอกจากนี้ อ้างอิงจาก Hamerly et al., การตัดแบ่งข้อมูลแบบสุ่มที่เหมาะกับขั้นตอนวิธีการหา k-harmonic means และ fuzzy k-means มากกว่า ในทางกลับกัน สำหรับขั้นตอนวิธีหาค่าคาดหมายสูงสุด หรือขั้นตอนวิธีการหาเคมีนแบบมาตรฐาน วิธีของ Forgy จะเป็นที่นิยมมากกว่า
การที่เป็นขั้นตอนวิธีแบบศึกษาสำนึก มันจะไม่สามารถรับประกันได้ว่ากระบวนการนี้จะลู่เข้าหา global optimum และการจัดกลุ่มในตอนเริ่มต้น หรือการกำหนดค่าตั้งต้นจะมีผลอย่างมากต่อผลลัพธ์ อย่างไรก็ตามขั้นตอนวิธีนี้สามารถหาผลลัพธ์ได้อย่างรวดเร็ว จึงเป็นเรื่องปรกติที่จะทดสอบข้อมูลหลายๆครั้งด้วยเงื่อนไขเริ่มต้นที่แตกต่างกัน แต่ในกรณีที่เลวร้ายที่สุดค่าเคมีน (k-means) อาจจะลู่เข้าอย่างช้า ซึ่งมีความเป็นไปได้แม้แต่กับข้อมูลจำนวนน้อยๆ และมีการแสดงอย่างเฉพาะเจาะจงว่า สำหรับในบางตัวอย่างข้อมูล ที่มีแค่สองมิติ การหาค่าเคมีนเป็นขั้นตอนวิธีเวลาแบบเลขชี้กำลัง (exponential time) หรือก็คือ 2 ในการลู่เข้า ข้อมูลดังกล่าวเหมือนว่าจะไม่เกิดขึ้นในการปฏิบัติจริง จึงสามารถยืนยันได้ว่า เวลาที่ใช้ในการทำงานที่ปรับเรียบ (smoothed running time) ของขั้นตอนการหาค่าเคมีนเป็นเป็นฟังก์ชันพหุนาม
ขั้นตอนการกำหนดค่ามีอีกชื่อหนึ่งคือ ขั้นตอนการคาดหมาย (expectation step) และขั้นตอนการปรับค่าสามารถเรียกว่า ขั้นตอนการหาค่าสูงสุด maximization step ทำให้ขั้นตอนวิธีนี้เป็นส่วนหนึ่งของขั้นตอนวิธีหาค่าคาดหมายสูงสุดแบบทั่วไป (generalized expectation-maximization algorithm)

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

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

การแบ่งนับเวกเตอร์

การแบ่งกลุ่มแบบเคมีนถูกริเริ่มขึ้นเพื่อใช้ในการประมวลสัญญาณและยังคงถูกใช้มาจนถึงในปัจจุบันนี้ ยกตัวอย่างเช่นในคอมพิวเตอร์กราฟิก, การแบ่งนับสี (Color quantization) เป็นกระบวนการของการลดจำนวนชนิดสีในแต่ละภาพให้เหลือเพียงจำนวนสีเท่ากับ k ตามที่ถูกกำหนดไว้ ซึ่งการการแบ่งกลุ่มแบบเคมีนนี้สามารถนำมาใช้เพื่อปฏิบัติการแบ่งนับสีได้อย่างง่ายดายและมีประสิทธิภาพ การใช้ประโยชน์จากการแบ่งนับเวกเตอร์อย่างอื่นได้แก่การชักตัวอย่างแบบไม่สุ่ม (non-random sampling) ซึ่งการแบ่งกลุ่มแบบเคมีนช่วยในการเลือก k ชนิดของข้อมูลที่แตกต่างกันจากจำนวนข้อมูลขนาดใหญ่เพื่อการดำเนินการวิเคราะห์ผลต่อไป

การวิเคราะห์กลุ่มข้อมูล

ในการวิเคราะห์กลุ่มข้อมูล (Cluster Analysis) การแบ่งกลุ่มแบบเคมีนสามารถถูกนำมาใช้ในการแบ่งเซ็ตข้อมูลอินพุทให้เป็น k ส่วนได้ อย่างไรก็ตามด้วยการแบ่งกลุ่มแบบเคมีนเพียงอย่างเดียวไม่ยืดหยุ่นพอที่จะใช้แบ่งกลุ่มข้อมูลได้อย่างมีประสิทธิภาพโดยเฉพาะอย่างยิ่งความยากในการเลือกค่าของ k ที่เหมาะสมต่อกลุ่มข้อมูลและข้อจำกัดที่การแบ่งกลุ่มแบบเคมีนนั้นไม่สามารถใช้แบ่งเซ็ตข้อมูลที่ไม่ใช่ตัวเลขได้ ด้วยเหตุนี้อัลกอริทึมอื่นๆจึงถูกพัฒนาขึ้นทดแทนการแบ่งกลุ่มแบบเคมีนเพื่อผลลัพธ์ที่ดีขึ้น

ฟีเจอร์เลิร์นนิ่ง (Feature learning)

การแบ่งกลุ่มข้อมูลแบบเคมีนได้ถูกนำไปใช้ในขั้นตอนฟีเจอร์เลิร์นนิ่ง (Feature learning) ทั้งในการเรียนรู้แบบมีผู้สอน (supervised learning) การเรียนรู้แบบกึ่งมีผู้สอน (semi-supervised learning) และการเรียนรู้แบบไม่มีผู้สอน (unsupervised learning) ขั้นตอนในการปฏิบัติเริ่มจากการสร้างกลุ่มข้อมูลจำนวน k กลุ่มด้วยการแบ่งกลุ่มข้อมูลแบบเคมีนโดยใช้ข้อมูลสอน (training data) หลังจากนั้นจึงโปรเจกต์ข้อมูลอินพุทไปยังฟีเจอร์สเปซใหม่ โดยใช้แมทริกส์โปรดัคระหว่างข้อมูลและตำแหน่งของศูนย์กลางของแต่ละกลุ่มข้อมูล ระยะห่างระหว่างข้อมูลอินพุทและศูนย์กลางของแต่ละกลุ่มข้อมูล ฟังก์ชันที่ชี้ข้อมูลอินพุทถึงจุดศูนย์กลางของกลุ่มข้อมูลที่ใกล้ที่สุด หรือสมูทฟังก์ชันของระยะห่างระหว่างข้อมูลและศูนย์กลางของกลุ่มข้อมูลเป็นต้น
การใช้งานของการแบ่งกลุ่มแบบเคมีนนี้ประสบความสำเร็จในร่วมใช้งานกับตัวแยกแบบเชิงเส้น (linear classifier) สำหรับข้อมูลแบบกึ่งมีผู้สอนในการประมวลภาษาธรรมชาติ และในคอมพิวเตอร์วิทัศน์ โดยเฉพาะอย่างยิ่งในการรู้จำวัตถุ (object recognition) นั้นการแบ่งกลุ่มข้อมูลแบบเคมีนสามารถให้ผลลัพธ์ที่มีประสิทธิภาพใกล้เคียงกับวิธีการฟีเจอร์เลิร์นนิ่งที่ซับซ้อนแบบอื่นยกตัวอย่างเช่น [autoencoders]] และ [restricted Boltzmann machines]. อย่างไรก็ตามการแบ่งกลุ่มข้อมูลแบบเคมีนนั้นต้องการจำนวนข้อมูลอินพุทที่มีขนาดมากกว่าที่วิธีฟีเจอร์เลิร์นนิ่งที่ซับซ้อนที่กล่าวมาข้างต้นต้องการเพื่อให้ได้ผลลัพธ์ที่ใกล้เคียงกัน เนื่องจากในการแบ่งกลุ่มข้อมูลแบบเคมีนนั้น ข้อมูลแต่ละอันส่งผลถึงฟีเจอร์เพียงอันเดียวมากกว่าที่จะส่งผลถึงหลายๆฟีเจอร์

ความสัมพันธ์กับอัลกอริธึมการเรียนรู้ของเครื่องแบบอื่นๆ

เราสามารถกล่าวได้ว่าการแบ่งกลุ่มข้อมูลแบบเคมีนและอัลกอริทึมแบบ EM นั้นเป็นเพียงแค่เคสพิเศษของการประมาณรูปร่างผสมของเกาส์ (Gaussian mixture model) ดังนั้นโดยปรกติแล้วเราจึงสามารถเปลี่ยนรูปของการแบ่งกลุ่มข้อมูลแบบเคมีนให้อยู่ในรูปของรูปร่างผสมของเกาส์ได้ นอกจากรูปร่างผสมของเกาส์แล้ว เรายังสามารถเปลี่ยนรูปของการแบ่งกลุ่มข้อมูลแบบเคมีนให้อยู่ในรูปของอัลกอริทึมแบบ K-SVD ซึ่งเป็นอัลกอริทึมที่คาดการณ์จุดข้อมูลแต่ล่ะจุดในรูปแบบของผลรวมเชิงเส้นของ"เวกเตอร์โค้ดบุ้ค" (codebook vector) โดยที่การแบ่งกลุ่มข้อมูลแบบเคมีนนั้นมีความข้องเกี่ยวกับกรณีที่มีการใช้เวกเตอร์โค้ดบุ้คเพียงเวกเตอร์เดียวด้วยค่าน้ำหนักเท่ากับหนึ่งเท่านั้น

การแบ่งกลุ่มแบบมีนชิฟท์ (Mean shift clustering)

การแบ่งกลุ่มแบบมีนชิฟท์นั้นเป็นอัลกอริทึมที่คงจำนวนของข้อมูลในเซ็ตไว้ให้มีขนาดที่เท่ากับจำนวนข้อมูลอินพุทเริ่มต้น ในจุดเริ่มต้นของอัลกอริทึมนั้นเซ็ตของข้อมูลนี้เกิดจากการคัดลอกมาจากเซ็ตข้อมูลอินพุท หลังจากนั้นในแต่ละการวนซ้ำข้อมูลในเซ็ตนี้ได้ถูกแทนที่ด้วยค่าเฉลี่ยของจุดข้อมูลที่อยู่ในเซ็ตที่อยู่ภายในระยะทางที่กำหนดจากจุดข้อมูลจุดนั้น ในทางกลับกันการที่การแบ่งกลุ่มข้อมูลแบบเคมีนจำกัดการอัปเดตข้อมูลนี้ให้อยู่ที่ข้อมูล k จุดและเปลี่ยนค่าของแต่ละจุดใน k จุดนี้ด้วยค่าเฉลี่ยของจุดข้อมูลทุกจุดที่ในเซ็ตข้อมูลอินพุทที่อยู่ใกล้กับจุดจุดนั้นที่สุดเมื่อเทียบกับจุดอื่นใน k จุด การแบ่งกลุ่มแบบมีนชิฟท์ที่มีลักษณะคล้ายคลึงกับการแบ่งกลุ่มแบบเคมีนนั้นเรียกว่า likelihood mean shift ซึ่งในอัลกอริทึมนี้มีการแทนที่ค่าของเซ็ตข้อมูลด้วยค่าเฉลี่ยของจุดข้อมูลทั้งหมดในเซ็ตอินพุทที่มีระยะห่างภายในระยะทางที่กำหนดไว้จากเซ็ตนั้นๆ  การแบ่งกลุ่มแบบมีนชิฟท์นั้นมีข้อได้เปรียบอย่างหนึ่งเหนือการแบ่งกลุ่มข้อมูลแบบเคมีนซึ่งคือการที่การแบ่งกลุ่มแบบมีนชิฟท์นั้นไม่จำเป็นต้องมีการกำหนดจำนวนของกลุ่มข้อมูลเพราะว่าการแบ่งกลุ่มแบบมีนชิฟท์นั้นจะหาจำนวนของกลุ่มข้อมูลที่จำเป็นโดยอนิมัติ แต่อย่างไรก็ตามการแบ่งกลุ่มแบบมีนชิฟท์นั้นใช้เวลาในการประมวลผลนานกว่าการแบ่งกลุ่มแบบเคมีนมาก

การวิเคราะห์ส่วนประกอบสำคัญ (Principal component analysis)

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

การวิเคราะห์องค์ประกอบอิสระ (Independent component analysis)

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

การกรองข้อมูลแบบสองฝ่าย (Bilateral filtering)

การแบ่งกลุ่มข้อมูลแบบเคมีนมีการทึกทักเอาว่าลำดับของจุดข้อมูลแต่ละจุดในเซ็ตข้อมูลอินพุทนั้นไม่มีผลต่ออัลกอริทึม การกรองข้อมูลแบบสองฝ่าย ([bilateral filter]) นั้นเหมือนกับการแบ่งกลุ่มข้อมูลของเคมีนด้วยตรงที่ว่ามันมีการเก็บรักษาเซ็ตของข้อมูลในขณะที่มีการแทนที่ข้อมูลด้วยค่าเฉลี่ยในแต่ละการวนซ้ำ อย่างไรก็ตามการกรองข้อมูลแบบสองฝ่ายจำกัดการคำนวณของค่าเฉลี่ย (แบบ kernel weighted)ให้รวมถึงเพียงแค่จุดข้อมูลที่ใกล้ในลำดับของข้อมูลอินพุท ด้วยเหตุนี้การกรองข้อมูลแบบสองฝ่ายจึงสามารถนำไปประยุกต์ใช้ได้กับปัญหาเช่นการขจัดสัญญาณรบกวนในรูปภาพ (image denoising) ซึ่งการเรียงตัวของพิกเซลในภาพนั้นมีความสำคัญเป็นอย่างยิ่ง

อัลกอริทึมที่ใกล้เคียง

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