Flat Clustering

🔍 Clustering이란?

• 문서 집합에서 비슷한 문서끼리 그룹화 하는 것
• 거리가 가까운 것끼리 묶음
• Training set 없이 작업한다.(unsupervised learning)
• ※classification과 clustering의 차이
  • classification은 supervised learning이고, clustering은 unsupervised learning이다.
  • classification의 class는 사람이 정의한다.
  • clustering은 사람의 개입이 없다.
• 가설 : 정답과 같은 cluster에 속해있다면 그것도 정답일 가능성이 크다.
• clustering의 효과
  • 검색 결과들을 clustering : 좀 더 연관성 있는 결과들을 보여줄 수 있다.
  • 문서 집합을 clustering : 카테고리별로 문서들을 볼 수 있다.
  • 정보검색 모델에 clustering 이용
• 장점 : recall(재현율)이 높아진다. (정답과 같은 cluster에 있으면 정답이기 때문에)

✔ clustering 종류

• Flat clustering : 일반적인 clustering
• Hierarchical clustering : 계층적으로 여러번 clustering
• Hard clustering : 하나의 문서는 하나의 cluster에 속해있음
• Soft clustering : 하나의 문서가 여러개의 cluster에 속할 수 있다.

🔍 K-means 알고리즘

• k는 군집의 갯수이다.
• Flat clustering이다.
• Euclidean distance를 사용해서 문서 간의 유사도를 계산한다. (모든 문서 간 서로의 유사도를 구해야한다.)
• centroid : 한 군집의 문서들의 벡터들의 평균
• 좋은 군집의 기준
  • RSS = (각 벡터와 centroi 사이의 거리)^2 -> 모든 벡터에서 구하고 합한다.
  • 이것이 최소화된 군집이 좋은 군집이다.
• 알고리즘
  1. k개의 군집의 centroid를 임의로 선택한다.
  2. 모든 문서에 대해 가까운 centroid를 구해 해당 centroid의 cluster 번호를 매긴다.
  3. 번호가 매겨진 군집을 가지고 새로운 centroid를 구한다.
  4. 다시 2번,3번을 반복한다.
  5. centroid가 바뀌지 않거나, 문서의 소속이 바뀌지 않으면 반복문을 끝낸다.
• 단점 : 초기 centroid를 잘못 잡으면 clustering의 결과가 나쁘게 나올 수 있다.