2 4. Clustering

Distance

1. Euclidian Distance (유클리디안 거리)
2. Manhattan Distance (맨하탄 거리)
3. Cosine Distance (코사인 거리)
4. Minkowski Distance (민코프스키 거리)
5. Chebychev Distance (체비셰프 거리)
6. Levenshtein Distance (리벤슈테인 거리)
7. Mahalanobis Distance (마할라노비스 거리)

K-means?

• K-Means 참조
• Clustering은 비지도학습에 속하며 K-means 알고리즘은 데이터를 K개의 군집으로 묶어주는 알고리즘
• 군집의 개수를 몇 개로 설정 할 것인가?
  • Rule of thumb
  • **Elbow Method
  • 정보 기준 접근법 (Information Criterion Approach)
• 중심점 설정하는 방법
  • Randomly Select
  • Maually assign
  • K-means ++ (실제 사용되는 초기 중심 값 설정하는 방법)
• Step 1: 군집의 개수 (K) 설정
  • k=3으로 설정
• Step 2: 초기 중심점 설정 – C1, C2, C3 로 Randomly 선택 가정
• Step 3 : 데이터를 군집에 할당(배정)
  • 거리 상 가장 가까운 군집(중심점)으로 주어진 데이터를 할당 또는 배정하는 단계
  • 거리 측정 방법은 일반적으로 유클리디안 거리로 측정
  • 가장 가까운 C들과 같은 군집으로 묶임
• Step 4 : 중심점 재설정(갱신)
  • C1, C2, C3 각각의 중심점은 그 군집의 속하는 데이터들의 가장 중간(평균)에 위치한 지점으로 재설정
  • 중심점 C1은 데이터 1, 2의 평균인 지점으로 C2는 데이터 3, 4의 평균인 지점으로, 중심점 C3은 데이터 5, 6의 평균인 지점으로 갱신 됨
• Step 5 : 데이터를 군집에 재할당(배정)
  • 더 이상 중심점의 이동이 없을 때까지, step4와 step5를 반복함
• 실습: 13. K-means Code

Hierarchical Clustering

• K-means와 달리 군집 수(K)를 사전에 정하지 않아도 학습을 수행할 수 있음
  • 개체들이 결합되는 순서를 나타내는 트리 형태의 구조인 덴드로그램(Dendrogram) 덕분임
• 덴드로그램 생성한 후 적절한 수준에서 트리를 자르면 전체 데이터를 몇 개 군집으로 나눌 수 있게 됨
• HC의 경우 계산 복잡성은 𝐎(𝒏^𝟑 )으로 K-means 보다 무거운 편임
• Step 1 : HC를 수행하려면 모든 개체들 간 거리(Distance)나 유사도(Similarity)가 이미 계산 되어 있어야함
  • 주어진 학습데이터의 개체 수가 4개이고 아래 그림처럼 거리 행렬을 이미 구해놨다고 가정
• Step 2 : 거리가 가까운 관측치들끼리 차례대로 군집으로 묶음
  • [A-D]가 하나의 군집으로 묶이면서 군집과 데이터 혹은 군집과 군집 간의 거리를 계산해야 함
  • 총 4개의 계산 방식이 존재 (계산양은 4개다 비슷함)
• Step 3 : 군집과 데이터(군집) 간 거리를 다시 계산함
  • 유사도 테이블 업데이트 후 묶어줌
• Step 4 : 분석 대상 관측치가 하나도 없으면 학습을 종료
• 실습: 14. Hierarchical Clustering Code

Spectral Clustering

• [Graph 구축 → Graph Edge Cut]
• • Spectral Clustering을 수행하기 위해서는 데이터를 그래프로 변환하기 위해 인접행렬(Adjacency Matrix)을 만들어야 함
    • 인접행렬을 만들 때 보통 가우시안 커널(Gaussian kernel)을 많이 사용함
• 무방향 가중치 그래프(Undirected Weighted Graph)를 사용함
  • LIME처럼 가까우면 가중치를 많이 주고, 멀면 가중치를 적게 줌
• Graph 구축
  • Fully connected graph란 모든 노드(데이터)가 엣지로 연결돼 있는 그래프를 칭함
  • ε-neighborhood graph란 거리가 ε보다 가까운 엣지들만 살리고 나머지는 끊어버린 그래프
    • K-NN Graph는 각 노드 주변 k개 이웃들만 엣지로 연결하고 나머지 엣지는 끊어놓은 그래프
  • ε-neighborhood graph는 노드의 밀도가 높은 지역에선 엣지가 지나치게 많이 발생하고, 밀도가 낮은 지역에선 엣지가 하나도 없는 노드가 발생
    • K-NN Graph는 끊기는 노드가 발생하진 않지만, 군집이 극단적으로 멀리 떨어져 있는 경우 군집과 군집 사이는 연결되지 않는 경우가 발생
  • 일반적으로 그래프를 구축할 때는 ε-neighborhood graph를 먼저 구축한 뒤 K-NN Graph를 적용하여 엣지가 없는 노드도 연결 하는 방식을 씀
  • 그럼에도 불구하고 군집 사이가 너무 멀어서 연결이 안되는 경우 발생할 수 있는데, 이럴 때는 Minimum spanning tree 방법도 자주 사용
• Graph Cut 지표
  • Graph Cut은 Graph를 특정 기준에 의해 두 개 이상의 Subgraph로 나누는 것을 의미함
  • Subgraph가 바로 Spectral Clustering의 학습 결과물인 군집이 되는 것
    • Cut(A, B) : A에서 B로 향하는 엣지들의 가중치 합 (0.1 + 0.2 = 0.3)
    • Cut(A, A) : A에서 A로 향하는 엣지들의 가중치 합 (0.8 + 0.8 + 0.6 = 2.2)
    • Cut(B, B) : B에서 B로 향하는 엣지들의 가중치 합 (0.8 + 0.8 + 0.7 = 2.3)
  • Subgraph가 바로 Spectral Clustering의 학습 결과물인 군집이 되는 것
    • Vol(A) : A에 속한 노드에 연결된 엣지들의 모든 가중치 합
      • [① : 0.8 + 0.6 + 0.1] + [② : 0.8 + 0.8] + [③ : 0.2 + 0.6 + 0.8] = 4.7 → Vol(A) = Cut(A, A) + Cut(A, B)
    • Vol(B) : B에 속한 노드에 연결된 엣지들의 모든 가중치 합
      • [⑤ : 0.1 + 0.8 + 0.8] + [⑥ : 0.8 + 0.7] + [④ : 0.2 + 0.7 + 0.8] = 4.9 → Vol(B) = Cut(B, B) + Cut(A, B)
• Minimum Cut Method
  • Graph를 A와 B라는 Subgraph로 나눌 때 끊어지는 엣지들의 가중치가 최소가 되도록 하는 방법
  • 최종적으로 도출된 𝒘𝟏𝟒, 𝒘𝟐𝟑은 원 Graph에서 두 개 Subgraph로 나눠질 때 끊어지는 가중치들 임
    • 끊어진 가중치를 제외하고 붙어 있는 가중치들만 보면 두 개의 Subgraph 완성!
• 실습: 15. Spectral Clustering Code

DBSCAN

• Density-Based Spatial Clustering of Applications with Noise
• DBSCAN은 밀도 기반의 기법이며 세밀하게 몰려 있어서 밀도가 높은 부분을 Clustering 하는 기법
  • 점 p가 있다고 할 때, 점 p에서 부터 거리 e(epsilon)내에 점이 m(minPls)개 있으면 하나의 군집으로 인식함
  • 따라서 e와 m이 Hyperparameter임
• K-means와 같이 Cluster의 수를 정하지 않아도 됨
• Cluster의 밀도에 따라 Cluster를 서로 연결하기 때문에 기하학적인 모양을 갖는 군집도 잘 찾을 수 있음
• K-means와 같이 Cluster의 수를 정하지 않아도 됨
• Cluster의 밀도에 따라 Cluster를 서로 연결하기 때문에 기하학적인 모양을 갖는 군집도 잘 찾을 수 있음
• DBSCAN을 활용하여 이상치를 발견할 수 있음
• DBSCAN은 Cluster 결과가 이상치에 영향을 받지 않음
• 다양한 모양의 Cluster 패턴도 잘 잡아 낼 수 있음

• 구현이 비교적 쉬움

• 고차원 데이터 대해서 잘 작동하지 않음

• Sparse Data에 대해 결과가 좋지 못함

• 실습: 16. DBSCAN Code

HDBSCAN

• Hierarchical Density-Based Spatial Clustering of Applications with Noise
• DBSCAN은 Local density에 대한 정보를 반영해 줄 수 없으며 Data들의 계층적 구조를 반영한 Clustering이 불가능함

• HDBSCAN의 경우 더 이상 epsilon(e)이 필요하지 않음

• Transform the space according to the density/sparsity.
  • Distance를 더 Robust(이상치, noise에 강한)하게 만들어주는 작업
  • 𝒄𝒐𝒓𝒆𝒌(𝒂) : a의 이웃과의 거리
  • 𝒄𝒐𝒓𝒆𝒌(𝒃) : b의 이웃과의 거리
  • 𝐝(𝒂,𝒃) : a, b의 자체 거리
  • dense한 지점의 data는 𝒄𝒐𝒓𝒆𝒌가 매우 작기 때문에 𝐝(𝒂,𝒃) 값을 사용하고, dense가 낮은 지점의 경우 𝒄𝒐𝒓𝒆𝒌 의 주변 정보를 사용하게 됨
  • Distance의 robustness를 늘리고, 최종적으로는 더 효율적인 Clustering을 가능하게 함
• Build the minimum spanning tree of the distance weighted graph.
  • Robust Distance를 계산한 정보를 가지고 Minimum spanning tree를 구축함
  • Spanning Tree는 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안됨
• Construct a cluster hierarchy of connected components.
  • 계층 (Hierarchy)를 만드는 과정 중 하나
  • Robust Distance의 Cut을 점점 높여가며 하나씩 Graph의 Edge를 끊어 나감
  • 그리고 만들어진 Minimum spanning tree를 가장 가까운 거리부터 묶어줌
    • HC에서 군집들 간 거리를 계산해서 묶어 주는 것과 같은 원리
• Condense the cluster hierarchy based on minimum cluster size.
  • Robust Distance가 0.4 이하로는 거의 모든 데이터가 1개로 떨어져 나오는 지저분한 상황이 발생함
    • 이러한 경우 Noise 처럼 보일 수 있음
  • 따라서 minimum size 이상의 크기를 가진 component 들만 남게 만들다
    • minimum size는 HDBSCAN의 Hyperparameter-> Hyperparameter가 1개!
• Extract the stable clusters from the condensed tree.
• 실습:17. HDBSCAN Code

평가는?

• Clustering 평가 지표를 활용하여 Clustering의 결과를 확인해야 함
  • Clustering 결과에 대한 평가지표는 확실한 것이 없음
  • Clustering은 비지도 학습이기 때문에 정답과 비교할 수 없기 때문
• Elbow point 찾기
• Clustering의 결과 평가 지표는 크게 3개의 카테고리가 존재함
  • External : 우리가 알고 있는 정답(Label)과 비교해 봄 (있을 수 없음)
  • Internal : Cluster들의 공간들을 확인해보는 방법
  • Relative : Cluster의 공간과 Cluster들 간 떨어진 정도를 가지고 판단할 수 있음
• Dunn Index
  • 군집 간 거리의 최소 값(좌측 하단)을 분자, 군집 내 요소 간 거리의 최대 값(우측 하단)울 분모로 하는 지표
  • 군집 간 거리(RED)는 멀수록, 군집 내 분산(BLUE)은 작을 수록 좋은 군집화 결과라고 말해주는 지표
• Silhouette Score
  • Dunn Index의 경우 Clustering의 유효성을 검증하기 위한 하나의 값이 있음
  • Silhouette Score는 개체별로 그 적합성이 평가 됨(값이 1에 가까울수록 군집화가 잘 되었다고 판단함)