이 글에서는 클러스터링(군집화)에 대해 살펴보겠습니다.
이 글은 ISLR 책과 고려대학교 김성범 교수님 강의를 정리했습니다.
<목차>
1. 군집화란?
2. 좋은 군집화란?
3. 군집화 수행 시 주요 고려사항
3-1. 유사도 척도
3-1-1. 유클리디안 거리
3-1-2. 맨해튼 거리
3-1-3. 마할라노비스 거리
3-1-4. 상관계수 거리
3-1-5. 스피어만 순위 상관계수 거리
3-2. 알고리즘
3-2-1. Hierarchical Clustering
3-2-2. K-means Clustering
3-3. 군집 수
3-4. 평가
1. 군집화란?
유사한 속성들을 갖는 관측치들을 묶어 전체 데이터를 몇 개의 군집으로 나누는 것
2. 좋은 군집화란?
1). 동일한 군집에 소속된 관측치들은 서로 유사할수록 좋다.
2). 상이한 군집에 소속된 관측치들은 서로 다를수록 좋다.
3. 군집화 수행 시 주요 고려사항
1). 어떤 거리 척도를 사용하여 유사도를 측정할 것인가?
2). 어떤 군집화 알고리즘을 사용할 것인가?
3). 어떻게 최적의 군집수를 결정할 것인가?
4). 어떻게 군집화 결과를 측정 / 평가할 것인가?
3-1). 군집화 :: 유사도 척도
" 어떤 거리척도를 사용하여 유사도를 측정할 거니? "
3-1-1). 유클리디안 거리 (Euclidean Distance)
- 가장 흔히 사용되는 거리 측도
- 대응되는 X,Y 값 간 차이 제곱 합의 제곱근으로써, 두 관측치 사이의 직선거리(최단거리)를 의미한다.
3-1-2). 맨하탄 거리 (Manhattan Distance)
- X에서 Y로 이동시 각 좌표축 방향으로만 이동할 경우에 계산되는 거리
- 위의 그림으로 설명하자면, A에서 B지점으로 이동할 때, 직선거리로 이동하면 가장 짧은 거리로 이동할 수 있다.
하지만 저 직선에는 건물들과 도로 등등 이동할 수 없는 요소들이 있다.
우리는 정상적으로 B로 이동하기 위해서는 파란 경로로 이동하게 될 것이고 이때 파란 선의 길이가 맨해튼 거리이다.
3-1-3). 마할라노비스 거리 ( Mahalanobis Distance )
- 변수 내 분산, 변수 간 공분산을 모두 반영하여 X, Y 간 거리를 계산하는 방식
- 데이터의 공분산 행렬이 단위행렬인 경우는 유클리언 거리와 동일해진다. (공식 참고)
** 단위행렬인 경우 아래 공식의 공분산 행렬 역행렬 부분이 1이 되어 없는 것과 같아진다. **
- 공분산 행렬의 역행렬이 갖는 의미 :: 변수들 간의 분산값에 역수를 취한 것
:: 분산 값이 크면 작은 값을 곱해주고, 분산 값이 작으면 큰 값을 곱하겠다는 의미
** 마할라노비스의 보충 설명 **
>> 마할라노비스 거리의 값을 c라고 했을 때, 양변을 제곱해준다.
>> 2차원을 예시로 들었을 때, X,Y,공분산 행렬의 역행렬을 위와 같이 정의해준다.
>> 정의한 X,Y,공분산 행렬을 위의 식에 대입해주면 위와 같이 나온다.
>> Y에 0을 대입해주면 마지막 식이 유도되며, 위 식은 타원 방정식이다.
즉, 마할라노비스 거리의 제곱은 타원 방정식이 되는구나!라는 결론에 도달할 수 있다.
예시를 통해 좀 더 알아보자.
1. 공분산 행렬이 단위행렬인 경우
2. 공분산 행렬에서 분산만 있고 공분산은 0인 경우
3. 공분산 행렬에서 분산도 있고, 공분산도 존재하는 경우
>> 공분산 값이 존재할 때 타원이 더 휘어지는 것을 알 수 있다.
3번째 예시를 좀 더 자세하게 알아보자.
3. 공분산 행렬에서 분산도 있고, 공분산도 존재하는 경우
- c의 값이 커짐에 따라 타원이 커짐을 알 수 있다.
- 타원 위의 있는 점의 값들은 같은 값을 가진다.
다음 그림에서 중심C에서 점 A와 점 B 중 거리가 먼 것은?
> 유클리디안 관점에서 직선 AC = 4.3 , 직선 BC = 1.6으로 점 A가 더 멀다.
> 마할라노비스 관점에서 X1과 X2의 상관관계가 크다.
값을 구해보면 마할라노비스 거리 AC = 3.4 , BC = 3.7로 점 B가 더 멀다. (상관관계를 고려한다면)
>> 그래프를 보면 X1과 X2가 거의 y=x관계를 가지고 있다 >> 상관관계수가 강하다.
>> AC가 상관계수와 같은 방향에 위치해 있고, BC는 거의 반대 방향에 위치해 있다.
3-1-4). 상관계수 거리
- 데이터간 Pearson correlation을 거리 측 도로 사용하는 방식으로, 데이터 패턴의 유사도를 반영할 수 있다.
- 상관계수의 범위가 -1과 1 사이이니 상관계수 거리의 범위는 0과 2 사이이다.
- 즉, 상관계수가 클수록 상관계수 거리는 작아진다.
- 1과 2를 살펴보면, 상관계수 관점에서 1이 2보다 더 상관계수가 크니 상관계수 거리는 1이 더 짧을 것이다.
5. 스피어만 순위 상관계수 거리
- 데이터의 rank를 이용하여 상관계수 거리를 계산하는 방식
예시를 통해 살펴보자.
- 각 행별로 낮 최고온도 순위를 매긴다.
- 오른쪽 표를 봐도 알 수 있듯이, 서울과 뉴욕은 같은 값 (유사한 패턴)을 갖는 반면에 시드니는 아예 다른 패턴을 가지 고 있다.
- 실제로 값을 구해봐도
- 서울과 뉴욕 사이의 스피어만 순위 상관계수 거리는 0이고, 서울과 시드니는 2 임을 알 수 있다.
3-2. 군집화 :: 알고리즘
" 어떤 군집화 알고리즘을 사용할거니? "
군집화 알고리즘 종류
1. 계층적 군집화
2. 분리형 군집화
3. 자기조식화 지도
4. 분포 기반 군집화
** 여기서는 1,2 위주로 설명 **
3-2-1). Hierarchical Clustering - 계층적 군집화
- 계층적 트리 모형을 이용해 개별 개체들을 순차적, 계층적으로 유사한 개체 내지 그룹과 통합하여 군집화를 수행하는 알고리즘
- 즉, 각각의 관측값들을 하나의 클러스터로 가정하고 이들의 거리를 이용하여 거리가 가까운 관측값들끼리 병합하여 상 위 단계 클러스터를 구성하고, 이렇게 구성된 상위단계 클러스터를 다시 거리를 구해 병합하는 과정을 반복하며 최종적으로 데이터 전체를 하나의 클러스터로 구성하는 방법이다.
- K-Means Clustering과 달리 K(군집수)를 사전에 정의하지 않아도 된다.
- '덴드로그램'이라는 매력적인 트리 기반 시각자료를 가지고 있다.
- '덴드로그램'을 통해 군집의 수를 정할 수 있다.
< Interpreting a Dendrogram >
가장 아래에 있는 각각의 leaf들은 데이터의 관측값들이다.
트리가 위로 올라갈수록 몇몇의 leaf들끼리 결합을 한다. 이때, 결합한다는 것은 결합된 관측값들이 서로 유사한 관측치로 판단된다는 의미이다. 일찍 결합될수록 (트리가 낮을수록) 결합된 그룹들은 유사한 패턴을 가지고 있다는 것이며, 늦게 결합될수록 (트리가 높을수록) 결합된 그룹들 간의 패턴이 다르다는 것을 의미한다.
< Important point in interpreting dendrograms that is often misunderstood >
다음은 9개의 관측치의 덴드로그램을 나타낸 것이다.
관측치 5와7은 가장 낮은 높이에서 결합되었기 때문에 서로 유사하다고 볼 수 있다. 1과 6도 마찬가지다.
그러나 관측치 9와 2가 덴드로그램에서 서로 가까이 있다는 것을 근거로 관측치 9와 2가 비슷하다고 결론을 내리는 것은 구미가 당기는 일이지만 부정확하다. 실제로 덴드로그램에 수록된 정보를 근거로 관측치 9는 관측치 8, 5, 7과 마찬가지로 2와도 비슷하지 않다. ( 오른쪽 그래프는 실제 데이터를 펼친 것이다. )
- 즉, 덴드로그램에서 가로축 방향으로 얼마나 가까운지는 의미가 없다.
- 결합(fuse)이 되는 과정에서의 세로축의 값이 두 그룹이 얼마나 유사한지를 알려주는 척도이다.
세로축의 값이 작으면 작을수록 유사도가 크다고 본다.
< Clustering By Dendrogram >
- Hierarchical Clustering은 덴드로그램을 통해 K를 결정한다고 했다.
- 위의 그림처럼 수평선 방향으로 어느 지점에서 자를지를 결정하면 클러스터링이 결정된다.
- 사전에 K값을 모를 때, 덴드로그램을 통해 시각적으로 군집 개수를 찾아낼 수 있는 것이 장점이다.
< Hierarchical Algorithm >
- 위의 알고리즘 설명은 간단한 예제를 통해 알아보자.
< Hierarchical 알고리즘 예시 >
** 관측치가 4개 있다고 가정 / 각 관측값들은 A,B,C,D **
1. 모든 개체들 사이의 거리에 대한 유사도 행렬을 계산한다.
:: 이때, 유사도는 유클리디안 거리를 계산
:: 거리가 인접한 관측치끼리 군집을 형성
:: A와 D의 거리가 2로 가장 가깝다 ( A&D 군집 형성 )
2. 유사도 행렬 업데이트
:: (A,D)를 군집화 시켜 하나의 관측치라고 생각함
:: 업데이트 결과 (A, D)와 C 거리가 3으로 가장 가깝다.
:: (A,D) & C 군집 형성
3. 위의 과정을 계속 반복
모든 과정이 끝났으면 유사도 행렬을 통해 덴드로그램을 직접 그릴 수 있다.
3-2-2). K-Means Clustering (K평균 군집화) - 분리형 군집화
- K평균 클러스터링은 데이터를 K개의 겹쳐지지 않는 군집으로 정의하기에 간단하면서도 명쾌한 알고리즘이다.
- K평균 클러스터링을 하기 전에는 몇 개의 K개로 군집할지를 사전에 미리 정해야 한다.
- K개의 군집들은 아래와 같은 특징을 가지고 있다.
> 각각의 관측값들은 최소한 하나의 군집에는 속해야 한다.
> 하나의 관측값은 하나의 군집에만 속한다. 중복되지 않는다.
- K평균 클러스터링은 군집화 내의 variation이 작으면 작을수록 좋은 클러스터링이라고 한다.
< K-Means Clustering 알고리즘 예시 >
1. 임의의 K를 정한다 :: k = 2 설정
:: 보라색은 데이터이며, 녹색 네모는 임의로 정한 클러스터링의 중심이다. ( k=2로 했으니 중심 2개가 임의로 설정 )
2. 개별 관측치로부터 각 중심까지의 거리를 계산후 가장 가까운 중심이 이루는 군집에 관측치를 할당
:: 즉, A1이라는 관측치가 있고, 중심이 C1, C2가 있다고 하자.
:: A1과 C1사이의 거리와 A1과 C2사이의 거리를 계산 후 C1의 거리가 더 가까우면 C1이 이루는 군집에 속하게 된다.
군집이 2개 생성되었으니 그럼 끝 ?? NOPE
3. 2에서 생성된 군집의 중심을 다시 계산해서 중심을 업데이트한다.
4. 새로 생성된 중심을 기준으로 2~3번 과정을 반복한다.
언제까지? 중심이 더 이상 변하지 않을 때 까지
< K-Means Clustering 수학적으로 접근하기 >
- Ck : k번쨰 군집
- W(Ck) : k번째 군집의 Variation 분산
- 위에서 언급했듯이 K평균 클러스터링은 군집화 내의 variation이 작으면 작을수록 좋은 클러스터링이라고 한다.
- 즉, 우리는 아래의 식을 풀기를 원한다.
>> 즉, 우리는 K개의 클러스터링 내의 분산의 합들이 최소가 되는 K개의 군집을 구하기를 원한다.
- 위의 식을 풀기 위해서는 우리는 W(Ck)를 정의해야 한다. 많은 정의들이 있지만 여기서는
' Squared Euclidean distance '를 사용할 것이다.
- 즉, K번째 클러스터링 안에 있는 모든 관측값들 사이의 유클리디언 거리의 제곱합을 구하고 |Ck|로 나눈다.
이때, |Ck| : K번째 클러스터링 안에 속해있는 관측값 개수
- 위의 두개의 식을 결합해보면 아래와 같이 쓸 수 있다.
- K와 K에 속하는 관측값의 값이 크다면 계산량은 엄청날 것이다.
- Fortunately, a very simple algorithm can be shown to provide a local optimum - a pretty good solution - to the K-means optimization problem
- 이때, K-Means 알고리즘은 local optimum을 찾아주는 근사 알고리즘이다.
- (10.12)식이 나온 과정은 아래와 같다.
** 노란,초록 별도의 표시는 넘어가는 과정이 개인적으로 이해가 안 되어서 따로 표시해둔 것 **
1. 각각의 관측값들에게 1~K까지 랜덤하게 번호를 부여한다.
이 부여된 번호는 각 관측값이 포함되는 군집 번호이다.
2. 군집 배정이 끝날때 까지 아래 (a)~(b) 과정을 반복한다.
( a ) . 각 K개의 클러스터링에서 그 클러스터링의 중심을 정한다.
이때, 중심은 그 군집에 포함되어 있는 관측값들의 p개의 feature들의 평균값이다.
( b ) . (a)에서 정한 중심점에 근접한 관측값들을 새로운 군집에 배정한다.
이때, 근접하다는 것은 유클리디언 거리를 사용해서 판단한다.
< K-Means Clustering의 문제점 및 해결점 >
문제점 1).
초기에 중심을 임의로 설정하게 되면, 초기 중심 설정에 따라 최종 군집 결과가 다르게 나타날 수도 있다.
>> 왼쪽은 중심을 초기에 적절하게 설정됐기 때문에 원하는 대로 군집화가 되었다.
>> 오른쪽은 초기 중심 설정이 잘못 설정되었기 때문에 원하는 결과대로 군집화가 되지 않았다.
해결점 1).
- 반복적으로 수행해 가장 여러 번 나타나는 군집을 사용한다.
- 전체 데이터 중 일부만 샘플링하여 덴드로그램을 그려 초기 군집 중심을 설정한다.
- 데이터 분포의 정보를 활용하여 초기 중심을 결정한다.
>> 하지만 대부분의 경우는 초기 중심 설정이 최종 결과에 큰 영향을 끼치지는 않는다.
문제점 2).
서로 다른 크기의 군집을 잘 찾아내지 못한다.
>> 각 군집의 크기가 많이 차이가 나면 원하는 군집 결과를 내기가 어렵다.
문제점 3).
서로 다른 밀도의 군집을 잘 찾아내지 못한다.
>> 각 군집의 크기가 동일하다고 해도 밀도 차이가 많이 나면 원하는 군집 결과를 내기가 어렵다.
문제점 4).
지역적 패턴이 존재하는 군집을 판별하기 어렵다.
** 지역적 패턴 = 보는 방향에 따라 패턴이 달라지는
해결점 4).
- 이런 경우는 거리를 재는 척도로 Geodesic Distance를 사용 ( 자세한 내용은 생략 )
3-3. 군집화 :: 최적의 군집 수 결정
- K-Means Clustering은 사전에 몇 개의 군집으로 나눌 것인지 K를 정해야 한다고 했다.
Q. 그렇다면 어떤 기준으로 K를 정하는 게 좋을까?
A. 다양한 군집수에 대해 성능평가지표를 아래 그림과 같이 도시하여 최적의 군집수를 선택한다.
일반적으로는 Elbow point에서 최적의 군집 수가 결정된다.
아래 그림은 y축이 SSE 지만, 다양한 지표들이 y축에 올 수 있다.
3-4. 군집화 :: 결과 측정 및 평가
Q. 위의 그래프에서 y축에 어떤 평가 지표를 사용해야 최적의 K를 찾을 수 있을까?
A. 내부평가지표 = Dunn Index, Silhouette, SSE 등등
외부평가지표 = Rand Index, Jaccard Coefficient, Folks and Mallows Index 등등
y축 평가지표에 따라 방법론이 달라진다.
여기서는 대표적으로 SSE와 Silhouette에 대해 설명할 것이다.
1. SSE
- 각 군집의 중심에서 해당 군집에 속해있는 관측치들의 거리 제곱의 합
- 즉, 첫 번째 군집에서 중심과 관측치들의 거리 제곱의 합을 구하고
두 번째 군집에서 중심과 관측치들의 거리 제곱의 합을 구하고
.... K번째 군집에서 중심과 관측치들의 거리 제곱의 합을 구한 후, K개의 합을 다 더한 값이다.
- 각 군집에서 중심과 관측치들의 거리는 작을수록 좋으니 SSE는 작을수록 좋다고 할 수 있다.
- 문제점
:: 클러스터링의 핵심 목표는 1. 군집 내 거리 최소화
2. 군집 간 거리 최대화이다.
:: 하지만 SSE는 군집 내 거리 최소화는 고려를 하지만 군집 간 거리 최대화는 고려하고 있지 않는다.
:: 이를 보완해서 나온 지표가 Silhoutte 통계량이다.
2. Silhouette 통계량
- a(i) : i번째 관측치로부터 같은 군집 내에 있는 모든 다른 개체들 사이의 평균 거리 (군집 내 거리) >> 작을수록 좋음
- b(i) : i번째 관측치로부터 다른 군집내에 있는 모든 개체들 사이의 평균 거리 중 최솟값 (군집 간 거리) >> 클수록 좋음
- b(i) - a(i)는 클수록 좋으며,
이 값은 범위가 정해져 있지 않아서 무한대까지 갈 수 있으니 스케일링 차원에서 max로 나눠준다.
- 최종적인 Silhouette는 S(i)들의 평균이다.
'ML' 카테고리의 다른 글
| 의사결정나무(Classification&Regression)-JoJo's Blog (0) | 2021.08.09 |
|---|---|
| [ISLR] Chapter6. Linear Model Selection and Regularization - Intro (0) | 2021.07.12 |
| [PCA]Principal Components Analysis 주성분분석 - JoJo's Blog (2) | 2021.07.08 |
| [머신러닝&딥러닝] Train / Validation / Test 의 차이 (4) | 2021.02.01 |
| [ISLR] 8. Tree-Based Methods ( 진행중 ) (0) | 2020.10.13 |
댓글