ดูต้นฉบับสำหรับ การจับกลุ่มข้อมูลแบบค่าเฉลี่ย k

{{Machine learning bar}}
'''การจับกลุ่มข้อมูลแบบค่าเฉลี่ย k''' ({{langx|en|<i>k</i>-means clustering}}) เป็นวิธีหนึ่งในวิธีการแบ่งเวกเตอร์ที่มีรากฐานมาจาก[[การประมวลผลสัญญาณ]] วิธีนี้เป็นที่นิยมสำหรับ[[การจับกลุ่มข้อมูล]]ใน[[การทำเหมืองข้อมูล]] การจับกลุ่มข้อมูลแบบค่าเฉลี่ย k ใช้สำหรับการแบ่งการสังเกตจำนวน n สิ่งเป็น k กลุ่ม โดยแต่ละการสังเกตจะอยู่ในกลุ่มที่มีค่าเฉลี่ย(ที่ใช้เป็นแม่แบบ)ใกล้เคียงกันที่สุด โดยวิธีนี้จะเป็นการแบ่งพื้นที่ข้อมูลไปเป็น[[แผนภาพโวโรนอย]]

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

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

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

<math>\underset{\mathbf{S}} {\operatorname{arg\,min}}  \sum_{i=1}^{k} \sum_{\mathbf x \in S_i} \left\| \mathbf x - \boldsymbol\mu_i \right\|^2 </math>

โดยที่ '''''μ'''''<sub>''i''</sub> เป็นค่าเฉลี่ยของจุดใน ''S''<sub>''i''</sub>

==  ประวัติ ==
คำศัพท์ "''k''-means" ได้ถูกระบุใช้ครั้งแรกโดย James MacQueen ในปี พ.ศ. 2510,<ref name="macqueen1967">{{cite conference
 |first=J. B. |last=MacQueen
 |year=1967
 |title=Some Methods for classification and Analysis of Multivariate Observations
 |url=http://projecteuclid.org/euclid.bsmsp/1200512992 |access-date=2009-04-07
 |conference=Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability
 |publisher=University of California Press
 |volume=1 |pages=281–297
 |mr=0214227
 |zbl=0214.46201
}}</ref> แม้ว่าแนวคิดเริ่มแรกจะเป็นของ Hugo Steinhaus ซึ่งเกิดขึ้นในปี พ.ศ. 2500<ref>{{cite journal
 |first=H. |last=Steinhaus |authorlink=Hugo Steinhaus
 |title=Sur la division des corps matériels en parties
 |journal=Bull. Acad. Polon. Sci.
 |volume=4 |issue=12 |pages=801–804
 |year=1957
 |mr=0090073
 |zbl=0079.16403 |language=fr
}}</ref> และขั้นตอนวิธีมาตรฐานนั้นก็ถูกเสนอขึ้นในปี พ.ศ. 2500 โดย Stuart Lloyd เพื่อเป็นเทคนิคสำหรับ[[การกล้ำรหัสของพัลส์]] อย่างไรก็ตามขั้นตอนวิธีไม่ได้ถูกเผยแพร่ออกไปจาก Bell Labs จนกระทั่งปี พ.ศ. 2525<ref name="lloyd1957">{{cite journal
 |first=S. P. |last=Lloyd
 |title=Least square quantization in PCM
 |journal=Bell Telephone Laboratories Paper
 |year=1957
}} Published in journal much later:
{{cite journal
 |first=S. P. |last=Lloyd.
 |url=http://www.cs.toronto.edu/~roweis/csc2515-2006/readings/lloyd57.pdf |access-date=2009-04-15
 |title=Least squares quantization in PCM
 |journal=[[IEEE Transactions on Information Theory]]
 |volume=28 |issue=2 |pages=129–137
 |year=1982
 |doi=10.1109/TIT.1982.1056489
}}</ref> ในปี พ.ศ. 2508 E.W.Forgy ได้ตีพิมพ์วิธีเดียวกันนี้เช่นกัน จึงทำให้บางครั้งวิธีนี้ถูกกล่าวถึงในชื่อ Lloyd-Forgy<ref name="forgy65">{{Cite journal
 |author=E.W. Forgy
 |title=Cluster analysis of multivariate data: efficiency versus interpretability of classifications
 |url=https://archive.org/details/sim_biometrics_1965-09_21_3/page/768
 |journal=Biometrics
 |volume=21
 |pages=768–769
 |year=1965}}</ref> นอกจากนี้ได้มีการตีพิมพ์แบบฉบับที่มีการพัฒนาขึ้นไป โดย Hartigan and Wong ในปี พ.ศ. 2518 / 2522<ref name="hartigan1975">{{Cite book
 |title=Clustering algorithms
 |author=J.A. Hartigan
 |year=1975
 |publisher=John Wiley & Sons
}}</ref>

== ขั้นตอนวิธี ==
=== ขั้นตอนวิธีมาตรฐาน ===
[[ไฟล์:K-means_convergence.gif|right|thumb|การลู่เข้าของค่าเฉลี่ย k]]
ขั้นตอนวิธีที่ใช้มากที่สุดใช้แนวทางกระทำซ้ำการกลั่นกรอง (iterative refinement approach) และถูกเรียกว่า การจับกลุ่มข้อมูลแบบค่าเฉลี่ย k ('''''k''-means algorithm''') หรือในบางครั้งสามารถพบในชื่อ '''[[Lloyd's algorithm]]''' โดยเฉพาะในวงการวิทยาการคอมพิวเตอร์
เริ่มด้วยเซตเริ่มต้นประกอบด้วยค่าเฉลี่ย ''k'' ค่า ''m''<sub>1</sub><sup>(1)</sup>,…,''m''<sub>''k''</sub><sup>(1)</sup> แล้วจากนั้นจะเป็นการทำซ้ำระหว่างสองขั้นตอน<ref>{{Cite book
  | last =MacKay
  | first =David
  | authorlink =David MacKay (scientist)
  | title =Information Theory, Inference and Learning Algorithms
  | publisher = Cambridge University Press
  | year =2003
  | url =http://www.inference.phy.cam.ac.uk/mackay/itila/book.html
  | isbn = 0-521-64298-1
  | chapter=Chapter 20. An Example Inference Task: Clustering
  | chapter-url=http://www.inference.phy.cam.ac.uk/mackay/itprnn/ps/284.292.pdf
  | pages=284–292
  | ref=mackay2003
  | mr=2012999
}}</ref>
:'''ขั้นตอนการกำหนดค่า''': กำหนดแต่ละข้อมูลการสังเกตไปยังคลัสเตอร์ โดยเลือกคลัสเตอร์ที่จะทำให้ค่าผลบวกกำลังสองภายในคลัสเตอร์ (within-cluster sum of squares; WCSS) นั้น ๆ มีค่าน้อยที่สุด เนื่องจากผลบวกของค่ากำลังสองเป็นค่ากำลังสองของระยะทางแบบยุคลิด (Euclidean distance) มันจึงเป็นค่าเฉลี่ย “ที่ใกล้ที่สุด”<ref>Since the square root is a monotone function, this also is the minimum Euclidean distance assignment.</ref> (โดยทางคณิตศาสตร์  นี่เป็นการแสดงว่าการตัดแบ่งข้อมูลตาม[[แผนภาพโวโรนอย]] (Voronoi diagram) นั้นแบ่งตามค่าเฉลี่ยข้างต้น)
<math>S_i^{(t)} = \big \{ x_p : \big \| x_p - m^{(t)}_i \big \|^2 \le \big \| x_p - m^{(t)}_j \big \|^2 \ \forall j, 1 \le j \le k \big\},</math>
:: โดยที่ ค่า <math>x_p</math> แต่ละค่ามีแค่หนึ่งค่า <math>S^{(t)}</math> แม้ว่าจะมีค่าที่เป็นไปได้สองค่าขึ้นไป
:'''ขั้นตอนการปรับค่า''': คำนวณค่าเฉลี่ยค่าใหม่เพื่อเป็นจุดเซนทรอยด์ (centroid) ของข้อมูลการสังเกตในแต่ละคลัสเตอร์ที่สร้างขึ้นใหม่
<math>m^{(t+1)}_i = \frac{1}{|S^{(t)}_i|} \sum_{x_j \in S^{(t)}_i} x_j </math>
:: ซึ่งจะทำให้ค่าผลบวกกำลังสองภายในคลัสเตอร์ใหม่นั้นมีค่าน้อยกว่าเก่า เนื่องจากว่าค่าเฉลี่ยเลขคณิตเป็นตัวประมาณค่ากำลังสองน้อยสุด
จากขั้นตอนข้างต้น ค่าที่ได้จะลู่เข้าหาค่าค่าหนึ่งและไม่มีการเปลี่ยนแปลงในการกำหนดค่าอีก และเนื่องจากทั้งสองขั้นตอนให้ค่า WCSS ที่เหมาะที่สุด และการเลือกแบ่งกลุ่มข้อมูลมีวิธีได้จำกัด ขั้นตอนวิธีนี้จะต้องลู่เข้าหาค่า local optimum ทั้งนี้ทั้งนั้นวิธีนี้ไม่สามารถรับประกันได้ว่าจะพบค่าที่ดีที่สุดที่เป็นไปได้ หรือ global optimum<ref name="hartigan19792">{{Cite journal |last1=Hartigan |first1=J. A. |last2=Wong |first2=M. A. |year=1979 |title=Algorithm AS 136: A ''k''-Means Clustering Algorithm |journal=[[Journal_of_the_Royal_Statistical_Society#Journal_of_the_Royal_Statistical_Society,_Series_C_(Applied_Statistics)|Journal of the Royal Statistical Society, Series C]] |volume=28 |issue=1 |pages=100–108 |jstor=2346830 }}</ref>
ขั้นตอนวิธีนี้ถูกใช้บ่อยเพื่อการแจกแจงสิ่งของไปยังกลุ่มที่ใกล้ที่สุดด้วยระยะห่าง ขั้นตอนวิธีมาตรฐานมีจุดมุ่งหมายเพื่อทำให้ค่า WCSS มีค่าน้อยที่สุดที่เป็นไปได้ และใช้ค่ากำลังสองน้อยสุดกำหนดระยะห่าง ซึ่งก็คือ ค่ากำลังสองของระยะทางแบบยุคลิด อย่างไรก็ตาม การเลือกใช้ฟังก์ชันระยะห่างอื่น ๆ นอกเหนือไปจากค่ากำลังสองของระยะทางแบบยุคลิด อาจทำให้ขั้นตอนวิธีนี้ไม่เกิดการลู่เข้า นอกจากนี้มีการแก้ไขเพิ่มเติมของกระบวนการ (modifications of k-means) เช่น ค่าเฉลี่ย k แบบทรงกลม (spherical k-means) และ [[k-medoids]] เพื่อทำให้การคำนวณระยะห่างแบบอื่น ๆ ใช้กับขั้นตอนวิธีนี้ได้

==== วิธีการกำหนดค่าตั้งต้น ====
โดยทั่วไปแล้ว จะใช้วิธีของ Forgy และวิธีการตัดแบ่งแบบสุ่ม (Random Partition<ref name="hamerly">{{Cite conference
 |author1=Hamerly, G.
 |author2=Elkan, C.
 |year=2002
 |title=Alternatives to the k-means algorithm that find better clusterings
 |conference=Proceedings of the eleventh international conference on Information and knowledge management (CIKM)
 |url=http://charlotte.ucsd.edu/users/elkan/cikm02.pdf
 |access-date=2015-04-27
 |archive-date=2012-08-05
 |archive-url=https://web.archive.org/web/20120805022051/http://charlotte.ucsd.edu/users/elkan/cikm02.pdf
 |url-status=dead
 |df=dmy-all
 }}</ref>) เป็นวิธีการกำหนดค่าตั้งต้น
วิธีของ Forgy คือการเลือกข้อมูลการสังเกต ''k'' อย่างขึ้นมาแบบสุ่ม จากข้อมูลทั้งหมด แล้วใช้เป็นค่าเฉลี่ยเริ่มต้น ส่วนการตัดแบ่งข้อมูลแบบสุ่มนั้นจะเริ่มต้นด้วยการสุ่มจัดข้อมูลการสังเกตแต่ละอันไปอยู่ในกลุ่มใด ๆ และจากนั้นจะทำการปรับค่าตามขั้นตอนที่กล่าวไปแล้ว ดังนั้นค่าเฉลี่ยเริ่มต้นที่ได้จาการปรับค่าจะเป็นจุดเซนทรอยด์ (centroid) ของข้อมูลการสังเกตในแต่ละคลัสเตอร์ที่สร้างขึ้นมาแบบสุ่มนั่นเอง วิธีของ Forgy มีแนวโน้มที่จะกระจายค่าเฉลี่ยเริ่มต้น ในขณะที่การตัดแบ่งข้อมูลแบบสุ่มจะเลือกค่าเริ่มต้นที่ใกล้กับจุดกึ่งกลางของข้อมูลทั้งหมด นอกจากนี้ อ้างอิงจาก Hamerly และคณะ<ref name="hamerly" /> การตัดแบ่งข้อมูลแบบสุ่มที่เหมาะกับขั้นตอนวิธีการหา ''k''-harmonic means และ fuzzy ''k''-means มากกว่า ในทางกลับกัน สำหรับขั้นตอนวิธีหาค่าคาดหมายสูงสุด หรือขั้นตอนวิธีการหาค่าเฉลี่ย k แบบมาตรฐาน วิธีของ Forgy จะเป็นที่นิยมมากกว่า
<gallery caption="ภาพสาธิตของขั้นตอนวิธีมาตรฐาน" widths="150px">
ไฟล์:K Means Example Step 1.svg|1) เลือกค่าเฉลี่ยเริ่มต้น ''k'' (ในกรณีนี้ ''k''=3) แบบสุ่มจากโดเมนข้อมูล
ไฟล์:K Means Example Step 2.svg|2) สร้างคลัสเตอร์ ''k'' กลุ่ม โดยการเชื่อมโยงทุกข้อมูลการสังเกตด้วยค่าเฉลี่ยที่ใกล้ที่สุด เส้นแบ่งในที่นี้แสดงให้เห็นแผนภาพของโวโรนอย (Voronoi diagram) ที่สร้างขึ้นจากค่าเฉลี่ย
ไฟล์:K Means Example Step 3.svg|3) จุดเซนทรอยด์ของแต่ละคลัสเตอร์กำหนดเป็นค่าเฉลี่ยค่าใหม่
ไฟล์:K Means Example Step 4.svg|4) ทำซ้ำขั้นตอนที่ 2 และ 3 จนกระทั่งค่ากลางของแต่ละคลัสเตอร์ไม่เปลี่ยนแปลง
</gallery>

เนื่องจากเป็นขั้นตอนวิธีแบบ[[ศึกษาสำนึก]] จึงไม่สามารถรับประกันได้ว่ากระบวนการนี้จะลู่เข้าหา global optimum และการจัดกลุ่มในตอนเริ่มต้น หรือการกำหนดค่าตั้งต้นจะมีผลอย่างมากต่อผลลัพธ์ อย่างไรก็ตามขั้นตอนวิธีนี้สามารถหาผลลัพธ์ได้อย่างรวดเร็ว จึงเป็นเรื่องปรกติที่จะทดสอบข้อมูลหลาย ๆ ครั้งด้วยเงื่อนไขเริ่มต้นที่แตกต่างกัน แต่ในกรณีที่เลวร้ายที่สุดค่าเฉลี่ย k (''k''-means) อาจจะลู่เข้าอย่างช้า ซึ่งมีความเป็นไปได้แม้แต่กับข้อมูลจำนวนน้อย ๆ และมีการแสดงอย่างเฉพาะเจาะจงว่า สำหรับในบางตัวอย่างข้อมูล ที่มีแค่สองมิติ การหาค่าเฉลี่ย k เป็นขั้นตอนวิธีเวลาแบบเลขชี้กำลัง (exponential time) หรือก็คือ {{math|2<sup>Ω(<var>n</var>)</sup>}} ในการลู่เข้า<ref>{{cite journal
 |first=A. |last=Vattani.
 |url=http://cseweb.ucsd.edu/users/avattani/papers/kmeans-journal.pdf
 |title=k-means requires exponentially many iterations even in the plane
 |journal=[[Discrete_%26_Computational_Geometry|Discrete & Computational Geometry]]
 |volume=45 |issue=4 |pages=596–616
 |year=2011
 |doi=10.1007/s00454-011-9340-1
}}</ref> ข้อมูลดังกล่าวเหมือนว่าจะไม่เกิดขึ้นในการปฏิบัติจริง จึงสามารถยืนยันได้ว่า เวลาที่ใช้ในการทำงานที่ปรับเรียบ ([[Smoothed analysis|smoothed]] running time) ของขั้นตอนการหาค่าเฉลี่ย k เป็นเป็นฟังก์ชันพหุนาม<ref name="Arthur, D.; Manthey, B.; Roeglin, H. 2009">{{cite conference | author1=Arthur, D.|author2=Manthey, B.|author3=Roeglin, H. | year=2009 | title=k-means has polynomial smoothed complexity | conference=Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS)}}</ref>

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

=== ความซับซ้อน ===
เมื่อกล่าวถึงความซับซ้อนเชิงคำนวณ (computational complexity) การหาคำตอบที่เหมาะสม ในการแบ่งข้อมูลแบบค่าเฉลี่ย k สำหรับข้อมูลการสังเกต ใน ''d'' มิติ จะเป็น
*ปัญหา[[เอ็นพี]]แบบยาก (NP-hard) ในปริภูมิแบบยุคลิดทั่วไป (Euclidean space) ''d'' แม้กระทั่งสำหรับ 2 กลุ่มข้อมูล<ref>{{cite journal
 |author1=Aloise, D.|author2=Deshpande, A.|author3=Hansen, P.|author4=Popat, P.
 |title=NP-hardness of Euclidean sum-of-squares clustering
 |journal=[[Machine_Learning_(journal)|Machine Learning]]
 |year=2009
 |volume=75 |pages=245–249
 |doi=10.1007/s10994-009-5103-0}}</ref><ref>
{{cite journal
 |title=Random Projection Trees for Vector Quantization
 |author1=Dasgupta, S.|author2=Freund, Y.
 |journal=Information Theory, IEEE Transactions on
 |volume=55
 |pages=3229–3242
 |date=July 2009
 |doi=10.1109/TIT.2009.2021326
 |arxiv=0805.1390
 |df=dmy-all}}
</ref>
*ปัญหา[[เอ็นพี]]แบบยาก (NP-hard) ในปริภูมิแบบยุคลิดทั่วไป (Euclidean space) ''d'' แม้กระทั่งสำหรับ 2 กลุ่มข้อมูล สำหรับจำนวนกลุ่มข้อมูล ''k'' แม้กระทั่งในระนาบ<ref>{{cite journal
 |author1=Mahajan, M.|author2=Nimbhorkar, P.|author3=Varadarajan, K.
 |title=The Planar k-Means Problem is NP-Hard
 |journal=[[Lecture Notes in Computer Science]]
 |year=2009
 |volume=5431 |pages=274–285
 |doi=10.1007/978-3-642-00202-1_24}}
</ref>
*ถ้ากำหนดค่า ''k'' และค่า ''d'' คงที่ จะสามารถแก้ปัญหาในเวลา <math>O(n^{dk+1}\log{n})</math> โดยที่ค่า ''n'' เป็นจำนวนข้อมูลทั้งหมด<ref>
{{cite conference
 |author1=Inaba, M.|author2=Katoh, N.|author3=Imai, H.
 |year=1994
 |title=Applications of weighted Voronoi diagrams and randomization to variance-based ''k''-clustering
 |conference=[[Symposium_on_Computational_Geometry|Proceedings of 10th ACM Symposium on Computational Geometry]]
 |pages=332–339
 |doi= 10.1145/177424.178042}}
</ref>
ดังนั้น ประเภทของขั้นตอนวิธีแบบ[[ศึกษาสำนึก]] เช่น ขั้นตอนวิธีของ Lloyds จึงถูกใช้อย่างแพร่หลาย
เวลาที่ใช้ในการทำงานของขั้นตอนวิธีของ Lloyds จะอยู่ในรูป <math>O(n k d i)</math> โดยที่ค่า ''n'' เป็นจำนวนของเวกเตอร์ข้อมูล ใน ''d'' มิติ ค่า ''k'' เป็นจำนวนของคลัสเตอร์ และค่า ''i'' เป็นจำนวนของการวนซ้ำจนกระทั่งผลลัพธ์ลู่เข้าและไม่เปลี่ยนแปลง สำหรับข้อมูลที่มีโครงสร้างเป็นกลุ่มก้อน การวนซ้ำในจำนวนรอบน้อย ๆ ก็มักจะเห็นการลู่เข้า และผลลัพธ์จะดีขึ้นเพียงเล็กน้อยเท่านั้นหลังจากการวนซ้ำสิบกว่าครั้ง ดังนั้นขั้นตอนวีธีของ Lloyds ในทางปฏิบัติจะระบุว่ามีความซับซ้อนแบบเชิงเส้น

ส่วนต่อจากนี้จะเป็นความรู้เพิ่มเติมล่าสุดเกี่ยวกับพฤติกรรมความซับซ้อนของขั้นตอนวิธีนี้ 
* ขั้นตอนวิธีการหาค่าเฉลี่ย k ของ Lloyd มีเวลาที่ใช้ในการทำงานปรับเรียบแบบพหุนาม แสดงให้เห็นว่า <ref name="Arthur, D.; Manthey, B.; Roeglin, H. 2009" /> สำหรับเซตของ ''n'' จุดใด ๆ ใน <math>[0,1]^d</math> ถ้าแต่ละจุดจะเป็นรบกวนด้วยการแจกแจงปรกติด้วยค่าเฉลี่ย <math>0</math> และค่าความแปรปรวน <math>\sigma^2</math> จากนั้นเวลาที่ใช้ในการทำงานที่คาดหมายไว้ของขั้นตอนวิธีค่าเฉลี่ย k จะอยู่ในขอบเขต <math>O( n^{34}k^{34}d^8 log^4(n)/ \sigma^6 )</math> ซึ่งจะเป็นพหุนามในรูป <math>n</math>, <math>k</math>, <math>d</math> และ <math>1/\sigma</math>

* นอกจากนั้นเราสามารถระบุขอบเขตที่ดีขึ้นในกรณีที่เรียบง่าย ตัวอย่างเช่น<ref>{{Cite journal|author1=Chatti Subbalakshmia|author2=P. Venkateswara Raob|author3=S. Krishna Mohan Rao|title=Performance Issues on K-Mean Partitioning Clustering Algorithm|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1011.7339&rep=rep1&type=pdf|journal=International Journal of Computer (IJC)|date=2014|volume=14|number=1|pages=41–51|issn=2307-4531}}</ref> เวลาที่ใช้ในการทำงานของขั้นตอนวิธีค่าเฉลี่ย k จะอยู่ในขอบเขต <math>O(dn^4M^2)</math> สำหรับจุดข้อมูล <math>n</math> จุดในแลตทิชจำนวนเต็ม (integer lattice) <math>\{1,\dots, M\}^d</math>

=== รูปแบบที่เปลี่ยนแปลง ===
* [[Jenks natural breaks optimization]]: การหาค่าค่าเฉลี่ย k สำหรับข้อมูลตัวแปรเดียว
* [[k-medians clustering]] ใช้ค่ามัธยฐานในแต่ละมิติของข้อมูลแทนค่าเฉลี่ย และวิธีนี้จะทำให้ค่ากลาง <math>L_1</math> มีค่าน้อยที่สุด ([[Taxicab geometry]])
* [[k-medoids]] (หรือก็คือ Partitioning Around Medoids, PAM) ใช้ตัวแทนของกลุ่มที่เรียกว่า medoid แทนค่าเฉลี่ย และวิธีนี้จะทำให้ผลรวมของระยะห่างสำหรับฟังก์ชันระยะห่างใด ๆ ให้มีค่าน้อยที่สุด
* [[Fuzzy_clustering#Fuzzy_c-means_clustering|Fuzzy c-means clustering]] เป็นเวอร์ชันที่ยืดหยุ่นจากการหาค่าเฉลี่ย k โดยที่แต่ละจุดข้อมูลมีดีกรีความคลุมเครือของความเป็นเจ้าของ (fuzzy degree of belonging) กับแต่ละคลัสเตอร์
* [[Mixture_model#Gaussian_mixture_model|Gaussian mixture]] เป็นแบบจำลองจากขั้นตอนวิธีหาค่าคาดหมายสูงสุด (EM algorithm) ที่สนับสนุนการกำหนดค่าตามความน่าจะเป็น (probabilistic assignments) ไปยังคลัสเตอร์ แทนที่จะเป็นการกำหนดค่าชี้เฉพาะ (deterministic assignments) และใช้การแจกแจงปรกติหลายตัวแปร (multivariate Gaussian distributions) แทนที่จะเป็นค่าเฉลี่ย
* [[K-means%2B%2B|k-means++]] เลือกศูนย์กลางเริ่มต้นที่ให้ค่าขอบเขตบนที่พิสูจน์ได้ในค่ากำลังสองน้อยสุด (WCCS)
* ขั้นตอนวิธีการกรองจะใช้ [[K-d_tree|kd-tree]] ในการเร่งการหาค่าเฉลี่ย k แต่ละขั้นให้เร็วขึ้น<ref>{{cite journal|author1=Kanungo, T.|author2=[[David_Mount|Mount, D. M.]]|author3=[[Nathan_Netanyahu|Netanyahu, N. S.]]|author4=Piatko, C. D.|author5=Silverman, R.|author6=Wu, A. Y.|doi=10.1109/TPAMI.2002.1017616|url=http://www.cs.umd.edu/~mount/Papers/pami02.pdf|access-date=2009-04-24|title=An efficient k-means clustering algorithm: Analysis and implementation|journal=IEEE Trans. Pattern Analysis and Machine Intelligence|volume=24|year=2002|pages=881–892|archive-date=2009-10-07|archive-url=https://web.archive.org/web/20091007160354/http://www.cs.umd.edu/~mount/Papers/pami02.pdf|url-status=dead}}</ref>
* บางวิธีพยายามเร่งการหาค่าเฉลี่ย k แต่ละขั้นให้เร็วขึ้นด้วย [[coreset]]<ref>{{Cite conference
 |author1=Gereon Frahling
 |author2=Christian Sohler
 |date=5 December 2005
 |title=A fast k-means implementation using coresets
 |conference=[[Symposium_on_Computational_Geometry|Proceedings of the twenty-second annual symposium on Computational geometry (SoCG)]]
 |url=http://static.googleusercontent.com/media/research.google.com/en/us/pubs/archive/33320.pdf
 |s2cid=5891336
 |df=dmy-all
 }}</ref> หรืออสมการสามเหลี่ยม [[triangle inequality]]<ref>{{Cite conference
 |author = Elkan, C.
 |year=2003
 |title=Using the triangle inequality to accelerate k-means
 |conference=Proceedings of the Twentieth International Conference on Machine Learning (ICML)
 |url=http://www-cse.ucsd.edu/~elkan/kmeansicml03.pdf
}}</ref>
* ขั้นตอนวิธีนี้สามารถหนีจากค่าเหมาะสมที่สุดเฉพาะที่ด้วยการสลับจุดข้อมูลระหว่างคลัสเตอร์<ref name="hartigan1979">{{Cite journal
 | first1 = J. A. |last1 = Hartigan
 | first2 = M. A. |last2 = Wong
 | year = 1979
 | title =  Algorithm AS 136: A K-Means Clustering Algorithm
 | journal = [[Journal_of_the_Royal_Statistical_Society#Journal_of_the_Royal_Statistical_Society,_Series_C_(Applied_Statistics)|Journal of the Royal Statistical Society, Series C]]
 | volume = 28
 | issue = 1
 | pages = 100–108
 | jstor = 2346830
}}</ref>

* ขั้นตอนวิธีการแบ่งกลุ่มแบบ [[Spherical k-means]] ซึ่งเหมาะสำหรับข้อมูลที่มีทิศทาง<ref>{{Cite journal
 | first1 = I. S. |last1 = Dhillon
 | first2 = D. M. |last2 = Modha
 | year = 2001
 | title =  Concept decompositions for large sparse text data using clustering
 | journal = Machine Learning
 | volume = 42
 | issue = 1
 | pages = 143–175
}}</ref>

* [[Minkowski metric weighted k-means]] ใช้สำหรับฟีเจอร์ที่ไม่สัมพันธ์กัน โดยการกำหนดค่าน้ำหนักเฉพาะของคลัสเตอร์กับแต่ละฟีเจอร์<ref>{{Cite journal
 | first1 = R. C. |last1 = Amorim
 | first2 = B |last2 = Mirkin
 | year = 2012
 | title =  Minkowski metric, feature weighting and anomalous cluster initializing in K-Means clustering
 | journal = Pattern Recognition
 | volume = 45
 | issue = 3
 | pages = 1061–1075
 | doi=10.1016/j.patcog.2011.08.012
}}</ref>

== อภิปราย ==
[[ไฟล์:K-means convergence to a local minimum.png|thumb|650px|ตัวอย่างที่การจับกลุ่มข้อมูลแบบค่าเฉลี่ย k ลู่เข้าถึงค่าต่ำสุดเฉพาะที่ ในตัวอย่างนี้ผลลัพธ์ของการแบ่งกลุ่มแบบค่าเฉลี่ย k (รูปขวาสุด) ขัดแย้งกับรูปแบบของกลุ่มข้อมูลที่สามารถเห็นได้อย่างชัดเจนจากภาพ วงกลมเล็กแทนถึงจุดข้อมูลแต่ละจุด ดาวสี่แฉกแทนถึงจุดศูนย์กลางของกลุ่มข้อมูลแต่ละกลุ่ม รูปแบบของกลุ่มข้อมูลเริ่มต้นแสดงในรูปด้านซ้ายสุด ขั้นตอนวิธีลู่เข้าหลังจากการวนซ้ำรอบที่ 5 (จากภาพซ้ายไปขวา)]]

[[ไฟล์:ClusterAnalysis Mouse.svg|thumb|400px|การแบ่งกลุ่มแบบค่าเฉลี่ย k (''k''-means clustering) และการแบ่งกลุ่มด้วย[[ขั้นตอนวิธีค่าคาดหมายสูงสุด]]ของกลุ่มข้อมูล ("mouse"). ผลลัพธ์ของการจับกลุ่มข้อมูลแบบค่าเฉลี่ย k สร้างกลุ่มข้อมูลที่มีขนาดเท่ากัน ทำให้ผลลัพธ์ออกมาอย่างไม่เหมาะสม ในขณะที่การแบ่งกลุ่มด้วยขั้นตอนวิธีค่าคาดหมายสูงสุดให้ผลลัพธ์ที่ดีกว่าเนื่องจากใช้การจัดแจงแบบปรกติที่แสดงให้เห็นในชุดข้อมูล]]

องค์ประกอบสองอย่างที่ทำให้การแบ่งกลุ่มแบบค่าเฉลี่ย k เป็นขั้นตอนวิธีที่มีประสิทธิภาพ แต่ก็มักจะถูกพิจารณว่าเป็นข้อเสียของการแบ่งกลุ่มแบบค่าเฉลี่ย k ได้แก่:
* [[%E0%B8%A3%E0%B8%B0%E0%B8%A2%E0%B8%B0%E0%B8%97%E0%B8%B2%E0%B8%87%E0%B9%81%E0%B8%9A%E0%B8%9A%E0%B8%A2%E0%B8%B8%E0%B8%84%E0%B8%A5%E0%B8%B4%E0%B8%94|ระยะทางแบบยูคลิด]]ได้ถูกใช้ให้เป็นตัววัดระยะห่างระหว่างข้อมูลและความแปรปรวน ([[Variance]]) ถูกใช้เป็นตัววัดการกระจ่ายของกลุ่มข้อมูล
* จำนวนของกลุ่มของข้อมูล k เป็นตัวแปรเสริมที่ถูกนำเข้าในขั้นตอนวิธี: ตัวเลือกที่ไม่เหมาะสมสำหรับค่าของ k อาจจะส่งผลให้ผลลัพธ์ที่ออกมาไม่ดีนัก ดังนั้นการ[[K-means_clustering|ตรวจสอบจำนวนของกลุ่มข้อมูลที่เหมาะสม]]ต่อข้อมูลจึงเป็นสิ่งที่สำคัญอย่างยิ่งก่อนจะเริ่มดำเนินการแบ่งกลุ่มแบบค่าเฉลี่ย k
* การลู่เข้าถึงค่าต่ำสุดเฉพาะที่ (local minimum) อาจส่งผลให้ขั้นตอนวิธีมอบผลลัพธ์ที่ผิดพลาดได้
ปัจจัยที่จำกัดความสามารถของการแบ่งกลุ่มแบบค่าเฉลี่ย k คือแบบจำลองของกลุ่มข้อมูล การแบ่งกลุ่มของข้อมูลแบบค่าเฉลี่ย k คาดการณ์แบบจำลองของกลุ่มข้อมูลเป็นรูปแบบของทรงกลม และข้อมูลสามารถถูกแบ่งกลุ่มได้โดยการที่ค่าเฉลี่ยของกลุ่มข้อมูลลู่เข้า ถึงจุดศูนย์กลางของกลุ่มข้อมูลทรงกลมนั้น กลุ่มข้อมูลแต่ละกลุ่มถูกคาดการณ์ไว้ว่าจะมีขนาดที่ใกล้เคียงกัน ทำให้การกำหนดกลุ่มของข้อมูลแต่ละตัวไปยังจุดศูนย์กลางของกลุ่มข้อมูลที่อยู่ใกล้ที่สุดถูกต้อง ซึ่งปัจจัยเหล่านี้ก่อให้เกิดปัญหาในการแบ่งกลุ่มแบบค่าเฉลี่ย k ต่อกลุ่มข้อมูลที่มีลักษณะไม่ตรงไปตามความคาดการณ์ที่ถูกกำหนดไว้ในขั้นตอนวิธี

เราสามารถมองผลลัพธ์ของการแบ่งกลุ่มแบบค่าเฉลี่ย k ได้ในรูปแบบของ[[%E0%B9%81%E0%B8%9C%E0%B8%99%E0%B8%A0%E0%B8%B2%E0%B8%9E%E0%B9%82%E0%B8%A7%E0%B9%82%E0%B8%A3%E0%B8%99%E0%B8%AD%E0%B8%A2|แผนภาพโวโรนอย]]ของค่าเฉลี่ยกลุ่มข้อมูล เนื่องจากข้อมูลถูกแบ่งครึ่งทางระหว่างระยะห่างของจุดศุนย์กลางของกลุ่มข้อมูลแต่ละกลุ่ม ดังนั้นจึงอาจจะทำให้เกิดการแบ่งข้อมูลที่ไม่เหมาะสมอย่างที่สุดได้ (ดูตัวอย่างใน กลุ่มข้อมูล "mouse") [[การแจกแจงปรกติ]]ซึ่งใช้โดย[[ขั้นตอนวิธีค่าคาดหมายสูงสุด]] ซึ่งมีความยึดหยุ่นในการแบ่งข้อมูลเนื่องจากมีการคำนวณโดยใช้ทั้งการแปรปรวนและการแปรปรวนร่วมเกี่ยว ส่งผลให้สามารถแบ่งกลุ่มข้อมูลที่มีขนาดแตกต่างกันในแต่ละกลุ่มได้ดีกว่าการแบ่งกลุ่มแบบค่าเฉลี่ย k

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

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

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

[[ไฟล์:Rosa Gold Glow 2 small noblue.png|frame|right|ภาพสองช่องสี (แดงและเขียว)]]
[[ไฟล์:Rosa Gold Glow 2 small noblue color space.png|thumb|right|250px|การแบ่งนับเวกเตอร์ของสีที่นำเสนอในรูปภาพสองช่องสีข้างต้น ให้อยู่ในรูปของแผนภาพโวโรนอยโดยการใช้การแบ่งกลุ่มแบบค่าเฉลี่ย k]]

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

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

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

=== การเรียนรู้ลักษณะเฉพาะ (Feature learning) ===
การจับกลุ่มข้อมูลแบบค่าเฉลี่ย k ได้ถูกนำไปใช้ในขั้นตอนฟีเจอร์เลิร์นนิ่ง (Feature learning) ทั้งในการเรียนรู้แบบมีผู้สอน (supervised learning) การเรียนรู้แบบกึ่งมีผู้สอน (semi-supervised learning) และการเรียนรู้แบบไม่มีผู้สอน (unsupervised learning)<ref name="Coates2012">{{cite encyclopedia
|last1 = Coates
|first1 = Adam
|last2 = Ng
|first2 = Andrew Y.
|title = Learning feature representations with k-means
|editor1 = Grégoire Montavon
|editor2 = Geneviève B. Orr
|editor3 = Klaus-Robert Müller
|display-editors = 1
|encyclopedia = Neural Networks: Tricks of the Trade
|publisher = Springer
|year = 2012
|url = http://www.stanford.edu/~acoates/papers/coatesng_nntot2012.pdf
|isbn = 978-3-642-35289-8
|access-date = 2015-04-25
|archive-date = 2013-06-06
|archive-url = https://web.archive.org/web/20130606213934/http://www.stanford.edu/~acoates/papers/coatesng_nntot2012.pdf
|url-status = dead
|df = dmy-all
}}</ref>
ขั้นตอนในการปฏิบัติเริ่มจากการสร้างกลุ่มข้อมูลจำนวน k กลุ่มด้วยการจับกลุ่มข้อมูลแบบค่าเฉลี่ย k โดยใช้ข้อมูลสอน (training data) หลังจากนั้นจึงโปรเจกต์ข้อมูลป้อนเข้าไปยังฟีเจอร์สเปซใหม่ โดยใช้แมทริกส์โปรดัคระหว่างข้อมูลและตำแหน่งของศูนย์กลางของแต่ละกลุ่มข้อมูล ระยะห่างระหว่างข้อมูลป้อนเข้าและศูนย์กลางของแต่ละกลุ่มข้อมูล ฟังก์ชันที่ชี้ข้อมูลป้อนเข้าถึงจุดศูนย์กลางของกลุ่มข้อมูลที่ใกล้ที่สุด<ref name="Coates2012" /><ref>{{cite conference
|last1 = Csurka
|first1 = Gabriella
|last2 = Dance
|first2 = Christopher C.
|last3 = Fan
|first3 = Lixin
|last4 = Willamowski
|first4 = Jutta
|last5 = Bray
|first5 = Cédric
|title = Visual categorization with bags of keypoints
|conference = ECCV Workshop on Statistical Learning in Computer Vision
|year = 2004
|url = http://www.cs.cmu.edu/~efros/courses/LBMV07/Papers/csurka-eccv-04.pdf
}}</ref> หรือสมูทฟังก์ชันของระยะห่างระหว่างข้อมูลและศูนย์กลางของกลุ่มข้อมูลเป็นต้น<ref name="coates2011" /> 

การใช้งานของการแบ่งกลุ่มแบบค่าเฉลี่ย k นี้ประสบความสำเร็จในร่วมใช้งานกับตัวแยกแบบเชิงเส้น ([[linear classifier]]) สำหรับข้อมูลแบบกึ่งมีผู้สอนในการประมวลภาษาธรรมชาติ<ref>{{cite conference
|last1 = Lin
|first1 = Dekang
|last2 = Wu
|first2 = Xiaoyun
|title = Phrase clustering for discriminative learning
|conference = Annual Meeting of the [[Association_for_Computational_Linguistics|ACL]] and IJCNLP
|year = 2009
|pages = 1030–1038
|url = http://www.aclweb.org/anthology/P/P09/P09-1116.pdf
}}</ref>
และในคอมพิวเตอร์วิทัศน์ โดยเฉพาะอย่างยิ่งในการรู้จำวัตถุ (object recognition) นั้นการจับกลุ่มข้อมูลแบบค่าเฉลี่ย k สามารถให้ผลลัพธ์ที่มีประสิทธิภาพใกล้เคียงกับ วิธีการเรียนรู้ลักษณะเฉพาะที่ซับซ้อนแบบอื่นยกตัวอย่างเช่น [[ตัวเข้ารหัสอัตโนมัติ]] และ [[restricted Boltzmann machines]].<ref name="coates2011">{{cite conference
|last1 = Coates
|first1 = Adam
|last2 = Lee
|first2 = Honglak
|last3 = Ng
|first3 = Andrew Y.
|title = An analysis of single-layer networks in unsupervised feature learning
|conference = International Conference on Artificial Intelligence and Statistics (AISTATS)
|year = 2011
|url = http://www.stanford.edu/~acoates/papers/coatesleeng_aistats_2011.pdf
|access-date = 2015-04-25
|archive-date = 2013-05-10
|archive-url = https://web.archive.org/web/20130510120705/http://www.stanford.edu/~acoates/papers/coatesleeng_aistats_2011.pdf
|url-status = dead
|df = dmy-all
}}</ref>
อย่างไรก็ตามการจับกลุ่มข้อมูลแบบค่าเฉลี่ย k นั้น ต้องการจำนวนข้อมูลป้อนเข้าที่มีขนาดมากกว่าที่วิธีฟีเจอร์เลิร์นนิ่งที่ซับซ้อนที่กล่าวมาข้างต้นต้องการ เพื่อให้ได้ผลลัพธ์ที่ใกล้เคียงกันเนื่องจากในการจับกลุ่มข้อมูลแบบค่าเฉลี่ย k นั้น ข้อมูลแต่ละอันส่งผลถึงฟีเจอร์เพียงอันเดียวมากกว่าที่จะส่งผลถึงหลาย ๆ ฟีเจอร์<ref name="Coates2012" />

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

เราสามารถกล่าวได้ว่าการจับกลุ่มข้อมูลแบบค่าเฉลี่ย k และ[[ขั้นตอนวิธีค่าคาดหมายสูงสุด]]นั้นเป็นเพียงแค่เคสพิเศษของการประมาณรูปร่างผสมของเกาส์ (Gaussian mixture model) ดังนั้นโดยปรกติแล้วเราจึงสามารถเปลี่ยนรูปของการจับกลุ่มข้อมูลแบบค่าเฉลี่ย k ให้อยู่ในรูปของรูปร่างผสมของเกาส์ได้<ref>{{Cite book | last1=Press | first1=WH | last2=Teukolsky | first2=SA | last3=Vetterling | first3=WT | last4=Flannery | first4=BP | year=2007 | title=Numerical Recipes: The Art of Scientific Computing | edition=3 | publisher=Cambridge University Press | place=New York | isbn=978-0-521-88068-8 | chapter=Section 16.1. Gaussian Mixture Models and k-Means Clustering | url=http://apps.nrbook.com/empanel/index.html#pg=842 | access-date=2015-04-27 | archive-date=2011-08-11 | archive-url=https://web.archive.org/web/20110811154417/http://apps.nrbook.com/empanel/index.html#pg=842 | url-status=dead }}</ref>  นอกจากรูปร่างผสมของเกาส์แล้ว เรายังสามารถเปลี่ยนรูปของการจับกลุ่มข้อมูลแบบค่าเฉลี่ย k ให้อยู่ในรูปของขั้นตอนวิธีแบบ K-SVD ซึ่งเป็นขั้นตอนวิธีที่คาดการณ์จุดข้อมูลแต่ล่ะจุดในรูปแบบของผลรวมเชิงเส้นของ"เวกเตอร์โค้ดบุ้ค" (codebook vector) โดยที่การจับกลุ่มข้อมูลแบบค่าเฉลี่ย k นั้นมีความข้องเกี่ยวกับกรณีที่ มีการใช้เวกเตอร์โค้ดบุ้คเพียงเวกเตอร์เดียวด้วยค่าน้ำหนักเท่ากับหนึ่งเท่านั้น<ref>{{Cite journal | last1=Aharon | first1=Michal | last2=Elad | first2=Michael | last3=Bruckstein | first3=Alfred | date=November 2006 | title=K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation | url=http://intranet.daiict.ac.in/~ajit_r/IT530/KSVD_IEEETSP.pdf | journal=IEEE Transactions on Signal Processing | volume=54 | number=11 | pages=4311–22 | access-date=2015-04-27 | archive-date=2013-06-20 | archive-url=https://web.archive.org/web/20130620125943/http://intranet.daiict.ac.in/~ajit_r/IT530/KSVD_IEEETSP.pdf | url-status=dead | df=dmy-all}}</ref>

=== การแบ่งกลุ่มแบบมีนชิฟต์ (Mean shift clustering) ===
การแบ่งกลุ่มแบบมีนชิฟต์นั้น เป็นขั้นตอนวิธีที่คงจำนวนของข้อมูลในชุดไว้ให้มีขนาดที่เท่ากับจำนวนข้อมูลป้อนเข้าเริ่มต้น ในจุดเริ่มต้นของขั้นตอนวิธีนั้นชุดของข้อมูลนี้เกิดจากการคัดลอกมาจากชุดข้อมูลป้อนเข้า หลังจากนั้นในแต่ละการวนซ้ำข้อมูลในชุดนี้ได้ถูกแทนที่ด้วย ค่าเฉลี่ยของจุดข้อมูลที่อยู่ในชุดที่อยู่ภายในระยะทางที่กำหนดจากจุดข้อมูลจุดนั้น ในทางกลับกันการที่การจับกลุ่มข้อมูลแบบค่าเฉลี่ย k จำกัดการอัปเดตข้อมูลนี้ให้อยู่ที่ข้อมูล k จุดและเปลี่ยนค่าของแต่ละจุดใน k จุดนี้ด้วยค่าเฉลี่ยของจุดข้อมูลทุกจุดที่ในชุดข้อมูลป้อนเข้า ที่อยู่ใกล้กับจุดจุดนั้นที่สุดเมื่อเทียบกับจุดอื่นใน k จุด การแบ่งกลุ่มแบบมีนชิฟต์ที่มีลักษณะคล้ายคลึงกับการแบ่งกลุ่มแบบค่าเฉลี่ย k นั้นเรียกว่า likelihood mean shift ซึ่งในขั้นตอนวิธีนี้มีการแทนที่ค่าของชุดข้อมูลด้วยค่าเฉลี่ยของจุดข้อมูลทั้งหมดในชุดข้อมูลป้อนเข้า ที่มีระยะห่างภายในระยะทางที่กำหนดไว้จากชุดนั้น ๆ<ref name="Little2011">{{cite journal|last1=Little|first1=M.A.|last2=Jones|first2=N.S.|title=Generalized Methods and Solvers for Piecewise Constant Signals: Part I|journal=[[Proceedings_of_the_Royal_Society#Proceedings_of_the_Royal_Society_A:_Mathematical,_Physical_and_Engineering_Sciences|Proceedings of the Royal Society A]]|url=http://www.maxlittle.net/publications/pwc_filtering_arxiv.pdf|year=2011|access-date=2015-04-27|archive-date=2019-08-19|archive-url=https://web.archive.org/web/20190819140345/http://www.maxlittle.net/publications/pwc_filtering_arxiv.pdf|url-status=dead}}</ref> การแบ่งกลุ่มแบบมีนชิฟต์นั้นมีข้อได้เปรียบอย่างหนึ่งเหนือการจับกลุ่มข้อมูลแบบค่าเฉลี่ย k ซึ่งคือ การที่การแบ่งกลุ่มแบบมีนชิฟต์นั้นไม่จำเป็นต้องมีการกำหนดจำนวนของกลุ่มข้อมูลเพราะว่า การแบ่งกลุ่มแบบมีนชิฟต์นั้นจะหาจำนวนของกลุ่มข้อมูลที่จำเป็นโดยอัตโนมัติ แต่อย่างไรก็ตามการแบ่งกลุ่มแบบมีนชิฟต์นั้นใช้เวลาในการประมวลผลนานกว่าการแบ่งกลุ่มแบบค่าเฉลี่ย k มาก

=== การวิเคราะห์ส่วนประกอบสำคัญ (Principal component analysis) ===
มีการแสดงให้เห็นใน<ref>{{cite journal|author1=H. Zha|author2=C. Ding|author3=M. Gu|author4=X. He|author5=H.D. Simon|title=Spectral Relaxation for K-means Clustering|journal=Neural Information Processing Systems vol.14 (NIPS 2001)|pages=1057–1064|location=Vancouver, Canada|date=December 2001|url=http://ranger.uta.edu/~chqding/papers/Zha-Kmeans.pdf|df=dmy-all}}</ref><ref>{{cite conference|author1=Chris Ding|author2=Xiaofeng He|title=K-means Clustering via Principal Component Analysis|work=Proc. of Int'l Conf. Machine Learning (ICML 2004)|pages=225–232|date=July 2004|url=http://ranger.uta.edu/~chqding/papers/KmeansPCA1.pdf|df=dmy-all}}</ref>ว่าผลลัพธ์ที่อยู่ในรูปทั่วไปของการจับกลุ่มข้อมูลแบบค่าเฉลี่ย k (ร่วมด้วยตัวบ่งชี้จุดข้อมูลถึงแต่ละกลุ่มข้อมูล) คือผลจากการวิเคราะห์ส่วนประกอบสำคัญ (PCA) และซับสเปซของการวิเคราะห์ส่วนประกอบสำคัญที่ถูกขยายในทิศทางที่สำคัญ กับซับสเปซของศูนย์กลางของกลุ่มข้อมูลที่เกิดจากการแบ่งกลุ่มแบบค่าเฉลี่ย k นั้นเป็นสิ่งเดียวกัน อย่างไรก็ตามการที่การวิเคราะห์องค์ประกอบสำคัญนั้น คือผลลัพธ์โดยทั่วไปของผลลัพธ์จากการแบ่งกลุ่มแบบค่าเฉลี่ย k นั้นไม่ใช่เรื่องใหม่แต่อย่างใด (โปรดดูตัวอย่าง<ref>{{cite journal | title = Clustering large graphs via the singular value decomposition | journal = Machine learning | year = 2004 | author1 = P. Drineas |author2=A. Frieze |author3=R. Kannan |author4=S. Vempala |author5= V. Vinay | volume = 56 | pages = 9–33| df = dmy-all | url = http://www.cc.gatech.edu/~vempala/papers/dfkvv.pdf | access-date = 2012-08-02 | doi=10.1023/b:mach.0000033113.59016.96}}</ref>), และมันก็ตรงไปตรงมาที่จะแสดงให้เห็นถึงตัวอย่างหักล้างกับข้อความที่ว่า ซับสเปซของจุดศูนย์กลางของกลุ่มข้อมูลถูกขยายโดยทิศทางที่สำคัญ<ref>{{cite arXiv | title = Dimensionality reduction for k-means clustering and low rank approximation (Appendix B) | year = 2014 | author1 = M. Cohen |author2 = S. Elder |author3 = C. Musco |author4 = C. Musco |author5 = M. Persu | arxiv = 1410.6801v3}}</ref>

=== การวิเคราะห์องค์ประกอบอิสระ (Independent component analysis) ===
มีการแสดงให้เห็นใน<ref>
{{cite conference|first1=Alon|last1=Vinnikov|first2=Shai|last2=Shalev-Shwartz
|title=K-means Recovers ICA Filters when Independent Components are Sparse
|work=Proc. of Int'l Conf. Machine Learning (ICML 2014)
|year=2014
|url=http://www.cs.huji.ac.il/~shais/papers/KmeansICA_ICML2014.pdf
|language=en
}}</ref>
ว่าภายใต้ข้อกำหนดบางประการและเมื่อข้อมูลป้อนเข้าได้รับการประมวลผลเบื้องค้นด้วยขั้นตอนวิธี [[whitening transformation]] การจับกลุ่มข้อมูลแบบค่าเฉลี่ย k นั้นจะให้ผลลัพธ์ที่มีค่าเท่ากับการวิเคราะห์องค์ประกอบอิสระแบบเชิงเส้น

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

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

== ซอฟต์แวร์ ==

=== ฟรีแวร์/โอเพ่นซอร์ส ===
{{Div col|colwidth=20em}}
* Apache Mahout
* Apache Spark 
* CrimeStat
* ELKI
* Julia
* MLPACK (ไลบรารีภาษา C++)
* R ([[ภาษาโปรแกรม]])
* SciPy
* Torch ([[การเรียนรู้ของเครื่อง]])
* Weka (การเรียนรู้ของเครื่อง)
* OpenCV
{{Div col end}}

=== ซอฟต์แวร์เชิงพาณิชย์ ===
{{Div col|colwidth=20em}}
* IDL Cluster, Clust_Wts
* MATLAB
* SAS System 
* Stata
* Grapheme (Data visualisation - iChrome)
{{Div col end}}

== อ้างอิง ==
{{รายการอ้างอิง|30em}}

== แหล่งข้อมูลอื่น ==
* {{คอมมอนส์-หมวดหมู่-บรรทัด|K-means algorithm}}

[[หมวดหมู่:ขั้นตอนวิธีการจับกลุ่มข้อมูล]]
[[หมวดหมู่:ขั้นตอนวิธีเชิงสถิติ]]