K Means Clustering with Python

  • K Means เป็นอัลกอริทึม Machine Learning แบบ Unsupervised คือไม่ต้องมีการเทรนจากมนุษย์ก่อน ปรกติ Supervised Machine Learning จะต้องกำหนด Input และ Output เพื่อใช้เทรนโมเดล แต่ K Means นั้นกำหนดเพียง Input อย่างเดียวก็พอ ความสามารถของ K Means นั้นคือการแบ่งกลุ่มข้อมูลหรือที่เรียกว่า Clustering เพื่อแบ่งข้อมูลออกเป็น K กลุ่มตามชื่อของมัน โดนแต่ละกลุ่มจะมีจุดศูนย์กลางข้อมูลเรียก Centroid โดย Centroid นี้เกิดจากค่าเฉลี่ย(Means) ตำแหน่งของข้อมูลทุกตัวในกลุ่มข้อมูล
  • โพสนี้จะเป็นการรีวิวแลปโน้ตและใช้โค้ด python ตัวเดียวกับในเว็บ pythonprogramming.net ในการอธิบาย สาเหตุที่เลือกเว็บนี้เพราะมีการสอนเขียนโปรแกรม python ที่เป็นขั้นเป็นตอนเข้าใจง่ายและไม่ใช้ library ในการเทรนโมเดล เหมือนที่เว็บอื่นทำ ซึ่งจะทำให้เข้าใจในตัว K Means ได้มากกว่า
  • โดยอัลกอริทึม K Means มีขั้นตอนดังนี้
    1. กำหนดก่อนว่าจะแบ่งกี่กลุ่มข้อมูล สมมติแบ่งสองกลุ่มข้อมูล K=2 วางจุด Centroid ไว้ตำแหน่งสุ่มใดๆก็ได้สองจุด หรือจะเลือกข้อมูลสองจุดมาเป็น Centroid ก่อนก็ได้
    2. จากนั้นวัดระยะแบบ Euclidean ระหว่างจุดข้อมูลทั้งหมดกับ Centroid ทั้งสองแล้วดูว่าใกล้กับ Centroid กลุ่มไหน ก็ให้กำหนดข้อมูลให้อยู่กลุ่มข้อมูลชุดนั้น
    3. จากนั้นให้ทำการหาระยะทางเฉลี่ย(Means) ของข้อมูลในกลุ่มทั้งหมดเพื่อหาจุด Centroid ของกลุ่มนั้นใหม่ ถ้า Centroid ไม่เปลี่ยนไปกว่าเดิมให้ทำการหยุด(tol) ตรวจสอบว่าทำครบรอบที่กำหนดแล้วหรือยัง(max_iter) ถ้ายังให้กระโดดไปที่ ข้อ 2

Line 1-12 จะเป็นการ import library ที่ชื่อว่า matplotlib เพื่อใช้ในการวาดกราฟและกำหนดข้อมูลที่ใช้ในการทำ K Means ภาพด้านล่างแสดงข้อมูลหกจุด ถ้ามองด้วยตาเปล่าจะสังเกตุว่าถ้าเราแบ่งข้อมูลเป็นสองชุดจะได้ชุดที่อยู่มุมซ้ายล่างสามจุด กับ ชุดที่อยู่มุมขวาบนสามจุด

figure_1

 

Line 14 เป็นการกำหนดชุดสีให้แต่ละกลุ่มข้อมูล
คลาส K_Means
Line 17-20  กำนหนดคอนสตัคเตอร์ของคลาส K_Means ที่สามารถกำหนดจำนวนคลัสเตอร์ K ค่า tolerance(เปอร์เซนต์การเปลี่ยนแปลงระหว่างค่า centroid เก่าและ centroid ใหม่ ถ้าเปลี่ยนน้อยกว่าค่านี้ให้หยุดการทำงาน) และค่า max_iter (จำนวนรอบในการหา centroid) โดยเมื่อคลาสนี้ถูกสร้างอินสแตนท์จะกำหนดค่าดีฟอล์ท ของ K เป็น 2 ค่า tolerance เป็น 0.001 และค่า max_iter=300
เมธอด fit
Line 22-24 เลือกข้อมูล k จุดเพื่อเป็น centroid เริ่มต้นของแต่กลุ่มข้อมูล
Line 26 ทำการวนซ้ำจนกว่าจะครบจำนวนตาม max_iter
Line 27-29 กำหนดดิกชันนารี่ชื่อ Classifications เพื่อเก็บกลุ่มข้อมูล จำนวน k กลุ่ม สมมติ k=2 ตามโค้ดด้านบน ชุดข้อมูลที่อยู่ในกลุ่มของ centroid แรก จะอยู่ใน Classifications[0] ข้อมูลที่อยู่ในกลุ่มของ centroid ที่สอง จะอยู่ใน Classifications[1]
Line 31-34 นำข้อมูลแต่ละตัว มาหาระยะทางแบบยูคลีเดียน(ใช้คำสั่ง np.linalg.norm)กับ centroid ทั้งหมด แล้วดูว่าใกล้กับ centroid ไหน ให้ทำการเอาข้อมูลตัวนั้นใส่ลงไปในดิกชันนารี่ Classification ตามที่ได้สร้างไว้ใน Line 27-29
Line 36 กำหนดตัวแปร  prev_centroids เพื่อเก็บตำแหน่ง centroid ทั้งหมดเพื่อใช้ในการเปรียบเทียบกับ centroid ชุดใหม่ที่เกิดขึ้นในขั้นตอนต่อไป
Line 38-39 ในแต่ละกลุ่มของดิกชันนารี่ classifications ให้หาค่าเฉลี่ย(np.average)ของข้อมูลทุกตัวในกลุ่มเพื่อกำหนดจุด centroid ของกลุ่มใหม่
Line 41-51 กำหนดตัวแปร optimization ให้เป็น true จากนั้นทำการตรวจสอบว่า centroid ครั้งที่แล้วกับ centroid ปัจจุบัน มีการเปลี่ยนแปลงเกินกว่าค่า tolerance ถ้าใช่ ให้กำหนดตัวแปร optimization ให้เป็น false เพื่อจะได้ขึ้นไปวนลูปใหม่ ถ้าไม่ ให้แสดงว่ามีการเปลี่ยนแปลงระหว่าง centroid เก่าและใหม่น้อยมากในขอบเขตที่ยอมรับได้ ให้ออกจากลูบแม้ว่าจะทำงานไม่ครบรอบตามที่กำหนดไว้ในตัวแปร max_iter ก็ตาม
Line 53-56 เป็นเมธอด predict คือเป็นการเอาข้อมูลที่เป็นในส่วนของการเทสมาทดสอบว่าข้อมูลนั้นๆอยู่ในกลุ่มคลัสเตอร์ใด ต้องทำการเทรนโมเดลก่อน เมธอดนี้ถึงจะทำงานได้ถูกต้อง เมธอดนี้คล้ายคลึงกับ Line 31-33 

ในส่วนของคลาส K_Means ก็จบแต่เพียงเท่านี้

Line 58-80 จะเป็นการสร้างอินสแตนท์ของคลาส K_Means และส่งข้อมูลในตัวแปร X ไปเทรน จากนั้นทำการวาดภาพ โดยกำหนดจุดที่เป็น centroid ของแต่ละกลุ่มข้อมูลให้เป็นสีดำ ส่วนข้อมูลที่อยู่ในตัวแปร X หลังจากเทรนแล้ว จะแบ่งเป็นสองกลุ่มคือสีเขียวและสีแดง แทนด้วยสัญลักษณ์ X

figure_2

 

จากนั้นเราต้องการเทสโดยเอาข้อมูลในตัวแปร unknown มาทำการ predict ผ่านโมเดลที่เทรนแล้วเพื่อดูว่าข้อมูลแต่ละตัวในตัวแปร unknown อยู่ในกลุ่มคลัสเตอร์ใด โดยใช้สีในการบ่งบอกกลุ่มคลัสเตอร์ ตัวแปร unknown จะใช้สัญลักษณ์ * ในการแสดงบนกราฟ

Ref :
[1]https://pythonprogramming.net/k-means-from-scratch-machine-learning-tutorial/
[2]https://pythonprogramming.net/k-means-from-scratch-2-machine-learning-tutorial/?completed=/k-means-from-scratch-machine-learning-tutorial/

Leave a Reply

Your email address will not be published. Required fields are marked *