Distance와 Similarity
유클리디안 거리 : 벡터거리
맨하탄 : 좌표간 절댓값차이
코사인 거리 : 벡터사이 각도
민코프스키 거리 : 맨하탄과 유클리디안 사이의 동적관계
체비셰프 거리 : 인근 8개 셀에 같은 거리처리
리벤슈타인 거리 : 편집거리 (문자열 A와 B가 같아지기 위한 거리)
마할라노비스 거리 : 데이터의 분포를 고려한 거리
1.K-means
- Clustering은 비지도학습에 속하며 K-means 알고리즘은 데이터를 K개의 군집으로 묶어주는 알고리즘
Step 1: 군집의 개수 (K) 설정
-
데이터를 준비한 뒤 가장 먼저 해야 할 것은 군집의 개수를 결정해야함 (사람이)
-
K-means 알고리즘의 한계점 중에 하나
-
군집의 개수 설정을 어떻게 하냐에 따라 결과가 크게 달라지며, 터무니 없는 결과가 나올 수 있음
-
군집의 개수를 몇 개로 설정 할 것인가?
-
Rule of thumb
-
Elbow Method
-
정보 기준 접근법 (Information Criterion Approach)
Step 2: 초기 중심점 설정
-
K개의 초기 중심점 (Center of Cluster, Centroid)을 설정하는 단계
-
K-means 알고리즘은 초기 중심점으로 어떤 값을 선택하는가에 따라 성능이 크게 달라짐
-
중심점 설정하는 방법
-
Randomly Select
-
Maually assign
-
K-means ++ (실제 사용되는 초기 중심 값 설정하는 방법)
Step 3 : 데이터를 군집에 할당(배정)
-
거리 상 가장 가까운 군집(중심점)으로 주어진 데이터를 할당 또는 배정하는 단계
-
거리 측정 방법은 일반적으로 유클리디안 거리로 측정
Step 4 : 중심점 재설정(갱신)
-
C1, C2, C3 각각의 중심점은 그 군집의 속하는 데이터들의 가장 중간(평균)에 위치한 지점으로 재설정
-
중심점 C1은 데이터 1, 2의 평균인 지점으로 C2는 데이터 3, 4의 평균인 지점으로, 중심점 C3은 데이터 5, 6의 평균인 지점으로 갱신 됨
Step 5 : 데이터를 군집에 재할당(배정)
- 더 이상 중심점의 이동이 없을 때까지, step4와 step5를 반복함
2.Hierarchical Clustering
- K-means와 달리 군집 수(K)를 사전에 정하지 않아도 학습을 수행할 수 있음
- 개체들이 결합되는 순서를 나타내는 트리 형태의 구조인 덴드로그램(Dendrogram) 덕분임
- 덴드로그램 생성한 후 적절한 수준에서 트리를 자르면 전체 데이터를 몇 개 군집으로 나눌 수 있게 됨
Step 1 : HC를 수행하려면 모든 개체들 간 거리(Distance)나 유사도(Similarity)가 이미 계산 되어 있어야함
Step 2 : 거리가 가까운 관측치들끼리 차례대로 군집으로 묶음
- [A-D]가 하나의 군집으로 묶이면서 군집과 데이터 혹은 군집과 군집 간의 거리를 계산해야 함
- 총 4개의 계산 방식이 존재 (계산양은 4개다 비슷함)
Step 3 : 군집과 데이터(군집) 간 거리를 다시 계산함
- 유사도 테이블 업데이트 후 묶어줌
Step 4 : 분석 대상 관측치가 하나도 없으면 학습을 종료
특징
-
K-means와 달리 사전에 군집수 k를 설정할 필요 없음
-
덴드로그램의 최상층을 끊어주면 A, D, C와 B 두 개 군집이 도출 됨
-
두번째 층을 끊으면 A, D와 C, B 이렇게 세 개 군집이 나옴
-
HC의 경우 계산 복잡성은 O(n3)으로 K-means 보다 무거운 편임
3.Spectral Clustering
-
[Graph 구축 → Graph Edge Cut]
-
Spectral Clustering을 수행하기 위해서는 데이터를 그래프로 변환하기 위해 인접행렬(Adjacency Matrix)을 만들어야 함
-
인접행렬을 만들 때 보통 가우시안 커널(Gaussian kernel)을 많이 사용함
-
무방향 가중치 그래프(Undirected Weighted Graph)를 사용함
-
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)
-
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로 나눌 때 끊어지는 엣지들의 가중치가 최소가 되도록 하는 방법
[Spectral Clustering]
- Hyperparameter Tuning using for Loop
[Spectral Clustering Parameters]
- Package : https://scikit-learn.org/stable/modules/generated/sklearn.cluster.SpectralClustering.html
- n_clusters : Cluster 개수 (K)
- affinity : 유사도 행렬 만드는 방법
- ‘nearest_neighbors’: construct the affinity matrix by computing a graph of nearest neighbors.
- ‘rbf’: construct the affinity matrix using a radial basis function (RBF) kernel.
- Gaussian Kernel
- ‘precomputed’: interpret X as a precomputed affinity matrix, where larger values indicate greater similarity between instances.
- ‘precomputed_nearest_neighbors’: interpret X as a sparse graph of precomputed distances, and construct a binary affinity matrix from the n_neighbors nearest neighbors of each instance.
- n_neighbors : 유사도 계산시 주변 n개를 보고 판단할 것 인지
- Number of neighbors to use when constructing the affinity matrix using the nearest neighbors method. Ignored for affinity='rbf'
