Clustering

Clustering 이란?

"데이터 포인트"의 그룹화와 관련된 머신러닝 기술이다. (unsupervised learning)

어떠한 데이터 포인트 집합이 주어졌을 때, clustering 알고리즘을 사용하여 각 데이터 포인트를 특정 그룹으로 분류할 수 있다.

 

분류할 때의 기준

① high intra-class: 하나의 그룹에는 최대한 비슷한 것끼리

② low intra-class: 서로 다른 그룹들은 최대한 다른 것끼리

 

 

<K-Means Clustering 기법>

각 군집에 할당된 데이터 포인트들의 평균을 이용하여, 중심점을 반복적으로 업데이트하며 군집을 형성하는 알고리즘이다.

 

장점

① 실제로 수행하는 작업이 "포인트와 그룹 중앙 사이의 거리 계산"이므로 매우 빠르다.

② 복잡도가 O(n) 이다.

 

단점

① 모든 value 가 numeric 이어야 한다.

② 군집의 개수가 사전에 정의되어야 한다.

③ 평균을 사용하기 때문에 outlier 가 발생한다.

 

알고리즘

① 모든 object 를 random 하게 'k 개'로 그룹핑한다. (k 는 user given 으로, 사전에 정의되어야 한다.)

② 평균을 구한다.

③ 평균을 기준으로 더 가까운 것끼리 다시 군집을 생성한다.

④ 다시 만들어진 그룹에서 평균을 구한다.

⑤ 평균을 기준으로 더 가까운 것끼리 다시 군집을 생성한다.

⑥ 평균의 변동이 없을 때까지 반복한다.

→ 이 때, 평균이 조금씩이라도 계속해서 바뀔 수 있으므로 ① 횟수 제한 ② 평균의 변화도 제한 등의 설정을 통해 조정한다.

 

예제: 본인이 살고 있는 지역의 위도/경도를 통해 가까운 사람들끼리 모여보자.

1. random 하게 사람들을 k 개의 그룹으로 나눈다.

2. 평균을 구한다. → A 그룹: 대전, B 그룹: 청주

3. 대전과 더 가까운 사람, 청주와 더 가까운 사람 그룹으로 나눈다.

4. 평균을 다시 구한다. → A 그룹: 평택, B 그룹: 원주

5. 평택과 더 가까운 사람, 원주와 더 가까운 사람 그룹으로 나눈다.

6. 이 과정을 평균의 변동이 없을 때까지 반복한다.

 

 

<K-Medoid Clustering 기법>

K-Means 와 같지만, 평균 대신 Medoid (중간값)를 사용하는 알고리즘이다. 

 

장점

① numeric 이 아니어도 사용할 수 있다.

② outlier 를 고려하지 않아도 된다.

③ 실존하는 값이다.

 

단점

① 선형 복잡도가 O(n^2) 이다.

 

알고리즘

K-Means 와 동일하다.

Medoid 는 모든 데이터 포인트마다 다른 데이터 포인트들과의 distance 를 계산하고, 그 중 가장 작은 값이다.

 

<Hierarchical Clustering 기법>

비슷한 군집끼리 묶어가면서 최종적으로 하나의 케이스가 될 때까지 군집을 묶는 알고리즘이다.

n 개일 때, 각각을 single group 으로 볼 수 있고, 결국 hierarchical clustering 은 n 개에서 1개 사이의 관계이다. (양쪽 극단)

 

장점

① 유사한 개체들이 결합되는 "dendogram" 을 통해 시각화할 수 있다.

 

② 계층적 구조로 인해 사전에 군집의 개수를 정의하지 않아도 된다.

 

두 가지 기법

① buttom up(=agglomerative): n 개에서 출발하여 1개로 묶어진다.

② top down(=divisive): 1개의 데이터를 n 개로 쪼갠다.

⇨ 보통 buttom up 방식을 많이 사용한다.

 

군집 구성 시 기준

① single

군집1의 모든 데이터와 군집2의 모든 데이터의 모든 조합에 대해 데이터 사이의 거리를 측정하고, 가장 작은 값을 구한다.

a&b 와 c&d 에서 {a, c} {a, d} {b, c} {b, d} 네 가지 를 따져보았을 때 가장 가까운 distance 를 기준으로 한다.

 

② complete

군집1의 모든 데이터와 군집2의 모든 데이터의 모든 조합에 대해 데이터 사이의 거리를 측정하고, 가장 큰 값을 구한다.

a&b 와 c&d 에서 {a, c} {a, d} {b, c} {b, d} 네 가지 를 따져보았을 때 가장 먼 distance 를 기준으로 한다.

 

③ average

군집1의 모든 데이터와 군집2의 모든 데이터의 모든 조합에 대해 데이터 사이의 거리를 측정하고, 평균을 구한다.

 {a, c} {a, d} {b, c} {b, d} 에서 평균을 기준으로 한다.

 

④ centroid

두 군집의 각 중심점(centroid)을 정의한 다음, 두 중심점의 거리를 군집 간의 거리로 정의한다.

a&b 에서의 centroid, c&d 에서의 centroid 를 구하고 그 두 점 사이의 거리를 기준으로 한다. 

 

예제: 30명의 학생들의 친구 관계를 buttom up 으로 만들어보자. "친하다"의 기준은 지난 연휴 때 전화통화를 가장 많이 한 사람이다. 

1. 나 자신만이 친구이다. → 30개의 그룹

2. 전화통화 시간이 가장 긴 pair 를 고른다. → 29개의 그룹

3. pair 가 된 두 사람을 대표하는 또 한 가지의 기준으로부터(ex. 두 사람 중 다른 사람과 통화 시간이 더 긴 것을 기준으로 하자.) 29개의 그룹을 검사한다. (이 때 기준은 user given) → 28개의 그룹

4. 반복한다. → 1개의 그룹

 

 

<Density Based Scan 기법>

밀도 기반의 data point 들이 밀집된 곳을 하나의 군집으로 보는 알고리즘이다.

 

장점

① outlier (노이즈)를 제외할 수 있다.

② 군집의 수를 지정해주지 않아도 된다.

③ convex 형태가 아닌 데이터 셋에 적용할 수 있다.

 

주요 parameter

① ε (입실론): 하나의 data point 를 중심으로 하는 반경

 

② Minimum Points: 군집을 이루기 위한 최소한의 data point 의 개수

⇨ Density 는 하나의 점으로부터 "반경 ε 내에" "점이 몇 개나 있는지"로 측정한다.

 

분류 point

① core point: 한 점의 ε 내에 min point 보다 많은 개체가 포함된 점

 

② border point: 한 점의 ε 내에 min point 보다 적은 개체가 포함하지만, 적어도 하나의 core point 에는 속한 점

③ noise point(outlier): 한 점의 ε 내에 min point 보다 적은 개체가 포함하는 점

 

알고리즘

① Directly Density Reachable

p 가 q 의 ε 내에 들어오고, q 는 core point 이다. → p 는 q 로부터 Directly Density Reachable 하다.

 

② Density Reachable

p 가 p2의 ε 내에 들어오고, q 가 p2 의 ε 내에 들어온다. → p 는 q 로부터 Density Reachable 하다.

 

③ Density Connected

p 는 o 로부터 Density Reachable 하고, q 역시 o 로부터 Density Reachable 하다. → p 는 q 로부터 Density Connected 하다.