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

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

อัลกอริทึม k-means มี ความซับซ้อนของ \(O(n)\)ซึ่งหมายความว่าอัลกอริทึมจะปรับสเกลเป็นเชิงเส้นกับ \(n\) อัลกอริทึมนี้จะมุ่งเน้นไปที่หลักสูตรนี้

ประเภทของคลัสเตอร์

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

คลัสเตอร์แบบเซนทรอยด์

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

วันที่ ตัวอย่างที่จัดเป็นกลุ่มโดยใช้การจัดกลุ่มแบบเซนทรอยด์
           เส้นต่างๆ จะแสดงเส้นขอบระหว่างคลัสเตอร์
รูปที่ 1: ตัวอย่างการจัดกลุ่มแบบเซนทรอยด์

คลัสเตอร์ตามความหนาแน่น

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

วันที่ ตัวอย่างที่จัดกลุ่มเป็น 2 คลัสเตอร์โดยใช้การจัดกลุ่มแบบอิงตามความหนาแน่น
      คลัสเตอร์แยกกันแบบเชิงเส้นไม่ได้
รูปที่ 2: ตัวอย่างการจัดกลุ่มตามความหนาแน่น

คลัสเตอร์แบบอิงตามการกระจาย

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

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

การจัดกลุ่มแบบลำดับชั้น

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

วันที่ สัตว์ที่จับกลุ่มกันโดยใช้ต้นไม้ลำดับชั้น
รูปที่ 4: ตัวอย่างกลุ่มสัตว์ที่มีต้นไม้เป็นลำดับชั้น