[머신러닝 & 딥러닝] K-means 알고리즘

---

00. K-평균 알고리즘을 사용하여 유사한 객체 그룹핑

• 군집 알고리즘(clustering) 
  • 비슷한 객체로 이루어진 그룹을 찾는 기법
  • 같은 그룹 안에 객체들과의 연관성이 다른 그룹 안의 객체들보다 연관성이 높음
  • 예시: 문서나 음악, 영화를 여러 주제의 그룹으로 모으는 경우, 추천 엔진에서 구매 이력을 기준으로 관심사 비슷한 고객을 찾음

---

01. 사이킷런을 이용한 k-평균 군집

• 장점: 구현하기 쉽고 다른 군집 알고리즘에 비해 계산 효율성이 높음
• 프로토타입 기반 군집(prototype-based clustering)
  • 의미: 각 클러스터가 하나의 프로토타입으로 표현됨
  • 연속적인 특성에서는 비슷한 데이터 포인트의 센트로이드(centroid), 즉 평균
  • 범주형 특성에서는 메도이드(medoid), 즉 가장 대표되는 포인트나 가장 자주 등장하는 포인트
• 원형 클러스터를 구분하는데 유용함
• 군집 품질 평가 방법: 엘보우 방법(elbow method), 실루엣 그래프(sihouette plot)
  • 최적의 k를 구하는데 유용함
• 실제 군집 애플리케이션에서는 샘플에 대한 진짜 카테고리 정보(실증 정보, 즉 타겟)가 존재하지 않음
  • 클래스 레이블이 존재한다면 지도 학습에 해당
  • 따라서 군집의 목표: 특성의 유사도에 기초하여 샘플을 그룹으로 모으는 것
• 단계 요약
  1. 샘플 포인트에서 랜덤하게 k개의 센트로이드를 초기 클러스터 중심으로 선택
  2. 각 샘플을 가장 가까운 센트로이드에 할당
  3. 할당된 샘플들의 중심으로 이동
  4. 클러스터 할당이 변하지 않거나 사용자가 지정한 허용 오차나 최대 반복 횟수에 도달할때까지 2,3 단계를 반복
• 샘플간의 유사도 측정: 거리의 반대 개념
  • 유클리디안 거리의 제곱(squared Euclidean distance): 연속적인 특성을 가진 샘플을 클러스터로 묶을 때 자주 사용

---

02. k-means의 문제

• 하나 이상의 클러스터가 비어있을 수 있음, 즉 소속된 포인트가 0개
  • 클러스터가 너무 촘촘하게 모여 있거나
  • 데이터 분포가 이상하거나
  • 클러스터 개수(k)가 너무 크면 
• k-메도이드(k-medoid), 퍼지 C-평균에는 나타나지 않음
• 사이킷런의 k-평균에는 문제를 고려함
  1. 빈 클러스터가 생기면
  2. 전체 데이터 포인트 중에서
  3. 모든 기존 중심점들과의 거리 합이 가장 큰 포인트를 찾아서
  4. 그 포인트를 새로운 중심(centroid) 으로 지정함

---

03. k-평균 알고리즘: 특성의 스케일

• 특성이 같은 스케일로 측정되어야 함
• 필요하다면 z-점수 표준화나 최소-최대 스케일로 변환해야 함

---

04. k-평균 알고리즘의 단점

• 사전에 k개의 클러스터를 지정해줘야 함
  • 적절하게 지정해주지 않으면 군집 성능이 좋지 않음
  • 개수를 몇 개로 설정할 지 실제 애플리케이션에서는 명확하지 않을 수 있음
  • 특히 시각화 할 수 없는 고차원 데이터셋에서 발생
• 클러스터가 중첩되지 않고 계층적이지 않음
• 각 클러스터에 적어도 하나의 샘플이 존재한다고 가정
  • 계층적 군집과 밀집도 군집과 같은 다른 알고리즘이 존재
    • 데이터셋에 원형 구조가 있다고 가정하지 않음
    • 사전에 클러스터의 개수를 지정할 필요가 없음

---

05. 기존 k-평균 알고리즘의 변형: k-평균++(k-means++)

• 초기 클러스터 센트로이드를 똑똑하게 할당
• 초기 센트로이드가 좋지 않게 선택 → 군집 결과를 만들거나 수렴이 느려짐
  • 해결 방법
    1. init = 'random'
       • 데이터셋에서 k-평균 알고리즘을 여러번 실행하여 SSE 입장에서 가장 성능이 좋은 모델을 선택하는 방법
    2. init = 'k-means++'
       • k-평균++ 알고리즘을 통해 초기 센트로이드가 서로 멀리 떨어지도록 위치하게 만듬 → 더 일관되고 훌륭한 결과를 만듬
• k-평균++ 정리
  1. 선택한 k개의 센트로이드를 저장할 빈 집합 M을 초기화
  2. 입력 샘플에서 첫 번째 센트로이드를 랜덤하게 선택하고 M에 할당
  3. M에 있지 않은 각 샘플에 대해 M에 있는 센트로이드까지 최소 제곱 거리를 찾음
  4. 가중치가 적용된 확률 분포를 사용하여 다음 센트로이드를 랜덤하게 선택
  5. k개의 센트로이드를 선택할 때까지 단계 3, 4를 반복
  6. 그다름 k-평균 알고리즘을 수행

---

06. 직접 군집 vs 간접 군집

• 직접 군집(hard clustering): 데이터셋의 샘플이 정확히 하나의 클러스터에 할당되는 알고리즘 종류
  • k-means, k-means++은 여기에 해당
• 간접 군집(soft clustering, == 퍼지 군집(fuzzy clustering)): 샘플이 하나 이상의 클러스터에 할당
  • 예시: 퍼지 C-평균(Fuzzy C-Means, FCM) 

---