2022/09/29 ~ 2022/10/04

[danbi5228]

2022-10-04 pm10:20 1: 9.1.6 2: 9.1.7 3: 9.2.1 전까지

[njs03332]

9.1.7 다른 군집 알고리즘

• 사이킷런에서 살펴볼 만한 여러 군집 알고리즘
• 병합 군집 (agglomerative clustering)
  • 클러스터 계층을 밑바닥부터 위로 쌓아 구성함
  • 하나의 샘플에서 시작, 반복마다 인접한 클러스터 쌍을 연결
  • 병합된 클러스터 쌍을 트리로 모두 그려 클러스터의 이진 트리를 얻을 수 있음
  • 대규모 샘플과 클러스터에 잘 확장됨
  • 다양한 형태의 클러스터를 감지할 수 있음
  • 클러스터 트리 - 특정 클러스터 개수를 선택하는 데 도움이 됨
  • 어떤 짝 거리 (pairwise distance)와도 사용할 수 있음
  • 대규모 샘플에도 잘 적용할 수 있음 (단, 연결 행렬이 없으면 대규모 데이터셋으로 확장하기 어려움)
• BIRCH (balanced iterative reducing and clustering using hierarchies)
  • 대규모 데이터셋을 위해 고안됨
  • 특성 개수가 20개 이하라면 배치 k-평균보다 빠르고 비슷한 결과를 만듦
  • 훈련 과정에서 새로운 샘플을 클러스터에 빠르게 할당할 수 있는 정보를 담은 트리 구조를 만듦
  • 제한된 메모리를 사용해 대용량 데이터셋을 다룰 수 있음
• 평균-이동
  • 각 샘플을 중심으로 하는 원을 그리고, 원마다 안에 포함된 모든 샘플의 평균을 구함 -> 원의 중심을 평균점으로 이동시킴 -> 모든 원이 움직이지 않을 때까지 mean-shift (평균 이동)을 계속함
  • 평균 이동은 지역의 최대 밀도를 찾을 때까지 높은 쪽으로 원을 이동시킴
  • DBSCAN과 유사한 특징
  • 모양이나 개수에 상관없이 클러스터를 찾을 수 있음
  • 하이퍼파라미터가 매우 적음 (bandwidth 하나)
  • 국부적인 밀집도 추정에 의존함
  • DBSCAN과 달리 클러스터 내부 밀집도가 불균형할 때 여러 개로 나누는 경향이 있음
  • 대규모 데이터셋에는 적합하지 않음 (계산 복잡도가 O(m²)
• 유사도 전파
  • 샘플이 자신을 대표할 수 있는 비슷한 샘플에 투표함
  • 알고리즘이 수렴하면 각 대표와 투표한 샘플이 클러스터를 형성함
  • 크기가 다른 여러 개의 클러스터를 감지할 수 있음
  • 대규모 데이터셋에는 적합하지 않음 (계산 복잡도가 O(m²)
• 스펙트럼 군집
  • 샘플 사이의 유사도 행렬을 받아 저차원 임베딩을 만든 후 (차원 축소)
  • 이 저차원 공간에서 도 다른 군집 알고리즘을 사용함 (사이킷런에서는 k-평균)
  • 복잡한 클러스터 구조를 감지하고 그래프 컷 (graph cut) 을 찾는 데 사용할 수 있음
  • 샘플 개수가 많으면 잘 적용되지 않음
  • 클러스터의 크기가 매우 다르면 잘 동작하지 않음

[givitallugot]

9.1.6 DBSCAN

• 밀집된 연속적 지역을 클러스터로 정의, 모든 클러스터가 충분히 밀집되어 있고 밀집되지 않은 지역과 잘 구분될 때 좋은 성능

[작동 방식]

• 알고리즘이 각 샘플에서 ε-이웃 내 샘플이 몇 개 놓여 있는지 셈, 샘플의 ε-이웃이라고 부름
• ε-이웃 내 적어도 min_sample개 샘플이 있다면 이를 핵심 샘플로 간주, 즉 핵심 샘플은 밀집된 지역에 있는 샘플
• 핵심 샘플의 이웃에 있는 모든 샘플은 동일한 클러스터에 속함
• 핵심 샘플이 아니고 이웃도 아닌 샘플은 이상치로 판단

[ex 반달 모양 데이터 셋]

from sklearn.datasets import make_moons
from sklearn.cluster import DBSCAN

X, y = make_moons(n_samples=1000, noise=0.05, random_state=42)
dbscan = DBSCAN(eps=0.05, min_samples=5)
dbscan.fit(X)
# DBSCAN(eps=0.05)

dbscan.labels_[:10]
# array([ 0,  2, -1, -1,  1,  0,  0,  0,  2,  5])

dbscan.core_sample_indices_[:10] # 핵심 샘플의 인덱스
# array([ 0,  4,  5,  6,  7,  8, 10, 11, 12, 13])

dbscan.components_[:3]
# array([[-0.02137124,  0.40618608],
#         [-0.84192557,  0.53058695],
#         [ 0.58930337, -0.32137599]])

• labels에 클러스터 인덱스 존재, -1은 해당 샘플이 이상치로 판단되었다는 의미

• eps: epsilon 파라미터

• eps를 0.2로 증가해서 이웃의 범위를 넓히면 오른쪽 그래프처럼 완벽한 군집을 얻을 수 있음

  

• predict() 메서드를 제공하지 않고 fit_predict()만 존재, 즉 새로운 샘플에 대해 클러스터를 예측할 수 없음

• 필요한 예측기를 추가로 선택해야 함, 예를 들어 핵심 샘플만 가지고 다시 예측기를 만들어서 새로운 샘플에 대해 클러스터 레이블을 예측

from sklearn.neighbors import KNeighborsClassifier

knn = KNeighborsClassifier(n_neighbors=50)
knn.fit(dbscan.components_, dbscan.labels_[dbscan.core_sample_indices_])

X_new = np.array([[-0.5, 0], [0, 0.5], [1, -0.1], [2, 1]])
knn.predict(X_new)
# array([1, 0, 1, 0])



• 이 분류기의 결정 경계는 위와 같음, X_new의 샘플 네 개가 표시되어 있음
• DBSCAN은 클러스터 모양과 개수에 상관없이 감지할 수 있는 능력 존재, 하이퍼파라미터는 eps, min_samples 두 개뿐

[danbi5228]

9.2 가우시안 혼합

• 가우시안 혼합 모델 Gaussian mixture model(GMM)은 샘플이 파라미터가 알려지지 않은 여러 개의 혼합된 가우시안 분포에서 생성되었다고 가정하는 확률모델
• 하나의 가우시안 분포에서 생성된 모든 샘플은 하나의 클러스터를 형성 (일반적으로 이 클러스터는 타원형)
• 여러 GMM 변종이 존해하고, 가장 간단한 버전이 사이킷런 GaussianMixture 클래스에 구현 - 사전에 가우시안 분포의 개수 k를 알아야 함
• 가우시안 혼합 모델의 그래프 모형
  • 
  • 그래프 보는 법
  • 원: 확률 변수 / 색이 채워진 원: 알려진 값. 관측 변수 (cf. 알려지지 않은 확률 변수 = 잠재 변수)
  • 사각형: 고정값 / 큰 사각형: 플레이트 plate. 이 사각형 안의 내용이 여러번 반복됨 (플레이트 오른쪽 아래 숫자만큼 반복)
  • 과정 설명
  • 샘플마다 k개의 클러스터에서 랜덤하게 한 클러스터가 선택되고, j번째 클러스터를 선택할 확률은 클러스터의 가중치 ø(j)로 정의
  • i번째 샘플을 위해 선택한 클러스터 인덱스는 z(i)로 표시
  • z(i)=j 이면, 즉 i번째 샘플이 j번째 클러스터에 할당되었다면 이 샘플의 위치 x(i)는 평균이 μ(j)이고 공분산 행렬이 Σ(j) 인 가우시안 분포에서 랜덤하게 샘플링됨 (= x(j) ~ N( μ(j), Σ(j) ) )
  • 이 모델로 데이터셋 X가 주어지면 가중치 Φ와 전체 분포의 파라미터 μ(1)에서 μ(k)까지, Σ(1)에서 Σ(k)까지 추정
• GaussianMixture 클래스를 이용한 혼합 모델 생성

  
  from sklearn.mixture import GaussianMixture

n_init : k평균처럼 나쁜 솔루션으로 수렴할 수 있으므로 여러번 실행하도록 10으로 설정. 기본값은 1

gm = GaussianMixture(n_components=3, n_init=10) gm.fit(X)

gm.weights # 추정 가중치 --> 실제 데이터 생성할 때 사용한 가중치 값과 매우 유사 gm.means # 평균 gm.covariances_ # 분산 행렬

gm.converged_ # 수렴 여부. True or False 를 리턴 gm.niter # 반복 횟수

- 해당 클래스는 기댓값-최대화 Expectation-maximization (EM) 알고리즘을 사용함
- EM 알고리즘은 클러스터 파라미터를 랜덤하게 초기화하고 수렴할 때까지 두 단계를 반복함
  - 기댓값 단계: 현재 클러스터 파라미터에 기반해서 각 클러스터에 속할 확률을 예측
  - 최대화 단계: 각 클러스터가 데이터셋에 있는 모든 샘플을 사용해 업데이트 됨. 클러스터에 속할 추정 확률로 샘플에 가중치가 적용됨
  - 군집 입장에서 EM을 클러스터 중심 뿐만 아니라 크기, 모양, 방향과 클러스터의 가중치를 찾는 k-평균의 일반화로 생각할 수 있음
  - k 평균은 EM과 같은 소프트 클러스터 할당이 아닌, 하드 클러스터 할당 방식 (확률 예측 대신, 가장 비슷한 클러스터에 바로 할당)

```python
gm.predict(X) # 하드 군집
gm.predict_proba(X) # 소프트 군집

X_new, y_new = gm.sample(6) # 가우시한 혼합 모델은 생성모델이므로 새로운 샘플을 만들 수 있음 (반환된 샘플은 클러스터 인덱스 순 정렬)

gm.score_samples(X) # 모델의 밀도 추정

• 주어진 위치에서 확률 밀도 함수(PDF)의 로그를 예측. 점수가 높을 수록 밀도가 높음
  • 확률이 아닌 확률 밀도이므로 어떤 양숫값도 될 수 있음. 확률 예측을 위해서는 그 지역에 대해 PDF를 적분해야 함
  • 
• 실제 데이터는 가우시안 분포나 저차원이 아닌 경우가 많고, 클러스터 갯수를 정확히 알 수 없어 위처럼 훌륭한 솔루션을 찾는 것이 어려움
• 특성이나 클러스터가 많거나 샘플이 적을 때는 EM이 최적의 솔루션으로 수렴하기 어려움
  • 어려움을 줄이려면 알고리즘이 학습할 파라미터 개수를 제한해야 함. 이 방법 중 하나는 클러스터의 모양과 방향의 범위를 제한하는 것
  • 사이킷런에서는 covariance_type 매개변수에 spherical / diag / tied 중 하나로 설정하여 제한 가능 (기본값은 full. 제한 없음)
  • spherical: 모든 클러스터가 원형. 지름(즉, 분산)은 다를 수 있음
  • diag: 클러스터 크기에 상관없이 어떤 타원형도 가능. 하지만 타원의 축은 좌표축과 나란해야 함
  • tied: 모든 클러스터가 동일한 타원 모양, 크기, 방향을 가짐 (즉, 모든 클러스터는 동일한 공분산 행렬을 공유
  •