อัลกอริทึมคลัสเตอร์

ชุดข้อมูลแมชชีนเลิร์นนิงอาจมีตัวอย่างหลายล้านรายการ แต่อัลกอริทึมการจัดกลุ่มบางรายการอาจปรับขนาดได้อย่างมีประสิทธิภาพ อัลกอริทึมการจัดกลุ่มหลายอัลกอริทึมจะคํานวณความคล้ายคลึงกันระหว่างคู่ตัวอย่างทั้งหมด ซึ่งหมายความว่ารันไทม์จะเพิ่มขึ้นตามจํานวนตัวอย่างที่เพิ่มขึ้นเป็น 2 เท่า $n$ซึ่งเขียนเป็น $O(n^2)$ ในนิพจน์ความซับซ้อน อัลกอริทึม $O(n^2)$ จึงไม่เหมาะสําหรับชุดข้อมูลที่มีตัวอย่างหลายล้านรายการ

อัลกอริทึม K-means มีความซับซ้อน $O(n)$ซึ่งหมายความว่าอัลกอริทึมจะปรับขนาดตาม $n$ในเชิงเส้น อัลกอริทึมนี้จะเป็นส่วนสำคัญของหลักสูตรนี้

ประเภทของการจัดกลุ่ม

ดูรายการแนวทางต่างๆ ในการคลัสเตอร์ได้ที่ การสํารวจอัลกอริทึมการจัดกลุ่มที่ครอบคลุม Xu, D. และ Tian, Y. Ann. Data. Sci. (2015) 2: 165. แต่ละแนวทางเหมาะกับการเผยแพร่ข้อมูลแต่ละประเภท หลักสูตรนี้จะกล่าวถึงแนวทางทั่วไป 4 แนวทางโดยสังเขป

การจัดกลุ่มตามเซนทรอยด์

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

รูปที่ 1: ตัวอย่างการคลัสเตอร์ตามจุดศูนย์กลางมวล

การจัดกลุ่มตามความหนาแน่น

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

รูปที่ 2: ตัวอย่างการคลัสเตอร์ตามความหนาแน่น

การจัดกลุ่มตามการแจกแจง

วิธีการจัดกลุ่มนี้ถือว่าข้อมูลประกอบด้วยการแจกแจงความน่าจะเป็น เช่น การแจกแจงแบบกaussian ในรูปที่ 3 อัลกอริทึมตามการแจกแจงจะจัดกลุ่มข้อมูลออกเป็นการแจกแจงแบบกaussian 3 รูปแบบ เมื่อระยะทางจากจุดศูนย์กลางของข้อมูลประชากรเพิ่มขึ้น ความน่าจะเป็นที่จุดหนึ่งๆ จะอยู่ในข้อมูลประชากรก็จะลดลง แถบแสดงถึงระดับความน่าจะเป็นที่ลดลง เมื่อคุณไม่แน่ใจเกี่ยวกับการกระจายข้อมูลพื้นฐานที่เฉพาะเจาะจง คุณควรใช้อัลกอริทึมอื่น

รูปที่ 3: ตัวอย่างการคลัสเตอร์ตามการแจกแจง

การแบ่งกลุ่มตามลําดับชั้น

การจัดกลุ่มตามลําดับชั้นจะสร้างลําดับชั้นของคลัสเตอร์ ไม่น่าแปลกใจเลยที่การจัดกลุ่มตามลําดับชั้นเหมาะสําหรับข้อมูลลําดับชั้น เช่น การจัดหมวดหมู่ ดูตัวอย่างได้จากบทความ การเปรียบเทียบจีโนมของ Escherichia coli ที่เรียงลำดับแล้ว 61 รายการโดย Oksana Lukjancenko, Trudy Wassenaar และ Dave Ussery คุณเลือกคลัสเตอร์จํานวนเท่าใดก็ได้โดยการตัดต้นไม้ที่ระดับที่เหมาะสม

รูปที่ 4: ตัวอย่างการจัดกลุ่มสัตว์ตามลําดับชั้นในแผนภูมิต้นไม้

คําสําคัญ:

• อัลกอริทึม K-means
• centroid
• การแจกแจงแบบกaussian