Sử dụng bộ sưu tập để sắp xếp ngăn nắp các trang
Lưu và phân loại nội dung dựa trên lựa chọn ưu tiên của bạn.
Như đã đề cập trước đó, nhiều thuật toán phân cụm không mở rộng theo quy mô cho các tập dữ liệu được sử dụng trong học máy, thường có hàng triệu ví dụ. Ví dụ: các thuật toán phân cụm phân cấp hợp nhất hoặc phân chia xem xét tất cả các cặp điểm và có độ phức tạp tương ứng là \(O(n^2 log(n))\) và \(O(n^2)\).
Khoá học này tập trung vào k-means vì thuật toán này có tỷ lệ theo \(O(nk)\), trong đó \(k\)là số cụm do người dùng chọn. Thuật toán này nhóm các điểm thành các cụm\(k\) bằng cách giảm thiểu khoảng cách giữa mỗi điểm và tâm của cụm (xem Hình 1).
Do đó, k-means xử lý hiệu quả dữ liệu như được tạo thành từ một số
phân phối hình tròn gần đúng và cố gắng tìm các cụm tương ứng với các
phân phối này. Tuy nhiên, dữ liệu thực tế chứa các giá trị ngoại lai và cụm dựa trên mật độ và có thể không khớp với các giả định cơ bản của k-means.
Thuật toán phân cụm k-means
Thuật toán này tuân theo các bước sau:
Cung cấp một giá trị dự đoán ban đầu cho \(k\). Bạn có thể sửa đổi giá trị này sau. Trong ví dụ này, chúng ta chọn \(k = 3\).
Chọn ngẫu nhiên \(k\) trung tâm.
Hình 1: k-means tại thời điểm khởi tạo.
Gán mỗi điểm cho tâm điểm gần nhất để nhận được \(k\) các cụm ban đầu.
Hình 2: Các cụm ban đầu.
Đối với mỗi cụm, hãy tính toán một tâm mới bằng cách lấy vị trí trung bình của tất cả các điểm trong cụm. Các mũi tên trong Hình 4 cho thấy sự thay đổi về vị trí tâm.
Hình 3: Tính lại trọng tâm.
Chỉ định lại từng điểm cho tâm mới gần nhất.
Hình 4: Các cụm sau khi chỉ định lại.
Lặp lại bước 4 và 5, tính toán lại trọng tâm và thành viên cụm cho đến khi các điểm không còn thay đổi cụm. Trong trường hợp tập dữ liệu lớn, bạn có thể dừng thuật toán trước khi hội tụ dựa trên các tiêu chí khác.
Vì các vị trí trọng tâm ban đầu được chọn ngẫu nhiên, nên k-means có thể trả về kết quả khác biệt đáng kể trong các lần chạy liên tiếp. Để giải quyết vấn đề này, hãy chạy k-means nhiều lần và chọn kết quả có chỉ số chất lượng tốt nhất. (Chúng ta sẽ mô tả các chỉ số chất lượng ở phần sau của khoá học này.) Bạn sẽ cần một phiên bản k-means nâng cao để chọn các vị trí trọng tâm ban đầu tốt hơn.
[null,null,["Cập nhật lần gần đây nhất: 2025-02-25 UTC."],[[["\u003cp\u003eThe k-means clustering algorithm groups data points into clusters by minimizing the distance between each point and its cluster's centroid.\u003c/p\u003e\n"],["\u003cp\u003eK-means is efficient, scaling as O(nk), making it suitable for large datasets in machine learning, unlike hierarchical clustering methods.\u003c/p\u003e\n"],["\u003cp\u003eThe algorithm iteratively refines clusters by recalculating centroids and reassigning points until convergence or a stopping criteria is met.\u003c/p\u003e\n"],["\u003cp\u003eDue to random initialization, k-means can produce varying results; running it multiple times and selecting the best outcome based on quality metrics is recommended.\u003c/p\u003e\n"],["\u003cp\u003eK-means assumes data is composed of circular distributions, which may not be accurate for all real-world data containing outliers or density-based clusters.\u003c/p\u003e\n"]]],[],null,["# What is k-means clustering?\n\nAs previously mentioned, many clustering algorithms don't scale to the datasets\nused in machine learning, which often have millions of examples. For example,\nagglomerative or divisive hierarchical clustering algorithms look at all pairs\nof points and have complexities of \\\\(O(n\\^2 log(n))\\\\) and \\\\(O(n\\^2)\\\\),\nrespectively.\n\nThis course focuses on k-means because it scales as \\\\(O(nk)\\\\), where \\\\(k\\\\)\nis the number of clusters chosen by the user. This algorithm groups points into\n\\\\(k\\\\) clusters by minimizing the distances between each point and its\ncluster's centroid (see Figure 1).\n\nAs a result, k-means effectively treats data as composed of a number of roughly\ncircular distributions, and tries to find clusters corresponding to these\ndistributions. But real-world data contains outliers and density-based clusters\nand might not match the assumptions underlying k-means.\n\nk-means clustering algorithm\n----------------------------\n\nThe algorithm follows these steps:\n\n1. Provide an initial guess for \\\\(k\\\\), which can be revised later. For this\n example, we choose \\\\(k = 3\\\\).\n\n2. Randomly choose \\\\(k\\\\) centroids.\n\n \u003cbr /\u003e\n\n **Figure 1: k-means at initialization.**\n\n \u003cbr /\u003e\n\n3. Assign each point to the nearest centroid to get \\\\(k\\\\) initial clusters.\n\n \u003cbr /\u003e\n\n **Figure 2: Initial clusters.**\n\n \u003cbr /\u003e\n\n4. For each cluster, calculate a new centroid by taking the mean position of\n all points in the cluster. The arrows in Figure 4 show the change in\n centroid positions.\n\n \u003cbr /\u003e\n\n **Figure 3: Recomputed centroids.**\n\n \u003cbr /\u003e\n\n5. Reassign each point to the nearest new centroid.\n\n \u003cbr /\u003e\n\n **Figure 4: Clusters after reassignment.**\n\n \u003cbr /\u003e\n\n6. Repeat steps 4 and 5, recalculating centroids and cluster membership, until\n points no longer change clusters. In the case of large datasets, you can\n stop the algorithm before convergence based on other criteria.\n\nBecause the centroid positions are initially chosen at random, k-means can\nreturn significantly different results on successive runs. To solve this\nproblem, run k-means multiple times and choose the result with the best quality\nmetrics. (We'll describe quality metrics later in this course.) You'll need an\nadvanced version of k-means to choose better initial centroid positions.\n\nThough a deep understanding of the math is not necessary, for those who are\ncurious, k-means is a special case of the\n[expectation-maximization algorithm](https://wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm). See\n[lecture notes on the topic](https://alliance.seas.upenn.edu/%7Ecis520/dynamic/2021/wiki/index.php?n=Lectures.EM#toc-1.2) from UPenn."]]
