[ML] K-means clustering algorithms(k-평균 알고리즘)

 오라클은 K-means clustering algorithms 다음과 같이 소개하고 있다.

 

: K-means clustering은 unsupervised learning(자율 학습)의 하나로, 레이블 되지 않은 데이터를 갖고 있을 때 사용한다(예를 들어, 카테고리나 그룹이 정의되지 않은 데이터). 이 알고리즘의 목적은 데이터를 K개의 그룹으로 나누는 것이다. 이 알고리즘은 각 데이터를 데이터의 특징(features)에 따라 반복적으로 K개의 그룹 중 하나에 할당하는 것이다. 데이터는 특징의 유사성에 따라 무리지어진다(clustered). K-means clustering algorithm의 결과물은 아래와 같다:

 

1. 새로운 데이터를 레이블 할 수 있는 각 K개의 clusters의 중심들(centroids)

2. 학습 데이터를 레이블 (각 데이터는 하나의 cluster에 할당된다)

 

 clustering은 데이터를 살펴보기 전에 그룹을 정의하기보다 당신이 유기적으로 형성된 그룹들을 확인하고 분석할 수 있도록 해준다. 아래 "Choosing K" 단락에선 어떻게 그룹의 개수가 정해지는지 기술하고 있다.

 

 cluster의 각 중심(centroid)은 축척된 특징들의 값으로 이는 결과로 나타나는 그룹을 정의한다. centroid를 파악하는 것은 각 cluster가 어떤 종류의 그룹을 나타내는지를 유의미하게 해석할 수 있도록 한다.

 

: K-means clustering is a type of unsupervised learning, which is used when you have unlabeled data (i.e., data without defined categories or groups). The goal of this algorithm is to find groups in the data, with the number of groups represented by the variable K. The algorithm works iteratively to assign each data point to one of K groups based on the features that are provided. Data points are clustered based on feature similarity. The results of the K-means clustering algorithm are:

1. The centroids of the K clusters, which can be used to label new data
2. Labels for the training data (each data point is assigned to a single cluster)

 

 Rather than defining groups before looking at the data, clustering allows you to find and analyze the groups that have formed organically. The "Choosing K" section below describes how the number of groups can be determined.  

 Each centroid of a cluster is a collection of feature values which define the resulting groups. Examining the centroid feature weights can be used to qualitatively interpret what kind of group each cluster represents.  

 

* K 결정하기

: 위 알고리즘에 대한 설명에서 cluster와 데이터 집합이 미리 결정된 특정한 K개로 레이블 된다는 것을 확인할 수 있다. 데이터에서 cluster의 개수를 구하기 위해, 사용자는 다양한 K 값에 대해 K-means clustering algorithms을 실행하고 그 결과를 비교해야한다. 일반적으로 정확한 K값을 구할 수 있는 방법은 없지만, 아래 기법들을 통해 정확한 추정값을 얻을 수 있다.

 

 서로 다른 K 값을 비교할 때 흔히 사용되는 방법 중 하나는 데이터와 해당 데이터의 cluster centroid 사이의 거리의 평균값이다. cluster 개수의 증가는 cluster centroid로부터 데이터까지의 거리를 항상 줄이기 때문에, K의 증가는 이 거리의 감소로 이어진다, 이를 극단적으로 0까지 줄이는 것은 K를 데이터의 개수와 같도록 만들면 된다. 이러한 이유로, 이 방법은 하나의 타겟에는 적용이 불가하다. 대신 centroid까지의 평균 거리를 K의 함수로 표시하고, 감소율이 급격하게 증가하는 "elbow point(엘보우 포인트)"를 사용하여 대략적인 K를 결정할 수 있다.

 

 K를 검증하는 많은 기법이 존재하고 여기에는 cross-validation, information criteria, the information theoretic jump method, the silhouette method, G-means algorithm이 있다. 또한, 그룹 간 데이터의 분포를 모니터링하면 알고리즘이 각 K에 대해 데이터를 분할하는 방식에 대해 이해(insight)할 수 있다.

 

* Choosing K

 The algorithm described above finds the clusters and data set labels for a particular pre-chosen K. To find the number of clusters in the data, the user needs to run the K-means clustering algorithm for a range of K values and compare the results. In general, there is no method for determining exact value of K, but an accurate estimate can be obtained using the following techniques.

 One of the metrics that is commonly used to compare results across different values of K is the mean distance between data points and their cluster centroid. Since increasing the number of clusters will always reduce the distance to data points, increasing K will always decrease this metric, to the extreme of reaching zero when K is the same as the number of data points. Thus, this metric cannot be used as the sole target. Instead, mean distance to the centroid as a function of K is plotted and the "elbow point," where the rate of decrease sharply shifts, can be used to roughly determine K.

 A number of other techniques exist for validating K, including cross-validation, information criteria, the information theoretic jump method, the silhouette method, and the G-means algorithm. In addition, monitoring the distribution of data points across groups provides insight into how the algorithm is splitting the data for each K.

 

 scikit learn의 설명보다 오라클의 설명이 이해하기 쉽고 실제로 초보자(Novice)를 대상으로 한 글이라 소개를 했지만, scikit learn은 기본이 되는 수식도 포함하고 있어 읽어보면 K-means clustering algorithms을 이해하는데 도움이 될 것이다. 하단에 링크를 참고하면 접근이 가능하다.

 

참고

- https://blogs.oracle.com/ai-and-datascience/post/introduction-to-k-means-clustering

- https://scikit-learn.org/stable/modules/clustering.html#k-means