Basic Data Science : การหาค่า k ที่เหมาะสม

เฮฮา ก่อนอ่าน

https://xkcd.com/2200/

ถ้าเราเปิดตำราเกี่ยวกับ Machine Learning หรือ Data Science จะต้องได้พบกับเรื่องของ k-nearest neighbors, k-means (clustering, regression,classification)  เกือบทุกเล่ม เพราะเป็น algorithm ที่ถูกใชังานบ่อยมากในระบบวิเคราะห์ข้อมูล
algorithm นี้พยายามข้อมูลที่จัดเก็บมาได้ออกเป็น k กลุ่มข้อมูล โดยอาศัยหลักการของการวัดระยะทางระหว่างข้อมูล[6] ค่าของ k ถือว่าเป็น hyper parameter [5]  หรือค่าที่ต้องได้รับการกำหนดค่าไว้ก่อนที่กระบวนการเรียนรู้ของ machine จะดำเนิน คำถามที่ข้อเขียนนี้พยายามจะตอบคือ เราจะหาค่า k ที่เหมาะสมได้อย่างไร

Cluster Centroid [8]

รูปที่ 1

รูปที่ 1 แสดงตัวอย่างการแบ่งกลุ่มข้อมูล (toy dataset) ออกเป็น 4 กลุ่ม แต่ละกลุ่มจะมีจุดหนึ่งที่เกิดจากค่าเฉลี่ย หรือแนวโน้มเข้าสู่ศูนย์กลางของข้อมูล ของระยะทางระหว่างข้อมูลเรียกว่า จุด cluster centroid

cluster centroid เกิดจากการคำนวณ ดังนั้นค่าของจุดนี้อาจไม่ตรงกับค่าของข้อมูลดิบค่าใดเลยก็ได้


Cluster distortion [4]
ถ้าให้ชุดข้อมูลถูกแบ่งออกเป็น k กลุ่ม
 $x_k^i$ แทนข้อมูลตำแหน่งที่ i ในกลุ่มที่ k
 ${\mu }_k$ แทนจุด centroid ของกลุ่มที่ k
$N_k$ แทนจำนวนข้อมูลในกลุ่มที่   k
ค่า cluster distortion หาได้จาก

$I_k=\sum _{i=1}^{N_j}d(x_i^k,{\mu }_k{)}^2$

ค่า  $I_k$ คือผลรวมของกำลังสองของระยะทางของข้อมูลกับจุด Centroid ของกลุ่มที่ k  และเรานิยามค่าผลรวมของ Cluster distortion ทั้งหมดใน sample space  คือ

$S_k=\sum _{j=1}^k{I}_j$

Elbow Method

หากเรานำข้อมูล  N มาทดลองแบ่งข้อมูลออกเป็น k กลุ่ม โดยให้ k มีค่าไล่ไปตั้งแต่ 1,2,3,...,N ในการทดลองแบ่งแต่ละครั้งทำการคำนวณหาค่า $S_k$ เก็บไว้ แล้วนำมา plot ระหว่างค่า $S_k$  กับ k จะได้กราฟออกมาคล้ายกับรูปที่ 2 (เรียกว่า scree plot [2]) ซึ่งมีลักษณะเฉพาะตัวคือเหมือนกับข้อศอก จึงมีชื่อเรียกว่า elbow method

รูปที่ 2

จุดที่ให้ค่า k ที่เหมาะสมคือจุดที่ความชันของกราฟมีการเปลี่ยนแปลงเข้าสู่แนวราบ จากรูปตำแหน่ง k ที่เหมาะสมน่าจะอยู่ระหว่างค่าในกรอบสีแดงตามรูปที่ 3

รูปที่ 3 บริเวณที่ให้ค่า K ที่เหมาะสมคือบริเวณที่ความชันเริ่มเปลี่ยนเข้าสู่แนวราบ

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

1) วิธีของ Asanka Perera [1]
ใช้สร้างเส้นที่เรียกว่า envelope line ซึ่งก็คือเส้นตรงที่ลากจากจุดเริ่มต้นไปยังจุดสุดท้ายของ scree plot ดังรูปที่ 4

รูปที่ 4

จากนั้นทำการหาระยะห่างระหว่างจุดสีน้ำเงิน (แทนความสัมพันธ์ระหว่าง K,D) ก้บ envelope line ซึ่งหาได้จากสูตร [3]

$d=\frac{\mid (y_2-y_1)x_0-(x_2-x_1)y_0+x_2{y}_1-x_1{y}_2\mid }{\sqrt{[2](x_2-x_1{)}^2+(y_2-y_1{)}^2}}$

หรือ

$d_K=\frac{\mid (S_K-S_1)K-(N-1)S_1+N{S}_1-S_K\mid }{\sqrt{[2](N-1{)}^2+(S_K-S_1{)}^2}}$

โดยที่

$K_{optimum}=argmax(d_k)$

2 วิธีของ Pham-Dimov-Nguyen  [4]
วิธีนี้อาศัย evaluation function (f(n))  มาช่วยในการพิจารณาหาค่า K ซึ่งกำหนดไว้ตามนี้

$f(n)=\{\begin{array}{ll}1& \text{if }K\text{ =1}\\ \frac{S_K}{{\alpha }_K{S}_{K-1}}& \text{if }{S}_{K-1}>0,\mathrm{\forall }K>0\\ 1& \text{if }{S}_{K-1}\text{=0,}\mathrm{\forall }K>0\end{array}$

และ
${\alpha }_K=\{\begin{array}{ll}1-\frac{3}{4N_d}& \text{if }K\text{ =2,}{N}_d>1\\ {\alpha }_{K-1}+\frac{1-{\alpha }_{K-1}}{6}& \text{if }K>2\text{ , }{N}_d\text{ >1}\end{array}$

โดยที่

$K_{optimum}=argmim(f(n))$

เมื่อ
 $N_d$ คือ จำนวน data attributes หรือจำนวน features ของ dataset
$\alpha$ คือ weight factor สังเกตุว่าจะมีการประมาณค่าของ $f(n)$ โดยอิงค่าของจาก $S_{K-1}$ และ ${\alpha }_K$

มีข้อสังเกตุจาก [4] คือ ในกรณีที่ได้ค่า  f(n) < 0.85 จะใช้ค่า K เป็น 1

3. Silhouette Method [9]
วิธีการนี้ไม่ได้บอกว่าจำนวน k เป็นเท่าใด แต่จะบอกว่า k ที่ใช้ขณะนี้ดีพอหรือไม่ โดยใช้การเทียบกันระหว่างระยะทางจากข้อมูลใน cluster เดียวกัน (intra cluster) กับข้อมูลที่อยู่ต่าง cluster กัน (nearest cluster)

การคำนวณ
สำหรับข้อมูลตำแหน่งที่ i เราวัดความเหมือน (กำหนดให้

$a_i=\frac{1}{\mid C_i\mid -1}\sum _{j\in C_i,i\ne j}^{}d(i,j)$

เมื่อ
$a_i$ คือ ค่าเฉลี่ยของระยะห่างจากข้อมูล i กับข้อมูล j ที่อยู่ใน cluster เดียวกัน
$\mid C_i\mid$ คือ จำนวนข้อมูลที่มีอยู่ใน  cluster
$d(i,j)$ คือ ระยะห่างจากข้อมูลตำแหน่งที่ i กับข้อมูล j ที่อยู่ใน cluster เดียวกัน

นอกจากนี้เรายังได้กำหนดค่าความต่าง (dissimilarity) ของข้อมูล i โดยดูจากค่าเฉลี่ยของระยะห่างข้อมูล i กับข้อมูลอื่นที่ไม่ได้อยู่ร่วม cluster เดียวกัน โดย

$b_i=min\frac{1}{\mid C_k\mid }\sum _{j\in k}^{}d(i,j)$

เรานำค่า $b_i$ ที่น้อยที่สุดมาใช้เท่านั้น เรียกว่าค่านี้ว่า nearest neighbor ของ i

แล้วกำหนดค่า silhouette value ดังนี้

 $s_i=\frac{b_i-a_i}{max(ai,bi)}$

หรือ อาจเขียนได้เป็น

$s_i=\{\begin{array}{ll}1-\frac{a_i}{b_i}& ,a_i<b_i\\ 0& ,a_i=b_i\\ \frac{b_i}{a_i}-1& ,a_i>b_i\end{array}$

ค่า $s_i$ ที่ได้จะมีค่าระหว่าง -1 ถึง  1 ซึ่งตีความได้ดังนี้

• เข้าใกล้ 1 มากเท่าใดแสดงว่าข้อมูล i อยู่ห่างจาก nearest neighbor มากเท่านั้น
• มีค่าเป็น 0 แสดงว่าข้อมูล i อยู่ ณ ตำแหน่งของเส้นแบ่ง cluster
• มีค่าเข้าใกล้ -1 มากเท่าใดแสดงว่าข้อมูล i อยู่ใกล้ nearest neighbor มากเท่านั้น

------------------------------------
เอกสารอ้างอิง
[1] https://www.linkedin.com/pulse/finding-optimal-number-clusters-k-means-through-elbow-asanka-perera
[2] https://en.wikipedia.org/wiki/Scree_plot
[3] https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line
[4] http://www.ee.columbia.edu/~dpwe/papers/PhamDN05-kmeans.pdf
[5] https://en.wikipedia.org/wiki/Hyperparameter_(machine_learning)
[6] https://raspberrypi-thailand.blogspot.com/2019/09/blog-post.html
[7] https://stats.stackexchange.com/questions/87950/distortion-function-for-k-means-algorithm
[8] https://th.wikipedia.org/wiki/%E0%B9%80%E0%B8%8B%E0%B8%99%E0%B8%97%E0%B8%A3%E0%B8%AD%E0%B8%A2%E0%B8%94%E0%B9%8C
[9] https://en.wikipedia.org/wiki/Silhouette_(clustering)