Search
🤖

[ML] k-means++란?

먼저 기존 k-means에서 Centroid를 초기화를 하는 방법 복습하자면 아래와 같다.
1.
Cluster별 Centroid가 주어진 경우
a.
각 sample에 가장 가까운 centroid의 cluster를 할당하면 된다.
2.
sample별 label이 주어진 경우
a.
각 cluster에 속한 sample의 평균을 계산하여 모든 centroid를 구한다.
3.
1과 2에 속하지 않는 경우
a.
random(무작위 초기화)
i.
Centroid를 랜덤하게 선정한다.(e.g. 무작위로 kk개의 샘플을 뽑아 그 위치를 Centroid로 선정한다.)
ii.
Sample에 label을 할당하고, Centroid를 업데이트하는 것을 반복하여 수행한다.
iii.
더 이상의 변화가 없을 때 동작을 멈춘다.
b.
k-means++
i.
첫 번째 Centroid를 무작위로 선택한다.
ii.
나머지 Centroid를 선택할 때, 이미 선택된 Centroid들과의 거리가 멀 수록 우선적으로 선택한다.(거리 비례 확률)

왜 k-means++ 알고리즘을 사용하게 되었을까?

•
기존 random init 방식은 centroid를 랜덤하게 위치시키기 때문에, 결과가 매번 달라질 수 있다.
•
또한 한 번에 k개의 centroid를 랜덤하게 생성하기 때문에, k개의 centroid들 사이 거리가 짧으면 분류가 잘 안될 수 있다.
•
구체적인 이미지 자료는 아래 참고
[인공지능][개념] K-Means 알고리즘의 문제점과 'K-Means++ 클러스터링'을 통해 개선하기
K-평균(K-Means)에 대한 이론이 필요하신 분들은 아래 링크를 참조해주시기 바랍니다. [인공지능][개념] K-평균(K-means) 알고리즘과 군집화(Clustering) + 이너셔(Inertia) 이해하기 : https://itstory1592.tistory.com/17 [인공지능][실습] K-평균(K-Means) 알고리즘으로 과일(fruits) 사진을 분류해보고 엘보우(Elbow) 방법을 통해 최적의 k값을 찾아보자 : https://itstory1592.tistory.com/18 이번 포스팅에서는 지난 시간에 이어 K-Means++ 알고리즘에 대해 알아보도록 하자! K-Means++ 알고리즘은 기존 K-Means 알고리즘을 개선한 분류 알고리즘이다. 그런데 왜 K-Means++ 알고리즘이 생겨나..
https://itstory1592.tistory.com/19
•
상세 과정
1.
중심위치를 저장할 집합 MM 준비
2.
일단 하나의 중심위치 μ0\mu_0를 랜덤하게 선택하여 MM에 넣는다.
3.
MM에 속하지 않는 모든 표본 xix_i에 대해 거리 d(M,xi)d(M,x_i)를 계산. d(M,xi)d(M,x_i)는 MM안의 모든 샘플 μk\mu_k에 대해 d(μk,xi)d(\mu_k,x_i)를 계산하여 가장 작은 값 선택
4.
d(M,xi)d(M,x_i)에 비례한 확률로 다음 중심위치 μ\mu를 선택.
5.
KK개의 중심위치를 선택할 때까지 반복
6.
K-means 방법 사용
•
기존 random init에 비해 장점?
◦
기존 random 방식보다 더 최적화된 centroid init을 할 수 있다.
◦
기존 random 방식에 비해 알고리즘이 수렴하는 속도가 빠르다.
▪
random에서는 운이 나쁘면 초기 centroid가 잘못 지정되어 수렴하는데 오랜 시간이 걸릴 수 있다.
•
Reference
hleecaster.com
https://hleecaster.com/k-means-clustering-concept/
fin