9. 군집화
**지금까지는 supervised learning, 이제 unsupervised learning할 차례**
Clustering
Clustering(군집화)
- 서로 비슷하거나, 유사한데이터를 같은 군집에, 다른 데이터들이 다른 군집!
- 데이터에 레이블 없는 비지도 학습방법
- 응용분야
1) 이해 : 서로 관련된 문서 표현, 비슷한 기능을 수행하는 유전자, 비슷한 주식들의 그룹을 확인
2) 요약 : 큰 데이터 셋 사이즈 축소
군집화의 유형
- 군집화: 여러 군집들의 집합
- 분할적 군집화 : 데이터들을 겹치지 않는 부분집합으로 분할해, 하나의 데이터-하나의 부분집합
- 계층적 군집화 : 계층적 구조를 이루는 서로 중첩된 군집들
군집의 다른 구별들
- 배타적 vs 비배타적
: 비배타적 (데이터 여러군집 ok) -> 경계선상의 데이터 표현에 적합
- Fuzzy vs non-fuzzy
: 하나의 데이터가 모든 군집에 0~1 가중치 갖고 소속. 가중치 합 1. 확률적 군집화와 유사
- 부분 vs 완전
: 대부분은 완전
- 비균질 vs 균질
: 서로 다른 크기, 모양, 밀도의 군집 확인
k-means clustering
k-means clustering
- 분할적 군집화 방법론
- 각 군집에는 중심점 존재.
- 각 데이터는 자신과 가장 가까운 중심점을 가진 군집에 할당
: 초기 중심저믄 종종 임의로 선택. 중심점에 따라 다른 군집
: 주로 중심점 = 군집에 소속된 데이터들의 평균
: 가까움 = 유클리디안, 코사인유사도, 상관관계로 정의
- 군집의 수 미리 결정
- 유사성 측도에 수렴함.
k-means clustering의 평가방법
- 오차제곱합(SSE)
- SSE 작은게 군집화 잘되는 것 !
- 다만, SSE를 감소시키기 위해 K를 증가시켜야함.
- 그러나, 낮은 k로 좋은 군집화를 수행하면 높은 k를 좋지않은 군집화를 수행한 것 보다
낮은 SSE얻을 수 있음
- k개 군집 존재하는 경우, 임의로 뽑 았을 때 하나의 대표점이 제대로 선택될 확률 매우 낮음
- k가 커질수록 확률이 낮아짐.
Solution to initial centroids problem
- 반복
- 일부 데이터 샘플링 -> 계층적 군집화 적용해 초기 대표값 확인
- k보다 많은 초기 대표값 잡은 후, 이중 서로 멀리 있는 k개의 대표값 선택
- 후처리
- bisecting K-means (k두개로 계속 쪼갬 배아처럼)
k-means의 한계
1) 서로 다른 크기의 군집
2) 서로 다른 밀도의 군집
3) 원형이 아닌 모양의 군집
4) 이상치에 민감하게 반응
=> 평균대신 중앙값 사용하면 이상치에 덜 민감해짐
Hierarchical Clustering
hierarchical clustering
- 계층구조를 이용!
- 덴드로그램을 이용해 시각화
- 군집의 수를 미리 결정 X 적정한 cuttingline을 조절해 군집의 수 결정
- 의미있는 분류체계 ex) 동물킹덤...
- 전통적으로 유사도, 거리행렬
- 한번에 한쌍의 군집 병합 or 분리
1) 병합
- 각 데이터를 군집으로 간주
- 원하는 수의 군집이 남을 때까지 가장 가까운 군집의 쌍을 병합
2) 분리
- 모든 데이터를 포함하고 있는 하나의 군집에서 시작
- 원하는 수의 군집이 생성될때까지 군집을 분리
병합
- 널리 사용되는 계층적 군집화 방법
- 단순하고 직관저긴 알고리즘
- 처음 군집 -> 각 군집마다 proximit matrix -> 가까운 군집 2개 병합 -> matrix update
- 두 군집의 근접도를 계산하는 것이 핵심 ! : 거리를 정의하는 서로 다른 방식이 서로다른 알고리즘 구분요소
- 거리정의 방식 (어떤 군집과 어떤 군집이 비슷한지 어떻게 판단해!)
1) Min (point끼리 가장 가까운 거리) = 싱글링크
: 서로간의 유사도가 가장 큰 데이터들을 이용해 군집간의 유사도 계산
: 타원아닌것도 ok
: noise나 outlier에 민감하게 반응
2) Max(point끼리 가장 멀게 만드는 거리)
: 각 군집에 속한 데이터들 주 서로간의 유사도가 가장 작은 데이터 이용해 군집간 유사도
: 그 outlier나 noise에 강하다 좀더 동그람!
: 하지만, 큰 클러스터를 찾지 못하는 경향!!
: 단점 : '구형'의 군집을 형성하려고함.
3) Group average(r군집군집의 모든 거리의 평균)
: 각 군집에 속한 데이터들의 평균 유사도 !
: 싱글링크 min과 max사이의 절충
: 장점은 noise에 덜 민감함
: 단점 : 구형의 군지블 형성하려는 경향
4) Distance Between Centroids(대표값들 사이의 거리)
5) Cluster Similarity : Ward's method
: 군집병합내 데이터들 사이의 거리를 이용해 두 군집 사이의 유사도
: 노이즈 이상치에 덜 민감
: 구형의 군집 형성하려는 경향
: k-means의 초기값 결저에 사용
문제와 한계
1) 한번에 한 군집을 병햡하기로 결정하면 다시 분리 X
2) 직접적으로 최적화하는 목적함수 X
3) 서로다른 바법론들은 다음중 하나이상의 약점
- 노이즈와 이상치에 민감 (MIN)
- 군집의 크기와 모야을 조절하기 어려움 (MAX, Group, Similarity)
- 큰 군집을 분리하려는 경향 (MAX)
Cluster Validity (= 분류문제)
- 지도학습 분류문제에선 accuracy, precision, recall등 모델 작동 평가 가능
- 군집분석에선, '좋은'정도를 측정하는게 문제 이게 주관적!
- 그럼에도 평가이유
: 노이즈 에 적합되는 패턴 피하려고
: 군집화 방법 비교 (수치화)
: 두 군집화 결과를 비교하기 위해
: 두 군집을 비교하기 위해
어떻게 평가해야 하는가?
1) 데이터의 군집화 경향성 (실제로 데이터 안에 임의적이지 않은 구조 존재?)
2) 군집화 결과를 실제의 레이블과 비교가능 (데이터들의 실제 레이블 주어진 경우)
3) 외부정보 없이 군집 분석방법이 얼마나 적절하게 군집화 (데이터만 사용)
4) 서로 다른 군집화 결과 사이에 어느것이 우수한지
5) 알맞은 군집 화긴 위해 (k-means의 경우 k값을 바꿔가며!)
수치적 방법
- External index : 외부에서 주어진 class 레이블과 군집레이블을 비교해 군집평가
- Internal index : 외부정보 없이
- Relative index : 두 군집화 또는 군집 비교해 평가
실전!
- 유사도 행렬을 군집 레이블에 따라 정렬, 유사도 판단
: 두 행렬의 상관관계 계산
: 두 행렬의 유사도가 트다면, 같은 군집에 속한 데이터들이 서로 유사함을 의미
- 군집안에 데이터 얼마나 연관되어있는지 (군집내부의 SSE) (늘려)
- 하나의 군집이 다른 군집으로부터 얼마나 잘 분리되거나 구분될 수 있는지( 군집간의 거리제곱합) (줄이고 )
=> 이게 clustering의 목적!!
- 두 군집의 비교 (ARI) : 함께 소속된 pair측정
