클러스터링 알고리즘

머신러닝 데이터 세트에는 수백만 개의 예가 포함될 수 있지만 모든 클러스터링 알고리즘이 효율적으로 확장되는 것은 아닙니다. 많은 클러스터링 알고리즘은 모든 예 쌍 간의 유사성을 계산합니다. 즉, 런타임은 복잡도 표기법으로 $O(n^2)$ 로 표시되는 예 수 $n$의 제곱으로 증가합니다. $O(n^2)$ 알고리즘은 수백만 개의 예가 있는 데이터 세트에는 실용적이지 않습니다.

k-평균 알고리즘의 복잡도는 $O(n)$입니다. 즉, 알고리즘은 $n$에 따라 선형으로 확장됩니다. 이 알고리즘이 이 과정의 핵심 주제입니다.

클러스터링 유형

클러스터링에 대한 다양한 접근 방식의 전체 목록은 A Comprehensive Survey of Clustering Algorithms(클러스터링 알고리즘에 대한 포괄적인 연구 조사) Xu, D.를 참고하세요. & 톈, Y. 앤. 데이터. Sci. (2015) 2: 165. 각 접근 방식은 특정 데이터 분포에 가장 적합합니다. 이 과정에서는 네 가지 일반적인 접근 방식을 간략히 설명합니다.

중심 기반 군집화

클러스터의 중심은 클러스터의 모든 점의 산술 평균입니다. 중심 기반 클러스터링은 데이터를 계층 구조가 아닌 클러스터로 구성합니다. 중심 기반 군집화 알고리즘은 효율적이지만 초기 조건과 외부값에 민감합니다. 이 중 k-평균이 가장 널리 사용됩니다. 이 방법을 사용하려면 사용자가 중심점 수 k를 정의해야 하며, 크기가 거의 동일한 클러스터에 적합합니다.

그림 1: 중심 기반 군집화의 예

밀도 기반 군집화

밀도 기반 클러스터링은 예시 밀도가 높은 연속 영역을 클러스터로 연결합니다. 이렇게 하면 임의의 모양의 클러스터를 원하는 수만큼 찾을 수 있습니다. 특이치는 클러스터에 할당되지 않습니다. 이러한 알고리즘은 밀도가 다른 클러스터와 차원이 높은 데이터에 어려움을 겪습니다.

그림 2: 밀도 기반 군집화의 예

분포 기반 클러스터링

이 클러스터링 접근 방식은 데이터가 가우시안 분포와 같은 확률적 분포로 구성된다고 가정합니다. 그림 3에서 분포 기반 알고리즘은 데이터를 세 개의 가우시안 분포로 클러스터링합니다. 분포의 중심에서 거리가 멀어질수록 점이 분포에 속할 확률은 감소합니다. 밴드는 이러한 감소하는 확률을 보여줍니다. 데이터의 특정 기본 분포를 가정하는 것이 불편하다면 다른 알고리즘을 사용해야 합니다.

그림 3: 분포 기반 클러스터링의 예

계층적 군집화

계층적 군집화는 클러스터 트리를 만듭니다. 당연히 계층적 군집화는 분류와 같은 계층적 데이터에 적합합니다. 예를 보려면 Oksana Lukjancenko, Trudy Wassenaar, Dave Ussery의 61개의 Escherichia coli 게놈 시퀀스 비교를 참고하세요. 적절한 수준에서 트리를 자르면서 원하는 수만큼 클러스터를 선택할 수 있습니다.

그림 4: 동물을 계층적 트리로 군집화하는 예시

핵심 용어:

• k-평균 알고리즘
• centroid
• 가우시안 분포