클러스터링

 

 

• 클러스터링이란? 

 

군집화(Clustering, 클러스터링) 은 어떤 데이터들이 주어졌을 때, 특성이 비슷한 데이터끼리 묶어 주는 머신 러닝 기법이다.

 

 

 

 

 

• 거리유형

 

 

1. 유클리드 거리 (Euclidean distance)

 

두 점사이의 거리를 계산할 때 사용하는 방법이다.

 

 

 

 

2. 맨해튼 거리 (Manhattan distance)

 

이 거리는 단위 사각형이있는 도시 한 지점에서 다른 지점으로 이동하는 것과 같다. 

수평 방향과 수직 방향으로 이동한 값을 합한 것이다.

 

 

 

 

 

 

 

3. 체비셰프 거리 (Chebyshev distance)

 

 

이 거리는 모든 축을 따르는 최대 거리와 같다.

이는 체스(chess) 거리 라고도하는 데, 왕이 처음 지점에서 최종 지점으로 이동하는데 최소한의 이동량을 제공하기 때문이다.

 

 

 

 

 

 

 

 

 

 

 

 

• 공통 중심점 찾기 : K-평균

 

 

K-평균 (K-means clustering algorithm)은 주어진 데이터를 k개의 군집(클러스터)로 묶는 알고리즘으로, 각 클러스터와 거리 차이의 분산을 최소화하는 방식으로 동작한다. 

 

 

이 알고리즘은 자율 학습의 일종으로, 레이블이 달려 있지 않은 입력 데이터에 레이블을 달아주는 역할을 수행한다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

●  장단점

 

 

1. 매우 잘 스케일된다. (대부분의 계산은 병렬로 실행 될 수 있다.)

2. 매우 광범위한 응용 분야에서 사용된다.

3. 단순한 방법이지만 약간의 비용이 필요하다. (완벽한 방법은 없다)

4. 사전 지식이 필요하다. (가능한 클러스터 수를 알아야 한다.)

5. 이상치 또한 다른 샘플과 같은 가중치를 가지므로 중심점 값을 왜곡할 수 있다.

6. 형태가 볼록하고 등방성인 것으로 가정하기 때문에 덩어리진 형태를 갖지 않는 클러스터에서는 잘 동작하지 않는다.

 

 

 

 

 

 

 

 

•   최근접 이웃 (K - nearest neighbors)

 

K- NN은 분류 알고리즘이다.

K개의 최근접 이웃을 참조하여 자신의 클래스를 결정하게 된다.

 

 

 

 

 

 

●  WCSS

 

 

올바른 클러스터 개수를 알아내는 이상적인 방법은 WCSS를 계산하는 것이다. 

WCSS는 모든 클러스터에 있는 각 데이터가 중심까지의 거리를 제곱하여 합을 계산하는 것으로, 수식은 다음과 같다.

 

 

 

 

 

이때 합계를 최소화하는 것이 가장 이상적이다. 

 

주어진 데이터셋에 n개의 관측치가 있고 n개의 클러스터 개수(k=n)를 가정하면, 데이터들이 중심 값이 되어 거리가 0이 되므로 이상적으로는 완벽한 클러스터를 형성하여 WCSS는 0이 됩니다. 

 

 

그러나 이것은 관측치만큼 많은 클러스터를 가지고 있기 때문에 의미 없는 결과다. 

 

 

 

이러한 문제를 해결하기 위해 ‘엘보 그래프(elbow graph)’를 많이 사용한다.

엘보 그래프는 K 값 범위에 대해 K-평균 알고리즘을 무작위로 초기화하고, 각 K 값을 WCSS에 플로팅합니다.

 

 

 

최적의 엘보를 찾는 방법은 다음과 같다.

 

1. 곡선의 처음과 마지막 점을 직선으로 연결

2. 각 점에서 직선까지의 수직 거리를 계산

3. 가장 긴 거리를 엘보(elbow)로 선정

 

 

 

 

 

 

 

 

 

 

• 가우시안 혼합 모델(Gaussian Mixture Model)

 

가우시안 혼합 모델 이름 그대로 가우시안 분포(gaussian distribution)가 여러 개 혼합된 클러스터링 알고리즘이다. 

 

현실에 있는 복잡한 형태의 확률 분포를 다음 그림과 같이 가우시안 분포 K개를 혼합하여 표현하자는 것이 가우시안 혼합 분포(gaussian mixture distribution)이다. 

 

 

 

이때 K는 하이퍼파라미터다.

 

 

 

 

가우시안 혼합 모델을 이용한 분류는 주어진 데이터 Xn 에 대해 이 데이터가 어떤 가우시안 분포에 속하는지 찾는 것으로 다음 수식을 사용한다.

 

 

 

 

znk(znk∈{0,1})은 xn이 주어졌을 때 가우시안 혼합 모델의 K번째 가우시안 분포가 선택되면 1을 갖고, 아니면 0 값을 갖는다. 

즉, znk가 1이라는 의미는 xn이 K번째 가우시안 분포에 속한다는 것이다. 

 

 

다시 말해 가우시안 혼합 모델을 이용한 분류는 xn이 주어졌을 때, K개의 γ(znk)를 계산하여 가장 높은 값의 가우시안 분포를 선택하는 것이라고 할 수 있다.

 

 

 

학습으로 가우시안 혼합 모델의 모든 파라미터 π, μ, Σ의 값이 결정되었다면, 베이즈 정리(Bayes’ theorem)를 이용하여 γ(znk)를 다음과 같이 정리할 수 있다.

 

 

 

 

 

πk와 p(znk=1)은 모두 K번째 가우시안 분포에 선택될 확률을 나타내기 때문에 수식에서 p(znj=1)이 πj로 치환된다.

πk는 zk=1일 때의 사전 확률 값이며, γ(znk)는 관찰 데이터 x가 주어졌을 때의 사후 확률 값이다. 

 

또한, γ(zk)를 성분 K에 대한 책임 값(responsibility)이라고 한다.

 

 

 

 

 

 

 

• 자기 조직화 지도(Self-Organizing Map)

 

자기 조직화 지도는 신경 생리학적 시스템을 모델링한 것으로 입력 패턴에 대해 정확한 정답을 주지 않고 스스록 학습을 하여 클러스터링하는 알고리즘이다.

 

 

 

 

●  SOM 구조

 

 

자기 조직화 지도를 설명하려고 네트워크를 층 두 개로 구성한다. 

 

 

입력층(input layer)과 2차원 격자(grid)로 된 경쟁층(competitive layer)인데, 입력층과 경쟁층은 서로 연결되어 있다. 

이때 가중치는 연결 강도(weight)를 나타내며, 0과 1 사이의 정규화(normalize)된 값을 사용한다.

 

 

 

 

 

 

 

 

 

 

●  과정

 

 

자기 조직화 지도의 학습은 네 단계로 진행된다.

 

 

1. 초기화(initialization): 모든 연결 가중치는 작은 임의의 값으로 초기화한다.

 

2. 경쟁(competition): 자기 조직화 지도는 경쟁 학습(competive learning)을 이용하여 입력층과 경쟁층을 연결한다. 

 

자기 조직화 지도는 연결 강도 벡터가 입력 벡터와 얼마나 가까운지 계산하여 가장 가까운 뉴런이 승리하는 ‘승자 독점(winner take all)’ 방식을 사용한다. 

 

이때 사용되는 수식은 다음과 같다.

 

 

 

 

Dij 값이 작을수록 연결 강도 벡터와 입력 벡터가 가까운 노드이며, 연결 강도는 다음 식을 사용하여 새로운 값으로 업데이트한다.

 

 

 

 

 

연결 강도 벡터와 입력 벡터가 가장 가까운 뉴런으로 계산되면 그 뉴런의 이웃 뉴런들도 학습을 하게 되는데, 이때 모든 뉴런이 아닌 제한된 이웃 뉴런들만 학습한다.

 

 

 

 

 

 

3. 협력(cooperation): 승자 뉴런은 네트워크 토폴로지에서 가장 좋은 공간 위치를 차지하게 되며, 승자와 함께 학습할 이웃 크기를 정의한다.

 

 

 

 

 

 

 

4. 적응(adaptation): 승리한 뉴런의 가중치와 이웃 뉴런을 업데이트한다.

 

그리고 최종적으로 원하는 횟수만큼 2~3의 과정을 반복한다.