เทคนิคในการจัดกลุ่ม
ในส่วนนี้จะเป็นการอธิบายแนวคิด หลักการ วิธีการทำงาน และตัวอย่างของเทคนิควิธีในการจัดกลุ่มที่สำคัญๆ สามวิธี ได้แก่ การจัดกลุ่ม K-means การจัดกลุ่มแบบ Agglomerative Hierarchy และการจัดกลุ่มแบบ DBSCAN
การจัดกลุ่มแบบ K-means Clustering
K-means คือ หนึ่งในอัลกอริทึมเทคนิคการเรียนรู้โดยไม่มีผู้สอนที่ง่ายที่สุด เพราะเป็นการแก้ปัญหาการจัดกลุ่มที่รู้จักกันทั่วไป โดยอัลกอริทึม K-Means จะตัดแบ่ง (Partition) วัตถุออกเป็น K กลุ่ม โดยแทนแต่ละกลุ่มด้วยค่าเฉลี่ยของกลุ่ม ซึ่งใช้เป็นจุดศูนย์กลาง (centroid) ของกลุ่มในการวัดระยะห่างของข้อมูลในกลุ่มเดียวกัน ในขั้นแรกของการจัดกลุ่มโดยการหาค่าเฉลี่ยแบบเคย์ต้องกำหนดจำนวนกลุ่ม (K) ที่ต้องการ และกำหนดจุดศูนย์กลางเริ่มต้นจำนวน K จุด สิ่งสำคัญในการกำหนดจุดศูนย์กลางเริ่มต้นของแต่ละกลุ่มนี้ ควรจะถูกกำหนดด้วยวิธีที่เหมาะสม เพราะตำแหน่งจุดศูนย์กลางเริ่มต้นที่แตกต่างกันทำให้ได้ผลลัพธ์สุดท้ายแตกต่างกัน ดังนั้นในทางที่ดีควรจะกำหนดจุดศูนย์กลางนี้ให้หางจากจุดศูนย์กลางอื่นๆ ขั้นตอนต่อไปคือสร้างกลุ่มข้อมูลและความสัมพันธ์กับจุดศูนย์กลางที่ใกล้มากที่สุด โดยแต่ละจุดจะถูกกำหนดไปยังจุดศูนย์กลางที่ใกล้เคียงที่สุดจนครบหมดทุกจุด และคำนวณจุดศูนย์กลางใหม่ โดยการหาค่าเฉลี่ยทุกวัตถุที่อยู่ในกลุ่ม หากจุดศูนย์กลางในแต่ละกลุ่มถูกเปลี่ยนตำแหน่ง จะได้จุดมีความสัมพันธ์กับกลุ่มใหม่และใกล้กับจุดศูนย์กลางใหม่ ทำซ้ำแบบนี้ไปเรื่อย ๆ จะสังเกตเห็นว่าผลลัพธ์จากการทำซ้ำแบบนี้ทำให้จุดศูนย์กลางเปลี่ยนตำแหน่งทุกรอบ จนกระทั่งจุดศูนย์กลางจำนวน K จุด ไม่มีการเปลี่ยนแปลงจึงจะสิ้นสุดกระบวนการ
อัลกอริทึมการจัดกลุ่มโดย K-means
1. กำหนดจำนวนกลุ่ม K กลุ่ม และกำหนดจุดศูนย์กลางเริ่มต้นจำนวน K จุด
2. นำวัตถุทั้งหมดจัดเข้ากลุ่มที่มีจุดศูนย์กลางที่อยู่ใกล้วัตถุนั้นมากที่สุด โดยคำนวณจากการวัดระยะห่างระหว่างจุดที่น้อยที่สุด
3. คำนวณจุดศูนย์กลาง K จุดใหม่ โดยหาจากค่าเฉลี่ยทุกวัตถุที่อยู่ในกลุ่ม
4. ทำซ้ำในข้อ 2. จนกระทั่งจุดศูนย์กลางไม่เปลี่ยนแปลง
ข้อดีและข้อเสียของการจัดกลุ่มโดยใช้เทคนิค K-means
ข้อดี
1).เมื่อจำนวนข้อมูลมีจำนวนมาก การหาค่าเฉลี่ยแบบเคย์อาจจะคำนวณได้เร็วกว่าการจัด กลุ่มแบบ Hierarchical (ถ้าจำนวนกลุ่มน้อย)
2).ขั้นตอนการหาค่าเฉลี่ยแบบ k อาจจะได้กลุ่มที่หนาแน่นกว่าการจัดกลุ่มแบบ Hierarchical โดยเฉพาะถ้ากลุ่มเป็นวงกลม
ข้อเสีย
1). ยากในการเปรียบเทียบในการสร้างกลุ่ม (สำหรับความแตกต่างของค่าเริ่มต้น หรือ ผลลัพธ์ค่าของ k)
2). จำนวนที่ตายตัวของกลุ่มสามารถคาดเดาได้ยากกว่าค่า k ควรจะเป็นอะไร
ทำงานได้ไม่ดีในกลุ่มข้อมูลที่ไม่เป็นรูปวงกลม
3). มีข้อจำกัดในเรื่องของขนาด ความหนาแน่น และรูปร่าง
การจัดกลุ่มแบบ Agglomerative Hierarchy (Agglomerative Hierarchical Clustering)
ใน Hierarchical-cluster analysis เราไม่ได้ระบุจำนวนกลุ่มของ Input กล่าวคือ Input ที่เข้ามา คือ (X,s) โดยที่ X เป็นเซตของตัวอย่าง และ s เป็นการวัดความเหมือนของ output จากระบบเป็นลำดับชั้นของกลุ่ม ขั้นตอนส่วนใหญ่สำหรับการจัดกลุ่มลำดับชั้น ไม่ได้ขึ้นอยู่กับแนวคิดของการเพิ่มประสิทธิภาพ และเป้าหมายก็คือการหาบางอย่างที่ใกล้เคียงกัน วิธีการแก้ปัญหา suboptimal ใช้ทำซ้ำเพื่อการปรับปรุงการแบ่งจนการลู่เข้า ขั้นตอนของ hierarchical-cluster analysis แบ่งได้ 2 ประเภท คือ
Divisible algorithms (แบ่งแยกแตกออก) โดย divisible algorithms เริ่มจากกลุ่มตัวอย่าง X และ แบ่งมันไปเป็นส่วนของส่วนย่อยแล้วการแบ่งแต่ละส่วนย่อยเป็นชุดที่เล็กกว่า และอื่น ๆ ดังนั้น divisible algorithms ทำให้เกิดลำดับของการแบ่งจาก หยาบ (coarser) ไป อย่างละเอียด (finer) ในกรณีนี้เราต้องตัดสินใจได้ว่ากลุ่มไหนหรือ clusterไหนที่ควรแบ่งแยก และจะทำการแบ่งแยกอย่างไร
Agglomerative algorithms (รวมเป็นกลุ่มเป็นก้อน) โดย Agglomerative algorithms เริ่มต้นจากพิจารณาจุดหรือตำแหน่งที่อยู่ในบริเวณส่วนเฉพาะของแต่ละกลุ่ม ซึ่งแต่ละขั้นตอนจะทำการรวมกลุ่มเข้าด้วยกันโดยการพิจารณากลุ่มคู่ที่ใกล้กันมากที่สุด แนวคิดของวิธีการนี้เพื่อกำหนดความใกล้ชิดหรือความสัมพันธ์ของกลุ่มนั้นๆ รวมเข้าด้วยกัน การดำเนินการของ clustering เป็นการดำเนินการแบบ bottom-up โดยทั่วไป Agglomerative algorithms เป็นการแบ่งอย่างละเอียดไปหยาบ มันบ่อยมากที่ใช้ประโยชน์ในโลกแห่งความเป็นจริง กว่าวิธี divisible ดังนั้นจะกล่าวถึงรายละเอียดเฉพาะเทคนิควิธีการ Agglomerative Hierarchical Clustering
วิธีการ Hierarchical Clustering นี้ส่วนใหญ่จะเป็นขั้นตอนวิธีของ single-link หรือ complete-link โดยทั้ง 2 วิธีนี้มีความแตกต่างกันในทางการอธิบายลักษณะความเหมือนระหว่างการจับกลุ่ม ซึ่งวิธี single-link ความสัมพันธ์ทั้งสองกลุ่มที่กำหนดนั้นมีระยะห่างระหว่างจุด 2 จุดที่อยู่ต่างกลุ่มกันน้อยที่สุด กล่าวคือ อยู่ใกล้กันมากที่สุด หากพิจารณาทางกราฟ ถ้าเริ่มต้นด้วยทุกๆ จุดที่เป็นกลุ่มลักษณะที่มีเพียงสิ่งเดียว (singleton cluster) และทำการเชื่อมโยงระหว่างจุดนั้นๆ ทีละครั้ง จะได้เส้นเชื่อมสั้นที่สุด จากนั้นทำการรวมเป็นเส้นเชื่อมเดียวกันไปยังกลุ่มต่างๆ
ส่วนวิธี complete-link ความสัมพันธ์ของทั้งสองกลุ่มที่กำหนดนั้นมีระยะห่างระหว่างจุด 2 จุดที่อยู่ต่างกลุ่มกันมากที่สุด ในกรณีที่ 2 กลุ่มจะรวมกันเป็นกลุ่มที่ใหญ่ขึ้น ขึ้นอยู่กับระยะห่างที่น้อยที่สุดเป็นเกณฑ์ ถึงแม้ว่าวิธี single-link เป็นการคำนวณที่ง่าย แต่ในทางปฏิบัติ complete-link มีประโยชน์มากกว่า อธิบายให้ง่ายก็คือ ความแตกต่างระหว่าง Single-link และ complete-link วิธีการคำนวณระยะห่าง
สำหรับขั้นตอนการเริ่มต้นขั้นตอนของ Agglomerative Hierarchical Clustering ในการแบ่งกลุ่ม
1. คำนวณหาความสัมพันธ์ข้อมูลที่ต้องการในรูปของตาราง (proximity matrix)
2. รวมกลุ่มของสองกลุ่มเข้าด้วยกัน โดยพิจารณาจากค่าระยะห่างหรือค่าความคล้าย
3. ปรับเปลี่ยนความสัมพันธ์ข้อมูล (proximity matrix) ระหว่างกลุ่มใหม่ที่ได้กับกลุ่มเดิม
4. ทำจนกระทั่ง รวมเป็นกลุ่มเดียวกัน