클러스터링 에서 문제

1.점의 집합들이 주어졌을때 점들사이의 거리를 어떻게 구할것인가

2.클러스터의 개수를 몇개로 해야할것인가

클러스터 멤버들 각각의 가까움과 유사도

다른클러스터들 간의 유사도가 낮게 ,서로 다르게

 

고차원에서의 점들

거리측정시 유사하게 측정되는것들

유클리드,코사인,잭카드,기타 거리재기에서

 

왜 클러스터링을 정하는것이 어려울까?

1번문제

클러스터링이 2차원 공간이라면 눈으로 보기 굉장히 쉽겠지만

클러스터의 차원이 증가하고 데이터가 증가하면 매우 보기 어려울것이다

그리고 고차원의 데이터로가면 모든점의 거리가 매우 비슷하게 보일수가 있다.

2번문제

음악씨디를 예로 들어 보면

음악씨디의 장르를 군집으로 대표해야할지

아니면 그cd를 산 사람을 군집으로 대표해야할지 고민해야한다

 

이때 구별하는 방법으로 3가지가 있는 Cosine,Jaccard,Euclidean이 있다

이것은 recommendation 에서 했으므로 비슷하게 생각하면된다

 

Hierarchical (계층적)

agglomerative(bottomup)

클러스트를 만들때 가장작은 점들을 2개씩 묶어서 만드는방식

Divisive (top down)

모든점을 하나의 클러스터로 만든뒤 클러스터를 2개씩 나누는 방식

 

계층적 클러스터링을 할때

어떻게 클러스터를 나눌것인지가 매우 중요하다

이때 3개의 중요 질문이있는데

1. 어떻게 클러스터를 대표할것인가 한점보다

2. 어떻게 가장 가까운 클러스터를 정할것인가

3. 언제 클러스터링 결합을 멈출것인가

Euclidean의 경우

centroid = 모든 점들의 평균이 되는지점

을 가장 가까운 지점으로 사용한다.

 

만약 Euclidean 이 아니라면

clustroid = 모든점과의 거리가 가장 가까운점 그러니까 중앙에 가까운 점이다 . 이걸 사용하는데

clustroid를 어떻게 정의하는가

다른점들과의 최대거리가 가장 작아야하며

다른점들과의 평균거리가 가장 적어야하고

다른점들과의 거리 제곱의 합이 가장 작아야한다

 

아무튼 이렇게 정의를 해두고

이번에는 클러스터들간에 가장 가까운 클러스터는 어떻게 정할것이냐에 대한 의논을 할것이다

접근법2:

Intercluster distance = 두 클러스터간 점들의 거리중 가장 가까운 점의 거리로 계산하는방법

접근법3

클러스터의 cohesion ( 응집력) 의 개념을 선택

clustroid의 최고거리를 이용하는방법

 

응집력(cohesion)에 대하여

1 클러스터의 직경(diameter)을 사용한다 = 클러스터의 점들사이 최고거리가 직경이 된다

2. 클러스터 안의 점들의 평균 거리를 이용한다

3. density-base approach(밀도기반 접근을 한다)

- 직경의 평균,거리,제공되는 클러스터의 점 데이터를 사용

 

사용하다

Naive implementation of hierarchical clustering

- 각각의 과정에서 클러스터의 쌍으로 계산을 해야되 ,그들이 합병할때

- O(N^3)

Careful implementation using priority queue can reduce time to O(N^2*logN)

-그러나 여전히 큰데이터는 넣을수 없을만큼 너무나도 크다