블로그 이미지
평범하게 살고 싶은 월급쟁이 기술적인 토론 환영합니다.같이 이야기 하고 싶으시면 부담 말고 연락주세요:이메일-bwcho75골뱅이지메일 닷컴. 조대협


Archive»


 
 

NMF 알고리즘을 이용한 유사한 문서 검색과 구현(1/2)



조대협 (http://bcho.tistory.com)


앞의 글들에서, 데이타의 특징을 뽑아내는 방법으로 차원 감소 (Dimension reduction) 기법에 대해서 설명하였다. 구체적인 알고리즘으로는  PCA와 t-SNE 알고리즘을 소개하였는데, 오늘은 차원 감소 기법중의 하나인 행렬 인수분해 (Matrix Factorization)에 대해서 알아보고자 한다.

문서 유사도 검색

행렬 인수 분해를 설명하기 위해서 유사한 문서를 찾는 시나리오를 예를 들어서 설명하겠다.

문서 유사도 검색의 원리는 다음과 같다


  1. 문서에 나온 각 단어들을 숫자(벡터)로 변환하여 행렬화 한다.

  2. 행렬화된 문서에서 차원 감소 기법을 이용하여, 문서의 특징을 추출한다.

  3. 추출된 특징을 기반으로, 해당 문서와 특징이 유사한 문서를 찾아서 유사값을 기반으로 소팅하여, 유사 문서를 찾아낸다.


각 과정에서 사용할 알고리즘을 보면 다음과 같다.


  1. 문서의 단어들을 숫자화 하여, 행렬로 변환하는 과정에서는 여러가지 word2Vec (요즘 대세) 알고리즘이 있지만, 간단하게 tfidf 라는 알고리즘을 사용하겠다.

  2. 다음 문서의 행렬을 값을 가지고 특징을 추천하기 위해서는 앞에서 언급한 행렬 인수 분해 (Matrix Factorization) 알고리즘을 이용하여, 행렬의 차원을 줄일것이고

  3. 해당 문서와 특징 값이 유사한 문서를 찾기 위한 방법으로는 벡터간의 거리를 측정하는 방법을 사용하여 유사도를 측정하는데, Consine distance (코싸인 거리) 알고리즘을 사용하도록 한다.


각 알고리즘에 대한 간략한 개념을 설명하고 구현은 파이썬의 sklearn의 라이브러리를 사용해서 구현하도록 하겠다.그러면 각 알고리즘에 대한 설명을 보자

TF-IDF (Term Frequency Inverse Document Frequency)

TF-IDF를 이해하기 위해서는 먼저 TF(Term Frequency)와 DF(Document Frequency)에 대한 개념을 먼저 이해해야 한다

  • TF(Term Frequency) : TF랑, 하나의 문서에서 그 단어(Term) 가 얼마나 자주 나타나는가(Frequency)를 정의한 값이다.
    예를 들어, 한문서에서 “조대협" 이라는 단어가 10번 등장했다면 조대협에 대한 TF값은 10이 된다.

  • DF(Document Frequency) : DF란, 전체 문서(Document)에서 그 단어(Term)가 등장한 문서의 수를 나타낸다.  “조대협" 이라는 단어가 20개의 문서에 나타났다고 하면 DF 값은 20이 된다.

그러면 TF-IDF란 무엇인가 TF값을 DF값으로 나눈 값을 TFIDF라고 하는데, 위의 설명에서 “조대협" 이라는 단어에 대한 TFIDF값은 10/20=0.5 가 된다. (정확하게는 IDF는 log 를 포함한 다른 수식을 사용하지만 의미상으로 DF를 나눈것과 같이 문서에 등장하는 단어의 밀도를 나타낸다고 이해하면 된다.)


TF-IDF값의 의미는 무엇일까?

10년치 뉴스 문서가 있다고 가정하자.

그리고 우리가 뉴스에  많이 사용하는 단어로 “예를 들어" 라는 단어가 있다고 가정하자. (원래는 단어별로 잘라서 생각해야 하지만 설명을 쉽게 하기 위해서 두 단어를 하나의 단어로 생각하자). “예를 들어" 라는 단어는 어떤 문서의 특징을 나타내기는 사실 어렵다. 너무 일반적으로 사용되는 말이기 때문인데, 이런 단어의 경우에는 거의 모든 문서에 나타날 수 있기 때문에 DF 값이 매우 커진다. 그래서 “예를 들어"의 TF-IDF 값은 거의 0으로 수렴하게 되고, “세월호"와 같은 단어는 세월호를 언급한 뉴스 기사에만 있기 때문에, DF 값은 낮아질것이고, 결과적으로 TF-IDF 값은 커질 수 있는데, 세월호 라는 단어가 많이 언급된 문서일 수 록 TF-IDF 값이 커지게 된다.


눈치가 빠른 사람은 벌써 이해했겠지만, TFIDF의 기본 원리는 전체 문서에 널리 사용되는 일반적인 단어는 특징에서 배제하고, 문서에 특정 단어가 많이 언급될 수 록 그 단어의 TF-IDF값을 크게 하여, 문서의 특징을 나타내는데 사용할 수 있다.

NMF (Non-negative Matrix Factorization)

NMF (비음수 행렬 인수 분해)는 차원 감소 기법으로, 컴퓨터 시각 처리나, 우리가 하려는 문서 분류 그리고 음파 분석등에 널리 사용된다. 앞의 글들에서 소개했던 PCA나 t-SNE와 같은 차원 감소 기법에 대비한 차이를 보면, NMF에 의해 추출된 특징의 경우에는 해석이 가능하다는 장점을 가지고 있다.

PCA나 t-SNE는 원본 데이타의 특징을 추출하여 새로운 특징 셋으로 표현을 하지만 새로운 특징셋이 원본 특징과 어떤 연관 관계를 가지는지는 해석이 불가능하다. NMF의 경우 새로운 특징셋이 어떻게 원본 데이타 들과 관계를 가지는지 확인이 가능한데 이 부분은 NMF 알고리즘을 먼저 이해하고 하도록 하자


NMF는 행렬 인수 분해 알고리즘 중 하나로, 행렬 인수 분해란 다음과 같다.

우리가 원본 행렬 V가 있다고 했을때, 행렬 인수 분해는 이 V 행렬을 두개의 행렬로 분리 하는 것이다.

아래 그림은 원본 행렬 V 를 V=W*H 로 분리한 예이다.


예를 들어 TF-IDF를 이용하여 책 제목과 단어로 이루어진 행렬 V의 모양이 다음과 같다고 하자



책제목

협상

스타트업

투자

비지니스

데이타

...

...

협상의법칙

0.9

0

0.3

0.8

0



린스타트업

0

0.8

0.7

0.9

0.3



빅데이타

0

0

0.5

0

0.8



< 그림. 책 제목과, 그 책에 나온 단어의 TFIDF 값으로 이루어진 행렬 V >


이를 행렬 분해를 통하면


행렬 W는 다음과 같은 모양을 가지게 되고

책제목

특징1

특징2

특징3

특징4

협상의법칙

0.9

0

0.1

0.2

린스타트업

0

0.8

0

0

빅데이타

0.2

0.1

0.8

0.1


행렬 H는 다음과 같은 모양을 가지게 된다.


협상

스타트업

투자

비지니스

데이타

...

...

특징1

0.92

0

0.1

0.2

0



특징2

0

0.85

0.5

0.3

0.3



특징3

0

0

0.3

0

0.8



특징4

0

0

0

0

0

...



여기서 W를 가중치 행렬 (Weight Matrix), H를 특성 행렬 (Feature Matrix)라고 한다.

W는 카테고리 (책제목) 에 특성과의 관계를 나타내며, H는 원래 특성(협상,스타트업,...)에 대비한 새로운 특성(특징 1,2,3…)에 대한 관계를 나타낸다.


W 값을 보면 특징 1은 “협상의 법칙"에 자주 나오는 단어들 빈도와 관련이 높은 특성임을 알 수 있고, 특징 2는 “린스타트업", 특징3은 “빅데이타"에 자주 나오는 단어들의 빈도와 관련이 높은 특성임을 예측할 수 있다.

또한 특성 행렬 H를 보면 특징 1은 “협상" 이라는 단어와 관련이 많고, 특징 2는 “스타트업" 이라는 단어와 관련이 많은 것을 알 수 있다.

아래는 그림은  특징을 NMF를 이용하여 추출한 특성 행렬 H를 나타내는데, 해당 특징이 어떤 단어들에 의해서 반응 하는지를 알 수 있다.


그래서 NMF를 PCA나 t-SNE와 같은 다른 알고리즘과 비교했을때 특성을 해석 가능하다고 이야기 하는 것이다.


이 데이타셋에 만약에 이 데이타에 “스타트업 데이타 분석" 이라는 책이 들어왔고, 이 책은 빅데이타와 스타트업에 대해 다루고 있다면, 아마도 가중치 행렬 W에서 “스타트업 데이타 분석"은 다음과 같이 특징2와 3과 관련이 높은 형태를 나타낼 것이다.


책제목

특징1

특징2

특징3

특징4

협상의법칙

0.9

0

0.1

0.2

린스타트업

0

0.8

0

0

빅데이타

0.2

0.1

0.8

0.1

스타트업 데이타 분석

0

0.9

0.7

0


여기서 중요한 것은 차원을 줄일때 몇개의 특징으로 기존의 특성을 압축(줄일가)인데, 여기서는 4개의 특징으로 전체 특성을 줄이는 것으로 하였다. (특징을 몇개로 표현할 것인가가 매우 중요한 튜닝 패러미터가 된다.)


지금까지 설명한 행렬 인수 분해 방식은 행렬의 값이 양수일때 사용하는 행렬 분해 방식으로 “비음수 행렬 인수 분해 (Non negative Matrix Factorization)이라고 한다. NMF 방식에도 여러가지 다양한 발전된 알고리즘들이 있으며, 알고리즘 리스트는 https://en.wikipedia.org/wiki/Non-negative_matrix_factorization 를 참고하기 바란다.



코싸인 거리기반의 유사도 측정

NMF등을 이용하여 압축되어 있는 특성을 기반으로 하여 유사한 문서를 찾는 방법에 대해서 알아보자. 특성을 기반으로 유사도를 측정하는 방법은 여러가지가 있다. 주로 특성값을 벡터 공간에 맵핑 한후, 벡터간의 거리를 기반으로 계산하는 방법이 많이 사용되는데, 유클리디안 거리, 코사인 거리, 자카드 거리, 피어슨 상관 계수, 맨해튼 거리등이 있다. 여기서는 코사인 거리를 사용하여 문서간의 유사도를 측정한다.


코사인 거리의 기본 원리는 다음과 같다.


특성 값을 나타내는 벡터 A와 B가 있을때, 이 벡터 A와 B사이의 각도가 가까울 수록, 두 개의 특성이 유사하다고 판단하기로 한다. 즉 A와 B의 각도 θ 가 최소일 수 록 값이 유사하다고 판단하면 된다. 그러면 벡터 A 와 B만을 가지고, 어떻게 각도 θ를 구할 수 있는가?

벡터의 내적을 사용하면 이 θ 가 크고 작음을 알아낼 수 있는데 기본 원리는 다음과 같다.

벡터 a와 b 가 있을 때 이 두 벡터의 내적 ab = |a|*|b|*cos(θ) 가 된다.

cos(θ)를 좌변으로 옮기면


cos(θ) = ab / |a|*|b


가 되고, 이를 계산하는 공식은 ab 은 벡터 a 행렬의 각 항의 값 Ai 과  b행렬의 각 항의 값 Bi를 순차적으로 곱하여 더하면 된다. (A1*B1+A2*B2 …. + An*Bn)

|a|는 a 벡터의 길이로, sqrt(A1^2 + A2^2 + …. An^2)로 계산을 하고, |b|역시 sqrt(B1^2 + B2^2 + …  Bn^2로 계산한다.)


이를 수식으로 풀어보면 다음과 같다.




이렇게 계산하여, cos(θ) 의 값이 1에 가까우면 유사도가 높고, 0에 가까우면 유사도가 낮은 것으로 판단할 수 있다.


정리해보면  유사도를 파악하고자 하는 문서를 정한 후에, NMF를 이용하여 각 문서의 특성을 추출한후에 NMF에 의해 추출된 가중치 행렬을 가지고, 유사도를 파악하고자 하는 문서와 다른 문서들간의 코싸인 거리를 구하여, 이 거리 값이 가장 큰 문서가 가장 유사한 문서가 된다.


여기까지 간단한게 TF-IDF,NMF 그리고 코사인 유사도를 이용하여 유사한 문서를 찾는 방법을 설명하였다.코싸인 유사도를 적용하지 않고 NMF로 찾아낸 특성값을 기반으로 문서를 군집화 하는 클러스터링에도 활용이 가능하다.


다음글에서는 이 알고리즘을 실제로 sklearn을 이용해서 구현해보도록 한다.





DBSCAN (밀도 기반 클러스터링)


조대협(http://bcho.tistory.com)

기본 개념

이번에는 클러스터링 알고리즘중 밀도 방식의 클러스터링을 사용하는 DBSCAN(Density-based spatial clustering of applications with noise) 에 대해서 알아보도록 한다.

앞에서 설명한 K Means나 Hierarchical 클러스터링의 경우 군집간의 거리를 이용하여 클러스터링을 하는 방법인데, 밀도 기반의 클러스터링은 점이 세밀하게 몰려 있어서 밀도가 높은 부분을 클러스터링 하는 방식이다.

쉽게 설명하면, 어느점을 기준으로 반경 x내에 점이 n개 이상 있으면 하나의 군집으로 인식하는 방식이다.


그러면 조금 더 구체적인 개념과 용어를 이해해보자

먼저 점 p가 있다고 할때, 점 p에서 부터 거리 e (epsilon)내에 점이 m(minPts) 개 있으면 하나의 군집으로 인식한다고 하자. 이 조건 즉 거리 e 내에 점 m개를 가지고 있는 점 p를 core point (중심점) 이라고 한다.

DBSCAN 알고리즘을 사용하려면 기준점 부터의 거리 epsilon값과, 이 반경내에 있는 점의 수 minPts를 인자로 전달해야 한다.


아래 그림에서 minPts = 4 라고 하면, 파란점 P를 중심으로 반경 epsilon 내에 점이 4개 이상 있으면 하나의 군집으로 판단할 수 있는데, 아래 그림은 점이 5개가 있기 때문에 하나의 군집으로 판단이 되고, P는 core point가 된다.



아래 그림에서 회색점 P2의 경우 점 P2를 기반으로 epsilon 반경내의 점이 3개 이기 때문에, minPts=4에 미치지 못하기 때문에, 군집의 중심이 되는 core point는 되지 못하지만, 앞의 점 P를 core point로 하는 군집에는 속하기 때문에 이를 boder point (경계점)이라고 한다.



아래 그림에서 P3는 epsilon 반경내에 점 4개를 가지고 있기 때문에 core point가 된다.



그런데 P3를 중심으로 하는 반경내에 다른 core point P가 포함이 되어 있는데, 이 경우 core point P와  P3는 연결되어 있다고 하고 하나의 군집으로 묶이게 된다.


마지막으로 아래 그림의 P4는 어떤 점을 중심으로 하더라도 minPts=4를 만족하는 범위에 포함이 되지 않는다. 즉 어느 군집에도 속하지 않는 outlier가 되는데, 이를 noise point라고 한다.


이를 모두 정리해보면 다음과 같은 그림이 나온다.


정리해서 이야기 하면, 점을 중심으로 epsilon 반경내에 minPts 이상수의 점이 있으면 그 점을 중심으로 군집이 되고 그 점을 core point라고 한다. Core point 가 서로 다른 core point의 군집의 일부가 되면 그 군집을 서로 연결되어 있다고 하고 하나의 군집으로 연결을 한다.

군집에는 속하지만, 스스로 core point가 안되는 점을 border point라고 하고, 주로 클러스터의 외곽을 이루는 점이 된다.

그리고 어느 클러스터에도 속하지 않는 점은 Noise point가 된다.

장점

DBSCAN 알고리즘의 장점은

  • K Means와 같이 클러스터의 수를 정하지 않아도 되며,

  • 클러스터의 밀도에 따라서 클러스터를 서로 연결하기 때문에 기하학적인 모양을 갖는 군집도 잘 찾을 수 있으며


    기하학적인 구조를 군집화한 예 (출처 : https://en.wikipedia.org/wiki/DBSCAN )

  • Noise point를 통하여, outlier 검출이 가능하다.

예제 코드

코드의 내용은 앞과 거의 유사하다.


model = DBSCAN(eps=0.3,min_samples=6)


모델 부분만 DBSCAN으로 바꿔 주고, epsilon 값은 eps에 minPts값은 min_samples 인자로 넘겨주면 된다. 이 예제에서는 각각 0.3 과 6을 주었다.


전체 코드를 보면 다음과 같다.


import pandas as pd
iris = datasets.load_iris()

labels = pd.DataFrame(iris.target)
labels.columns=['labels']
data = pd.DataFrame(iris.data)
data.columns=['Sepal length','Sepal width','Petal length','Petal width']
data = pd.concat([data,labels],axis=1)

data.head()



IRIS 데이타를 DataFrame으로 로딩 한 다음, 학습에 사용할 피쳐를 다음과 같이 feature 변수에 저장한다.


feature = data[ ['Sepal length','Sepal width','Petal length','Petal width']]
feature.head()


다음은 모델을 선언하고, 데이타를 넣어서 학습을 시킨다.


from sklearn.cluster import DBSCAN
import matplotlib.pyplot  as plt
import seaborn as sns

# create model and prediction
model = DBSCAN(min_samples=6)
predict = pd.DataFrame(model.fit_predict(feature))
predict.columns=['predict']

# concatenate labels to df as a new column
r = pd.concat([feature,predict],axis=1)


다음은 모델을 선언하고, 데이타를 넣어서 학습을 시킨다.

학습이 끝난 결과를 다음과 같이 3차원 그래프로 시각화 해보자. 아래 시각화는 3차원인데, 학습은 4차원으로 하였다. 그래서 다소 오류가 있어 보일 수 있다. 다차원 데이타를 시각화 하기위해서는 PCA나 t-SNE와 같은 차원 감소 (dimensional reduction) 기법을 사용해야 하는데,  이는 다음 글에서 다루도록한다.


from mpl_toolkits.mplot3d import Axes3D
# scatter plot
fig = plt.figure( figsize=(6,6))
ax = Axes3D(fig, rect=[0, 0, .95, 1], elev=48, azim=134)
ax.scatter(r['Sepal length'],r['Sepal width'],r['Petal length'],c=r['predict'],alpha=0.5)
ax.set_xlabel('Sepal lenth')
ax.set_ylabel('Sepal width')
ax.set_zlabel('Petal length')
plt.show()







마지막으로 Cross tabulazation 을 이용하여 모델을 검증해보면 다음과 같은 결과를 얻을 수 있다.

ct = pd.crosstab(data['labels'],r['predict'])
print (ct)



이 코드에 대한 전체 내용은 https://github.com/bwcho75/dataanalyticsandML/blob/master/Clustering/5.%20DBSCANClustering-IRIS%204%20feature-Copy1.ipynb 에서 확인할 수 있다.

Hierarchical clustering을 이용한 데이타 군집화


조대협 (http://bcho.tistory.com)


Hierarchical clustering (한글 : 계층적 군집 분석) 은 비슷한 군집끼리 묶어 가면서 최종 적으로는 하나의 케이스가 될때까지 군집을 묶는 클러스터링 알고리즘이다.

군집간의 거리를 기반으로 클러스터링을 하는 알고리즘이며, K Means와는 다르게 군집의 수를 미리 정해주지 않아도 된다. 참고로 이 글에서 사용된 예제 코드는 https://github.com/bwcho75/dataanalyticsandML/blob/master/Clustering/3.%20Hierarchical%20clustering-IRIS%204%20feature.ipynb 에 저장되어 있다.


예를 들어서 설명해보자

“진돗개,세퍼드,요크셔테리어,푸들, 물소, 젖소" 를 계층적 군집 분석을 하게 되면

첫번째는 중형견, 소형견, 소와 같은 군집으로 3개의 군집으로 묶일 수 있다.


이를 한번 더 군집화 하게 되면 [진돗개,셰퍼드] 와 [요크셔테리어,푸들] 군집은 하나의 군집(개)로 묶일 수 있다.


마지막으로 한번 더 군집화를 하게 되면 전체가 한군집(동물)으로 묶이게 된다.


이렇게 단계별로 계층을 따라가면서 군집을 하는 것을 계층적 군집 분석이라고 한다.

계층적 군집 분석은 Dendrogram이라는 그래프를 이용하면 손쉽게 시각화 할 수 있다.





계층형 군집화에 대한 좀 더 상세한 개념은 https://www.slideshare.net/pierluca.lanzi/dmtm-lecture-12-hierarchical-clustering?qid=94d8b25a-8cfa-421c-9ed5-03c0b33c29fb&v=&b=&from_search=1 를 보면 잘 나와 있다.


skLearn을 이용한 계층 분석 모델 구현

개념을 잡았으면 실제로 계층 분석 모델을 구현해보자.

데이타는 K Means에서 사용했던 IRIS 데이타를 똑같이 사용한다.

이번에는 4개의 피쳐를 이용해서 사용한다.


from sklearn import datasets
import pandas as pd
iris = datasets.load_iris()

labels = pd.DataFrame(iris.target)
labels.columns=['labels']
data = pd.DataFrame(iris.data)
data.columns=['Sepal length','Sepal width','Petal length','Petal width']
data = pd.concat([data,labels],axis=1)


다음은 IRIS 데이타를 이용하여 dendrogram을 그려보자

# Perform the necessary imports
from scipy.cluster.hierarchy import linkage, dendrogram
import matplotlib.pyplot as plt

# Calculate the linkage: mergings
mergings = linkage(data,method='complete')

# Plot the dendrogram, using varieties as labels
plt.figure(figsize=(40,20))
dendrogram(mergings,
          labels = labels.as_matrix(columns=['labels']),
          leaf_rotation=90,
          leaf_font_size=20,
)
plt.show()


먼저 linkage 함수를 import 한 다음 linkage 함수에 data를 넘겨주면 Hierarchical clustering을 수행한다. 이때 method=’complete’로 정했는데, 이 부분은 뒤에서 설명한다.

Hierarchical clustering 한 결과를 dendrogram 함수를 이용하여 dendrogram 그래프를 표현해 보면 다음과 같이 출력된다.




계층 분석 방식

앞의 코드에서, linkage 함수에서 method 를 사용했다. 이에 대해서 알아보자.

Hierachical clustering의 기본 원리는 두 클러스터 사이의 거리를 측정해서 거리가 가까운 클러스터끼리 묶는 방식이다.  그러면 두 클러스터의 거리를 측정할때 어디를 기준점으로 할것인가를 결정해야 하는데 다음 그림을 보자.



출처 : https://www.multid.se/genex/onlinehelp/hs515.htm


앞의 코드에서 사용한 complete linkage 방식은 두 클러스터상에서 가장 먼 거리를 이용해서 측정하는 방식이고 반대로  single linkage 방식은 두 클러스터에서 가장 가까운 거리를 사용하는 방식이다.

average linkage 방식은 각 클러스터내의 각 점에서 다른 클러스터내의 모든 점사이의 거리에 대한 평균을 사용하는 방식이다.


이 linkage 방식에 따라서 군집이 되는 모양이 다르기 때문에, 데이타의 분포에 따라서 적절한 linkage  방식을 변화 시켜가면서 적용해가는 것이 좋다.


계층 분석을 통한 군집의 결정

계층 분석은 최종적으로 1개의 군집으로 모든 데이타를 클러스터링 하는데, 그렇다면 n개의 군집으로 나누려면 어떻게 해야 하는가?

아래 dendrogram을 보자 y축이 각 클러스터간의 거리를 나타내는데, 위로 올라갈 수 록 클러스터가 병합되는 것을 볼 수 있다.




즉 적정 y 값에서 클러스터링을 멈추면 n개의 군집 까지만 클러스터링이 되는데, 위의 그림은 y 값을 3에서 클러스터링을 멈춰서 총 3개의 클러스터로 구분을 한 결과이다.


이렇게 계층형 분석에서 sklearn을 사용할 경우 fcluster 함수를 이용하면, 특정 y값에서 클러스터링을 멈출 수 있다. 다음 코드를 보자.


from scipy.cluster.hierarchy import fcluster

predict = pd.DataFrame(fcluster(mergings,3,criterion='distance'))
predict.columns=['predict']
ct = pd.crosstab(predict['predict'],labels['labels'])
print(ct)


앞의 코드에서 계층형 클러스터링을 한 mergings 변수를 fcluster 함수에 전달하고 두번째 인자에 y의 임계값을 3으로 지정하였다. Predict 컬럼에는 원본 입력데이타에 대한 예측 결과 (어느 클러스터에 속해있는지를 0,1,2로 입력 데이타의 수만큼 리턴한다.)를 리턴한다.


이를 원본 데이타의 라벨인 labels[‘label’]값과 Cross tabulation 분석을 해보았다.




세로축이 예측 결과, 가로측이 원래 값이다.

원래 label이 0인 데이타와 1인 데이타는 각각 잘 분류가 되었고, 2인 데이타는 34개만 정확하게 분류가 되었고 16개는 원본 레이블이 1인 데이타로 분류가 되었다.


지금까지 Hierachical clustering model에 대해서 알아보았다. K Means와 같은 군집화 모델이라도 내부 알고리즘에 따라서 군집화 결과가 다르기 때문에, 샘플 데이타의 분포를 보고 적절한 클러스터링 모델을 고르는 것이 필요하다. 다행이 sklearn의 경우 복잡한 수식 이해 없이도 간단한 라이브러리 형태로 다양한 클러스터링 모델 사용할 수 있도록 해놨기 때문에, 여러 모델을 적용해가면서 적정한 데이타 분류 방식을 찾아보는 것이 어떨까 한다.




클러스터링 #1 - KMeans

빅데이타/머신러닝 | 2017.10.09 22:41 | Posted by 조대협

클러스터링과 KMeans를 이용한 데이타의 군집화

조대협 (http://bcho.tistory.com)

클러스터링 문제

클러스터링은 특성이 비슷한 데이타 끼리 묶어주는 머신러닝 기법이다. 비슷한 뉴스나 사용 패턴이 유사한 사용자를 묶어 주는것과 같은 패턴 인지나, 데이타 압축등에 널리 사용되는 학습 방법이다.

클러스터링은 라벨링 되어 있지 않은 데이타를 묶는 경우가 일반적이기 때문에 비지도학습 (Unsupervised learning) 학습 방법이 사용된다.


클러스터링 알고리즘은 KMeans, DBSCAN, Hierarchical clustering, Spectral Clustering 등 여러가지 기법이 있으며, 알고르즘의 특성에 따라 속도나 클러스터링 성능에 차이가 있기 때문에, 데이타의 모양에 따라서 적절한 클러스터링 알고리즘을 선택하는 것이 중요하다. 다음은 sklearn에 나와 있는 각 클러스터링 알고리즘의 성능에 대한 비교표이다.



출처 : http://scikit-learn.org/stable/auto_examples/cluster/plot_cluster_comparison.html#sphx-glr-auto-examples-cluster-plot-cluster-comparison-py


이 글에서는 클러스터링 알고리즘 중에서 간단하게 사용할 수 있는 KMeans와 Hierachical Clustering 알고리즘을 파이썬 sklearn 라이브러리를 이용하여 설명한다.


KMeans

KMeans 클러스터링 알고리즘은 n개의 중심점을 찍은 후에, 이 중심점에서 각 점간의 거리의 합이 가장 최소화가 되는 중심점 n의 위치를 찾고, 이 중심점에서 가까운 점들을 중심점을 기준으로 묶는 클러스터링 알고리즘이다.

아래 그림을 보면 3개의 군집이 존재하는 것을 볼 수 있다. 각 군집별로 중심점이 찍혀 있는데, 이 중심점의 위치를 움직여 가면서 각 군집의 데이타와 중심점의 거리가 가장 작은 중심점을 찾는 것이다.



이 중심점은 결국 각 군집의 데이타의 평균값을 위치로 가지게 되는데, 이런 이유로 Means(평균) 값 알고리즘이라고 한다.


IRIS 데이타를 이용한 KMeans Clustering

그러면 파이썬 sklearn 라이브러리를 이용하여 IRIS 데이타를 KMeans 알고리즘을 이용하여 클러스터링 해보자

Iris 데이타는 붓꽃의 데이타를 머신러닝 학습용으로 잘 정리해놓은 테스트 데이타 셋으로 꽃잎(Petal)의 크기와 꽃받침(Petal)의 크기에 따라 Iris 꽃의 종류를 분리해놓았다.

이 Iris 데이타는 sklearn 라이브러리 안에 샘플 데이타로 제공되고 있다. 이 데이타셋에는 세가지 붓꽃의 종류별로 50장, 총 150장의 데이타를 샘플로 제공한다.



출처 : https://www.google.co.kr/url?sa=i&rct=j&q=&esrc=s&source=images&cd=&ved=0ahUKEwi0u5aAxePWAhXCNpQKHbTlAWwQjRwIBw&url=https%3A%2F%2Fwww.datacamp.com%2Fcommunity%2Ftutorials%2Fkeras-r-deep-learning&psig=AOvVaw2LZqoz0__VGKTODVDAbJnu&ust=1507638255303298


전체 소스 코드는 https://github.com/bwcho75/dataanalyticsandML/blob/master/Clustering/1.%20KMeans%20clustering-IRIS%202%20feature.ipynb 에 있다.


먼저 Iris 데이타를 로딩해보자


데이타를 로딩한 후에, 이 예제에서는 두개의 속성만 사용해서 분류하기로 해보자.  “Sepal length”와 “Sepal width” 컬럼 두개만 추출하여 학습용 feature라는 데이타 프레임으로 학습용 데이타를 만든다. Iris 데이타는 skearn.datasets에 들어있고 이를 로딩하려면 iris = datasets.load_iris()를 하면 로딩이 된다.

데이타는 로딩된 iris 데이타의 iris.data 필드에 들어가 있고, label은 iris.labels 컬럼에 들어가 있다.


from sklearn import datasets

import pandas as pd

iris = datasets.load_iris()


labels = pd.DataFrame(iris.target)

labels.columns=['labels']

data = pd.DataFrame(iris.data)

data.columns=['Sepal length','Sepal width','Petal length','Petal width']

data = pd.concat([data,labels],axis=1)

feature = data[ ['Sepal length','Sepal width']]

feature.head()




다음 K Means 라이브러리를 이용하여 학습을 시켜보자.


from sklearn.cluster import KMeans

import matplotlib.pyplot  as plt

import seaborn as sns


# create model and prediction

model = KMeans(n_clusters=3,algorithm='auto')

model.fit(feature)

predict = pd.DataFrame(model.predict(feature))

predict.columns=['predict']


sklearn.cluster에서 KMeans 라이브러리를 import 한후에, KMeans 객체를 생성하여 model에 저장한다. 이때 3개의 클러스터로 데이타를 군집화할것이기 때문에, 인자로 n_clusters=3으로 클러스터의 수를 정해준다.

model.fit(학습데이타)를 실행하면 학습 데이타를 이용하여 클러스터링을 위한 학습을 시작하고 학습 데이타에 맞는 중심점 3개를 추출해낸다. 이 학습이 된 모델을 가지고 model.predict(데이타) 를 수행하면 데이타를 학습된 모델에 맞춰서 군집화를 해서 어느 클러스터로 군집화가 되었는지 라벨을 리턴해준다.


클러스터링시, 클러스터의 라벨은 자동으로 0,1,2로 지정되는데, 이 순서는 학습을 할때 마다 임의로 변경이 될 수 있다.  클러스터링 된 라벨과 Sepal length, Sepal width를 하나의 데이타 프레임 r에  저장해서 출력해보자


# concatenate labels to df as a new column

r = pd.concat([feature,predict],axis=1)

시각화

K Means를 이용해서 클러스터링된 데이타를 Scatter plot을 이용해서 시각화 해보자


plt.scatter(r['Sepal length'],r['Sepal width'],c=r['predict'],alpha=0.5)


Scatter plot을 이용하여 클러스터링된 데이타를 그리고, 각 클러스터링 된 데이타를 라벨 (0,1,2)에 따라 색을 다르게 표시한다.

그리고 각 클러스터의 중심점을 붉은 색으로 점을 찍어서 나타내자.

클러스터별 중심점은 model.clsuter_centers 값에 저장이 된다. 중심점을 읽어서 center_x, center_y에 에 각 클러스터의 중심점 좌표를 저장하고 출력하자


centers = pd.DataFrame(model.cluster_centers_,columns=['Sepal length','Sepal width'])

center_x = centers['Sepal length']

center_y = centers['Sepal width']

plt.scatter(center_x,center_y,s=50,marker='D',c='r')

plt.show()


그래프로  출력된 결과는 다음과 같다.




데이타 스케일링를 통한 학습 데이타 정재

학습 데이타의 각 속성의 값이 범위가 크게 차이가 나면 머신러닝 학습이 잘 안되는 경우가 있는데, 예를 들어 속성 A의 범위가 1~1000이고, 속성 B의 범위가 1~10이면, 학습이 제대로 되지 않을 수 있다. 그래서 각 속성의 값의 범위를 동일하게 맞추는 것을 스케일링 (Feature scaling)이라고 한다


그림 좌측은 스케일링전의 원본 데이타, 우측은 데이타는 모든 속성을 0~1 사이로 조정한 결과이다. .

( 데이타 스케일링 대한 내용은 http://bcho.tistory.com/tag/data%20frame 참고 )



여러가지 알고리즘이 있는데 여기서 사용하는 스케일링 방법은 속성의 모든 값을 0~1 사이로 만들어주는 StandardScaling 방법을 사용한다.


즉 학습이 되기전에 데이타를 StandardScaler를 이용하여 스케일링을 조정한 후에, 스케일된 데이타를 KMeans 모델에 넣어서 학습 시키는 방법으로 두 단계를 거치는데, 이렇게 여러 단계를 거쳐서 데이타가 정재되고 학습되는 것을 파이프라인이라고 하고, sklearn.pipeline을 이용하여 손쉽게 구현이 가능하다.

아래 코드를 보자


from sklearn.pipeline import make_pipeline

from sklearn.preprocessing import StandardScaler

from sklearn.cluster import KMeans


scaler = StandardScaler()

model = KMeans(n_clusters=3)

pipeline = make_pipeline(scaler,model)


먼저 StandardScaler 객체 scaler를 만든 후, KMeans 모델 객체를 model로 선언한다. 다음에 make_pipeline 메서드를 이용하여 scaler 아 kmeans 모델을 순차로 실행하도록 파이프라인을 만든다.


pipeline.fit(feature)

predict = pd.DataFrame(pipeline.predict(feature))


다음 pipeline.fit과 .predict 메서드를 이용하여 모델을 학습 시키고 예측을 수행한다.

위의 iris 예제의 경우 스케일링을 적용하더라도 크게 모델의 정확도가 향상된것을 확인할 수 없는데, 이유는 Sepal length의 범위가 4~8, Sepal width의 범위가 2~5로 각 범위의 편차가 크지 않기 때문에 스케일링이 효과가 없다.

Inertia value를 이용한 적정 군집수 판단

K Means를 수행하기전에는 클러스터의 개수를 명시적으로 지정해줘야 한다. 데이타를 2개로 군집화할것인지, 3개로 할것인지등을 정해야 하는데, 몇개의 클러스터의 수가 가장 적절할지는 어떻게 결정할 수 있을까? Inertia value 라는 값을 보면 적정 클러스터 수를 선택할 수 있는 힌트를 얻을 수 있는데, Inertia value는 군집화가된 후에, 각 중심점에서 군집의 데이타간의 거리를 합산한것이으로 군집의 응집도를 나타내는 값이다, 이 값이 작을 수록 응집도가 높게 군집화가 잘되었다고 평가할 수 있다.


이 inertia value는 KMeans 모델이 학습된 후에, model.inertia_ 값으로 뽑아 볼 수 있다.

다음은 iris 데이타를 가지고 1~6개의 클러스터로 클러스터링을 했을때, 각 클러스터 개수별로 inertia value를 출력해보는 코드이다.


ks = range(1,10)

inertias = []


for k in ks:

   model = KMeans(n_clusters=k)

   model.fit(feature)

   inertias.append(model.inertia_)

   

# Plot ks vs inertias

plt.plot(ks, inertias, '-o')

plt.xlabel('number of clusters, k')

plt.ylabel('inertia')

plt.xticks(ks)

plt.show()


다음은 출력된 그래프이나. Inertia 값이 급격하게 하강해서 3~5사이에서는 변화의 폭이 크지 않은 것을 볼 수 있다.


이 값을 보면, iris 데이타는 3~5개의 클러스터로 분류하는 것이 적절하다고 판단할 수 있다.

크로스 테이블 체크를 이용한 모델 판단

클러스터링 모델을 검증하는 방법이 inertia 값을 사용하는 방법도 있지만 학습용 데이타가 라벨링이 되어 있는 경우에는 Cross tabulation (교차 분석)를 통해서 모델을 검증할 수 있다.

Cross tabulation 은 Pandas 라이브러리의 .crosstab 함수를 이용하면 쉽게 수행이 가능하다.


ct = pd.crosstab(data['labels'],r['predict'])

print (ct)


다음은 iris 모델에 대한 교차 분석 결과 인데



새로 축이 원본 데이타의 라벨링 된 값을 나타내고 가로가 KMeans로 인해서 클러스터링 된 결과이다.

원래 라벨 값이 0 인 값이  KMeans 에서 클러스터링 된 결과 predict값을 보면, 2 로 결과가 나온것이 50개이다. 즉 49개는 제대로 분류했다는 이야기지만, label이 1로 된 데이타는 38 제대로 분리되고 12개는 잘못 분리된것을 볼 수 있다. 그리고 마지막으로 label이 2인 데이타는 35개가 제대로 분리되고 15개는 제대로 분리되지 않았음을 볼 수 있다.

KMeans 알고리즘의 문제점

K Means 알고리즘은 사용이 편하고 속도가 비교적 빠른 알고리즘인데 비해서 몇가지 문제점을 가지고 있다. 먼저 클러스터의 수를 정해줘야 하고, 결정적으로 K Means에서는 중심점을 측정할때 처음에 랜덤으로 중심점의 위치를 찾기 때문에,  잘못하면, 중심점과 점간의 거리가 Global optimum 인 최소 값을 찾는 게 아니라 중심점이 Local optimum 에 에 수렴하여 잘못된 분류를 할 수 있다는 취약점을 가지고 있다.



출처 : http://www.cenaero.be/Page.asp?docid=27087&langue=EN


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



MySQL 클러스터링을 위한 Galera Cluster

아키텍쳐 | 2015.11.18 23:52 | Posted by 조대협

MySQL Galera Replication


조대협 (http://bcho.tistory.com)


RDBMS 오픈소스 중에서 단연 가장 많이 사용되는 것은 MySQL인데, 근래에 웹 스케일이 커지면서, 단일 인스턴스로만 서비스가 불가능한 용량까지 가게 되서, 이 MySQL에 대한 클러스터링 스케일링에 대한 이슈가 많아졌다. 이에 Tungsten, MySQL Replication, NDB, Galera 등 다양한 클러스터링 방법이 있는데, 그중에서 갈레라 클러스터링 (Galera Clustering)에 대해서 간단하게 정리하고자 한다.


MySQL Replication


갈레라 클러스터링을 이해하기에 앞서서 먼저 가장 널리(그리고 쉽게) 사용되는 MySQL Replication 방식에 대해서 알아보자. MySQL Replication 방식은 Master/Slave 방식의 구성이 일반적이며, 이 구성의 경우 특정 노드는 쓰기를 담당하고 나머지 노드는 읽기를 담당하는 형태로 구성이 된다.

통상적으로 데이타 베이스 트랜젝션의 60~80%가 읽기 트렌젝션이기 때문에, 이러한 구조를 사용하더라도 충분히 성능의 향상을 기대할 수 있다.


다음 그림은 MySQL Replication 의 간단한 구조도 이다.

 




먼저 좌측의 Master Node에 쓰기 트렌젝션이 수행되면 Master node는 데이타를 저장하고, 트렌젝션에 대한 로그를 내부적으로 BIN LOG라는 파일에 저장한다. (시간 순서대로 수행한 업데이트 트렌젝션이 기록되어 있다.)


Slave Node에서는 이 BIN LOG를 복사해온다. 이 복사 작업을 IO Thread라는 스레드가 수행하는데, 이렇게 읽어온 내용은 Replay Log라는 파일에 기록이 된다. 이렇게 기록된 내용은 SQL Thread라는 스레드가 읽어서, 하나씩 수행을 해서  MySQL 데이타 파일에 기록을 한다.


쉽게 설명하면, insert 쿼리를 master node에서 실행했으면 그 쿼리가 master node의 bin log에 기록이 되고, 이 내용은 slave node에 복사가 된후에, slave node에서 같은 쿼리가 수행이 되서 복제가 반영되는 방식이다.


방식이 단순해서 신뢰도가 높은 반면, 단점으로는

  • 읽기와 쓰기 노드를 분리해야 하며,
  • 데이타 복제가 동기 방식이 아닌 비동기 방식으로 적용된다. 바꿔서 말하면, master node에 적용한 데이타 변경사항이 slave에 반영될때까지 일정 시간이 걸린다는 것으로, master와 slave node간의 순간적인 데이타 불일치성이 발생할 수 있다는 것이다.


Galera cluster


Galera cluster는 http://galeracluster.com/ 에서 제공되는 오픈소스로, 동기방식의 복제 구조를 사용하고 있다.

간단하게 구조를 살펴보자 아래 그림을 보면 




각각의 노드가 있을때, 아무 노드에나 쓰기나 업데이트가 발생하면, 모든 노드에 데이타를 복사를 완료하고 나서, 업데이트 내용이 파일에 저장된다. 아키텍쳐상의 구조를 보면, 위의 그림과 같이 각 MySQL 노드에는 WSREP 라는 모듈이 있다. 이 모듈은 데이타베이스에 복제를 위한 범용 모듈로 여기에 마치 드라이버처럼 Galera replication module을 연결해주면 데이타 변경이 있을때 마다, 이 Garela replication module이 다른 mysql node로 데이타를 복제한다.


약간 더 구체적인 구조를 살펴보면 노드간의 데이타 복제는 다음과 같은 흐름을 따르게 된다. 





노드에 트랜젝션이 발생하고 COMMIT이 실행이되면, 디스크에 내용을 쓰기 전에 다른 노드로 복제를 요청하고 다른 노드에 복제 요청이 접수되었을때, 해당 노드의 디스크에 실제로 데이타를 쓰게 된다.


이러한 특성으로, 전체 노드에 데이타가 항상 일관성있게 저장되고, 모든 노드가 마스터 노드로 작동을 하며, 특정 노드가 장애가 나더라도 서비스에 크게 문제가 없다. 

(MySQL Replication의 경우 마스터 노드가 장애가 나면 슬레이브 노드중 하나를 마스터로 승격을 해야하는 등 다소 운영 프로세스가 갈레라에 비해서는 복잡하다.)


상당히 좋아 보이는 구조이기는 한데, 반대로 가지는 단점도 만만하지 않다.


성능

먼저 성능적인 부분에서, 데이타를 디스크에 저장하기 전에, 다른 모든 노드에 데이타 복제 요청을 해야 하기 때문에, 비동기 방식의 MySQL Replication에 비해서, 쓰기 성능이 떨어지는 것으로 보인다.


장애 전파

이렇게 다른 노드에 복제 요청을 하는 클러스터 구조의 경우, 장애를 다른 노드로 전파 시킬 가능성이 높은데, 예전에 대표적인 웹 애플리케이션 서버인 웹로직의 경우 유사한 세션 클러스터링 구조를 사용했다. 

이 경우 복제를 요청했을때 복제 요청을 받은 노드가 장애 상황 특히 느려지거나 일시적으로 멈췄으때, 복제를 요청한 노드가 응답을 받지 못하고 대기하게 되고, 이 대기한 노드에 다른 노드가 복제를 또 요청하면, 같은 이유로 복제가 지연 되면서 클러스터를 타고 장애가 전파되는 현상을 야기하게 된다.

그래서 갈레라 클러스터의 경우 LOCK문제가 생기거나 슬로우 쿼리들이 많이 발생할때 장애를 전파시킬 수 있는 잠재적인 문제를 가지고 있다.


스케일링의 한계

갈레라가 모든 노드에 데이타를 복제하고 트렌젝션을 끝내는 만큼, 전체적인 노드수가 많아지게 되면, 복제를 하는데 그만큼 시간이 많이 걸림에 따라, 하나의 클러스터에서 유지할 수 있는 노드의 수가 한계가 있어져서, 횡적 스케일링의 한계가 올 수 있다. 


이런 단점에도 불구하고, 모든 노드에 읽기 쓰기가 가능한 멀티 마스터 구조와 모든 노드의 데이타를 일관적으로 유지 시켜준다는 장점과 쉬운 설정 방법으로 인하여 MySQL 클러스터를 구성한다면 한번쯤 검토해봐야 하는 솔루션이 아닌가 한다.


(아쉽게도 국내 사례는 그다지 많지 않은듯...)


몇가지 참고 사항

  • 갈레라 클러스터는 서로 다른 MySQL 버전간에도 클러스터로 묶을 수 있다.
  • 갈레라 클러스터에서 노드가 떨어졌다가 붙으면 일정 부분은 GTID (Global Transaction ID)를 이용하여, 데이타가 복제 되지 않은 델타 부분만 복제가 가능하지만, 시차가 오래되 버리면 풀 백업본을 가져다 엎어야 한다. (풀백업은 복구는 시간이 많이 걸림)




'아키텍쳐' 카테고리의 다른 글

MySQL 클러스터링을 위한 Galera Cluster  (3) 2015.11.18
요구 사항 정의 기법  (0) 2013.11.13
소프트웨어 개발팀의 구조  (0) 2013.11.01
Technical Debt  (1) 2013.10.30
License Key Management  (0) 2013.08.01
암호화 알고리즘 속도 비교 (대칭키)  (0) 2013.07.17

빠르게 훝어보는 node.js

#13 - Socket.IO 클러스터링

조대협 (http://bcho.tistory.com)


node.js 노드가 하나가 아니라 여러개의 프로세스를 이용해서 운영할 때,socket.io를 어떻게 사용해야 할까? 이런 멀티 프로세스를 지원하기 위해서, node.js는 내부적으로 redis store를 지원한다. redis에는 publish/subscribe라는 기능이 있는데, 마치 메세지 큐처럼 메세지를 subscriber로 보낼 수 있는 기능이다.

아래 그림을 보자,하나의 node프로세스에서 메세지를 보내면, 다른 프로세스로 redis를 통해서 메세지를 전달한다. 이때 메세지를 보내는 프로세스는 redis에 메세지를 “publish”하고 나머지 프로세스들은  “subscribe”를 이용하여 메세지를 읽어드린다. 이때, 메세지를 전달하는 채널은 “dispatch”라는 이름의 채널을 이용한다.



 

그러면 실제로, socket.io에서 redis store를 사용하려면 어떻게 해야 할까? 간단한 설정만으로 가능하다. 아래와 같이 redis client를 생성한 후에, socket.io set 명령을 이용하여 store redis client로만 지정해주면 된다.


var httpServer =http.createServer(app).listen(process.argv[2], function(req,res){

    console.log('Socket IO server has been started listen:'+process.argv[2]);

});

// upgrade http server to socket.io server

var io = socketio.listen(httpServer);

var pub = redis.createClient(6379,'127.0.0.1');

var sub = redis.createClient(6379,'127.0.0.1');

var store = redis.createClient(6379,'127.0.0.1');

 

io.set('store',new socketio.RedisStore({

    redis: redis

    ,redisPub : pub

    ,redisSub : sub

    ,redisClient : store

}));

 


그리고, cluster 모듈을 이용하거나, 앞단에 nginx(http:// http://nginx.org/ ) haproxy (http://haproxy.1wt.eu/)  로드밸런서를 이용하여 여러개의 node.js 프로세스에 대한 end point를 하나로 묶으면, 대규모 분산 서비스를 할 수 있는 socket.io 클러스터를 구성할 수 있다.