군집화 - K-Mean, DBSCAN 소개
이번 포스팅에서는 군집화에 대해 알아보겠습니다.
군집화(Clustering)
군집화(Clustering)는 주어진 데이터들에 대해 유사도를 파악해 그룹으로 묶는 것을 의미합니다.
이때, 군집화는 분류(classification)과 비슷하다고 볼 수 있습니다.
하지만 군집화는 특정한 독립변수와 종속변수의 구분을 하지 않고, 학습을 위한 목표 값도 필요로 하지 않아 비지도 학습으로 분류됩니다.
쉽게 말하자면 분류는 정답이 주어졌을 때 그 라벨을 기반으로 데이터를 나누는 것이고, 군집화는 라벨이 주어지지 않고 데이터 값의 특징을 보고 묶는 방법이라는 것입니다.
군집화는 라벨이 없어 어떤 라벨이 속할지 예측하기 보다는 하나의 어떻게 묶일 수 있다의 가능성을 찾기 위해 사용합니다.
따라서 그 목적과 방법에 따라 다양하게 종류가 나뉩니다.
그 중 이번 시간에는 보편적으로 사용되는 두 모델에 대해 간략하게 설명하고 scikit-learn 라이브러리를 사용한 결과 비교를 해보도록 하겠습니다.
- K-Mean (K-평균 군집화)
- DBSCAN
K-Mean Clustering
K-Mean Clustering은 각 군집의 평균을 활용해 데이터를 K 개의 군집으로 묶는 군집화 알고리즘입니다.
여기서 사용되는 군집의 평균 값은 각 군집의 중심과 데이터들의 평균 거리를 의미합니다.
작동원리는 다음과 같습니다.
<작동원리>
1. 군집 개수 설정
데이터를 몇 개의 군집으로 설정할 것인지 사용자가 결정합니다.
이때, 군집의 개수를 설정하는 것은 K-Mean Clustering의 성능에 큰 영향을 미칩니다.
따라서 군집의 개수를 결정하기 위한 방법론이 존재하는데, 이를 사용자가 결정해야 한다는 점은 K-Mean Clustering의 한계점으로 꼽히기도 합니다.
-
군집 개수 설정 방법
- Rule of thumb
- Elbow Methd
- 정보 기준 접근법(Information Criterion Approach)
2. 초기 중심점 결정
초기 중심점을 역시 성능이 크게 달라집니다.
따라서 초기 중심점 결정을 위한 방법론 역시 존재합니다.
다양한 방법 중 실제로 많이 사용되는 방법은 K-Means ++ 방법 입니다.
해당 방법은 보통 초기 첫 값은 랜덤으로 설정 후 K개의 중심이 선택될때까지
- 각 중심과 가장 가까운 데이터와의 거리를 계산하고,
- 확률이 해당 거리의 제곱에 비례하는 편중 확률 분포를 사용해 임의의 데이터를 선정해 다음 중심으로 설정하는 과정을 반복한다.
3. 데이터를 군집에 할당
거리 상 가장 가까운 군집으로 주어진 모든 데이터를 할당합니다.
4. 중심점 재 설정
모든 주어진 데이터에 배정 후 군집의 중심점을 군집에 속하는 데이터들의 중간 위치의 값으로 재지정 합니다.
5. 데이터를 군집에 재 할당 후 중심점의 위치가 더 이상 바뀌지 않을 때까지 반복 수행
재 지정된 중심을 중심으로 3번부터의 과정을 다시 시작합니다.
해당 과정은 현재의 중심점 위치와 할당 후 재 계산한 중심점의 위치가 같을 때까지 반복해서 수행합니다.
DBSCAN
또 하나의 소개할 군집화 알고리즘인 DBSCAN은 데이터의 밀집도를 이용한 군집화 방법입니다.
여기서 DBSCAN에서 전제조건으로 사용하는 내용은 특정 요소가 군집에 속하기 위해서는 다른 요소들과의 거리가 가까워야 한다는 점 입니다.
이에, DBSCAN은 데이터의 군집의 형태를 상관하지 않고 초기 데이터로부터 근접한 데이터를 찾아 나가는 방법으로 확장합니다.
특히 군집의 개수를 미리 정하지 않아도 군집할 수 있다는 장점이 있습니다.
단, DBSCAN에서 필요로 하는 값은 같은 군집으로 여길 최소 거리, 그리고 군집이라고 볼 수 있는 군집 속 데이터의 갯수입니다.
작동원리는 다음과 같습니다.
<작동원리>
1. 최소거리(epsilon)와 최소 데이터 수 설정
각 값들은 사용자가 설정합니다.
2. 임의의 점을 선택해 핵심 데이터, 경계 데이터
핵심 데이터는 설정한 최소 거리 안의 영역에 존재하는 데이터의 개수가 최소 데이터 수 이상이면 그 데이터를 핵심 데이터로 설정합니다.
이때의 값들은 임의로 선정한 데이터이며, 반복적으로 선정해 탐색 과정을 수행합니다.
이를 위해 다음과 같은 탐색 알고리즘들을 사용합니다.
- 탐색 알고리즘
- brute force
- KD Tree
핵심 데이터가 정해지면 그 데이터를 기준으로 최소 거리 안에 겹치는 요소들을 경계 데이터로 설정합니다.
해당 과정은 탐색 알고리즘으로 선정한 데이터들을 모두 돌아다니며 탐색해 각 군집을 생성합니다.
3. 이상 데이터(Noise Point) 설정
2번의 과정에서 핵심 데이터에도 경계 데이터에도 속하지 못한 값들은 이상 데이터로 설정합니다.
4. 최소거리 이내의 핵심 데이터를 연결 후 모든 경계 데이터를 하나의 군집으로 할당
2, 3과정을 통해 각각 핵심 데이터, 경계 데이터, 이상 데이터가 설정되면 각 군집 간 거리가 최소 거리 이하의 범위인 경우에 하나의 군집으로 판단해 합칩니다.
K-Mean vs DBSCAN
이러한 K-Mean Clustering과 DBSCAN Clustering은 그 결과가 전혀 다르게 나옵니다.
다음은 두 군집화 알고리즘의 결과를 도식화한 결과입니다.
K-Mean Clustering은 군집을 직접 설정해 마치 데이터가 하나의 형상을 보임에도 같은 데이터라고 판단하지 않는 경우들이 있습니다.
반면에 DBSCAN은 사람이 판단하는 하나의 형상과 같이 분류하여 데이터의 군집을 이해하기 쉽습니다.
하지만, K-Mean에서는 평균을 사용하기 때문에 이상치에 민감하다는 장점이 있습니다.
성능 기준
이러한 군집화 방식에는 K-Mean, DBSCAN 이외에도 Affinity Propagation, Hierarchical, Spectral 등 다양하게 존재합니다.
이러한 군집화의 성능은 분류문제와는 달리 원래의 데이터의 군집이 어떤지 모르기 때문에 성능을 판단하기 힘듭니다.
따라서 분류문제와는 다른 성능 기준을 다양하게 제시하고 있습니다.
-
조정 랜드 지수(ARI : Adjusted Rand Index)
랜드지수는 가능한 모든 데이터 쌍의 개수에 대해 정답인 데이터 쌍의 개수의 비율을 말합니다.
랜드지수는 0~1 사이의 값을 갖으며 1에 가까울수록 좋은 성능을 의미합니다.
이러한 랜드지수의 기대값을 원래의 값에서 빼서 기댓값과 분산을 재조정한 것이 바로 조정 랜드 지수 입니다.
-
조정 상호 정보량(Adjusted Mutual Information)
상호 정보량은 두 확률변수 간 상호의존성을 측정한 값입니다.
두 확률변수가 서로 독립인 경우 상호 정보량의 값은 0이며 의존성이 강할수록 상호정보량이 증가합니다.
이때, 군집의 개수가 많아져도 상호정보량이 올라가 올바른 비교가 어려워 조정 랜드 지수에서와 같이 각 경우에 따른 상호정보량의 기댓값을 빼서 재조정한 조정 상호 정보량을 사용합니다.
앞선 두 방법의 경우 성능 측정을 위해서 각 데이터가 어떤 군집에 속해있는지에 대한 groundtruth 값을 알고 있는 경우에 대한 성능 측정 방식입니다.
하지만 groundtruth 값이 없는 경우에서 사용할 수 없는 경우에 대한 성능 평가 기준도 필요합니다.
다음은 이러한 경우에 군집화 성능평가 기준 중 하나입니다.
-
실루엣 계수(Silhouette Coefficient)
모든 데이터 쌍에 대해 거리 혹은 비유사도를 구해 모든 데이터에 대해 각 군집에 속한 원소끼리의 평균집합 a와 다른 군집 중 가장 가까운 군집까지의 거리 b를 구해 다음의 수식을 구한 것이 실루엣 계수 입니다. \(s_i = b_i - a_i / max(a_i, b_i)\) 전체 데이터의 실루엣계수의 평균을 구하면 평균 실루엣계수라고 합니다.
만약 데이터에 대해 같은 군집의 데이터가 다른 군집의 데이터보다 더 가까우면 그 데이터의 실루엣 계수는 양수가 되고 좋은 군집화로 평가되며 그 반대의 경우는 음수로 잘못된 군집화라고 평가합니다.
즉, 실루엣 계수가 클수록 좋은 군집화가 이루어졌다고 평가합니다.
군집화 방법 중 군집의 개수를 정해야 하는 알고리즘들이 있는데, 실루엣계수는 그 경우 군집의 개수를 정하는데 큰 도움이 됩니다.
이번 포스팅에서는 군집화에 대한 정의와 가장 대표되는 알고리즘인 K-Mean 군집화와 DBSCAN 군집화에 대해 알아보았습니다.
또한 각 군집화 알고리즘들에 대해 자주 사용되는 성능평가인 ARI, AMI, 실루엣계수에 대해 알아보았습니다.
<참고 자료="">
[1] https://datascienceschool.net/03%20machine%20learning/16.01%20%EA%B5%B0%EC%A7%91%ED%99%94.html
[2] https://velog.io/@jhlee508/%EB%A8%B8%EC%8B%A0%EB%9F%AC%EB%8B%9D-K-%ED%8F%89%EA%B7%A0K-Means-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
[3] https://syj9700.tistory.com/40
[4] https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html