[머신러닝] 군집화(Clustering)

K-평균 군집화(K-Means Clustering)

K-평균 군집화(K-Means Clustering)은 군집화에서 가장 많이 사용되고 쉽게 적용할 수 있다. 우선 군집 중심점(Centroid)를 설정하고 주변 데이터를 그룹화한다. 그룹화된 데이터들의 평균 지점으로 군집 중심점을 이동하며 다시 주변 데이터를 그룹화한다. 이 과정을 반복하면서 데이터들을 군집화하게 된다. 적용 알고리즘이 쉽고 간결하며 대용량 데이터에도 활용이 가능하지만 거리 기반 알고리즘이기 때문에 속성의 개수가 많을 경우 군집화 정확도가 떨어진다. 또 이상치(Outlier) 데이터가 많을 경우 군집화의 신뢰도가 떨어지게 된다.

- K-평균 군집화 과정

 

1. 군집 중심점을 군집화 개수만큼 임의의 위치에 가져다 놓는다.

2. 각각의 데이터들은 가장 가까운 군집 중심점에 소속된다.

3. 중심점에 할당된 데이터들의 평균 위치로 중심점을 이동시킨다.

4. 데이터들은 이동된 중심점들을 중 가까운 중심점에 다시 소속된다.

5. 중심점에 할당된 데이터들의 평균 위치로 다시 중심점을 이동시킨다.

6. 중심점이 이동되고 다시 데이터들을 할당하는데 이전의 데이터와 변화가 없으면 군집화가 완료된다. 

 

평균 이동(Mean Shift)

평균 이동(Mean Shift)는 K-평균과 유사하게 군집의 중심으로 지속적으로 움직이며 군집화를 수행한다. 소속된 데이터의 평균으로 이동하는 K-평균과 다르게 평균 이동은 주변 데이터 값 중 확률 밀도가 가장 높은 곳으로 이동한다. 확률 밀도 함수(Probability density function)를 통해 함수 밀도가 높은 곳을 판단하며 모델의 확률 밀도 함수를 찾기 위해 KDE(Kernel Density Estimation)을 이용한다.

 

 

- KDE(Kernel Desity Estimation)

 

KDE(Kernel Desity Estimation)는 커널(Kernel) 함수를 적용한 값을 모두 더한 뒤 데이터 건수로 나누어서 확률 밀도 함수를 추정하는 방법이다. KDE를 이용하여 추정한 확률 밀도 함수를 통해 변수의 특성(정규 분포의 평균, 분산 등) 요소를 알 수 있다.

KDE(Kernel Desity Estimation)

 

K는 커널 함수, x는 확률 변수값, xi는 관측 값, h는 대역폭(bandwidth)이다. 설정된 대역폭의 값에 따라 확률 밀도 추정 성능을 좌우하게 되는데 작은 대역폭은 변동성이 커져 과적합하기 쉽다. 큰 대역폭의 값을 가지면 단순화된 방식으로 추정하게 되어 과소적합의 가능성이 커진다.

 

- 평균 이동 과정

1. 개별 데이터의 특정 반경 내 데이터 분포도를 KDE를 통해 계산한다.

2. 데이터 분포도가 높은 방향으로 데이터를 이동시킨다.

3. 앞의 1, 2 과정을 반복하며 개별 데이터들을 군집 중심점으로 모은다.

4. 지정된 Iteration 만큼 데이터를 이동시키며 군집화를 수행한다.

5. 개별 데이터들이 모인 중심점을 군집 중심점으로 설정한다.

 

 

GMM(Gaussian Mixture Model)

GMM(Gaussian Mixture Model)은 데이터가 여러 개의 가우시안 분포(GaussianDistribution)를 가진 데이터 집합들이 섞여 생성된 것이라는 가정하에 군집화를 수행하는 방식이다. GMM은 개별 정규 분포들의 평균과 분산을 추정하고 데이터가 특정 정규 분포에 해당될 확률을 추정하는 데 이를 모수 추정이라고 한다. 이러한 모수 추정을 위해 EM(Expectation and Maximization)을 사용한다.

 

 

 

- EM 방법

 

Expectation

-> 개별 데이터 각각에 대해서 특정 정규 분포에 소속될 확률을 구하고 가장 높은 확률을 가진 정규 분포에 소속한다.

Maximization

-> 데이터들이 특정 정규분포로 소속되면 다시 해당 정규 분포의 평균과 분산을 구한다.

    해당 데이터가 발견될 수 있는 가능도를 최대화(Maximum likelihood) 할 수 있도록 평균과 분산을 구한다.

 

개별 정규분포의 모수인 평균과 분산이 더 이상 변경되지 않고 각 개별 데이터들이 이전 정규 분포 소속이 더 이상 변경되지 않으면 그것으로 최종 군집화를 결정하고 그렇지 않으면 EM을 반복한다.

 

 

DBSCAN(Density Based Spatial Clustering of Applications with Noise)

DBSCAN(Density Based Spatial Clustering of Applications with Noise)는 대표적인 밀도 기반 군집화 알고리즘이다. 복잡한 기하학적 분포도를 가진 데이터 세트에서도 잘 수행한다. 데이터의 밀도가 자주 변하거나 밀도가 크게 변하지 않으면 군집화의 성능이 떨어지며 피처의 개수가 많아도 군집화의 성능이 떨어진다.

 

 

 

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

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

 

핵심 포인트(Core Point) : 주변 영역 내에 최소 데이터 개수 이상의 타 데이터를 가지고 있을 경우 해당 데이터를 의미

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

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

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

 

- DBSCAN 과정

 

1. 입실론 반경 내의 최소 데이터의 수를 만족하는 핵심 포인트(Core Point)를 찾는다.

2. 이웃 데이터 포인트에도 핵심 포인트가 존재하면 핵심 포인트끼리 연결한다. 

3. 계속해서 핵심 포인트를 찾고 연결해가며 군집화를 진행한다.

 

여러 군집화 알고리즘 결과 비교

 

군집 평가(Cluster Evaluation) - 실루엣 분석(Silhouette analysis)

실루엣 분석(Sihouette analysis)은 군집화가 효율적으로 진행됐는지 평가하는 방법이다. 군집화된 클러스터의 내부는 가깝고 클러스터 간 거리는 멀면 효율적으로 잘 분리됐다는 것을 의미한다. 이는 실루엣 계수(Silhouette Coefficent) 값으로 나타낼 수 있는데 -1과 1사이의 값 중에서 1에 가까울수록 근처의 클러스터와 더 멀리 떨어졌다는 의미이고 0에 가까울수록 클러스터 간 거리가 가깝다는 것을 뜻한다. 음수의 값을 가지면 아예 다른 군집의 데이터가 할당됐음을 의미한다.

 

실루엣 계수(Silhouette Coefficent)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

출처 : 파이썬 머신러닝 완벽 가이드 - 권철민