criling

DBSCAN은 간단하고 직관적인 알고리즘으로 되어 있지만 데이터의 분포가 기하학적을 복잡한 데이터 세트에도 효과적인 군집화가 가능하다.

내부의 원모양과 외부의 원 모양 형태의 분포를 가진 데이터 세트는 K 평균, 평균 이동, GMM으로 효과적인 군집화는 수행이 어렵다. DBSCAN은 특정 공간 내에 데이터 밀도 차이를 기반 알고리즘으로 하고 있어 복잡한 기하학적인 분포도를 가진 데이터 세트에 대해서도 군집화를 잘 수행한다.

DBSCAN을 구성하는 가장 중요한 두 가지 파라미터는 입실론(epsilon)으로 표기하는 주변 영역과 이 입실론 주변 영역에 포함되는 데이터의 개수 min points이다.

- 입실론 주변 영역(epsilon) : 개별 데이터를 중심으로 입실론 반경을 가지는 원형의 영역

- 최소 데이터 개수(min points) : 개별 데이터의 입실론 주변 영역에 포함되는 타 데이터의 개수

입실론 주변 영역 내에 포함되는 데이터 개수를 충족시키는가 아닌가에 따라 데이터 포인트를 다음과 같이 정의

- 핵심 포인트(Core Point) : 주변 영역 내에 최소 데이터 개수 이상의 타 데이터를 가지고 있는 데이터

- 이웃 포인트(Neighbor Point) : 주변 영역 내에 위치한 타 데이터

- 경계 포인트(Border Point) : 주변 영역 내에 최소 데이터 개수 이상의 이웃 포인트를 가지고 있지 않지만 핵심 포인트를 이웃 포인트로 가지고 있는 데이터

- 잡음 포인트(Noise Point) : 최소 데이터 개수 이상의 이웃 포인트를 가지고 있지 않으며, 핵심 포인트도 이웃 포인트로 가지고 있지 않는 데이터

GMM(Gaussian Mixture Model)

군집화를 적용할 데이터가 여러개의 가우시간 분포를 가진 데이터 집합들이 섞여 생성된 것이라는 가정 하에 군집화를 수행하는 방식.

정규 분포는 평균 u(뮤)를 중심으로 높은 데이터 분포도를 가지고 있으며, 좌우 표준편차 1에 전체 데이터의 68.27%, 좌우 편차 2에 전체 데이터의 95.45%를 가지고 있습니다. 평균이 0이고, 표준편차가 1인 정규 분포를 표준 정규 분포라고 한다.

GMM은 데이터 여러개의 가우시안 분포가 섞인 것으로 간주한다. 즉, 각 각의 가우시안 분포가 개별 군집이 되는 것이다.

전체 데이터 세트는 서로 다른 정규 분포 형태를 가진 여러가지 확률 분포 곡선으로 구성될 수 있으며 이러한 서로 다른 정규 분포에 기반해 군집화를 수행하는 것이 GMM 군집화 방식이다.

여러 개의 데이터세트가 있다면 이를 구성하는 여러 개의 정규 분포 곡선을 추출하고, 개별 데이터가 이 중 어떤 정규 분포에 속하는지 결정하는 방식이다.

GMM에서의 모수 추정

- 개별 정규 분포의 평균과 분산

- 각 데이터가 어떤 정규 분포에 해당되는지의 확률

모수추정을 위해 GMM은 EM(Expectation and Maximization) 방법을 적용한다.

GMM과 K-평균의 비교

Kmeans는 원평의 볌위에서 군집화를 수행한다. 즉 데이터 세트가 원형의 범위를 가질수록 KMeans의 군집화 효율은 더욱 높아진다.

평균 이동(Mean Shift)

K-평균과 비슷하게 중심을 군집의 중심으로 지속적으로 움직이면서 군집화를 수행

K-평균이 중심에 소속된 데이터의 평균 거리 중심으로 이동하는 반면, 평균 이동 중심은 데이터가 모여 있는 밀도가 가장 높은 곳으로 이동

평균 이동 군집화를 데이터 분포도를 이용해 군집 중심점을 찾는다. 이를 위해 확률 밀도 함수(probability density function)를 이용한다. 주어진 모델의 확률 밀도 함수를 찾기 위해 KDE(Kernel Density Estimation)를 이용한다.

(표현은 확률 밀도 함수를 찾는다고 했지만 확률 밀도 함수를 정하여 밀도가 

특정 데이터를 반경 내의 데이터 분포 확률 밀도가 가장 높은 곳으로 이동하기 위해 주변 데이터와의 거리 값을 KDE 함수 값으로 입력한 뒤 그 반환 값을 현재 위치에서 업데이트하면서 이동한다.

KDE는 커널 함수를 통해 어떤 변수의 확률 밀도 함수를 추정하는 대표적인 방법이다.

관측된 데이터 각각에 커널 함수를 적용한 값을 모두 더하여 데이터 건수로 나눠 확률 밀도 함수를 추정한다.

모든 커널 함수를 더하게 되면 KDE 함수가 생성되고, 각 커널 함수에서 겹치는 부분, 데이터의 밀도가 높은(밀집되어 있는)구간은 KDE 함수의 크기가 커진다.

확률 밀도 함수 PDF(Probability Density Function)는 확률 변수의 분포를 나타내는 함수로 널리 알려진 정규 분포 함수를 포함해 감마 분포, t-분포 등이 있다.

이렇게 구한 확률 밀도 함수로 특정 변수가 어떤 값을 갖게 될지에 대한 확률을 알게되므로 이를 통해 변수의 특성(정규분포의 경우 평균, 분산), 확률 분포 등 변수의 많은 요소를 알 수 있다.

대표적인 커널 함수로는 가우시안 분포 함수가 있다.

$$ KDE = \frac{1}{n}\sum_{i=1}^{n}K_{h}(x-x_{i}) = \frac{1}{nh}\sum_{i=1}^{n}K(\frac{x-x_{i}}{h}) $$

K = 커널 함수, xi = 관측값, h = 대역폭

h(대역폭)는 KDE 형태를 부드러운(또는 뾰족한) 형태로 평활화(Smoothing)하는데 적용된다.

이 h를 어떻게 설정하느냐에 따라 확률 밀도 추정 성능을 크게 좌우 할 수 있다.

h가 작다면 좁고 뾰족한 KDE를 가지고(군집 중심점이 많다) 이는 변동성이 큰 방식으로 확률 밀도 함수를 추정하여 과적합이 발생하기 쉽다. 반대로 h가 크다면 KDE가 과도하게 평활화되어(군집 중심점이 적다) 과소적합이 발생하기 쉽다. 따라서 적절한 h값은 평균 이동 군집화에서 매우 중요하다.

평균 이동의 장점은 데이터 세트의 형태를 특정 형태로 가정한다든가, 특정 분포도 기반의 모델로 가정하지 않기 때문에 좀 더 유연한 군집화가 가능하다는 것이다. 이상치의 영향력 또한 크지 않으며, 미리 군집의 개수를 정할 필요도 없다.

하지만 알고리즘 수행 시간이 오래걸리고 bandwidth의 크기에 따른 군집화 영향도가 매우 크다.

그렇기에 평균 이동 군집화는 분석 업무 기반의 데이터 세트보단 컴퓨터 비전 영역에서 많이 사용된다.

이미지나 영상 데이터에서 특정 개체를 구분하거나 움직임을 추적하는데 뛰어난 역할을 수행하는 알고리즘이다.

군집화는 분류(Clasification)와 비슷해 보일 수 있으나 성격이 많이 다르다. 데이터 내에 숨어 있는 별도의 그룹을 찾아서 의미를 부여하거나 동일한 분류 값에 속하더라도 그 안에서 더 세분화된 군집화를 추구하거나 서로 다른 분류 값의 데이터도 더 넓은 군집화 레벨화 등의 영역을 가지고 있다.

비지도학습의 특성상 어떠한 지표라도 정확하게 성능을 평가하긴 어렵다 그럼에도 군집화의 성능을 평가하는 대표적인 방법으로 실루엣 분석을 이용한다.

실루엣 분석(silhouette analysis)

각 군집 간의 거리가 얼마나 효율적으로 분리돼 있는지를 나타낸다.

효율적으로 잘 분리됐다는 것은 다른 군집과의 거리는 떨어져 있고 동일 군집끼리의 데이터는 서로 가깝게 잘 뭉쳐 있다는 의미이다.

실루엣 분석은 실루엣 계수(silhouette coefficient)를 기반으로 한다. 실루엣 계수는 개별 데이터가 가지는 군집화 지표이다. 즉, 개별 데이터가 가지는 실루엣 계수는 해당 데이터가 같은 군집 내의 데이터와 얼마나 가깝게 군집화 돼 있고, 다른 군집에 있는 데이터와는 얼마나 멀리 분리돼 있는지를 나타내는 지표이다.

a(i) : 해당 데이터 포인트와 같은 군집 내에 있는 다른 데이터 포인트와의 거리를 평균한 값

b(i) : 해당 데이터 포인트가 속하지 않은 군집 중 가장 가까운 군집과의 평균 거리

두 군집 간의 거리가 얼마나 떨어져 있는가 b(i) - a(i), 정규화 -> MAX( a(i), b(i) )

i번째 데이터 포인트의 실루엣 계수 s(i) = (b(i) - a(i)) / MAX( a(i), b(i) )

이는 -1 ~ 1 값을 가지며 1에 가까울 수록 근처의 군집과 멀리 떠떨어져 있고, 0에 가까울 수록 근처의 군집과 가깝다는 말이다. - 값은 아예 다른 군집 데이이터 포인트가 할당 됐음을 의미

좋은 군집화의 기준

1. 전체 실루엣 계수의 평균값이 0 ~ 1사이, 1에 가까울수록 좋다.

2. 개별 군집의 평균 값의 편차가 크지 않아야 한다. -> 개별 군집의 실루엣 계수가 전체 실루엣 계수의 평균값에서 크게 벗어나지 않아야 한다.

K-평균은 군집 중심점(centroid)라는 특정한 임의의 지점을 선택해 해당 중심에 가장 가까운 포인트들을 선택하는 군집화 기법.

군집 중심점

선택된 포인트의 평균 지점으로 이동하고 이동된 중심점에서 다시 가까운 포인트를 선택, 다시 중심점을 평균 지점으로 이동하는 프로세스를 반복적으로 수행. 모든 데이터 포인트에서 더 이상 중심점의 이동이 없을 경우에 반복을 멈추고 해당 중심점에 속하는 데이터 포인트들을 군집화하는 기법.

1. k개의 군집 중심점 설정

2. 각 데이터는 k개의 중심점들 중 가장 가까운 중심점에 소속

3. 중심점에 할당된 데이터들의 평균 중심으로 중심점 이동

4. 중심점을 이동하였지만 데이터들의 중심점 소속 변경이 없으면 군집화 완료

K-평균의 장점

- 일반적인 군집화에서 가장 많이 활용되는 알고리즘

- 알고리즘이 쉽고 간결

k-평균의 단점

- 거리 기반 알고리즘으로 속성의 개수가 매우 많을 경우 군집화 정확도가 떨어진다.

(이를 PCA로 차원 감소를 적용해야할 수도 있다.)

- 반복을 수행하는데 반복 횟수가 많을 경우 수행시간이 매우 느려진다.

- 몇 개의 군집(cluster)을 선택해야 할지 가이드가 어렵다.