평균 이동 알고리즘으로 데이터 클러스터링

이번엔 k- means 보다 약간 어려운.. 2단계 ! 데이터 클러스터링을 해보겠다. 

 

평균 이동 Mean shift 은 비모수 알고리즘이다. 항상 말이 좀 어려워....비모수 알고리즘 = 데이터가 표준 확률 분포를 안 따른다고 가정 = 데이터가 적거나 독립적이거나 연속적이지 않음 뭔가 중간에 끊김. 여튼 뭔가 문제가 많은 데이터인 경우! 혹은 기본 분포에 대한 가정을 하지 않는 경우 이 알고리즘을 사용할 수 있다. 

 

이렇게 분류하는 비지도학습 뿐 만 아니라 상관관계를 파악해야할때도 비모수 데이터들은 나를 곤란하게 한다.. 그래서 여러가지 다양한 방법들이 존재하는 것 !

 

 

 

1. k-means 와의 차이 

 

k- means 알고리즘은 중심에 소속된 데이터의 평균 거리를 기준으로 클러스터화시키는 반면, 평균 이동 알고리즘은 데이터의 밀도가 가장 높은 곳을 데이터의 중심으로 잡는다. 

 

그러니까, 하나의 데이터가  A 클러스터 혹은 B 클러스터에 속해있는지 아닌지 자체를 "확률 밀도" 를 이용해 판단한다는거다. 그럼 단계적으로 데이터 분포를 중심으로 중심점인 centroid 가 이동하게 된다. k- means 의 경우 아무 데이터를 랜덤으로 골라 다른 데이터 개별간의 거리를 계산해서 그 거리가 좁혀지는 구간을 찾았다.

 

그런데 Mean shift 방법은 "데이터의 분포" 를 기준으로 보기 때문에 임의의 원을 그려서 그것을 분포의 반경으로 삼아 이 분포의 밀도가 높은 곳을 찾아나간다고 이해하면 되겠다. 아래 그림처럼 말이다. 

 

 

출처: michigusa

 

그리고, 얘는 k 를 선택해 줄 필요가 없다. mean 이 shift 되면서 자동으로 클러스터링 개수가 정해짐. 대신! 탐색할 반경 = kernel 의 반지름은 정해줘야한다. 이때 저 탐색반경을 "대역폭" 이라고 부르기도 하는 듯? 이거에 따라 성능도 달라짐

 

효율성의 측면에선 k- means 보다 작동시간이 더 오래 걸린다. 그리고 일반적인 데이터셋보다는 이미지나 영상처리같은 비전 분야에서 더 많이 쓴다고 함

 

 

 

2. 작동원리 

 

1. 초기 중심점에서 시작
2. KDE(Kernerl Density Estimation)를 이용해서 어떤 반경의 확률 밀도를 구한다.
3. 확률 밀도가 높은 곳으로 이동
4. 데이터가 집중적으로 모여있어 확률 밀도 함수가 피크인 점을 새로운 군집 중심점으로 선정한다.
5. 이러한 방식을 전체 데이터에 반복적으로 적용하면서 데이터의 군집 중심점을 찾는다.
6. 더 이상 좋은 중심점이 없으면 끝, 수렴

출처: jeonsm

 

* 확률밀도함수?

-> 어떤 데이터가 A 에 속할만큼의 확률이 얼마나 되느냐를 말해주는 함수

-> 뭔 말인지 모르겠다면 여기로 https://darkpgmr.tistory.com/147

 

 

 

 

3. 예제코드

3.1. 라이브러리, 데이터 import

 

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import MeanShift, estimate_bandwidth
from itertools import cycle

# Load data from input file
X = np.loadtxt('Chapter07\data_clustering.txt', delimiter=',')

 

3.2. 대역폭 (반경) 예상

 

다짜고짜 대역폭을 정하라고하면 당황스럽잖아..? estimate_bandwidth 는 대역폭을 추정해주는데 좋다. 이걸 일단 baseline 으로 쓰고 나중에 반복문으로 튜닝을 해도 좋을 것 같음 

# Estimate the bandwidth of X
# quantile = 대역폭을 예상하는데 중요한 파라미터, 값이 클수록 예상 대역폭이 증가, 데이터셋이 크다면 작게 선택 
bandwidth_X = estimate_bandwidth(X, quantile=0.1, n_samples=len(X))
print(bandwidth_X)

#out: 1.3044799765090382

 

 

 

3.3. 모델 선언, 학습 

 

# Cluster data with MeanShift
meanshift_model = MeanShift(bandwidth=bandwidth_X, bin_seeding=True)
meanshift_model.fit(X)

 

 

3.4. 중심과 클러스터 수 추출, 시각화 

 

 

여기서는 시각화 반복문에 마커 옵션을 줘서 클러스터마다 모양을 다르게 출력함. 굳이 안 해도 됨...^^

# Extract the centers of clusters
cluster_centers = meanshift_model.cluster_centers_
print('\nCenters of clusters:\n', cluster_centers)

'''out: 
Centers of clusters:
 [[2.95568966 1.95775862]
 [7.20690909 2.20836364]
 [2.17603774 8.03283019]
 [5.97960784 8.39078431]
 [4.99466667 4.65844444]]
 '''
 

# Estimate the number of clusters
labels = meanshift_model.labels_
num_clusters = len(np.unique(labels))
print("\nNumber of clusters in input data =", num_clusters)

#out: Number of clusters in input data = 5

# Plot the points and cluster centers
plt.figure()
markers = 'o*xvs'
for i, marker in zip(range(num_clusters), markers):
    # Plot points that belong to the current cluster
    plt.scatter(X[labels==i, 0], X[labels==i, 1], marker=marker, color='black')

    # Plot the cluster center
    cluster_center = cluster_centers[i]
    plt.plot(cluster_center[0], cluster_center[1], marker='o', 
            markerfacecolor='black', markeredgecolor='black', 
            markersize=15)

plt.title('Clusters')
plt.show()

 

 

짠! 

 

이 데이터는 사실 이미 분류가 너무 잘 된 2차원 데이터라 k-means 와의 명백한 차이는 드러나지 않을겨! 근데 이미지나 영상같은 비전에서는 요 알고리즘 많이 쓴대..

 

다음 글은 클러스터링 품질 평가하는 "실루엣 스코어" 에 대해 다뤄보겠다요