이 페이지는 Cloud Translation API를 통해 번역되었습니다.

클러스터링 알고리즘 실행

머신러닝에서는 수백만 개의 예시를 포함할 수 있는 데이터 세트가 발생하는 경우가 있습니다. ML 알고리즘은 이러한 대규모 데이터 세트에 맞게 효율적으로 확장되어야 합니다. 그러나 많은 클러스터링 알고리즘은 모든 포인트 쌍 간 유사성을 계산해야 하므로 확장되지 않습니다. 즉, 런타임은 $O(n^2)$의 포인트 수의 제곱으로 증가합니다. 예를 들어 집계 또는 다분야 계층적 클러스터링 알고리즘은 모든 포인트 쌍을 살펴보고 각각 $O(n^2 log(n))$ 와 $O(n^2)$의 복잡성을 갖습니다.

이 과정에서는 k-평균에 중점을 둡니다. $O(nk)$는 클러스터 수. 여기서 $k$는 클러스터 수이고, k-평균은 아래 그림 1에서처럼 지점과 클러스터 중심 사이의 거리를 최소화하여 클러스터를 $k$ 클러스터로 그룹화합니다. 클러스터의 중점은 클러스터에 있는 모든 포인트의 평균입니다.

표시된 대로 k-평균은 대략 원형 클러스터를 찾습니다. 개념적으로, k-평균은 데이터를 여러 개의 대략적인 분포로 구성된 것으로 효과적으로 처리하고 이러한 분포에 해당하는 클러스터를 찾으려고 한다는 의미입니다. 실제로 데이터에는 이상점이 포함되어 있으므로 이 모델에 맞지 않을 수 있습니다.

k-평균을 실행하기 전에 클러스터 수( $k$)를 선택해야 합니다. 처음에는 $k$를 추측합니다. 이 숫자를 미세 조정하는 방법은 나중에 설명하겠습니다.

k-평균 클러스터링 알고리즘

데이터를 클러스터로 $k$ 클러스터링하려면 k-평균이 아래 단계를 따릅니다.

1단계

알고리즘은 각 클러스터의 중심을 무작위로 선택합니다. 이 예시에서는 3의 $k$ 를 선택하므로 알고리즘이 3개의 중심을 무작위로 선택합니다.

2단계

알고리즘은 각 클러스터를 가장 가까운 중심에 할당하여 $k$ 초기 클러스터를 가져옵니다.

3단계

알고리즘은 모든 클러스터에 대해 클러스터의 모든 포인트 평균을 사용하여 중심을 다시 계산합니다. 중심의 변화는 그림 3에 화살표로 표시되어 있습니다. 중심이 변하면 알고리즘은 포인트를 가장 가까운 중심에 다시 할당합니다. 그림 4는 재할당한 후의 새 클러스터를 보여줍니다.

4단계

알고리즘은 포인트의 클러스터 변경이 중지될 때까지 중심 계산과 포인트 할당을 반복합니다. 대규모 데이터 세트를 클러스터링할 때는 다른 기준을 대신 수렴하기 전에 알고리즘을 중지합니다.

이 과정의 k-평균에 대한 수학은 이해하지 않아도 됩니다. 하지만 궁금한 점은 아래에서 수학적 증거를 확인하세요.

더하기 아이콘을 클릭하여 수학적 증거를 확보합니다.

예를 들어 $n$ 클러스터에 할당된 예시가 중심에 있을 때 예제의 거리 합계를 최소화합니다. 각 항목의 의미는 다음과 같습니다.

$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$$ Subject: $$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-평균은 연속 실행에서 크게 다른 결과를 반환할 수 있습니다. 이 문제를 해결하려면 k-평균을 여러 번 실행하고 최상의 품질 측정항목으로 결과를 선택하세요. 품질 측정항목은 이 과정 후반부에서 설명합니다. 더 나은 초기 중심 위치를 선택하려면 k-평균의 고급 버전이 필요합니다.

요약

결과 해석