K-means in Machine Learning

Customer Segmentation

  머신러닝 기법 중, 비지도학습의 일종으로서 K-means 기법이 있습니다. 이번 포스트에서는, K-means 알고리즘을 이해하고, 직접 구현하여 sklearn library와 비교를 해보겠습니다. 물론 성능에 있어 최적의 조건을 보장하는 sklearn library가 더 우위에 있겠지만, 알고리즘을 완벽히 이해하고 사용하는데 이번 포스트의 목적을 두겠습니다.

  내용이 조금 길 수 있으나, 알고리즘의 설명과 주석을 통해 순차적으로 이해해주시길 바랍니다. 그리고 본 포스팅의 순서는 다음과 같이 진행됩니다.

1) 직접 구현한 알고리즘과 sklearn의 k-means 제시

2) 두 방법으로 도출된 군집(k=3)의 중심점 비교

3) wcss를 통해 k값의 기준을 확립

4) 군집에 따라 파생특징으로부터 도출된 dataframe을 plotting할 것입니다.

K-means 알고리즘

1) n차원 공간에서, k개의 중심값을 임의로 선택

2) 중심에서 각 샘플 데이터까지의 거리를 계산 ex) np.linalg.norm(Data_i - Centroid_k,axis=1)

3) 각 데이터 포인트를 가장 가까운 중심점에 할당하여 클러스터 갱신

4) 각 중심점에 선택된 데이터 포인트들의 평균위치로 중심점을 다시 이동

5) 위 과정을 '수렴할 때(중심점의 변화가 거의 없어 할당된 군집이 변화가 없을 때)' 까지 반복

K-means의 단점 중 하나로 알고리즘이 수렴하지 않는 문제가 발생할 수 있는데, 이를 피할 수 있도록 initialization method를 "random"이 아닌 "k-means++"을 이용하기로 합니다. k-means++알고리즘은 초기 seed를 최적화하는 알고리즘 입니다.

또한, K값과 군집에 대한 해석은 분석자의 감에 많이 의존하는 문제도 있습니다. 이를 방지하기 위해 군집을 직접 "Plotting" 해보거나 "Within Cluster Sum of Squared(Cluster inertia)를 K값 별로 구하여 elbow point를 찾는 것"도 많은 도움이 됩니다.

class kmeans:       

     def __init__(self,k,input):

         self.k=k

         self.df=input

         self.C=None

#k개의 중심값을 임의로 선택한다.

     def centroids(self):

         import random

         C={

         i+1:[data for data in self.df.values[i]]

         for i,j in zip(range(self.k),random.sample(range(len(self.df)),self.k))}

         return C

#각 중심에서 데이터까지의 거리를 계산 using np.linalg.norm

#각 데이터에 가장 가까운 중심점(군집)을 할당

     def classify(self,C):

         import copy

         clsuter_df=copy.deepcopy(self.df)

         col_n=clsuter_df.shape[1]

         for i in C.keys():

             clsuter_df["Distance_from_{}".format(i)]\

             =np.linalg.norm(np.array(clsuter_df)[:,:col_n]-C[i],

             axis=1)

         dist_cols=["Distance_from_{}".format(i) for i in C.keys()]

         clsuter_df["Closet_Cluster"]=clsuter_df.loc[:,dist_cols].idxmin(axis=1).map(lambda x:int(x.lstrip("Distance_from_")))

         return clsuter_df

#각 중심점에 선택된 데이터 포인터들의 평균위치로 중심점을 재이동

     def update(self,C):                           

         c_df=self.classify(C)                  

         self.C={

         i:[c for c in np.mean(self.df[c_df["Closet_Cluster"]==i],axis=0)]

          for i in c_df["Closet_Cluster"].unique()}

         return self.C

#위 과정을 '갱신된 중심점이 거의 변화가 없어 할당된 군집이 바뀌지 않을 만큼' 반복

     def train_cluster(self):

         assignments=None

         C=self.centroids()

         while True:

             #중심점에 해당되는 군집 찾기

             cluster_df=self.classify(C)

             new_assignments=list(self.classify(C)["Closet_Cluster"])

             #새로운 중심점 찾기

             new_C=self.update(C)

             #'할당된 군집'이 바뀌지 않을 만큼 중심점이 수렴했다면 종료

             if assignments==new_assignments:

                 break

             #아니라면 다시 중심점과 군집 찾기

             assignments=new_assignments

             C=new_C

         return new_C,list(new_assignments)

#test_data

>> group=pd.read_csv("group.csv",header=0)

>> group=group[["mean","var","size"]]

>> model1=kmeans(3,group)

>> from sklearn.cluster import KMeans

>> model2=KMeans(n_clusters=3,init="k-means++").fit(group)

>> model1.train_cluster()[0] #중심점 using algorithm made by me!

>> model2.cluster_centers_ #중심점 using sklearn

>> model1.train_cluster()[2] #거리와 군집을 포함한 cluster_df

직접 구현한 알고리즘을 통한 각 군집의 중심점들이 sklearn과 같은 결과를 보여줍니다.

  직접 구현한 알고리즘과 sklearn을 통해 K-means 머신러닝 기법을 시도해 보았습니다. 위 과정은 K값을 3이라 가정하고 진행하였지만, 어떠한 기준도 없이 K값을 선택하는 것은 사실 매우 어려운 일입니다. 물론 이전 포스트들에서 진행했던 '데이터 탐색'이 매우 큰 도움이 될 수 있습니다.

  평점의 기준, 평점에 대한 호불호, 영화의 인상도(or 영화에 대한 관심도)에 대한 EDA를 시도한 결과, '영화로부터 어느 정도의 인상을 받았는지'가 마케팅 요소에 가장 중요하다고 판단되었습니다. 따라서 이러한 중요 척도에 따라 (충성층, 충성가망층, 일반층) 3가지로 분류할 수 있다고 가정할 수 있었습니다.

  그러나 이 방법 외에, WCSS(Within Cluster Sum of Squares)을 Plotting함으로써 K값에 대한 보다 확실한 기준을 얻을 수 있습니다.

WSSC

def ssd(input,n_k): #sum_of_squared_distance using algorithm made by me!      

     dist_list=[]

     for i in range(1,n_k+1):

         fit=kmeans(i,input)

         C=fit.train_cluster()[0]

         C_df=fit.classify(C)

         dist=[np.sum(C_df.loc[C_df["Closet_Cluster"]==j,"Distance_from_{}".format(j)]**2)

         for j in [c for c in C.keys()]]

         dist_list.append(np.sum(dist))

     return dist_list,range(1,n_k+1)

def elbow(x,n_k): #sum_of_squared_distance using sklearn

    sse=[]

    for i in range(1,n_k+1):

        km=KMeans(n_clusters=i,init="k-means++").fit(x)

        sse.append(km.inertia_)

    return sse, range(1,n_k+1)

## plotting Within_cluster sum of suqares(= Cluster inertia) to choose 'K'

def wcss(input,k):

     import seaborn as sns

     import matplotlib.pyplot as plt

     Info=elbow(input,k)

     plt.plot(Info[1],Info[0],marker="o",color="c")

     plt.xticks(Info[1])

     plt.xlabel("K")

     plt.ylabel("Total Squared Error")

     plt.title("Within #Cluster sum of squares")

     plt.show()

>>%timeit wcss1(group,10)#18.6s per loop

>>%timeit wcss2(group,10)#2.16s per loop

  직접 작성한 k-means알고리즘과 sklearn을 활용하여 WCSS plotting을 시도한 결과, 거의 같은 양상을 확인할 수 있습니다. elbow point가 K=3이라는 사실을 알 수 있으며 탐색한 결과로부터 예상했던 것과 다르지 않습니다. 다음으로, K=3일 때 파생특징으로부터 도출된 dataframe이 어떠한 군집 형태를 띠고 있는지 확인해보겠습니다.

## K=3인 DataFrame 3D plotting

>> from mpl_toolkits.mplot3d import Axes3D

>> fig=plt.figure(facecolor='w')

>> ax=Axes3D(fig,rect=[0,0,1,1],elev=30,azim=120)

>> ax.set_xlabel('mean')

>> ax.set_ylabel('var')

>> ax.set_zlabel('size')

>> model2=KMeans(3,init="k-means++",random_state=0).fit(group)

>> labels=pd.Series(model2.labels_,dtype="category")

>> labels=labels.cat.rename_categories(["loyalist","big_spender","new_potentials"])

>> c0,c1,c2=model1.train_cluster()[0].values()

>> cluster=(0,1,2)

>> col=("b","g","r")

>> mark=("v","^","o")

>> center=(c0,c1,c2)

for cluster,col,mark,center in zip(cluster, col, mark,center):

      ax.scatter(group.iloc[model1.train_cluster()[1]==cluster,0],\

     group.iloc[model1.train_cluster()[1]==cluster,1],\

     group.iloc[model1.train_cluster()[1]==cluster,2],\

     s=5,marker=mark,c=col)

>> plt.legend(labels.unique()) #[new_potentials,big_spender,loyalist] 

>> plt.show()

  결과적으로, 이 dataframe은 3개의 군집으로 잘 나뉜 것을 확인할 수 있습니다. 또한, "Size(영화로부터의 인상도 또는 영화에 대한 관심도)"가 3개의 군집을 분류하는데 가장 중요한 척도임을 알 수 있습니다. 물론 단위의 표준화를 시도하지 않아 그 영향이 없었다고 말할 수는 없습니다. 하지만, 이 자체로도 우리에게 고객을 분류할 수 있는 합리적인 근거를 발견할 수 있습니다. EDA와 군집을 통해 분류된 고객 집단을 보다 자세히 정의해보겠습니다.

영화를 꾸준히 관람 vs 영화를 가끔 관람

size 高, var 低 :  먼저, 이 집단은 영화를 꾸준히 관람하는 라이프스타일을 지녔습니다. 따라서 다른 집단에 비해, '받은 인상에 따라 특정 관람자는 더 많은 횟수의 평점을 부여' 했습니다. 그리고 이들의 대부분은 영화의 만족도(or 호불호)가 크게 변하지 않습니다.

size 低, var 高 : 이들은 위 집단과 정 반대되는 집단입니다. 영화의 평점을 부여하는 활동 자체가 적다보니, 영화를 관람하는 횟수 자체도 적을 수 밖에 없습니다. 따라서 영화의 평점은 본인의 만족도에 크게 치우치는 편입니다. 

  ROI관점에서 영화의 매출에 긍정적 기여를, 또한 그 특성에 따라 Buzz마케팅을 도울 수 있는 '1등 고객'은 첫번째 관람객 집단임을 쉽게 판별할 수 있습니다. 우리는 이 관람객들을 앞으로 충성층이라 부를 것이며, 관람객들을 총 3분류로서 (Loyalist, Big_Spender, New_Potential)으로 구분하겠습니다.

  그리고 실제로 관람객들이 이렇게 '3가지로 분류된 집단'에 속하고 있음을 전제로 다음 포스트들을 진행하겠습니다. 바로 다음 포스트는, PCA를 통해 차원축소 및 important feature extraction작업을 시도해보겠습니다.