Basic Data Science : K Means Clustering

K Means Clustering เป็น algorithm ในกลุ่มงาน unsupervised machine learning เป้าหมายเพื่อใช้แบ่งกลุ่มข้อมูลออกเป็นจำนวน k กลุ่ม (k clusters)

Input : 

1. เซตของข้อมูล \( X = \left\{x_1,x_2,x_3,...x_n \right\}  \) 
2. ค่าของ K หรือ จำนวน cluster ที่ต้องการ

Output:

1. เซตของค่ากลาง (centroid) แต่ละ cluster \( C = \left\{c_1,c_2,c_3,...c_k \right\}  \) 
2. เซตของข้อมูลพร้อม label ระบุ cluster \( L = \left\{l(x) \mid x = 1,2,3,..,N \right\}  \) 

การทำงานของ algorithm 

รูปที่ 1

เราอาจแบ่งขั้นตอนการทำงานออกเป็นสองขั้นตอน

1. การจัดข้อมูลให้เข้าไปอยู่ตามกลุ่ม (data assignment) โดยอาศัยการความห่างจากข้อมูลกับ centroid [1]

2. การปรับปรุงค่า centroid ของแต่ละกลุ่ม (centroid update) ซึ่งก็คือค่าเฉลี่ยของค่าที่คำนวณได้จากข้อ 1

\(  C_{new} = \cfrac{\sum_i^{N} d(x_i,C)}{N} \)

เมื่อ \(N \) คือ จำนวนข้อมูลภายใน cluster
 \(x_i \) คือ ข้อมูลภายใน cluster ตำแหน่งที่ i
 \(C \) คือ centroid ของ cluster
 \(d(x_i,C) \) คือ ระยะห่างข้อมูลกับ centroid

การทำงานจะทำงานวนไปมาระหว่างข้อ 1 - 2 จนกว่าจะพบกับเงื่อนไขของการจบการทำงาน เช่น ไม่สามารถหา \(  C_{new}  \) ได้อีก

ตัวอย่างงานหลายอย่างที่ใช้ประโยชน์จาก algorithm นี้ได้แก่

• การแบ่งลูกค้าจากพฤติกรรมการซื้อหรือความสนใจ (ยังไม่ได้ซื้อ)
• จัดกลุ่มสินค้าจากยอดขาย ความสามารถการผลิต
• แบ่งกิจกรรมจากข้อมูล motion sensors
• แบ่งกลุ่มรูปภาพ เพลง 
• แบ่งกลุ่มโรคที่เกิดขึ้นตามกลุ่มต่าง ๆ
• ฯลฯ

การหา K ที่เหมาะสม
เป็นขั้นตอนแรกก่อนที่ต้องทำ วิธีการหาค่า K ที่เหมาะสมศึกษาได้จาก [2]

ตัวอย่าง
ใช้ตัวอย่างข้อมูลจำนวนการกด "likes","shares","love" จากการทำ video live และ photo live ผ่าน Facebook ของร้านค้าปลีกประเภท fashion และ cosmetics จำนวน 10 ราย  [3] ตัวอย่างข้อมูลบางส่วนแสดงในรูปที่ 2 (ข้อมูลบางส่วนถูกตัดออกไป)

รูปที่ 2

1. หา K ในที่นี้จะใช้ silhouette score [2][4]

import operator
import numpy as np
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score
import pandas as pd 


def find_sihouette(data,max_k,min_k = 2):
     # place holder for sihouette score
     si = dict()

     # compute si score for every assigned k
     for k in range(min_k,max_k,1):
          try:
               kmeans = KMeans(n_clusters=k).fit(data)
               pred = kmeans.predict(data)
               s_avg = silhouette_score(data, pred)
               si[k] = s_avg
          except:
               pass
   
     # find max si
     max_si = (max(si.items(), key=operator.itemgetter(1))[0])  
     return max_si,si[max_si] 

find_sihouette รับ parameter 3 ตัวคือ
data คือ array ของข้อมูลดิบ
max_k คือ k มากที่สุดที่เราต้องการ ต้องมีค่าไม่เกินจำนวนของข้อมูล
min_k คือ   k  น้อยที่สุดที่ต้องการให้เริ่มการคำนวณ มีค่าตั้งแต่ 2  ขึ้นไป

หากเรากำหนดให้ k =1 นั้นคือข้อมูลทั้งหมดจะถูกจัดอยู่ใน cluster เดียวกันทั้งหมด ก็จะไม่มีความหมายใดๆ  และค่า k จะมีค่ามากกว่าจำนวนข้อมูลที่มีอยู่ไม่ได้เช่นกัน

การทำงานคือการวนรอบหาค่า silhouette score (si) สำหรับทุกค่า k ไล่ตั้งแต่ k_min ไปยัง k_max แล้วเก็บไว้ จากนั้นทำการหาค่า k ที่เหมาะสมคือ k ที่ให้ค่า si ที่สูงสุด

#load data from csv

data = pd.read_csv('Lives.csv')

# find optimum k
num_data = data.shape[0]
k_opt = find_k_sihouette(data.loc[:,['num_shares','num_likes','num_loves']],max_k=num_data,min_k=2)

ได้ผลลัพธ์

k_opt = (2, 0.8538023973556131)

เราได้ค่า K ที่เหมาะสมกับ data ชุดนี้คือ 2 ด้วย silhouette score 0.853

2. Data assignment คือการจัดให้ข้อมูลเข้าไปอยู่ใน cluster ที่เหมาะสม ในที่นี้จะใช้  KMeans module จาก sklearn [5]

kmeans = KMeans(n_clusters=k_opt[0]) # n cluster = 2
kmeans.fit(data.loc[:,['num_shares','num_likes','num_loves']])
labled = kmeans.predict(data.loc[:,['num_shares','num_likes','num_loves']])
print(labled)

ค่าของตัวแปร labeled คืเซตของหมายเลข cluster ของข้อมูล [0,1] เรียงลำดับตามข้อมูลที่นำเข้า ตัวอย่างข้อมูลที่ติดตั้ง labeld ของ cluster แสดงในรูปที่ 3

รูปที่ 3

ต่อไปหาค่าของ centroid ของแต่ละ cluster

centroids = kmeans.cluster_centers_
print(centroids) 

ผลที่ได้

รูปที่ 4

จากรูปที่ 4 จะเห็นว่า cluster 0 คือกลุ่มที่มีค่าของจำนวนครั้งการกด "likes","shares" และ "loves" ต่ำกว่า cluster 1

รูปที่ 5

ในรูปที่ 5 เมื่อนำเอา centroid ของทั้งสอง cluster ทั้งสองมา plot ดู จุดสีแดงแทน centroid ของ cluster 0 จุดสีน้ำเงินแทนตำแหน่งของ centroid ของ cluster 1 ซึ่งจะเห็นว่าตำแหน่งค่อนข้างอยู่ห่างกัน

รูปที่ 6

รูปที่ 6 เป็นมุมมองอีกด้านหนึ่งเมื่อเทียบกับรูปที่ 5 แสดงให้เห็นว่าเมื่อนำเอาข้อดิบมา plot ทับลงไป ข้อมูลส่วนใหญ่ไปรวมตัวกันใน cluster 0 มีข้อมูลเพียงส่วนน้อยที่อยู่ใน cluster 1 และมีการกระจายตัวสูงมาก

ข้อสรุป
1. K Means Clustering เป็น algorithm ใช้แบ่งข้อมูลตัวอย่างออกเป็นจำนวน k กลุ่ม ค่าของ K จำเป็นต้องมีการกำหนดขึ้นมาก่อน ซึ่งมีวิธีการช่วยกำหนดค่า K  หลังจากการประมวลผลแล้วสิ่งที่ได้คือ เซตของ centroid ของทุก cluster และ ข้อมูลตัวอย่างพร้อมหมายเลข cluster
2. กรณีที่ข้อมูลไม่ได้แบ่งกลุ่มตามธรรมชาติที่ชัดเจน algorithm นี้อาจล้มเหลวได้
3. ความเร็วในการประมวลผลขึ้นกับจำนวนตัวอย่าง
4. ค่าของ k อาจมีการเปลี่ยนแปลงได้ หากมีการเพิ่มข้อมูลใหม่เข้ามา

-----------------------------
อ้างอิง
[1] https://somchaisom.blogspot.com/2019/09/blog-post.html
[2] https://somchaisom.blogspot.com/2019/09/k.html
[3] https://archive.ics.uci.edu/ml/datasets/Facebook+Live+Sellers+in+Thailand
[4] https://scikit-learn.org/stable/modules/generated/sklearn.metrics.silhouette_score.html#sklearn.metrics.silhouette_score
[5] https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html