ml/ library Learn by doing
Algorithm catalog/UNSUPERVISED · CLUSTERING
ALGORITHM 29 · PYTHON / JAVASCRIPT

Mini Batch K-Means

ขยับศูนย์กลางทีละชุดเล็ก เพื่อทำงานกับข้อมูลจำนวนมาก

LEARNING LEVEL2
ต่อยอดโดยตรงควรรู้มาก่อน · K-Means Clustering และ mini batch optimization
ลองใน Playground

01Overall Concept

OVERALL CONCEPT

ไอเดียหลัก — Mini Batch K-Means แบ่งกลุ่มโดยใช้ตัวอย่างครั้งละส่วนเล็ก ๆ มาอัปเดต centroid แทนการอ่านทุกแถวในทุกรอบ จึงลดต้นทุนต่อการอัปเดตและใช้กับข้อมูลใหญ่ได้สะดวกขึ้น คำตอบใกล้เคียง K-Means แต่ไม่จำเป็นต้องเหมือนกัน

ลองนึกภาพว่า — ถ้าต้องหาจุดนัดพบของคนทั้งเมือง เราอาจสุ่มถามคนทีละกลุ่มแล้วค่อย ๆ ขยับจุดนัดพบตามข้อมูลที่สะสม แทนการสำรวจทุกคนใหม่ทุกครั้ง

ตัวอย่างการนำไปใช้ — แบ่งกลุ่มลูกค้าจำนวนมาก จัดกลุ่มเวกเตอร์เอกสาร และทำ color quantization ของภาพที่มีพิกเซลจำนวนมาก

02อธิบายภาษาคนเข้าใจง่ายๆ

เล่าแบบไม่ใช้ศัพท์ยาก

K-Means ปกติอ่านทุกจุดเพื่อจัดกลุ่มแล้วคำนวณศูนย์กลางใหม่ ถ้ามีข้อมูลเป็นล้านจุด การทำแบบนี้ซ้ำหลายรอบอาจใช้เวลามาก

Mini Batch K-Means เลือกมาเพียงชุดเล็กก่อน เช่นครั้งละ 1,024 จุด จัดแต่ละจุดเข้าศูนย์กลางใกล้ที่สุด แล้วขยับศูนย์กลางจากข้อมูลชุดนั้น

การขยับไม่ลืมข้อมูลเก่าทั้งหมด แต่ใช้น้ำหนักตามจำนวนตัวอย่างที่เคยถูกจัดเข้าศูนย์กลาง ถ้าเคยเห็นมาหลายจุดแล้ว จุดใหม่เพียงจุดเดียวจะขยับศูนย์กลางได้น้อยลง

ถ้าศูนย์กลางเดิมเป็น 4 จากข้อมูลสองจุด และได้รับจุดใหม่ที่ 10 ค่าเฉลี่ยสะสมจะเป็น 4+(10−4)/3=6 นี่คือภาพง่าย ๆ ของการอัปเดตทีละตัวอย่าง

ชุดเล็กทำงานต่อรอบน้อยแต่แกว่งได้มาก ชุดใหญ่ใช้เวลาในรอบนั้นมากขึ้นและมักนิ่งขึ้น ต้องดูทั้งคุณภาพกลุ่มและเวลารวม ไม่ใช่บอกว่าชุดเล็กเร็วกว่าเสมอโดยไม่ดูจำนวนรอบ

ภาพจำ: ค่อย ๆ ปรับจุดนัดพบจากคนกลุ่มเล็กที่ผลัดกันเข้ามา พร้อมเก็บความรู้จากคนก่อนหน้า

03How it works

ค่อยๆ ทำไปด้วยกัน ตั้งแต่ข้อมูลแถวแรกจนถึงการตรวจคำตอบ

  1. เตรียม X โดยไม่ส่งคำตอบ

    รับตารางตัวเลขที่แต่ละแถวเป็นวัตถุหนึ่งชิ้น เลือก feature และปรับสเกลให้ระยะ Euclidean มีความหมาย การแบ่งกลุ่มไม่ใช้ label ระหว่าง fit แม้ข้อมูลสาธิตจะสร้างจากกลุ่มที่รู้ไว้ก็ตาม

  2. ตั้งจำนวนกลุ่มและจุดเริ่มต้น

    เลือก n_clusters=3 และกำหนด random_state เพื่อทำซ้ำได้ scikit-learn รองรับ init="k-means++" และการลองเริ่มหลายครั้ง ส่วน Playground ใช้จุดเริ่มต้นคงที่แล้วสุ่ม batch ด้วย seed คงที่

  3. สุ่มชุดเล็กและจัดเข้าศูนย์กลาง

    ในแต่ละรอบเลือก batch_size แถว แล้ววัดระยะกำลังสองไปยัง centroid จัดแต่ละแถวให้ศูนย์กลางใกล้ที่สุด จากนั้นเพิ่มตัวนับจำนวนแถวที่ centroid นั้นรับไว้

  4. อัปเดตค่าเฉลี่ยสะสม

    ถ้าศูนย์กลางรับตัวอย่างใหม่เป็นลำดับที่ n ให้ c_new=c_old+(x−c_old)/n ทำซ้ำหลายรอบ Playground ใช้ 40 รอบคงที่ ส่วน MiniBatchKMeans ใน Python มีเกณฑ์หยุดและการจัดการศูนย์กลางที่สมาชิกน้อยเพิ่มเติม ผลจึงอาจต่างกัน

  5. ตรวจกลุ่มหลังฝึก

    ใช้ predict หรือ fit_predict เพื่อกำหนด label ให้ข้อมูลทุกแถว และวัด inertia=Σ||x−c_label||² ลองหลาย seed, batch_size และ K พร้อมดู silhouette เมื่อมีเงื่อนไขเหมาะสม หากใช้ partial_fit กับข้อมูลเป็นชุด ต้องจัดการการอ่านชุดและการปรับสเกลให้สม่ำเสมอเอง

เปิดตัวอย่างโค้ดเพื่อลองทำตาม →ตัวอย่างตัวเลขในเรื่องใช้ช่วยอธิบาย ส่วนโค้ดและ Playground ใช้ชุดข้อมูลสาธิตของแต่ละหน้าอ่านเอกสารอ้างอิงของเทคนิคนี้ ↗

ข้อมูล พารามิเตอร์ และภาพรวมการคำนวณ

DATA INX · features · no target ycentroid เดิม 4 · เคยรับ 2 จุด · จุดใหม่ 10
CALCULATEMini Batch K-Means
n_clustersbatch_sizemax_iter
RESULTcluster labels + centerscentroid ใหม่ = 4+(10−4)/3 = 6
เส้นทางของข้อมูล: จากค่าที่รับเข้า ผ่านการคำนวณด้วยพารามิเตอร์ ไปเป็นผลลัพธ์
INPUT

ข้อมูลที่รับเข้ามา

X เป็นตาราง feature เชิงตัวเลข ไม่มี y ที่ใช้ฝึก

centroid เดิม 4 · เคยรับ 2 จุด · จุดใหม่ 10
PARAMETERS

พารามิเตอร์ที่ใช้

n_clusters
จำนวนศูนย์กลาง K ที่ต้องการ
batch_size
จำนวนแถวต่อ mini batch
max_iter
งบการฝึกสูงสุด; Python มีเกณฑ์หยุดเพิ่มเติม
OUTPUT

ผลลัพธ์ที่ได้

centroid, label ของข้อมูล และ inertia

centroid ใหม่ = 4+(10−4)/3 = 6
CALCULATION

คำนวณทีละขั้น

  1. 01

    สุ่ม batch และหาศูนย์กลางใกล้ที่สุด

  2. 02

    เพิ่ม count แล้วอัปเดต c ← c+(x−c)/count

  3. 03

    ทำนายทุกแถวและรวม squared distance เป็น inertia

ควรรู้อีกนิด — batch_size ไม่ใช่จำนวนกลุ่ม และการใช้ fit ยังรับ X ทั้งชุดเข้าฟังก์ชัน ถ้าต้องการทยอยอ่านข้อมูลจากดิสก์จริง ต้องจัด batch แล้วเรียก partial_fit โดยเตรียมชุดแรกให้มีอย่างน้อย K แถว

04Make it yours

Python · scikit-learn
# ติดตั้ง: pip install numpy scikit-learn# ดาวน์โหลด sample.csv จากหน้านี้ แล้ววางไว้ข้างสคริปต์import numpy as np data = np.genfromtxt("mini-batch-k-means-sample.csv", delimiter=",", skip_header=1)X = data[:, :2] from sklearn.cluster import MiniBatchKMeansfrom sklearn.metrics import silhouette_score model = MiniBatchKMeans(n_clusters=3, batch_size=15,                        n_init=10, max_iter=100, random_state=42)labels = model.fit_predict(X)  # ไม่ส่ง label เดิมเข้า fitprint("Centers:", model.cluster_centers_)print("Inertia:", model.inertia_)if 1 < len(np.unique(labels)) < len(X):    print("Silhouette:", silhouette_score(X, labels))# ไลบรารีมี initialization/เกณฑ์หยุดต่างจาก Playground ที่ตรึง 40 รอบ

โค้ดเปลี่ยนตามค่าที่เลือกใน Playground · แต่ละภาษาใช้ข้อมูลตัวอย่างตามที่ระบุในโค้ด

05Learn by playing

ปรับ ขนาด mini batch แล้วสังเกตรูปแบบคำทำนายและตัวชี้วัดที่คำนวณใหม่ทันที

Sample dataset / Unlabeled points● คำนวณใหม่เมื่อปรับค่า
จำนวนจุดที่สุ่มต่อรอบ · K=3 · 40 รอบคงที่ จึงใช้งานคำนวณรวมต่างกัน
กากบาทดำคือ centroid จาก mini batch123กากบาท = centroid · สี = กลุ่มที่เรียนรู้
Inertia47665.738
จำนวนจุดที่สุ่มใช้600 · 40 รอบ
พารามิเตอร์ที่ลอง15

Playground เป็น implementation เพื่อการเรียนรู้ที่คำนวณในเบราว์เซอร์ ส่วนโค้ด Python ใช้ scikit-learn จึงอาจให้ค่าต่างกันเล็กน้อยจากรายละเอียดการ optimize และค่าเริ่มต้นของไลบรารี ผลนี้ไม่ใช่ benchmark บนข้อมูลจริง