[ML][패턴인식] 10. 군집화(clustering)

class discovery
supervised learning : 샘플의 부류 정보가 주어진 상황에서의 학습
unsupervised learning : 부류 정보가 없음

10.2.2 거리와 유사도 측정
Minkowski 거리 : 가장 널리 쓰이는 거리 척도
p를 변화시키면 여러가지 거리 척도를 만들 수 있다.
유클리디언 거리 : p=2, 가장 널리 사용함
도시 블록 거리(맨하탄 거리) : p= 1

군집화 알고리즘 : 계층, 분할, 신경망, 통계적 탐색
10.4 계층 군집화 알고리즘(hierarchical clustering)
A. 응집 : 작은 군집들에서 출발하여 이들을 모아 나감
B. 분열 : 큰 군집에서 출발하여 이들을 나눔

10.5 분할 군집화(partitional clustering)
- 대부분은 미리 군집의 개수 k를 알려주어야 함
10.5.1. 순차 알고리즘 : 샘플을 순차적으로 군집에 할당
각 샘플을 차례로 살펴보고 가장 가까운 군집까지의 거리가 임계값보다 작으면 그 군집에 속하는 것으로 간주하여 그 군집에 넣는다.
군집의 개수를 자동으로 찾아준다.
임계 값을 지정해 주어야 하는데 추정하기가 어렵다.
10.5.2. k-means : 초기 분할을 가지고 출발하여 계속 개선해 나감
가장 인기가 높고 널리 쓰이는 군집화 알고리즘
k개의 군집 중에 가장 가까운 것을 찾아 그것에 배정하고 군집의 중심을 평균으로 대치한다.
그리고 평균을 중심으로 가장 가까운 것을 찾아 배정한다.
위를 반복 후 변경이 없을 때까지 돌린다.

- MST알고리즘 : 그래프 표현을 만들고 그것을 분할해 나감
- GMM 알고리즘 : 가우시언 분포를 추정하고 그것에서 군집을 찾음
가우시안 알고리즘 -> EM알고리즘

10.6 신경망
군집화를 풀기위해 개발된 신경망 : SOM, ART
SOM(Self organizin map) 자기조직화 맵 : kohonen 네트워크
- SOM은 기본적으로 경쟁 학습(competitive learning) 사용
하나의 샘플이 입력되면 여러 개의 대표 벡터가 경쟁하는데 샘플에 가장 가까운 대표 벡터가 승자가 되어 그 샘플을 취한다.

10.7 통계적 탐색(stochastic searching)
통계적 탐색은 알고리즘 수행 중에 난수를 많이 사용한다. 이 난수가 의사 결정에 참여함으로써 해에 임의성을 부여한다. 따라서 알고리즘을 수행할 때마다 다른 해를 얻게 된다. 이러한 통계적 의사 결정에서 중요한 점은 임의성을 적절히 제어하는 것이다. 통계적 탐색을 사용하는 모든 알고리즘은 이러한 제어 기능을 가지고 있다.
10.7.1 시뮬레이티드 어닐링(Simulated annealing)
기본적으로 내리막 경사법의 구조를 따르는데 지역 최적 점을 벗어나기 위해 현재 해보다 열등한 지점으로 이동(랜덤 발생)하는 연산도 가지고 있다.
10.7.2 유전 알고리즘
해 표현, 선택, 교차, 변이, 대치를 고려해야 함
- 교차 연산 : 두 부모 해를 가지고 자식 해를 만드는데 자식은 부모와 달라지지만 특성을 이어받아야한다.
다른 알고리즘과 협력이 쉽다.-> 혼성 유전 알고리즘
유전 알고리즘이 가진 해를 k-means를 이용하여 지역 최적점으로 수렴 시킨 후 이들에 교차와 변이 연산을 가하는 것.