หน้านี้ได้รับการแปลโดย Cloud Translation API

เรียกใช้อัลกอริทึมคลัสเตอร์

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

หลักสูตรนี้มุ่งเน้นที่ K-means เนื่องจากปรับขนาดเป็น $O(nk)$โดยที่ $k$คือจํานวนคลัสเตอร์ โดย K-means จะจัดกลุ่มเป็น $k$ คลัสเตอร์โดยลดจํานวนระยะห่างระหว่างจุดและเซนทรอยด์ของคลัสเตอร์ (ตามที่เห็นในรูปที่ 1 ด้านล่าง) centroid ของคลัสเตอร์คือค่าเฉลี่ยของจุดทั้งหมดในคลัสเตอร์

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

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

อัลกอริทึมการจัดกลุ่ม k-means

หากต้องการจัดกลุ่มข้อมูลเป็น $k$ คลัสเตอร์ k-means จะทําตามขั้นตอนต่อไปนี้

กราฟของ k-means ที่การเริ่มต้น — **รูปที่ 1: k-means ในขั้นเริ่มต้น**

ขั้นตอนที่ 1

อัลกอริทึมจะสุ่มเลือกศูนย์เซนเซอร์สําหรับแต่ละคลัสเตอร์ ในตัวอย่างของเรา เราเลือก $k$ จาก 3 ตัว ดังนั้นอัลกอริทึมจะเลือกแบบสุ่มจาก centroid 3 ตัว

ขั้นตอนที่ 2

อัลกอริทึมจะกําหนดแต่ละจุดให้เซนทรอยด์ใกล้เคียงที่สุดเพื่อรับ $k$ คลัสเตอร์เริ่มต้น

การคํานวณเปอร์เซ็นต์ของเซนทรอยด์ — **รูปที่ 3: การคํานวณเซนทรอยด์ใหม่**

ขั้นตอนที่ 3

สําหรับทุกคลัสเตอร์ อัลกอริทึมจะคํานวณเซนทริกซ์ใหม่โดยใช้ค่าเฉลี่ยของจุดทั้งหมดในคลัสเตอร์ การเปลี่ยนแปลงของเซนทรอยด์จะแสดงในรูปที่ 3 ด้วยลูกศร เนื่องจากศูนย์นี้มีการเปลี่ยนแปลง อัลกอริทึมจึงจะกําหนดคะแนนให้อีกครั้งแก่ศูนย์เซนติกที่ใกล้เคียงที่สุด รูปที่ 4 แสดงคลัสเตอร์ใหม่หลังจากกําหนดอีกครั้ง

**ภาพที่ 4: คลัสเตอร์หลังจากมอบหมายใหม่**

ขั้นตอนที่ 4

อัลกอริทึมจะคํานวณการคํานวณเซนทรอยด์และกําหนดแต้มซ้ํา จนกว่าคะแนนจะหยุดเปลี่ยนคลัสเตอร์ เมื่อจัดกลุ่มชุดข้อมูลขนาดใหญ่ คุณต้องหยุดอัลกอริทึมก่อนที่จะเข้าถึง Conver โดยใช้เกณฑ์อื่นๆ แทน

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

คลิกไอคอนบวกของหลักฐานทางคณิตศาสตร์

จากตัวอย่าง $n$ ที่ให้ไว้กับ $k$ คลัสเตอร์ ให้ลดจํานวนระยะทางของตัวอย่างไปยังเซนทรอยด์ สถานที่:

$A_{nk} = 1$ เมื่อ $n$ตัวอย่างถูกกําหนดให้กับคลัสเตอร์ $k$ และ 0 หากไม่เป็นเช่นนั้น
$\theta_k$ เป็นศูนย์กลางของคลัสเตอร์ $k$

เราต้องการลดนิพจน์ต่อไปนี้ให้เหลือน้อยที่สุด $$\min_{A,\theta} \sum_{n=1}^N \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n ||^2$$ ขึ้นอยู่กับ $$A_{nk} \in \{0,1\} \forall n,k$$ และ $$\sum^{K}_{k=1}A_{nk}=1 \forall n$$ หากต้องการลดนิพจน์ซึ่งเกี่ยวข้องกับศูนย์เซนทัลของคลัสเตอร์ $\theta_k$ ให้ใช้อนุพันธ์ที่เกี่ยวข้องกับ $\theta_k$ และเทียบเท่ากับ 0 $$f(\theta) = \sum^{N}_{n=1} \sum_{k=1}^{K} A_{nk} ||\theta_k - x_n||^2$$ $$\frac{\partial f}{\partial \theta_k} = 2 \sum_{n=1}^{N} A_{nk}(\theta_k - x_n) = 0$$ $$\implies \sum_{n=1}^{N} A_{nk}\theta_{k} = \sum^N_{n=1} A_{nk}x_{n}$$ $$\theta_k \sum_{n=1}^{N} A_{nk} = \sum_{n=1}^{N} A_{nk} x_n$$ $$\theta_k = \frac{\sum^N_{n=1} A_{nk} x_n}{\sum^N_{n=1} A_{nk}}$$ ตัวเลขเศษคือผลรวมของระยะทางจากตัวอย่างเซนทรอยด์ทั้งหมดในคลัสเตอร์ ตัวส่วนคือจํานวนตัวอย่างในคลัสเตอร์ ดังนั้น เซนทริกเซนต์ของคลัสเตอร์ $\theta_k$ คือค่าเฉลี่ยของระยะทางที่เซนเซอร์ตัวอย่างในคลัสเตอร์ ด้วยเหตุนี้จึงได้รับการพิสูจน์แล้ว

เนื่องจากเบื้องต้นระบบจะสุ่มเลือกตําแหน่งของศูนย์ k-meer จึงอาจให้ผลลัพธ์ที่ต่างกันมากเมื่อเรียกใช้ต่อเนื่อง หากต้องการแก้ไขปัญหานี้ ให้เรียกใช้ k-mean หลายๆ ครั้งและเลือกผลลัพธ์ที่มีเมตริกคุณภาพดีที่สุด (เราจะอธิบายเมตริกคุณภาพในหลักสูตรนี้ในภายหลัง) คุณต้องมี k-me> เวอร์ชันขั้นสูงเพื่อเลือกตําแหน่งเซนทรอยด์แรกเริ่มที่ดีขึ้น

สรุป

ตีความผลลัพธ์