Machine Learning/ K-평균 알고리즘

주의) 이 페이지에서는 공식의 유도 과정 같은 것은 정리하지 않는다. 공식의 유도 과정은 <코세라 강의> 참조.

K-평균 알고리즘(K-Means)

https://www.coursera.org/learn/machine-learning/

  • 정답이 주어지지 않는 비지도 학습(Unsupervised Learning)의 분류 알고리즘 중 하나. 가까운 데이터들끼리 묶어서 Cluster를 만드는 것이 핵심이다.
  • K-Means 알고리즘의 Input은 데이터셋과 클러스터의 갯수 2가지가 된다.
    • 몇 개의 클러스터를 만들 것이냐는 정하기 나름.

K-평균 알고리즘의 절차

https://www.coursera.org/learn/machine-learning/

  • K-Means 알고리즘의 절차는 간단하다.
    1. 데이터들 사이에 클러스터를 만들 갯수만큼의 중심점(centroid)을 랜덤하게 배치한 후에
      1. 각 중심점은 μ(Mu)라고 부르며 자신의 index를 아래 첨자로 표기한다. μ1, μ2, μk
    2. 전체 데이터셋에 대하여 가장 가까운 중심점의 위치를 체크하여 그 결과를 Ci로 나타낸다. (이를 Cluster Assignment라고 한다)
      • Ci에는 i번째의 데이터의 가장 가까운 중심점을 담는다.
    3. 각 중심점 별로 자신과 가장 가까운 데이터들의 평균값을 구한 후 그 위치로 이동한다.
      • Ci에서 자신에 Assignment된 데이터들을 뽑아낸 후 그 평균 값을 구하고 자신의 위치를 그 위치로 이동시킨다.
    4. 2번부터 다시 반복하여, 최적의 위치를 찾을 때까지 반복한다.

K-평균 알고리즘의 비용함수

  • K-means 알고리즘에서는 비용함수를 Distortion이라고도 하며, 계산 방식은 다음과 같다.
    • \frac{1}{m} \sum_{i=1}^m || x_i - \mu_{ci} ||^2
    • K-Means 에서 중심점과 데이터의 거리는 두 점 사이의 차이의 제곱으로만 계산한다. 어차피 상대적인 크기를 비교하는 것이기 때문에 루트는 씌우지 않는다.
  • K-means 알고리즘에서는 비용함수를 줄이는 방법은 알고리즘 절차를 돌면서 위 계산을 반복하는 것이다.

https://www.coursera.org/learn/machine-learning/

  • 중심점의 시작 위치를 잘못 잡을 경우 Local Optima에 빠질 수 있는데, 이를 해결하는 방법은 Random으로 중심점을 반복해서 잡는 것 외엔 없다.

https://www.coursera.org/learn/machine-learning/

  • 최적의 클러스터의 개수는 클러스터의 개수를 조절해 가면서 비용 함수를 계산하는 것인데, 클러스터 개수를 조절하는 그래프에서 elbow가 나타나면 좋지만 그렇지 않은 경우엔 딱히 방법이 없다.
[ssba]

The author

지성을 추구하는 디자이너/ suyeongpark@abyne.com

댓글 남기기

This site uses Akismet to reduce spam. Learn how your comment data is processed.