[데이터 마이닝5] Cluster Analysis #2

Clustring Approaches- 클러스터링 접근법

1. Partitioning approach

2. Hierarchical approach

3. Density-based approach

4. Grid-based approach

5. Model-based

6. Frequent pattern-based

7. User-guided or Constraint-based

대표적인 클러스터 간의 거리 계산 방법

1. Single Link 

두 클러스터에 포함되는 모든 점들 중 가장 서로 가까운 두 점의 거리를 클러스터 간의 거리로 정의

2. Complete Link

Single Link의 반대로 두 클러스터 간의 가장 먼 거리를 클러스터 간의 거리로 정의

3. Average

dis(Ki, Kj) = avg(tip, tjq)

4. Centroid

dis(Ki, Kj) = dis(Ci, Cj)

5. Medoid

클러스터 안에서 중심에 위치한 하나를 선택하여 거리를 계산

Cm은 중심을 나타내며 Rm은 반지름, Dm은 지름을 구하는 수식이다.

Partitioning Method

전체 집합을 k개의 클러스터로 분할하고 각 클러스터 안에 객체와 각 클러스터의 센터와의 거리를 minimization하여 클러스터링 하는 방법

k가 주어졌을 경우 최적의 클러스터를 찾는 방법

1. Global Optimal : 모든 가능한 클러스터를 모두 계산하여 최적의 값 찾기

2. Heuristic Method : K-means, K-Medoids

• K-Means Clustering Method

  
  

  

  장점 

      상대적 계산 효율성 : O(tkn)  -> n은 오브젝트 수 , k는 클러스터 수, t는 반복 횟수 (t<<n)

        비교 : PAM: O(k(n-k)2 ), CLARA: O(ks2 + k(n-k))

  문제점

      때때로 지역적 최적화에 빠진다. 

      전역적 최적해를 위해서는 유전자 알고리즘(genetic algorithm), Deterministic Annealing 을 사용

  단점

      오직 평균이 정의 될 때만 적용가능하다. 그렇다면 Categorical Data는 어떻게?

      특별한 변수인 k를 정의할 필요가 있다

      노이즈와 아웃라이어(왕따)에 취약하다

      non-convex 형태의 클러스터에 적합하지 않다.

  
  

  여러가지 방법에 따른 K-means 다양성

      1. 초기 Mean에 선택에 따라 다르다

      2. 거리 계산 방법에 따라 다르다

      3. 클러스터 중심을 구하는 방법에 따라 다르다

  
  

  K-mean은 outlier에 약하기 때문에 이에 대한 대책으로 k-medoid 방법을 말하고 있다.

  medoid는 실제 데이터 중에 하나를 클러스터의 중심으로 쓰는 방법이다. 

  
  

  K-Medoid 종류

      1. PAM ( Partitioning Around Medoid)

      2. CLARA

      3. CLARANS

      4. Focusing + spatial data structure

  
  

  1. PAM(Partitioning Around Medoid)

  

  
  

  위의 그림은 PAM의 전체적인 알고리즘을 도식화 한 결과이다. 임의로 medoid 선택하고 다른 medoid를 선택하여 얼마나 좋아졌나를 계산한 뒤 좋아졌다면 medoid 변경, 좋아지지 않았다면 다른거 선택하여 반복하는 방법을 나타낸다. 그렇다면 거리 계산, 비용 계산은 어떻게 할까?

  

  이 그림은 비용 계산 하는 방법에 대해서 나타낸다. 먼저 i는 현재 medoid를 나타내며, h는 랜덤하게 선택한 medoid를 나타낸다 즉. i에서h로 바꿀지 말지를 결정해야된다는 말이다. 이를 위해 나머지 다른 오브젝트랑 거리를 계산해야한다. 그 예가 j이다.  

  그림을 잘 보면 위의 4가지 경우 모두 j를 기준으로 생각하는 것이 편하다. 좌상단 그림에서 j는 i medoid에 속해있다가 h로 변경할 경우 h medoid에 속한다 따라서 " 변경햇을 경우 거리 - 현재 거리 "를 계산한다. 두번째 그림은 j는 이전 i medoid에 속해있지 않으며, h로 변경하더라도 h에 속하지도 않는다, 따라서 0이다. 좌하단 그림은 j는 i에 속해있는 상태에서 h로 변경할 경우 t에 속하게 된다. 따라서 변경햇을 때 거리(d(j,t)) - 현재 거리(d(j,i)) 를 이용하여 Cjih를 구한다. 마지막 그림은 j는 i에 속해있지는 않지만 h로 변경할 경우 h에 속하게 된다.  따라서 변경했을 때 거리( d(j,h) ) - 현재 상태의 거리 ( d(j,t) ) 를 이용하여 Cjih를 구하는 것이다.

  
  

2. CLARA

 - 기본적으로 PAM와 유사하다. PAM은 데이터 크기가 커지면 무진장 연산량이 늘어나게 된다. 이를 극복하기 위한 방법이 CLARA이다. 

  단점 

     효율성은 샘플 크기에 의존적이다

     샘플이 골고루 샘플링되지 않고, 한쪽으로 치우지거나 bias 형태로 추출되었다면 좋은 클러스터링을 기대하        

기 어렵다

3. CLARANS ("Randomized" CLARA)

       - randomized Search 에 기반한 클러스터링 방법

Hierarchical Method

클러스터링 판별식으로 거리 행렬을 사용하며, 클러스터의 갯수 k를 정할 필요 없지만 대신 종료 조건이 필요하다

크게 두가지 방법이 있다 top-down 방식( 처음에 모두 병합된 상태로 조금씩 분할하는 단계) , bottom-up (모두 분할된 상태로 점점 병합하는 방법)이 있다.

BIRCH

CF는 갯수와 벡터의 합, 제곱의 합을 가지고 있다. 따라서 평균과 분산을 쉽게 구할수 있다

파라미터 B는 자식의 맥스 갯수이며, 임계값 L은 리프노드에 저장된 하위 클러스터의 맥스 갯수(지름)이다.

ROCK(Robust Clustering using Links)

Jaccard co-efficient-based Similarity function :

예제) T1 = {a,b,c}, T2={c,d,e}

link의 개념은 다시 말해서 위의 예제를 보면 c가 겹친다. 부분 집합인 c가 포함된 다른 객체들의 수가 두 집합간의 link가 된다.

CHAMELEON

두 클러스터 간의 내부 연결성과 근접성이 클러스터의 내부 연결성과 클러스터 내의 아이템들의 근접성에 상대적으로 높을 때만 두 클러스터는 병합된다. ( 즉 between Class와 within class의 거리를 이용하여 병합을 결정한다는 의미인듯)

알고리즘

1. 전체 집합을 아주 작은 서브 집합으로 분할한다.

2. 반복적으로 하위 집합을 결합하여 잘 맞는 클러스터를 찾는다

Density-Based Method

장점

모든 형태로 클러스터링 가능( 컨벡스가 아니여도 가능)

노이즈를 조절 가능

one scan

종료 조건으로서 밀도 파라미터 필요

파라미터 종류

Eps : 이웃의 가장 큰 반경

Minpts : eps 반경안에 포인트들의 최소 갯수

Directly density-reachable

어떤 한 점 q에서 반지름 내에 p가 있고(Neps(q) ) q 주위 반경 eps 내에 일정 갯수 이상의 점이 존재하면   ( | Neps(q) | >= MinPtr ) Core Point이며 둘 다 만족할 경우 density-reachable 하다 한다.

Density-reachable

A에서 B는 directly density-reachable 하고 B에서 C가 directly density-reachable 하다면 A에서 C는 density-reachable 하다

Density-connected

어떤 한 점 o로 부터 q와 p가 모두 density-reachable 하다면 q와 p는 density-connected 하다라고 할 수 있다.

DBSCAN(Density Based Spatial Clustering of Applications with Noise) 알고리즘

1. 임의 점 p 선택

2. Eps와 MinPts를 만족하는 p로부터 Density-reachable한 모든 포인트 찾는다

3. p가 만약 core point라면 클러스터를 만든다

4. p가 border 포인트라면 density-reachable한 포인트는 존재 하지 않을 것이며, 다음 포인트를 방문한다.

5. 모든 포인트가 다 처리 될 때까지 반복한다.

OPTICS ( A Cluster-Ordering Method)

너무 어렵다.ㅋㅋ 완전 햇갈림

나름 정리를 해보자면, 

1. Core distance

     eps와 minptr가 주어지면 반경 eps안에 minptr이상의 점들이 존재해야하며, 존재할 경우 minptr 번째 점과의 거리가 core distance가 된다.

2. Reachability distance

o가 core object이면 o의 이웃들에서 모두 구하는 것이다. 구하는 방법은 o와 o의 이웃점들 중 하나인 p와의 거리와 o의 core distance 중 큰 겂을 점 p의 reachability distance로 정의한다. 그렇다면 각 점 p는 여러 점 o에서 reachbility distance가 여러개가 나올 수 있는데 이중 가장 작은 값을 점 p의 Reachability distance로 정의한다.

Max (core-distance (o), d (o, p))

 

본 게시물이 도움이 되었다면, 꾸~욱~ 눌러주세요.

포스팅 하는데 많은 힘이 됩니다~~~