Clustering에 대해서 배워보자.
여기부터는 unsupervised learning에 대해서 배워볼 것이다!
자세히
Super: Regression, Classification…
Unsuper: 차원 축소, Clustering…
[Unsupervised Learning]
What
label 없이 분류한다.
(따라서 정답이 없다고 할 수 있다. 이렇게 분류하는 것이 맞는지, 저렇게 분류하는 것이 맞는지 정답이 없을 수도 있다. 라벨이 없기 때문에 생기는 문제이다)
Application
비슷한 화제의 뉴스끼리 분류해 준다.
관심이 비슷한 SNS 친구를 추천해 준다.
…
[Clustering]
Type
클러스터링 종류는 다음과 같다.
- Hierarchical clustering
- K-means clustering
- Gaussian Mixture Model
- Spectral clustering
++ clustering은 정해진 정답이 없다.
개발자 입장에서는 label이 없기 때문에 “뭐가 맞다!”를 알 수가 없다.
이는 이를 요구한 전문가가 자신의 입맛대로 판단해야 한다.
[Hierarchical Clustering]
What
거리가 가까운 것들을 찾고 이들을 묶거나 나눈다!
장점: 원하는 level로 자를 수 있다.
ex. 최종적으로 Tree 형태를 구현하고 나면 원하는 height 만큼 자르면 된다.
Top-Down
Division
가장 먼 것부터 쪼개는 방식이다.
이 부분은 수업 시간에 자세히 다루지는 않는다.
Bottom-Up
Agglomerative
가장 가까운 것부터 묶는 방식이다.
거리 구하는 방법?
개개인 간의 거리는 KNN에서 배웠던 distance를 구하는 방법을 통해서 구할 수 있을 것이다.
cluster 간의 거리 구하는 방법?
세 가지 방법이 존재한다.
- single linkage: 두 클러스터에서 가장 가까운 원소 두 개를 뽑아 거리 비교를 한다.
- complete linkage: 두 클러스터에서 가장 먼 원소 두 개를 뽑아 거리 비교를 한다.
- average linkage: 두 클러스터 모두의 평균 거리를 비교 한다.
예시를 통해 자세히 알아보자.
example of single linkage
거리가 가까운 순서 대로 묶는다. cluster 간의 거리는 min 값을 이용한다.
- A-B
- D-E
- A-B cluster - C
- A-B-C cluster - D-E cluster
- A-B-C-D-E cluster - F
example of complete linkage
거리가 가까운 순서 대로 묶는다. cluster 간의 거리는 max 값을 이용한다.
- A-B
- D-E
- A-B cluster - C
- D-E cluster - F
- A-B-C cluster - D-E-F cluster
[K-means Clustering]
What
K는 cluster의 개수
ex. K=2일 때, clustering을 진행해 보자.
- 초기 상태는 밑과 같을 것이다.
- 이후에 EM 알고리즘을 이용해서 cluster를 생성한다.
- 최종적으로 final cluster와 mean을 찾으면 알고리즘이 종료 된다.
K-means Optimization (EM algorithm)
Cost Function
이걸 바탕으로 hutistic하게 구한다.
(cost function을 직접 optimizing하기 어려운 형태이기 때문에 huristic하게 구하는 것이다..)
EM 알고리즘
- initial choice of means를 선택한다. (random)
- E step: 가장 잘 나눌 수 있는 선을 optimize한다.
- M step: means를 optimize한다.
means가 변하지 않을 때 까지 반복한다.
Limitation
한계 점
- Categorical label들에 대해 적합하지 않다. (숫자가 아닌 라벨…)
- Outlier들에 약하다.
- 속도가 느리다.
- local optima를 찾는 방법이다.
자세히
EM 알고리즘으로 휴리스틱하게 푸는 것은 global optima를 찾지 못한다.
밑과 같이 학습할 때마다 결과가 달라질 수 있기 때문이다.
따라서 여러 번 해야한다.
Extra..
K-median, K-center 같은 것들도 있다…