2009/04/26 01:26
if (IR or NLP)
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
댓글을 달아 주세요
제일 먼 인스턴스의 확률(64/176)이 가장 높지만, -> 제일 먼 인스턴스의 확률(64/140)이 가장 높지만, ??
그리고, 인스턴스 밀집도를 표현하는 '3'을 곱해주는 것은 위 식에 안나와 있잖아요. T.T
숫자 오타는 수정했어.
식은 인스턴스 하나가 선택될 확률이고,
빨간 인스턴스 3개중에 하나가 선택될 확률이니까 곱하기 3.
열심히 읽어줘서 감사.
음.. 궁금한 점이 있는데요 두번째 센터까지는 저렇게 구한다지만 세번째 센터를 구할때 거리에 관해서 이미 정해진 두 센터중 어떤 센터를 기준으로 확률을 계산해야 하나요? 점들별로 가까운 센터가 다 틀릴텐데.. 이부분이 이해가 안되요 ㅡ.ㅜ
알고리즘 설명 박스에 보면
"여기서 D(x)는 x에서 지금까지의 center중 제일 가까운 center와의 거리를 뜻한다." 라는 말이 있습니다.
3번째 센터를 구기 위해 D(x)를 계산할 때는 1, 2번째 센터중 가까운 센터와의 거리를 구하고, 4번째 센터를 구할 차례라면 1, 2, 3 번째 센터중 가중 가까운 센터와의 거리를 구하고...
이런식으로 진행됩니다.
음..분자의 D(x)는 해당 인스턴스에서 가장 가까운 정해진 센터의 거리가 되는것으로 이해하는게 맞는건가요 ㅡ.ㅜ
^^; 그리고 또있는데요 분모의 sum D(x') 는 무조건 첫번째 센터에서 모든 인스턴스로의 거리의 합이되는건가요?
참 어려운거같아요 ㅡ.ㅜ
첫번째 질문의 답은 '예'이구요.
두번째 질문의 답은
인스턴스 각각 마다 가장 가까운 센터를 다르게 선정하는 것이 맞습니다.
감사합니다 ^^ 많은 도움이 되었어요~
좋은글 감사합니다. 그런데 글을 읽던중 궁금한점이 있어서 글을 남깁니다.
위의 내용을 요약하자면 영상의 모든점의 확률(D(x))를 랜덤으로 뽑아서 seed로 뽑힐 확률을 높인다는 개념인거 같은데..
그렇다면 굳이 분모(D(x'))가 필요한 이유가 있는지 궁금합니다.
분모 값으로 정규화를 해주지 않아도,, 랜덤으로 뽑기에 필요한 값의 분포는 D(x)가 충분히 가지고 있는게 아닌가 궁금합니다. 분모를 사용하지 않을경우에 다른점이 있는지요...
좋은 포스팅 잘 읽었습니다.
k-means에 대해 공부하다가 k-means++이 있는것도 알게 되었네요.
말씀하신대로라면 k-means++에서 다음 center를 구하기위해 선택하는 방법은
Genetic algorithm의 Roulette wheel selection과 거의 흡사하다고 생각되는군요.. 맞는지요 ??
잘 보고 갑니다 :)