데이터 과학자가 알아야 할 6가지 클러스터링 알고리즘

현재 Google 뉴스와 같은 많은 애플리케이션은 클러스터링 알고리즘을 주요 구현 방법으로 사용하며 레이블이 지정되지 않은 대량의 데이터를 사용하여 강력한 주제 클러스터링을 구축할 수 있습니다. 이 기사에서는 가장 기본적인 K-평균 클러스터링부터 강력한 밀도 기반 방법까지 6가지 유형의 주류 방법을 소개합니다. 각 방법에는 고유한 전문 분야와 시나리오가 있으며 기본 아이디어가 반드시 클러스터링 방법에 국한되는 것은 아닙니다.

이 기사에서는 간단하고 효율적인 K-평균 군집화부터 시작하여 평균 이동 군집화, 밀도 기반 군집화, 가우스 혼합 및 최대 기대 방법을 사용한 군집화, 계층적 군집화 및 구조화된 데이터에 적합한 방법을 소개합니다. 발각. 기본적인 구현 개념을 분석할 뿐만 아니라 각 알고리즘의 장단점을 제시하여 실제 적용 시나리오를 명확히 할 것입니다.

클러스터링은 데이터 포인트를 그룹화하는 기계 학습 기술입니다. 일련의 데이터 포인트가 주어지면 클러스터링 알고리즘을 사용하여 각 데이터 포인트를 특정 그룹으로 분류할 수 있습니다. 이론적으로 동일한 그룹에 속한 데이터 포인트는 비슷한 속성 및/또는 특성을 가져야 하지만, 다른 그룹에 속한 데이터 포인트는 매우 다른 속성 및/또는 특성을 가져야 합니다. 클러스터링(Clustering)은 비지도 학습(Unsupervised Learning) 방법이자 많은 분야에서 공통적으로 사용되는 통계 데이터 분석 기법이다.

K-평균(K-Means) 클러스터링

K-평균은 아마도 가장 잘 알려진 클러스터링 알고리즘일 것입니다. 이는 많은 입문 데이터 과학 및 기계 학습 과정의 일부입니다. 코드로 이해하고 구현하기가 매우 쉽습니다! 아래 그림을 참조하십시오.

K-Means Clustering

먼저 일부 클래스/그룹을 선택하고 해당 중심점을 무작위로 초기화합니다. 사용할 클래스 수를 계산하려면 데이터를 빠르게 살펴보고 다양한 그룹을 식별해 보는 것이 좋습니다. 중심점은 각 데이터 포인트 벡터와 길이가 같은 위치로, 위 이미지에서 "X"로 표시됩니다.

데이터 포인트와 각 그룹의 중심 사이의 거리를 계산하여 각 포인트를 분류한 다음, 그룹 중심이 가장 가까운 그룹 내 포인트를 분류합니다.

이러한 분류 포인트를 기반으로 그룹 내 모든 벡터의 평균을 사용하여 그룹 중심을 다시 계산합니다.

특정 반복 횟수 동안 또는 각 반복 후 그룹 중심이 거의 변경되지 않을 때까지 이 단계를 반복합니다. 그룹 센터를 무작위로 몇 번 초기화한 다음 최상의 결과를 제공하는 것으로 보이는 실행을 선택할 수도 있습니다.

K-평균은 빠르다는 장점이 있습니다. 우리가 실제로 하는 일은 점과 그룹 중심 사이의 거리를 계산하는 것뿐이므로 계산이 거의 없습니다! 따라서 선형 복잡도는 O(n)입니다.

반면에 K-Means에는 몇 가지 단점이 있습니다. 먼저, 그룹/클래스 수를 선택해야 합니다. 이는 항상 신중하게 수행되는 것은 아니며 이상적으로는 클러스터링 알고리즘이 분류할 클래스 수 문제를 해결하는 데 도움이 되기를 원합니다. 그 목적은 데이터에서 통찰력을 얻는 것이기 때문입니다. K-평균은 무작위로 선택된 클러스터 중심에서 시작하므로 다른 알고리즘에서 다른 클러스터링 결과를 생성할 수 있습니다. 따라서 결과가 재현되지 않고 일관성이 부족할 수 있습니다. 다른 클러스터링 방법이 더 일관됩니다.

K-Medians는 평균을 사용하는 대신 그룹의 중앙값 벡터를 사용하여 그룹 중심을 다시 계산한다는 점을 제외하면 K-Means와 관련된 또 다른 클러스터링 알고리즘입니다. 이 방법은 중앙값이 사용되기 때문에 이상값에 민감하지 않지만, 중앙값 벡터를 계산할 때 각 반복마다 정렬이 필요하므로 대규모 데이터 세트의 경우 속도가 훨씬 느립니다.

평균 이동 클러스터링

평균 이동 클러스터링은 데이터 포인트의 밀집된 영역을 찾으려는 슬라이딩 윈도우 기반 알고리즘입니다. 이는 중심 기반 알고리즘으로, 각 그룹/클래스의 중심점을 찾는 것이 목표이며 중심점의 후보 지점을 슬라이딩 창 내 지점의 평균으로 업데이트하여 수행됩니다. 그런 다음 이러한 후보 창은 사후 처리 단계에서 필터링되어 거의 중복된 부분을 제거하고 최종 중심점 집합과 해당 그룹을 형성합니다. 아래 범례를 참조하세요.

단일 슬라이딩 윈도우에 대한 평균 이동 클러스터링

1. 평균 이동을 설명하기 위해 위 그림에 표시된 대로 2차원 공간의 점 집합을 고려해 보겠습니다. 점 C(무작위로 선택됨)를 중심으로 하고 반경 r의 코어를 갖는 원형 슬라이딩 윈도우로 시작합니다. 평균 이동은 수렴할 때까지 각 단계에서 더 높은 밀도 영역을 향해 반복적으로 이동하는 언덕 오르기 알고리즘입니다.
2. 각 반복에서 슬라이딩 창은 중심점을 창 내(따라서 이름) 점의 평균쪽으로 이동하여 더 높은 밀도 영역을 향해 이동합니다. 슬라이딩 윈도우 내의 밀도는 내부 포인트 수에 비례합니다. 당연히 창 내 점의 평균을 향해 이동하여 점차 점 밀도가 높은 영역으로 이동합니다.
3. 커널에 더 많은 포인트를 수용할 수 있는 방향이 없을 때까지 평균에 따라 슬라이딩 창을 계속 이동합니다. 위 그림을 보세요. 밀도가 더 이상 증가하지 않을 때까지(즉, 창의 점 수) 원을 계속 움직입니다.
4. 모든 지점이 하나의 창 안에 위치할 때까지 여러 개의 슬라이딩 창을 통해 1~3단계의 과정이 완료됩니다. 여러 개의 슬라이딩 창이 겹치는 경우 가장 많은 포인트를 포함하는 창이 유지됩니다. 그런 다음 데이터 포인트가 위치한 슬라이딩 윈도우를 기반으로 클러스터링이 수행됩니다.

모든 슬라이딩 윈도우의 전체 과정은 처음부터 끝까지 아래에 나와 있습니다. 각 검은색 점은 슬라이딩 윈도우의 중심을 나타내고, 각 회색 점은 데이터 포인트를 나타냅니다.

평균 이동 클러스터링의 전체 과정

K-평균 클러스터링과 비교하여 이 방법은 평균 이동이 자동으로 이를 발견하므로 클러스터 수를 선택할 필요가 없습니다. 이것은 큰 장점입니다. 클러스터 중심이 최대 포인트 밀도를 향해 클러스터링된다는 사실도 매우 만족스럽습니다. 자연스러운 데이터 기반 의미를 이해하고 적응하는 것이 매우 직관적이기 때문입니다. 단점은 창 크기/반경 "r" 선택이 중요하지 않을 수 있다는 것입니다.

밀도 기반 클러스터링 방법(DBSCAN)

DBSCAN은 평균 이동과 유사하지만 몇 가지 중요한 장점이 있는 밀도 기반 클러스터링 알고리즘입니다. 아래에서 또 다른 재미있는 그래픽을 확인하고 시작해 보세요!

DBSCAN 클러스터링

1. DBSCAN은 아직 방문하지 않은 임의의 시작 데이터 지점에서 시작됩니다. 이 점의 이웃은 거리 ε으로 추출됩니다(ε 거리 내의 모든 점은 이웃 점입니다).
2. 이 동네 내에 minPoints에 따라 충분한 수의 포인트가 있는 경우 클러스터링 프로세스가 시작되고 현재 데이터 포인트가 새 클러스터의 첫 번째 포인트가 됩니다. 그렇지 않으면 해당 점이 노이즈로 표시됩니다(나중에 이 노이즈 점이 여전히 클러스터의 일부가 될 수 있음). 두 경우 모두 해당 지점은 "방문"으로 표시됩니다.
3. 새 클러스터의 첫 번째 포인트의 경우 ε 거리 이웃 내의 포인트도 클러스터의 일부가 됩니다. ε 이웃의 모든 포인트를 동일한 클러스터에 속하게 만드는 이 프로세스는 클러스터에 방금 추가된 모든 새 포인트에 대해 반복됩니다.
4. 군집의 모든 점이 결정될 때까지, 즉 군집의 ε 인근에 있는 모든 점을 방문하고 표시할 때까지 2단계와 3단계를 반복합니다.
5. 현재 클러스터 작업이 완료되면 방문하지 않은 새로운 지점이 검색 및 처리되어 다른 클러스터나 노이즈가 발견됩니다. 이 과정은 모든 지점이 방문한 것으로 표시될 때까지 반복됩니다. 모든 지점을 방문했으므로 각 지점은 일부 클러스터 또는 노이즈에 속합니다.

DBSCAN은 다른 클러스터링 알고리즘에 비해 많은 장점을 가지고 있습니다. 첫째, 고정된 수의 클러스터가 전혀 필요하지 않습니다. 또한 데이터 포인트가 매우 다르더라도 단순히 클러스터로 그룹화하는 평균 이동과 달리 이상치를 노이즈로 식별합니다. 또한 모든 크기와 모양의 클러스터를 매우 잘 찾을 수 있습니다.

DBSCAN의 가장 큰 단점은 클러스터의 밀도가 다를 때 다른 클러스터링 알고리즘만큼 성능을 ​​발휘하지 못한다는 것입니다. 이는 밀도가 변경되면 인접 지점을 식별하는 데 사용되는 거리 임계값 ε 및 minPoints의 설정이 클러스터에 따라 변경되기 때문입니다. 이 단점은 거리 임계값 ε을 다시 추정하기 어려워지기 때문에 매우 고차원 데이터에서도 발생합니다.

가우시안 혼합 모델(GMM)을 사용한 기대 최대값(EM) 클러스터링

K-평균의 주요 단점은 클러스터 중심 수단을 간단하게 사용한다는 것입니다. 아래 다이어그램에서 이것이 최선의 접근 방식이 아닌 이유를 확인할 수 있습니다. 왼쪽에는 동일한 평균을 중심으로 반지름이 다른 두 개의 원형 클러스터가 있음을 매우 명확하게 볼 수 있습니다. K-Means는 이러한 클러스터의 평균이 매우 가깝기 때문에 이 상황을 처리할 수 없습니다. K-평균은 평균을 군집 중심으로 사용하기 때문에 군집이 원형이 아닌 경우에도 실패합니다.

K-평균의 두 가지 실패 사례

가우스 혼합 모델(GMM)은 K-평균보다 더 많은 유연성을 제공합니다. GMM의 경우 데이터 포인트가 가우스 분포라고 가정합니다. 이는 평균을 사용하여 원형이라고 가정하는 것보다 덜 제한적인 가정입니다. 이런 식으로 클러스터의 모양을 설명하는 두 가지 매개변수인 평균과 표준편차를 갖게 됩니다! 2D를 예로 들면, 이는 클러스터가 모든 종류의 타원형 모양을 취할 수 있음을 의미합니다(x 및 y 방향 모두에서 표준 편차가 있으므로). 따라서 각 가우스 분포는 단일 클러스터에 할당됩니다.

각 클러스터의 가우스 매개변수(예: 평균 및 표준편차)를 찾기 위해 EM(Expectation Maximum)이라는 최적화 알고리즘을 사용합니다. 클러스터에 대한 가우스 적합의 예인 아래 다이어그램을 살펴보십시오. 그런 다음 GMM을 사용하여 최대 기대 클러스터링 프로세스를 계속할 수 있습니다.

GMM을 사용한 EM 클러스터링

1. 먼저 클러스터 수를 선택하고(K-Means에서와 같이) 각 클러스터에 대한 가우스 분포 매개변수를 무작위로 초기화합니다. 또한 데이터를 빠르게 살펴봄으로써 초기 매개변수에 대한 적절한 추측을 제공할 수도 있습니다. 그러나 위에서 볼 수 있듯이 Gaussian은 매우 열악하게 시작하지만 빠르게 최적화되기 때문에 이것이 100% 필요한 것은 아닙니다.
2. 각 클러스터의 가우스 분포를 고려하여 각 데이터 포인트가 특정 클러스터에 속할 확률을 계산합니다. 점이 가우스 중심에 가까울수록 해당 클러스터에 속할 가능성이 높아집니다. 가우스 분포를 사용하면 대부분의 데이터가 클러스터 중심에 더 가깝다고 가정하므로 이는 직관적이어야 합니다.
3. 이러한 확률을 기반으로 클러스터 내 데이터 포인트의 확률을 최대화하는 새로운 가우스 분포 매개변수 세트를 계산합니다. 우리는 데이터 포인트 위치의 가중치 합을 사용하여 이러한 새로운 매개변수를 계산합니다. 여기서 가중치는 데이터 포인트가 특정 클러스터에 속할 확률입니다. 시각적으로 설명하기 위해 위의 이미지, 특히 예로 사용하는 노란색 클러스터를 볼 수 있습니다. 분포는 첫 번째 반복에서 바로 시작되지만 대부분의 노란색 점은 분포의 오른쪽에 있음을 알 수 있습니다. 확률가중합을 계산해 보면 중앙 근처에 몇몇 점이 있더라도 대부분 오른쪽에 위치합니다. 따라서 분포의 평균은 자연스럽게 이 점에 가까워집니다. 또한 대부분의 포인트가 "오른쪽 위에서 왼쪽 아래로" 분포되어 있음을 알 수 있습니다. 따라서 표준 편차는 확률의 가중 합을 최대화하기 위해 점에 더 잘 맞는 타원을 생성하도록 변경됩니다.
4. 수렴이 이루어질 때까지 2단계와 3단계를 반복합니다. 여기서 반복 간 분포는 거의 변하지 않습니다.

GMM을 사용하면 두 가지 주요 이점이 있습니다. 첫째, GMM은 표준 편차 매개변수로 인해 클러스터 공분산 측면에서 K-평균보다 더 유연하며 클러스터는 원으로 제한되지 않고 타원형 모양을 취할 수 있습니다. K-평균은 실제로 각 클러스터의 공분산이 모든 차원에서 0에 가까운 GMM의 특수한 경우입니다. 둘째, GMM은 확률을 사용하기 때문에 데이터 포인트당 많은 클러스터가 있을 수 있습니다. 따라서 데이터 포인트가 두 개의 겹치는 클러스터 중간에 있는 경우 해당 데이터 포인트의 X%가 클래스 1에 속하고 Y%가 클래스 2에 속한다고 간단히 정의할 수 있습니다. 즉, GMM은 하이브리드 자격을 지원합니다.

집합 계층적 클러스터링

계층적 클러스터링 알고리즘은 실제로 하향식 또는 상향식의 두 가지 범주로 나뉩니다. 상향식 알고리즘은 먼저 각 데이터 포인트를 단일 클러스터로 처리한 다음 모든 클러스터가 모든 데이터 포인트를 포함하는 단일 클러스터로 병합될 때까지 두 클러스터를 연속적으로 병합(또는 집계)합니다. 따라서 상향식 계층적 클러스터링을 응집 계층적 클러스터링 또는 HAC라고 합니다. 이 클러스터 계층 구조는 트리(또는 덴드로그램)로 표시됩니다. 트리의 루트는 모든 샘플을 수집하는 유일한 클러스터이고, 리프는 샘플이 하나만 있는 클러스터입니다. 알고리즘 단계를 시작하기 전에 아래 범례를 참조하세요.

집적 계층적 클러스터링

1. 먼저 각 데이터 포인트를 단일 클러스터로 처리합니다. 즉, 데이터 세트에 X개의 데이터 포인트가 있으면 X개의 클러스터가 있습니다. 그런 다음 두 클러스터 사이의 거리를 측정하는 거리 측정법을 선택합니다. 예를 들어, 두 클러스터 사이의 거리를 첫 번째 클러스터의 데이터 포인트와 두 번째 클러스터의 데이터 포인트 사이의 평균 거리로 정의하는 평균 연결을 사용합니다.
2. 각 반복에서 두 개의 클러스터를 하나로 병합합니다. 병합할 두 클러스터는 평균 연결이 가장 작아야 합니다. 즉, 우리가 선택한 거리 측정법에 따르면 두 클러스터는 그들 사이의 거리가 가장 작으므로 가장 유사하므로 함께 병합해야 합니다.
3. 트리의 루트에 도달할 때까지 2단계를 반복합니다. 즉, 모든 데이터 포인트를 포함하는 클러스터가 하나만 있습니다. 이러한 방식으로 클러스터 병합을 중지할 시기, 즉 트리 구축을 중지할 시기만 선택하고 결국 필요한 클러스터 수를 선택하면 됩니다!

계층적 클러스터링에서는 클러스터 수를 지정할 필요가 없으며 트리를 구축하므로 가장 적합한 클러스터 수를 선택할 수도 있습니다. 또한 알고리즘은 거리 측정법 선택에 민감하지 않습니다. 모두 동일하게 성능을 발휘하는 반면, 다른 클러스터링 알고리즘의 경우 거리 측정법 선택이 중요합니다. 계층적 클러스터링 방법의 특히 좋은 예는 기본 데이터에 계층적 구조가 있고 계층을 복원하려는 경우입니다. 다른 클러스터링 알고리즘은 이를 수행할 수 없습니다. K-Means 및 GMM의 선형 복잡도와 달리 계층적 클러스터링의 이러한 장점은 O(n³)의 시간 복잡도를 갖기 때문에 효율성이 떨어지는 대가를 치르게 됩니다.

그래프 커뮤니티 감지

데이터를 네트워크나 그래프로 표현할 수 있는 경우 그래프 커뮤니티 감지 방법을 사용하여 클러스터링을 완료할 수 있습니다. 이 알고리즘에서 그래프 커뮤니티는 일반적으로 네트워크의 다른 부분보다 더 밀접하게 연결된 정점의 하위 집합으로 정의됩니다.

아마도 가장 직관적인 사례는 소셜 네트워크일 것입니다. 꼭지점은 사람을 나타내고, 꼭지점을 연결하는 모서리는 친구 또는 팬인 사용자를 나타냅니다. 그러나 시스템을 네트워크로 모델링하려면 다양한 구성 요소를 효율적으로 연결하는 방법을 찾아야 합니다. 클러스터링을 위한 그래프 이론의 혁신적인 응용에는 이미지 데이터의 특징 추출, 유전자 조절 네트워크 분석 등이 포함됩니다.

아래는 Wikipedia 페이지의 링크를 기반으로 연결된 최근에 본 웹사이트 8개를 보여주는 간단한 다이어그램입니다.

꼭지점의 색상은 그룹 관계를 나타내며 크기는 중심성에 따라 결정됩니다. 이러한 클러스터는 실제 생활에서도 의미가 있습니다. 여기서 노란색 정점은 일반적으로 참조/검색 사이트이고 파란색 정점은 모두 온라인 게시 사이트(기사, 트윗 또는 코드)입니다.

네트워크를 그룹으로 클러스터링했다고 가정해 보겠습니다. 그런 다음 이 모듈성 점수를 사용하여 클러스터링의 품질을 평가할 수 있습니다. 점수가 높을수록 네트워크를 "정확한" 그룹으로 분할했음을 의미하고, 점수가 낮을수록 클러스터링이 무작위에 더 가깝다는 것을 의미합니다. 아래 그림과 같이:

모듈성은 다음 공식을 사용하여 계산할 수 있습니다.

여기서 L은 네트워크의 가장자리 수를 나타내고, k_i 및 k_j는 각 꼭지점의 정도를 나타냅니다. 각 행을 추가하여 계산됩니다. 각 열의 항목을 추가하여 계산됩니다. 둘을 곱하고 2L로 나누면 네트워크가 무작위로 할당될 때 정점 i와 j 사이의 예상되는 가장자리 수를 나타냅니다.

전체적으로 괄호 안의 용어는 네트워크의 실제 구조와 무작위로 결합했을 때 예상되는 구조 간의 차이를 나타냅니다. 그 값을 연구해 보면 A_ij = 1이고 ( k_i k_j ) / 2L이 작을 때 가장 높은 값을 반환한다는 것을 알 수 있습니다. 이는 고정점 i와 j 사이에 "예기치 않은" 가장자리가 있는 경우 결과 값이 더 높다는 것을 의미합니다.

마지막 δc_i, c_j는 유명한 크로네커 δ 함수(Kronecker-delta function)입니다. Python 설명은 다음과 같습니다.

그래프의 모듈성은 위 공식을 통해 계산할 수 있으며, 모듈성이 높을수록 네트워크가 여러 그룹으로 클러스터링되는 정도가 좋습니다. 따라서 네트워크를 클러스터링하는 가장 좋은 방법은 최적화 방법을 통해 최대의 모듈성을 찾는 것에서 찾을 수 있습니다.

Combinatorics는 꼭지점이 8개뿐인 네트워크의 경우 4,140가지의 서로 다른 클러스터링 방법이 있음을 알려줍니다. 16개의 정점으로 구성된 네트워크는 100억 개가 넘는 방식으로 클러스터링됩니다. 32개의 정점이 있는 네트워크의 가능한 클러스터링 방법은 128셉틸리언(10^21)을 초과합니다. 네트워크에 80개의 정점이 있으면 가능한 클러스터링 방법의 수가 관측 가능한 우주의 클러스터링 방법 수를 초과합니다.

따라서 우리는 모든 가능성을 시도하지 않고 가장 높은 모듈성 점수를 산출하는 클러스터를 평가하는 데 효과적인 휴리스틱에 의지해야 합니다. 이는 Fast-Greedy Modularity-Maximization이라는 알고리즘으로 위에서 설명한 응집형 계층적 클러스터링 알고리즘과 다소 유사합니다. Mod-Max는 거리에 따라 그룹을 융합하는 것이 아니라 모듈성 변화에 따라 그룹을 융합합니다.

작동 방법은 다음과 같습니다.

• 먼저 각 정점을 자체 그룹에 할당한 다음 전체 네트워크의 모듈성 M을 계산합니다.
• 1단계에서는 각 커뮤니티 쌍이 하나 이상의 일방적 링크로 연결되어야 합니다. 두 커뮤니티가 함께 병합되면 알고리즘은 결과적인 모듈성 변경 ΔM을 계산합니다.
• 2단계는 ΔM이 가장 많이 성장한 그룹 쌍을 선택한 후 융합하는 것입니다. 그런 다음 이 클러스터에 대해 새로운 모듈성 M이 계산되어 기록됩니다.
• 1단계와 2단계를 반복합니다. 매번 그룹 쌍을 융합하여 ΔM의 최대 이득을 얻은 다음 새 클러스터링 패턴과 해당 모듈성 점수 M을 기록합니다.
• 모든 정점이 거대한 클러스터로 그룹화되면 중지해도 됩니다. 그런 다음 알고리즘은 이 과정에서 레코드를 검사하고 가장 높은 M 값이 반환된 클러스터링 패턴을 찾습니다. 이는 반환된 그룹 구조입니다.

커뮤니티 감지는 그래프 이론에서 인기 있는 연구 분야로, 일부 작은 클러스터를 무시하고 구조화된 그래프 모델에만 적용할 수 있다는 점에서 그 한계가 주로 반영됩니다. 그러나 이러한 유형의 알고리즘은 일반적인 구조화된 데이터와 실제 네트워크 데이터에서 매우 좋은 성능을 나타냅니다.

결론

위는 데이터 과학자가 알아야 할 6가지 주요 클러스터링 알고리즘입니다! 다양한 알고리즘의 시각화를 보여드리며 이번 글을 마무리하겠습니다!

위 내용은 데이터 과학자가 알아야 할 6가지 클러스터링 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!