[scikit-learn 라이브러리] KMeans (K-Means)

K - 평균 (K - means)

• 구현이 쉽고, 다른 군집 알고리즘에 비해 효율이 좋아 인기가 많은 알고리즘이다.
• 학계와 산업현장 모두에서 활용된다.
• 프로토 타입 기반 군집(각 클러스터가 하나의 프로토타입으로 표현됨)에 속한다.
• 프로토 타입 : 연속적 특성에서는 비슷한 데이터 포인트의 centroid(평균) / 범주형 특성에서는 medopid(가장 자주 등장하는 포인트)
• 몇개의 군집을 설정할 것인지 정해야한다는 다소 주관적인 사람의 판단이 개입된다. (K값 결정)

---

K - 평균의 과정

• 1) 데이터 포인터에서 랜덤하게 k개의 센트로이드를 초기 클러스터 중심으로 선택한다.
• 2) 각 데이터를 가장 가까운 센트로이드에 할당한다.
• 3) 할당된 샘플들의 중심으로 센트로이드를 이동시킨다.
• 4) 클러스터 할당이 변하지 않거나, 사용자가 지정한 허용오차나 최대 반복횟수에 도착할 때 까지 두번째와 세번째 과정을 반복한다.

---

• 유사도 측정 : 임의의 차원 공간의 두 데이터 포인트 x와 y 사이의 유클리디안 거리, 유클리디안 거리 제곱 지표를 기반하여 '최적화 문제'로 k평균 알고리즘을 설명할 수 있다. 즉, k-means도 최적화 문제라고 할 수 있다.
• 클러스터 내 제곱 오차합(SSE = 센트로이드와 클러스터 내 데이터의 거리 제곱합)를 계산하여 이를 반복적으로 최소화시킨다. 각 데이터를 가장 가까운 센트로이드(클러스터)에 할당하면, 센트로이드는 이동되고 SSE는 다시 계산된다. 이런 과정에서 SSE가 일정 수준 내로 들어온다면 클러스터가 변화하지 않는다는 것이고, 최적화가 완료되었음을 의미한다.
• 각 데이터들의 변동폭이 크다면, '왜곡'이 일어날 가능성이 높다. 이러한 왜곡을 줄이기 위해서는 거리 산출시 불필요한 항목간의 특성을 제거하고 단위를 일치시키는 '표준화' 과정을 진행하면 좀 더 좋은 결과를 가져올 수 있다.

from sklearn.cluster import KMeans

km = KMeans(n_clusters = 3, init = 'random', n_init = 10, max_iter = 300, tol = 1e-04, random_state = 0)

• KMeans(클러스터개수, 초기 중심좌표설정방법, 초기설정 시 가장 작은 SSE값 찾는 횟수, 데이터 추가 후 센트로이드 이동 횟수, SSE 허용 오차값, 랜덤 설정값)
• 초기 센트로이드 위치를 랜덤하게 설정하기 때문에, 잘못 설정된다면 클러스터 성능이 매우 불안정해진다.
• 이를 위해 초기 센트로이드를 더 똑똑하게 할당할 수 있는 방법 등장 (K-means++)
• 또한 K-평균 방법은 데이터 당 클러스터가 중복되지 않고, 계층적이지 않다. 그리고 클러스터 당 하나 이상의 데이터는 있다는 '가정'도 존재한다.
• 이러한 특징과 가정 극복이 어렵다. 때문에 더더욱 초기 센트로이드를 잘 설정해야 한다.

---

원리기반 알고리즘 구현

def distance(x1, x2):
    return np.sqrt(np.sum((x1 - x2) ** 2))

def kmeans(X, num_clusters, initial_centroid_indices):
    import time
    N = len(X)
    centroids = X[initial_centroid_indices]
    labels = np.zeros(N)   
    while True:
        is_changed = False

        for i in range(N):
            distances = []
            for k in range(num_clusters):
                k_dist = distance(X[i], centroids[k])
                distances.append(k_dist)
            if labels[i] != np.argmin(distances):
                is_changed = True
            labels[i] = np.argmin(distances)

        for k in range(num_clusters):
            x = X[labels == k][:, 0]
            y = X[labels == k][:, 1]

            x = np.mean(x)
            y = np.mean(y)
            centroids[k] = [x,y]
        if not is_changed:
            break

    return labels

• PCA로 2차원 처리된 데이터 X를 제공받고, 이를 기반으로 num_clusters개수의 클러스터를 생성한다.
• 초기 중심점은 initial_centroid_indices 좌표로 설정된다.
• distance함수는 두 점 사이의 거리를 쉽게 구하기 위한 함수이다.
• 새로운 중심점은 데이터 포인트들의 위치의 산술평균으로 구했다.
• is_changed 변수로 labels의 변경 여부를 체크하고 변하지 않았다면 알고리즘을 종료한다. (변했다면 반복)