K-평균 군집화

K-Means Clustering

절차

• k 개수 선정 (분류를 원하는 만큼 임의 지정)
• Centroid 배치
• 각 값과 Centroid의 거리 기준, 값 분류
• Centroid를 값의 중앙으로 이동
• 각 값과 Centroid의 거리 기준, 값 다시 분류 - 반복
• 값의 분류 변동이 없으면 종료

유형

• Randomly Select Centroid
  • Centroid를 랜덤하게 지정
• Manually Assign Centroid
  • Centroid의 초기값을 원하는 지점으로 선택
• k-mean++
  • 첫 Centroid를 기준으로 가장 먼 위치에 Centroid 지정

거리 측정

• 유클리디언 거리
• K-최근접 이웃

특징

• 군집 수 K를 초기에 미리 정해야 한다. 최적의 K는 엘보 기법이나 실루엣 계수로 고른다.
• 중심점(centroid)은 군집에 속한 값들의 평균이다. 실제 객체가 아니다. 군집 가운데 실제 객체를 중심으로 쓰는 것은 K-메도이드(K-Medoids, PAM)다.
• 평균을 쓰므로 이상치·노이즈에 민감하다. K-메도이드는 노이즈에 더 강하지만 연산량이 많다.
• 둥근(구형) 군집을 가정한다. 초승달 모양처럼 모양이 복잡한 군집에는 맞지 않는다 → 밀도 기반의 DBSCAN을 쓴다.
• 초기 중심점에 따라 결과가 달라질 수 있어 여러 번 돌리거나 k-means++ 로 초기값을 고른다.
• 계산이 단순하고 빨라 대용량 자료에 쓰기 좋다.

거리 계산 횟수

한 번 반복할 때 점마다 모든 군집 중심과의 거리를 구해 가장 가까운 군집에 배정한다.

• 중심이 평균점(실제 점이 아님)이면 반복 한 번에 n × k 번 계산한다. n = 100, k = 5 이면 500 번이다
• 중심을 대상 점들 가운데서 고르면(K-메도이드처럼), 중심으로 뽑힌 k 개 점은 자기 자신과 거리를 잴 필요가 없다. 반복 한 번에 (n − k) × k 번이다. n = 100, k = 5 이면 95 × 5 = 475 번이다
• 반복을 r 번 하면 r 을 곱한다. 위 조건에서 5번 반복하면 475 × 5 = 2,375 번이다
• 새 중심을 정하는 단계(평균 계산이나 대표점 선택)의 계산은 이 횟수와 따로 센다. K-메도이드가 중심 후보마다 군집 안 모든 점과의 거리 합을 비교하면 계산량이 훨씬 커진다

같이 보기

• 군집 분석
• DBSCAN
• 실루엣 계수