앞서 언급한 바와 같이 많은 클러스터링 알고리즘은 수백만 개의 예시가 있는 머신러닝에 사용되는 데이터 세트로 확장되지 않습니다. 예를 들어 집계형 또는 분할형 계층적 클러스터링 알고리즘은 모든 점 쌍을 살펴보고 각각 \(O(n^2 log(n))\) 및 \(O(n^2)\)의 복잡도를 갖습니다.
이 과정에서는 k-means에 중점을 둡니다. k-means는 \(O(nk)\)(여기서 \(k\)는 사용자가 선택한 클러스터 수)로 확장되기 때문입니다. 이 알고리즘은 각 점과 클러스터의 중심점 사이의 거리를 최소화하여 점을\(k\) 클러스터로 그룹화합니다 (그림 1 참고).
따라서 k-평균은 데이터를 대략 원형인 여러 개의 분포로 구성된 것으로 효과적으로 처리하고 이러한 분포에 해당하는 클러스터를 찾으려고 시도합니다. 하지만 실제 데이터에는 외부값과 밀도 기반 클러스터가 포함되어 있으며 k-means의 기본 가정과 일치하지 않을 수 있습니다.
k-평균 클러스터링 알고리즘
알고리즘은 다음 단계를 따릅니다.
나중에 수정할 수 있는 \(k\)의 초깃값을 제공합니다. 이 예에서는 \(k = 3\)를 선택합니다.
\(k\) 중심을 무작위로 선택합니다.
그림 1: 초기화 시 k-평균
각 점을 가장 가까운 중심에 할당하여 \(k\) 초기 클러스터를 가져옵니다.
그림 2: 초기 클러스터.
각 클러스터의 경우 클러스터에 있는 모든 지점의 평균 위치를 사용하여 새 중심을 계산합니다. 그림 4의 화살표는 중심점 위치의 변화를 보여줍니다.
그림 3: 다시 계산된 중심점.
각 점을 가장 가까운 새 중심에 다시 할당합니다.
그림 4: 재할당 후 클러스터
점이 더 이상 클러스터를 변경하지 않을 때까지 4단계와 5단계를 반복하여 중심점과 클러스터 멤버십을 다시 계산합니다. 대규모 데이터 세트의 경우 다른 기준에 따라 수렴하기 전에 알고리즘을 중지할 수 있습니다.
중앙점 위치는 처음에 무작위로 선택되므로 k-means는 연속 실행에서 상당히 다른 결과를 반환할 수 있습니다. 이 문제를 해결하려면 k-means를 여러 번 실행하고 품질 측정항목이 가장 우수한 결과를 선택합니다. 품질 측정항목은 이 과정의 뒷부분에서 설명합니다. 더 나은 초기 중심점 위치를 선택하려면 고급 버전의 k-means가 필요합니다.
[null,null,["최종 업데이트: 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."]]
