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


Archive»


 
 

클러스터링 #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을 정의하지 않고도 사용이 가능하다.



오토 인코더를 이용한 신용카드 비정상 거래 검출 

#3 학습 데이타 전처리


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




앞의 글들 (http://bcho.tistory.com/1198 http://bcho.tistory.com/1197 ) 에서 신용카드 이상 검출을 하기 위한 데이타에 대한 분석과, 오토 인코더에 대한 기본 원리 그리고 오토 인코더에 대한 샘플 코드를 살펴보았다.


이제 실제 모델을 만들기에 앞서 신용카드 거래 데이타를 학습에 적절하도록 전처리를 하도록한다.

데이타양이 그리 크지 않기 때문에, 데이타 전처리는 파이썬 데이타 라이브러리인 pandas dataframe을 사용하였다. 여기서 사용된 전처리 코드는 https://github.com/bwcho75/tensorflowML/blob/master/autoencoder/creditcard_fraud_detection/2.data_normalization.ipynb 에 공개되어 있다.


데이타 전처리 과정

신용카드 거래 데이타를 머신러닝 학습의 검증과 테스트에 적절하도록 다음과 같은 절차를 통하여 데이타를 전처리하여 CSV 파일로 저장하였다.

데이타 정규화

학습 데이타에 여러가지 피쳐를 사용하는데, 예를 들어 피쳐 V1의 범위가 -10000~10000이고, 피쳐 V2의 범위가 10~20 이라면, 각 피쳐의 범위가 차이가 매우 크기 때문에, 경사 하강법등을 이용할때, 학습 시간이 더디거나 또는 제대로 학습이 되지 않을 수 있다. 자세한 내용은 김성훈 교수님의 모두를 위한 딥러닝 강좌중 정규화 부분  https://www.youtube.com/watch?v=1jPjVoDV_uo&feature=youtu.be 을 참고하기 바란다.

그래서 피쳐의 범위를 보정(정규화)하여 학습을 돕는 과정을 데이타 정규화라고 하는데, 정규화에는 여러가지 방법이 있다. 여기서 사용한 방법은 Fearture scaling이라는 방법으로, 모든 피쳐의 값들을 0~1사이로 변환하는 방법이다. 위에서 언급한 V1은 -10000~10000의 범위가 0~1사이로 사상되는 것이고, V2도 10~20의 범위가 0~1사이로 사상된다.

공식은 아래와 같은데



참고 https://en.wikipedia.org/wiki/Normalization_(statistics)


정규화된 값은 = (원본값 - 피쳐의 최소값) / (피쳐의 최대값 - 피쳐의 최소값)


으로 계산한다.

앞의 V1값에서 0의 경우는 (0 - (-10000)) / (10000 - (-10000)) = 0.5 로 사상이 되는것이다.


그러면 신용카드 데이타에서 V1~V28 컬럼을 Feature scaling을 위해서 정규화를 하려면

df_csv = pd.read_csv('./data/creditcard.csv')

CSV에서 원본 데이타를 읽는다.

읽어드린 데이타의 일부를 보면 다음과 같다.


df_csv 는 데이타의 원본값을 나타내고,  df_csv.min() 각 컬럼의 최소값, df_csv.max()는 각 컬럼의 최대값을 나타낸다. 이 값들을 이용하여 위의 Feature Scaling 공식으로 구현하면 아래와 같이 된다


df_norm = (df_csv - df_csv.min() ) / (df_csv.max() - df_csv.min() )


이렇게 정규화된 값을 출력해보면 다음과 같다.




V1 컬럼의 -1.359807이 정규화후에 0.935192 로 변경된것을 확인할 수 있고 다른 필드들도 변경된것을 확인할 수 있다.

데이타 분할

전체 데이타를 정규화 하였으면 데이타를 학습용, 검증용, 테스트용 데이타로 나눠야 하는데, 오토 인코더의 원리는 정상적인 데이타를 학습 시킨후에, 데이타를 넣어서 오토인코더가 학습되어 있는 정상적인 패턴과 얼마나 다른가를 비교하는 것이기 때문에 학습 데이타에는 이상거래를 제외하고 정상적인 거래만으로 학습을 한다.

이를 위해서 먼저 데이타를 정상과 비정상 데이타셋 두가지로 분리한다.

아래 코드는 Class=1이면 비정상, Class=0이면 정상인 데이타로 분리가 되는데, 정상 데이타는 df_norm_nonfraud에 저장하고, 비정상 데이타는 df_norm_fraud에 저장하는 코드이다.

# split normalized data by label
df_norm_fraud=df_norm[ df_norm.Class==1.0] #fraud
df_norm_nonfraud=df_norm[ df_norm.Class==0.0] #non_fraud


정상 데이타를 60:20:20 비율로 학습용, 테스트용, 검증용으로 나누고, 비정상 데이타는 학습에는 사용되지 않고 테스트용 및 검증용에만 사용되기 때문에, 테스트용 및 검증용으로 50:50 비율로 나눈다.


# split non_fraudfor 60%,20%,20% (training,validation,test)
df_norm_nonfraud_train,df_norm_nonfraud_validate,df_norm_nonfraud_test = \
   np.split(df_norm_nonfraud,[int(.6*len(df_norm_nonfraud)),int(.8*len(df_norm_nonfraud))])


numpy의 split 함수를 쓰면 쉽게 데이타를 분할 할 수 있다. [int(.6*len(df_norm_nonfraud)),int(.8*len(df_norm_nonfraud))] 가 데이타를 분할하는 구간을 정의하는데,  데이타 프레임의 60%, 80% 구간을 데이타 분할 구간으로 하면 0~60%, 60~80%, 80~100% 구간 3가지로 나누어서 데이타를 분할하여 리턴한다. 같은 방식으로 아래와 같이 비정상 거래 데이타도 50% 구간을 기준으로 하여 두 덩어리로 데이타를 나눠서 리턴한다.


# split fraud data to 50%,50% (validation and test)
df_norm_fraud_validate,df_norm_fraud_test = \
   np.split(df_norm_fraud,[int(0.5*len(df_norm_fraud))])

데이타 합치기

다음 이렇게 나눠진 데이타를 테스트용 데이타는 정상과 비정상 거래 데이타를 합치고, 검증용 데이타 역시 정상과 비정상 거래를 합쳐서 각각 테스트용, 검증용 데이타셋을 만들어 낸다.

두개의 데이타 프레임을 합치는 것은 아래와 같이 .append() 메서드를 이용하면 된다.


df_train = df_norm_nonfraud_train.sample(frac=1)
df_validate = df_norm_nonfraud_validate.append(df_norm_fraud_validate).sample(frac=1)
df_test = df_norm_nonfraud_test.append(df_norm_fraud_test).sample(frac=1)

셔플링

데이타를 합치게 되면, 테스트용과 검증용 데이타 파일에서 처음에는 정상데이타가 나오다가 뒷부분에 비정상 데이타가 나오는 형태가 되기 때문에 테스트 결과가 올바르지 않을 수 있는 가능성이 있다. 그래서, 순서를 무작위로 섞는 셔플링(Shuffling) 작업을 수행한다.

셔플링은 위의 코드에서 .sample(frac=1)에 의해서 수행되는데, .sample은 해당 데이타 프레임에서 샘플 데이타를 추출하는 명령으로 frac은 샘플링 비율을 정의한다 1이면 100%로, 전체 데이타를 가져오겠다는 이야기 인데, sample()함수는 데이타를 가지고 오면서 순서를 바꾸기 때문에, 셔플링된 결과를 리턴하게 된다.


전체 파이프라인을 정리해서 도식화 해보면 다음과 같다.


다음글에서는 이렇게 정재된 데이타를 가지고 학습할 오토인코더 모델을 구현해보도록 한다.


Wide and deep network 모델 활용하기

빅데이타/머신러닝 | 2017.07.20 17:12 | Posted by 조대협


Wide & deep model 알아보기

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

Wide & deep model

이글에 설명된 예제는 https://www.tensorflow.org/tutorials/wide_and_deep  문서에 있는 코드를 활용하였습니다. 음식 검색 키워드와 검색 결과를 학습 시킨 후에 이 결과를 기반으로 사용자에게 음식을 추천해주는 서비스가 있다고 하자.

Monetization and Wide model (기억과 와이드 모델)

로지스틱 회귀 모델을 이용하여 추천 알고리즘을 작성하여 학습을 시킨 경우, 학습 데이타를 기반으로 상세화된 예측 결과를 리턴해준다. 예를 들어 검색 키워드 (프라이드 치킨)으로 검색한 사용자가 (치킨과 와플)을 주문한 기록이 많았다면, 이 모델은 (프라이드 치킨)으로 검색한 사용자는 항상 (치킨과 와플)을 추천해주게 된다.  즉 예전에 기억된 값 (Memorization된 값)을 통해서 예측을 하는데, 이러한 모델을 와이드 모델이라고 한다.



<그림 와이드 모델 >

그러나 (프라이드 치킨)으로 검색한 사용자에게 같은 패스트 푸드 종류인 햄버거나 프렌치프라이등을 추천해도 잘 구매가 되지만 와이드 모델은 기존에 기억된 결과로만 추천을 하기 때문에 이러한 결과를 얻기가 어렵다.


Generalization and Deep model (일반화와 딥모델)

뉴럴네트워크 모델의 경우 프라이드 치킨을 햄버거, 프랜치 프라이등을 일반화 시켜서 패스트 푸드로 분류하여 프라이드 치킨으로 검색을 해도 이와 같은 종류의 햄버거를 추천해도 사용자가 택할 가능성이 높다.


<그림 딥 모델>


이러한 모델을 딥모델이라고 하는데, 딥 모델의 경우 문제점이, 너무 일반화가(under fitting)  되서 엉뚱한 결과가 나올 수 있다는 것인데, 예를 들어서 따뜻한 아메리카노를 검색했는데, 커피라는 일반화 범주에서 아이스 라떼를 추천해줄 수 있다는 것이다. 즉 커피라는 일반화 범주에서 라떼는 맞는 추천일 수 있지만, 따뜻한 음료를 원하는 사람에게 차가운 음료를 추천하는 지나친 일반화가 발생할 수 있다.


그래서 이런 문제를 해결하기 위해서 와이드 모델과 딥모델을 합친 “Wide & deep model”이라는 것을 구글이 개발하였고 이를 구글 플레이 스토어에 적용한 결과, 큰 효과를 얻었다고 한다. (https://arxiv.org/abs/1606.07792)


<그림 와이드 앤 딥모델 >


모델 사용 방법

이 모델이 텐서플로우에서 tf.contrib.learn 패키지에 라이브러리 형태로 공개가 되었다.

Classification 용은 tf.contrib.learn.DNNLinearCombinedClassifier

Regression 용은 tf.contrib.learn.DNNLinearCombinedRegressor

를 사용하면 된다.


이 라이브러리들은 텐서플로우의 Esimator API (https://www.tensorflow.org/extend/estimators)인데, 복잡한 알고리즘을 구현할 필요 없이 불러다 쓸 수 있는 하이레벨 API 이면서 학습에서 중요한 다음 두가지를 도와준다.

  • 분산러닝
    멀티 GPU나 멀티 머신에서 분산학습을 하려면 직접 텐서플로우 코드를 써서 작업 분산 및 취합 작업을 해줘야 하는데, Estimator API를 사용할 경우 Experiment API 를 통해서 Google CloudML 인프라 상에서 이런 작업을 자동으로 해준다.

  • 모델 EXPORT
    그리고 학습된 모델은 운영환경에서 예측용으로 사용할때, 모델을 Export 하여 Tensorflow Serving 과 같은 예측 엔진에 배포해야 하는데, 모델을 Export 하려면, 예측에 사용할 텐서플로우 그래프를 다시 그려주고 변수 값을 채워넣는 것에 대한 코드를 작성해야 하는데 (자세한 설명은 http://bcho.tistory.com/1183 문서 참조), 이 역시도 자동화를 해준다.


자 이제 머신러닝 모델은  있으니 여기에 데이타 즉 적절한 피쳐만 제대로 넣어서 학습을 시키면 되는데, 와이드 모델과 딥모델 각각 학습 하기 좋은 피쳐가 따로 있다.

와이드 모델 학습용 피쳐

와이드 모델에는 카테고리(분류)와 같은 비연속성을 가지는 데이타가 학습에 적절하다. 카테고리성 컬럼의 경우에는 다음과 같이 크게 두 가지가 있다.

Sparse based column

성별, 눈동자의 색깔과 같이 비연속성을 지니는 값으로 학습에 사용하려면 이를 벡터화를 해야 한다.

예를 들어 남자 = [1,0] 여자는 = [0,1] 식으로 또는 검정눈 = [1,0,0], 갈색눈 = [0,1,0], 푸른눈 = [0,0,1] 식으로 벡터화할 수 있다.

이때는 다음과 같이 sparse_column_with_keys라는 메서드를 써주면 위와 같은 방식으로 인코딩을 해준다.

gender = tf.contrib.layers.sparse_column_with_keys(column_name="gender", keys=["Female", "Male"])

만약에 나이와 같이 연속형 데이타라도 이를 10대,20대,30대와 같이 구간으로 나눠서 비연속성 분류 데이타로 바꾸고자 할 경우에는 다음과 같이 bucketized_column을 사용하면 된다.

age_buckets = tf.contrib.layers.bucketized_column(age, boundaries=[18, 25, 30, 35, 40, 45, 50, 55, 60, 65])

Crossed column

다음은 crossed column 이라는 피쳐인데, 예를 들어 교육 수준과, 직업이라는 피쳐가 있다고 하자. 이를 각각의 독립된 변수로 취급할 수 도 있지만, 교육수준과 직업에 상관 관계가 있다고 할때 이를 관계를 묶어서 피쳐로 사용할 수 있다. 예를 들어 대졸 사원의 연봉, 컴퓨터 프로그래머의 연봉과 같이 독립된 특징으로 보는것이 아니라 대졸 컴퓨터 프로그래머, 대학원졸 컴퓨터 프로그래머와 같은 상관 관계를 기반으로 피쳐를 사용할 수 있는데 이를 Crossed column이라고 한다. Cross column은 다음과 같이 crossed_colmn이라는 메서드를 이용해서 정의할 수 있다.

tf.contrib.layers.crossed_column([education, occupation], hash_bucket_size=int(1e4))

딥 모델 학습용 피쳐

딥 모델용 학습데이타는 연속성을 가지는 데이타가 적절하다.

Continuous column

Continuous column은 일반적인 연속형 데이타 변수이고 간단하게 real_valued_column 메서드를 정해서 다음과 같이 정의가 가능하다.

age = tf.contrib.layers.real_valued_column("age")

Embedding column

문장의 단어들을 학습 시키기 위해서 각 단어를 벡터로 표현하고자 할때 , 예를 들어 boy = [1,0,0,0..], girl=[0,1,0,...] 으로 단어 하나를 하나의 숫자로 1:1 맵핑을 시킬 수 있다. 그러나 이 경우 이 단어가 다른 단어와 어떤 상관 관계를 갖는지 표현이 불가능하다. 예를 들어 남자:소년=여자:?? 라는 관계식을 줬을때, 위의 방식으로는 단어간의 관계를 유추할 수 없기 때문에, ?? 를 찾아낼 수 없다. 즉 컴퓨터가 “단어가 다른 단어와 어떤 차이점과 공통점”을 가지는지 이해할 수가 없다는 단점이 존재한다.

이런 문제를 해결하기 위해서 단어를 다차원 공간에서 벡터로 표현하여 각 단어간의 관계를 표현할 수 있는 방법을 만들었다.

이와 같은 원리로 어떤 비연속된 카테고리 피쳐들을 숫자로 맵핑할때, 위의 boy,girl 과 같은 방식 (on_hot_encoding) 으로 의미없이 1:1 맵핑을 하는 것이 아니라, 각 카테고리들이 어떠한 연관 관계를 가질때 이 연관성을 표현하여 벡터값으로 변환하는 방법을 임베딩 (embedding)이라고 한다.


그래서 카테고리내의 값들이 서로 연관성을 가질때는 임베딩을 이용하여 벡터 값으로 변경을 한 후, 이 값을 딥모델에 넣어서 학습하면 좋은 결과를 얻을 수 있다. 카테고리화된 값을 임베딩하기 위해서는 아래와 같이 embedding_column이라는 메서드를 사용하면 된다.


tf.contrib.layers.embedding_column(education, dimension=8)

피쳐를 모델에 넣는 방법

위와 같은 방법으로 분리되고 변경된 피쳐는, Wide & deep model에서 각각 와이드 모델과, 딥모델로 주입되서 학습되게 된다.

아래와 같이 피쳐를 와이드 컬럼과 딥 컬럼으로 구별한 후에, 리스트에 넣는다.

wide_columns = [
 gender, native_country, education, occupation, workclass, relationship, age_buckets,
 tf.contrib.layers.crossed_column([education, occupation], hash_bucket_size=int(1e4)),
 tf.contrib.layers.crossed_column([native_country, occupation], hash_bucket_size=int(1e4)),
 tf.contrib.layers.crossed_column([age_buckets, education, occupation], hash_bucket_size=int(1e6))

deep_columns = [
 tf.contrib.layers.embedding_column(workclass, dimension=8),
 tf.contrib.layers.embedding_column(education, dimension=8),
 tf.contrib.layers.embedding_column(gender, dimension=8),
 tf.contrib.layers.embedding_column(relationship, dimension=8),
 tf.contrib.layers.embedding_column(native_country, dimension=8),
 tf.contrib.layers.embedding_column(occupation, dimension=8),
 age, education_num, capital_gain, capital_loss, hours_per_week]

다음 딥모델용 피쳐 리스트와 와이드 모델용 피쳐 리스트를 DNNLinearCombinedClassifier 에 각각 변수로 넣으면 된다. 이때 딥 모델은 뉴럴네트워크이기 때문에, 네트워크의 크기를 정해줘야 하는데 아래 코드에서는 각각 크기가 100인 히든 레이어와 50인 레이어 두개를 넣어서 구성하도록 하였다.

m = tf.contrib.learn.DNNLinearCombinedClassifier(
   model_dir=model_dir,
   linear_feature_columns=wide_columns,
   dnn_feature_columns=deep_columns,
   dnn_hidden_units=[100, 50])



지금 까지 아주 간단하게 나마 Wide & deep model에 대한 이론 적인 설명과 이에 대한 구현체인 DNNLinearCombinedRegressortf.contrib.learn.DNNLinearCombinedClassifier 에 대해서 알아보았다.  이 정도 개념만 있으면 실제 Wide & deep model 튜토리얼을 이해할 수 있으니, 다음은 직접 튜토리얼을 참고하기 바란다. https://www.tensorflow.org/tutorials/wide_and_deep


Reference


Hashtable의 이해와 구현 #1

프로그래밍/알고리즘 | 2016.02.06 02:40 | Posted by 조대협

해쉬 테이블의 이해와 구현 (Hashtable)


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


기본적인 해쉬 테이블에 대한 이해


해쉬 테이블은 Key Value를 저장하는 데이타 구조로, value := get(key)에 대한 기능이 매우매우 빠르게 작동한다. 개발자라면 자주 쓰는 데이타 구조지만, 실제로 어떻게 작동하는지에 대해서 정확하게 알고 있지는 모르는 경우가 많다. 이 글에서는 해쉬 테이블에 대한 기본적인 구조와, 구현 방식에 대해서 설명 하도록 한다.

 

해쉬 테이블의 기본적인 개념은 다음과 같다.

이름을 키로, 전화 번호를 저장하는 해쉬 테이블 구조를 만든다고 하자.  전체 데이타 양을 16명이라고 가정하면

 

John Smith의 데이타를 저장할때, index = hash_function(John Smith) % 16  를 통해서 index 값을 구해내고, array[16] = John Smith의 전화 번호 521-8976”을 저장한다.



(출처 :https://en.wikipedia.org/wiki/Hash_table )

 

이런 형식으로 데이타를 저장하면, key에 대한 데이타를 찾을때, hash_function을 한번만 수행하면 array내에 저장된 index 위치를 찾아낼 수 있기 때문에, 데이타의 저장과 삭제가 매우매우 빠르다.

 

충돌 처리 방식에 따른 알고리즘 분류

 

그런데, 이 해쉬 테이블 문제는 근본적인 문제가 따르는데, hash_function(key) / size_of_array의 값이 중복이 될 수 가 있다.

 

예를 들어 저장하고자 하는 key가 정수라고 하고, hash_function key%10 이라고 하자. 그리고 size_of_array 10일때, key 1,11,21,31은 같은 index 값을 가지게 된다. 이를 collision (충돌)이라고 하는데, 이 충돌을 해결하는 방법에 따라서 여러가지 구현 방식이 존재한다.

 

1. Separate chaining 방식

 

JDK내부에서도 사용하고 있는 충돌 처리 방식인데, Linked List를 이용하는 방식이다.

index에 데이타를 저장하는 Linked list 에 대한 포인터를 가지는 방식이다.



(출처 :https://en.wikipedia.org/wiki/Hash_table )

 

만약에 동일  index로 인해서 충돌이 발생하면 그 index가 가리키고 있는 Linked list에 노드를 추가하여 값을 추가한다.  이렇게 함으로써 충돌이 발생하더라도 데이타를 삽입하는 데 문제가 없다.

 

데이타를 추출을 하고자할때는 key에 대한 index를 구한후, index가 가리키고 있는 Linked list를 선형 검색하여, 해당 key에 대한 데이타가 있는지를 검색하여 리턴하면 된다. 

삭제 처리


key를 삭제하는 것 역시 간단한데, key에 대한 index가 가리키고 있는 linked list에서, 그 노드를 삭제하면 된다.

Separate changing  방식은 Linked List 구조를 사용하고 있기 때문에, 추가할 수 있는 데이타 수의 제약이 작다.

 

참고 : 동일 index에 대해서 데이타를 저장하는 자료 구조는 Linked List 뿐 아니라, Tree를 이용하여 저장함으로써, select의 성능을 높일 수 있다. 실제로, JDK 1.8의 경우에는 index에 노드가 8개 이하일 경우에는 Linked List를 사용하며, 8개 이상으로 늘어날때는 Tree 구조로 데이타 저장 구조를 바꾸도록 되어 있다.

 

2. Open addressing 방식

 

Open addressing  방식은 index에 대한 충돌 처리에 대해서 Linked List와 같은 추가적인 메모리 공간을 사용하지 않고, hash table array의 빈공간을 사용하는 방법으로, Separate chaining 방식에 비해서 메모리를 덜 사용한다. Open addressing  방식도 여러가지 구현 방식이 있는데, 가장 간단한 Linear probing 방식을 살펴보자

 

Linear Probing

 

Linear Probing 방식은 index에 대해서 충돌이 발생했을 때, index 뒤에 있는 버킷중에 빈 버킷을 찾아서 데이타를 넣는 방식이다. 그림에서 key % 10 해쉬 함수를 사용하는  Hashtable이 있을때, 그림에서는 충돌이 발생하지 않았다.

 

 


아래 그림을 보자, 그런데, 여기에 11을 키로 하는 데이타를 그림과 같이 넣으면 1이 키인 데이타와 충돌이 발생한다. (이미 index1인 버킷에는 데이타가 들어가 있다.) Linear Probing에서는 아래 그림과 같이 충돌이 발생한 index (1) 뒤의 버킷에 빈 버킷이 있는지를 검색한다. 2번 버킷은 이미 index2인 값이 들어가 있고, 3번 버킷이 비어있기 3번에 값을 넣으면 된다.


검색을 할때, key 11에 대해서 검색을 하면, index1이기 때문에, array[1]에서 검색을 하는데, key가 일치하지 않기 때문에 뒤의 index를 검색해서 같은 키가 나오거나 또는 Key가 없을때 까지 검색을 진행한다. 


삭제  처리


이러한 Open Addressing의 단점은 삭제가 어렵다는 것인데, 삭제를 했을 경우 충돌에 의해서 뒤로 저장된 데이타는 검색이 안될 수 있다. 아래에서 좌측 그림을 보자,  2index를 삭제했을때, key 11에 대해서 검색하면, index1이기 때문에 1부터 검색을 시작하지만 앞에서 2index가 삭제되었기 때문에, 2 index까지만 검색이 진행되고 정작 데이타가 들어 있는 3index까지 검색이 진행되지 않는다.

그래서 이런 문제를 방지하기 위해서 우측과 같이 데이타를 삭제한 후에, Dummy node를 삽입한다. Dummy node는 실제 값을 가지지 않지만, 검색할때 다음 Index까지 검색을 연결해주는 역할을 한다.


Linear probing에 대한 샘플 코드는

http://www.cs.rmit.edu.au/online/blackboard/chapter/05/documents/contribute/chapter/05/linear-probing.html

http://www.tutorialspoint.com/data_structures_algorithms/hash_data_structure.htm

를 참고하기 바란다.

Dummy Node를 이용해서 삭제를 할때, 삭제가 빈번하게 발생을 하면, 실제 데이타가 없더라도 검색을 할때, Dummy Node에 의해서, 많은 Bucket을 연속적으로 검색을 해야 하기 때문에, Dummy Node의 개수가 일정 수를 넘었을때는 새로운 array를 만들어서, 다시 hash를 리빌딩 함으로써, Dummy Node를 주기적으로 없애 줘야 성능을 유지할 수 있다.


Resizing

Open addressing의 경우, 고정 크기 배열을 사용하기 때문에 데이타를 더 넣기 위해서는 배열을 확장해야 한다. 또한 Separate changing에 경우에도 버킷이 일정 수준으로 차 버리면 각 버킷에 연결되어 있는 List의 길이가 늘어나기 때문에, 검색 성능이 떨어지기 때문에 버킷의 개수를 늘려줘야 한다. 이를 Resizing이라고 하는데, Resizing은 별다른 기법이 없다. 더 큰 버킷을 가지는 array를 새로 만든 다음에, 다시 새로운 arrayhash를 다시 계산해서 복사해줘야 한다.


해쉬 함수


해쉬 테이블 데이타 구조에서 중요한 것중 하나가 해쉬 함수(hash function)인데, 좋은 해쉬 함수란, 데이타를 되도록이면 고르게 분포하여, 충돌을 최소화할 수 있는 함수이다. 수학적으로 증명된 여러가지 함수가 있겠지만, 간단하게 사용할 수 있는 함수를 하나 소개하고자 한다. 배경에 대해서는 http://d2.naver.com/helloworld/831311 에 잘 설명되어 있으니 참고하기 바란다. (필요하면 그냥 외워서 쓰자)

String key

char[] ch = key.toChar();

int hash = 0;

for(int i=0;i<key.length;i++)

 hash = hash*31 + char[i]

 

Cache를 이용한 성능 향상


해쉬테이블에 대한 성능 향상 방법은 여러가지가 있지만, 눈에 띄는 쉬운 방식이 하나 있어서 마지막으로 간략하게 짚고 넘어가자. 해쉬테이블의 get(key)put(key)에 간단하게, 캐쉬 로직을 추가하게 되면, 자주 hit 하는 데이타에 대해서 바로 데이타를 찾게 함으로써, 성능을 간단하게 향상 시킬 수 있다.  

다음은 실제로 간단한 HashTable 클래스를 구현하는 방법에 대해서 알아보도록 하겠다. 

dynamic array resizing에 대해서.

프로그래밍/알고리즘 | 2016.02.05 02:52 | Posted by 조대협

알고리즘쪽을 파다보니 재미있는게, 예전에 알았던 자료 구조도 구현 방식등에 대해서 다시 되짚어 볼 수 있는게 좋은데. (그간 생각하던 구현 방식과 다른 방식도 종종 나와서.)


보통 메모리 문제 때문에 불확실한 데이타 크기를 가지는 데이타 구조는 LinkedList를 사용하는게 유리하다고 생각했는데, 내용중에, 배열을 사용하고, 배열이 다 차면 그크기를 늘리는 (새롭게 더 큰 배열을 만들어서 기존 배열 내용을 복사해서 대처 하는것) 방식 (Array Resize)를 봤다.  일반적인 방식이기는 하지만 메모리 소모량이나 배열 복사 속도 때문에 그다지 바람직하다고 생각 안하고 있었는데, JDK내의 Map 클래스의 구현 부분을 보니, 실제로 Map 클래스에서도  array resize를 사용하고 있다.


(출처 : http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap.addEntry%28int%2Cjava.lang.Object%2Cjava.lang.Object%2Cint%29 )

꽉 막혀서 생각할 것이 아니라, 이런 방식도 융통성 있게 고려를 해봐야겠다.



튜토리얼 포인트

자료 구조에 대한 설명과 코드들을 간략하게 잘 정리해 놓음

http://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm 


코세라 프린스턴 알고리즘 강의

https://class.coursera.org/algs4partI-010


코세라 데이타 구조에 대한 강의 (그래프 구조에 대한 문제가 잘 정리되어 있음)

https://class.coursera.org/algs4partI-010


알고리즘에 대한 일반적인 설명 (Algorithm 4th edition)

http://algs4.cs.princeton.edu/


Octree와 QuadTree에 대한 설명 (게임에서의 응용)

http://www.gamedev.net/page/resources/_/technical/game-programming/introduction-to-octrees-r3529


동적 연결 알고리즘 (Dynamic Connectivity)


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


요즘 알고리즘이 대세라 기초를 다지는 차원에서 다시 알고리즘을 보고 있는데, 오늘은 동적 연결 알고리즘에 대해서 공부한 내용을 간략하게 정리해본다.


동적 연결 알고리즘은 노드끼리 연결이 되어 있는지를 찾는 알고리즘이다.

각 도시간에 연결이 되어 있는지, SNS에서 친구끼리 서로 연결이 되어 있는지와 같은 연결성만을 판단한다.


예전에 이러한 문제를 그래프 형태의 자료구조를 이용해서 풀려고 했는데, 여기서 문제의 핵심은 노드 A와 B가 연결되었는지만 판단하면 된다. 즉 자료 구조상에서, 어떤 노드가 어떤 노드와 인접해 있는지등은 표시할 필요가 없다. 아래 그림을 보자, 아래 그림에서 1과 5는 연결이 되어 있다. (1->2->5 경로) 4,2는 연결되어 있지 않다.



이 처럼 노드간의 연결 여부만 판단 하는 것이 동적 연결 알고리즘 (Dynamic Connectivity)문제이다.

 

QuickUnionFind


이를 구현하는데 몇가지 알고리즘이 있는데, 가장 간단한 알고리즘으로는 QucikUnionFind라는 알고리즘이다.

QuickUionFind 알고리즘은 아래와 같이 일차원 배열을 이용해서 구현하는데, 배열의 Index가 노드명, 그 값이 ID이다. ID가 같은 노드들은 서로 연결되어 있는 것으로 취급 한다.



이런식으로 된다. 값이 9,8,7 3의 컴포넌트로 나뉘어 짐을 알 수 있다.

이 알고리즘의 경우 구현은 쉽지만, 매번 연결을 추가할때 마다 ID값을 스캔해서, 같은 컴포넌트에 있는 노드의 ID값을 매번 변경해야 하기 때문에 성능이 매우 낮다. O(N^2)의 복잡도를 갔는다.


Tree (QuickFindUF)


그래서 이를 보완하는 알고리즘으로는 Tree를 사용하는 방법이 있는데, Tree의 값에는 이 노드와 연결된 상위 노드의 인덱스 값을 가지게 한다.

이때 주의해야 하는 것이, Tree에서 표현되는 상하위 노드의 연결 내용은 중요하지 않다. 실제로 그림에서 1,3 노드간에는 연결은 없지만, 필요하다면 Tree에서는 1,3 노드를 연결해서 표현하되, 1,3이 하나의 트리에만 있으면 된다.

헷갈릴 수 있는 부분이, 각 노드간의 연결을 온전히 저장하는 것이 아니라, 컴포넌트에 어떤 노드가 있는지를 저장하는 것이기 때문에, 각 노드 간의 연결성에 초점을 맞출 필요가 없다. 



위의 그래프 저장 결과는 배열에서 다음과 같다.

 



여기서 노드가 연결되어 있는지를 찾으려면, root 노드가 같은지를 비교하면 된다.

즉, 노드 9,5가 연결되어 있는지 찾으려면 9 --> 5 까지의 경로를 트래버스 하는 것이 아니라, 9와 5의 root 노드(1)을 찾아서 동일한지를 비교하면 된다.


WeightTree

위의 트리 기반의 알고리즘의 경우, Depth가 비약적으로 길어질 수 있는 문제가 있는데, 이를 해결하기 위해서는 WeightTree라는 알고리즘을 사용할 수 있다. 이 알고리즘은 두개의 트리를 병합할때, 항상 작은 트리를 큰 트리의 루트에 붙이게 함으로써 전체 트리의 Depth를 줄이는 방법이다.


아마 이 알고리즘을 보지 않았더라면, Dynamic Connectivity 문제도 Node *  기반의 자료 구조를 만들어서 DFS(깊이 우선 검색)으로 해결하려고 하지 않았을까? (성능은 무지 안나오겠지)


참고자료 및 소스

http://algs4.cs.princeton.edu/15uf/

나이브 베이즈 분류 (Naive Bayesian classification) #1 - 소개

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


지금 부터 소개할 알고리즘은, 머신러닝 알고리즘 중에서 분류 알고리즘으로 많이 사용되는 나이브 베이스 알고리즘이다. 


배경 지식

나이브 베이스 알고리즘을 이해하려면 몇가지 배경 지식이 필요하다. 


베이스 정리

먼저 베이스 정리를 보면, 매개 변수, x,y가 있을때,  분류 1에 속할 확률이 p1(x,y)이고, 분류 2에 속할 확률이 p2(x,y)일때, 

  • p1(x,y) > p2(x,y) 이면, 이 값은 분류 1에 속한다.
  • p1(x,y) < p2(x,y) 이면, 이 값은 분류 2에 속한다.
  • 나이브 베이스 알고리즘은 이 베이스의 정리를 이용하여, 분류하고자 하는 대상의 각 분류별 확률을 측정하여, 그 확률이 큰 쪽으로 분류하는 방법을 취한다.

예를 들어, 이메일에 대해서 분류가 스팸과 스팸이 아닌 분류가 있을때, 이메일에 들어가 있는 단어들 w1,…,wn 매개 변수 (“쇼핑”,”비아그라”,”보험”,….)에 대해서,  해당 이메일이 스팸일 확률과 스팸이 아닌 확률을 측정하여, 확률이 높은 쪽으로 판단한다.


조건부 확률

나이브 베이스를 이해하기 위해서는 확률의 개념 중 조건부 확률이란 것을 이해 해야 한다. 존건분 확률 이란, 사건 A에 대해서, 사건 A가 일어났을때, 사건 B가 일어날 확률

“사건 A에 대한 사건 B의 조건부 확률” 이라고 하며, P(B|A)로 표현한다.

예를 들어, 한 학교의 학생이 남학생인 확률이 P(A)라고 하고, 학생이 키가 170이 넘는 확률을 P(B)라고 했을때, 남학생 중에서, 키가 170이 넘는 확률은 B의 조건부 확률이 되며 P(B|A)로 표현 한다.

베이스 규칙

이 조건부 확률을 이용하면, 모르는 값에 대한 확률을 계산할 수 있는데

  • P(A|B) = P(A∩B) / P(B) <- 1)
  • P(B|A) = P(A∩B) / P(A) <- 2)

1),2)를 대입 하면

  • P(A|B)*P(B) = P(B|A)*P(A)
  • P(A|B) = P(B|A)*P(A)/P(B)

앞의 남학생인 확률 P(A)와 키가 170이상인 확률 P(B)를 알고, 남학생중에서 키가 170인 확률 P(B|A)를 알면, 키가 170인 학생중에, 남학생인 확률 P(A|B)를 알 수 있다.


나이브 베이스 알고리즘을 이용한 분류 예


다음과 같이 5개의 학습 문서가 존재하고, 분류가 comedy(코메디 영화), action(액션 영화) 두개가 존재한다고 하자. 

movie

단어(Word)

분류

1

fun,couple,love,love

Comedy

2

fast,furious,shoot

Action

3

Couple,fly,fast,fun,fun

Comedy

4

Furious,shoot,shoot,fun

Action

5

Fly,fast,shoot,love

Action


이제, 어떤 문서에 “fun,furious,fast” 라는 3개의 단어만 있는 문서가 있을 때, 이 문서가 코메디인지 액션 영화인지 분리를 해보자 


해당 영화가 코메디인 확률은

P(comedy|words) = P(words|comedy)*P(comedy)/P(words)  A.1 이며

액션 영화인 확률은

P(action|words) = P(words|action)*P(action)/P(words)  A.2 이 된다.

A.1 > A.2이면, 코메디 영화로 분류하고, A.1<A.2이면 액션 영화로 분리한다.

이때, A.1과 A.2는 모두 P(words)로 나누는데, 대소 값만 비교 하기 때문에 때문에 굳이 P(words)를 구해서 나눌 필요가 없이 

  • P(comedy|words) = P(words|comedy)*P(comedy) <-- B.1
  • P(action|words) = P(words|action)*P(action) <-- B.2

만 구하면 된다. 그러면, B.1과 B.2의 값을 실제로 계산해보자

먼저 각 단어의 빈도수를 계산하면

  • Count (fast,comedy) = 1 (코메디 중, fast 라는 단어가 나오는 횟수)
  • Count(furious,comedy) = 0
  • Count(fun,comedy) = 3
  • Count(fast,action)= 2
  • Count(furious,action)=2
  • Count(furious,action) = 1

P(words|comedy)는 comedy 영화중, 지정한 단어가 나타나는 확률로, 이를 개별 단어로 합치면펼치면 P(fast,furious,fun|comedy)으로, 각 단어가 상호 연관 관계가 없이 독립적이라면 (이를 조건부 독립 conditional independence라고 한다), 


P(fast|comedy)*P(furious|comedy)*P(fun|comedy)로 계산할 수 있다.


이를 계산 해보면, Comedy 영화에서 총 단어의 개수는 9번 나타났기 때문에, 모수는 9가 되고 그중에서 각 단어별로 comedy에서 나타난 횟수는 위와 같이 comedy이면서 fast인것이 1번, comedy 이면서 furious인것이 0번, comedy이면서 fun인것이 3번이 되서, 


P(fast|comedy)*P(furious|comedy)*P(fun|comedy) 는 { (1/9) * (0/9) * (3/9)} 가 된다.


그리고, P(comedy)는 전체 영화 5편중에서 2편이 comedy이기 때문에, P(comedy)=2/5가 된다.

이를 B.1에 대입해보면,

P(comedy|words) = { (1/9) * (0/9) * (3/9)} * 2/5 = 0 이 된다.

같은 방식으로 B.2를 계산하면 액션 영화에서 총 단어수는 11이고, 각 단어의 발생 빈도로 계산을 해보면

P(action|words) = { (2/11) * (2/11)*(1/11) } * 3/5 = 0.0018이 된다.

결과 “P(action|worlds) = 0.0018” > “P(comedy|word) = 0” 이기 때문에, 해당 문서는 액션 영화로 분류가 된다.


Laplace smoothing

위의 나이브 베이스 알고리즘을 사용할때, 하나의 문제점이 학습 데이타에 없는 단어가 나올때이다. 즉 분류를 계산할 문서에 “cars”라는 단어가 있다고 하자, 이 경우 학습 데이타를 기반으로 계산하면, cars는 학습 데이타에 없었기 때문에, P(cars|comedy)와 P(cars|action) 은 모두 0이 되고, P(comedy|words)와 P(action|words)도 결과적으로 모두 0이 되기 때문에, 분류를 할 수 없다.

즉 문서가 “fun,furious,fast,cars”로 되면

P(comedy|words) = { (1/9) * (0/9) * (3/9) * (0/9:cars 단어가 나온 확률) } * 2/5 = 0

P(action|words) = { (2/11) * (2/11)*(1/11) * (0/9:cars 단어가 나온 확률)  } * 3/5 = 0

이를 해결하기 위한 방법이 Smoothing이라는 기법으로, 이 기법은 새로운 단어가 나오더라도 해당 빈도에 +1을 해줌으로써 확률이 0이 되는 것을 막는다

다시 P(x|c)를 보자

 


이렇게 계산했다.

즉, P(“fun”|comedy) = “comedy중 fun”이 나오는 횟수 / “comedy 중 나오는 모든 단어의 수 중 중복을 제거한수” 로 계산했다.

.Laplace smoothing을 하려면 빈도에 1씩을 더해 줘야 하는데, 빈도를 더해주면 공식은

 


같이 된다.

여기서 |V|는 학습 데이타에서 나오는 전체 단어의 수(유일한 개수)가 된다. 위의 학습데이타에서는 fun,couple,love,fast,furious,shoot,fly로 총 7개가 된다.

이 공식에 따라 분자와 분모에 빈도수를 더하면

P(comedy|words) = { (1+1/9+7) * (0+1/9+7) * (3+1/9+7) * (0+1/9+7:cars 단어가 나온 확률) } * 2/5 = 0.00078

P(action|words) = { (2+1/11+7) * (2+1/11+7)*(1+1/11+7) * (0+1/9+7:cars 단어가 나온 확률)  } * 3/5 = 0.0018

※ 수식에서 편의상 (2+1)/(11+7) 등으로 괄호로 묶어야 하나 2+1/11+7과 같이 표현하였으나 분자에 +1, 분모에 +7을 해서 나눈 것으로 계산하기 바란다

로 액션 영화로 판정 된다.


Log를 이용한 언더 플로우 방지


이 알고리즘에서 문제는 P(words|comedy)나 P(words|action)은 각 단어의 확률의 곱으로 계산된다는 것인데, P(fun|comedy)*P(furios|comedy)*…. 각 확률은 <1 이하기이 때문에, 항목이 많은 경우 소숫점 아래로 계속 내려가서, 구분이 어려울 정도까지 값이 작게 나올 수 있다.

이를 해결 하기 위해서 로그 (log)를 사용하면 되는데

log(a*b) = log (a) + log(b)와 같기 때문에,

  • P(comedy|words) = P(words|comedy)*P(comedy)  B.1
  • P(action|words) = P(words|action)*P(action) B.2

양쪽 공식에 모두 Log를 취하면 (어짜피 대소 크기만 비교하는 것이니까)

  • Log(P(comedy|words)) = Log(P(words|comedy)*P(comedy))<-- B.1
  • Log(P(action|words)) = Log(P(words|action)*P(action))<--B.2

가 되고, B.1을 좀 더 풀어보면

Log(P(words|comedy)*P(comedy)) 

= Log(P(fun|comedy)*P(furios|comedy)*…*P(Comedy) ) 

= log(P(fun|comedy))+log(P(furios|comedy)+…+log(P(Comedy)) 로 계산할 수 있다.


위의 자료는 http://unlimitedpower.tistory.com/entry/NLP-Naive-Bayesian-Classification%EB%82%98%EC%9D%B4%EB%B8%8C-%EB%B2%A0%EC%9D%B4%EC%A6%88-%EB%B6%84%EB%A5%98 를 참고하였습니다.