K-means, Approx_k Clustering(의사코드, 근사비율)

□ K-means 알고리즘

  - k평균 클러스터링 알고리즘은 클러스터링 방법 중 분할법에 속한다.

ex)

 N개의 데이터 오브젝트를 입력 받았다면, 분할법은 N보다 작거나 같은 K개의 그룹으로 나누는데,

이 때 각 군집은 클러스터를 형성하게 된다.  (1개 이상의 데이터 오브젝트로 구성된 k개의 그룹으로 나누는것)

이 때 군집을 나누는 과정에서 같은 그룹 내 데이터 오브젝트 끼리 유사도는 증가

다른 그룹에 있는 데이터 오브젝트와의 유사도는 감소.

 - 최초에는 무작위 k개의 중심 1)데이터를 선정하고, 해당 데이터로부터 각  2)데이터의 거리(유클리디언, 맨하탄 등)을

    계산한다.

그 거리의 평균이 작은 곳으로 3)중심점을 변경하고,   4)다시 거리를 계산하는 것을 반복하여 최적의 군집을 찾을 수 있다.

(유클리디언 거리)

(그림으로 보는 과정 - 출처 : 위키디피아)

(복잡도)

□ Approx_k_Clusters의 의사코드

각 라인별로 과정을 살펴 보면

□ 최적해와 근사비율

컴퓨터 과학에서 프로그램 최적화 혹은 소프트웨어 최적화는 더 적은 자원을 사용하거나

프로그램체계에서 더 효율적으로 작동되어지게 변경(수정)하는 작업이다.

Approx_k_Clusters 알고리즘에서는 최적해를 구하는것이 사실 NP완전문제 이므로

최적해에 가까운 근사해를 찾는것이 바람직하다 볼 수 있다.

N개의 점에 대해 K개의 Center까지 거리를 계산하는 과정을 K개의 Center들에 대해서

가장 큰 직경을 갖는 클러스터가 최적해가 된다.

최적해인 클러스터 OPT는 두 개의 Center가 포함되며,

두 Center의 거리보다는 직경이 크거나 같을 것이므로

두 센터의 거리를 d라 했을 때 OPT>=d 라는 등식이 성립한다 볼 수 있다.

또한,  각 클러스터의 센터를 중심으로 반경d 이내에 클러스터에 속하는 모든 점들이

위치하게 되므로 근사해를 OPT’ 이라고 가정 했을때 OPT’ <= 직경(2d)와 같은 등식이

성립되는 것을 볼 수 있는데, 결과적으로, 직경과의 등식 관계를 통해

2OPT>= 2d >= OPT’ 으로써  2OPT>=OPT’ 이라는 근사비율이 2가 넘지않는다는 것을 증명 할 수 있다.