k-means 클러스터링 작동 방식

k-means는 유사한 객체를 그룹화하는 모델을 교육하는 알고리즘입니다. k-means 알고리즘은 입력 데이터 세트의 각 관측치를 n 차원 공간(n은 관측치의 속성 수)의 지점으로 매핑하여 이를 달성합니다. 예를 들어 데이터 세트에는 특정 위치의 온도 및 습도 관측치가 포함될 수 있으며, 이는 2차원 공간의 지점(t, h)에 매핑됩니다.

참고

클러스터링 알고리즘은 비지도 방식입니다. 비지도 학습에서 훈련 데이터 세트의 객체와 연결될 수 있는 레이블은 사용되지 않습니다. 자세한 정보는 비지도 학습을 참조하세요.

k-means 클러스터링에서 각 클러스터에는 중심이 있습니다. 모델 훈련 도중 k-means 알고리즘은 클러스터링의 기반인 클러스터 중심까지 데이터 세트의 각 관측치에 해당하는 지점 거리를 사용합니다. 생성할 클러스터의 수(k)를 선택합니다.

예를 들어 수기 숫자를 인식하는 모델을 생성하고자 하는 경우 훈련용 MNIST 데이터 세트를 선택합니다. 데이터 세트는 수천 개의 수기 숫자 이미지를 제공합니다(0~9). 이 예제에서 각 숫자별로(0, 1, …, 9) 하나씩 10개의 클러스터를 선택할 수 있습니다. 모델 훈련의 일환으로 k-means 알고리즘은 입력 이미지를 10개의 클러스터로 그룹화합니다.

MNIST 데이터 세트의 각 이미지는 28x28픽셀 이미지로, 총 784픽셀입니다. 각 이미지는 784차원 공간의 지점과 일치하고, 2차원 공간의 지점(x,y)과 유사합니다. 지점이 속하는 클러스터를 확인하기 위해 k-means 알고리즘은 모든 클러스터 중심으로부터 해당 지점의 거리를 확인합니다. 그리고 가장 근접한 중심이 포함된 클러스터를 이미지가 속하는 클러스터로 선택합니다.

참고

SageMaker Amazon은 알고리즘이 k개의 클러스터를 생성하도록 지정하는 대신 추가 클러스터 중심 (K = k*x) 을 지정하여 모델 정확도를 개선할 수 있는 사용자 지정 알고리즘 버전을 사용합니다. 하지만 알고리즘은 이를 k 클러스터로 줄입니다.

SageMaker에서는 교육 작업을 생성할 때 클러스터 수를 지정합니다. 자세한 정보는 CreateTrainingJob을 참조하세요. 요청 본문에서 HyperParameters 문자열 맵을 추가하여 k 및 extra_center_factor 문자열을 지정합니다.

다음은 k-means가 모델 학습에서 SageMaker 작동하는 방식을 요약한 것입니다.

1. 초기 K 클러스터 중심을 결정합니다.

   참고

   다음 주제에서 K 클러스터는 k * x를 참조합니다. 여기서 모델 훈련 작업 생성 시 k 및 x를 지정합니다.

2. 입력 훈련 데이터에 대해 반복하고 클러스터 중심을 다시 계산합니다.

3. 결과 클러스터를 k로 줄입니다(데이터 과학자가 요청에서 k*x 클러스터 생성을 지정한 경우).

다음 단원은 데이터 과학자가 HyperParameters 문자열 맵의 일부로서 모델 훈련 작업을 구성하도록 지정할 수 있는 일부 파라미터를 설명합니다.

1단계: 초기 클러스터 중심 결정

에서 SageMaker k-평균을 사용하는 경우 랜덤하게 샘플링된 소량 배치의 관측치 중에서 초기 군집 중심을 선택합니다. 다음 전략 중 하나를 선택하여 초기 클러스터 중신의 선택 방법을 결정합니다.

• 무작위 접근법 - 입력 데이터 세트에서 K개의 관측치를 클러스터 중심으로 무작위로 선택합니다. 예를 들어 MNIST 훈련 데이터 세트에 있는 10개의 이미지와 일치하는 784차원 공간을 가리키는 클러스터 중심을 선택할 수 있습니다.

• k-means++ 접근 방식은 다음과 같이 작동합니다.

  1. 하나의 클러스터로 시작하고 중심을 결정합니다. 훈련 데이터 세트로부터 관측치를 임의적으로 선택하고 관측치와 일치하는 지점을 클러스터 중심으로 사용합니다. 예를 들어 MNIST 데이터 세트에서 수기 숫자 이미지를 임의적으로 선택합니다. 그런 다음 이미지와 일치하는 784차원 공간의 지점을 클러스터 중심으로 선택합니다. 이는 클러스터 중심 1입니다.

  2. 클러스터 2의 중심을 결정합니다. 훈련 데이터 세트의 남은 관측치에서 임의적으로 관측치를 선택합니다. 이전에 선택했던 것과는 다른 것을 선택합니다. 이 관측치는 클러스터 중심 1로부터 멀리 떨어진 지점과 일치합니다. MNIST를 예제로 사용하여 다음을 수행합니다.

     • 각각의 남은 이미지의 경우 클러스터 중심 1로부터 일치하는 지점의 거리를 확인합니다. 거리를 제곱하고 거리의 제곱에 비례하는 가능성을 할당합니다. 그러한 방식으로 이전에 선택했던 것과 다른 이미지는 클러스터 중심 2로 선택될 가능성이 더욱 높습니다.

     • 이전 단계에 할당된 가능성을 기반으로 이미지 중 하나를 임의적으로 선택합니다. 이미지와 일치하는 지점은 클러스터 중심 2입니다.

  3. 2단계를 반복하여 클러스터 중심 3을 찾습니다. 이번에는 클러스터 중심 2로부터 남은 이미지의 거리를 확인합니다.

  4. K 클러스터 중심을 확보할 때까지 프로세스를 반복합니다.

모델을 학습시키려면 훈련 작업을 SageMaker 생성해야 합니다. 요청에서 다음 HyperParameters 문자열 맵을 지정하여 구성 정보를 제공합니다.

• 생성할 클러스터의 수를 지정하려면 k 문자열을 추가합니다.

• 더 높은 정확도를 위해 선택 사항으로 extra_center_factor 문자열을 추가합니다.

• 초기 클러스터 중심을 결정할 때 사용하고자 하는 전략을 지정하려면 init_method 문자열을 추가하고 그 값을 random 또는 k-means++로 설정합니다.

SageMaker k-평균 추정기에 대한 자세한 내용은 Amazon Python SageMaker SDK 설명서의 K-평균을 참조하십시오.

이제 초기 클러스터 중심 세트를 보유합니다.

2단계: 훈련 데이터 세트 반복 및 클러스터 중심 계산

이전 단계에서 생성한 클러스터 중심은 대부분 임의적인 것으로 훈련 데이터 세트에 대한 일부 고려가 포함됩니다. 이 단계에서 훈련 데이터 세트를 사용하여 이 중심을 진짜 클러스터 중심으로 이동합니다. 알고리즘은 훈련 데이터 세트를 반복하고 K 클러스터 중심을 다시 계산합니다.

1. 훈련 데이터 세트에서 관측치의 미니 배치(모든 레코드에서 임의적으로 선택된 소형 서브셋)를 읽고 다음을 수행합니다.

   참고

   모델 훈련 작업 생성 시 mini_batch_size 문자열 맵의 HyperParameters 문자열에서 배치 크기를 지정합니다.

   1. 미니 배치의 모든 관측치를 가장 가까이에 있는 클러스터 중심이 포함된 클러스터 중 하나로 할당합니다.

   2. 각 클러스터에 할당된 관측치의 수를 계산합니다. 그런 다음 클러스터당 할당된 새 지점의 비율을 계산합니다.

      예를 들어 다음 클러스터를 고려해 보세요.

      클러스터 c1 = 이전에 할당된 100개의 지점. 이 단계의 미니 배치에서 25개의 지점을 추가합니다.

      클러스터 c2 = 이전에 할당된 150개의 지점. 이 단계의 미니 배치에서 40개의 지점을 추가합니다.

      클러스터 c3 = 이전에 할당된 450개의 지점. 이 단계의 미니 배치에서 5개의 지점을 추가합니다.

      다음과 같이 각 클러스터에 할당된 새 지점의 비율을 계산합니다.

      p1 = proportion of points assigned to c1 = 25/(100+25)
      p2 = proportion of points assigned to c2 = 40/(150+40)
      p3 = proportion of points assigned to c3 = 5/(450+5)

   3. 각 클러스터에 추가된 새 지점의 중심 컴퓨팅:

      d1 = center of the new points added to cluster 1
      d2 = center of the new points added to cluster 2
      d3 = center of the new points added to cluster 3

   4. 다음과 같이 업데이트된 클러스터 중심을 찾는 가중치 평균 컴퓨팅:

      Center of cluster 1 = ((1 - p1) * center of cluster 1) + (p1 * d1)
      Center of cluster 2 = ((1 - p2) * center of cluster 2) + (p2 * d2)
      Center of cluster 3 = ((1 - p3) * center of cluster 3) + (p3 * d3)

2. 다음 미니 배치를 읽고 1단계를 반복하여 클러스터 중심을 다시 계산합니다.

3. 미니 배치 k-means에 대한 자세한 정보는 웹 스케일 k-means 클러스터링을 참조하세요.

3단계: 클러스터를 K에서 k로 감소

알고리즘이 x가 1보다 큰 경우 K = k*x인 K 클러스터를 생성하는 경우 이는 K 클러스터를 k 클러스터로 축소합니다. (자세한 정보는 이전 논의의 extra_center_factor 참조) Lloyd의 메서드를 kmeans++ 초기화와 함께 K 클러스터 중심에 적용하여 이 작업을 수행합니다. Lloyd의 메서드에 대한 자세한 정보는 k-means clustering을 참조하세요.