การจับกลุ่มข้อมูลแบบค่าเฉลี่ย k

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

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

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

คำอธิบาย

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

${\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,^[1] แม้ว่าแนวคิดเริ่มแรกจะเป็นของ Hugo Steinhaus ซึ่งเกิดขึ้นในปี พ.ศ. 2500^[2] และขั้นตอนวิธีมาตรฐานนั้นก็ถูกเสนอขึ้นในปี พ.ศ. 2500 โดย Stuart Lloyd เพื่อเป็นเทคนิคสำหรับการกล้ำรหัสของพัลส์ อย่างไรก็ตามขั้นตอนวิธีไม่ได้ถูกเผยแพร่ออกไปจาก Bell Labs จนกระทั่งปี พ.ศ. 2525^[3] ในปี พ.ศ. 2508 E.W.Forgy ได้ตีพิมพ์วิธีเดียวกันนี้เช่นกัน จึงทำให้บางครั้งวิธีนี้ถูกกล่าวถึงในชื่อ Lloyd-Forgy^[4] นอกจากนี้ได้มีการตีพิมพ์แบบฉบับที่มีการพัฒนาขึ้นไป โดย Hartigan and Wong ในปี พ.ศ. 2518 / 2522^[5]

ขั้นตอนวิธี

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

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

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

$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 \}},$

โดยที่ ค่า

x_{p}

แต่ละค่ามีแค่หนึ่งค่า

S^{(t)}

แม้ว่าจะมีค่าที่เป็นไปได้สองค่าขึ้นไป

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

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

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

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

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

โดยทั่วไปแล้ว จะใช้วิธีของ Forgy และวิธีการตัดแบ่งแบบสุ่ม (Random Partition^[9]) เป็นวิธีการกำหนดค่าตั้งต้น วิธีของ Forgy คือการเลือกข้อมูลการสังเกต k อย่างขึ้นมาแบบสุ่ม จากข้อมูลทั้งหมด แล้วใช้เป็นค่าเฉลี่ยเริ่มต้น ส่วนการตัดแบ่งข้อมูลแบบสุ่มนั้นจะเริ่มต้นด้วยการสุ่มจัดข้อมูลการสังเกตแต่ละอันไปอยู่ในกลุ่มใด ๆ และจากนั้นจะทำการปรับค่าตามขั้นตอนที่กล่าวไปแล้ว ดังนั้นค่าเฉลี่ยเริ่มต้นที่ได้จาการปรับค่าจะเป็นจุดเซนทรอยด์ (centroid) ของข้อมูลการสังเกตในแต่ละคลัสเตอร์ที่สร้างขึ้นมาแบบสุ่มนั่นเอง วิธีของ Forgy มีแนวโน้มที่จะกระจายค่าเฉลี่ยเริ่มต้น ในขณะที่การตัดแบ่งข้อมูลแบบสุ่มจะเลือกค่าเริ่มต้นที่ใกล้กับจุดกึ่งกลางของข้อมูลทั้งหมด นอกจากนี้ อ้างอิงจาก Hamerly และคณะ^[9] การตัดแบ่งข้อมูลแบบสุ่มที่เหมาะกับขั้นตอนวิธีการหา 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)$ ในการลู่เข้า^[10] ข้อมูลดังกล่าวเหมือนว่าจะไม่เกิดขึ้นในการปฏิบัติจริง จึงสามารถยืนยันได้ว่า เวลาที่ใช้ในการทำงานที่ปรับเรียบ (smoothed running time) ของขั้นตอนการหาค่าเฉลี่ย k เป็นเป็นฟังก์ชันพหุนาม^[11]

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

ความซับซ้อน

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

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

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

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

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

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

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

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

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

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

อภิปราย

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

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

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

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

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

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

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

การแบ่งกลุ่มแบบค่าเฉลี่ย k ถูกริเริ่มขึ้นเพื่อใช้ในการประมวลสัญญาณและยังคงถูกใช้มาจนถึงในปัจจุบันนี้ ยกตัวอย่างเช่นในคอมพิวเตอร์กราฟิก, การแบ่งนับสี (Color quantization เป็นกระบวนการของการลดจำนวนชนิดสีในแต่ละภาพให้เหลือเพียงจำนวนสีเท่ากับ k ตามที่ถูกกำหนดไว้ ซึ่งการการแบ่งกลุ่มแบบค่าเฉลี่ย k นี้สามารถนำมาใช้เพื่อปฏิบัติการแบ่งนับสีได้อย่างง่ายดายและมีประสิทธิภาพ การใช้ประโยชน์จากการแบ่งนับเวกเตอร์อย่างอื่นได้แก่การชักตัวอย่างแบบไม่สุ่ม (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)^[23] ขั้นตอนในการปฏิบัติเริ่มจากการสร้างกลุ่มข้อมูลจำนวน k กลุ่มด้วยการจับกลุ่มข้อมูลแบบค่าเฉลี่ย k โดยใช้ข้อมูลสอน (training data) หลังจากนั้นจึงโปรเจกต์ข้อมูลป้อนเข้าไปยังฟีเจอร์สเปซใหม่ โดยใช้แมทริกส์โปรดัคระหว่างข้อมูลและตำแหน่งของศูนย์กลางของแต่ละกลุ่มข้อมูล ระยะห่างระหว่างข้อมูลป้อนเข้าและศูนย์กลางของแต่ละกลุ่มข้อมูล ฟังก์ชันที่ชี้ข้อมูลป้อนเข้าถึงจุดศูนย์กลางของกลุ่มข้อมูลที่ใกล้ที่สุด^[23]^[24] หรือสมูทฟังก์ชันของระยะห่างระหว่างข้อมูลและศูนย์กลางของกลุ่มข้อมูลเป็นต้น^[25]

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

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

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

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

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

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

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

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

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

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

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

อ้างอิง

↑ 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. MR 0214227. Zbl 0214.46201. สืบค้นเมื่อ 2009-04-07.
↑ 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.
↑ 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). IEEE Transactions on Information Theory. 28 (2): 129–137. doi:10.1109/TIT.1982.1056489. สืบค้นเมื่อ 2009-04-15.
↑ E.W. Forgy (1965). "Cluster analysis of multivariate data: efficiency versus interpretability of classifications". Biometrics. 21: 768–769.
↑ J.A. Hartigan (1975). Clustering algorithms. John Wiley & Sons.
↑ 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.
↑ Since the square root is a monotone function, this also is the minimum Euclidean distance assignment.
↑ 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.0 ^9.1 Hamerly, G.; Elkan, C. (2002). Alternatives to the k-means algorithm that find better clusterings (PDF). Proceedings of the eleventh international conference on Information and knowledge management (CIKM). คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 5 สิงหาคม 2012. สืบค้นเมื่อ 27 เมษายน 2015.
↑ Vattani., A. (2011). "k-means requires exponentially many iterations even in the plane" (PDF). Discrete & Computational Geometry. 45 (4): 596–616. doi:10.1007/s00454-011-9340-1.
↑ ^11.0 ^11.1 Arthur, D.; Manthey, B.; Roeglin, H. (2009). k-means has polynomial smoothed complexity. Proceedings of the 50th Symposium on Foundations of Computer Science (FOCS).
↑ 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.
↑ Dasgupta, S.; Freund, Y. (กรกฎาคม 2009). "Random Projection Trees for Vector Quantization". Information Theory, IEEE Transactions on. 55: 3229–3242. arXiv:0805.1390. doi:10.1109/TIT.2009.2021326.
↑ Mahajan, M.; Nimbhorkar, P.; Varadarajan, K. (2009). "The Planar k-Means Problem is NP-Hard". Lecture Notes in Computer Science. 5431: 274–285. doi:10.1007/978-3-642-00202-1_24.
↑ 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.
↑ 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.
↑ 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. คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2009-10-07. สืบค้นเมื่อ 2009-04-24.
↑ Gereon Frahling; Christian Sohler (5 ธันวาคม 2005). A fast k-means implementation using coresets (PDF). Proceedings of the twenty-second annual symposium on Computational geometry (SoCG). S2CID 5891336.
↑ Elkan, C. (2003). Using the triangle inequality to accelerate k-means (PDF). Proceedings of the Twentieth International Conference on Machine Learning (ICML).
↑ 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.
↑ Dhillon, I. S.; Modha, D. M. (2001). "Concept decompositions for large sparse text data using clustering". Machine Learning. 42 (1): 143–175.
↑ 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.0 ^23.1 ^23.2 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. คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 6 มิถุนายน 2013. สืบค้นเมื่อ 25 เมษายน 2015.
↑ 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.0 ^25.1 Coates, Adam; Lee, Honglak; Ng, Andrew Y. (2011). An analysis of single-layer networks in unsupervised feature learning (PDF). International Conference on Artificial Intelligence and Statistics (AISTATS). คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 10 พฤษภาคม 2013. สืบค้นเมื่อ 25 เมษายน 2015.
↑ Lin, Dekang; Wu, Xiaoyun (2009). Phrase clustering for discriminative learning (PDF). Annual Meeting of the ACL and IJCNLP. pp. 1030–1038.
↑ 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. คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2011-08-11. สืบค้นเมื่อ 2015-04-27.
↑ Aharon, Michal; Elad, Michael; Bruckstein, Alfred (พฤศจิกายน 2006). "K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation" (PDF). IEEE Transactions on Signal Processing. 54 (11): 4311–22. คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 20 มิถุนายน 2013. สืบค้นเมื่อ 27 เมษายน 2015.
↑ ^29.0 ^29.1 Little, M.A.; Jones, N.S. (2011). "Generalized Methods and Solvers for Piecewise Constant Signals: Part I" (PDF). Proceedings of the Royal Society A. คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2019-08-19. สืบค้นเมื่อ 2015-04-27.
↑ 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.
↑ 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.
↑ 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.
↑ M. Cohen; S. Elder; C. Musco; C. Musco; M. Persu (2014). "Dimensionality reduction for k-means clustering and low rank approximation (Appendix B)". arXiv:1410.6801v3.
↑ 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

[macqueen1967-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. 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.

[lloyd1957-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). IEEE Transactions on Information Theory. 28 (2): 129–137. doi:10.1109/TIT.1982.1056489. สืบค้นเมื่อ 2009-04-15.

[forgy65-4] E.W. Forgy (1965). "Cluster analysis of multivariate data: efficiency versus interpretability of classifications". Biometrics. 21: 768–769.

[hartigan1975-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.

[hartigan19792-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.

[hamerly-9] 9.0 ^9.1 Hamerly, G.; Elkan, C. (2002). Alternatives to the k-means algorithm that find better clusterings (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). Discrete & Computational Geometry. 45 (4): 596–616. doi:10.1007/s00454-011-9340-1.

[Arthur,_D.;_Manthey,_B.;_Roeglin,_H._2009-11] 11.0 ^11.1 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. (กรกฎาคม 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". 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. คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 2009-10-07. สืบค้นเมื่อ 2009-04-24.

[18] Gereon Frahling; Christian Sohler (5 ธันวาคม 2005). A fast k-means implementation using coresets (PDF). Proceedings of the twenty-second annual symposium on Computational geometry (SoCG). 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).

[hartigan1979-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.

[Coates2012-23] 23.0 ^23.1 ^23.2 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. คลังข้อมูลเก่าเก็บจากแหล่งเดิม (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.

[coates2011-25] 25.0 ^25.1 Coates, Adam; Lee, Honglak; Ng, Andrew Y. (2011). An analysis of single-layer networks in unsupervised feature learning (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 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. คลังข้อมูลเก่าเก็บจากแหล่งเดิมเมื่อ 2011-08-11. สืบค้นเมื่อ 2015-04-27.

[28] Aharon, Michal; Elad, Michael; Bruckstein, Alfred (พฤศจิกายน 2006). "K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation" (PDF). IEEE Transactions on Signal Processing. 54 (11): 4311–22. คลังข้อมูลเก่าเก็บจากแหล่งเดิม (PDF)เมื่อ 20 มิถุนายน 2013. สืบค้นเมื่อ 27 เมษายน 2015.

[Little2011-29] 29.0 ^29.1 Little, M.A.; Jones, N.S. (2011). "Generalized Methods and Solvers for Piecewise Constant Signals: Part I" (PDF). Proceedings of the Royal Society A. คลังข้อมูลเก่าเก็บจากแหล่งเดิม (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)". arXiv: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) (ภาษาอังกฤษ).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]