Unsupervised Learning: Cluster Analysis

Unsupervised Learning: Cluster Analysis

데이터들의 분포에서 어떠한 그룹을 찾는 것이 cluster Analysis 이다.

대표적인 Unsupervised learning 방법이다. 정답을 모르는 상태에서 데이터들의 분포를 가지고 그룹을 결정 하기 때문이다.

위와 같이 그룹을 생성 했을때 Cluster안에서의 각각의 Data들 사이의 거리는 작아야한다. 즉 조밀한 배치를 이루고 있어야 한다.

Cluster들간의 거리는 최대한 먼 상태가 좋은 것이다.

기본적인 Clustering의 종류는 다음과 같이 나뉜다.

1) Partitional Clustering

각각의 그룹이 overlapping 되어지지 않고 정확히 하나의 그룹으로 구성되는 형태를 의미한다.

2) Hierarchical Clustering

계층적인 트리 형태로 구성되는 것을 말하며 그룹이 중첩되서 클러스터를 이루는 형태를 말한다.

Clustering Algorithms: K-means and its variants

---

가장 기본적인 Clustering 알고리즘이다.

초기 K를 정해서 각각의 초기 중심을 잡는다.

각각의 초기 중심을 기점으로 흩어져있는 데이터들중에서 가장 가까운 것을 그 중심을 기준으로한 클러스터에 편입 시킨다.

각각의 클러스터에대한 중심을 새로 계산 한다.

모든 중심이 변하지 않을때까지 반복한다.

하지만 어떤 경우에서는 끝나지 않을 수도 있다. 

따라서 몇 %이상 변하지 않을 때 까지나, SSE를 계산해서 변화량을 볼수도 있고

iteration 횟수를 고정해서 줄 수도 있다.

특성은 아래와 같다.

partitional clustering approach: 정확히 하나의 그룹에만 들어가지는 형태이다. 오버랩핑 되지 않는다.

Each cluster is associated with a centroid (or center point)

Each point is assigned to the cluster with the closest centroid

Number of clusters, K, must be specified 

The basic algorithm is very simple

- Complexity O(n*K*I*d)

n: number of points

K: number of clusters

I: number of iterations

d: number of attributes

- 어려운점

K값을 알기가 어렵다.

distance measure에 너무 민감하게 작용 한다.

초기 값의 선택이 매우 중요 한다.

결국 K-means cluster의 성능은 초기 center point의 선택으로 좌우 하는데,

성능 측정 지표가 있어야 계속 중심 포인트를 변경해 가면서 테스트를 수해할 수 있다.

제안된 성능 측정 방식은

Sum of Squared Error (SSE) 

방법이다.

아중 시크마의 의미는 아래와 같다

만약 K가 3이라고 가정하자.

즉 3개의 클러스터로 분할하고 싶어서 3이라고 준것이다.

각각의 클러스터에서의 중심 즉 평균과 각각의 데이터 포인트들간의 distance를 계산해서 제곱한다음 합을 구해주게 된다.

이렇게 해서 다 더하기 때문에 위와 같은 더블 시크마 공식이 나오게 된다.

이렇게해서 구한 SEE를 가지고 초기 seed를 변경해 가면서 

더 좋은 cluster를 찾을 수 있게 된다.

하지만 SSE measure의 한계점도 존재한다.

이것은 Intra개념만을 포함한 수치이다.

즉 클러스터들 간의 거리는 고려하지 않았다. inter 개념이 빠졌기 때문에

SSE가 최적의 k-means cluster를 찾는 가장 좋은 measure 라고 할 수 없다.

초기 중앙 점을 찾는 문제

• 여러번 수행한다.

• 계층적 클러스터를 구성해서 시각적으로 분석한 다음 적절히 K를 설정한다.

• 의도적으로 더 많은 K를 설정한 다음 이중에서 적절히 초기 K를 선택한다. 즉 가장 넓게 분할되는 K를 선택 하는 거이다.

• Bisecting K-means 알고리즘을 수행 한다. Not as susceptible to initialization issues

Bisecting K-means

하나의 클러스터에서 출발해서 반복하는 숫자만큼 클러스터를 분할하는 방법이다.

bisection에서 가장 작은 SSE를 가지는 2개의 클러스터를 list of clusters로 추가한다.

이 작업을 cluster 리스트가 K 클러스터를 포함할 때 까지 반복 하게 된다.

아래는 Bisecting K-means를 수행 했을 때의 그림이다.

기본적인 K-means algorithm의 문제는 바로 empty cluster의 생성 이다.

즉 클러스터를 계속 생성하는데, 가장 가까운 data가 하나도 없는 경우가 과정중에 자주 발생한다.

이때 어떻게 처리할 것인가?

해결방법

가장 멀리있는 포인트로 새로 시작

가장 높은 SSE로 새로 출발

동시에 몇개의 empty cluster가 발생하면 위가정을 몇번 더 반복 한다.

한번에 하나씩만 Center들을 업데이트 하는 방법. 시간이 오래걸리지만 empty는 생성되지 않는다.

Limitations of K-means

1) Differing Size 문제

크기가 서로 다른 클러스터를 만들어야 할 때 그렇게 하지 못하고,

큰것을 분할하는 성향이 강하다.

2) Differing Density

각각의 클러스터가 밀도가 서로 다르다면 문제가 또 발생 한다.

3) Non-Globular Shapes

구형태를 추구하는것이 K-means Algorithm의 특징이다. 

하지만 구형태가 아니라면 문제가 발생 한다. 

극복방법: 많이 쪼개서 합치는 방법이다. 아래와 같이

Hierarchical Clustering

---

중첩된 클러스터들로 구성된 계층적인 트리를 생성 한다.

시각적으로 볼 수 있는 특징이 있다.

생성하면 아래와 같은 모습을 볼 수 있다.

이러한 시각적인 모습을 통해서 적절히 클러스터를 생성 할 수 있다.

따라서 K를 설정할 필요가 없게 된다.

2가지 종류의 전략

Agglomerative:

Start with the points as individual clusters

At each step, merge the closest pair of clusters until only one cluster (or k clusters) left

단, 하나의 cluster가 남을 때 까지 이 방법을 반복 한다.

Divisive:

Start with one, all-inclusive cluster

At each step, split a cluster until each cluster contains a point (or there are k clusters)

Distance 또는 similarity matrix를 사용해서 clustering 과정을 수행 하게 된다.

클러스터를 합칠 때 어떻게 클러스터들간의 Similarity를 계산 할 수 있을까?

• MIN

• MAX

• Group Average

• Distance Between Centroids

• Other methods driven by an objective function

object function means that an measure such as SSE

각각의 방법을 그림으로 표현하면 아래와 같다.

예제

Min (single llinkage)으로 계산해 보자.

5개의 point data에 대해서 similarity를 모두 계산한다.

min이니 가장 가까운 것을 합치게 된다.

similarity 가 1이면 가장 높은것을 의미 한다.

1 v 2 : 3 (0.1 or 0.7)

1 v 2 : 4 (0.65 or 0.6)

1 v 2 : 5 (0.2 or 0.5)

	1 v 2		3	4	5
1 v 2	1		0.7	0.65	0.5
3	0.7		1	0.4	0.3
4	0.65		0.4	1	0.8
5	0.5		0.3	0.8	1

1 v 2 : 4 v 5 (0.65 or 0.5)

1,2,4,5의 경우 조합의 수는 총 4가지 이다. 왜 이것을 고려 하지 않을까? 이유는 둘중 가장 Similarity가 큰 것을 골랐기 때문에 나온 결과 2개중 하나만 고르게되면 이미 그것이 Similarity가 가장 큰것이 된다.

3 : 4 v 5 (0.4 or 0.3)

4 v 5 : 4 v 5 (0.8 or 1)

	1 v 2		3	4 v 5
1 v 2	1		0.7	0.65
3	0.7		1	0.4
4 v 5	0.65		0.4	1

	1 v 2 v 3			4 v 5
1 v 2 v 3	1			0.65
4 v 5	0.65			1

	1 v 2 v 3 v 4 v 5
1 v 2 v 3 v 4 v 5	1

최종적으로 Min 방식인 둘 사이의 유사도가 가장 큰것을 합치는 방식으로 했을 때의

계층적 트리는 아래와 같다.

Max(Complete linkage) 방식

두개의 similarity 중에서 더 유사도가 적은것 즉 값이 작은것을 선택하는 방식이다.

하지만, 항상 병합은 가장 가까운 것들 끼리 한다는것을 염두 해야한다.

선택이 필요할때는 덜 유사한 거리가 가장 먼 것을 선택하지만 일단 병합은 가장 가까운 것들 끼리 하게 된다.

	1 v 2		3	4	5
1 v 2	1		0.1	0.6	0.2
3	0.1		1	0.4	0.3
4	0.6		0.4	1	0.8
5	0.2		0.3	0.8	1

	1 v 2		3	4v5
1 v 2	1		0.1	0.2
3	0.1		1	0.3
4 v 5	0.2		0.3	1

	1v2		3v4v5
1v2	1		0.1
3v4v5	0.1		1

Group average 방식

Clustering의 각각의 특징

MIN 방식의 강점과 약점

강점: 구 모양이 아닌것에 강하다.

단점: noise에 민감하다.

MAX 방식의 강점과 약점

강점: noise에 덜 민감하다.

단점: 큰 클러스터를 쪼개는 성향이 있다. 구 모양을 선호하는 경향이 있다.

Group Average

아래와 같은 데이터가 있을때

그룹 방식의 경우 위와 같이 계산 된다.

이중에서 결국 0.26이 가장 distance 값이 작기 때문에 이렇게 합쳐지게 된다.

장점: noise와 outlier에 민감하지 않다.

단점: 구형태의 구조를 지향한다.

계층적 클러스터의 시간과 공간 관점에서의 요구사항

O(N^2)의 공간 복잡도를 가진다. proximity matrix을 생성해야 하기 때문이다.

O(N^3) 시간 복잡도를 가진다. 많은 경우에 있어서

일단 n번 수행 해야 된다.

왜냐하면 하나하나 합쳐야하니 n번 수행 해야한다.

그다음 n^2의 매트릭을 매번 업데이트 해야 한다.

사실 이건 매트릭이 매번 줄어 들기 때문에 실제로는 N^2까지는 아니다.

upper limitation의 개념이라고 할 수 있다.

추가로 특별한 자료구조를 사용할 경우 복잡도는 더 줄어 든다.

계층적 클러스터의 문제점과 한계

계산과 공간 면에서 비싸다.

한번 결정한것을 되돌리기 어렵다.

노이즈와 아웃라이어에 민감하다.

큰 클러스터를 쪼개는 경향이 있다.

그래서 결국 어느정도 계층적 알고리즘을 초반에 돌리고 그다음 부터는

K-means로 돌리는것이 좋을 수 있다.

하나만 절대적으로 쓰지않고 복합적으로 쓰는 방법이다.

Divisive Hierarchical Clustering

큰것에서 작은것으로 쪼개는 방식이다.

MST를 생성한다음 쪼개면서 수행하게 된다.

Density-based Clustering 

밀도가 가장 낮은 영역에 의해서 두개의 밀도가 높은 영역으로 분할되는 클러스터링을 말한다.

DBSCAN 이 대표적인 알고리즘이다.

Density는 EPS즉 어떤 radius 안에 있는 point들의 수를 말한다.

core point를 결정하는 것이 중요한데

이것은 EPS 안에 특정 최소한의 포인트의 개수보다 더 높은 포인트들이 있을때 이것을 결정하는 EPS를 코어라 한다.

border point는 특정 포인트 개수 보다는 적지만 코어 포인트의 이웃일때를 의미한다.

noise 포인트의 경우 코어도 아니고 border도 아닐 때를 의미 한다.

Eps =1 

MinPts = 4 

일때의 값일때의 DBSCAN의 모습이다.

DBSCAN Algorithm

모든 포인트들이 결국 core, border, noise 이 셋중 하나로 라벨링 됨.

noise point들이 제거 된다.

2개의 코어 포인트 사이에 edge를 생성 하게 된다.

연결된 코어 포이느트들의 그룹을 생성한다 어떤 분할된 클러스터 안에

각각의 border point를 연관된 코어 포인터의 하나의 클러스터로 연결 시킨다.

노이즈에 강건 하다.

서로 다른 모양과 크기의 클러스터들을 핸들 할 수 있다.

단점

밀도가 서로 다를 경우

고차원 데이터 ( 고차원 데이터는 밀도가 낮아지는 현상)

Cluster는 어떻게 평가 할 수 있을까?

Numerical measure는 다음과 같은 세가지 타입이 존재 한다.

External Index:
    클래스 라벨이 존재하는것으로 테스트 한다.

Internal Index:

외부 데이터 없이 goodness를 측정하는 방법이다.

Sum of Squared Error (SSE)

Relative Index:

External과 Internal 방법을 모두 사용 한다.