Hierarchical Clustering
K-Means clustering은 clusters의 숫자를 선택하는 것을 요구합니다.
만일 그렇게 하는 것을 원치 않는다면, 대안으로 Hierarchical Clustering을 사용합니다.
Hierarchical Clustering은 Dendogram고 불리는 관측치의 트리 기반 표현을 생산하는 추가적인 이점이 있습니다.
Dendograms
먼저 가장 가까운 포인트들(5 and 7)을 join 합니다.
Fusing/Mergin(세로축)의 높이는 points의 유사도를 나타냅니다.
Points가 합쳐진 후엔 하나의 관측치로 다루어지고 알고리즙을 진행합니다.
Interpretation
Dendogram의 각 'leaf'는 45 관측치 중 하나를 나타냅니다.
Dendogram의 밑바닥에서 각 관측치는 별개의 leaf입니다.
그러나 트리가 올라갈수록 몇몇 leaves는 fuse됩니다.
이것은 관측치들이 서로 유사점이 많다는 것과 대응합니다.
Tree가 위로 올라갈 수록 fuse 되는 관측치의 숫자가 증가합니다. 더 먼저(lower in the tree) 두 관측치가 fuse 될수록 둘 사이에는 더 많은 유사 접이 있습니다.
나중에 fuse 된 관측치들은 꽤 다르다고 할 수 있습니다.
Choosing Clusters
Clusters를 선택하기 위해서 dendogram을 가로지르는 lines을 그리면 됩니다.
멈추고 싶은 곳이 어딘지에 따라 clusters의 수를 결정합니다.
Algorithm (Agglomerative Approach)
The dendogram은 다음과 같이 만들어집니다.
분리된 cluster (n clusters)가 각 point인 채로 시작합니다.
모든 points/clusters 사이의 비유 사성을 측정합니다.
가장 유사하게 보이는 두 개의 clusters를 fuse 합니다. 그럼 지금은 n-1 clusters가 있습니다.
다음으로 가장 유사하게 보이는 두 개의 clusters를 fuse합ㄴ디ㅏ. n-2 clusters가 있습니다.
1 cluster가 될 때까지 계속합니다.
An Example
9 clusters로 시작합니다.
5와 7을 fuse 합니다.
6과 1을 fuse 합니다.
(5, 7) cluster와 8을 fuse 합니다.
모든 관측치가 fuse 할 때까지 계속합니다.
How do we define dissimilarity?
Hierarchical clustering은 한 가지 명백한 issue를 포함합니다.
어떻게 dissimilarity나 linkage를 정의할 수 있을까요? fused (5, 7) cluster와 8의 관계를?
4개의 선택지가 있습니다.
Complete Linkage
Single Linkage
Average Linkage
Centriod Linkage
Linkage Methods : Distance Between Clusters
Complete Linkage : 관측치 사이의 가장 큰 거리입니다.
Single Linkage : 관측치 사이의 가장 작은 거리입니다.
Average Linkage : 관측치 사이의 평균 거리입니다.
Centroid : 관측치의 중심 사이의 거리입니다.
Linkage Can be Important
같은 데이터에서 세 개의 clustering을 진행했습니다.
Linkage method만 다르게 한 것이지만 결과는 매우 다릅니다.
Complete와 average linkages는 균일한 사이즈의 clusters를 만드는 경향이 있고
single linkage는 single leaves가 하나씩 fuse 된 확장 clusters를 만드는 경향이 있습니다.
Choice of Dissimilarity Measure
The dissimilarity 측정으로 Euclidean distance를 고려했습니다.
그러나 어떤 경우에는 correlation based distance가 대안일 수 있습니다.
Comparing Dissimilarity Measures
3개의 관측치와 p = 20 variables를 가지고 있습니다.
Euclidean distance observation의 경우 1과 3이 유사합니다.
그러나 obs. 1과 2는 높은 상관성을 가집니다. 그러므로 correlation measure의 관점에서 유사하게 고려됩니다.
Online Shopping Example
고객마다 구매한 아이템의 수를 기록합니다.
Euclidean distance를 사용하여, 가장 적게 구매한 고객을 함께 cluster 하려고 합니다.
Correlation measure를 사용하여, 같은 유형의 물건을 구매하는 경향이 있는 고객들을 함께 cluster하려고 합니다(구매의 규모가 꽤 다를지라도).
Standardizing the Variables
온라인 shop에서는 두 가지 items만 팔고 있습니다. socks and computers
왼쪽 : Quantity의 관점에서, socks가 더 높은 weight를 가집니다.
중앙 : Standardizing 후에, socks와 computers는 똑같은 weight를 가집니다.
오른쪽 : Dollar sales의 측면에서, computers는 더 높은 weight를 가집니다.
Practical Issues in Clustering
Clustering을 수행하기 위해서는 몇몇 결정들이 반드시 이루어져야 합니다.
The features를 표준화시켜야 합니까? varialbes를 평균이 0이고 표준편차가 1이 되도록 합니다.
Hierarchical clustering의 경우 :
어떤 비유 사성 측정 방법이 사용되었습니까?
어떤 유형의 linkage가 사용되었습니까?
Clusters를 획득하기 위해서 어디에서 dendogram을 잘라야 합니까?
K-means clustering의 경우 :
얼마나 많은 clusters를 설정해야 합니까?
실제로, 몇 개의 다른 선택들을 시도하고 가장 유용하거나 해석하기 쉬운 solution을 하나 찾아야 합니다. 물론, 정답은 없습니다.
Final Thoughts
가장 중요한 것은, 어떻게 clustering analysis의 결과가 보고되는지입니다.
결과들은 데이터 셋에 관한 절대적인 truth로 여겨선 안됩니다.
오히려 과학적 가설의 발전과 추가 연구, 바람직하게는 독립적인 데이터에 대한 출발점으로 구성해야 합니다.
Exercise
5개의 관측치가 있다고 가정해보고 similarity (distance) matrix를 계산했습니다.
|
A |
B |
C |
D |
E |
|
|
A |
0 |
||||
|
B |
9 |
0 |
|||
|
C |
3 |
7 |
0 |
||
|
D |
6 |
5 |
9 |
0 |
|
|
E |
11 |
10 |
2 |
8 |
0 |
Similarity matrix을 기반으로 complete linkage를 사용하여 5개의 관측치들을 hierarchically clustering부터 나온 dendogram을 스케치해보세요.
댓글