머신러닝(4): Clustering

1. K-means

-비지도학습으로 데이터를 K개의 군집으로 묶어주는 알고리즘

Step 1: 군집의 개수(K) 선정 #직접 설정하며 몇 개를 정할 지는 Rule of thumb, Elbow method, 정보 기준 접근법 활용 Step 2: 초기 중심점 설정 # Randomly Select, Maually assign, K-means(++) Step 3: 데이터를 군집에 할당(배정) Step 4: 중심점 재설정(갱신) Step 5: 데이터를 군집에 재할당(배정)

2. Hierarchical Clustering:

-군집 수를 사전에 정하지 않아도 학습을 수행, 덴드로그램 생성 후 적절한 수준에서 트리 CUT

Step 1: 모든 개체들 간 거리와 유사도를 미리 계산 #유클리디안, 마할라노비스, etc Step 2: 거리가 가까운 관측치 간 차례대로 군집 형성 Step 3: 군집과 데이터(군집)간 거리를 재계산 Step 4: 분석 대상 관측치가 하나도 없으면 학습 종료

3. Spectral Clustering:

 -인접행렬(가우시안 커널), 무방향 가중치 그래프를 사용 

Step 1:Graph 구축  -Fully connected graph:모든 노드(데이터)가 엣지로 연결돼 있는 그래프  -e-neighborhood graph: 거리가 입실론보다 가까운 엣지들만 살리고 나머지는 끊어버리는 그래프  -K-NN graph: 각 노드 주변 k개 이웃들만 엣지로 연결하고 나머지 엣지는 끊어놓은 그래프  -Minimum spanning tree: 모든 정점들이 연결되어 있고 사이클을 포함하지 않는 그래프 #군집 사이가 너무 멀어 연결이 안될 때 Step 2: Graph Cut 지표  -Graph를 특정 기준에 의해 2개 이상의 Subgraph로 나누는 것  -서브 그래프 = 스펙트럴 클러스터링의 군집(학습 결과물)  -Minimum Cut method: 그래프를 a와 b라는 서브 그래프로 나눌 때 끊어지는 엣지들의 가중치가 최소가 되도록 하는 방법

 4. DBSCAN:

 -밀도 기반 밀도가 높은 부분을 클러스터링 하는 기법

Step 1: 점 p에서 부터 거리 e(epsilon)내에 점이 m(minPls)개 있으면 하나의 군집으로 인식 # e = 하이퍼 파라미터 Step 2:  p를 이동했을 때 Core point를 만족하는 경계를 찾아 반복 # 일부충족 시 Boders(경계점으로 구분), 완전불충족: noise

 5. HDBSCAN:

 -계층적 구조를 반영한 클러스터링 가능, epsilone이 필요하지 않음

Step 1: minimum spanning tree 구축 Step 2: Robust Distance의 Cut을 높여가며 하나씩 Graph Edge를 끊어나감 Step 3: 미니멈 스패닝 트리를 가장 가까운 거리부터 묶어줌

★DBSCAN vs HDBSCAN: 노이즈 처리 차이(DBSCAN은 대부분을 노이즈로 구분)

---

평가지표:

• Dunn Index: 군집 간 거리의 최소값을 분자, 군집 내 요소 간 거리의 최대값을 분모로 하는 지표 #클수록 Good
• Silhouette Score: 개체별로 적합성 평가 #1에 가까울수록 군집화가 Good