Intro to machine learning - (8) Clustering

Clustering은 Unsupervised Learning, 비지도학습 중 하나입니다. 정답이나 Label이 따로 존재하지 않고, 데이터에서 구조나 패턴을 발굴하는 것이 목표입니다.

 

첫번째 Plot은 데이터를 크게 3개의 그룹으로 묶어볼 수 있습니다. 나중에 새로운 데이터가 들어왔을 때, 그 데이터의 주변에 있는 데이터에 따라 어떤 그룹에 속할지를 정할 수 있습니다. 이러한 Task는 Clustering이라고 합니다.

 

두번째 Plot은 데이터가 두개의 차원으로 그려져있습니다. 고차원의 데이터가 연관성이 높은 경우, 저차원으로 변환하면서 연관성을 낮추는 처리를 할 수 있습니다. 이러한 Task는 Dimensionality Reduction, 차원축소라고 합니다.

 

Clustering에 대해서 먼저 살펴보면, Sebastian과 Katie 두 사람이 영화에 대해 평점을 준 데이터입니다. Sebastian이 높은 평점을 준 영화에 Katie는 낮은 평점을, 반대로 Sebastian이 낮은 평점을 준 영화에 Katie는 높은 평점을 준 것을 볼 수 있습니다. 영화에 대한 정보가 없더라도, Sebastian과 Katie 두 사람이 각각 좋아하는 영화의 스타일이 다른것을 볼 수 있죠. 데이터가 크게 두개의 Class로 나뉘는 것입니다. 실제로 Sebastian은 Old style westerns를, Katie는 Modern chick flicks 장르의 영화를 좋아한다고 합니다. 

 

Clustering의 대표적인 알고리즘으로 K-Means가 있습니다. K-Means는 Cluter의 중심인 Centroid를 정하는 Assign과 Centroid - Data Point 거리의 제곱합을 최소화하는 방향으로 Centroid를 움직이는 Optimize과정을 갖습니다. 

 

Sklearn에서 K-Means를 돌릴 때의 주요 파라미터에 대해서 소개하면,

n_clusters : Cluster의 개수입니다.

max_iter : 앞서 얘기했던 Assign - Optimize의 과정을 반복하는 횟수를 의미합니다. default는 300인데, 보통은 이전에 최적의 결과로 수렴합니다.

n_init : Initial Centroid에 따라 결과가 달라지기 때문에 초기값을 변경해가면서 알고리즘을 돌리는 횟수입니다.

 

이런 K-Means는 완벽한 알고리즘은 아닙니다. 단점도 물론 존재합니다.

강의에서는 initial cluster에 따라 다른 결과가 나타나는 것을 단점으로 이야기합니다. 기본적으로는 Inital Centroid를 무작위로 결정하기 때문에 최적의 결과를 내는데는 한계가 있는 것입니다.

 

빨간색으로 표시된 데이터들을 보면, 3개의 파란색 Centroid를 중심으로 구성된 Cluster들을 생각할 수 있습니다. 하지만 Initial Cluster에 따라 3개의 연두색 Centroid를 중심으로 하는 Cluster가 구성될수도 있는 것입니다. 에러를 계속해서 줄여나가는 방향이 Global Optimum이 아니라 Local Optimum에 도달하며 종료되는 것입니다.

 

경험적으로는, Cluster의 개수가 많아지면 Local Minima에 빠질 확률이 높다고 합니다. 때문에 n_init 파라미터를 활용해서 초기값을 여러번 변경해가면서 알고리즘이 작동하도록 해야한다고 이야기합니다.

 

위의 예시를 보면, 동일한 데이터에서 밑에 있는 Centroid의 위치만 살짝 오른쪽으로 변경해주었음에도 완전히 다른 결과가 나오는 경우를 보여줍니다.

 

강의에서 K-Means의 Assign-Optimize를 직관적으로 볼 수 있는 사이트를 소개하고 있습니다.

Visualizing K-Means Clustering

원하는 Initial Centroid, Data 형태를 고르면, K-Means가 돌아가는 과정을 직접 볼 수 있습니다. 함께 있는 설명을 보면,

 

Initialization Strategies

K-Means의 Initial Centroid 설정.

Data Point들 중에서 임의로 선택하는 방식이 있습니다. 특별하게 좋은 성능을 보이지는 않지만, 많은 Initial Centroid들이 동일한 실제 클러스터로 마무리 될 가능성이 매우 높아보입니다. 운이 좋게 정확한 K를 설정했다고 가정하면, 각 Cluster들은 동일한 크기의 데이터를 갖습니다. 그러면 K개의 Centroid가 고유한 Cluster로 초기화 될 확률은 K!/K^K입니다. 스털링 근사에 따르면, 이는 e^-k  sqrt(2*pi*k)인데, 빠르게 0으로 갑니다.

 

더 나은 아이디어는, 'Farthest' 선택지인데, 이는 Initial Centroid를 임의로 고르고, 두번째 Centroid를 그로부터 가장 멀리 있는 데이터로 초기화합니다. 보통 우리는 j번째 Centroid를 이전의 Centroid와의 최소 거리를 극대화하는 Point로 초기화합니다. 이러한 과정은 각각의 Centroid가 서로 멀리 떨어지도록 합니다.

 

아마 더 나은 초기화 전략은 'K-means++'일 것입니다. 이는 'Farthest'와 비슷하게 작동하는데, j번째 Centroid가 이전 Centroid와의 거리가 가장 먼 데이터를 고르는 'Farthest'와는 다르게, 가장 가까운 이전 Centroid와의 거리 제곱에 비례하는 편중 확률분포를 사용하여 Centroid를 선택합니다. 만약 가장 먼 Point를 고르낟면, Cluster의 가장자리에 있는 Point를 고르게 되지만 만약 임의의 Point를 고르면, Cluster의 중심과 가까운 Point를 고를 가능성이 높아집니다. 

 

여전이 Cluster의 개수인 K를 설정하는 문제가 남습니다. 보통 사전에 데이터가 몇개의 Cluster로 구성될지, 2-3차원 이상의 고차원 데이터에서 데이터를 직관적으로 보기 어렵습니다. (만약 예시와 같이 데이터를 보고 Cluster를 명확하게 볼 수 있다면, 직접 Clustering을 하는 것도 좋은 방법입니다.)

 

K-Means Performance

K-Means는 대략적으로 동일한 크기와 규칙적인 모양의 Cluster를 갖는 데이터에서 가장 좋은 결과를 보입니다. 예시에서는 "Gaussian Mixture", "Packed Circles" 데이터와 Farthest Initial Centroid, 그리고 정확한 Centroid 개수에서 좋은 성능을 보입니다.

 

그러나 "Smiley"와 "Pimpled Smiley"에서는 4개의 Cluster를 찾을 수 없습니다. 얼굴 Outline이 비정규적인 모양을 갖기 때문입니다. Initial Cluster에 대한 의존성과 K의 설정조건은 까다롭습니다. 그리고 K-Means는 Data Point들이 유클리드 공간 안에 놓여있을때만 적용가능하고, 더 복잡한 형태의 데이터에서는 활용하기가 어렵습니다.

 

이러한 단점에도 불구하고, K-Means는 Clustering에서 많이 쓰이는 알고리즘입니다. 많은 현실의 데이터에서도 잘 작동하고, 상대적으로 빠르며, 활용하기도 쉽습니다. K-Means에서 발전하거나 이를 일반화한 K-Medians, K-Medioids, K-Means++, EM algorithm for Gaussian Mixture는 모두 Cluster 내의 데이터는 Centroid에 가까워야 한다는 기본개념을 반영합니다.