데이터마이닝에 관한 스터디를 진행하고자 정리한 내용입니다. 참고한 자료들은 아래에 따로 정리해두었으며,개인 공부 과정에서 틀린 부분이 있을 수 있습니다. (잘못된 부분은 알려주시면 수정하겠습니다!)
Intro.
지도학습의 대표 격인 트리 기반 모델에 대해 알아봤으니, 이젠 비지도학습 차례입니다. 비지도학습의 대표적인 알고리즘인 클러스터링(clustering)의 세계로 들어가봅시다.
1. 클러스터링 개요
1.1. Background
지도학습은 입력(X)과 정답(Y)이 모두 존재하여 둘의 관계를 찾아내는 것이 목표인 반면, 비지도학습은 정답(Y)없이 입력(X)의 내재적 특징을 찾는 것이 목표였죠. 그중에서도 아래 그림처럼 비슷한 객체끼리 묶어주는 것을 ‘군집화(clustering)’라고 합니다.
이미지 출처 : github.com/pilsung-kang/Business-Analytics-ITS504
군집화(clustering)는 실제 비즈니스 의사결정에서도 많이 사용되는 실용적인 기술로, 아래와 같이 다양한 상황에서 쓸 수 있습니다.
데이터 이해 : 문서들을 주제별로 분류, 유사한 유전자 정보 묶기, 가격이 비슷한 주식 종목 묶기 등
데이터 요약 : 방대한 데이터를 한눈에 확인 가능 = 주로 '시각화'로 연결됨 (ex. 군집화, 시각화 동시에 해주는 Self-Organizing-Map)
전략 수립 : 군집별로 적절한 전략을 계획하는 데 활용 가능 (ex. 자산관리 포트폴리오, 경쟁사와의 특허 비교, 반도체 공정 최적화 등)
ex) 나라별 거시경제 지표들을 군집화 & 시각화한 사례ex) 반도체 웨이퍼 패턴을 군집화하여 불량 형태를 역추적한 사례
1.2. 핵심 아이디어
이제 클러스터링(군집화)이 무엇인지, 그리고 어떻게 활용될 수 있는지 감을 잡으셨을 것 같습니다. 그렇다면, “좋은” 클러스터링이란 무엇일까요? 클러스터링은 비지도 학습이기 때문에, 군집들이 ‘잘’ 분리되었는지 확인할 수 있는 정답(Y)이 없죠. 따라서, 우리는 다음과 같은 대안을 생각해볼 수 있습니다.➡️ “같은 그룹끼리는 비슷하고, 다른 그룹끼리는 차이가 난다면, 잘 분리된 것이다!”
이미지 출처 : github.com/pilsung-kang/Business-Analytics-ITS504
이것이 바로 클러스터링의 핵심 아이디어이며, 이는 아래와 같은 용어로 정리될 수 있습니다.
군집 내 분산(Intra-cluster variance) 최소화 : 같은 그룹끼리는 비슷해야 함.
군집 간 분산(Inter-cluster variance) 최대화 : 다른 그룹끼리는 차이 나야 함.
2. 군집 타당성 지표(Clustering Validity Measure)
그럼 이제 클러스터링의 품질(타당성)을 평가하는 지표를 알아보겠습니다. Clustering Validity Measure는 크게 아래 세 종류로 구분해볼 수 있습니다.
External measure : 클러스터의 개수와 멤버가 정해져있다고 가정하고 그에 맞춰 평가하는 방식이다. (사실상 지도학습 같은 비현실적인 방법으로, 새로운 알고리즘을 개발 및 연구과정에서 확인용으로 사용하는 방식)
Internal measure : 앞서 본 핵심 아이디어 중 ‘군집 내 분산’에 집중한 방식
Relative measure : ‘군집 내 분산’과 ‘군집 간 분산’ 모두에 집중한 방식입니다. (가장 일반적으로 사용됨!)
이미지 출처 : github.com/pilsung-kang/Business-Analytics-ITS504
2.1. Internal measure
📌WSS (Within cluster Sum of Squares: 군집 내 거리 제곱합)
웬만하면 더 안정적인 Relative measure를 쓰지만, 적절한 클러스터 개수를 쉽게 정할 수 있는 Elbow Method를 언급하고자 WSS 하나만 짚고 넘어가도록 하겠습니다. 이는 군집 내의 중심과 객체들 간의 거리를 제곱합한 것으로, 작을수록 좋은 값(=군집 내 분산)으로 볼 수 있습니다.
그러나 이 값에는 문제가 하나 있는데, 클러스터를 무작정 많이 생성할수록 자연스럽게 WSS가 줄어든다는 것입니다. (이는 트리 기반 모델에서, 노드에 데이터가 하나씩만 들어갈 정도로 깊게 분기할 때 impurity가 최소화됐던 것과 같은 맥락으로 볼 수 있음) 만약 n개의 데이터가 존재하는데, 이들 각각을 모두 하나의 군집으로 잡아 n개의 클러스터로 묶었다고 가정해보죠. 그러면 ‘군집 내 분산’인 WSS는 (좋은 클러스터링이 아님에도) 모든 클러스터에서 0이 됩니다..!
클러스터 개수가 늘어남에 따라 이 값이 어떻게 변하는지 그려보면, 위와 같이 우하향하는 그래프가 그려집니다. 그런데 이때 보통 그 감소 폭이 급격하게 줄어드는 지점이 있게 되는데, 이 지점 이후에는 WSS의 유의미한 감소가 없을 것이라 생각할 수 있고, 그 지점의 클러스터 개수를 최적의 클러스터 개수로 정할 수 있습니다. 이러한 방법을 Elbow Method라고 합니다. (=유의미한 성능 향상이 없을 때 조기종료시키는 것이므로 Earlystopping과 비슷한 맥락으로도 볼 수 있음)
2.2. Relative measure
📌Dunn Index
Dunn index는 앞서 말한 “군집 내 분산 최소화 & 군집 간 분산 최대화”의 논리를 직접적으로 적용한 지표입니다. 구체적으로는 "클러스터 내 최대거리에 대한 클러스터 간 최소거리의 비율"로 군집 결과를 평가하는데, 그 식은 아래와 같습니다. ‘클러스터 내 최대거리’는 작을수록 좋고, ‘클러스터 간 최소거리’는 클수록 좋기 때문에, $I(C)$ 값이 클수록 클러스터링이 잘 된 것으로 판단할 수 있습니다.
‘거리’를 측정할 때는 보통 min, max를 사용하는데, 이상치의 영향을 상쇄시키기 위해 average나 centroid 값을 이용하기도 합니다.
📌Silhouette Index
Silhouette Index는 객체 하나하나에 대해 계산하기 때문에 Dunn Index보다 더 복잡한 지표입니다.
실루엣 계수는 아래와 같이 정의되고, 이 값이 1에 가까울수록 클러스터링이 잘 된 것으로 판단합니다.
$a(i)$ : 같은 군집 내 다른 객체들과의 거리를 평균낸 값 (군집 내 분산) = 작을수록 좋은 값
$b(i)$ : 다른 군집 객체들과의 거리를 평균 낸 후 그 중 최소인 값 (군집 간 분산) = 클수록 좋은 값
이렇게 실루엣 계수를 모든 점(데이터)에 대해 계산하고, 그것의 평균값을 최종 Silhouette Score로 사용합니다. 이론적으로 가질수 있는 값의 범위는 -1 ~ 1 사이지만, 정상적인 군집화라면 양수값이 나오는 게 일반적입니다.
$a(i)$가 0일 경우 : 같은 군집의 객체들이 전부 겹쳐 있는 상황➡️ S(i) = 1
$b(i)$가 0일 경우 : 다른 군집의 객체들이 겹쳐 있는 상황(현실적으로 불가능)➡️ S(i) = -1
흔히 Silhouette Score가 0.5 또는 0.7을 넘으면 잘 묶인 군집이라고 판단합니다. (물론 task에 따라 얼마든지 기준이 달라질 수 있습니다) 또, 아래 그림처럼 python으로 실루엣 점수를 시각화해볼 수도 있습니다. 군집 개수를 다르게 설정해가며 실루엣 계수를 측정하고, 어떤 게 제일 괜찮은지 보는 것이죠.
(빨간 점선으로 표시된 것이 최종 실루엣 계수)
⚠️그런데 한 가지 주의해야 할 점은, 전체 silhouette score가 높다고 해서 해당 클러스터링이 가장 좋은 클러스터링이라고 단정지을 수 없다는 것입니다. 이유는 특정 군집의 실루엣 계수만 높은 경우도 전체 score가 높을 수 있기 때문인데요. 따라서, 각 군집별 데이터의 수가 고르게 분포하면서, 각 군집별 실루엣 계수들도 전체 실루엣 계수에 크게 벗어나지 않는 것이 중요하겠습니다.
위 예시에서 Cluster 2개인 경우 : 전체 score는 높지만, 0번 군집의 대부분이 전체 score보다 낮음
위 예시에서 Cluster 4개인 경우 : 전체 score가 최고는 아니지만, 개별 score가 균일하게 전체 score를 웃돌고 있음 (이걸로 채택하는 것이 더 좋아보임!)
➕참고 Dunn index와 Silhouette index 역시 클러스터 개수를 정하는 데 활용할 수 있습니다. 다만 이 지표들은 WSS처럼 계속 감소하는 형태가 아니기 때문에 Elbow methond를 활용할 순 없겠죠. 아래 그림처럼 클러스터 개수에 따른 지표를 계산하여 비교하여 판단하는 것이 좋습니다!
3. 비계층적 클러스터링
어떤 클러스터링이 좋은 클러스터링인지 살펴봤으니, 이제 본격적으로 클러스터링을 수행하는 방법에 대해서 다뤄보도록 하겠습니다. 클러스터링은 종류가 매우 다양하지만, 본 스터디에서 다룰 내용은 크게 2가지로 구분할 수 있습니다. 먼저 비계층적 클러스터링에서 Centroid(중심) 기반 클러스터링과 Density(밀도) 기반 클러스터링을 다루고, 계층적 클러스터링에서 Agglomerative 클러스터링을 다뤄볼 것입니다.
3.1. K-Means Clustering (Centroid-based)
가장 대중적으로 사용되는 클러스터링인 K-Means Clustering은, 이름에서 알 수 있듯이 데이터들의 평균 지점을 Centroid로 활용하는 클러스터링입니다.
먼저 목적 함수를 살펴보면 아래와 같습니다. (아래 예시를 먼저 보고 오면 이해하기 더욱 쉽습니다!!)
각 데이터 포인트를 해당 클러스터의 중심과 가깝게 할당하여 거리의 제곱합을 최소화하는 것이 목표!
클러스터링을 수행(학습)하는 과정은 다음과 같습니다.
초기화: K개의 클러스터 중심(centroids) $\mathbf{c}_1$, $\mathbf{c}_2$, ..., $\mathbf{c}_K$ 을 랜덤하게 설정
할당 단계: 각 데이터 포인트 $\mathbf{x}_j$ 를 가장 가까운 중심 $\mathbf{c}_j$의 클러스터 $C_i$에 할당
'가까운' : ||$\mathbf{x}_j - \mathbf{c}_i$|| 값이 가장 작은 클러스터 $C_i$에 할당
업데이트 단계: 각 클러스터($C_i$)의 중심을 해당 클러스터에 속한 데이터 포인트들의 평균으로 업데이트
'평균' : $\mathbf{c}_i = \frac{1}{|C_i|} \sum{\mathbf{x}_j}$ 식으로 중심을 업데이트
목적 함수(거리 제곱합)를 최소화하려면, 중심이 데이터들의 평균이 되는 것이 최적이라고 증명되어있음!
수렴 검사: 클러스터 할당이 변하지 않거나 중심 이동량이 작아지면 종료. 아니라면 2~3단계를 반복.
보다 직관적인 이해를 위해, 예시와 함께 구체적인 학습 과정을 살펴봅시다. (⭐클러스터 개수 K는 사용자가 직접 지정해줘야 합니다!)
① K개의 Centroid가 랜덤하게 정해진다. (이 경우에는 K가 2이며, 초기 Centroid는 빨간색 네모가 된다)
② 관측치들(파란 점)을 가장 가까운 Centroid에 맞게 1차 군집(초록 박스)으로 할당한다.
③ 1차 군집의 관측치들을 기준으로 Centroid를 업데이트한다.
④ 관측치들을 수정된 Centroid에 맞게 2차 군집(보라색 박스)으로 할당한다.
⑤ 2차 군집의 관측치들을 기준으로 Centroid를 다시 업데이트한다.
⑥ 관측치들을 수정된 Centroid에 맞게 3차 군집으로 할당한다.
⑦ Centroid와 Membership에 더 이상 변화가 없으면 (or 지정한 반복 횟수를 넘으면) 학습을 종료한다.
KMeans 클러스터링은 직관적이고 구현이 쉽다는 장점이 있지만, 아래와 같은 한계들도 갖고 있습니다.
초기값에 민감함 : 단순 거리기반 알고리즘이라, 초기값에 따라 이상한 군집(local minima)으로 수렴될 수 있습니다. 그래도 랜덤하게 반복하면 7-80%는 바람직한 군집으로 나오니, 여러 번 시도해보고 자주 나오는 결과로 택하면 됩니다. (계산 복잡도가 낮아서 반복해도 괜찮음) 혹은 계층적 클러스터링이나 도메인 지식을 활용해 초기값을 적당히 지정해줄 수도 있습니다.
이상치의 영향을 많이 받음 : 단순 거리(WSS)를 기반으로 하기 때문입니다. 중앙값을 사용하는 K-Medoids를 대안으로 사용할 수도 있습니다.
그룹 내 분산 구조가 원(구)형인 경우에 특화됨 : 유클리드 거리를 기반으로 하기 때문에, 특정한 모양(타원, 나선 등)에는 맞지 않을 수 있습니다. 같은 이유로 밀도의 차이도 반영하지 못하는데, 뒤에 나오는 DBSCAN 등의 방법으로 해결할 수 있습니다.
범주형 데이터에는 적용 불가함 : K-Means를 확장한 K-Modes 클러스터링을 대안으로 사용할 수 있습니다.
3.2. K-Medoids Clustering (Centroid-based)
K-Means가 데이터의 평균값으로 Centroid를 업데이트 했다면, K-Medoids는 데이터의 중앙값(median)으로 Centroid를 설정하는 방법입니다. 대표적으로 PAM(Partitioning Around Medoids) 기법이 있는데, 학습 과정을 간단히 살펴보면 아래와 같습니다. (KMeans와 유사합니다)
초기화 : n개의 데이터 포인트 중에서 임의로 k개의 Centroid를 지정한다.
할당 : 가장 가까운 Centroid에 각각의 데이터 포인트를 할당한다.
업데이트 : 각 Centroid에 대해서 거리(비용) 합이 가장 작은 데이터 포인트를 new Centroid로 선택한다
수렴 검사 : 2,3단계를 반복한다. 더 이상 Centroid가 변하지 않거나, 최대 반복 횟수에 도달하면 종료!
위 사진에 보이다시피 K-medoids는 실제 포인트를 centroid로 활용한다는 핵심적인 차이가 있습니다. 평균은 가상의 값이었지만 중앙값은 실제로 존재하는 값인 것과 같은 맥락인 거죠! 이는 아래와 같은 이점을 가져다 줍니다.
K- Means보다 이상치에 강건함 : 그래서 비선형적이거나 복잡한 데이터의 경우 K-Means보다 좋은 성능을 보이기도 합니다.
거리 측정 방식이 더 유연함 : ‘가깝다’는 기준을 연구자의 필요에 따라 다른 방식(맨해튼 거리, 코사인 유사도, 자카드 유사도 등) 으로 사용할 수 있습니다.
군집 자체의 해석도 어느 정도 가능함 : 그래서 의료 데이터 분석이나 고객 분류 등 해석 가능한 결과가 필요한 경우에 사용하면 좋습니다.
다만 실제 포인트 간 거리를 일일이 계산해야 하므로, 연산량은 늘어난다는 단점도 있습니다.
3.3. DBSCAN (Density-based)
앞에서 본 방법들은 모두 Centroid와의 ‘거리’를 기반으로 하는 클러스터링이었습니다. 하지만 이미 언급했듯이, 거리 기반 방법은 밀도의 차이나 특수한 형태를 반영하지 못하는 한계가 있습니다.
예를 들어, 아래와 같이 데이터가 분포되어 있을 경우, 우리는 직관적으로 왼쪽에 1개, 오른쪽에 2개로 총 3개의 군집으로 묶을 수 있다고 생각할 것입니다.
하지만 앞서 본 Centroid 기반 클러스터링은 단순히 거리를 기반으로 묶기 때문에, 좌측 그림처럼 직관과 어긋나는 결과를 줄 수 있습니다.
반면, 데이터가 뭉쳐 있는 정도를 고려한다면, 우리의 직관에 부합하는 결과를 얻을 수 있습니다. 따라서 이런 경우에는 밀도 기반 클러스터링을 사용하는 것이 더욱 효과적입니다.
밀도 기반 클러스터링의 대표적인 알고리즘이 바로 DBSCAN입니다. 말 그대로 “밀도가 높은 객체끼리 한 군집으로 묶자”는 것이 핵심 아이디어인데요, 그렇다면 ‘밀도가 높다’는 것을 어떻게 정량화할 수 있을까요? 이를 이해하기 위해 몇 가지 용어들을 정리하고 넘어갈 필요가 있습니다.
📌ɛ-Neighborhood (of a point p); (p의) 엡실론 이웃 • 어떤 점 p의 ɛ-Neighborhood란 p와의 거리가 ɛ보다 작은 점들을 말합니다. 즉, p를 기준으로 반경 ɛ 내에 있는 모든 점은 p의 ɛ-Neighborhood가 되는 거죠. • 쉽게 말해 ‘p가 하나의 군집을 이루려면 p의 ɛ-Neighborhood가 많아야(=밀도가 높아야) 하는 것 아닐까?’ 라는 접근입니다. • 그래서 ‘ɛ-Neighborhood가 많다(밀도가 높다)’에 대한 기준으로 minPts를 설정해줘야 합니다. 다시 말해, 어떤 점 p에 대해서 ɛ-Neighborhood가 최소 minPts개 이상이면 그것들을 군집으로 묶겠다는 것이죠. (ɛ와 minPts는 사용자가 설정해주는 값입니다!)
📌Core point / Border point / Noise point: 각 점(데이터 포인트)을 구분하는 용어 • Core point는 엡실론(ɛ) 반경 내에 minPts개 이상의 점이 존재하는 점입니다. 아래 그림 (a)에서 x의 경우, minPts가 6일 때 엡실론 반경 내에 6개의 점이 있으므로 core point라 할 수 있습니다. (이 점이 나중에 군집을 이루는 중심이 됩니다) •Border point는 엡실론(ɛ) 반경 내에 minPts개 미만의 점을 갖는 점들 중, core point의 엡실론(ɛ) 반경 내에 포함되는 점입니다. 아래 그림 (b)에서 y는 minPts보다 적은 5개의 점만 갖고 있지만, core point인 x의 반경 내에 있으므로 border point가 되는 것이죠. •Noise point는 core도 아니고 border도 아닌, 즉 주변에 minPts개 이하의 점을 가지고, 주변에 core point도 없는 경우를 말합니다. 아래 그림의 z가 noise point가 되겠죠.
📌Directly Density-reachable; 직접 밀도 접근 가능 (이하 D.D.R)
• 어떤 점 p가 q로부터 Directly Density-reachable하다는 것은, 아래 2가지 조건을 만족시켜야 합니다. (1) p가 q의 ɛ-Neighborhood에 속해야 한다 (2) q의 ɛ-Neighborhood 개수는 minPts개 이상이어야 한다 ⇒ 즉, q가 Core point가 되며, 점 p가 점 q로부터 직접 밀도 접근 가능한 관계에 있다는 것을 말합니다.
📌Density-reachable ; 밀도 접근 가능 (이하 D.R)
• 그런데 만약 D.D.R한 점들만 한 군집으로 묶는다면, 비교적 바깥쪽에 있는 점들을 놓치게 될 수 있습니다. 왜냐하면 바깥쪽에 있는 점들은 core point condition(D.D.R의 2번 조건)을 만족하지 못할 수 있기 때문이죠. • 그래서 도입한 개념이 Density-reachable로, 어떤 점 p가 q의 반경 밖에 있더라도, 그 사이의 점들끼리 D.D.R로 연결할 수 있다면 p를 q로부터 D.R하다고 하는 것입니다.
📌Density-connected ; 밀도 연결됨
• 마지막으로 어떤 점 p가 점 o로부터 D.R하고 어떤 점 q도 점 o로부터 D.R하다면, 점 p와 q는 Density-connected 관계에 있다고 합니다. 비유로 설명하자면, A가 O의 친구이고 B도 O의 친구일 때 A와 B가 O를 통해 연결될 수 있다는 것입니다. • D.C는 클러스터링 과정에 직접적으로 사용되는 개념이라기보다는, 클러스터링의 결과적인 표현으로 보면 되겠습니다. 즉, 같은 군집에 할당된 점들은 모두 Density-connected된 것이라 할 수 있는 거죠. •‘🤔그냥 한쪽에서부터 D.R로 뻗어나가면 되는데 굳이 D.C 개념이 왜 필요한가?’라고 생각할 수 있지만, 그렇지 않습니다. 점 p와 q가 모두 border point라면 애초에 D.R을 뻗어나갈 수 없기 때문입니다.
이제, 위 개념들을 바탕으로 DBSCAN의 학습 과정을 보도록 합시다. (사용자는 사전에 ɛ과 minPts를 지정해주어야 합니다!)
임의의 데이터 포인트 p를 선택한다.
ɛ과 minPts에 따라, p로부터 Density-reachable한 점들을 탐색한다.
p가 Core point인 경우, 같은 클러스터로 할당한다.
p가 Border point인 경우, 더 이상 D.R 한 point가 존재하지 않기 때문에 ①번으로 돌아가 다른 포인트를 선택한다. (=이 클러스터는 다 됐으니 다른 클러스터를 묶어나가자)
모든 데이터 포인트가 탐색될 때까지 반복한다. (끝날 때까지 아무 군집에도 할당되지 않은 포인트들은 Noise point가 된다.)
아래 링크에 들어가면 위 예시처럼 실제 클러스터링 과정을 애니메이션으로 볼 수 있습니다! www.naftaliharris.com/blog/visualizing-dbscan-clustering/
DBSCAN도 장단점을 확인하고 마무리하겠습니다.먼저 장점입니다.
특정한 모양의 클러스터를 찾아낼 수 있다 : 앞서 K-Means는 유클리드 거리를 기반으로 해서 원형의 군집만 찾아낸다고 했는데, DBSCAN은 밀도 기반이므로 형태의 한정이 없습니다. (위의 smile face 예시도 잘 찾는 것처럼요!)
군집에 할당되지 않는 객체도 허용한다 : 이전에 본 방법들은 모든 데이터를 무조건 군집에 할당해줘야 했지만, DBSCAN은 Noise point가 있었죠. 덕분에 군집으로 묶기 애매한 이상치들은 굳이 군집에 할당하지 않아도 됩니다! (이런 특성 덕분에 데이터의 Anomaly Detection에 밀도 기반 클러스터링이 활용되기도 합니다)
클러스터링의 랜덤성이 작다 : 앞서 K-Means 같은 모델은 초기값에 굉장히 민감하다고 했는데, DBSCAN은 초기값이 바뀌더라도 클러스터에 큰 변화가 없습니다. (※여러 군집에 걸쳐있는 포인트는 먼저 만들어진 군집에 할당되기도 하지만, 그러한 포인트 개수는 많지 않습니다.)
클러스터 개수(K)를 지정해주지 않아도 된다 : DBSCAN의 작동 과정을 보면 쉽게 이해할 수 있습니다. 밀도 기반으로 알아서 군집을 묶어나가기 때문에, 사용자는 epsilon과 minPts만 잘 지정해주면 됩니다.
다음은 단점입니다.
하이퍼파라미터 튜닝이 많이 필요하다 : epsilon과 minPts를 얼마로 설정하는 것이 적절한지 한 번에 알기 쉽지 않습니다. 시각화를 통해서 경험적/정성적으로 판단하거나, 앞서 배운 실루엣 계수 등의 validity measure를 참고하는 수밖에 없습니다.
같은 데이터셋 내에서도 밀도가 제각각인 경우 성능이 좋지 않을 수 있다 : 이런 경우 적절한 epsilon과 minpts를 찾기 더욱 힘들어지는데, 이런 부분을 개선하고자 한 HDBSCAN(Hierarchical DBSCAN)이라는 알고리즘도 존재합니다. (=뒤에서 설명할 계층 구조를 DBSCAN에 반영한 모델로 epsilon 값을 지정해줄 필요가 없습니다.)
같은 데이터셋 내에서도 밀도가 제각각인 경우 예시
4. 계층적 클러스터링
계층적 클러스터링이란, 계층이 존재하는 트리를 이용해서 개별 개체들을 순차적으로 묶어나가는 군집화 방식입니다. 지금까지 배운 방법들은 모두 “분리형(Partitional) 클러스터링”으로, 전체 데이터가 겹치지 않고 분리되어 군집화되었습니다. 반면 “계층적(Hierarchical) 클러스터링”은 순차적 & 부분적으로 군집화하기 때문에 내포 관계(nested cluster)가 생길 수 있다는 차이가 있습니다.
4.1. 개념 소개
계층적 클러스터링은 장점을 미리 얘기해보겠습니다.
첫 번째로, 클러스터의 개수를 지정해주지 않고 학습이 가능하다는 장점이 가장 큽니다. 개체들을 ‘순차적으로 묶어나가는’ 알고리즘이기 때문에, 미리 몇 개의 클러스터로 지정할 필요가 없습니다. 오히려 사용자가 순차적인 부분 군집들 중에 원하는 정도를 선택할 수 있습니다. (ex. 위 그림에서 사용자가 초록색 군집 2개를 선택해도 되고, 보라색 군집 3개를 선택해도 됩니다.)
두 번째는, 클러스터링의 시퀀스를 ‘덴드로그램’이라는 구조도로 시각화할 수 있다는 것입니다. 계층적인 군집들을 보면서 데이터의 특성을 파악할 수 있고, 군집의 개수도 편하게 선택할 수 있습니다. (실제로 유의미한 분류체계와 상응할 수도 있습니다!)
덴드로그램 예시
계층적 클러스터링은 크게 2가지 종류로 나눠볼 수 있습니다.
상향식 계층적 클러스터링 : AGNES (AGglomerative NESting)로도 불리는 방식으로, 개별 데이터포인트들을 bottom-up 방식으로 점점 묶어가며 군집화를 수행합니다.➡️주로 이 방식을 많이 쓰기 때문에 상향식 중심으로 설명할 것입니다!
하향식계층적 클러스터링 : DIANA (DIvise ANAlysis)로도 불리는 방식으로, 데이터 전체에서 시작해서 top-down 방식으로 점점 쪼개가며 군집화를 수행합니다.
4.2. Agglomerative Clustering
계층적(상향식) 클러스터링은 '가장 가까운' 두 객체(또는 집단)를 '순차적으로' 병합해나가는 방식입니다.
이 말은 즉슨, 클러스터링 수행을 위해 개체(또는 집단) 간의 거리를 계산할 수 있어야 한다는 것입니다. 그래서 먼저 이 거리 측정 방식을 짚고 넘어가겠습니다.
sklearn에서는 각각 `affinity`, `linkage` 매개변수로 설정합니다.
scipy에서는 각각 `metric`, `method` 매개변수로 설정합니다.
📌Affinity(개체 간 거리 측정 방식)
• 유클리드(Euclidean) 거리 : 가장 흔히 사용되는 거리 척도로서, 두 관측치 사이의 직선 최단거리를 의미합니다. • 맨하탄(Manhattan) 거리 : 두 점 사이를 직선으로 이동하지 않고, 각 좌표축의 방향으로만 이동할 경우 계산되는 거리를 의미합니다 • 마할라노비스(Mahalanobis) 거리 : 주변 데이터의 맥락(변수 간 공분산, 주변 데이터 분포 등)을 반영해 거리를 계산하는 방식입니다. 두 점 사이의 거리를 절대적으로 보지 않고 상관관계를 고려하기 때문에, 이상치를 탐색하는 데에도 활용된다고 합니다. 출처: http://angeloyeo.github.io/2022/09/28/Mahalanobis_distance.html
📌Linkage(군집 간 거리 측정 방식)
• Single linkage : 서로 다른 군집의 모든 데이터 간 거리 중 최소값 (min) • Complete linkage : 서로 다른 군집의 모든 데이터 간 거리 중 최대값(max) •Centroid linkage : 서로 다른 군집의 중심 점 (centroid) 간 거리 •Average linkage : 서로 다른 군집의 모든 데이터 간 거리들의 평균 •Ward method : 서로 다른 군집의 병합 전 후 분산 차이 (병합했을 때 SSE가 적게 늘어날수록 더 유사한 군집이라는 아이디어를 바탕으로 합니다. 아래 예시의 경우, 파란 군집과 주황 군집 간 거리는 45-8=37로 계산되는 것입니다.)
이제 모든 준비가 끝났네요. 본격적으로 Agglomerative Clustering의 학습 과정을 살펴봅시다. 동시에, 계층적 클러스터링의 장점이었던 덴드로그램도 함께 그려나가 봅시다.
① 먼저 각 관측치(또는 군집) 간의 거리를 모두 계산한다.
주로 아래와 같은 거리 행렬(Distance Matrix)로 나타내는데, 아래와 같이 대칭행렬의 형태를 띠게 된다.
② 계산된 거리가 가장 가까운 두 관측치(또는 군집)를 병합한다.
③ 병합 이후 Distance Matrix를 업데이트한다. (이 예시의 경우는 single linkage를 사용했다)
④ 클러스터가 1개만 남을 때까지(=전체가 다 묶일 때까지) 위 과정을 반복한다.
이렇게 모든 데이터가 하나의 클러스터로 묶이면 계층적 클러스터링을 완료한 것입니다!
앞서 말했듯이, 계층적 클러스터링의 최대 장점은 클러스터 개수 K를 정할 필요가 없다는 점입니다. 이렇게 나온 최종 결과에서 사용자는 원하는 클러스터 수를 선택하면 되는 것이죠.
예를 들어, 덴드로그램의 최하층에서 끊으면 A, B, C, D로 4개의 군집이 되고, 두 번째 층을 끊으면 AD, B, C로 3개의 군집이 될 것입니다.
참고로 덴드로그램의 선 높이는 개체(또는 군집) 간 거리와 일치하게 그려야 합니다! (ex. 마지막 그림을 보면 ADC 군집과 B 간의 거리가 10이므로 10만큼 긴 선으로 그렸음)
다만, 기본적인 계산량이 많기 때문에 대용량 데이터에 적용하려면많은 연산 시간과 컴퓨팅 파워가 소모된다는 단점도 있습니다.
5. 그 외 다양한 클러스터링
지금까지 다뤘던 계층적, 비계층적 클러스터링 외에도 수많은 클러스터링 기법이 존재합니다.
(1) KMeans와 유사하지만 centroid를 갱신할 때 데이터 분포(밀도)를 활용하는 Mean Shift Clustering이 있습니다. 이는 확률밀도함수가 피크인 점을 centroid로 선택하며, KDE(Kernel Density Estimation)을 활용합니다. K를 정하지 않아도 되고, 데이터 형태나 분포를 가정하지 않기 때문에 유연한 군집화가 가능하다는 장점이 있지만, 수행 시간이 오래 걸리고 최적의 대역폭(bandwidth)을 찾기 어렵다는 단점이 있습니다.
(2) 데이터가 가우시안 분포를 가진 데이터 집합들이 섞여서 생성된 것이라는 가정 하에 수행하는 GMM(Gaussian Mixture Model)이 있습니다. 여러 개의 가우시안 분포(ex. 정규분포)를 추출하고 개별 데이터가 어느 분포에 속하는지 결정하기 위해 EM 알고리즘을 사용합니다. GMM 역시 원형 이외의 다양한 데이터셋에 유연하게 적용될 수 있다는 장점이 있지만, 수행시간이 오래 걸린다는 단점이 있습니다.
(3) 데이터를 더 낮은 차원으로 사영하여(= 차원축소를 진행한 후) 클러스터링을 진행하는 Spectral Clustering이 있습니다. Spectral 클러스터링은 비어있는 지점이 많거나, 이중 나선 형태를 띠는 데이터에서 효과적으로 사용됩니다. 그러나 연산 시간이 오래 걸리고 클러스터 개수 K를 결정하기 어렵다는 단점이 있습니다.
다양한 클러스터링의 세계...
👆🏻마지막으로 정리를 해봅시다!
일반적으로 가장 편리한 K-means 클러스터링을 많이 사용합니다. 다만 이상치가 많은 데이터일 경우 K-Medoids Clustering을 사용할 수 있습니다.
데이터의 분포가 특정 지점에 쏠려 있어 밀도가 다르면 DBSCAN을 쓸 수 있습니다.
데이터가 구형이 아니라 나선형 등 특수한 형태로 묶일 것 같으면 Spectral Clustering이나 DBSCAN을 쓸 수 있습니다.
결국, 이처럼 데이터의 특징과 상황에 맞게 적절한 클러스터링을 할 줄 아는 것이 중요합니다. 그리고 맨 앞에서 배웠던 Validity measure를 통해 군집을 평가하고 해석할 줄도 알아야 하겠습니다.
