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

k-Medoids

เลือกสมาชิกจริงมาเป็นตัวแทนแต่ละกลุ่ม

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

01Overall Concept

OVERALL CONCEPT

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

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

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

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

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

K-Means สร้างจุดกลางขึ้นมาจากค่าเฉลี่ย ส่วน k-Medoids ต้องเลือกสมาชิกที่มีอยู่จริงมาเป็นหัวหน้ากลุ่ม เราจึงหยิบภาพหรือสินค้า ณ จุดนั้นมาแสดงให้คนดูได้เลย

สมมติเพื่อนอยู่ที่ตำแหน่ง 0,1,2,3 และ 20 ถ้าใช้ค่าเฉลี่ยจะได้ 5.2 ซึ่งไม่ใช่บ้านใคร แต่ถ้าเลือกบ้าน 2 ระยะทางรวมจะเป็น 22 และเป็นค่าต่ำสุดในตัวเลือกเหล่านี้

เมื่อมีหลายกลุ่ม เราเลือกบ้านตัวแทน K หลัง แล้วให้แต่ละคนไปบ้านตัวแทนที่ใกล้ที่สุด จากนั้นลองสลับว่าถ้าเปลี่ยนตัวแทนเป็นคนอื่น ระยะทางรวมจะลดหรือไม่

วิธี PAM ลองสลับตัวแทนกับสมาชิกที่ยังไม่เป็นตัวแทน เลือกการสลับที่ช่วยมากที่สุด แล้วทำซ้ำจนไม่มีการสลับที่ดีขึ้น นี่เป็นการค้นหาคำตอบที่ดีในบริเวณหนึ่ง ไม่ได้ยืนยันว่าดีที่สุดจากทุกชุดตัวแทน

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

ภาพจำ: เลือกตัวแทนจากสมาชิกจริง แล้วลองเปลี่ยนตัวแทนจนการเดินทางรวมสั้นลงไม่ได้อีก

03How it works

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

  1. นิยามระยะที่มีความหมาย

    เริ่มจาก X ตัวเลขที่ปรับสเกลเหมาะสม หรือ D ซึ่งเป็นตารางระยะระหว่างทุกคู่ขนาด n×n ตัวอย่าง Python สร้าง D ด้วย pairwise_distances(metric="euclidean") ตารางนี้โตตาม n² จึงใช้ข้อมูลสาธิตขนาดเล็ก

  2. เลือก K จุดเริ่มต้น

    ใช้ KMedoids(n_clusters=3,metric="precomputed",method="pam",random_state=42) จากแพ็กเกจ kmedoids ซึ่งต้องติดตั้งเพิ่ม แพ็กเกจนี้ไม่ใช่ estimator ที่มากับ scikit-learn หลัก Playground เริ่มจากสมาชิกที่เลือกแบบ deterministic

  3. จัดกลุ่มและรวมต้นทุน

    แต่ละจุดเลือก medoid ที่ระยะน้อยที่สุด คำนวณ J=Σ_i min_m D(i,m) ซึ่งเป็นผลรวมระยะ ไม่ใช่ inertia แบบผลรวมระยะกำลังสองของ K-Means หมายเลขกลุ่มเป็นเพียงรหัส ไม่มีลำดับมากน้อย

  4. ลองสลับสมาชิกตัวแทน

    สำหรับ medoid แต่ละตัว ลองแทนด้วยจุดที่ยังไม่ได้เป็น medoid แล้วคำนวณ J ใหม่ เลือก swap ที่ลด J มากที่สุด ทำซ้ำจนไม่มี swap ที่ดีขึ้น Playground ทำขั้นตอนนี้จริงและแสดงตัวแทนเป็นวงแหวนดำ

  5. อ่านผลและตรวจความเสถียร

    ดู medoid_indices_ เพื่อเปิดตัวอย่างตัวแทน และ labels_ เพื่อดูสมาชิก ลองหลาย seed และ K ประเมิน silhouette จากระยะเดียวกับที่ฝึก พร้อมอ่านความหมายของตัวแทนจริง หากข้อมูลใหญ่มากควรเปรียบเทียบ FasterPAM หรือวิธี sampling

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

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

DATA INX · features · no target yX=[0,1,2,3,20] · K=1
CALCULATEk-Medoids
n_clustersmetricmethod
RESULTcluster labels + centersmedoid=2 · cost=22 · เป็นสมาชิกจริง
เส้นทางของข้อมูล: จากค่าที่รับเข้า ผ่านการคำนวณด้วยพารามิเตอร์ ไปเป็นผลลัพธ์
INPUT

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

X หรือตารางระยะ D ที่สมมาตร ไม่ติดลบ และแนวทแยงเป็นศูนย์สำหรับระยะที่ใช้ในตัวอย่าง

X=[0,1,2,3,20] · K=1
PARAMETERS

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

n_clusters
จำนวนสมาชิกตัวแทน K
metric
ตัวอย่าง Python ใช้ precomputed distance matrix
method
pam ลองสลับ medoid กับสมาชิกอื่น
OUTPUT

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

ดัชนีสมาชิกตัวแทน label กลุ่ม และผลรวมระยะ

medoid=2 · cost=22 · เป็นสมาชิกจริง
CALCULATION

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

  1. 01

    กำหนด K medoids จากจุดข้อมูลจริง

  2. 02

    คำนวณ J=Σระยะถึง medoid ใกล้ที่สุด

  3. 03

    เลือก swap ที่ลด J มากที่สุดจนไม่ดีขึ้น

ควรรู้อีกนิด — ค่า cost ลดลงเมื่อเพิ่ม K ได้อยู่แล้ว จึงไม่ควรเลือก K จาก cost ต่ำสุดอย่างเดียว ส่วน predict สำหรับ metric="precomputed" ต้องรับระยะจากข้อมูลใหม่ถึงข้อมูลฝึกตามรูปแบบของไลบรารี ไม่ใช่ส่ง feature ดิบ

04Make it yours

Python · kmedoids / scikit-learn
# ติดตั้ง: pip install numpy scikit-learn kmedoids# ดาวน์โหลด sample.csv จากหน้านี้ แล้ววางไว้ข้างสคริปต์import numpy as np data = np.genfromtxt("k-medoids-sample.csv", delimiter=",", skip_header=1)X = data[:, :2] from sklearn.metrics import pairwise_distances, silhouette_scorefrom kmedoids import KMedoids # D มีขนาด n × n จึงเหมาะกับข้อมูลสาธิตขนาดเล็กD = pairwise_distances(X, metric="euclidean")model = KMedoids(n_clusters=3, metric="precomputed",                 method="pam", random_state=42)model.fit(D)print("Medoid indices:", model.medoid_indices_)print("Representatives:", X[model.medoid_indices_])print("Labels:", model.labels_)print("Total distance:", D[:, model.medoid_indices_].min(axis=1).sum())if 1 < len(np.unique(model.labels_)) < len(X):    print("Silhouette:", silhouette_score(D, model.labels_, metric="precomputed"))

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

05Learn by playing

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

Sample dataset / Unlabeled points● คำนวณใหม่เมื่อปรับค่า
ตัวแทนต้องเป็นจุดข้อมูลจริง · วงแหวนดำแสดง medoid ของแต่ละกลุ่ม
วงแหวนดำคือ medoid ซึ่งเป็นสมาชิกจริง123วงแหวนดำ = สมาชิกตัวแทนจริง · สี = กลุ่มที่เรียนรู้
Total distance2420.471
PAM swaps2
พารามิเตอร์ที่ลอง3

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