10장. 군집화

개요

• 유사한 샘플들끼리 분류하는 것
• Stirling 수 : S(n, 2) = 2^{n-1} - 1
• 지도 학습 (supervised learning) : 샘플의 부류 정보(정답)가 주어짐
• 비지도 학습 (unsupervised learning) : 샘플의 부류 정보가 없음

10.2 거리와 유사도

• 거리(distance) 또는 유사도(similarity)는 군집 내외의 샘플들 간의 거리를 계산하기 위해 필요하다.
• 양적 특징 (거리 개념 있음)
  • 수량 값
• 질적 특징 (거리 개념 없음)
  • 순서 값 : 학점(A, B, ..., F)
  • 명칭 값 : 혈액형
• 처리와 유사도 측정 방법
  • Minkowski 거리 -> 유클리디언 거리, 맨하탄 거리
  • 마할노비스 거리: 특징이 속한 분포를 고려
  • 코사인 유사도: 단어 출현 빈도를 활용
• 점 or 군집 과 군집 사이의 거리
  • min, max, avg, mean, rep 활용
  • 점을 군집으로 계산할 때는 군집 내의 모든 점과 다른 군집 내의 모든 점간의 거리를 계산

10.3 군집화 알고리즘의 분류

• 계층, 분할, 신경망, 통계적 탐색

10.4 계층 군집화

• 응집 계층 알고리즘 : 덴드로그램으로 표현될 수 있으며 거리 계산에 따라 중간 군집화 결과에서 차이가 발생할 수 있다.
• 분열 계층 알고리즘 : greedy 방식이 있지만 연산 시간을 단축하더라도 응집 방법보다 큰 성능상 이득이 없다.

10.5 분할 군집화

• 순차 알고리즘 : 임계값을 기준으로 가장 가까운 군집을 찾아낸다.
• k-means 알고리즘 : 속도가 빠르며 성능도 괜찮아서 가장 널리 쓰임
  • squared error 를 사용하는 gradient descent 방법의 일종
  • 따라서, 초기값에 민간하며 local minimum 에 빠질 수 있음
  • 다중 시작 알고리즘으로 위 단점을 어느정도 해소가 가능함
  • 다중 시작 알고리즘은 서로 다른 초기 군집 중심을 갖는 여러 개의 k-means를 수행하고 그 중 성능이 가장 좋은 것을 취한다.

10.6 신경망

• SOM(Self Organizing Map)
  • 유연성이 좋다 ; 새로운 샘플에 weight가 잘 학습된다.
  • 안정성이 떨어진다 ; 샘플이 특정 군집에 한번 배정되면 이후 세대에서도 그 군집에 계속 머무를 가능성이 크다.
• ART(Adaptive Resonance Theory)
  • 안정성과 유연성을 조화롭게 추구하려는 목적에서 고안됨
  • 상향 가중치 벡터와 하향 가중치 벡터를 도입; weight를 반영할 때 바로 반영하지 않고 검증 과정을 통해 반영할지 말지 결정한다.