K-means clustering

การแบ่งกลุ่มข้อมูลแบบค่าเฉลี่ย k (อังกฤษ: k-means clustering) เป็นวิธีหนึ่งในวิธีการแบ่งเวกเตอร์ () ที่มีรากฐานมาจากการประมวลผลสัญญาณ วิธีนี้เป็นที่นิยมสำหรับการแบ่งกลุ่มข้อมูล (cluster analysis) ในการทำเหมืองข้อมูล (data mining) การแบ่งกลุ่มข้อมูลแบบค่าเฉลี่ย k ใช้สำหรับการแบ่งการสังเกตจำนวน n สิ่งเป็น k กลุ่ม โดยแต่ละการสังเกตจะอยู่ในกลุ่มที่มีค่าเฉลี่ย(ที่ใช้เป็นแม่แบบ)ใกล้เคียงกันที่สุด โดยวิธีนี้จะเป็นการแบ่งพื้นที่ข้อมูลไปเป็นแผนภาพโวโรนอย

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

ขั้นตอนวิธีนี้ไม่มีอะไรเกี่ยวข้องกับวิธีการค้นหาเพื่อนบ้านใกล้สุด (k-nearest neighbor) ซึ่งเป็นเทคนิคการเรียนรู้ของเครื่อง (machine learning) ที่เป็นที่นิยมอีกอย่างหนึ่ง

คำอธิบาย

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

${\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

ขั้นตอนวิธี

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

การลู่เข้าของค่าเฉลี่ย k

ขั้นตอนวิธีที่ใช้มากที่สุดใช้แนวทางกระทำซ้ำการกลั่นกรอง (iterative refinement approach) และถูกเรียกว่า การแบ่งกลุ่มข้อมูลแบบค่าเฉลี่ย k (k-means 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) เช่น ค่าเฉลี่ย k แบบทรงกลม (spherical k-means) และ เพื่อทำให้การคำนวณระยะห่างแบบอื่น ๆ ใช้กับขั้นตอนวิธีนี้ได้

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

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

• ภาพสาธิตของขั้นตอนวิธีมาตรฐาน
• 1) เลือกค่าเฉลี่ยเริ่มต้น k (ในกรณีนี้ k=3) แบบสุ่มจากโดเมนข้อมูล
• 2) สร้างคลัสเตอร์ k กลุ่ม โดยการเชื่อมโยงทุกข้อมูลการสังเกตด้วยค่าเฉลี่ยที่ใกล้ที่สุด เส้นแบ่งในที่นี้แสดงให้เห็นแผนภาพของโวโรนอย (Voronoi diagram) ที่สร้างขึ้นจากค่าเฉลี่ย
• 3) จุดเซนทรอยด์ของแต่ละคลัสเตอร์กำหนดเป็นค่าเฉลี่ยค่าใหม่
• 4) ทำซ้ำขั้นตอนที่ 2 และ 3 จนกระทั่งค่ากลางของแต่ละคลัสเตอร์ไม่เปลี่ยนแปลง

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

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

ความซับซ้อน

เมื่อกล่าวถึงความซับซ้อนเชิงคำนวณ (computational complexity) การหาคำตอบที่เหมาะสม ในการแบ่งข้อมูลแบบค่าเฉลี่ย k สำหรับข้อมูลการสังเกต ใน 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 ในทางปฏิบัติจะระบุว่ามีความซับซ้อนแบบเชิงเส้น

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

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

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

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

• : การหาค่าค่าเฉลี่ย k สำหรับข้อมูลตัวแปรเดียว
• ใช้ค่ามัธยฐานในแต่ละมิติของข้อมูลแทนค่าเฉลี่ย และวิธีนี้จะทำให้ค่ากลาง ${\displaystyle L_{1}}$ มีค่าน้อยที่สุด ()
• (หรือก็คือ Partitioning Around Medoids, PAM) ใช้ตัวแทนของกลุ่มที่เรียกว่า medoid แทนค่าเฉลี่ย และวิธีนี้จะทำให้ผลรวมของระยะห่างสำหรับฟังก์ชันระยะห่างใด ๆ ให้มีค่าน้อยที่สุด
• เป็นเวอร์ชันที่ยืดหยุ่นจากการหาค่าเฉลี่ย k โดยที่แต่ละจุดข้อมูลมีดีกรีความคลุมเครือของความเป็นเจ้าของ (fuzzy degree of belonging) กับแต่ละคลัสเตอร์
• เป็นโมเดลจากขั้นตอนวิธีหาค่าคาดหมายสูงสุด (EM algorithm) ที่สนับสนุนการกำหนดค่าตามความน่าจะเป็น (probabilistic assignments) ไปยังคลัสเตอร์ แทนที่จะเป็นการกำหนดค่าชี้เฉพาะ (deterministic assignments) และใช้การแจกแจงปรกติหลายตัวแปร (multivariate Gaussian distributions) แทนที่จะเป็นค่าเฉลี่ย
• เลือกศูนย์กลางเริ่มต้นที่ให้ค่าขอบเขตบนที่พิสูจน์ได้ในค่ากำลังสองน้อยสุด (WCCS)
• ขั้นตอนวิธีการกรองจะใช้ ในการเร่งการหาค่าเฉลี่ย k แต่ละขั้นให้เร็วขึ้น
• บางวิธีพยายามเร่งการหาค่าเฉลี่ย k แต่ละขั้นให้เร็วขึ้นด้วย หรืออสมการสามเหลี่ยม
• ขั้นตอนวิธีนี้สามารถหนีจากค่าเหมาะสมที่สุดเฉพาะที่ด้วยการสลับจุดข้อมูลระหว่างคลัสเตอร์

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

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

อภิปราย

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

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

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

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

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

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

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

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

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

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

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

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

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

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

การเรียนรู้ลักษณะเฉพาะ (Feature learning)

การแบ่งกลุ่มข้อมูลแบบค่าเฉลี่ย k ได้ถูกนำไปใช้ในขั้นตอนฟีเจอร์เลิร์นนิ่ง (Feature learning) ทั้งในการเรียนรู้แบบมีผู้สอน (supervised learning) การเรียนรู้แบบกึ่งมีผู้สอน (semi-supervised learning) และการเรียนรู้แบบไม่มีผู้สอน (unsupervised learning) ขั้นตอนในการปฏิบัติเริ่มจากการสร้างกลุ่มข้อมูลจำนวน k กลุ่มด้วยการแบ่งกลุ่มข้อมูลแบบค่าเฉลี่ย k โดยใช้ข้อมูลสอน (training data) หลังจากนั้นจึงโปรเจกต์ข้อมูลอินพุตไปยังฟีเจอร์สเปซใหม่ โดยใช้แมทริกส์โปรดัคระหว่างข้อมูลและตำแหน่งของศูนย์กลางของแต่ละกลุ่มข้อมูล ระยะห่างระหว่างข้อมูลอินพุตและศูนย์กลางของแต่ละกลุ่มข้อมูล ฟังก์ชันที่ชี้ข้อมูลอินพุตถึงจุดศูนย์กลางของกลุ่มข้อมูลที่ใกล้ที่สุด หรือสมูทฟังก์ชันของระยะห่างระหว่างข้อมูลและศูนย์กลางของกลุ่มข้อมูลเป็นต้น

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

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

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

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

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

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

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

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

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

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

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

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

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

ซอฟต์แวร์

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

• Apache Mahout
• Apache Spark
• CrimeStat
• ELKI
• Julia
• MLPACK (ไลบรารีภาษา C++)
• R (ภาษาโปรแกรม)
• SciPy
• Torch (การเรียนรู้ของเครื่อง)
• Weka (การเรียนรู้ของเครื่อง)
• 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. Vol. 1. University of California Press. pp. 281–297.  0214227.  0214.46201. สืบค้นเมื่อ 2009-04-07.
2. (1957). "Sur la division des corps matériels en parties". Bull. Acad. Polon. Sci. (ภาษาฝรั่งเศส). 4 (12): 801–804.  0090073.  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). . 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. (2003). "Chapter 20. An Example Inference Task: Clustering" (PDF). Information Theory, Inference and Learning Algorithms. Cambridge University Press. pp. 284–292. ISBN .  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". . 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)เมื่อ 5 สิงหาคม 2012. สืบค้นเมื่อ 27 เมษายน 2015.
10. Vattani., A. (2011). "k-means requires exponentially many iterations even in the plane" (PDF). . 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". . 75: 245–249. doi:10.1007/s10994-009-5103-0.
13. Dasgupta, S.; Freund, Y. (กรกฎาคม 2009). "Random Projection Trees for Vector Quantization". Information Theory, IEEE Transactions on. 55: 3229–3242. :0805.1390. doi:10.1109/TIT.2009.2021326.
14. Mahajan, M.; Nimbhorkar, P.; Varadarajan, K. (2009). "The Planar k-Means Problem is NP-Hard". . 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. . 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.; ; ; 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. Gereon Frahling; Christian Sohler (5 ธันวาคม 2005). A fast k-means implementation using coresets (PDF). . S2CID 5891336.
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". . 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). (PDF). ใน Grégoire Montavon; และคณะ (บ.ก.). Neural Networks: Tricks of the Trade. Springer. ISBN . คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 6 มิถุนายน 2013. สืบค้นเมื่อ 25 เมษายน 2015.
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)เมื่อ 10 พฤษภาคม 2013. สืบค้นเมื่อ 25 เมษายน 2015.
26. Lin, Dekang; Wu, Xiaoyun (2009). Phrase clustering for discriminative learning (PDF). Annual Meeting of the 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". (3 ed.). New York: Cambridge University Press. ISBN . คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2011-08-11. สืบค้นเมื่อ 2015-04-27.
28. Aharon, Michal; Elad, Michael; Bruckstein, Alfred (พฤศจิกายน 2006). (PDF). IEEE Transactions on Signal Processing. 54 (11): 4311–22. คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 20 มิถุนายน 2013. สืบค้นเมื่อ 27 เมษายน 2015.
29. Little, M.A.; Jones, N.S. (2011). (PDF). . คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2019-08-19. สืบค้นเมื่อ 2015-04-27.
30. H. Zha; C. Ding; M. Gu; X. He; H.D. Simon (ธันวาคม 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 (กรกฎาคม 2004). K-means Clustering via Principal Component Analysis (PDF). Proc. of Int'l Conf. Machine Learning (ICML 2004). pp. 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. สืบค้นเมื่อ 2 สิงหาคม 2012.
33. M. Cohen; S. Elder; C. Musco; C. Musco; M. Persu (2014). "Dimensionality reduction for k-means clustering and low rank approximation (Appendix B)". :1410.6801v3.
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) (ภาษาอังกฤษ).

แหล่งข้อมูลอื่น

• วิกิมีเดียคอมมอนส์มีสื่อเกี่ยวกับ K-means algorithm