2022/9/1~2022/9/14

[njs03332]

• 1: 9.1 의 9.1.1 전까지
• 2: 9.1.1 k-평균 알고리즘 전까지
• 3: 센트로이드 초기화 방법 까지
• 9/14 수요일 10:30PM

[njs03332]

9.1.1 k-평균

k-평균 알고리즘

• k-평균 알고리즘 작동 방식

  • 센트로이드를 랜덤하게 선정 (무작위로 k 개의 샘플을 뽑아 지정)
  • 샘플에 레이블을 할당하고 센트로이드를 업데이트하는 과정을 반복
  • 센트로이드에 변화가 없을 때까지
  • 이 알고리즘은 제한된 횟수 안에 수렴하는 것을 보장함

• 계산 복잡도: 샘플 개수 m, 클러스터 개수 k, 차원 개수 n에 선형적

  • 그러나 최악의 경우 샘플 개수에 대해 지수적으로 급격히 증가할 수 있음
  • 일반적으로는 가장 빠른 군집 알고리즘 중 하나

• 이 알고리즘은 적절한 솔루션으로 수렴하지 못할 수 있음 (지역 최적점으로 수렴)

  • 이 여부는 센트로이드 초기화에 달려있음

센트로이드 초기화 방법

• 센트로이드 위치를 근사하게 알 수 있는 경우 (예: 또 다른 군집 알고리즘을 먼저 실행)

  • init 매개변수에 센트로이드 리스트를 담은 넘파이 배열을 지정하고 n_init=1로 설정

    good_init = np.array([[-3,3],[-3,1],[-3,1],[-1,2],[0,2]])
    kmeans = KMeans(n_clusters=5, init=good_init, n_init=1)

• 랜덤 초기화를 다르게 하여 어러 번 알고리즘을 실행하고 가장 좋은 솔루션을 선택

  • 랜덤 초기화 횟수는 n_init 매개변수로 조절 (기본값은 10)
  • 최선의 솔루션을 평가하는 방법: 이너셔 (inertia)라는 성능 지표를 사용함
  • 즉, KMeans 클래스는 알고리즘을 n_init 번 실행하여 이너셔가 가장 낮은 모델을 반환
  • 이 값은 inertia_ 인스턴스 변수로 확인 가능
  • score() 메서드는 이너셔의 음숫값을 반환함 (사이킷런의 '큰 값이 좋은 것이다'라는 규칙을 따라야 하기 때문)

• k-평균++ 알고리즘

  • 다른 센트로이드와 거리가 먼 센트로이드를 선택하는 똑똑한 초기화 단계를 소개함
  • 최적이 아닌 솔루션으로 수렴할 가능성을 크게 낮춤
  • 알고리즘 반복 횟수를 크게 줄일 수 있기 때문에 이 초기화 단계에 드는 추가 계산이 충부한 가치가 있다는 것을 보여줌
  • KMeans 클래스는 기본적으로 이 초기화 방법을 사용함
  • 원래 방식을 사용하고 싶다면 init="random"으로 지정

[givitallugot]

9.1.1 k-평균

k-평균

• 아래와 같이 레이블 없는 데이터 셋
• 몇 번의 반복을 통해 데이터셋을 빠르게 효율적으로 클러스터로 묶을 수 있음
• 1957년 벨 연구소의 스튜어트 로이드와 1965년 에드워드 포지에 의해 알고리즘 발표됨

from sklearn.cluster import KMeans

k = 5
kmeans = KMeans(n_clusters=k, random_state=42)
y_pred = kmeans.fit_predict(X)

• 결과로 나오는 레이블은 알고리즘이 샘플에 할당한 클러스터 인덱스
• 알고리즘이 찾은 센트로이드 확인

  
  kmeans.labels_
  # array([4, 0, 1, ..., 2, 1, 0], dtype=int32)

kmeans.clustercenters

array([[-2.80389616, 1.80117999],

[ 0.20876306, 2.25551336],

[-2.79290307, 2.79641063],

[-1.46679593, 2.28585348],

[-2.80037642, 1.30082566]])

- 클러스터의 결정 경계를 그려보면 보로노이 다이어그램을 얻을 수 있음
- 샘플은 대부분 적절한 클러스터에 할당
<img width=400 src=https://user-images.githubusercontent.com/50584633/190105267-af2ae3c9-b0f8-4214-a949-e983af94a544.png>

- 하드 군집: 샘플을 하나의 클러스터에 할당하는 것
- 소프트 군집: 클러스터마다 샘플에 점수를 부여하는 것 ex 샘플과 센트로이드 사이의 거리, 가우시안 방사 기저 함수와 같은 유사도 점수
- transform() 메서드는 샘플과 각 센트로이드 사이의 거리 반환
```python
kmeans.transform(X_new)
# array([[2.81093633, 0.32995317, 2.9042344 , 1.49439034, 2.88633901],
#        [5.80730058, 2.80290755, 5.84739223, 4.4759332 , 5.84236351],
#        [1.21475352, 3.29399768, 0.29040966, 1.69136631, 1.71086031],
#        [0.72581411, 3.21806371, 0.36159148, 1.54808703, 1.21567622]])
# 첫 번째 샘플이 첫 번째 센트로이드에서 2.81, 두 번째 센트로이드에서 0.33 ... 거리 만큼 떨어짐

[danbi5228]

9.1 군집

• 군집 clustering : 비슷한 샘플을 구별해 하나의 클러스터 또는 비슷한 샘플의 그룹으로 할당하는 작업. 비지도 학습
• 
  • 모든 특성을 사용하면 가운데와 같이 레이블이 없는 데이터에 대해서도 군집 알고리즘이 클러스터 세 개를 매우 잘 구분할 수 있음
  • 예를 들어 가우시안 혼합 모델을 사용하면 150개중 5개 샘플만 잘못된 클러스터로 할당 (오른쪽 그래프 확인)
• 군집의 활용 범위
  • 고객 분류: 고객 구매 이력이나 웹사이트 내 행동을 기반으로 클러스터 모을 수 있음. ex. 추천 시스템
  • 데이터 분석: 새로운 데이터셋 분석할 때 군집 알고리즘을 실행하고 각 클러스터를 따로 분석하면 도움이 됨
  • 차원축소 기법: 각 클러스터에 대한 샘플의 친화성을 측정, 즉 특성벡터 x를 사용하면 원본 특성벡터보다 저차원으로 유의미한 분석가능
  • 이상치 탐지: 모든 클러스터에 친화성이 낮은 샘플을 감지. ex. 부정 거래 감지
  • 준지도 학습: 레이블된 샘플이 적다면 군집 수행 후, 동일 클러스터에 있는 모든 샘플에 레이블 전파 가능
  • 검색 엔진: 제시된 이미지와 비슷한 이미지 찾기 - 먼저 모든 이미지에 군집 알고리즘 적용이 필요
  • 이미지 분할: 색을 기반으로 픽셀을 클러스터로 모은 뒤, 평균색으로 바꿔 이미지 종류를 줄이면 물체 윤곽 탐지 가능
• 클러스터에 대한 보편적인 정의는 없고, 상황에 따라 다름
• 알고리즘이 다르면 다른 종류/모양의 클러스터를 감지함