파이썬 코딩으로 말하는 데이터 분석 - 3. 군집화

요즘 데이터분석과 관련하여  텐서플로우와 스파크(ML)등의 머신러닝 솔루션들이 굉장히 유행하고 있습니다. 물론 저것들이 삶을 편안하게 만들어주기도 하지만 대부분의 데이터 분석은 저런 거창한 것 말고 평균,편차 같은 기본적인 개념으로 부터 시작되고 있으며 이러한 개념을 조금씩 변경해가며 더 의미있는 가치를 찾기 위해 빠르게 적용해보는 과정을 거쳐야하는데  그러기 위해서는 

1. 직접 코딩해서 기본적인 데이터분석 유틸리티 함수들을 만들어봐야한다. 

2. SQL문을 잘 다루어야한다. 

3. 엑셀을 잘 다루어야 한다. 

이 3가지는 기본이라고 저는 생각합니다. 소규모 데이터를 가지고 이리저리 반복해서 돌려보는 과정은 매우 중요하며 이런 기본적인 것들도 못하면서 하둡,텐서플로우나 깔짝대고, 데이터 분석 한다 라고 칭할 수는 없겠지요. (이것은 논쟁의 여지가 있습니다.) 그래서 이것들 중 1번에 대하여  "밑바닥부터 시작하는 데이터과학" 등의 좋은책의 내용을 통해서 살펴보는 시간을 갖도록 하겠습니다. 

통계,확률,패턴인식 분야의 내용들의 수식은 외우기가 힘듭니다. 외워도 금방 까먹어지는게 통계관련 공식인거 같습니다. (예를들어 정규분포,확률밀도라는 개념은 매우 쉽게 수긍이 가지만 , 그 식을 외우는건 좀 .;;) 또한 체득하고 나면 당연한거 아냐? 라고 느껴지는 알고리즘(수식) 인데 글로 설명하면 매우 산만해지는거 학문인거 같습니다. 하지만  우리들은 소프트웨어 개발자이기 때문에 수많은 기술변화도 따라가야하는 운명에 있는데 쓸때 없이 공식 및 수학을 외우고 있을 수는 없지 않겠습니까? 

제가 초등학교 5학년때 만(10,000) 단위 암산을 했었는데요. 주산,암산을 배워보신분은 아시겠지만 그것이 가능한것은 기억의 매개로 주판을 이용한 것 입니다. 마찬가지로 우리 개발자들은 그 기억의 매개체로 코드를 이용하면 개념과 함정(예를들어 K-Means 를 통해 군집화하면 길이차를 가지고 구분짓는 것이기 때문에 문제가 생기는 도메인 또한 많다) 에 대한 이해가 더 오래갈 것이라 보며 덤으로 가져다 사용도 할 수 있을것입니다.

* 그 상상의 매개체로써의 언어로 "파이썬" 을 선택했으며 정말 좋은 언어라고 생각합니다.

순서 

1. 통계 - 카운팅,min,max,평균,중앙값,산포도,분산,편차,공분산,상관관계 

2. 가설과 추론 (베이지언 - 사후확률,우도) 

3. 군집화 (K-Means)

4. 연관 (Apriori)

5. 함수형으로 데이터 다루기 

6. 경사하강법

7. 회귀분석

8. 은닉 마코프법 (HMM) 

9. k-NN

10. DTW 

 * 참고로 "밑바닥부터 배우는 데이터과학" 서적은 numpy,scikit-learn 등의 외부라이브러리를 활용은 배제되었습니다.

K-Means 알고리즘 이란 ? 

머신러닝의 큰 바운더리로 중 하나로 군집을 들수있는데 K-Means 는 군집분석을 할때  활용되는 기본 알고리즘 입니다. 군집이란 , 쉽게 말해 도서관에서 여러분이 어떤 기준에 따라서 책을 그룹핑할때 하는 행동 . 그때 책들을 군집화 한다라고 말할수있습니다. (역사책, 수학책, 소프트웨어 책)  군집할때는 어떤 데이터간의 유사성을 정량적으로 측정하여 수치화하는게 핵심이며, (역사와 수학, 소프트웨어 를 각각 어떤 기준으로 수치화) 수치화가 된후 K-Means 알고리즘을 이용하여 자동 그룹핑 할 수 있게 되는데 K-Means 는 말 그래도 K 개로 그룹핑하라~ 와 같습니다. 유사한 입력 값끼리 묶어서 군집을 찾습니다.굉장히 클리어한 알고리즘이며 간단한데에 비해 많은곳에서 주요 알고리즘으로 사용됩니다.

다음 코드는 K-Means 를 나타내는데 그 수행과정을 보면 

1) 임의의 K개의 군집수를 결정하고 (여기선 3개) 그것의 초기치를 1개씩 할당(여기선 랜덤)하여 위치 설정한다.

self.means = random.sample(inputs, self.k)

2) 각각의 데이터에 대해 K개의 위치까지의 거리를 구하고 가장 가까운 군집에 소속시킨다.(유클리드 거리를 이용)

   def classify(self, input):
        return min(range(self.k),
                   key=lambda i: squared_distance(input, self.means[i]))

3) 3개의 군집으로 나뉘어진 데이터를 가지고 새로운 중앙의 위치를 설정한다.

   # 현재 클러스터링의 중심점 재 계산
    for i in range(self.k):
        i_points = [p for p, a in zip(inputs, assignments) if a == i] # i 번 요소들의 리스트
          if i_points:
            self.means[i] = vector_mean(i_points) # 그것들의 평균 ( 중심점 )

4) 이전 군집과 새롭게 중앙점을 이동한후에 얻어진 군집이 갖으면 종료한다.

        while True:
            # 요소들이 어느 (변경된)중심점에 가까이 있는지 매핑 [1,1,0,2,1, ... 이런식
            new_assignments = map(self.classify, inputs)

            # 기존 매핑과 동일하다면 더 이상 프로세싱 할 필요 없음. 리턴 ~
            if assignments == new_assignments:
                return

이 과정을 통하여 K개의 군집으로 나눈다. 아래는 전체 소스이다.

# coding: utf-8

from __future__ import division
from linear_algebra import squared_distance, vector_mean
import random


class KMeans:

    def __init__(self, k):
        self.k = k  # 클러스터의 갯수
        self.means = None  # 클러스터의 평균들

    # input 값이 3개의 means 중 어디와 가장 가까운지 찾아서 0,1,2 중 하나를 리턴
    def classify(self, input):
        return min(range(self.k),
                   key=lambda i: squared_distance(input, self.means[i]))

    def train(self, inputs):

        self.means = random.sample(inputs, self.k)
        assignments = None

        while True:
            # 요소들이 어느 (변경된)중심점에 가까이 있는지 매핑 [1,1,0,2,1, ... 이런식
            new_assignments = map(self.classify, inputs)

            # 기존 매핑과 동일하다면 더 이상 프로세싱 할 필요 없음. 리턴 ~
            if assignments == new_assignments:
                return

            # 현재 매핑을 저장
            assignments = new_assignments

            # 현재 클러스터링의 중심점 재 계산
            for i in range(self.k):
                i_points = [p for p, a in zip(inputs, assignments) if a == i] # i 번 요소들의 리스트
                if i_points:
                    self.means[i] = vector_mean(i_points) # 그것들의 평균 ( 중심점 )




if __name__ == "__main__":

    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]]

    random.seed(0) # so you get the same results as me
    clusterer = KMeans(3)
    clusterer.train(inputs)
    print "3-means:"
    print clusterer.means
    print

문제 발생 1 

위처럼 단순 길이차이로 군집하는 알고리즘을 이용해서 

5,6,50,60,500,600 <-- 이걸 3개로 군집화 한다면 

[5,6,50,60] [500] [600]   이렇게 3개로 나뉠것이다.

하지만 [5,6] [50,60] [500,600]  이렇게 3개로 나뉘길 바랬더라면 망하는거다. OTL 

상향식 계층 군집화 

1. 각 데이터 포인트를 하나의 군집으로 간주한다.

2. 군집이 두개 이상이라면, 가장 가까운 두개의 군집을 찾아 하나의 군집으로 묶는다. 

위의 알고리즘으로 

5,6,50,60,500,600 <-- 이걸 3개로 군집화 한다면 

5에서 가장 가까운 6을 찾아서 [5,6] 군집화 

50에서 가장 가까운 60 찾아서 [50,60] 군집화

500 에서 가장 가까운 600 찾아서 [500,600] 군집화 

이렇게 나뉠것이다.

이런식으로 최소 거리를 이용한 계층 군집화는 위의  K-means 와는 다른 군집을 이룬다. 

K 값 찾기 

위 에서는 k 값을 그냥 3개로 했지만 k 값을 보다 합리적으로 찾을 수 있는 방법도 여러가지이다.
쉬운 방법은 k 값에 대해 중심점과 각 데이터 포인트 사이의 거리의 제곱합을 그래프로 그리고, 그 그래프가 어디서 꺽이는지 관찰하는 것이다.

def squared_clustering_errors(inputs, k):
    clusterer = KMeans(k)
    clusterer.train(inputs)
    means = clusterer.means
    assignments = map(clusterer.classify, inputs)

    return sum(squared_distance(input, means[cluster])
               for input, cluster in zip(inputs, assignments))

아래 처럼 꺽이는데 K=3 이 적절했던 거 같다.

전체소스

https://github.com/Insight-book/data-science-from-scratch/blob/master/code/ch19_clustering.py

분산환경에서 K-Means 알고리즘 알아보기 

[하마 인사이드] 1. HAMA with K-Means