k means algorithm

k-หมายถึง-อัลกอริทึม

นี่คือการใช้ Python ของอัลกอริธึม k-means รวมถึงวิธีข้อศอกและวิธีการเงาสำหรับการเลือก K ที่เหมาะสมที่สุด

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

อัลกอริทึม

• สุ่มเลือก K เซนทรอยด์คลัสเตอร์เริ่มต้นจากจุดข้อมูล
• กำหนดจุดข้อมูลแต่ละจุดให้กับศูนย์กลางคลัสเตอร์ที่ใกล้ที่สุด
• คำนวณเซนทรอยด์ของแต่ละคลัสเตอร์ใหม่ตามจุดข้อมูลที่กำหนด
• ทำซ้ำขั้นตอนที่ 2-3 จนกระทั่งมาบรรจบกัน (เช่น เมื่อการกำหนดคลัสเตอร์ไม่เปลี่ยนแปลงอีกต่อไป)

ฟังก์ชั่นวัตถุประสงค์

วัตถุประสงค์ของเคมีนคือการลดผลรวมของระยะทางยกกำลังสองระหว่างจุดข้อมูลแต่ละจุดและเซนทรอยด์ของคลัสเตอร์ที่กำหนด ฟังก์ชันวัตถุประสงค์สามารถเขียนได้ดังนี้: $$J = sum_{j=1}^K sum_{i=1}^N||x_i^j - mu_j||^2$$ ที่ไหน $x_i^เจ$ คือจุดข้อมูล i-th ภายในคลัสเตอร์ j , μj คือจุดเซนทรอยด์ของคลัสเตอร์ j และ N คือจำนวนจุดข้อมูลทั้งหมด

วิธีข้อศอก

วิธี Elbow เป็นการวิเคราะห์พฤติกรรมที่ใช้ในการกำหนดจำนวนคลัสเตอร์ที่เหมาะสมที่สุดในการจัดกลุ่ม K-Means วิธีการนี้จะพล็อตผลรวมของระยะทางกำลังสองระหว่างการสังเกตแต่ละครั้งกับเซนทรอยด์ที่กำหนดให้เป็นฟังก์ชันของจำนวนกระจุกดาว จุด "ข้อศอก" บนแผนระบุจำนวนกระจุกที่การเพิ่มกระจุกเพิ่มเติมไม่ส่งผลให้ผลรวมของระยะทางยกกำลังสองลดลงอย่างมีนัยสำคัญ

วิธี Elbow สามารถสรุปได้ตามขั้นตอนต่อไปนี้:

• เรียกใช้การจัดกลุ่ม K-Means สำหรับช่วงค่า k
• คำนวณผลรวมของระยะทางกำลังสองสำหรับค่า k แต่ละค่า
• เขียนผลรวมของระยะทางกำลังสองเป็นฟังก์ชันของ k
• ระบุจุด "ข้อศอก" บนโครงเรื่อง

วิธีการซิลลูเอต

วิธี Silhouette เป็นอีกหนึ่งการศึกษาพฤติกรรมที่ใช้ในการกำหนดจำนวนคลัสเตอร์ที่เหมาะสมที่สุดในการจัดกลุ่ม K-Means วิธีการนี้จะวัดคุณภาพของการกำหนดคลัสเตอร์ของการสังเกตแต่ละครั้งโดยการคำนวณค่าสัมประสิทธิ์ภาพเงาของมัน ค่าสัมประสิทธิ์ภาพเงาอยู่ในช่วงตั้งแต่ -1 ถึง 1 โดยที่ค่า 1 บ่งชี้ว่าการสังเกตมีการรวมกลุ่มกันเป็นอย่างดี และค่า -1 บ่งชี้ว่าการสังเกตมีการจัดประเภทไม่ถูกต้อง สูตรในการคำนวณค่าสัมประสิทธิ์ภาพเงาของจุดข้อมูล i คือ: $$s(i) = frac{(b(i) - a(i))}{max(a(i), b(i))}$$ โดยที่ a(i) คือระยะห่างเฉลี่ยระหว่าง i และจุดข้อมูลอื่นๆ ทั้งหมดในคลัสเตอร์ และ b(i) คือระยะห่างเฉลี่ยขั้นต่ำระหว่าง i และคลัสเตอร์อื่นๆ ทั้งหมด (กล่าวคือ คลัสเตอร์ที่มีเซนทรอยด์ถัดไปที่ใกล้ที่สุด) ค่าสัมประสิทธิ์ภาพเงาสำหรับการจัดกลุ่มทั้งหมดคือค่าเฉลี่ยของค่าสัมประสิทธิ์ภาพเงาสำหรับจุดข้อมูลทั้งหมด

วิธีการ Silhouette สามารถสรุปได้ตามขั้นตอนต่อไปนี้:

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