[Data Mining] 4 - Clustering

Clustering

점들이 주어지고, 점들 사이에 distance가 정의되어있다.

N개의 cluster로 점들을 그룹화 하자.

 

cluster의 멤버들은 비슷하거나 가깝다.(distance가 작다.)

cluster가 다른 멤버들은 서로 비슷하지 않다.

 

Usually:

점들은 고차원 공간에 존재한다.

Similarity는 distance 척도로 정의된다. (유클리디안, 코사인, Jaccard, edit distance 등)

 

clustering 고려 사항.

몇개의 cluster로 나눌지?

차원이 높으면 어렵다.

 

고차원 공간에서 clustering은 어려워 보인다.

거의 모든 pair들은 비슷한 distance를 가진다. -> 차원의 저주

 

차원의 저주

차원이 증가하면서 관측할수록 빈 공간이 많아지고 데이터간 거리가 늘어난다.

1차원 공간에서 [0, 1] 에 10,000 개 점이 있다고 하자.

가장 가까운 점 10개를 찾기 위해서 평균적으로 0.001 거리를 가야한다.

2차원일 경우 sqrt(0.001) = 0.032 만큼 거리를 가야한다.

10차원일 경우 0.1% 데이터를 보기 위해서 50%가 넘는 공간을 탐색해야한다.

 

 

Method of Clustering

1. Hierarchical

Agglomerative (bottom up):

  초기 각 점은 하나의 cluster이다.

  가까운 cluster들을 병합한다.

Divisive (top down):

  하나의 cluster에서 재귀적으로 분할한다.

 

2. Point assignment

cluster 수를 유지한다.

각 점들을 가장 가까운 cluster에 귀속시킨다.

 

 

Hierarchical Clustering

1. Key operation : 반복적으로 두 cluster를 병합한다.

3가지 중요한 질문이 있음.

1). 2개 이상의 점들을 가진 cluster를 어떻게 표현할 것인가? (centroid 점을 생성)

2) cluster들의 'nearness'를 어떻게 측정할 것인가? (distance 함수)

3) 언제까지 cluster를 병합할 것인가?

 

 

1). 2개 이상의 점들을 가진 cluster를 어떻게 표현할 것인가?

유클리디안 케이스 : 각 cluster는 centroid를 갖는다.

centroid = 각 점들의 평균

 

2) cluster들의 'nearness'를 어떻게 측정할 것인가? 

각 cluster의 centroid 들 사이의 거리를 측정한다.

 

 

closest Point?

clustroid = 다른 점들과 가장 가까운 점

closest의 의미

- 다름 점들과 가장 작은 최대 distance

- 다른 점들과 가장 작은 평균 distance

- 다른 점들과의 distance들의 제곱 합이 가장 작은 값.

등등...

 

Inter-Cluster Distance

cluster 간 distance ? Similarity?

다른 점들과의 가장 작은 최대/최소 distance

다른 점들과 가장 작은 평균 distance

다른 점들과의 distance들의 제곱의 합이 가장 작은 값.