[null,null,["上次更新時間：2025-02-25 (世界標準時間)。"],[[["\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,["As 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\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."]]
