K-means 알고리즘

군집화(K-means)란,

- 전체 데이터를 몇 개의 집단으로 그룹화하여 각 집단의 성격을 파악함으로써 데이터 전체의 구조에 대한 이해를 돕고자 하는 분석법

- 모집단 또는 범주에 대한 사전 정보가 없는 경우 주어진 관측 값들 사이의 거리 또는 유사성을 이용하는 분석법

- 주어진 데이터들의 특성을 고려해 데이터 집단(클러스터)을 정의하고 데이터 집단의 대표할 수 있는 대표점을 찾는 것으로 데이터 마이닝의 한 방법

군집분석의 활용

- 군집분석은 속성이 비슷한 잠재 고객들끼리 그룹화 하여 시장을 세분화 하는 방법에 자주 활용

- 기업의 수익에 기여 정도를 파악해서 우수고객의 인구통계적 요인, 생활패턴 파악하거나 개별고객에 대한 맞춤관리를 해야할때

- 구매패턴을 파악해서 신상품 판촉하거나 교차판매를 위한 목표집단을 구성해야할때

군집분석알고리즘

1. k개의 random 값을 구한다.

2. random값 에 대한 군집을 구성한다.

3. 군집에 대한 중앙점을 구한다.

4. 만약 이 중앙점들이 이전에 구한 중앙값과 동일하다면 종료한다.

5. 그렇지 않으면 현재 중앙점을 가지고 2.를 수행한다.

k-means알고리즘

import random
import matplotlib.pyplot as plt
 
class KMeans:
    
    #__init__ : 생성자
    #classify : 분류메서드
    #train : 훈련메서드
    
    def __init__(self, k) :
        self.k = k
        self.means = None
        
    #a와 b의 거리를 구함
    def squared_distance(self,a, b):
        return ((b[0] - a[0])**2 + (b[1] - a[1])**2)
    
    #군집간(i_point)의 중앙점을 구함
    def vector_mean(self, i_points):
        sum_x = 0;
        sum_y = 0
        for i in list(i_points):
            sum_x += i[0]
            sum_y += i[1]
            
        avg_x = (sum_x / len(i_points))
        avg_y = (sum_y / len(i_points))
       
        return [avg_x, avg_y]
        
    #군집을 분류함
    def classify(self, input) :
        #range(self.k)에 key를 적용해서 min값을 구함
        return min(range(self.k), key = lambda i: self.squared_distance(input, self.means[i]))
    
    
    def train(self, inputs) :
    
        self.means = random.sample(inputs, self.k)
        assignment = None
        
        while True :
            new_assignment = list(map(self.classify , inputs))
 
            if assignment == new_assignment:
                return assignment
 
            assignment = new_assignment
            
            for i in range(self.k):
 
                i_points = [p for p, a in zip(assignment, inputs) if a == i]
 
                if i_points:
                    self.mean[i] = self.vector_mean(i_points)
    
    #그래프를 그리기위해서 데이터를 가공함
    def make_praph_data(self, data):
        axis_x = list()
        axis_y = list()
        for i in list(data):
            axis_x.append(i[0])
            axis_y.append(i[1])
        
        return axis_x, axis_y
 
 
if __name__ == "__main__":
    inputs = inputs = [
                        [-14,-5],[13,13],[20,23],[-19,-11],[-9,-16],[21,27],[-49,15],
                        [26,13],[-46,5],[-34,-1],[11,15],[-49,0],[-22,-16],[19,28],
                        [-12,-8],[-13,-19],[-41,8],[-11,-6],[-25,-9],[-18,-3]
                      ]
 
    clus = KMeans(3)
    
    clus.train(inputs)
    
    print(clus.means)
   
    axis_x_mean, axis_y_mean = clus.make_praph_data(clus.means)
    axis_x, axis_y = clus.make_praph_data(inputs)
    
    plt.scatter(axis_x, axis_y)
    plt.scatter(axis_x_mean, axis_y_mean, marker='>', c='r')
    
    plt.show()

k-means의 k값 구하기

k-means는 k값을 임의로 정해주어야한다. k값을 찾는 방법에 대해서 알아보자.

방법은 각 k값에 대하여 군집들의 거리를 구해서 합한다음 이것에 대해 가장 가파르게 꺾이는 부분을 찾는 것이다.

k_value = list();
 
for k in range(1,10):
    model = KMeans(k)
    model.train(inputs)
    means = model.means
    assignments = map(model.classify, inputs)
    k_value.append(sum(model.squared_distance(input, means[cluster]) 
                    for input, model in zip(inputs, assignments)))
print(k_value)
plt.plot(k_value)
plt.show()

결과해석 :
가장 가파르게 하강한 부분이 2-3 부분이므로 이 군집은 2-3개의 군집으로 나누는 것이 합리적이다.

k-means알고리즘 단점

1. 최초 초기화하는 값에 따라 시작하기때문에, 중심점과 점간의 거리가 Global optimum인 최소 값을 찾는 게 아니라 중심점이 Local optimum 에 에 수렴하여 잘못된 분류를 할 수 있다는 취약점을 가지고 있다. 

2. 군집의 크기다 다를 경우 원하는 대로 분류되지않을수 있다.

3. 군집의 밀도가 다를경우도 분류가 잘되지 않을수 있다.

4. 데이터 분포가 특이한 경우에도 군집이 잘일어나지 않을수 있다.

k-mean 알고리즘의 문제점을 해결할수 있는 알고리즘으로 비지도 학습 기반의 클러스터링 알고리즘중의 하나인 Hierachical Clustering 알고리즘이 있다.  Hierarchical Clustering은 이름에서도 알 수 있듯이 각 클러스터가 유사한 특징을 가지고 있는 여러 계층으로 되어 있을 때 효과적으로 사용할 수 있으며, 클러스터의 수 n을 정의하지 않고도 사용이 가능하다. 

[참고]

http://bcho.tistory.com/1203

http://hamait.tistory.com/740?category=132470

http://www.jidum.com/jidums/view.do?jidumId=1099

https://ratsgo.github.io/machine%20learning/2017/04/19/KC/