비지도 학습과 알고리즘

군집

군집^clustering : 비슷한 샘플을 구별해 하나의 클러스터 또는 비슷한 샘플의 그룹으로 할당하는 작업
클러스터^cluster : 보편적인 정의는 없다. 상황에 따라 다르고 어떤 모양이든 될 수 있고 종류가 아주 많다.
센트로이드^centroid : 클러스터의 특정 포인트

k-평균

각 클러스터의 중심을 찾고 가장 가까운 클러스터에 샘플을 할당
군집에서 각 샘플의 레이블은 알고리즘이 샘플에 할당한 클러스터의 인덱스

k-평균 알고리즘

처음에 센트로이드를 랜덤하게 선정
샘플에 레이블을 할당하고 센트로이드를 업데이트하는 식으로 센트로이드에 변화가 없을 때까지 계속 반복 (일반적으로 이 횟수는 매우 작다.)

센트로이드 초기화 방법

센트로이드 위치를 알 수 있다면 (e.g. 또 다른 군집 알고리즘을 먼저 실행) 직접 초기화
랜덤 초기화를 다르게 하여 어러 번 알고리즘을 실행하고 가장 좋은 솔루션을 선택
k-평균++ 초기화 알고리즘 (k-평균 알고리즘이 최적이 아닌 솔루션으로 수렴할 가능성을 크게 낮춘다.)

• 데이터셋에서 무작위로 균등하게 하나의 센트로이드 $c^{(1)}$을 선택
• $D(x^{(i)})^{2}/\sum_ {j=1}^{m}D(x^{(j)})^{2}$의 확률로 샘플 $x^{(i)}$를 새로운 센트로이드 $c^{(i)}$로 선택 (여기서 $D(x^{(i)})$는 샘플 $x^{(i)}$와 이미 선택된 가장 가까운 센트로이드까지 거리, 이 확률 분포는 이미 선택한 센트로이드에서 멀리 떨어진 샘플을 다음 센트로이드로 선택할 가능성을 높인다.)
• k개의 센트로이드가 선택될 때까지 이전 단계를 반복

이너셔^inertia : 각 샘플과 가장 가까운 센트로이드 사이의 평균 제곱 거리로 성능 지표

k-평균 속도 개선과 미니배치 k-평균

삼각 부등식^{triangle inequality}을 사용해 불필요한 계산을 많이 피함으로서 알고리즘의 속도를 높였다. (i.e. 두 점 사이의 직선은 항상 가장 짧은 거리) 그리고 샘플과 센트로이드 사이의 거리를 위한 하한선과 상한선을 유지
각 반복마다 미니배치를 사용해 센트로이드를 조금씩 이동한다. k-평균 알고리즘보다 훨씬 빠르지만 이너셔는 일반적으로 조금 더 나쁘다.

최적의 클러스터 개수 찾기

실루엣 점수^{silhouette score} : 모든 샘플에 대한 실루엣 계수의 평균
실루엣 계수^{silhouette coefficient} : $(b-a)/\text{max}(a,b)$

• $a$는 동일한 클러스터에 있는 다른 샘플까지 평균 거리 (i.e. 클러스터 내부의 평균 거리)
• $b$는 가장 가까운 클러스터까지 평균 거리 (i.e. 자신이 속한 클러스터는 제외하고 가장 가까운 클러스터의 샘플까지 평균 거리)
• +1에 가까우면 자신의 클러스터 안에 잘 속해 있고 다른 클러스터와는 멀리 떨어져 있다는 뜻
• 0에 가까우면 클러스터 경계에 위치한다는 의미이고 -1에 가까우면 잘못된 클러스터에 할당되었다는 의미

k-평균의 한계

k-평균의 장점

• 속도가 빠르고 확장이 용이

k-평균의 단점

• 여러 번 실행해야 하고 클러스터 개수를 지정해야 한다.
• 클러스터의 크기나 밀집도가 서로 다르거나 원형이 아닐 경우 잘 작동하지 않는다.

군집을 사용한 이미지 분할

이미지 분할^{image segmentation} : 이미지를 세그먼트^segment 여러 개로 분할하는 작업
시맨틱 분할^{semantic segmentation} : 동일한 종류의 물체에 속한 모든 픽셀은 같은 세그먼트에 할당
색상 분할^{color segmentation} : 동일한 색상을 가진 픽셀을 같은 세그먼트에 할당

군집을 사용한 전처리

군집은 차원 축소에 효과적인 방법
특히 지도 학습 알고리즘을 적용하기 전에 전처리 단계로 사용할 수 있다.

군집을 사용한 준지도 학습

레이블이 없는 데이터가 많고 레이블이 있는 데이터는 적을 때 사용
능동 학습^{active learning} : 전문가가 학습 알고리즘과 상호작용하여 알고리즘이 요청할 때 특정 샘플의 레이블을 제공

• 불확실성 샘플링^{uncertainty sampling}
  • 지금까지 수집한 레이블된 샘플에서 모델을 훈련 (이 모델을 사용해 레이블되지 않은 모든 샘플에 대한 예측을 만든다.)
  • 모델이 가장 불확실하게 예측한 샘플(i.e. 추정 확률이 낮은 샘플)을 전문가에게 보내 레이블을 붙인다.
  • 레이블을 부여하는 노력만큼의 성능이 향상되지 않을 때까지 이를 반복
• 다른 전략은 모델을 가장 크게 바꾸는 샘플이나 모델의 검증 점수를 가장 크게 떨어뜨리는 샘플, 여러 개의 모델(e.g. SVM이나 랜덤 포레스트)이 동일한 예측을 내지 않는 샘플에 대해 레이블을 요청

DBSCAN

밀집된 연속적 지역을 클러스터로 정의

• 알고리즘이 각 샘플에서 작은 거리인 $\varepsilon$(입실론) 내에 샘플이 몇 개 놓여 있는지 센다. (이 지역을 샘플의 $\varepsilon$-이웃^{$\varepsilon$-neighborhood}이라고 부른다.)
• (자기 자신을 포함해) $\varepsilon$-이웃 내에 적어도 min_samples개 샘플이 있다면 이를 핵심 샘플^{core instance}로 간주 (i.e. 핵심 샘플은 밀집된 지역에 있는 샘플)
• 핵심 샘플의 이웃에 있는 모든 샘플은 동일한 클러스터에 속한다. 이웃에는 다른 핵심 샘플이 포함될 수 있다. 따라서 핵심 샘플의 이웃의 이웃은 계속해서 하나의 클러스터를 형성
• 핵심 샘플이 아니고 이웃도 아닌 샘플은 이상치로 판단

다른 군집 알고리즘

병합군집^{agglomerative clustering}

반복마다 인접한 클러스터 쌍을 연결 (처음에는 샘플 하나에서 시작)
병합된 클러스터 쌍을 트리로 모두 그리면 클러스터의 이진 트리를 얻을 수 있다. (이 트리의 리프는 개별 샘플)
대규모 샘플과 클러스터에 잘 확장되며 다양한 형태의 클러스터를 감지
특정 클러스터 개수를 선택하는 데 도움이 되는 유용한 클러스터 트리를 만들 수 있다. (이는 어떤 짝 거리^{pairwise distance}와도 사용 가능)
이웃한 샘플 간의 거리를 담은 $m\times m$ 크기 희소 행렬을 연결 행렬로 전달하는 식으로 대규모 샘플에도 잘 적용 (연결 행렬이 없으면 대규모 데이터셋으로 확장하기 어렵다.)

BIRCH^{balanced iterative reducing and clustering using hierarchies}

훈련 과정에서 새로운 샘플을 클러스터에 빠르게 할당할 수 있는 정보를 담은 트리 구조를 만든다. (이 트리에 모든 샘플을 저장하지 않는다.)
이 방식은 제한된 메모리를 사용해 대용량 데이터셋을 다룰 수 있다.

평균-이동^mean-shift

각 샘플을 중심으로 하는 원을 그리고 원마다 안에 포함된 모든 샘플의 평균을 구한다.
그리고 원의 중심을 평균점으로 이동시키고 모든 원이 움직이지 않을 때까지 계속 반복 (i.e. 원의 중심이 포함된 샘플의 평균점일 때까지)
지역의 최대 밀도를 찾을 때까지 높은 쪽으로 원을 이동시키고 동일한 지역에 (또는 충분히 가깝게) 안착한 원에 있는 모든 샘플은 동일한 클러스터가 된다.
모양이나 개수에 상관없이 클러스터를 찾을 수 있고 국부적인 밀집도 추정에 의존
클러스터 내부 밀집도가 불균형할 때 여러 개로 나누는 경향이 있고 대규모 데이터셋에는 적합하지 않다.

유사도 전파^{affinity propagation}

샘플은 자신을 대표할 수 있는 비슷한 샘플에 투표 (투표 방식 사용)
알고리즘이 수렴하면서 각 대표와 투표한 샘플이 클러스터를 형성
크기가 다른 여러 개의 클러스터를 감지할 수 있고 대규모 데이터셋에는 적합하지 않다.

스펙트럼 군집^{spectral clustering}

샘플 사이의 유사도 행렬을 받아 저차원 임베딩을 만든다. (i.e. 차원을 축소)
그다음 이 저차원 공간에서 또 다른 군집 알고리즘을 사용
복잡한 클러스터 구조를 감지하고 그래프 컷^{graph cut}을 찾는 데 사용
샘플 개수가 많으면 잘 적용되지 않고 클러스터의 크기가 매우 다르면 잘 동작하지 않는다.

---

가우시안 혼합 모델^{Gaussian mixture model}(GMM)

샘플이 파라미터가 알려지지 않은 여러 개의 혼합된 가우시안 분포에서 생성되었다고 가정하는 확률 모델
타원형 클러스터에 잘 작동하지만 다른 모양을 가진 데이터셋에 훈련하면 나쁜 결과를 얻는다.
데이터셋 X가 다음 확률 과정을 통해 생성되었다고 가정 (사전에 가우시안 분포의 개수 k를 알아야 한다.)

• 샘플마다 k개의 클러스터에서 랜덤하게 한 클러스터가 선택된다. $j$번째 클러스터를 선택할 확률은 클러스터의 가중치 $\phi ^{(j)}$로 정의된다. $i$번째 샘플을 위해 선택한 클러스터 인덱스는 $z^{(i)}$로 표시
• $z^{(i)}=j$이면, 즉 $i$번째 샘플이 $j$번째 클러스터에 할당되었다면 이 샘플의 위치 $x^{(i)}$는 평균이 $\mu ^{(j)}$이고 공분한 행렬이 $\sum^{(j)}$인 가우시안 분포에서 랜덤하게 샘플링된다. (이를 $x^{(i)}\sim N(\mu^{(j)},\sum ^{(j)})$와 같이 쓴다.)

기댓값-최대화^{expectation-maximization}(EM) 알고리즘을 사용

• 클러스터 파라미터를 랜덤하게 초기화하고 수렴할때까지 두 단계를 반복
• 기댓값 단계^{expectation step}
  • 샘플을 클러스터에 할당
• 최대화 단계^{maximization step}
  • 클러스터를 업데이트
  • 클러스터를 중심뿐만 아니라 크기, 모양, 방향과 클러스터의 상대적 가중치를 찾는 k-평균의 일반화
• 최대화 단계에서 각 클러스터가 데이터셋에 있는 모든 샘플을 사용해 업데이트 (책임이 가장 많은 샘플에 크게 영향을 받는다.)
• 기댓값 단계에서 예측한 클러스터에 속할 추정 확률(클러스터의 책임^{responsibility})로 샘플에 가중치가 적용 (소프트 클러스터 할당)

생성 모델^{generative model} : 새로운 샘플을 만들 수 있다.
확률 밀도 함수^{probability density function}(PDF) : 주어진 위치에서 모델의 밀도를 추정 (샘플이 특정 지역 안에 속할 확률을 예측하려면 그 지역에 대해 PDF를 적분, 적분한 값을 다 더하면 1이 된다.)

가우시안 혼합을 사용한 이상치 탐지

이상치 탐지 ^{outlier detection} : 보통과 많이 다른 샘플을 감지하는 작업 (보통 샘플은 정상치^inlier)
밀도가 낮은 지역에 있는 모든 샘플을 이상치로 볼 수 있다.
이상치 탐지는 데이터셋을 정제하는 데 자주 사용
비슷한 작업으로 특이치 탐지^{novelty detection} (이상치로 오염되지 않은 '깨끗한' 데이터셋에서 훈련한다는 것이 다르다.)

클러스터 개수 선택하기

BIC^{Bayesian information criterion}나 AIC^{Akaike information criterion}와 같은 이론적 정보 기준^{theoretical information criterion}을 최소화하는 모델을 찾는다.
$\text{BIC}=log(m)p-2log(\hat{L})$
$\text{AIC}=2p-2log(\hat{L})$

• $m$은 샘플의 개수
• $p$는 모델이 학습할 파라미터 개수
• $\hat{L}$은 모델의 가능도 함수^{likelihood function}의 최댓값

BIC와 AIC는 모두 학습할 파라미터가 많은 (i.e. 클러스터가 많은) 모델에게 벌칙을 가하고 데이터에 잘 학습하는 모델에게 보상을 더한다.
둘은 종종 동일한 모델을 선택하지만 다를 경우 BIC가 선택한 모델이 AIC가 선택한 모델보다 간단한(파라미터가 적은) 경향이 있다. (데이터에 잘 맞지 않을 수 있다. 특히 대규모 데이터셋에서)

베이즈 가우시안 혼합 모델

최적의 클러스터 개수를 수동으로 찾지 않고 불필요한 클러스터의 가중치를 0으로 (또는 0에 가깝게) 만든다. (자동으로 불필요한 클러스터를 제거)
클러스터 파라미터(가중치, 평균, 공분산 행렬 등)는 더는 고정된 모델 파라미터가 아니라 클러스터 할당처럼 잠재 확률 변수로 취급

이상치 탐지와 특이치 탐지를 위한 다른 알고리즘

PCA (그리고 inverse_transform() 메서드를 가진 다른 차원 축소 기법)

보통 샘플의 재구성 오차와 이상치의 재구성 오차를 비교하면 일반적으로 후자가 크다. (이는 간단하고 효과적인 이상치 탐지 기법)

Fast-MCD^{minimum covariance determinant}

이상치 감지에 유용하고 특히 데이터셋을 정제할 때 사용

아이솔레이션 포레스트

고차원 데이터셋에서 이상치 감지를 위한 효율적인 알고리즘

LOF^{local outlier factor}

이상치 탐지에 좋은 알고리즘

one-class SVM

특이치 탐지에 잘 맞는 알고리즘

---

실습코드링크 : unsupervised learning