[머신러닝] Unsupervised learning : Clustering

비지도학습 unsupervised learning의 가장 대표적인 방법이 clustering입니다.

label이 없기 때문에 prediction이나 classification이 불가능하고 객체 간의 유사성이 큰 것들끼리 묶어주는 방법입니다.

 

유사성 기준으로 1) 거리를 계산하거나 2) 상관계수를 구하는 방법이 있습니다.

 

 

1. 유사성 척도

1) 거리

두 n차원 데이터 $P=(p_{1},p_{2},...,p_{n})$과 $Q=(q_{1}, q_{2},..., q_{n})$이 있을 때 두 점 사이의 거리는 다양하게 구할 수 있습니다.

 

- 유클리디안 거리(euclidean distance)

가장 흔하게 쓰이는 거리 척도

 

$d(P,Q)=\sqrt{\sum_{i=1}^{n}(p_{i}-q_{i})^{2}}$

 

- 민코프스키 거리(minkowski distance) 

유클리디안 거리의 일반화된 형태

 

$d(P,Q)=\left( \sum_{i=1}^{n}|p_{i}-q_{i}|^{m}\right)^{\frac{1}{m}}$

 

 

그 외에도

- 맨하탄 거리(manhattan distance) - $L_{1} distance$라고도 부름

두 벡터 간의 절대적인 거리

 

$d(P,Q)=\sum_{i=1}^{n}|p_{i}-q_{i}|$

 

- Canberra distance

 

$d(P,Q)=\overset{n}{\underset{i=1}{\sum}} \frac{|p_{i}-q_{i}|}{|p_{i}|+|q_{i}|}$

 

 

2) 상관 계수

 

- 마할라노비스 거리(mahalanobis distance)

객체 간 상관계수가 있을 때 사용

 

$d(P,Q)=\sqrt{(P-Q)^{T}S^{-1}(P-Q)}\text{, where S is covariance matrix}$

 

군집 방법에는 계층적 군집과 비계층적 군집이 존재합니다.

 

2. Hierarchical clustering (계층적 군집분석)

 

군집 개수를 정해두지 않고 계층적으로 군집한 다음에 원하는 만큼만 군집하는 방법입니다.

이 계층적 군집 분석에는 병합 계층 군집(agglomerative hierarchical clustering)과 분할 계층 군집(divisive hierarchical clustering)이 있습니다.

 

분할 계층 군집은 전체 샘플 데이터를 하나의 클러스터로 보고 더 작은 클러스터로 나누는 방식이고

병합 계층 군집은 각각의 샘플 데이터를 하나의 클러스터로 보고 가까운 클러스터를 합치면서 나누는 방식입니다.

 

이 글에서는 병합 계층 군집을 중심으로 설명하겠습니다. (수업에서 병합 계층을 중심으로 배웠습니다 :D)

병합 계층에는 아래와 같은 방법들이 존재합니다.

 

1) 완전연결법 complete linkage method

군집을 만들 때 모든 객체 간의 거리 중에서 가장 먼 거리를 기준으로 군집을 형성

 

2) 단일연결법 average linkage method

군집을 만들 때 모든 객체 간의 거리 중에서 가장 가까운 거리를 기준으로 군집 형성

 

3) 중심연결법 centroid linkage method

두 군집의 중심 사이의 거리를 구해서 그 거리 중에 가까운 것을 기준으로 군집 형성

 

4) 평균연결법 average linkage method

 

5) ward's linkage : 두 군집 간의 유사성을 두 군집이 합쳐졌을 때의 오차제곱합(Sum of Squared Error)이 적어지는 쪽으로 군집하는 방법

 

위의 방법 중 하나를 택해서 군집을 해보면 아래와 같은 dendrogram(이진 트리 형태로 계층 군집을 시각화할 수 있는 그래프)을 그릴 수 있습니다.

 

Dendrogram 예시

 

 

3. Non-hierarchical clustering (비계층적 군집분석)

 

대부분 사람들이 소개하는 군집 방법은 non-hierarchical clustering입니다.

군집의 개수를 미리 정하고 군집을 수행하는 방식입니다.

 

방법을 크게 나누면

k-means

k-mediods

두 개의 알고리즘으로 나눌 수 있고,

 

두 개의 알고리즘에 대한 variation도 많이 등장했습니다.

 

k-means	k-means++, fuzzy k-means(Fuzzy C-means)
k-mediods	PAM(Partitioning Around Medoids), CLARA(Clustering LARge Application)

k-mediods 알고리즘에서 variation으로 PAM(Partitioning Around Medoids), CLARA(Clustering LARge Application)이 있습니다.

 

1) k-means 알고리즘

 

1. 샘플 데이터(객체)에서 랜덤하게 k개의 centroids를 초기 클러스터 중심으로 선택
2. 각 샘플을 가장 가까운 centroids에 할당
3. 할당된 샘플들의 중심을 구해서 centroids를 이동
1,2,3을 centroids가 바뀌지 않거나 사용자가 정한 반복 횟수 또는 허용 오차에 도달할 때까지 반복

 

장점 : 알고리즘이 단순하고, 계산 복잡성이 낮다

단점 : 임의의 초기값에 따라 다른 결과가 나올 수 있다. 데이터 분포가 특이하면 군집이 잘 이루어지지 않는다

 

 

2) k-meidods 알고리즘

 

중앙값을 각 군집의 대표 객체로 사용하고, 객체와 속하는 군집의 대표 객체(중앙값)의 거리 총합을 최소화하도록 군집을 형성합니다.

 

PAM 알고리즘 : 모든 객체에 대하여 대표 객체가 변했을 때 발생하는 거리 총합의 변화를 계산한다.

CLARA 알고리즘 : 적절한 수의 객체를 샘플링해서 PAM을 적용해 대표 객체를 선정한다. 샘플링을 여러 번 한 다음 가장 좋은 결화를 택한다.

 

3) 평가지표

 

clustering은 label이 없기 때문에 classification 문제나 regression 문제처럼 명료한 평가지표는 없습니다.

다만 얼마나 군집이 조밀하게 모여있는지에 대해 평가합니다.

 

그래서 이에 대한 평가지표로

 

• SSE(sum of squared error) 또는 distortion

sklearn의 k-means 알고리즘에서는 inertia_에 저장된 값으로,

군집의 centroid와 군집에 속한 sample이 얼마나 떨어져있는지를 나타내는 지표입니다.

 

$SSE = \sum_{i}^{n}\sum_{j=1}^{k} w^{(i,j)} \left \| x^{(i)}-\mu^{(j)} \right \|_{2}^{2}$

$\text{where }\mu\text{ is centroid of cluster j and x is sample data}$

 

w는 x가 j라는 cluster에 속해있으면 1이고, 없으면 0입니다.

 

이 distortion을 가지고 number of clusters에 대해서 그래프를 그렸을 때 급격하게 distortion이 줄어들며 수렴하는 지점에서 최적의 cluster 개수를 찾을 수 있습니다.

 

 

• Silhouette analysis

silhouette coefficient(실루엣 계수)를 구해서 이 계수가 1에 가까울수록 더 적절한 cluster라고 판단할 수 있습니다.

 

$\text{Silhouette coefficient : }s_{i}=\frac{b_{i}-a_{i}}{max(a_{i},b_{i})}$

$a_{i}$은 i번째 데이터의 같은 군집 안에 있는 다른 데이터들 사이의 평균 거리

$b_{i}$은 i번째 데이터와 다른 군집과의 평균 거리 중 가장 작은 거리

 

한 군집 안에 속했을 때 그 군집 안의 데이터와 얼마나 가까운지(다른 군집의 데이터에 비해)를 나타내는 척도

군집 안의 거리가 작을 수록, 다른 군집과의 거리는 클수록 좋습니다.

 

coefficient를 분석하기 위해 parameter를 극단적인 값으로 보내겠습니다.

$a_{i}\rightarrow 0$이면 $s_{i}\rightarrow 1$이 되고, 만약 $b_{i}\rightarrow 0$이면 $s_{i}\rightarrow -1$입니다.또한 $a_{i}\approx b_{i}$이면 coefficient가 0에 가까워지므로, 항상 1에 가까울수록 좋은 것임을 알 수 있습니다.

$b_{i}<a_{i}$이면 coefficient는 음수 값을 가집니다.

 

또한 coefficient는 -1에서 1 사이의 값을 가질 수 있고, 전체 실루엣 평균값은 0에서 1사이입니다. (알고리즘이 잘못되지 않는 한, 보통은 데이터가 속한 군집과의 거리가 다른 군집보다 가까울 것이기 때문입니다.)

 

 

 

4) DBSCAN (Density Based Spatial Clustering of Application with Noise)

 

density(밀도) 기반 군집으로, 앞서 본 비계층적 군집 분석의 k-means와 k-mediods처럼 비계층적 군집으로 볼 수는 있지만 군집 개수를 달리 정해주지 않는 대신, 최소 반경과 군집이 최소한으로 가져야하는 데이터 개수가 하이퍼 파라미터가 됩니다.

 

장점 : 군집 수를 지정할 필요가 없다. k-means는 원형 클러스터를 전제로 하지만, DBSCAN은 원형이 아닌 불특정한 모양의 군집도 가능하다. outlier에 robust하다.

단점 : 최소 반경 및 최소 데이터 개수를 미리 정해줘야 하는데 이 값에 따라 성능이 많이 바뀐다. 데이터가 sparse하면 군집화가 잘 이루어지지 않는다.

 

---

graph-based clustering 방법 역시 있는데 그 중에서 spectral clustering이 대표적입니다.

나중에 가능하면 따로 공부해서 작성하도록 하겠습니다.

(실루엣 계수도 보충 필요)