k-means알고리즘은 맨 처음 k개의 center를 잘못 정하면 엉뚱한 결과가 생길 수 있다.
예를 들면, 다음 그림과 같은 경우이다.
k=3 일때, 파란색 세개의 클러스터로 묶이는 것이 올바른 결과다. 하지만, 잘못 해서(또는 재수가 없어서) 두번째 열의 인스턴스 세개를 초기 center로 잡고 k-means 알고리즘을 돌리면 엉뚱하게도 빨간색 묶음으로 클러스터링되는 난감한 결과가 생기고 만다. 이게 2차원으로 시각화 되어서 그렇지, 실제 상황에서는 눈에도 잘 안뜨일 듯.
그래서, 이제 갖가지 초기 center 정하는 방법들이 등장하게 된다. 창시자들이 저렇게 빈틈을 남겨주어야 후배 연구자들이 먹구 살 거리가 생기게 된다. 암튼, 개선안 중에 하나가 그럼 되도록 center간의 간격을 멀게 멀게 만들자는 것이다. 위의 예를 계속 이용하면 아마 이렇게 될 것이다.
1 ~ 3이 초기 center로 선정된 instance들이다. 1번은 랜덤으로 선정된 것이고, 2번은 1번으로 부터 제일 먼 것, 3번은 1번, 2번으로 부터 가장 먼 것으로 선정된다. 이렇게 선정한 세개의 center를 가지고 클러스터링을 하면 창시자의 부족함을 매꾸며 성공적인 클러스터링을 달성함과 동시에 후배들에게 또다시 TODO list를 남겨준다. 즉, 이 방법 또한 큰 약점을 가지고 있는데, Outlier라는 넘을 만나면 여지 없이 무너지는 수가 있다.
이 번에는 k=2인 경우인데 되도록 먼 인스턴스를 선택 하다보니 맨 오른쪽 독도 같은 outlier가 초기 center로 선정되었다. 이러고 k-means를 돌리면, 7:1의 클러스터링이 탄생할 것이다. outlier말고, 가운데 3개 중에 하나가 선택되면 좋을 텐데 말이다.
이래서 등장한 것이 k-means++. k-means++는 다음 순서대로 하나씩 하나씩 1번 부터 k번째 center까지 정한다. 이게 개념은 참 간단한데, 글로 표현하는 것이 쉽지가 않다.
위 식의 분모는 모든 인스턴스 x의 D(x)2의 합이니까. 모든 x에 대해서 같고, 결국 분자인 D(x)2이 큰 게 확률이 높다. 그러면 결국 D(x)가 클수록 확률이 높다. 이 얘기는 지금까지 만들어진 center들과 멀 수록 확률이 높다는 건데, 그럼 결국 먼거를 찍는다는 얘기?? 그럼, 저 위에 거랑 똑같다? 그럴리가.
중요한 건, 확률을 저렇게 정해놓고, 랜덤으로 찍는다는 것이다. 그러니까, 거리가 먼 outlier는 물론 확률은 높다. 하지만, 거리가 가장 먼 놈을 무조건 선정하지는 않는다는 것이다. 무조건 먼거로 결정할 거면 그냥 D(x)만 구하지, 굳이 D(x)2 나누기 D(x')2의 합을 굳이 구하지는 않았겠지. 그림을 보면,
파란색이 1번째 center이고, 이제 2번째 center를 선정하려고 한다. 숫자는 인스턴스 마다 지금까지 center 중(지금은 파란 인스턴스 하나뿐) 제일 가까운 것과의 거리인 D(x)이다.
이제 인스턴스마다 확률을 부여해야 하는데, 분모 먼저 구하면 모든 D(x)2의 합이니까 12+52+52+52+82=140 이다. 그러면, 제일 가까운 인스턴스의 확률은 1/140, 빨간색 애들은 각각 25/140, 제일 먼 애는 64/140 의 확률을 받는다. 이런 확률를 놓고 랜덤으로 찍는다. 제일 먼 인스턴스의 확률(64/140)이 가장 높지만, 세개의 빨간 인스턴스 중의 하나가 될 확률(3 * 25/140)이 더 높다. 먼 것도 유리하지만, 몰려있는 것중 하나가 될 확률도 높다. 2제곱이라는 숫자는 거리를 확률에 반영하는 정도를 결정하는 factor라고 생각하면 되겠다.
요약 정리 : k-means++는 확률 기반으로,
1. center가 밀집되지 않게
2. outlier는 되도록 피하면서
k개의 초기 center를 선정하는 방법이다.
참고 :
k-means++: The Advantages of Careful Seeding(David Arthur et al. 2007)
slides
예를 들면, 다음 그림과 같은 경우이다.
그래서, 이제 갖가지 초기 center 정하는 방법들이 등장하게 된다. 창시자들이 저렇게 빈틈을 남겨주어야 후배 연구자들이 먹구 살 거리가 생기게 된다. 암튼, 개선안 중에 하나가 그럼 되도록 center간의 간격을 멀게 멀게 만들자는 것이다. 위의 예를 계속 이용하면 아마 이렇게 될 것이다.
1 ~ 3이 초기 center로 선정된 instance들이다. 1번은 랜덤으로 선정된 것이고, 2번은 1번으로 부터 제일 먼 것, 3번은 1번, 2번으로 부터 가장 먼 것으로 선정된다. 이렇게 선정한 세개의 center를 가지고 클러스터링을 하면 창시자의 부족함을 매꾸며 성공적인 클러스터링을 달성함과 동시에 후배들에게 또다시 TODO list를 남겨준다. 즉, 이 방법 또한 큰 약점을 가지고 있는데, Outlier라는 넘을 만나면 여지 없이 무너지는 수가 있다.
이래서 등장한 것이 k-means++. k-means++는 다음 순서대로 하나씩 하나씩 1번 부터 k번째 center까지 정한다. 이게 개념은 참 간단한데, 글로 표현하는 것이 쉽지가 않다.
1. 1 번째 center는 랜덤으로 정한다.
2. for i = 2 ~ k
모든 인스턴스 x마다 아래의 확률을 부여한다.
p(x) = D(x)2/Σx'D(x')2 [x'는 인스턴스집합 X의 원소들]
여기서 D(x)는 x에서 지금까지의 center중 제일 가까운 center와의 거리를 뜻한다.
그러면, 모든 인스턴스에 확률이 부여된 이 상태에서 i 번째 center를 'random으로 찍는다'.
높은 확률이 부여되어 있다는 것은 i번째 center로 선정될 가능성이 높다는 뜻이다.
D(x)의 뜻이 핵심이다. center를 한개 한개 만들어 가는데, 지금까지 만들어진 center중에 제일 가까운 center와의 거리.2. for i = 2 ~ k
모든 인스턴스 x마다 아래의 확률을 부여한다.
p(x) = D(x)2/Σx'D(x')2 [x'는 인스턴스집합 X의 원소들]
여기서 D(x)는 x에서 지금까지의 center중 제일 가까운 center와의 거리를 뜻한다.
그러면, 모든 인스턴스에 확률이 부여된 이 상태에서 i 번째 center를 'random으로 찍는다'.
높은 확률이 부여되어 있다는 것은 i번째 center로 선정될 가능성이 높다는 뜻이다.
위 식의 분모는 모든 인스턴스 x의 D(x)2의 합이니까. 모든 x에 대해서 같고, 결국 분자인 D(x)2이 큰 게 확률이 높다. 그러면 결국 D(x)가 클수록 확률이 높다. 이 얘기는 지금까지 만들어진 center들과 멀 수록 확률이 높다는 건데, 그럼 결국 먼거를 찍는다는 얘기?? 그럼, 저 위에 거랑 똑같다? 그럴리가.
중요한 건, 확률을 저렇게 정해놓고, 랜덤으로 찍는다는 것이다. 그러니까, 거리가 먼 outlier는 물론 확률은 높다. 하지만, 거리가 가장 먼 놈을 무조건 선정하지는 않는다는 것이다. 무조건 먼거로 결정할 거면 그냥 D(x)만 구하지, 굳이 D(x)2 나누기 D(x')2의 합을 굳이 구하지는 않았겠지. 그림을 보면,
파란색이 1번째 center이고, 이제 2번째 center를 선정하려고 한다. 숫자는 인스턴스 마다 지금까지 center 중(지금은 파란 인스턴스 하나뿐) 제일 가까운 것과의 거리인 D(x)이다.
이제 인스턴스마다 확률을 부여해야 하는데, 분모 먼저 구하면 모든 D(x)2의 합이니까 12+52+52+52+82=140 이다. 그러면, 제일 가까운 인스턴스의 확률은 1/140, 빨간색 애들은 각각 25/140, 제일 먼 애는 64/140 의 확률을 받는다. 이런 확률를 놓고 랜덤으로 찍는다. 제일 먼 인스턴스의 확률(64/140)이 가장 높지만, 세개의 빨간 인스턴스 중의 하나가 될 확률(3 * 25/140)이 더 높다. 먼 것도 유리하지만, 몰려있는 것중 하나가 될 확률도 높다. 2제곱이라는 숫자는 거리를 확률에 반영하는 정도를 결정하는 factor라고 생각하면 되겠다.
요약 정리 : k-means++는 확률 기반으로,
1. center가 밀집되지 않게
2. outlier는 되도록 피하면서
k개의 초기 center를 선정하는 방법이다.
참고 :
k-means++: The Advantages of Careful Seeding(David Arthur et al. 2007)
slides
