출처: 이기용 교수님, 데이터마이닝및분석 수업
7장에서는 클러스터링이 무엇인지와 대표적인 클러스터링인 (1) K-means, (2) Agglomerative Hierarchical Clustering, (3) DBScan에 대해서 배웠다.
이번에 정리한 내용은 Agglomerative Hierarchical Clustering에 대한 내용이다.
순서대로 전반적으로 정리하자면,
- Agglomerative Hierarchical Clustering이 무엇인지
- Hierarchical Clustering(계층형 클러스터링)이 무엇인지
: singleton cluster가 가장 가까운 클러스터로 뭉치는 과정을 반복하는 것을 말한다
- Hierarchical Clustering의 두 종류: agglomerative(individual cluster에서 시작) vs divisive(all inclusvie에서 시작)
- Agglomerative Hierarchical Clustering의 알고리즘
- Dendogram: Agglomerative Hierarchical Clustering의 표현 방법으로 사용됨.
이 클러스터링은 어떻게 가까운 거리를 정의할 것인가에 따라 클러스터링 결과가 다를 수 있다.
- Defining Proximity between Clusters: 약 4가지의 방법이 있다.
- Single Link or Min 방법
- Complete Link or Max 방법
- Average Link or Group Average 방법
- Ward's Method 방법
- (참고) Centroid Method를 사용할 수 없는 이유
- Compare Different Linkage Methods: 이 방법들에 대한 특징을 하나의 그림으로 표현한 것이다.
마지막으로 Hierarchical Clustering을 사용할 때 고려해야할 점들이다.
- Key Issues in Hierarchical Clustering
- 초기점 선택에 어려움이 없다.
- 목적 함수가 없다.
- 계산 비용이 크다.
- 특이치가 단일 혹은 작은 군집으로 형성된다.
이런 순서대로 전개된다.
Agglomerative(응집형의) Hierarchical Clustering
: 두 번째로 중요한 clustering 방법
: k-means 와 함께 오래됐지만 아직 widespread 하게 사용된다.
Hierarchical Clustering
- 각각의 점을 singleton cluster(멤버가 하나인 cluster) 라고 부른다.
→ 가장 가까운 클러스터로 뭉치는 과정을 반복한다.
Two Approaches for Hierarchical clustering
- Agglomerative(점점 뭉쳐지는): by far the most common → our focus
- individual clusters로 부터 시작한다
- 각각의 단계에서 clusters의 closest pair 끼리 합쳐진다.
- Divisive(점점 나눠지는) : 느려서 별로 사용되지 않는다
- 하나의 all-inclusive cluster로부터 시작한다.
- 각각의 단계에서, 모든 cluster가 하나의 point를 가질 때까지 cluster를 나눈다.
Agglomerative Hierarchical Clustering의 Basic algorithm
: ‘클러스터 간의 거리를 정의’하는 방법이 가장 큰 이슈
: 모든 pair 간의 거리를 찾는 게 쉽지 않고, 한번 뭉치면 클러스터 간의 거리를 다시 계산해야 함
→ overhead 가 작지 않다
- 필요한 경우 proximity matrix(인접 행렬)을 계산한다.
- repeat
- closest(가장 가까운) 두 클러스터를 병합한다.
: 점과 점 사이의 거리라면 쉽게 구하겠지만, cluster 안의 여러 점 중에서 ‘거리’를 어떻게 정의할 것인지 정하는 건 사람마다 다를 수 있고 그에따라 결과도 달라질 수 있다. - 새 클러스터를 반영하도록 proximity matrix를 update 한다.
- until (하나의 클러스터가 남을 때까지)
Dendogram
- 계층적 클러스터링은 덴드로그램이라고 하는 트리 모양의 다이어그램을 사용하여 그래픽으로 표현
- 덴드로그램은 두 가지를 모두 표시: cluster-subcluster 관계 + 클러스터가 병합된 순서
Defining Proximity between Clusters
: Hierarchical Clustering (=linkage function)의 key operation 은 다양한 agglomerative hierarchical 기술이 있다는 것
- MIN (single link or single linkage) : 서로 다른 군집에서 가장 가까운 (closest)두 점 사이의 proximity
→ 클러스터가 커지는 것에 대한 부담이 있다. - MAX (complete link or complete linkage) : 서로 다른 군집에서 가장 먼(farthest) 두 점 사이의 proximity
→ 클러스터가 커지는 것을 감당하지 않으려고 함. - Group average (average link or average linkage) : 서로 다른 군집에 있는 모든 점 쌍의 평균 proximity
→ 가까운 점, 먼 점 모두 고려하지만 주로 먼 점에 영향력이 있으면 MAX와 유사하게 됨. MIN보다 MAX와 유사 - Ward’s method (ward’s link or ward’s linkage) : 두 군집의 병합으로 인한 SSE의 값 증가
→ SSE가 얼마나 들어날지 구하는 것 → SSE의 값이 가장 조금 늘어나는 것을 사용
→ k-means와 마찬가지로 ward’s method는 SSE 값을 최소화 하는 것
(1) Single Link or MIN
: 두 군집의 근접성은 서로 다른 두 군집에 있는 모든 두 점 사이의 거리의 최소값으로 정의된다
: 약간 길어지게 묶이는 경향이 있다
: (ex) dist( {3, 6} {2, 5} ) = min( dist(3,2), dist(3,5) , dist(6,2) , dist(6,5))
: non-elliptical shapes(타원형이 아닌 모양)에는 좋으나 노이즈 및 특이치에 민감함
(2) Complete Link or MAX
: 두 군집의 근접성은 서로 다른 두 군집에 있는 모든 두 점 사이의 거리의 최대값으로 정의된다
: 약간 원형으로 뭉쳐지는 경향이 있다
: (ex) dist( {3, 6} {2, 5} ) = max( dist(3,2), dist(3,5) , dist(6,2) , dist(6,5))
: 멀리 있는 값은 잘 안 붙으려는 경향이 있어 noise 나 outliers에 강하다.
: globular shapes 을 선호하고, 큰 클러스터의 경우 k-means와 같은 문제가 발생하다.
(3) Average Link or Group Average
: 서로 다른 군집에 있는 모든 점 쌍의 평균 proximity
: (ex) dist({3,6,4}, {2,5}) =(dist(3,2)+dist(3,5)+dist(6,2)+dist(6,5)+dist(4,2)+dist(4,5) / 6)
: MIN과 MAX 사이의 intermediate 방식 – globular clusters(구형 선호)
(4) Ward’s Method
: 두 군집의 근접성은 두 군집이 병합될 때 발생하는 SSE의 증가로 정의
: K-means clusters와 동일한 objective function 을 사용한다
: group average와 매우 유사
: 각 cluster에서 중심을 정의할 수 있는 경우에만 적용됩니다
(cf) Centroid Method
: 두 군집의 근접성은 군집의 중심 사이의 거리로 정의된다.
- centroid 방법에는 inversions(역전)이 일어날 수 있다.
→ 개념이 잘못된 것이 아니고 계층적 클러스터링에서 사용하는 순간 개념이 달라지기 때문에 잘 사용하지 않는다. - 구체적으로 왼쪽 그림의 예를 들어 설명하자면, (d1과 d3), (d2와 d3)의 거리가 각각 4.1, (d1과 d2)의 거리가 4인 경우이다.
가장 가까운 d1과 d2가 합쳐졌다. Centroid 방법을 사용하면, d1/d2와 d3의 거리가 3.5로, 기존의 4.1보다 더 작아져 역전이 발생할 수 있다는 것이다. - 이는 가정과 모순되기 때문에 종종 bad 하다고 간주한다.
- 다른 방법의 경우 merged clusters 사이의 거리가 단조롭게(monotonically) 증가한다.
Comparing Different Linkage Methods
: 위의 방법들을 한번에 볼 수 있도록 이미지로 정리한 것이다. 각각의 장/단점 및 특징을 파악하기 쉽다.
- single linkage 는 빠르고 non-globular 데이터에서 잘 수행될 수 있지만 노이즈가 있는 경우에는 제대로 수행되지 않습니다
- average and complete linkage는 cleanly separated globular cluster 에서 잘 수행되지만 그렇지 않으면 결과가 혼합됩니다
- ward는 noise가 많은 데이터에 가장 효과적인 방법
Key Issues in Hierarchical Clustering
: 계층적 클러스터링에서 고려해야 할 사항들이다
1. Initial points
- 계층적 클러스터링은 초기점을 선택하는 데 어려움이 없음 (특히 k-means 와 차별되는 장점)
2. lack of global objective function: 가까운 값을 뭉치지만, 수학적으로 clear한 목적이 없다(목적 함수가 없다)
- 각 단계에서 병합할 클러스터가 locally 하게 결정된다
- 두 클러스터를 병합하기로 결정한 후에는 나중에 취소할 수 없다
- 어려운 최적화 문제를 해결하려는 시도는 피할 수 있다
3. computational cost가 엄두도 못 낼정도로 많다
- 각 단계에서 모든 군집 쌍 사이의 거리를 계산해야 한다 → 너무 느리다는 것이 단점
4. 특이치
- 특이치는 merging process의 훨씬 나중까지 클러스터를 진행했을 때, 단일 또는 작은 군집을 형성하는 경향이 있다
- 다른 군집과 병합되지 않은 단일 또는 작은 군집을 삭제하여 특이치를 제거할 수 있다 → 계층적 클러스터링은 가까운 값을 뭉쳐 나가기 때문에, outlier는 초기에 뭉쳐질 리가 없어서 outlier를 쉽게 제거할 수 있다. 원래 계층적 클래스는 끝까지 묶지만, outlier를 대비해서 90~95% 정도만 묶기도 한다.
