.

그림, 실습코드 등 학습자료 출처 : https://datascienceschool.net

# K-Means 클러스터링 알고리즘

• 클러스터링하면 가장 대표적이고 가장 쉽고 가장 많이쓰이는 방법이 kmeans 클러스터링 알고리즘이다.

• 왜냐하면 사람이 직관적으로 이해하기 쉬운구조이기 때문이다. 목적함수는 다음과 같다.

\[\ J = \sum_{k=1}^K \sum_{i \in C_k} d(x_i, \mu_k)\] \[\ d(x_i, \mu_k) = || x_i - \mu_k ||^2\]

J값을 inertia라고 부른다.

• Ck는 k번째 클러스터에 속하는 데이터 집합을 말하는 것이고, d는 Xi와 뮤k 두 데이터 사이의 거리(유클리드 거리) 또는 비유사도이다.

• k는 k개라는 클러스터 개수를 의미하는 것이고, means는 평균들이 여러개 있다는 것이다. 이 평균을 클러스터의 중심값 또는 centroid라고 부른다. 그래서 중심값이라는 어떤 파라미터를 이용한다. 위의 식에서는 뮤로 표현하였다. 이 중심값이 k는 1부터 k개의 중심값이 존재하는 것이다 라고 가정하고 문제를 푼다.

• 내가 데이터를 보고 뮤를 두개로 나누겠다 그러면 이 데이터들에 대한 중심값이 두개가 있는 것이다. 그래서 우리가 원하는 것은 중심값들이 어디에 존재하냐를 알아야 하고 클러스터링 한다는 것은 어떤식으로 중심값을 기준으로해서 클러스터링을 할 것인가이다.

• 그래서 우리가 최종적으로 뽑고 싶은 것은 x1, x2, x3, x4, x5.. 데이터들을 클러스터링 번호를 매겨줘야 한다.

• 일단 뮤하고 뮤2를 정한다. 그리고 뮤를 중심으로 클러스터링을 구성한다. 이렇게 클러스터링을 구성하게하면 d라는 거리가 계산된다. d라는 거리를 계산할때 x하고 뮤하고 사이의 거리를 계산한다. 계산할때 같은 클러스터인 데이터들끼리만 중심에 얼마나 가까운지 계산을 한다. k번째 클러스터에서 각각의 멤버들과 중심점과의 결속관계를 나타낸다. 이 거리가 작으면 결속이 잘되어 있는 것이다. 이 연산과정을 k개의 클러스터 모두 다 해준다. 그래서 이 방법으로 구했을때 수치가 작으면 작을수록 좋은 것이다.

• 이게 잘 되려면 클러스터에 중심값의 위치가 좋은 위치에 있어야 하고, 각각의 데이터에 대해 특정 데이터가 어떤 클러스터에 있는지 라벨링해줄때 가장 근처에 있는 중심점으로 잘 라벨링 해줘야 한다.

• 다시말해 inertia가 가장 줄이도록 뮤값과 라벨값을 동시에 찾아내는 방법이다. 이것을 어떻게 찾아내냐 iterate roatating 방법을 보통 많이 쓴다.

1) 임의의 중심값 뮤를 고른다. 보통 데이터 샘플중에서 K개를 선택한다.

2) 중심값에서 각 데이터까지의 거리를 계산한다.

3) 각 데이터에서 가장 가까운 중심을 계산했을때 더 가까운 중심점이 있다면 클러스터 소속을 갱신해준다.

4) 다시 만들어진 클러스터에 대해 중심을 다시 계산하고(보통 평균으로 계산) 1 ~ 4를 반복한다.

• scikit-learn의 cluster 서브패키지는 KMeans 클래스를 제공한다. 데이터가 큰 것을 대비하여 사용자는 max_iter를 조절할 수 있다. 클러스터링이 몇번 돌다가 멈춰라 라는 의미이다.

• 이 kmean를 여러가지로 변형을 시킬 수 있는데 가장 간단한 방법은 distance를 정할때 다른 distance 척도를 넣어주면 클러스터링 결과가 달라질 수 있다. 예를 들어서 유클리드 거리 대신에 코싸인 거리를 넣어도 된다.

• 또 다른 변형방법은 중심점을 업데이트 할때 평균을 활용했는데 평균을 안쓰는 방법도 있다. 데이터 집합의 대푯값을 구하는 방법 중 중앙값을 활용할 수 있다. 중앙값을 쓰게 되는 경우에는 아웃라이어에 대한 영향이 적어지는 장점이 있다. 이 중앙값을 활용하는 방법이 케이미노이드 방법이다.

• 다시말해 케이센트로이드 방법안에 케이민즈와 에키미노이드 두개가 있다.

• mini-batch k-means라는 것도 있다. 데이터가 엄청나게 많아지게 되면 중심값과 데이터 간의 거리를 일일히 다 측정해야 하니까 메모리에 데이터 자체가 못올라가는 현상이 발생한다. 이럴때 쓰는 방법이다. 핵심은 데이터가 너무 많으면 데이터를 일부만 쓰게 된다. 그래서 원래 kmeans를 썼을때보다 오차가 발생할 가능성이 있다.

• kmeans는 predict 메서드가 있다. 클러스터 알고리즘 중에서 predict메서드가 존재하는 것도 있고 없는것도 있다. 왜냐하면 알고리즘에 따라서는 트레이닝 테스트를 나눠서 할 수 있기 때문이다. 예를 들어서 kmeans는 train test를 나누어서 할 수 있다. train 데이터가 있으면 이걸 갖고 뮤값을 구할 수 있다. 이 정보를 잘 저장하면 train 데이터 다 버려도 test 데이터가 들어와도 클러스터링을 할 수 있다. 이런게 가능하면 predict 메서들 갖고 있다.

# K-Means++ 클러스터링 알고리즘

• 맨처음에 임이의 중심값을 구할때 아무렇게나 하지말고, 잘 구해보자라는 취지이다. 처음에 지정을 잘 하면 뒤에 계산양을 줄일 수 있기 때문이다.

• 최초의 중심값을 구하는 방법이고 나머지는 kmeans와 똑같은 방법이다.

• kmeans에서는 중심값을 기존의 데이터 중에서 k개를 뽑는 것인데 중심값이 한쪽에 쏠려 있으면 안된다. 아예 처음부터 이 중심값들을 가능하면 멀리 떨어뜨리는 것이다. 그렇다고 중심값을 가장자리에 넣자는 의미는 아니다.

• 첫번째 뮤1을 임의로 지정한다. 그다음에 데이터들을 카테고리 분포로 만들어서 뮤1에서 멀리 떨어진 얘들은 확률이 커지고 가까운 얘들은 확률이 낮아지도록 카테고리 분포로 만든다. 그리고 주사위를 던져서 나오는 위치를 두번째 중심값 뮤2로 지정한다. 뮤3는 뮤1과 뮤2와 멀리 떨어져 있어야 한다. 뮤3는 뮤1, 뮤2 집합과 특정 나머지 데이터들간에 거리는 집합안에서 특정 나머지 데이터간에 가장 짧은 거리에 있는 데이터와 거리를 측정한다. 이를 용어로 싱글링크라고 한다.

• 이렇게 하면 미리 만들어진 중심값 집합과 다른 모든 포인트간에 거리가 모두 측정이 된다. 그 다음에 다시 거리에 비례하게 주사위를 만든 다음에 주사위를 던진다. 그러면 또 하나가 선택이 될 것이다. 이런 방식으로 k개의 중심값이 정해질때까지 해준다.

• 중요한 포인트는 집합과 데이터의 거리를 어떻게 정의하냐인데 각각의 집합에 속하는 각각의 데이터 거리를 다 측정한다음에 그 중에 가장 짧은 거리로 집합과 데이터의 거리를 정한다는 것이다.

• 이 방법은 랜덤하게 주사위를 돌리는 것이기 때문에 시드값이 영향을 주게된다.