목차
1. 군집 (Clustering)
1.1 k-평균
1.2 k-평균의 한계
2. DBSCAN
2.1 DBSCAN 동작 원리
2.2 DBSCAN을 활용하여 새로운 샘플의 클러스터 예
3. 가우시안 분포
4. 가우시안 혼합 모델 (Gaussian mixture model) 이란?
4.1 가우시안 혼합 모델(GMM)의 그래프 모형
4.2 기댓값-최대화(EM) 알고리즘
4.2.1 초기화
4.2.2 기대값 단계
4.2.3 최대화 단계
4.2.4 EM 알고리즘 정리
4.3 이상치 탐지
4.4 클러스터 개수 선택하기
5. 베이즈 가우시안 혼합 모델(BayesianGaussianMixture model)
5.1 베이즈 가우시안 혼합 모델 모형
5.2 베이즈 정리
비지도 학습이란?
비지도 학습인 라벨링이 되어 있지 않은 데이터를 학습시키는 방법론입니다. 라벨링이 되어 있지 않다는 이야기는 정답, 즉 y가 없다는 의미입니다. 오늘날 생성되는 대부분의 데이터에는 라벨링이 되어 있지 않습니다. 알려진 입력 특성 X는 있지만 모델이 예측해야할, 훈련시켜야 할 y값이 없습니다.
이러한 데이터는 많은 비용을 투자하여 수동으로 라벨링을 하여야 하는데 현실적으로 그러기는 매우 어렵습니다. 그래서 보통 수많은 데이터들 중 일부분만 라벨링하여 모델에 사용하고 나머지는 사용하지 않습니다. 매우 비효율적이죠. 또한 적은 수의 데이터로 모델을 학습시켰으니 모델의 성능 또한 좋지 않을 것입니다.
이럴때 우리는 비지도 학습을 이용할 수 있습니다. 지금부터 어떻게 비지도 학습을 통해 모델을 학습시키는지 알아보도록 하겠습니다.
1. 군집 (Clustering)
비슷한 샘플들끼리 구별하여 하나의 클러스터(Cluster) 또는 비슷한 샘플의 그룹으로 할당하는 작업을 우리는 군집이라고 합니다. 군집(Cluster)은 분류(Classification)와 같이 각 샘플은 하나의 그룹으로 할당됩니다. 하지만 군집은 분류와 다르게 비지도 학습입니다. 따라서 데이터에 레이블이 달려있지 않고 기존에 공부하였던 분류 알고리즘인 로지스틱 회귀, SVM, 랜덤 포레스트를 사용할 수 없습니다. 이때는 군집 알고리즘을 사용합니다.
군집 알고리즘을 이용해 클러스터를 만들어 내는 것에는 보편적인 기준이 없습니다. 상황마다 클러스터는 다르게 정의되고 감지되어 결과로 나타나게 됩니다. 어떤 것은 centroid라고 부르는 특정 포인트의 중심으로 샘플을 찾습니다. 어떤 것은 샘플이 밀집되어 연속된 영역을 찾습니다. 계층이 될 수 있습니다.
1.1 k-평균
역사
k-평균 알고리즘은 1957년 벨 연구소에서 Stuart Lloyd가 제안하였습니다. 하지만 연구소에서 개발한 것이라 벨 연구소에서는 1982년에서야 외부에 공개되었고, 그 사이 1965년 Edward W. Forgy가 사실상 동일한 알고리즘을 발표했습니다.
따라서 k-평균 알고리즘은 두 연구자의 이름은 딴 Lloyd-Forgy 알고리즘이라고 부르기도 합니다.
k-평균 알고리즘은 각 클러스터의 중심을 찾고 가장 가까운 클러스터에 샘플들을 할당하여 군집화 시킵니다.
먼저 k-평균 알고리즘을 훈련시키기 위해서는 알고리즘이 몇개의 클러스터로 나눌지의 지표인 k를 지정해야 합니다. 위 데이터셋에서는 k를 5로 지정해야 한다는 것을 직관적으로 알 수 있지만, 많은 데이터셋에서는 k를 지정하는 것은 직관으로 해결되지 않습니다.
k(=5)를 지정하고 나면 모든 샘플들은 다섯 개의 클러스터 중 하나에 할당됩니다. 여기서 참고할 것은 군집에서 각 샘플의 레이블은 알고리즘이 샘플에 할당한 클러스터의 인덱스라는 것입니다. 분류(Classification)에서의 class label과는 다른 것입니다.
지도 학습 : Classification --> class label
비지도 학습 : Clustering --> cluster index
위 데이터셋을 k-평균 알고리즘을 통해 군집화하고 나면, 클러스터들의 결정 경계를 그릴 수 있습니다. 또한 결정 경계를 그리면 보로노이 다이어그램(Voronoi Diagram)을 그릴 수 있습니다.
보로노이 다이어그램 (Voronoi Diagram)
보로노이 다이어그램은 가장 가까운 거리에 있는 점과 점 사이를 선으로 잇고, 그 선을 수직 이등분선으로 분할한 것이 경계가 되어 그려지는 그림을 의미합니다. 현재 우리가 보고 있는 위의 그림에서는 seed가 되는 두 점을 잇고, 그 중심에서 결정 경계가 생기게 되어 그림이 그려지게 됩니다.
k-평균 알고리즘을 통해 군집화를 한 결과 대부분의 샘플은 적절한 클러스터에 잘 할당이 되었습니다. 하지만 모든 샘플이 그런 것은 아닙니다. 왼쪽 위의 분홍색 클러스터와 가운데의 노란색 클러스터의 경계 부분에서는 샘플이 잘 할당되지 않은 것처럼 보입니다. 실제로 k-평균 알고리즘은 클러스터의 크기가 많이 다르면 잘 작동하지 않습니다. 즉, 어떤 클러스터는 매우 작고 어떤 클러스터는 매우 크면 적절하게 작동하지 않음을 의미합니다. 이렇게 되는 이유는 다음과 같습니다. k-평균 알고리즘은 클러스터의 centroid와 샘플과의 거리만을 이용하여 clustering하기 떄문입니다.
하드 군집 : 하나의 샘플이 하나의 군집에만 할당되는 것
소프트 군집 : 하나의 샘플이 여러 개의 군집에 할당되는 것
이런 문제를 해결하기 위해서 소프트 군집(soft clustering) 개념을 도입할 수 있습니다. 하나의 cluster index를 샘플에 부여하는 것이 아니라 scoreing 개념을 도입합니다. 소프트 군집에서 score는 sample과 centroid의 거리, 유사도 점수 등 다양하게 정의할 수 있습니다. 이를 통해 결정 경계에 있는 샘플에 대한 문제를 해결할 수 있습니다.
군집을 통해서 할 수 있는 것 중 하나는, 고차원 데이터셋을 매우 효율적이게 차원 축소 기법으로 사용할 수 있다는 것입니다. 특징을 많이 가지고 있는 데이터셋을 k개의 군집으로 나누면 k-차원 데이터셋이 만들어지기 때문입니다.
- k-평균 알고리즘
k-평균 알고리즘이 어떻게 작동하는지 조금 더 자세히 알아보도록 하겠습니다.
만약 클러스터의 centroid가 주어지거나, 샘플들에 레이블이 주어진다면 알고리즘을 작동시키기 아주 쉽습니다. centroid가 주어진다면 샘플들은 자기 자신과 가장 가까운 centroid에 할당시켜 clustering 시키면 됩니다. 또한 샘플들에 레이블이 주어진다면 같은 레이블 내에 있는 샘플들의 특징을 평균내어 기준을 새우면 clustering 시키기 쉽습니다.
하지만 보통은 아무런 기준이 없는 상태에서 k-평균 알고리즘을 수행해야 합니다. 이런 경우에는 먼저 centroid를 무작위로 선정합니다. 선정된 centroid를 기준으로 클러스터 인덱스를 할당합니다. 그런 다음 centroid를 업데이트하고 샘플에 다시 클러스터 인덱스를 할당합니다. 이렇게 계속해서 반복하면 centroid의 변화가 없을때가 생깁니다. 이 지점까지 위 프로세스를 진행합니다. 이러한 방식은 제한된 횟수 안에 결과로 수렴하는 것을 보장합니다.
k-평균 알고리즘의 계산 복잡도
k-평균 알고리즘은 m, k, n에 선형적입니다.
m : 샘플 개수
k : 클러스터 개수
n : 차원 개수
이것은 데이터가 군집할 수 있는 형태를 가지고 있을 때 이야기입니다. 만약 데이터가 군집을 할 수 없는 형태를 띄고 있다면 지수적으로 계산 복잡도가 증가합니다. 하지만 현실에서는 대부분의 데이터가 군집할 수 있는 형태를 띄고 있는 경우가 대부분입니다.
k-평균 알고리즘은 결과에 수렴되는 것을 보장하지만, 최적의 솔루션이 아닐 수 있습니다. 즉 지역 최적점에 빠질 수 있습니다. 최적의 솔루션에 이르지 못하는 이유는 centroid를 초기화에 달려 있습니다.
- 센트로이드 초기화 방법
센트로이드를 어떻게 초기화하냐에 따라 최적의 솔루션을 가지지 못할 수 있다는 것을 알게 되었습니다. 어떻게 하면 센트로이드를 적절하게 잘 초기화할 수 있을까요?
k-평균 알고리즘을 여러번 수행하고 그 중 가장 적절한 센트로이드를 사용하는 것입니다. 알고리즘이 10번 시행되었다고하면 우리는 어떤 센트로이드가 최적인지를 알아야 할 것입니다. 그것의 성능 지표를 이너셔(inertia)라고 부릅니다. 이너셔는 다음과 같이 정의됩니다.
이너셔는 각 샘플과 가장 가까운 센트로이드 사이의 평균 제곱 거리입니다. 이렇게 계산이 되면 이너셔가 작을수록 최적의 모델이라는 것을 알 수 있습니다.
- k-평균++ 알고리즘
2006년 데이비드 아서(David Arthur)와 세르게이 바실비츠키(Sergei Vassilvitskii)가 k-평균 알고리즘을 향상시킨 k-평균++ 알고리즘을 제안했습니다. 이들은 처음 센트로이드를 초기화할 때 각각의 센트로이드들의 거리가 멀도록 초기화 하는 방법을 소개했습니다. 이 방법을 사용해서 최적의 솔루션에 수렴할 가능성을 크게 늘렸습니다. 사이킷런에서 제공하는 k-평균 알고리즘은 기본적으로 k-평균++ 알고리즘을 사용합니다.
- k-평균 속도 개선과 미니배치 k-평균
2013년 찰스 엘칸(Charles Elkan)은 삼각 부등식을 도입하여 불필요한 거리 계산을 줄임으로써 알고리즘의 속도를 크게 향상시켰습니다.
2010년 데이비드 스컬리(David Sculley)는 센트로이드를 업데이트하기 위해 전체 데이터셋을 사용해 반복하지 않고 각 반복마다 미니배치를 사용했습니다. 이를 사용해 알고리즘의 속도를 3배 정도 향상시켰습니다.
이처럼 미니배치를 이용하면 메모리에 들어가지 않는 대규모 데이터셋에 대해 군집 알고리즘을 적용할 수 있습니다. 하지만 미니배치 k-평균 알고리즘은 일반 k-평균 알고리즘보다 이너셔는 좋지 않습니다. 빠르지만 최적의 군집화를 시킬 확률은 낮은 것입니다.
그림에서 미니배치 k-평균 알고리즘의 이너셔는 더 높게 나오지만, 더 빨리 작동합니다.
- 최적의 클러스터 개수 찾기
이때까지 봤던 데이터셋은 직관적으로 최적의 클러스터 개수 k를 결정하기 쉬웠습니다. 하지만 일반적으로는 쉽지 않습니다.
기존의 데이터셋에서 가장 적절한 클러스터 개수는 5 였지만, 적절하지 않은 3 또는 8을 적용했을 때 군집화는 좋은 성능을 보이지 않습니다.
우리는 앞서 공부해왔던 것을 바탕으로 이너셔가 가장 작은 모델이 가장 좋은 모델이라고 생각할 수 있습니다. 그래프에서 k의 개수가 증가할수록 이너셔가 작아지는 것을 볼 수 있습니다. 그럼 이너셔가 가장 작은 k=8에서 가장 좋은 모델일까요? 아닙니다. 우리는 k=5가 최적의 클러스터 개수라는 것을 알고 있습니다. 이렇듯 이너셔가 절대적인 지표가 되진 못합니다. 우리는 위 그래프에서 이너셔가 빠르게 감소하는 지점과 느리게 감소하는 지점인 엘보에서 클러스터 개수를 지정하는 것이 좋은 선택이라고 할 수 있겠습니다.
최선의 클러스터 개수를 구하는 이와 같은 방법은 매우 허술합니다. 따라서 더 정확한 클러스터 개수를 선택하기 위해 실루엣 점수(silhouette score) 개념을 도입합니다.
실루엣 계수의 의미는 다음과 같습니다. 군집 내에서 거리 기반 유사도는 크고 인접한 군집 간 유사도는 작게 나온다면 클러스터 개수 k를 잘 정했다고 볼 수 있습니다. a는 자신이 속한 클러스터 내의 다른 샘플들과의 평균 거리입니다. b는 자신이 속한 클러스터가 아닌 가장 인접한 클러스터에 있는 샘플들과의 평균 거리입니다. 이것을 적용하여 한 번 생각을 해봅시다.
만약 적절하게 k를 설정했다면 군집 내에서 샘플들의 거리 평균은 작게 나오고, 인접 군집의 샘플에 대한 평균 거리는 크게 나올 것입니다.
반대로 k를 적절하게 설정하지 못했다면 군집 내에서 샘플들의 거리 평균은 크게 나오고, 인접 군집의 샘플에 대한 평균 거리는 작게 나올 것입니다.
실루엣 계수는 -1 ~ +1의 범위를 가지고 +1에 가까울수록 자신의 클러스터에 잘 속해 있다는 것을 의미합니다. 0에 가까우면 샘플이 클러스터 경계에 위치한다는 이야기이고, -1에 가까우면 샘플이 잘못된 클러스터에 할당되었다는 것을 의미합니다.
위 그래프는 클러스터 개수 k에 따라서 실루엣 점수가 어떻게 변하는지 나타내 줍니다. 실루엣 점수가 1에 가까울 k=4, 5에서 최적의 솔루션을 구할 수 있다는 것을 알 수 있습니다.
모든 샘플에 대해서 실루엣 계수를 구한 다음 같은 클러스터에 속하는 것을 같은 색으로 표현하고 계수값에 따라 내림차순으로 정리하면 실루엣 다이어그램(silhouette diagram)을 얻을 수 있습니다. 실루엣 다이어그램에서 세로 높이는 샘플의 개수를 의미하고, 가로 길이는 실루엣 계수를 의미합니다. 실루엣 계수는 1에 가까울수록 최적의 솔루션이라는 뜻이기에 넓을수록 좋습니다.
그림에 나타나있는 빨간색 수직 파선은 실루엣 점수(모든 실루엣 계수들의 평균)를 의미합니다. 한 클러스터의 샘플 부분이 이 점수보다 낮은 계수를 가지면 클러스터의 샘플들이 인접 클러스터와 너무 가깝다는 것을 의미합니다. 최적의 솔루션을 얻지 못했다는 것이지요. k=5일 때 모든 클러스터가 실루엣 점수 인근에 위치해 있고 분포가 일정하게 보입니다. k=5일 때가 최적의 솔루션이라는 것을 직관적으로 이해할 수 있습니다. 실루엣 계수가 +1에 많이 인접해 있는 k=4일 때 보다, +1에 근접함은 덜하지만 일정하게 분포하고 있는 k=5를 선택하는 것이 올바른 선택입니다.
1.1.2 k-평균의 한계
k-평균 알고리즘은 속도가 빠르다는 장점을 가지고 있습니다. 하지만 한계로는 한번에 최적을 솔루션을 찾을 수 없기 때문에 여러 번 실행해야 한다는 점입니다. 또한 앞서 봤던 이너셔나 실루엣 점수를 통해 클러스터 개수 k를 찾고 설정해줘야합니다. 샘플의 분포에 있어서도 한계점이 있습니다. 클러스터의 크기가 다르거나 밀집도가 다르고 원형이 아닐 경우에는 알고리즘이 잘 작동하지 않을 수 있습니다.
위 그림과 같이 샘플들이 크기가 다르고 밀집도가 다르고 원형의 분포를 가지지 못할 때 k-평균 알고리즘이 잘 작동하지 않는 것을 볼 수 있습니다. 이렇듯 타원형 분포를 가지고 있는 샘플들은 추후 설명할 가우시안 혼합 모델이 잘 작동합니다.
k-평균 알고리즘을 샘플에 적용하기 전에 입력 특성의 스케일을 맞추면 위와 같은 문제점을 조금은 해결할 수 있습니다. 물론 보장할 수는 없지만 일반적으로 더 좋아집니다.
2. DBSCAN (Density-based spatial clustering of applications with noise)
- 데이터가 놓여있는 공간 상에서 데이터가 많이 모여있는, 밀도가 높은 지역을 군집화하고 비교적 밀도가 낮은 지역을 기준을 경계로 군집을 구분합니다.
- 군집과 이상치(노이즈)를 밀도 기반으로 구분합니다.
- 모든 클러스터가 충분히 밀집되어 있고 밀집되지 않은 지역과 잘 구분될 때 좋은 성능을 냅니다.
2.1 DBSCAN 동작 원리
- ε-이웃 : 각 샘플에서 작은 거리인 ε(입실론) 내의 샘플입니다.
- 핵심 샘플 : ε-이웃 내에 적어도 min_samples개 샘플이 있는 샘플입니다.
- 핵심 샘플의 이웃에 있는 모든 샘플은 동일한 클러스터에 속합니다. (핵심 샘플 포함)
-
핵심 샘플이 아니고 이웃도 아닌 샘플은 이상치로 판단합니다.
예를 들어보겠습니다.
위의 그림에서 파란 원은 각 샘플이 공간에 위치한 모습을 나타냅니다.
빨간 원은 핵심 샘플으로 해당 샘플 주위의 작은거리 ($\epsilon $)안에 min_samples(위의 경우는 3) 이상의 샘플이 위치하게됩니다.
그리고 노란 원은 ($\epsilon $)거리 안의 $\epsilon $-이웃 샘플에 해당합니다. 이 $\epsilon $-이웃 샘플 역시 핵심 샘플이 될 수 있습니다.
좌측의 빨간 원 속 파란 샘플은 핵심 샘플도 아니고 $\epsilon $-이웃 샘플도 아니므로 이상치입니다.
DBSCAN의 결과는 다음과 같습니다.
DBSCAN은 클러스터의 개수와 모양에 상관없이 군집을 감지 가능합니다.
또한 하이퍼 파리미터또한 2개 뿐입니다. (min_samples, eps)
하지만, 클러스터간의 밀집도가 크게 다르면 성능이 떨어집니다.
2.2 DBSCAN을 활용하여 새로운 샘플의 클러스터 예측
- DBSCAN 클래스는 predict() 매서드를 제공하지 않습니다.
- 즉, 새로운 샘플에 대해 클러스터를 예측할 수 없습니다.
- 따라서 사용자가 필요한 예측기를 선택하여 사용하여야 합니다.
다음은 KNeighbosClassifier을 이용하여 새로운 샘플의 클러스터를 예측하는 예제입니다.
이때, 각 변수의 값은 다음과 같습니다. (DBSCAN모델은 이미 학습되어 있다고 가정합니다.)
즉, 핵심 샘플에 해당하는 샘플들의 값을 독립변수로, 핵심 샘플의 DBSCAN의 결과인 라벨을 종속변수로 하여 KNN을 학습 시킨후 이를 활용하여 새로운 샘플의 라벨을 예측하는 방식입니다.
DBSCAN을 이용하여 새로운 샘플을 예측하지 않는 이유는 단순히 다른 분류 알고리즘이 이런 작업을 더 잘 수행할 수 있기 때문입니다.
다음으로는 가우시안 혼합 모델에 대해 알아보기 전, 가우시안 분포를 알아보겠습니다.
3. 가우시안 분포
- 가우시안 분포는 보통 정규분포(standard distribution)으로 알려져 있습니다.
- 가우시안 분포는 연속확률분포의 하나로 일상적인 자료에서 흔히 볼 수 있는 분포입니다.
가우시안 분포는 다음과 같이 표현할 수 있습니다.
여기서 $\mu$ 는 평균이고 $\sigma ^2$ 는 분산입니다.
즉, 평균과 분산 값에 따라 가우시안 분포가 다른 형태를 띄게 됩니다.
4. 가우시안 혼합 모델 (Gaussian mixture model) 이란?
가우시안 혼합 모델(GMM)은 샘플이 파라미터가 알려지지 않은 여러 개의 혼합된 가우시안 분포에서 생성되었다고 가정하는 확률 모델입니다. 즉, label이 주어져 있지 않은 데이터에 대해 데이터셋은 가우시안 분포를 이룰 것이라 가정하고 클러스터링을 행해주는 과정을 Gaussian Mixture Modeling 이라고 합니다.
4.1 가우시안 혼합 모델(GMM)의 그래프 모형
우선 Scikit-learn의 GaussianMixture에 대하여 알아봅시다.
여기에서는 가우시안 분포의 개수 k를 알아야 합니다. 데이터셋 $\textbf{X}$가 다음 확률 과정을 통해 생성되었다고 가정합시다. (가우시안 혼합 모델은 생성 모델입니다.)
- 샘플마다 k개의 클러스터에서 랜덤하게 한 클러스터가 선택됩니다. j번째 클러스터를 선택할 확률은 클러스터의 가중치 $\phi^{(j)}$로 정의됩니다. $i$번째 샘플을 위해 선택한 클러스터 인덱스는 $z^{(i)}$로 표시합니다.
- $i$번째 샘플이 j클러스터에 할당되었다면 이 샘플의 위치 $\textbf{x}^{(i)}$는 평균이 $\mu^{(j)}$ 이고 공분산 행렬이${\sum}^{(j)}$인 가우시안 분포에서 랜덤하게 샘플링 됩니다. $\textbf{x}^{(i)} \sim N(\mu^{(j)},{\sum}^{(j)})$
이 생성 과정은 아래의 그래프 모형으로 나타낼 수 있습니다.
먼저, GMM의 그래프 모형을 살펴보겠습니다.
위 모형에서 각각의 도형은 다음을 의미합니다.
- 원 : 확률 변수
- 사각형 : 고정값 (모델의 파라미터)
- 큰 사각형 : 사각형 안의 내용이 여러 번 반복된다는 것을 나타냅니다. (플레이트)
- 플레이트 우측 아래의 숫자 : 플레이트 안의 내용의 반복 횟수
- 실선 화살표 : 조건부 의존성을 나타냅니다. 예를 들어, 각 확률 변수 $z^{(i)}$의 확률 분포는 가중치 벡터 $\Phi$에 의존합니다. 그리고 화살표가 플레이트 경계를 가로지르면 해당 플레이트의 모든 반복에 적용한다는 의미입니다.
- 구불구불한 화살표 : 스위치를 나타냅니다. 위의 모형에서는 $z^{(i)}$의 값에 따라 샘플 $\textbf{x}^{(i)}$가 다른 가우시안 분포에서 샘플링될 것입니다. 즉, 선택된 클러스터 인덱스에 따라 가우시안 분포의 파라미터인 평균과 분산이 달라지게 됩니다. ($z^{(i)}=j$ 라면 $\textbf{x}^{(i)} \sim N(\mu^{(j)},{\sum}^{(j)})$이 됩니다.)
- 색이 채워진 원 : 알려진 값이라는 의미입니다.
위 모델은 데이터 셋 $\textbf{X}$가 주어지면 가중치 $\Phi$와 전체 분포의 파라미터 $\mu^{(1)}$에서 $\mu^{(k)}$
까지와 ${\sum}^{(1)}$ 에서 ${\sum}^{(k)}$ 까지를 추정합니다.
즉, 사전에 클러스터의 개수 k를 지정한 만큼 가우시안 분포 k개를 추정하게 됩니다.
4.2 기댓값-최대화 (expectation-maximization) 알고리즘
위의 모형에서 저희가 찾아야 할 파라미터값이 각 클러스터의 평균$\mu$, 각 클러스터의 공분산 행렬
${\sum}$ , 그리고 가중치 파라미터 $\Phi$ 임을 알 수 있었습니다.
그럼 이 파라미터들을 어떻게 찾을 수 있을까요?
바로 기댓값-최대화(EM) 알고리즘을 이용하여 찾을 수 있습니다. 이 알고리즘은 k-means와 비슷하게 기대값 단계(expectation step)와 최대화 단계(maximization)를 반복하며 모델이 수렴할 때 까지 이 두 단계를 반복하게 됩니다. 아래에서 어떤 순서로 최적의 클러스터를 찾는지 알아보겠습니다. 순서는 다음과 같습니다.
- 초기화 : 클러스터 파라미터를 랜덤하게 초기화
- 기대값 단계 : 샘플을 각 클러스터에 할당
- 최대화 단계 : 클러스터를 업데이트
- 모델이 수렴할 때까지 2,3번 반복
4.2.1 초기화
우선, 이해하기 쉽게 1차원의 샘플을 2개의 클러스터로 분류한다고 가정하겠습니다.
그리고 각 클러스터 파라미터 또한 랜덤하게 설정합니다.
위의 그림에서 클러스터 파라미터는 $\Theta =\left\{ \pi_0,\pi_1,\mu_0,\mu_1,{\sum}_0,{\sum}_1\right\}$ 이를 표기를 간단하게 하기위해 $\Theta$로 표현하겠습니다.
이제 랜덤하게 설정된 두 클러스터를 업데이트 해보겠습니다.
4.2.2 기대값 단계
기대값 단계에서는 파라미터 $Theta$가 정해지고 나서 책임(responsibility)를 구하는 과정입니다.
여기서 책임이란 무엇일까요?
책임(responsibility)이란 각 샘플이 각 클러스터에 속할 추정 확률입니다. 예를 들어, 위의 그림에서 100번째 샘플이 클러스터 0에 속할 확률은 $\frac{0.02}{0.02+0.08}=0.2$ 이고 클러스트 1에 속할 확률은 $\frac{0.08}{0.02+0.08}=0.8$ 입니다.
이 때, 저희는 각 클러스터에 할당될 확률을 구하기 때문에 EM알고리즘은 소프트 클러스터링 (soft clustering)임을 알 수 있습니다.
책임의 표기는 위와 같이 쓸 수 있습니다. 여기서 $i$는 샘플의 번호이고 $k$는 클러스터의 번호입니다.
위의 예에서는 $r_{100\: 0} = 0.2$,$r_{100\: 1} = 0.8 $ 와 같이 표기할 수 있겠네요.
그렇다면 왜 저희는 여기서 책임을 계산하였을까요?
바로 클러스터 파라미터를 업데이트 하기 위해서 입니다.
그럼 이제 여기서 구한 책임(responsibility)으로 클러스터 파라미터를 업데이트 해보겠습니다.
4.2.3 최대화 단계
이제 기대값 단계에서 구한 책임을 활용하여 클러스터 파라미터를 업데이트 할 차례입니다.
먼저, 클러스터 가중치 $\pi$를 업데이트 하는 식을 살펴볼게요.
$$\pi_k = \frac{1}{N}\sum_{}^{i}r_{ik}=\frac{r_k}{N}$$
위의 식을 간단하게 해석하면 각 클러스터마다 모든 책임의 평균으로 클러스터 가중치를 업데이트 합니다.
예를 들어, 위의 그림에서 모든 샘플에 대한 클러스터 0의 책임의 평균이 0.7이고 클러스터 1의 책임의 평균이 0.3이라고 하면 $\pi_0 = 0.7, \pi_1 = 0.3$ 으로 업데이트 되게 됩니다. 따라서 클러스터의 분포는 다음과 같이 변하게 됩니다.
이렇게 클러스터 가중치 $\pi$를 업데이트 해보았습니다.
이제 나머지 파라미터인 $\mu$ 와 ${\sum}$ 을 업데이트 해 보겠습니다.
이는 MLE(Maximum Likelihood Estimation), 최대우도법으로 구할 수 있습니다.
최대우도법이란, 쉽게 말해서 샘플들을 이용하여 파라미터를 추정하는 방법입니다.
likelihood 를 구하는 식을 정의하고 이를 편미분하여 그 값이 0이되도록 하는 파라미터를 찾는 과정을 통해 likelihood 함수를 최대화 시켜줄 수 있는 파라미터를 구할 수 있습니다.
우도를 구하는 식은 위와 같습니다. 이를 계산을 더 편리하게 하기 위해 상수항은 버리고 log-likelihood로 변환하겠습니다.
단순히 위의 식을 편미분하여 파라미터 $Theta$의 기울기가 0이 되는 지점을 찾는다면 무엇이 문제일까요?
바로 평균 $\mu$가 샘플이 많이 모여있는 쪽으로 치우치게 됩니다.
예를들어, 위 그림의 우측 가우시안 분포의 평균이 비교적 샘플이 많이 모여있는 좌측으로 치우치게 됩니다.
이는 저희가 원하는 결과가 아닙니다.
따라서 아까 기대값 단계에서 구한 책임을 이용합니다.
이 식을 이용하면 책임이 낮은 클러스터는 우도를 더 작게, 책임이 높은 클러스터에는 우도를 더 크게 만들 수 있습니다.
저희는 위 식을 편미분하여 최종적으로 $\mu$ 와 ${\sum}$을 업데이트 하는 식을 얻을 수 있습니다.
식은 다음과 같습니다.(미분 과정은 생략하겠습니다 ㅎ...)
이러한 과정들을 통하여 모든 클러스터 파라미터 $\Theta$를 업데이트 해보았습니다.
최대화 단계는 기대값 단계에서 구한 책임을 이용하여 클러스터 파라미터 $\Theta$를 업데이트 하는 과정이었습니다.
이후에는 업데이트된 $\Theta$를 적용하여 다시 책임을 구하고 2,3번 과정을 모델이 수렴할 때까지 반복합니다.
4.2.4 EM 알고리즘 정리
EM알고리즘은 K-means 알고리즘이랑 비슷한 부분이 있습니다.
군집 입장에서 보면 EM을 클러스터 중심 ($\mu^{(1)}$에서 $\mu^{(k)}$까지) 뿐만 아니라 크기, 모양, 방향 (${\sum}^{(1)}$ 에서 ${\sum}^{(k)}$까지)과 클러스터의 상대적 가중치 ($\phi^{(1)}$에서 $\phi^{(k)}$까지) 를 찾는 k-means의 일반화로 생각할 수 있습니다.
지금까지 EM알고리즘을 통해 어떻게 Gaussian mixture model이 k개의 최적의 가우시안 분포를 찾아내는지 알아보았습니다.
4.3 이상치 탐지
가우시안 혼합 모델은 이상치 탐지에도 사용할 수 있습니다.
이상치 탐지는 보통과 많이 다른 샘플을 감지하는 작업입니다.
가우시안 혼합 모델을 이상치 탐지에 사용하는 방법은 간단합니다.
특정 밀도 임계값을 정해서 샘플이 위치한 밀도가 임곗값보다 낮으면 그 샘플을 이상치로 판단합니다.
위의 그림에서 별에 해당하는 샘플이 이상치입니다.
4.4 클러스터 개수 선택하기
k-means에서는 이너셔나 실루엣 점수를 사용해 적절한 클러스터 개수를 선택합니다.
하지만 가우시안 혼합에서는 클러스터가 타원형이거나 크기가 다를때 위의 두 지표가 안정적이지 않기 때문에 다른 지표를 사용합니다.
바로 BIC(Bayesian information criterion)나 AIC(Akaike information criterion)를 사용합니다.
$$BIC = log(m)p-2log(\hat{L})$$
$$AIC = 2p-2log(\hat{L})$$
- $m$은 샘플의 개수
- $p$는 모델이 학습할 파라미터 개수
- $\hat{L}$은 모델의 우도 함수(likelihood function)의 최대값
BIC와 AIC는 모두 학습할 파라미터가 많은 모델에게 벌칙을 가하고 데이터에 잘 학습하는 모델에게 보상을 더합니다.
하지만 대규모 데이터셋에서는 잘 적용되지 않을 수 있습니다.
저희는 BIC와 AIC가 최소가 되는 지점의 k를 클러스터 개수로 선택할 수 있습니다.
5. 베이즈 가우시안 혼합 모델 (BayesianGaussianMixture model)
베이즈 가우시안 혼합 모델에서는 최적의 클러스터 개수 k를 수동으로 찾지 않고 불필요한 클러스터의 가중치를 0으로 (또는 0에 가깝게) 만듭니다.
위의 결과에서 사용자가 지정한 클러스터의 개수(n_components)는 10이지만 모델이 판단하였을때에는 3개의 클러스터 가중치를 제외한 나머지 클러스터 가중치는 필요없다고 판단한 것을 볼 수 있습니다.
5.1 베이즈 가우시안 혼합 모델 모형
이 모델에서 클러스터 파라미터는 고정된 모델 파라미터가 아니라 잠재 확률변수로 취급합니다.
위의 모델에서 가중치는 베타 분포를 따르고 이 베타분포를 농도 $\alpha$에 의해서 제어합니다.
베타 분포는 두 매개변수 $\alpha$와 $\beta$에 따라 [0,1] 구간에서 정의되는 연속확률분포입니다.
자세한 내용은 아래 블로그를 참고해주세요!
https://losskatsu.github.io/statistics/betadist/#
[기초통계] 베타분포 의미 및 개념 정리
베타분포 의미 및 개념 정리
losskatsu.github.io
클러스터 인덱스인 $z^{(i)}$ 는 SBP($\Theta$)를 따릅니다.
SBP(stick-breaking process)를 설명해보자면 만약 $\Theta$=[0.3, 0.6, 0.5, ...] 이라면 샘플의 30%가 0에 할당되고 남은 샘플 60%가 클러스터 1에 할당됩니다. 그다음 남은 샘플의 50%가 클러스터 2에 할당되는 식입니다.
이는 새로운 샘플이 작은 클러스터보다 큰 클러스터에 합류할 가능성이 높은 데이터셋에 잘 맞는 모델입니다.
클러스터 인덱스는 결국 파라미터 $\alpha$로 표시되는 농도에 의해 제어됩니다. ($\Theta$가 농도를 독립변수로 가지기 때문)농도가 크면 $\Theta$값이 0에 가깝게 되고 SBP는 많은 클러스터를 만듭니다.
농도가 작으면 $\Theta$값이 1에 가깝게 되고 몇 개의 클러스터만 만들어 집니다.
마지막으로 위샤트 분포를 사용해 공분산 행렬을 샘플링합니다. 파라미터 $d$와 $v$가 클러스터 분포 모양을 제어합니다.
베이즈 가우시안 혼합모델에서는 클러스터 개수에 대한 사전 믿음(prior belief)을 지정할 수 있습니다.
이는 weight_concentration_prior이라는 파라미터로 조정 가능합니다.
weight_concentration_prior 값이 작을수록 클러스터 개수가 적을 것이라는 믿음을 가집니다.
5.2 베이즈 정리
베이즈 정리는 데이터 X를 관측하고 난 후 잠재 변수에 대한 확률 분포를 업데이트하는 방법을 설명합니다.
$$p(z|X) = \frac{p(X|z)p(z)}{p(X)}$$
베이즈 정리를 통해 사후 확률 분포를 계산하려면 분모인 $p(X)$ 계산해야합니다.
하지만 이는 모든 클러스터 파라미터와 클러스터 할당의 조합을 고려해야 되기 때문에 힘듭니다.
따라서 변분추론을 통해 $p(z|X)$ 근삿값을 찾는 방식을 택합니다.
변분추론에 관한 내용은 아래 블로그에 잘 정리되어 있습니다.
https://greeksharifa.github.io/bayesian_statistics/2020/07/14/Variational-Inference/
Python, Machine & Deep Learning
Python, Machine Learning & Deep Learning
greeksharifa.github.io
Kovi는 SSDC(Samsung Software Developer Community)를 기반으로 만들어진 커뮤니티입니다. ML, DL, Computer Vision, Robotics에 관심 있고 열정 있는 사람들이 모여 함께 활동 중입니다.
Kovi Instagram : https://www.instagram.com/kovi.or.kr/
Kovi SSDC : https://software.devcommunities.net/community/communityDetail/98
이 포스팅은 Kovi 커뮤니티 스터디의 일환으로 작성되었습니다.
posted by. Panda99 & Daevi
'Hands-On Machine Learning' 카테고리의 다른 글
| [핸즈온머신러닝] CH8. 차원 축소 (Dimension Reduction) (0) | 2023.01.13 |
|---|---|
| [핸즈온머신러닝] CH7. 앙상블(Ensemble) 학습 (0) | 2022.12.09 |
| [핸즈온머신러닝] CH6. 결정 트리(Decision Tree) (1) | 2022.12.09 |
| [핸즈온머신러닝] CH5. 서포트 벡터 머신(Support Vector Machine; SVM) (0) | 2022.12.09 |
| [핸즈온머신러닝] CH4. 모델 훈련 (Training Model) (0) | 2022.11.27 |