분류(K-Means, Agglomerative Clustering, DBSCAN)

본 포스팅은 충남대 이종률 교수님의 강의자료를 바탕으로 작성한 글입니다.

 

이제 분할 방법에 대한 알고리즘을 설명할 것이다.

어떤 데이터베이스 D의 n개의 객체를 k개의 클러스터로 분할하는 문제이다.

군집 내 데이터 끼리의 제곱 거리를 최소화한다.

 

K-Means Clustering

이건 가장 인기있는 접근 알고리즘이다.

임의의 수 k를 정하고, k개의 중심을 랜덤하게 배치한다. 각각 다른 컬러로.

그리고 아래의 과정을 더이상 변화가 없을 때까지 반복하는데,

1. 각 데이터를 가장 가까운 중심에 할당하고,

2. 모인 각각의 색깔의 중심을 계산에 k개의 중심을 각각 색의 중심으로 이동시킨다.

 

* 이름이 비슷한 KNN(K-Nearest Neighbors)와 헷갈릴 수 있는데,

KNN은 지도학습인 분류/회귀에서 쓰이는 아예 다른 알고리즘이다.

 

이 K-Means는 유한한 횟수 내에서 수렴이 보장되고, 

시간복잡도는

데이터 포인트들을 가장 가까운 중심에 할당하는 과정 : O(KN)

클러스터의 중심을 할당된 데이터의 중심으로 변경하는 과정 : O(N)

이다.

 

거리를 측정할 땐 여러 특성이 있는데,
D(A, B) = D(B, A)이고,
D(A, B) >= 0 이고,
D(A, B) + D(B, C) >= D(A, C) 이다. 
당연한 얘기다.

 

위의 알고리즘으로 포인트들을 분류했을 때, 얼마나 잘 분류했느냐를 '실루엣 점수'로 나타낼 수 있다.

실루엣 점수가 높으면 해당 군집 내의 다른 포인트와 가까운 것이고, 점수가 낮다면 군집 내 다른 포인트와 거리가 먼 것이다.

실루엣 점수를 S라 하고,

A를 군집내 점들간 거리의 평균이라 하고,

B를 가까운 군집까지 거리의 평균이라 하면,

S = (B-A)/max(A, B) 로 구할 수 있다.

 

S의 최댓값은 1로, 클러스터 내의 모든 포인트가 중심 위에 올려진 상황을 말한다.

그럼 A가 0이 되니까 말이다.

 

그리고 이 실루엣 점수를 plot으로 나타낸 실루엣 plot을 그릴 수 있는데, 그 plot에서  옆으로 넓으면 잘 모여있는 것이다.

그리고 이 plot에선 평균 실루엣 점수를 빨간 점선으로 나타낸다.

 

계층적 응집 클러스터링(Hierarchical Agglomerative Clustering)

이건 계층적으로 군집을 계속 결합하는 알고리즘이다.

우선 처음에는 모든 데이터 포인트가 별개의 클러스터이고,

그 중 가장 유사한 것끼리 묶어서 클러스터로 정의하는 과정을 반복한다.

이게 상향식 혹은 응집 방법이라고 한다.

근데 이게 결합 기준이 여러 개가 있다.

 

- single linkage(단일 연결) : 다른 군집 요소와 우리 군집 요소 중 가장 거리 짧은 거 중 가장 짧은 거

- complete linkage(완전 연결) : 다른 군집 요소와 우리 군집 요소 중 가장 거리 긴 거 중 가장 짧은 거

- average linkage(평균 연결) : 군집간 모든 요소쌍의 거리를 avg해서 가장 짧은 거

 

그래서 이렇게 클러스터링을 한 병합 계층들을 시각화한 것이 덴드로그램이다.

각 클러스터는 하나의 트리라고 볼 수 있고, 클러스터간 병합 시점을 추적할 수 있다.

 

이건 응집 클러스터링(계층적 클러스터링)이고, 

이제 밀도 기반 클러스터링을 봐보겠다.

 

밀도 기반 클러스터링(Density-based clustering)

만약 우리가 군집화해야하는 데이터의 형태가 막 꼬여있거나, 노이즈가 있다면?

위에서 거리만으로 군집화한 응집 클러스터링을 사용하면 클러스터링이 제대로 되지 않을 것이다.

그래서 이 밀도 기반 클러스터링을 할 것이다.

 

그 중 대표적인 DBSCAN을 할 것이다.

여기선 두 원칙이 있는데,

1. 노이즈 주변 영역은 희박하다.

2. 두 포인트가 동일 군집이라면, 두 포인트 사이를 '밀집된' 영역 내에서만 이동하면서 연결해야 한다.

 

이게 뭔 말이냐 하면은, 다음의 예시를 봐보자.

 

우선 거리 임계값인 엡실론을 설정해야 한다.

그리고 밀집 기준 임계값인 MinPts를 설정해야 한다.

 

원 형태로 볼 것인데, 

B(p, e) : 중심이 p인 반경 e의 공, p의 근접 영역

P : 군집으로 만들 포인트 set

Core point : B(p, e)가 MinPts보다 같거나 많은 개수의 포인트를 포함하는 중심 P

 

어떤 과정으로 진행되냐면,

우선 핵심 포인트 클러스터링을 하고, 비핵심 포인트를 할당할 것이다.

 

1. 핵심 포인트 클러스터링

Core Point가 될 수 있는 point들을 모두 찾는다.

그냥 그 point를 중심으로 반경이 epsilon인 원을 그렸을 때 그 안에 포인트의 개수가 Minpts이상이면 된다.

그렇게 찾아진 point 중, 반경 epsilon안에 있는 core point끼리 연결하며 엣지를 그린다.

각 연결요소가 하나의 클러스터가 된다.

 

2. 비핵심 포인트는 epsilon반경 내의 클러스터 모두에 할당된다.

만약 클러스터가 없으면 할당 안 된다.

그리고 최대 MinPts-1개의 클러스터에 할당될 수 있다.

만약 MinPts개의 클러스터에 할당된다면.. 이건 비핵심 포인트가 아니라 핵심 포인트여야 할 것이다.

 

이 과정을 거친다면 모든 군집은 유일한 군집이 될 것이다.

 

포인트 수가 n일 때, DBSCAN 클러스터는 O(dn^2)시간 내에 얻을 수 있을 것이다.