참고:
https://ratsgo.github.io/machine%20learning/2017/04/19/KC/
https://ko.wikipedia.org/wiki/K-%ED%8F%89%EA%B7%A0_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
클러스터링 알고리즘은 유사도를 적용해 비슷한 정보를 가진 관측값이나 정보를 식별한다. 여러 개의 데이터를 하나의 클러스트에 할당해, 특성을 한 눈에 알 수 있다. 알고리즘마다 생성 과정과, 유사한 팩터에 따라 다른 알고리즘을 사용한다.
k-means clustering : 가장 대표적인 알고리즘. k라는 하이퍼파라미터를 이용한다. k개의 군집을 만드는 것이 목표이며, EM알고리즘을 기반으로(expectation & maximization) 작동한다.
1. k개의 중심점을 랜덤하게 잡는다.
2. k개의 중심점중, 가장 가까운 것들을(즉 cost function이 최소인 것을) 하나의 그룹으로 묶는다. 가장 기초 함수는 거리의 제곱값이다.
3. 각 그룹을 이용해, 중심점을 그룹의 무게중심으로 갱신한다.
4. 수렴할 때까지, 혹은 정해진 횟수까지 2~3을 반복한다.
알고리즘의 목적은 전체의 비용함수를 최소화하는 것인데, 이는 np-hard문제라고 한다. 따라서, global minimum대신 local minimum을 찾는 것으로 종료하게 된다.
장점은 연산이 무척 간단하다는 것이다. iterating횟수를 정해줄 수 있으므로, 알고리즘의 복잡성은 O(n)에 그친다.
단점은 꽤 많은데, 1) 중심 값에 따라 결과가 매우 다르다. 2) 실제 클러스터의 크기나 밀도가 다르다면 제대로 작동하지 않는다. 3) 구형이 아닌 클러스터를 찾는 데에 적합하지 않다. 4) outlier에 민감하다 5)k의 값에 따라 결과가 매우 달라진다.
단점에 대한 보완으로 실제 문제를 풀 때는 majority voting이라는 방법으로 가장 여러분 등장하는 군집에 할당시킨다고 한다.
기법:
1. 무작위 분할(lloyd): 각 데이터를 임의의 클러스트에 배당한 뒤, 그 평균 값을 중심으로
2. Forgy 알고리즘: 초기점을 잡을 때 임의의 k개의 점을 선택. 이로 인해 전체 무게 중심에서 좀 퍼지는 경향
3. MacQueen : forgy와 같지만, 점들을 모두 할당한 뒤 중점을 다시 계산해 초기 중심점으로 설정
4. Kaufman: 전체 중심에 가장 가까운 데이터를 첫 점으로 설정. 이후 각 데이터에 대해, 가장 가까운 무게중심 보다 선택되지 않은 데이터 집합에 더 근접하게 위치한 것을 그 다음으로 설정, 이를 반복한다. 랜덤성에 의존하지 않으므로, 성능면에서 월등한 면을 보인다.
복잡도는 O(nkdi)라고 한다. 유클리드 공간 차원수 d, 클러스터 , 데이터n, 반복횟수 i이며, n이 보통 나머지보다 압도적으로 많으므로 O(n)이 된다.
k를 정하는 방법 중에, rule of thumb은 sqrt(n/2)개를 쓰는 것.
elbow method는 k를 늘려가다가 결과가 좋아지지 않으면 더이상 늘리지 않는 것이다.
평가 지표는 아직 봐도 모르겠어서 생략했다.
