K-means Clustering

이번 시간에는 K-means Clustering에 대해서 알아보고자합니다.

 

이에 앞서 먼저 Clustering에 대한 이해가 필요하기 때문에 간략하게 소개하겠습니다.

 

Clustering(군집분석) 이란?

개체를 분류하기 위한 명확한 분류기준이 존재하지 않거나 기준이 밝혀지지 않은 상태에서 주어진 데이터의 특성을 고려하여 같은 그룹(클러스터)을 정의하고 다른 그룹의 개체보다 서로 더 유사한 개체가 되도록 그룹화하여 그룹의 대표성을 찾아내는 방법입니다.

 

* 그룹(클러스터) : 비슷한 특성을 가진 데이터들의 집합

 

군집분석은 유사한 성향을 가진 개체를 모아 군집을 형성하여 군집간의 특성을 관찰하거나 목표변수와의 관계를 파악하기 위한 목적이 있습니다. 예측성 분석이 아니기 때문에 주로 분석 초기 단계에서 데이터의 특성을 파악하기 위해서 활용됩니다.

 

 

군집분석의 원리

• 군집 내 응집도 최대화 : 같은 군집 내 객체들의 거리를 최소화 하는 것
• 군집 내 분리도 최대화 : 다른 군집 간 거리를 최대화하는 것

 

 

Cluster의 기준

 

Cluster를 어떻게 군집화 할 것인지에 대한 기준은 보통 "거리"를 이용합니다.

 

거리 척도 유형에는 두가지가 존재합니다.

 

1. 유클리디안 거리(Euclidean Distance)

 

2. 맨하탄 거리(Manhattan Distance)

 

 

군집분석의 유형

 

1. 분리형(비계층형) 군집화(Partitioning Clustering) : 사전에 군집 수를 정해주어 대상들이 군집에 할당되도록 하는 것 

• 중심 기반(Center-based clustering) : 프로토타입 기반(Prototype-based)이라고도 하며, "동일한 군집에 속하는 데이터는 어떠한 중심을 기준으로 분포할 것이다."라는 가정을 기반으로 합니다. 대표적으로 K-means algorithm이 있습니다.
• 밀도 기반(Density-based clustering) : "동일한 군집에 속하는 데이터는 서로 근접하게 분포할 것이다."라는 가정을 기반으로 합니다. 대표적으로 DBSCAN algorithm이 있습니다.

2. 계층적 군집화(Hierarchical Clustering) : 각 객체가 n개(객체의 수)의 독립적인 각각의 군집에서 출발하여 점차 거리가 가까운 대상과 군집을 이루어 가는 것

대표적으로 H-Clustering algorithm이 있습니다.

그럼이제 중심기반 분리형 군집화의 대표적인 알고리즘인 K-means에 대해서 알아보겠습니다.

 

 

K-means clustering algorithm

 

주어진 데이터 k개를 클러스터로 묶는 알고리즘으로 각 클러스터와 거리 차이의 분산을 최소화하는 방식으로 동작합니다. 또한 자율 학습의 일종으로, 레이블이 달려 있지 않은 입력 데이터에 레이블을 달아주는 역할을 수행합니다.

 

K-means는 n개의 데이터 오브젝트를 입력받았다고 가정할 때, 입력 데이터를 n보다 작거나 같은 k개의 그룹으로 나누는데 이 때 각 그룹은 클러스터를 형성하게 됩니다. 즉, 데이터를 한 개 이상의 데이터 오브젝트로 구성된 k개의 그룹으로 나누는 것입니다.

 

그룹을 나누는 과정은 거리 기반의 그룹 간 비유사도(dissimilarity)와 같은 비용 함수를 최소화하는 방식으로 이루어지며, 이 과정에서 같은 그룹 내 데이터 오브젝트끼리의 유사도는 증가하고, 다른 그룹에 있는 데이터 오브젝트와의 유사도는 감소하게 됩니다.

 

K-means는 각 그룹의 중심(Centroid)과 그룹 내의 데이터 오브젝트와의 거리의 제곱합을 비용 함수로 정하고, 이 함수값을 최소화하는 방향으로 각 데이터 오브젝트의 소속 그룹을 업데이트 해 줌으로써 클러스터링을 수행하게 됩니다.

 

 

K-means clustering의 프로세스

 

1. 얼마나 많은 클러스터가 필요한지 결정(K 결정)

 

2. 초기 중심(Centroid) 선택

 

3. 모든 데이터를 순회하며 각 데이터마다 가장 가까운 Centroid가 속해있는 클러스터로 배치

 

4. Centroid를 클러스터의 중심으로 이동

 

5. 클러스터에 배치되는 데이터가 없을 때까지 3, 4를 반복

 

 

초기 중심 선택(초기화 기법) 방법

 

- 무작위 분할(Random partition)

무작위 분할 알고리즘은 가장 많이 쓰이는 초기화 기법으로 각 데이터들을 임의의 클러스터에 배당한 후, 각 클러스터에 배당된 점들의 평균 값을 초기로 설정하는 방법입니다. 무작위 분할은 다른 방법과 달리 데이터 순서에 독립적입니다. 또한 초기 클러스터가 각 데이터들에 대해 고르게 분포되기 때문에 각 초기 클러스터의 무게 중심들이 데이터 집합의 중심에 가깝게 위치하는 경향을 띕니다.

 

- Forgy

Forgy 알고리즘은 1965년 Forgy에 의해 고안되었으며 데이터 집합으로부터 임의의 k개의 데이터를 선택하여 각 클러스터의 초기로 선택합니다. 무작위 분할과 마찬가지로 데이터 순서에 대해 독립적입니다. 또한 초기 클러스터가 임의의 k개의 점들에 의해 설정되기 때문에 각 클러스터의 무게중심이 중심으로부터 퍼져있는 경향을 띕니다.

 

- MacQueen

1967년 MacQueen에 의해 고안된 MacQueen 알고리즘은 Forgy 알고리즘과 마찬가지로 데이터 집합으로부터 임의의 k개의 데이터를 선택하여 각 클러스터의 초기로 선택합니다. 이후 선택되지 않은 각 데이터들에 대해, 해당 점으로부터 가장 가까운 클러스터를 찾아 데이터를 배당합니다. 모든 데이터들이 클러스터에 배당되고 나면 각 클러스터의 무게중심을 다시 계산하여 초기로 설정합니다. MacQueen 알고리즘의 경우 최종 수렴에 가까운 클러스터를 찾는 것은 비교적으로 빠르지만 최종 수렴에 해당하는 클러스터를 찾는 것은 매우 느린 단점을 가집니다.

 

- Kaufman

1990년에 Kaufman과 Rousseeuw에 의해 고안된 Kaufman 알고리즘은 전체 데이터 집합 중 가장 중심에 위치한 데이터를 초기로 설정합니다. 이후 선택되지 않은 각 데이터들에 대해 가장 가까운 무게중심보다 선택되지 않은 데이터 집합에 더 근접하게 위치한 데이터를 또 다른 초기로 설정하는 것을 총 k개의 초기로 설정될 때까지 반복합니다. 무작위 분할과 마찬가지로 데이터의 순서에 독립적입니다.

 

 

K-means 단점

 

K-means clustering은 local minimum이 발생할 수 있다는 단점이 있습니다.

아래 데이터를 두 개의 클러스터 나누면 어떻게 될까요?

 

왼쪽과 오른쪽의 클러스터로 각각 나누어주면 됩니다. 하지만 초기에 설정된 Centroid가 아래와 같다면 클러스터를 위, 아래로 나눌 것입니다.

 

위쪽 6개 점은 위쪽 Centroid와 가장 가깝고, 아래쪽 6개 점은 아래쪽 Centroid와 가깝기 때문에 이대로 iteration이 끝나버립니다. 이런 현상을 local minimum이라고 합니다. 하지만 centroid 위치를 양 옆으로 조금만 움직여도 클러스터는 우리가 원하는 대로 오른쪽, 왼쪽으로 바뀔 것입니다. 

 

 

K-means clustering은 처음 소개된지 거의 반세기 지난 알고리즘이지만, 여전히 머신러닝에 가장 널리 활용되는 클러스터링 알고리즘 중에 하나입니다.

 

K-means clustering의 가장 큰 단점은 처음에 지정하는 중심점(Centroid)의 위치를 무작위로 결정하기 때문에 최적의 클러스터로 묶어주는 한계가 있다는 것입니다.

 

때문에 K-means의 새로운 버전이라고 할 수 있는 K-means++ 알고리즘이 등장하였습니다. 즉, 기존 K-means의 중심점 무작위 선정의 문제를 해결하기 위해 생겨난 것이라고 보면 됩니다.

 

 

K-means++ 프로세스

 

1. 아무 공간에 중심점 k개를 찍고 시작하는 것이 아니라 가지고 있는 데이터 포인트 중에서 무작위로 1개를 선택하여 첫번째 중심점으로 지정합니다.

 

2. 나머지 데이터들에 대해 첫번째 중심점까지의 거리를 계산합니다.

 

3. 두번쨰 중심점은 각 점들로부터 거리비례 확률에 따라 선택합니다. 즉, 이미 지정된 중심적으로부터 최대한 먼 곳에 배치된 데이터를 그 다음 중심점으로 지정하는 것입니다.

 

4. 중심점이 k개가 될 때까지 2, 3번을 반복합니다.

 

 

K-means++ 장점

 

• 초기 중심점을 더욱 전략적으로 배치하기 때문에 전통적인 K-means보다 더 최적의 군집화를 할 수 있습니다.
• K-means보다 알고리즘이 수렴하는 속도가 더 빠릅니다. 이는 전통적인 K-means를 사용할 시 초기 중심점이 재수없게 잘못 지정되는 경우 알고리즘이 수렴하는데 오래 걸릴 수 있기 때문입니다.

 

 

코드 실습

 

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
%matplotlib inline

X= -2 * np.random.rand(100,2)
X1 = 1 + 2 * np.random.rand(50,2)
X[50:100, :] = X1
plt.scatter(X[ : , 0], X[ :, 1], s = 50, c = 'b')
plt.show()

 

위의 데이터는 2개의 클러스터로 구분할 수 있다는 것을 쉽게 알 수 있습니다.

 

from sklearn.cluster import KMeans
Kmean = KMeans(n_clusters=2)
Kmean.fit(X)

클러스터를 2개로 할 것이기 때문에 n_clusters 파라미터를 2로 줬습니다. fit을 해주면 아래와 같은 결과가 나옵니다.

 

KMeans(algorithm='auto', copy_x=True, init='k-means++', max_iter=300,
         n_clusters=2, n_init=10, n_jobs=None, precompute_distances='auto',
         random_state=None, tol=0.0001, verbose=0)

init 파라미터의 default 값은 k-mean++입니다. 

max_iter=300으로 되어있습니다. 웬만하면 스텝 2~3의 iteration이 300번 이전에 끝나기 때문에 default가 300입니다.

 

Kmean.cluster_centers_

>>> array([[ 2.02664296,  1.88206121],
          [-1.01085055, -1.03792754]])

 

두 centroid의 위치입니다. 두 centroid와 함께 plot을 그려보겠습니다.

 

plt.scatter(X[ : , 0], X[ : , 1], s =50, c='b')
plt.scatter(-0.94665068, -0.97138368, s=200, c='g', marker='s')
plt.scatter(2.01559419, 2.02597093, s=200, c='r', marker='s')
plt.show()

 

 

참고 :

군집분석이란

군집분석이란? (What is clustering algorithm?)

K-평균 클러스터링

머신러닝 - 7. K-평균 클러스터링(K-means Clustering)

위키백과

k-평균 알고리즘 - 위키백과, 우리 모두의 백과사전

K-means++

K-Means++ 클러스터링 쉽게 이해하기 - 아무튼 워라밸

k-means clustering

[인공지능][개념] K-Means 알고리즘의 문제점과 'K-Means++ 클러스터링'을 통해 개선하기