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

การแบ่งกลุ่มข้อมูลแบบเคมีน (อังกฤษ: 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_n) โดยแต่ละการสังเกตเป็นเวกเตอร์ค่าจริงใน d มิติ การแบ่งกลุ่มข้อมูลแบบเคมีนจะตัดแบ่งการสังเกตจำนวน n ครั้งให้เป็นข้อมูลจำนวน k ชุด (โดยที่ k น้อยกว่าหรือเท่ากับ n) ในเซต S = {S₁, S₂, …, S_k} ที่จะทำให้ค่าผลบวกกำลังสองภายในคลัสเตอร์ (within-cluster sum of squares; WCSS) มีค่าน้อยที่สุด. หรือพูดได้อีกอย่างว่า จุดประสงค์ของการแบ่งกลุ่มข้อมูลแบบเคมีนคือการหาผลลัพธ์ต่อไปนี้:

${\displaystyle {\underset {\mathbf {S} }{\operatorname {arg\,min} }}\sum _{i=1}^{k}\sum _{\mathbf {x} \in S_{i}}\left\|\mathbf {x} -{\boldsymbol {\mu }}_{i}\right\|^{2}}$ 

โดยที่ μ_i เป็นค่าเฉลี่ยของจุดใน S_i.

ประวัติ

คำศัพท์ "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

ขั้นตอนวิธี

ขั้นตอนวิธีมาตรฐาน

 

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

ขั้นตอนวิธีที่ใช้มากที่สุดใช้แนวทางกระทำซ้ำการกลั่นกรอง (iterative refinement approach) และถูกเรียกว่า การแบ่งกลุ่มข้อมูลแบบเคมีน (k-means algorithm) หรือในบางครั้งสามารถพบในชื่อ Lloyd's algorithm โดยเฉพาะในวงการวิทยาการคอมพิวเตอร์ เริ่มด้วยเซตเริ่มต้นประกอบด้วยค่าเฉลี่ย k ค่า m₁⁽¹⁾,…,m_k⁽¹⁾ แล้วจากนั้นจะเป็นการทำซ้ำระหว่างสองขั้นตอน

ขั้นตอนการกำหนดค่า: กำหนดแต่ละข้อมูลการสังเกตไปยังคลัสเตอร์ โดยเลือกคลัสเตอร์ที่จะทำให้ค่าผลบวกกำลังสองภายในคลัสเตอร์ (within-cluster sum of squares; WCSS) นั้น ๆ มีค่าน้อยที่สุด เนื่องจากผลบวกของค่ากำลังสองเป็นค่ากำลังสองของระยะทางแบบยุคลิด (Euclidean distance) มันจึงเป็นค่าเฉลี่ย “ที่ใกล้ที่สุด” (โดยทางคณิตศาสตร์ นี่เป็นการแสดงว่าการตัดแบ่งข้อมูลตามแผนภาพโวโรนอย (Voronoi diagram) นั้นแบ่งตามค่าเฉลี่ยข้างต้น)

${\displaystyle S_{i}^{(t)}={\big \{}x_{p}:{\big \|}x_{p}-m_{i}^{(t)}{\big \|}^{2}\leq {\big \|}x_{p}-m_{j}^{(t)}{\big \|}^{2}\ \forall j,1\leq j\leq k{\big \}},}$ 

โดยที่ ค่า ${\displaystyle x_{p}}$  แต่ละค่ามีแค่หนึ่งค่า ${\displaystyle S^{(t)}}$  แม้ว่าจะมีค่าที่เป็นไปได้สองค่าขึ้นไป

ขั้นตอนการปรับค่า: คำนวณค่าเฉลี่ยค่าใหม่เพื่อเป็นจุดเซนทรอยด์ (centroid) ของข้อมูลการสังเกตในแต่ละคลัสเตอร์ที่สร้างขึ้นใหม่

${\displaystyle m_{i}^{(t+1)}={\frac {1}{|S_{i}^{(t)}|}}\sum _{x_{j}\in S_{i}^{(t)}}x_{j}}$ 

ซึ่งจะทำให้ค่าผลบวกกำลังสองภายในคลัสเตอร์ใหม่นั้นมีค่าน้อยกว่าเก่า เนื่องจากว่าค่าเฉลี่ยเลขคณิตเป็นตัวประมาณค่ากำลังสองน้อยสุด

จากขั้นตอนข้างต้น ค่าที่ได้จะลู่เข้าหาค่า ๆ หนึ่งและไม่มีการเปลี่ยนแปลงในการกำหนดค่าอีก และเนื่องจากทั้งสองขั้นตอนให้ค่า WCSS ที่เหมาะที่สุด และการเลือกแบ่งกลุ่มข้อมูลมีวิธีได้จำกัด ขั้นตอนวิธีนี้จะต้องลู่เข้าหาค่า local optimum ทั้งนี้ทั้งนั้นวิธีนี้ไม่สามารถรับประกันได้ว่าจะพบค่าที่ดีที่สุดที่เป็นไปได้ หรือ global optimum ขั้นตอนวิธีนี้ถูกใช้บ่อยเพื่อการแจกแจงสิ่งของไปยังกลุ่มที่ใกล้ที่สุดด้วยระยะห่าง ขั้นตอนวิธีมาตรฐานมีจุดมุ่งหมายเพื่อทำให้ค่า WCSS มีค่าน้อยที่สุดที่เป็นไปได้ และใช้ค่ากำลังสองน้อยสุดกำหนดระยะห่าง ซึ่งก็คือ ค่ากำลังสองของระยะทางแบบยุคลิด อย่างไรก็ตาม การเลือกใช้ฟังก์ชันระยะห่างอื่น ๆ นอกเหนือไปจากค่ากำลังสองของระยะทางแบบยุคลิด อาจทำให้ขั้นตอนวิธีนี้ไม่เกิดการลู่เข้า นอกจากนี้มีการแก้ไขเพิ่มเติมของกระบวนการ (modifications of k-means) เช่น เคมีนแบบทรงกลม (spherical k-means) และ k-medoids เพื่อทำให้การคำนวณระยะห่างแบบอื่น ๆ ใช้กับขั้นตอนวิธีนี้ได้

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

โดยทั่วไปแล้ว จะใช้วิธีของ Forgy และวิธีการตัดแบ่งแบบสุ่ม (Random Partition) เป็นวิธีการกำหนดค่าตั้งต้น วิธีของ Forgy คือการเลือกข้อมูลการสังเกต k อย่างขึ้นมาแบบสุ่ม จากข้อมูลทั้งหมด แล้วใช้เป็นค่าเฉลี่ยเริ่มต้น ส่วนการตัดแบ่งข้อมูลแบบสุ่มนั้นจะเริ่มต้นด้วยการสุ่มจัดข้อมูลการสังเกตแต่ละอันไปอยู่ในกลุ่มใด ๆ และจากนั้นจะทำการปรับค่าตามขั้นตอนที่กล่าวไปแล้ว ดังนั้นค่าเฉลี่ยเริ่มต้นที่ได้จาการปรับค่าจะเป็นจุดเซนทรอยด์ (centroid) ของข้อมูลการสังเกตในแต่ละคลัสเตอร์ที่สร้างขึ้นมาแบบสุ่มนั่นเอง วิธีของ Forgy มีแนวโน้มที่จะกระจายค่าเฉลี่ยเริ่มต้น ในขณะที่การตัดแบ่งข้อมูลแบบสุ่มจะเลือกค่าเริ่มต้นที่ใกล้กับจุดกึ่งกลางของข้อมูลทั้งหมด นอกจากนี้ อ้างอิงจาก Hamerly และคณะ. การตัดแบ่งข้อมูลแบบสุ่มที่เหมาะกับขั้นตอนวิธีการหา k-harmonic means และ fuzzy k-means มากกว่า ในทางกลับกัน สำหรับขั้นตอนวิธีหาค่าคาดหมายสูงสุด หรือขั้นตอนวิธีการหาเคมีนแบบมาตรฐาน วิธีของ Forgy จะเป็นที่นิยมมากกว่า

• ภาพสาธิตของขั้นตอนวิธีมาตรฐาน
•  

  1) เลือกค่าเฉลี่ยเริ่มต้น k (ในกรณีนี้ k=3) แบบสุ่มจากโดเมนข้อมูล

•  

  2) สร้างคลัสเตอร์ k กลุ่ม โดยการเชื่อมโยงทุกข้อมูลการสังเกตด้วยค่าเฉลี่ยที่ใกล้ที่สุด เส้นแบ่งในที่นี้แสดงให้เห็นแผนภาพของโวโรนอย (Voronoi diagram) ที่สร้างขึ้นจากค่าเฉลี่ย

•  

  3) จุดเซนทรอยด์ของแต่ละคลัสเตอร์กำหนดเป็นค่าเฉลี่ยค่าใหม่

•  

  4) ทำซ้ำขั้นตอนที่ 2 และ 3 จนกระทั่งค่ากลางของแต่ละคลัสเตอร์ไม่เปลี่ยนแปลง

การที่เป็นขั้นตอนวิธีแบบศึกษาสำนึก มันจะไม่สามารถรับประกันได้ว่ากระบวนการนี้จะลู่เข้าหา global optimum และการจัดกลุ่มในตอนเริ่มต้น หรือการกำหนดค่าตั้งต้นจะมีผลอย่างมากต่อผลลัพธ์ อย่างไรก็ตามขั้นตอนวิธีนี้สามารถหาผลลัพธ์ได้อย่างรวดเร็ว จึงเป็นเรื่องปรกติที่จะทดสอบข้อมูลหลาย ๆ ครั้งด้วยเงื่อนไขเริ่มต้นที่แตกต่างกัน แต่ในกรณีที่เลวร้ายที่สุดค่าเคมีน (k-means) อาจจะลู่เข้าอย่างช้า ซึ่งมีความเป็นไปได้แม้แต่กับข้อมูลจำนวนน้อย ๆ และมีการแสดงอย่างเฉพาะเจาะจงว่า สำหรับในบางตัวอย่างข้อมูล ที่มีแค่สองมิติ การหาค่าเคมีนเป็นขั้นตอนวิธีเวลาแบบเลขชี้กำลัง (exponential time) หรือก็คือ 2^Ω(n) ในการลู่เข้า ข้อมูลดังกล่าวเหมือนว่าจะไม่เกิดขึ้นในการปฏิบัติจริง จึงสามารถยืนยันได้ว่า เวลาที่ใช้ในการทำงานที่ปรับเรียบ (smoothed running time) ของขั้นตอนการหาค่าเคมีนเป็นเป็นฟังก์ชันพหุนาม

ขั้นตอนการกำหนดค่ามีอีกชื่อหนึ่งคือ ขั้นตอนการคาดหมาย (expectation step) และขั้นตอนการปรับค่าสามารถเรียกว่า ขั้นตอนการหาค่าสูงสุด maximization step ทำให้ขั้นตอนวิธีนี้เป็นส่วนหนึ่งของขั้นตอนวิธีหาค่าคาดหมายสูงสุดแบบทั่วไป (generalized expectation-maximization algorithm)

ความซับซ้อน

เมื่อกล่าวถึงความซับซ้อนเชิงคำนวณ (computational complexity) การหาคำตอบที่เหมาะสม ในการแบ่งข้อมูลแบบเคมีนสำหรับข้อมูลการสังเกต ใน d มิติ จะเป็น

• ปัญหาเอ็นพีแบบยาก (NP-hard) ในปริภูมิแบบยุคลิดทั่วไป (Euclidean space) d แม้กระทั่งสำหรับ 2 กลุ่มข้อมูล
• ปัญหาเอ็นพีแบบยาก (NP-hard) ในปริภูมิแบบยุคลิดทั่วไป (Euclidean space) d แม้กระทั่งสำหรับ 2 กลุ่มข้อมูล สำหรับจำนวนกลุ่มข้อมูล k แม้กระทั่งในระนาบ
• ถ้ากำหนดค่า k และค่า d คงที่ จะสามารถแก้ปัญหาในเวลา ${\displaystyle O(n^{dk+1}\log {n})}$  โดยที่ค่า n เป็นจำนวนข้อมูลทั้งหมด

ดังนั้น ประเภทของขั้นตอนวิธีแบบศึกษาสำนึก เช่น ขั้นตอนวิธีของ Lloyds จึงถูกใช้อย่างแพร่หลาย เวลาที่ใช้ในการทำงานของขั้นตอนวิธีของ Lloyds จะอยู่ในรูป ${\displaystyle O(nkdi)}$  โดยที่ค่า n เป็นจำนวนของเวกเตอร์ข้อมูล ใน d มิติ ค่า k เป็นจำนวนของคลัสเตอร์ และค่า i เป็นจำนวนของการวนซ้ำจนกระทั่งผลลัพธ์ลู่เข้าและไม่เปลี่ยนแปลง สำหรับข้อมูลที่มีโครงสร้างเป็นกลุ่มก้อน การวนซ้ำในจำนวนรอบน้อย ๆ ก็มักจะเห็นการลู่เข้า และผลลัพธ์จะดีขึ้นเพียงเล็กน้อยเท่านั้นหลังจากการวนซ้ำสิบกว่าครั้ง ดังนั้นขั้นตอนวีธีของ Lloyds ในทางปฏิบัติจะระบุว่ามีความซับซ้อนแบบเชิงเส้น

ส่วนต่อจากนี้จะเป็นความรู้เพิ่มเติมล่าสุดเกี่ยวกับพฤติกรรมความซับซ้อนของขั้นตอนวิธีนี้

• ขั้นตอนวิธีการหาเคมีนของ Lloyd มีเวลาที่ใช้ในการทำงานปรับเรียบแบบพหุนาม แสดงให้เห็นว่า สำหรับเซตของ n จุดใดๆใน ${\displaystyle [0,1]^{d}}$  ถ้าแต่ละจุดจะเป็นรบกวนด้วยการแจกแจงปรกติด้วยค่าเฉลี่ย ${\displaystyle 0}$  และค่าความแปรปรวน ${\displaystyle \sigma ^{2}}$  จากนั้นเวลาที่ใช้ในการทำงานที่คาดหมายไว้ของขั้นตอนวิธีเคมีนจะอยู่ในขอบเขต ${\displaystyle O(n^{34}k^{34}d^{8}log^{4}(n)/\sigma ^{6})}$  ซึ่งจะเป็นพหุนามในรูป ${\displaystyle n}$ , ${\displaystyle k}$ , ${\displaystyle d}$  และ ${\displaystyle 1/\sigma }$ 

• นอกจากนั้นเราสามารถระบุขอบเขตที่ดีขึ้นในกรณีที่เรียบง่าย ตัวอย่างเช่น เวลาที่ใช้ในการทำงานของขั้นตอนวิธีเคมีนจะอยู่ในขอบเขต ${\displaystyle O(dn^{4}M^{2})}$  สำหรับจุดข้อมูล ${\displaystyle n}$  จุดในแลตทิชจำนวนเต็ม (integer lattice) ${\displaystyle \{1,\dots ,M\}^{d}}$ .

รูปแบบที่เปลี่ยนแปลง

• Jenks natural breaks optimization: การหาค่าเคมีนสำหรับข้อมูลตัวแปรเดียว
• k-medians clustering ใช้ค่ามัธยฐานในแต่ละมิติของข้อมูลแทนค่าเฉลี่ย และวิธีนี้จะทำให้ค่ากลาง ${\displaystyle L_{1}}$  มีค่าน้อยที่สุด (Taxicab geometry).
• k-medoids (หรือก็คือ Partitioning Around Medoids, PAM) ใช้ตัวแทนของกลุ่มที่เรียกว่า medoid แทนค่าเฉลี่ย และวิธีนี้จะทำให้ผลรวมของระยะห่างสำหรับฟังก์ชันระยะห่างใดๆให้มีค่าน้อยที่สุด
• Fuzzy c-means clustering เป็นเวอร์ชันที่ยืดหยุ่นจากการหาค่าเคมีน โดยที่แต่ละจุดข้อมูลมีดีกรีความคลุมเครือของความเป็นเจ้าของ (fuzzy degree of belonging) กับแต่ละคลัสเตอร์
• Gaussian mixture เป็นโมเดลจากขั้นตอนวิธีหาค่าคาดหมายสูงสุด (EM algorithm) ที่สนับสนุนการกำหนดค่าตามความน่าจะเป็น (probabilistic assignments) ไปยังคลัสเตอร์ แทนที่จะเป็นการกำหนดค่าชี้เฉพาะ (deterministic assignments) และใช้การแจกแจงปรกติหลายตัวแปร (multivariate Gaussian distributions) แทนที่จะเป็นค่าเฉลี่ย
• k-means++ เลือกศูนย์กลางเริ่มต้นที่ให้ค่าขอบเขตบนที่พิสูจน์ได้ในค่ากำลังสองน้อยสุด (WCCS)
• ขั้นตอนวิธีการกรองจะใช้ kd-tree ในการเร่งการหาค่าเคมีนแต่ละขั้นให้เร็วขึ้น
• บางวิธีพยายามเร่งการหาค่าเคมีนแต่ละขั้นให้เร็วขึ้นด้วย coreset หรืออสมการสามเหลี่ยม triangle inequality.
• ขั้นตอนวิธีนี้สามารถหนีจากค่าเหมาะสมที่สุดเฉพาะที่ด้วยการสลับจุดข้อมูลระหว่างคลัสเตอร์

• ขั้นตอนวิธีการแบ่งกลุ่มแบบ Spherical k-means ซึ่งเหมาะสำหรับข้อมูลที่มีทิศทาง

• Minkowski metric weighted k-means ใช้สำหรับฟีเจอร์ที่ไม่สัมพันธ์กัน โดยการกำหนดค่าน้ำหนักเฉพาะของคลัสเตอร์กับแต่ละฟีเจอร์

อภิปราย

 

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

 

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

องค์ประกอบสองอย่างที่ทำให้การแบ่งกลุ่มแบบเคมีนเป็นอัลกอริธึมที่มีประสิทธิภาพ แต่ก็มักจะถูกพิจารณว่าเป็นข้อเสียของการแบ่งกลุ่มแบบเคมีนได้แก่:

• ระยะทางแบบยูคลิดได้ถูกใช้ให้เป็นตัววัดระยะห่างระหว่างข้อมูลและความแปรปรวน (Variance) ถูกใช้เป็นตัววัดการกระจ่ายของกลุ่มข้อมูล
• จำนวนของกลุ่มของข้อมูล k เป็นตัวแปรเสริมที่ถูกนำเข้าในอัลกอริธึม: ตัวเลือกที่ไม่เหมาะสมสำหรับค่าของ k อาจจะส่งผลให้ผลลัพธ์ที่ออกมาไม่ดีนัก ดังนั้นการตรวจสอบจำนวนของกลุ่มข้อมูลที่เหมาะสมต่อข้อมูลจึงเป็นสิ่งที่สำคัญอย่างยิ่งก่อนจะเริ่มดำเนินการแบ่งกลุ่มแบบเคมีน
• การลู่เข้าถึงค่าต่ำสุดเฉพาะที่ (local minimum) อาจส่งผลให้อัลกอริธึมมอบผลลัพธ์ที่ผิดพลาดได้

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

เราสามารถมองผลลัพธ์ของการแบ่งกลุ่มแบบเคมีนได้ในรูปแบบของแผนภาพโวโรนอยของค่าเฉลี่ยกลุ่มข้อมูล เนื่องจากข้อมูลถูกแบ่งครึ่งทางระหว่างระยะห่างของจุดศุนย์กลางของกลุ่มข้อมูลแต่ละกลุ่ม ดังนั้นจึงอาจจะทำให้เกิดการแบ่งข้อมูลที่ไม่เหมาะสมอย่างที่สุดได้ (ดูตัวอย่างใน กลุ่มข้อมูล "mouse") การแจกแจงแบบปรกติ (The Gaussian model)ซึ่งใช้โดย Expectation-maximization (EM) อัลกอริธึม มีความยึดหยุ่นในการแบ่งข้อมูลเนื่องจากมีการคำนวณโดยใช้ทั้งการแปรปรวนและการแปรปรวนร่วมเกี่ยว ส่งผลให้สามารถแบ่งกลุ่มข้อมูลที่มีขนาดแตกต่างกันในแต่ละกลุ่มได้ดีกว่าการแบ่งกลุ่มแบบเคมีน

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

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

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

 

ภาพสองช่องสี (แดงและเขียว)

 

การแบ่งนับเวกเตอร์ของสีที่นำเสนอในรูปภาพสองช่องสีข้างต้น ให้อยู่ในรูปของแผนภาพโวโรนอยโดยการใช้การแบ่งกลุ่มแบบเคมีน

การแบ่งกลุ่มแบบเคมีนถูกริเริ่มขึ้นเพื่อใช้ในการประมวลสัญญาณและยังคงถูกใช้มาจนถึงในปัจจุบันนี้ ยกตัวอย่างเช่นในคอมพิวเตอร์กราฟิก, การแบ่งนับสี (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 กลุ่มโดยทำให้ค่าความคลาดเคลื่อนน้อยที่สุด จุดที่แตกต่างกันนั้นคือการที่การแบ่งกลุ่มข้อมูลแบบเคมีนดอยด์กำหนดให้ จุดศูนย์กลางของแต่ละกลุ่มข้อมูลเป็นจุดข้อมูลจริง ๆ ที่อยู่ในเซ็ตข้อมูล ไม่ใช่จุดศูนย์กลางที่ถูกคำนวณขึ้นดังเช่นในอัลกอริธึมของการแบ่งกลุ่มข้อมูลแบบเคมีน

ซอฟต์แวร์

ฟรีแวร์/โอเพ่นซอร์ส

• Apache Mahout
• Apache Spark
• CrimeStat
• ELKI
• Julia
• MLPACK (C++ library)
• R (programming language)
• SciPy
• Torch (machine learning)
• Weka (machine learning)
• OpenCV

ซอฟต์แวร์เชิงพาณิชย์

• IDL Cluster, Clust_Wts
• MATLAB
• SAS System
• Stata
• Grapheme (Data visualisation - iChrome)

อ้างอิง

1. MacQueen, J. B. (1967). Some Methods for classification and Analysis of Multivariate Observations. Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. 1. University of California Press. pp. 281–297. MR 0214227. Zbl 0214.46201. สืบค้นเมื่อ 2009-04-07.
2. Steinhaus, H. (1957). "Sur la division des corps matériels en parties". Bull. Acad. Polon. Sci. (ภาษาฝรั่งเศส). 4 (12): 801–804. MR 0090073. Zbl 0079.16403.
3. Lloyd, S. P. (1957). "Least square quantization in PCM". Bell Telephone Laboratories Paper. Published in journal much later: Lloyd., S. P. (1982). "Least squares quantization in PCM" (PDF). [[:en:IEEE_Transactions_on_Information_Theory|]]. 28 (2): 129–137. doi:10.1109/TIT.1982.1056489. สืบค้นเมื่อ 2009-04-15.
4. E.W. Forgy (1965). "Cluster analysis of multivariate data: efficiency versus interpretability of classifications". Biometrics. 21: 768–769.
5. J.A. Hartigan (1975). Clustering algorithms. John Wiley & Sons.
6. MacKay, David (2003). "Chapter 20. An Example Inference Task: Clustering" (PDF). Information Theory, Inference and Learning Algorithms. Cambridge University Press. pp. 284–292. ISBN 0-521-64298-1. MR 2012999.
7. Since the square root is a monotone function, this also is the minimum Euclidean distance assignment.
8. Hartigan, J. A.; Wong, M. A. (1979). "Algorithm AS 136: A k-Means Clustering Algorithm". Journal of the Royal Statistical Society, Series C. 28 (1): 100–108. JSTOR 2346830.
9. Hamerly, G.; Elkan, C. (2002). (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM). คลังข้อมูลเก่า เก็บจาก แหล่งเดิม (PDF) เมื่อ 2012-08-05. สืบค้นเมื่อ 2015-04-27.
10. Vattani., A. (2011). "k-means requires exponentially many iterations even in the plane" (PDF). [[:en:Discrete_&_Computational_Geometry|]]. 45 (4): 596–616. doi:10.1007/s00454-011-9340-1.
11. Arthur, D.; Manthey, B.; Roeglin, H. (2009). k-means has polynomial smoothed complexity. Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS).
12. Aloise, D.; Deshpande, A.; Hansen, P.; Popat, P. (2009). "NP-hardness of Euclidean sum-of-squares clustering". Machine Learning. 75: 245–249. doi:10.1007/s10994-009-5103-0.
13. Dasgupta, S.; Freund, Y. (July 2009). "Random Projection Trees for Vector Quantization". Information Theory, IEEE Transactions on. 55: 3229–3242. arXiv:0805.1390. doi:10.1109/TIT.2009.2021326.
14. Mahajan, M.; Nimbhorkar, P.; Varadarajan, K. (2009). "The Planar k-Means Problem is NP-Hard". [[:en:Lecture_Notes_in_Computer_Science|]]. 5431: 274–285. doi:10.1007/978-3-642-00202-1_24.
15. Inaba, M.; Katoh, N.; Imai, H. (1994). Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering. Proceedings of 10th ACM Symposium on Computational Geometry. pp. 332–339. doi:10.1145/177424.178042.
16. Chatti Subbalakshmia; P.Venkateswara Raob; S Krishna Mohan Rao (2014). "Performance Issues on K-Mean Partitioning Clustering Algorithm". International Journal of Computer (IJC). 14 (1): 41–51. ISSN 2307-4531.
17. Kanungo, T.; Mount, D. M.; Netanyahu, N. S.; Piatko, C. D.; Silverman, R.; Wu, A. Y. (2002). "An efficient k-means clustering algorithm: Analysis and implementation" (PDF). IEEE Trans. Pattern Analysis and Machine Intelligence. 24: 881–892. doi:10.1109/TPAMI.2002.1017616. สืบค้นเมื่อ 2009-04-24.
18. Frahling, G.; Sohler, C. (2006). A fast k-means implementation using coresets (PDF). Proceedings of the twenty-second annual symposium on Computational geometry (SoCG).^{[ลิงก์เสีย]}
19. Elkan, C. (2003). Using the triangle inequality to accelerate k-means (PDF). Proceedings of the Twentieth International Conference on Machine Learning (ICML).
20. Hartigan, J. A.; Wong, M. A. (1979). "Algorithm AS 136: A K-Means Clustering Algorithm". Journal of the Royal Statistical Society, Series C. 28 (1): 100–108. JSTOR 2346830.
21. Dhillon, I. S.; Modha, D. M. (2001). "Concept decompositions for large sparse text data using clustering". Machine Learning. 42 (1): 143–175.
22. Amorim, R. C.; Mirkin, B (2012). "Minkowski metric, feature weighting and anomalous cluster initializing in K-Means clustering". Pattern Recognition. 45 (3): 1061–1075. doi:10.1016/j.patcog.2011.08.012.
23. Coates, Adam; Ng, Andrew Y. (2012). "Learning feature representations with k-means" (PDF). ใน Grégoire Montavon; และคณะ (บ.ก.). Neural Networks: Tricks of the Trade. Springer. ISBN 978-3-642-35289-8.
24. Csurka, Gabriella; Dance, Christopher C.; Fan, Lixin; Willamowski, Jutta; Bray, Cédric (2004). Visual categorization with bags of keypoints (PDF). ECCV Workshop on Statistical Learning in Computer Vision.
25. Coates, Adam; Lee, Honglak; Ng, Andrew Y. (2011). (PDF). International Conference on Artificial Intelligence and Statistics (AISTATS). คลังข้อมูลเก่า เก็บจาก แหล่งเดิม (PDF) เมื่อ 2013-05-10. สืบค้นเมื่อ 2015-04-25.
26. Lin, Dekang; Wu, Xiaoyun (2009). Phrase clustering for discriminative learning (PDF). Annual Meeting of the ACL and IJCNLP. pp. 1030–1038.
27. Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 16.1. Gaussian Mixture Models and k-Means Clustering". Numerical Recipes: The Art of Scientific Computing (3 ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
28. Aharon, Michal; Elad, Michael; Bruckstein, Alfred (2006). (PDF). คลังข้อมูลเก่า เก็บจาก แหล่งเดิม (PDF) เมื่อ 2013-06-20. สืบค้นเมื่อ 2015-04-27. Cite journal requires |journal= (help)
29. Little, M.A.; Jones, N.S. (2011). "Generalized Methods and Solvers for Piecewise Constant Signals: Part I" (PDF). Proceedings of the Royal Society A.
30. H. Zha; C. Ding; M. Gu; X. He; H.D. Simon (Dec 2001). "Spectral Relaxation for K-means Clustering" (PDF). Neural Information Processing Systems vol.14 (NIPS 2001). Vancouver, Canada: 1057–1064.
31. Chris Ding; Xiaofeng He (July 2004). "K-means Clustering via Principal Component Analysis" (PDF). Proc. of Int'l Conf. Machine Learning (ICML 2004): 225–232.
32. P. Drineas; A. Frieze; R. Kannan; S. Vempala; V. Vinay (2004). "Clustering large graphs via the singular value decomposition" (PDF). Machine learning. 56: 9–33. doi:10.1023/b:mach.0000033113.59016.96. สืบค้นเมื่อ 2012-08-02.
33. M. Cohen; S. Elder; C. Musco; C. Musco; M. Persu (2014). "Dimensionality reduction for k-means clustering and low rank approximation (Appendix B)". ArXiv. สืบค้นเมื่อ 2014-11-29.
34. Vinnikov, Alon; Shalev-Shwartz, Shai (2014). "K-means Recovers ICA Filters when Independent Components are Sparse" (PDF). Proc. of Int'l Conf. Machine Learning (ICML 2014).