[AI] k-평균 알고리즘

들어가며

오늘은 비지도 학습에 해당하는 군집 알고리즘을 사용하는 k-평균에 대해 알아볼 것이다

분류와 군집에 대한 개념은 많이 헷갈려 하는 개념이다

간단히 설명하자면 분류는 레이블이 있는 지도 학습이고

군집은 레이블이 없이 훈련시키는 비지도 학습이다

 

군집 알고리즘은 비슷한 샘플들을 클러스터라고 부르는 그룹으로 모으고

샘플이 들어왔을 때 샘플의 특성을 보고 하나의 클러스터에 할당하도록 동작한다

아래에서 유명한 군집 알고리즘인 k-평균과 DBSCAN 중 우선 k-평균에 대해 알아볼 것이다

 

K-평균

k-평균 알고리즘은 우선 각 클러스터의 중심을 세팅하고

샘플이 들어오면 그 중심에 가장 가까운 클러스터로 샘플을 할당하는 방식으로 동작한다

 

사이킷런에서 KMeans() 클래스를 통해 k-평균을 사용할 수 있다

kmeans = KMeans(n_clusters=k, n_init=10, random_state=42)
y_pred = kmeans.fit_predict(X)

우선 알고리즘이 찾을 클러스터의 개수 k를 지정해야한다

k값은 당연하게도 그냥 랜덤으로 지정하면 안되고

최적의 클러스터 개수를 찾아야하는데 그 방법은 조금 뒤에서 설명하도록하겠다

 

k-평균에서 각 샘플의 레이블은 샘플에 할당된 클러스터의 인덱스를 의미한다

y_pred
array([4, 0, 1, ..., 2, 1, 0], dtype=int32)

 

알고리즘이 찾은 클러스터의 중심도 확인 할 수 있다

kmeans.cluster_centers_
array([[-2.80389616,  1.80117999],
       [ 0.20876306,  2.25551336],
       [-2.79290307,  2.79641063],
       [-1.46679593,  2.28585348],
       [-2.80037642,  1.30082566]])

생성된 정보들을 통해 보로노이 다이어그램으로 결정 경계를 표현하면 아래와 같다

샘플들이 적절한 클러스터에 잘 할당된 모습이다

일부는 잘못 할당되었을 수 있는데 샘플이 클러스터에 할당될 때 고려되는 것이

중심과의 거리 뿐이기 때문에 그럴것이다

 

k-평균 알고리즘 작동방식

k-평균 알고리즘이 어떻게 샘플을 클러스터에 분류하는 지 그 학습과정에 대해 알아볼 것이다

큰 틀로 본다면 센트로이드(클러스터 중심)이 주어지고 샘플이 주어졌을 때

클러스터의 중심과의 거리가 가장 가까운 곳으로 할당된다

 

하지만 모든 데이터에서 처음부터 센트로이드가 주어지지는 않는다

그렇다면 센트로이드는 어떻게 설정되는 것일까?

 

우선 센트로이드는 처음에 랜덤으로 k개의 샘플을 뽑아서 결정된다

그리고 모든 샘플들에 레이블을 할당시키고 센트로이드를 업데이트 한다

이 때 업데이트는 클러스터에 속한 샘플들의 평균으로 계산하여 업데이트된다

그리고 다시 레이블을 할당하고 센트로이드를 업데이트하는 과정을 반복하며

센트로이드에 변화가 없을 때까지 계속한다

이 과정을 아래 그림으로 확인해보겠다

왼쪽 열은 센트로이드를 업데이트 하는 부분이고

오른쪽 열은 업데이트된 센트로이드를 기반으로 레이블을 할당시키는 모습이다

 

하지만 센트로이드를 처음 초기화 시 랜덤으로 뽑기때문에

운에 기반하고 최적이 아닌 예측을 내놓게 될 수 있다는 문제가 있다

위 두 그래프 모두 초기화 운이 없을 때 알고리즘이 어떻게 수렴되는지를 보여준다

센트로이드 초기화 방법

그래서 센트로이드를 적절하게 초기화하기 위해서는 

랜덤 초기화를 여러 번 실행하여 가장 좋은 솔루션을 선택한다

랜덤 초기화 횟수는 n_init 매개변수를 통해 조절하고 기본값은 10이다

 

만약 센트로이드의 위치를 근사하게라도 알고 있다면

n_init의 값을 1로 설정하고 센트로이드 리스트를 담은 넘파이 배열을 만들면 된다

good_init = np.array([[-3, 3], [-3, 2], [-3, 1], [-1, 2], [0, 2]])
kmeans = KMeans(n_clusters=5, init=good_init, n_init=1, random_state=42)
kmeans.fit(X)

 

그렇다면 가장 좋은 솔루션이라는 것은 무엇을 기준으로 할까?

여기서는 이너셔라고 부르는 지표를 사용한다

이너셔는 각 샘플과 가장 가까운 센트로이드 사이의 제곱 거리 합으로

알고리즘은 이너셔가 가장 낮은 모델로 반환한다

inertia_ 인스턴스 변수로 모델의 이너셔 값을 확인할 수 있다

kmeans.inertia_
211.5985372581684

이 이너셔는 가장 위의 그래프의 이너셔이고

그 밑에 초기화 운이 없을 때의 그래프 중 왼쪽은 219.4, 오른쪽은 258.6으로 더 큰 편이다

최적의 클러스터 개수 찾기

일반적으로 데이터를 다룰 때 클러스터를 몇개로 설정할 지 쉽게 판단하기가 어렵다

클러스터를 너무 작게 설정하면 별개의 클러스터가 합쳐지게 되고

너무 크게 설정하면 하나의 클러스터가 여러개로 나뉘게된다

 

위에서 봤었던 지표인 이너셔가 가장 작은 모델로 설정하면 될거라고 생각하지만

그렇게 간단한 것은 아니다

이너셔는 k(클러스터 개수)값이 증가함에 따라 작아지는 경향을 보이므로

무조건 k값을 크게 잡는 것이 유리하다고 생각할 수 있지만

클러스터가 늘어날수록 샘플은 가까운 센트로이드에 더 가까워지는 것은 당연한 것이므로

k값을 무작정 크게 설정해서는 안된다

 

그렇다면 어떻게 해야할까?

그래프를 보면 팔꿈치(엘보)처럼 보이는 굴곡 지점이 보일 것이다

만약 k에 대한 정보가 없다면 엘보 지점을 k값으로 설정하는 것이 좋은 선택이 될 수 있다

엘보지점보다 작은 값은 이너셔 변화가 심하고

큰 값은 이너셔 차이가 별로 없으므로 값이 커져봤자 크게 도움이 되지 않는다

 

또 다른 방법으로는 실루엣 점수를 확인하는 방법이 있다

실루엣 점수는 모든 샘플에 대한 실루엣 계수의 평균값이다

실루엣 계수는 (b-a)/max(a,b)로 계산되며

a는 동일한 클러스터에 있는 다른 샘플들과의 평균 거리이고

b는 가장 가까운 클러스터 안의 샘플들과의 평균 거리이다

실루엣 계수는 -1 ~ +1 범위에서 나오며 +1에 가까울수록 자신의 클러스터 안에 잘 속했다는 것이고

-1에 가까울수록 샘플이 잘못된 클러스터에 할당됐을 수 있다는 것을 의미한다

실루엣 점수를 계산하기 위해서는 silhouette_score()를 사용한다

silhouette_score(X, kmeans.labels_)
0.655517642572828

클러스터 개수에 따른 실루엣 점수를 나타낸 그래프이다

k=4일 때 실루엣 점수가 가장 크므로 k값으로 4를 선택하는 것이 좋은 선택일 수 있다

하지만 아래 정보를 통해 추가적으로 고려한 후 더 확실하게 결정해야한다

 

위 그림은 실루엣 다이어그램이라고 부르는 것으로

각 그래프에서 세로축은 클러스터를 의미하고 가로축은 실루엣 계수를 의미한다

각 클러스터에서 높이는 클러스터가 포함하는 샘플의 개수를 의미한다

수직 파선은 평균 실루엣 점수를 나타내고 한 클러스터의 샘플의 실루엣 계수가 이 파선보다 낮으면

잘못된 클러스터라고 판단할 수 있다 k=3,6일 때가 이에 해당한다

 

k값을 4 또는 5로 선택하면 되는데 4일 때 인덱스 1의 클러스터의 샘플이 매우 많은 것을 볼 수 있다

반면 k=5일 때 클러스터의 크기는 다 비슷하다

그러므로 k=4일 때 실루엣 점수가 k=5일 때보다 조금 높더라도 비슷한 크기의 클러스터를 얻을 수 있는

k=5로 선택하는 것이 옳은 판단이 된다

k-평균의 한계

k-평균 알고리즘은 속도가 빠르고 확장이 용이하다는 장점이 있지만

최적이 아닌 솔루션을 피하기 위해서는 여러번 알고리즘을 실행해야 하며

적절한 클러스터 개수를 지정해야한다 이 과정은 꽤나 번거로울 수 있다

또한 클러스터의 샘플들의 크기나 밀집도가 서로 다르거나 클러스터의 형태가 원형이 아닐 경우 잘 작동하지 않는다

위 그림은 크기와 밀집도가 서로 다른 3개의 타원형 클러스터를 가진 데이터셋에 k-평균 알고리즘을 작동시킨 모습이다

왼쪽 솔루션이 오른쪽보다 그나마 낫지만 가운데 클러스터의 오른쪽 끝부분이 오른쪽 클러스터로 할당되었다

오른쪽 솔루션은 이너셔가 왼쪽보다 더 작긴하지만 클러스터 구분이 전혀 안된 모습이다

이런 타원형 데이터셋에서는 가우스 혼합 모델이 잘 작동된다고 한다

가우스 혼합 모델에 대해서는 다음번 글에서 알아보겠다

 

마치며

이번 글에서는 군집 알고리즘들 중 k-평균에 대하여 공부해봤다

알고리즘 동작 과정만 보았을 때는 되게 간단한 작업이라고 생각했지만

클러스터 개수나 초기화 방식 등 내부적으로 설정해야할 것들이 많고 번거로운 것들이 숨어 있었다

타원형 데이터는 k-평균에서는 잘 동작하지 않고 가우스 혼합 모델에서 동작하는 것처럼

데이터 크기나 형태에 따라서 잘 수행될 수 있는 군집 알고리즘을 잘 선택해야 할 것 같다고 느꼈다

다음 글에서는 다른 군집 알고리즘인 DBSCAN에 대해 알아볼 것이다