군집화(Clustering)

Unsupervised Learing

- supervised learining은 training set의 label이 주어지는 반면, unsupervised learining은 주어진 label 없이 training 한다.

ex) 비슷한 특성을 가진 data 끼리 묶는다 (clustering)

ex) supervised learining : training set {(x1, y1), (x2, y2), .... ,(xm, ym)}

     unsupervised learining : training set {(x1, x2, ... , xm)}

- 모델을 신뢰 할 수 있는지 평가하기 어렵다. 즉, 성능을 평가하기 어렵다.

 

클러스터링(Clustering) - K-means clustering / Hierarchical clustering

- 클러스터 : 데이터 포인트 (data objects)의 모임으로 같은 그룹(or cluster) 안에서는 서로 비슷하고, 서로 다른 그룹 사이에는 안 비슷한 모양

- 클러스터 분석 또는 클러스터링 (clustering, data segmentation, ...) : 데이터 포인트들을 받아서 그룹들(cluster)로 나누는 것

    data set에서 하위그룹(subgroup), 즉 클러스터(cluster)를 찾는 것이다.

- 비지도 학습이다. 즉, 분류가 아니다. 

- 데이터가 있는데 정답이 없다? 데이터에 대해서 무엇을 해야 할 지 모를때 => 클러스터링을 사용한다!

- 각 클러스터 안의 데이터는 서로 비슷하고, 다른 클러스터 간의 데이터는 서로 다를수록 좋다.

- 적용분야: 다른 데이터 마이닝 작업의 중간 과정으로...

* 데이터의 요약

* outlier detection

* 데이터압축(이미지압축)

* 비슷한 유저나 비슷한 제품을 찾기

ex) 협업필터링(Collaborative filtering), 추천시스템, 고객군집화

* data distribution에 인사이트를 얻기 위해

* 이미지, 비디오, 오디오, 유전자, 단백질 시퀀스 분석 등

* 비지니스(마케팅에서 market segmentation을 하고 싶을때, 쇼핑몰에서 구매자의 유형별로 나눠서 추천상품을 보여주고 싶을 때)

- 가장 유명한 클러스터링 기법

1) K-means clustering : 미리 정해진 숫자의 클러스터로 클러스터링을 한다.

2) Hierarchical clustering

* 몇개의 클러스터를 원하는지 모를 때

* 데이터가 dendrogram이라는 트리 모양으로 나타내진다.

* 그 뒤 몇 개의 클러스터를 원하는지 선택한다.

 

1) K-means Clustering

- Algorithm

1. 먼저 원하는 클러스터의 개수 K를 고른다.

2. 각각의 데이터 포인트마다 무작위로 1부터 K까지의 클러스터 번호를 지정한다. (초기화)

3. 클러스터 할당(assignment)이 바뀌지 않을 때까지 다음을 반복한다.

3-1. 각각의 클러스터에 속한 데이터 포인트들을 평균내어 클러스터의 중심(centroid)을 계산한다.

3-2. 각각의 데이터 포인트마다 가장 가까운 중심(centroid)를 가진 클러스터에 할당한다.

 

 

- 초기화 방법

1. 무작위로 공간 상에서 중심(centroid)를 지정하기

2. 무작위로 K개의 데이터 포인트를 골라서 각각의 클러스터 중심으로 지정하기

 

- 특징

1. 모든 데이터 포인트는 K개 클러스터 중에 하나에 속한다.

2. 어떤 데이터 포인트도 두 개 이상의 클러스터에 속할 수 없다.

3. 랜덤성이 있다. (할때마다 클러스터가 바뀔 수 있다. 주황색이었다가.. 초록색이었다가..)

4. 클러스터 사이의 순서는 없다.

5. 데이터가 숫자일 때만 사용 가능하다. 질량변수를 더미화 하면 잘 안나눠 질 수도 있다.

 

!! 수학적으로 보면

- K-means 클러스터링은 클러스터 내의 분산(within-cluster variation)이 작은 클러스터링이 좋은 클러스터링이라고 전제한다.

- W(C_k)는 k번째 클러스터의 클러스터 내 분산 (within-cluster variation)

- |C_k|는 k번째 클러스터에 속하는 데이터 포인트의 개수

- k번째 클러스터 내 분산은 k번째 클러스터에 속하는 모든 데이터 포인트 들의 쌍 사이의 거리를 더하고 데이터의 갯수로 나눈 것

 

- Goal : 클러스터 내 분산을 최소화하는 클러스터링을 찾고 싶다.

* 매우 어려운 문제이다. n개의 데이터포인트를 K개의 클러스터로 K^n개의 방법이 있기 때문이다.

* K-means 알고리즘은 local optimum을 찾아주는 근사 알고리즘

** local optimum: 더 줄어들 수 없을때 멈추고, 그 점이 local optimum

* K-means 알고리즘을 여러번해서 서로 다른 결과를 얻었다면?? 클러스터 내 분산이 작은 쪽을 선택한다!

** EM(Expectation Maximization) 알고리즘의 가장 간단한 형태이다.

   EM? 관측되지 않는 잠재변수에 의존하는 확률 모델에서 최대가능도(maximum likelihood)나 최대사후확률(maximum a posteriori)을 갖는

    매개변수를 찾는 반복적인 알고리즘이다.

* centroid를 통해 변수의 특징이 아닌 데이터의 특징을 알 수 있다.

 

 

 

 

2) 계층형 클러스터링(Hierarchical Clustering)

- 계층형 클러스터링(Hierarchical Clustering)은 클러스터 개수를 미리 지정하지 않아도 된다.

- 데이터를 트리 모양으로 나타태는 dendrogram을 만들어 낸다.

 

 

 

- 어디에서 자르느냐에 따라 cluster 갯수가 나뉜다. 맨 아래 뿌리들은 data points

 

!! Dendrogram 해석하기

- Dendrogram의 잎은 각각의 데이터 포인트 들이다.

- 트리 위로 올라가며 가장 가까운 데이터 포인트들끼리 합쳐져서 가지(branch)를 만든다.

- 더 위로 올라가면 가지(branch)들이 다른 입(leave)나 가지(branch)와 합쳐진다.

- 가까운 가지일수록 합쳐지는게 더 빨리 (tree 아래부분에서) 일어난다.

- 즉, 나중에 (tree 윗부분에서) 합쳐질 수록 두 가지가 다르다는 것을 뜻한다.

 

example)

- 위 그림에서 5와 7은 상당히 비슷하다 (맞음)

- 1과 6도 상당히 비슷하다. (맞음)

- 9와 2는 비슷하다 (틀림)

* dendrogram을 그릴 때 leave의 순서는 중요하지 않다. 즉, 가로축 방향으로 얼마나 가까운지는 의미가 없다.

  오직 두 가지(branch)가 합쳐지는 순간의 세로축의 값(distance)이 두 그룹이 얼마나 비슷한지 알려주는 척도

 

!! Dendrogram 기반으로 클러스터링 하기

- 수평선 방향으로 어디에서 자를지 결정하면 클러스터링이 결정된다.

- 즉, 어느 거리(distance) 이하의 가지까지만 합쳐질 수 있게 하면 클러스터링이 결정된다.

- 하나의 dendrogram에서 어떤 개수의 클러스터도 구할 수 있다.

- dendrogram을 눈으로 보고 그럴듯한 클러스터 개수를 찾아낼 수 있는 것이 장점이다.

- 왜 Hierachical 인가?

* 클러스터 개수를 줄여갈수록 항상 기존 클러스터가 합쳐져서 더 큰 클러스터를 형성한다.

* 클러스터 개수를 늘여갈수록 항상 기존 클러스터가 나눠져서 더 작은 클러스터가 된다.

 

 

!! 계층형 클러스터링 알고리즘 (Hierarchical clustering algorithm)

 

- Algorithm

* 데이터 포인트를 각각 데이터 1개를 가지고 있는 클러스터라고 본다.

1. 지금 있는 모든 클러스터들 간의 거리(dissimmilarities)를 계산한다.

2. 가장 거리가 작은 두 클러스터를 합친다. 이 때 두 클러스터 간의 거리가 dendrogram에서 세로축의 값이 된다.

3. 더이상 할 게 없을 때까지 다음을 반복한다.

 

- 두가지를 결정해야 한다.

1. 두 데이터 포인트의 비슷하지 않은 정도, 즉 거리(dissimilarity) 정의  

** 다른 거리를 쓸 수 있지만, 보통 유클리드 거리(Euclidean distance)가 쓰인다.

2. 두 데이터 포인트의 그룹(cluster)끼리의 거리(dissimilarity)를 정의

      ** 두 점 사이의 거리가 아닌, 두 클러스터 사이의 거리를 정의해야 한다.

      ** 거리(dissimilarity)의 일반화된 개념으로 linkage라고 부른다.

 

 

- Linkage의 종류 

Complete	최대 클러스터간 거리 (Maximal intercluster dissimilarity) A 클러스터에 속한 점들과 B 클러스터에 속한 점들 사이의 거리를 모두 계산해서, 가장 큰 거리가 두 클러스터 사이의 거리가 된다.
Single	최소 클러스터간 거리 (Minimal intercluster dissimilarity) 가장 작은 거리가 두 클러스터 사이의 거리가 된다. 이 방식으로 하면 보통 한 클러스터가 계속해서 커지는 결과가 나옴
Average	평균 클러스터간 거리 (Average intercluster dissimilarity) 두 클러스터에 속한 점들 사이 거리를 구해서 평균을 낸다.
Centroid	중심(centroid) 사이의 거리 중심은 그 클러스터에 속한 점들의 평균으로 결정된다.

 

이 중, Average나 complete가 가장 자주 쓰인다.

왜냐하면 1. 더 균형잡힌 클러스터가 만들어 진다.

 2. single은 보통 한 클러스터가 계속 커지는 문제가 있다.

 3. centroid는 전도(inversion)이라는 문제가 있다. 즉, dendrogram 상에서 두 클러스터가 각각의 클러스터보다 낮은 높이에서 합쳐지는 것이다.

 4. dendrogram을 그릴 때 문제가 생긴다.

 

 

- 거리(dissimilarity)의 정의 * 우리는 지금까지 유클리드 거리(Euclidean distance)만 써왔지만 다른 거리를 써야 할 때도 있다.

:: Correlation-based distance

1. 두 데이터 포인트 간의 m개의 feature들의 상관관계(sorrelation)가 높으면 비슷하다.

2. 상관관계는 보통 변수들 간에 계산 되는데, 여기서는 데이터 포인트 사이에 계산된다.

3. 이 거리는 데이터 포인트 값의 크기가 아니라 모양에 주목한다.

 

 

- A와 B가 동일하게 움직인다. or 절대적인 거리가 B와 C가 가깝다.

 

example)

 

- 거리(dissimilarity)의 결정은 클러스터링에 매우 큰 영향을 미친다.

1. 위 그림에서 유클리디안 거리를 쓰면 Observation 1과 3이 비슷하다.

2. Correlation-based distance를 쓰면, Observation이 1과 2가 비슷하다.

3. 예컨대, 온라인 쇼핑몰에서 구매자들을 클러스터링 할 때,

유클리디안 거리를 쓰면 소비수준이 비슷한 구매자끼리 묶인다.

      correlation-based distance를 쓰면 소비 패턴이 비슷한 구매자끼리 묶인다.

4. 스케일링(scaling)도 중요한 이슈다.

구매자들이 양말은 자주 사고 컴퓨터는 드물게 산다면, 양말이 클러스터링에 더 큰 영향을 미치게 된다.

스케일링 하면 각각의 변수들이 비슷한 영향을 갖게 할 수 있다.

- 첫번째 : 개수, 스케일링 없이 // 두번째 : 개수, 스케일링 이후 // 세번째 : 금액

 

 

3) K-means VS Hierarchical clustering

- 어떤 데이터셋에서는 큰 클러스터링이 작은 클러스터링을 포함하는 것이 부적절 할 수 있다.

- 예를 들면, 남여 비율이 50:50이며 미국인, 일본인, 프랑스인 세 인종으로 삼등분 되어 있는 사람들의 경우

  2개로 나눌때와 3개로 나눌 때 가장 적절한 클러스터링이 다를 것이다. 이런 경우에는 계측형 클러스터링이 부적절할 수 있음

- K-means는 보통 주어진 클러스터 개수에 대해 더 나은 결과를 낳는다고 알려져 있다.

 

 

4) 클러스터링 할 때 고려해야 할 사항

1. Feature scaling이 필요한가?

2. Hierarchical clustering일 경우

- 거리척도(dissimilarity measure)는 무엇을 써야 할까?

- 어떤 linkage를 써야 할까?

3. K-means일 경우

- 몇개의 클러스터가 가장 적절할까?

 

 

5) 마지막으로 조심해야 할 점

1. 클러스터링은 유용하고 어디가서 말하기도 좋지만 클러스터링이 얼마나 좋은지 평가할 방법이 별로 없다.

   우리가 단순히 노이즈(noise)를 클러스터링 한 건지 구분하기 쉽지 않기 때문에 클러스터링 결과를 절대적이라고 믿으면 안된다.

2. 여러 조건에서 다른 방식으로 클러스터링을 해보고 일괄적으로 패턴이 드러나는지 보는 것이 좋다.