[Data] 범주형 변수의 Clustering

범주형 변수를 Clustering 할 수 있을것인가?

참고자료
[1] Zhexue Huang, A Fast Clustering Algorithm to Cluster Very Large Categorical Data Sets in Data Mining
[2] Zhexue Huang, Extensions to the k-Means Algorithm for Clustering Large Data Sets with Categorical Values
[3] https://medium.com/geekculture/the-k-modes-as-clustering-algorithm-for-categorical-data-type-bcde8f95efd7
[4] https://www.analyticsvidhya.com/blog/2021/06/kmodes-clustering-algorithm-for-categorical-data/

들어가기

Clustering 여러 기법들 중에 DBSCAN이나 K-Means, 계층적 군집화 등을 생각해 볼 수 있다. 이들은 모두 기본적으로 '거리'를 기준으로 군집을 나누는 시도를 하는 알고리즘들이다. 즉 '거리'를 계산해야만 하는 상황이다.

하지만 범주형 변수에서는 거리를 계산할 수가 없을 것이다. 특히 범주형 변수 자체에 우열도 없기 때문에 거리를 논하는 것 자체가 의미가 없다.

Remark. 
0-1 Encoding을 통해서 거리를 계산할 수 있지 않느냐? 라고 말할 수 있을 것이다.
그런데... 다음을 생각해보자.
예를들어, 10개의 0-1 Encoding된 데이터만 가지고 있는 데이터셋이 있다고 하자.
여기에 1~2개의 변수만 1인 케이스가 거의 대부분이라고 하면, 이들간의 거리는 거의 유사할 것이다.

즉, 아무리 여기서 K-Means 등을 써봤자, 거리 자체가 거의 동등하기 때문에 무력화가 되버린다.

극복 : K - Modes

이를 위해서 K - Modes를 도입한다. 이름에서 추론 가능하듯, K - Modes는 최빈값을 기반으로 한 K - Means 알고리즘의 변형이다. 범주형 변수들간의 비교를 통해 최빈값을 통해 중심점을 지정하고, 이를 토대로 클러스터를 찾아가는 방법이다.

K - Modes Algorithm의 개요

K - Modes Algorithm은 다음 과정대로 진행된다.

1) 최초 k개의 데이터를 선택하여 각 하나의 cluster에 할당한다.
2) 각 데이터들별로 cluster의 center들과 dissimilarity(비일치도)를 계산한다.
3) 비일치도를 계산 후 데이터별로 어느 cluster로 할당할지 새로 갱신한다.
   기존에 배치한 cluster 대비, 더 낮은 비일치도를 가진 cluster가 있을 경우 해당 cluster로 갱신한다.
4) cluster의 중심점을 새로 계산한다. 이 때 각 cluster에 할당된 점들의 mean을 계산하여 해당 데이터를 중심점으로 둔다.
5) 2 ~ 4를 반복한다. 이 때, 모든 pointer들의 cluster가 더 이상 갱신되지 않을 경우 알고리즘을 종료한다.

비일치도 (dissimilarity)

여기서 비일치도는 다음과 같이 둔다.

즉, 일치하지 않은 변수에 대해 페널티를 부과하는 지표라고 생각하면 된다.

 

K 값에 대한 결정

K - Modes의 경우에도 K - Means 처럼 K 값을 직접 지정해줘야 하는 부분이 있다.
elbow method를 사용하여, 최적의 K값을 찾아보는 시도를 할 수 있을 것이다.

 

생각해봐야 할 점들

1) 최빈값을 계산하는데, 동률인 경우에 대해서는 어떻게 생각해 주어야 할까..?
2) binary 변수들 위주로 이루어진 data set에 대해서도 좋은 효과를 낼 수 있을까..?

 

Example_code

https://github.com/SeongwonTak/TIL_swtak/blob/master/DataScience/K_Modes%20Clustering.ipynb

GitHub - SeongwonTak/TIL_swtak: Today, I learned.

단순한 예제를 통해 간단한 사용방법을 익혀보았다... 실제 현재 진행하고 있는 Fraud  detection 에 적용해볼 예정이다.