เฮฮา ก่อนอ่าน
ถ้าเราเปิดตำราเกี่ยวกับ 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 แสดงตัวอย่างการแบ่งกลุ่มข้อมูล (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 \) คือผลรวมของกำลังสองของระยะทางของข้อมูลกับจุด Centroid ของกลุ่มที่ k และเรานิยามค่าผลรวมของ Cluster distortion ทั้งหมดใน sample space คือ
Elbow Method
หากเรานำข้อมูล N มาทดลองแบ่งข้อมูลออกเป็น k กลุ่ม โดยให้ k มีค่าไล่ไปตั้งแต่ 1,2,3,...,N ในการทดลองแบ่งแต่ละครั้งทำการคำนวณหาค่า \( S_k \) เก็บไว้ แล้วนำมา plot ระหว่างค่า \( S_k \) กับ k จะได้กราฟออกมาคล้ายกับรูปที่ 2 (เรียกว่า scree plot [2]) ซึ่งมีลักษณะเฉพาะตัวคือเหมือนกับข้อศอก จึงมีชื่อเรียกว่า elbow method
จุดที่ให้ค่า k ที่เหมาะสมคือจุดที่ความชันของกราฟมีการเปลี่ยนแปลงเข้าสู่แนวราบ จากรูปตำแหน่ง k ที่เหมาะสมน่าจะอยู่ระหว่างค่าในกรอบสีแดงตามรูปที่ 3
วิธีการนี้ง่ายแต่ก็ขึ้นกับมุมมองและประสบการณ์ของผู้พิจารณา และเป็นไปได้ว่ากราฟที่ได้ในบางกรณีอาจจะไม่สามารถระบุช่วงของ k ได้เลย ดังนั้นจึงได้มีการคิดวิธีที่สามารถระบุได้ k ได้ชัดเจนและสามารถนำไปทำเป็นระบบ automatic ได้ วิธีที่พบได้บ่อยคือ
1) วิธีของ Asanka Perera [1]
ใช้สร้างเส้นที่เรียกว่า envelope line ซึ่งก็คือเส้นตรงที่ลากจากจุดเริ่มต้นไปยังจุดสุดท้ายของ scree plot ดังรูปที่ 4
จากนั้นทำการหาระยะห่างระหว่างจุดสีน้ำเงิน (แทนความสัมพันธ์ระหว่าง K,D) ก้บ envelope line ซึ่งหาได้จากสูตร [3]
หรือ
โดยที่
2 วิธีของ Pham-Dimov-Nguyen [4]
วิธีนี้อาศัย evaluation function (f(n)) มาช่วยในการพิจารณาหาค่า K ซึ่งกำหนดไว้ตามนี้
\( f(n) = \left\{ \begin{array}{l l} 1 & \quad \text{if $K$ =1}\\ S_K \over \alpha_K S_{K-1} & \quad \text{if $S_{K-1}$} > 0, \forall K > 0\\ 1 & \quad \text{if $S_{K-1}$=0,}\forall K > 0 \\ \end{array} \right. \)
และ
\( \alpha_{K} = \left\{ \begin{array}{l l} 1 - {3 \over 4N_d} & \quad \text{if $K$ =2,$N_d > 1$}\\ \alpha_{K-1} + {{1 -\alpha_{K-1}} \over {6}} & \quad \text{if $K>2$ , ${N_d}$ >1} \end{array} \right. \)
โดยที่
เมื่อ
\( 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 \) คือ ค่าเฉลี่ยของระยะห่างจากข้อมูล i กับข้อมูล j ที่อยู่ใน cluster เดียวกัน
\( \mid C_i \mid \) คือ จำนวนข้อมูลที่มีอยู่ใน cluster
\( d (i,j) \) คือ ระยะห่างจากข้อมูลตำแหน่งที่ i กับข้อมูล j ที่อยู่ใน cluster เดียวกัน
นอกจากนี้เรายังได้กำหนดค่าความต่าง (dissimilarity) ของข้อมูล i โดยดูจากค่าเฉลี่ยของระยะห่างข้อมูล i กับข้อมูลอื่นที่ไม่ได้อยู่ร่วม cluster เดียวกัน โดย
เรานำค่า \( b_i\) ที่น้อยที่สุดมาใช้เท่านั้น เรียกว่าค่านี้ว่า nearest neighbor ของ i
แล้วกำหนดค่า silhouette value ดังนี้
หรือ อาจเขียนได้เป็น
ค่า \( s_i\) ที่ได้จะมีค่าระหว่าง -1 ถึง 1 ซึ่งตีความได้ดังนี้
------------------------------------
เอกสารอ้างอิง
[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)
 |
| 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 |
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 |
 |
| รูปที่ 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_2y_1 - x_1y_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 + NS_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) = \left\{ \begin{array}{l l} 1 & \quad \text{if $K$ =1}\\ S_K \over \alpha_K S_{K-1} & \quad \text{if $S_{K-1}$} > 0, \forall K > 0\\ 1 & \quad \text{if $S_{K-1}$=0,}\forall K > 0 \\ \end{array} \right. \)
และ
\( \alpha_{K} = \left\{ \begin{array}{l l} 1 - {3 \over 4N_d} & \quad \text{if $K$ =2,$N_d > 1$}\\ \alpha_{K-1} + {{1 -\alpha_{K-1}} \over {6}} & \quad \text{if $K>2$ , ${N_d}$ >1} \end{array} \right. \)
โดยที่
\( 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 เราวัดความเหมือน (กำหนดให้
\( \begin{equation}
a_i =\cfrac{1}{\mid C_i \mid -1}\sum_{j \in C_i,i \neq j}^{}d(i,j)
\end{equation} \)
เมื่อ
\( a_i \) คือ ค่าเฉลี่ยของระยะห่างจากข้อมูล i กับข้อมูล j ที่อยู่ใน cluster เดียวกัน
\( \mid C_i \mid \) คือ จำนวนข้อมูลที่มีอยู่ใน cluster
\( d (i,j) \) คือ ระยะห่างจากข้อมูลตำแหน่งที่ i กับข้อมูล j ที่อยู่ใน cluster เดียวกัน
นอกจากนี้เรายังได้กำหนดค่าความต่าง (dissimilarity) ของข้อมูล i โดยดูจากค่าเฉลี่ยของระยะห่างข้อมูล i กับข้อมูลอื่นที่ไม่ได้อยู่ร่วม cluster เดียวกัน โดย
\( \begin{equation}
b_i =\min \cfrac{1}{\mid C_k \mid}\sum_{j \in k}^{}d(i,j)
\end{equation} \)
เรานำค่า \( b_i\) ที่น้อยที่สุดมาใช้เท่านั้น เรียกว่าค่านี้ว่า nearest neighbor ของ i
แล้วกำหนดค่า silhouette value ดังนี้
\( \begin{equation}
s_i = \cfrac{b_i - a_i}{\max(ai,bi)}
\end{equation} \)
หรือ อาจเขียนได้เป็น
\(
s_i =\begin{cases}
1- \cfrac{a_i}{b_i} &, a_i < b_i\\
0 &, a_i = b_i \\
\cfrac{b_i}{a_i} -1&,a_i>b_i
\end{cases}
\)
ค่า \( 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)
ความคิดเห็น
แสดงความคิดเห็น