k-means Clustering 클러스터링

[Clustering] 라벨이 없는 데이터를 clustering/grouping 하는 클러스터링 방법론 중 K-means Clustering을 정리합니다.

Clustering Algorithm

Clustering : Grouping similar unlabeled examples

Types of clustering algorithms

클러스터링 방법론은 크게 4가지 : Centroid-based, Density-based, Density-based, Hierarchical_가 있다. 데이터가 어떠한 특성을 지닐 때 해당 방법론을 사용하는 지 각각의 특징을 정리해보자. \_Each approach is best suited to a particular data distribution.

Centroid-based Clustering	Density-based Clustering	Distribution-based Clustering	Hierarchical Clustering

• Centroid-based Clustering 중심기반 클러스터링

  • 비 계층적 클러스터링 (↔hierarchical clustering)

  • sensitive to initial conditions and outliers 초기의 그룹핑 조건과 이상치에 민감하다.

  • k-means clustering : 간단하고 효율적인 방법론이기 때문에 가장 많이 쓰이는 중심기반 클러스터링 방법론이다.

• Density-based Clustering 밀도기반 클러스터링

  • 임의의 형태의 분포를 허용해 데이터의 밀도가 높은 (조밀한) 영역을 클러스터로 연결한다.

  • 이상치에는 클러스터를 할당하지 않는다.

  • clusters are not separable linearly 클러스터가 선형으로 분리되지 않는다.

  • 다양한 밀도, 높은 차원의 데이터인 경우, 밀도기반 알고리즘을 사용하기 어렵다.

• Distribution-based Clustering

  • 데이터가 Gaussian distributions 정규분포와 같은 분포로 구성되었다고 가정하고 접근하는 방법으로, 데이터 분포 유형을 모르는 경우 다른 클러스터 알고리즘을 사용해야한다.
  • 한 점이 분포의 중심에서 멀어질수록 해당 분포에 속할 확률은 감소한다.

• Hierarchical Clustering 계층적 클러스터링

  • _taxonomies_와 같은 계층적 데이터에 적합한 방법
  • a tree of clusters 클러스터 트리를 생성하고, Any number of clusters 적절한 수준에서 트리를 절단해 원하는 수 만큼의 클러스터를 선택한다.
    • Pan-genome clustering tree 대장균 게놈 클러스터링 트리
      

K-means Clustering

k-means Clustering step 1	k-means Clustering step 2	k-means Clustering step 3	k-means Clustering step 4

1. Step 1 : Initialization - 알고리즘은 랜덤으로 각 클러스터의 centroid 중심점을 선택한다.
2. Step 2 : Initial clusters - 알고리즘은 각 점들에서 가장 가까운 중심점에 할당해 $k$개의 초기 클러스터를 얻는다.
3. Step 3 : Recomputation of centroids - 알고리즘은 클러스터마다 모든 점들의 평균을 산출해 중심점을 다시 계산한다. 변경된 중심점으로 각 점들의 클러스터를 재할당한다.
4. Step 4 : Clusters after reassignment - 알고리즘은 점들이 클러스터 변경을 중지할 때까지, calculation of centroids and assignment of points 중심점 계산 ⇒ 클러스터에 할당을 반복한다. large 데이터를 클러스터링하는 경우라면, 다른 기준을 사용해 수렴하기전에 중지한다.

---

Source&Reference : Clustering in Machine Learning | A Comprehensive Survey of Clustering Algorithms |Xu, D. & Tian, Y. Ann. Data. Sci. (2015) | Comparison of 61 Sequenced Escherichia coli Genomes by Oksana Lukjancenko, Trudy Wassenaar & Dave Ussery | Colab - Clustering with a Manual Similarity Measure Colab - Clustering Using Supervised Similarity