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

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

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

ขั้นตอนการกำหนดค่า: กำหนดแต่ละข้อมูลการสังเกตไปยังคลัสเตอร์ โดยเลือกคลัสเตอร์ที่จะทำให้ค่าผลบวกกำลังสองภายในคลัสเตอร์ (within-cluster sum of squares; WCSS) นั้น ๆ มีค่าน้อยที่สุด เนื่องจากผลบวกของค่ากำลังสองเป็นค่ากำลังสองของระยะทางแบบยุคลิด (Euclidean distance) มันจึงเป็นค่าเฉลี่ย “ที่ใกล้ที่สุด”[7] (โดยทางคณิตศาสตร์ นี่เป็นการแสดงว่าการตัดแบ่งข้อมูลตามแผนภาพโวโรนอย (Voronoi diagram) นั้นแบ่งตามค่าเฉลี่ยข้างต้น) S i ( t ) = { x p : ‖ x p − m i ( t ) ‖ 2 ≤ ‖ x p − m j ( t ) ‖ 2   ∀ j , 1 ≤ j ≤ k } , {\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 \}},} โดยที่ ค่า x p {\displaystyle x_{p}} แต่ละค่ามีแค่หนึ่งค่า S ( t ) {\displaystyle S^{(t)}} แม้ว่าจะมีค่าที่เป็นไปได้สองค่าขึ้นไปขั้นตอนการปรับค่า: คำนวณค่าเฉลี่ยค่าใหม่เพื่อเป็นจุดเซนทรอยด์ (centroid) ของข้อมูลการสังเกตในแต่ละคลัสเตอร์ที่สร้างขึ้นใหม่ m i ( t + 1 ) = 1 | S i ( t ) | ∑ x j ∈ S i ( t ) x j {\displaystyle 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) เช่น เคมีนแบบทรงกลม (spherical k-means) และ k-medoids เพื่อทำให้การคำนวณระยะห่างแบบอื่น ๆ ใช้กับขั้นตอนวิธีนี้ได้

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

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

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

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

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

ความซับซ้อน

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

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

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

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

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

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

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

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

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

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