Clustering

clustering의 문제

• clustering은 서로 비슷한 멤버들로 구성되어 있다.
• 그러나 고차원공간일 때, 문제가 생긴다.
  -> 고차원으로 갈수록 빈 공간이 많아 한참 멀리 떨어져 있어도 같은 cluster로 묶인다.
  -> 차원의 저주(The Curse of Dimensionality)

 

similarity의 척도를 어떻게 측정할 것인가?

• vector로 되어있다면 cosine distance 사용
• set으로 되어있다면 jaccard distance 사용
• point로 되어있다면 Euclidean distance 사용

 

Clustering 방법

1. Hierarchical(계층적)

• Agglomerative(bottom up)
  : 가까운 두 cluster들을 반복적으로 결합하여 하나로 만든다.
• Divisive(top down)
  : 하나의 cluster를 재귀적으로 분리해 낸다.
• cluster들이 이상한 모양으로 있을 때 좋다

2. Point assignment

• point들이 가장 가까운 cluster에 속하게 된다.
• cluster들이 오목한 모양으로 이쁘게 있을 때 좋다

 

Euclidean 공간에선 실제값이 존재하므로, 

centroid를 정의할 수 있다.

centroid: point들의 집합의 평균점

 

그러나 non-Euclidean 공간에선 centroid를 정의할 수 없다.

 

 

Hierarchical Clustering

Euclidean 공간에서:

 

(1) 어떻게 cluster를 대표할까?

-> centroid= 각 점들의 평균 좌표(가상의 점)로 cluster를 대표한다.

 

(2) 어떻게 cluster에서 가장 가깝다는 것을 정의할까?

-> centroid들의 거리에 의한 cluster들의 거리를 측정 후 

가장 짧은 거리의 두 cluster를 합친다.

 

 

non-Euclidean 공간에서:

 

접근법 1. 

(1) 어떻게 cluster를 대표할까?

-> clustroid= 다른 점들과 그나마 가까운 좌표(존재하는 점)로 cluster를 대표한다.

가깝다는 건 어떻게 정의할까?

• 다른 점들과의  maximum 거리 중 가장 작은 걸 고른다. (Infinite-norm)
• 다른 점들과의 평균 거리가 가장 작은 걸 고른다. (L1-norm)
• 다른 점들과의 거리의 제곱의 합의 평균이 가장 작은걸 고른다. (L2-norm)
  -> 먼 점에게 페널티 

(2) 어떻게 cluster에서 가장 가깝다는 것을 정의할까?

-> clustroid를 centroid로 취급하고 합친다.

 

 

접근법 2.

(1) 어떻게 cluster를 대표할까?

-> 점들의 집합으로서 

 

(2) 어떻게 cluster에서 가장 가깝다는 것을 정의할까?

-> inter-cluster distance를 정의한다.

• 방법 1: 각 클러스터끼리 가장 가까운 점 2개로 거리를 잰다.
• 방법 2: 각 클러스터끼리 모든 점에 평균 거리를 잰다.

 

 

접근법 3.

1) 어떻게 cluster를 대표할까?

-> 점들의 집합으로서 

 

(2) 어떻게 cluster에서 가장 가깝다는 것을 정의할까?

-> cohesion의 개념을 정의한다.

• 합쳐진 cluster의 diameter= 클러스터에서 가장 먼 두 점사이의 거리
  -> diameter은 짧을수록 cohesion 높음
• 클러스터 안의 점들 사이의  평균거리
  -> 짧을수록  cohesion 높음
• 결합된 cluster의 density(밀도)
  -> 클수록  cohesion 높음

 

 

이런 상황이라면 그 cluster와는 합치면 안 된다.

• diameter가 threshold를 초과할 경우
• diameter가 갑자기 급격히 높아지는 경우
• density가 threshold보다 낮을 경우

 

 

K-means Algorithm

1. k개의 center를 랜덤 하게 정한다.
2. 그 center와 가까운 점들을 묶는다.

3. k개의 cluster의 centroid를 각 cluster 내의 점들의 평균점으로 업데이트한다.

4. centroid와 cluster 내의 점들의 평균점 사이의 변화가 거의 없을 때까지 2~3번 반복한다.

 

단점

: 초기 centroid에 영향을 많이 받는다.

 

 

K는 어떻게 선택할 것인가?

 

k가 작을수록 centroid로부터의 평균거리가 멀다

평균거리가 급격하게 짧아지다가 변화가 미미한 지점을 k로 선택하면 best

 

k=2인 경우

k=3