현재 Google 뉴스와 같은 많은 애플리케이션은 클러스터링 알고리즘을 주요 구현 방법으로 사용하며 레이블이 지정되지 않은 대량의 데이터를 사용하여 강력한 주제 클러스터링을 구축할 수 있습니다. 이 기사에서는 가장 기본적인 K-평균 클러스터링부터 강력한 밀도 기반 방법까지 6가지 유형의 주류 방법을 소개합니다. 각 방법에는 고유한 전문 분야와 시나리오가 있으며 기본 아이디어가 반드시 클러스터링 방법에 국한되는 것은 아닙니다.
이 기사에서는 간단하고 효율적인 K-평균 군집화부터 시작하여 평균 이동 군집화, 밀도 기반 군집화, 가우스 혼합 및 최대 기대 방법을 사용한 군집화, 계층적 군집화 및 구조화된 데이터에 적합한 방법을 소개합니다. 발각. 기본적인 구현 개념을 분석할 뿐만 아니라 각 알고리즘의 장단점을 제시하여 실제 적용 시나리오를 명확히 할 것입니다.
클러스터링은 데이터 포인트를 그룹화하는 기계 학습 기술입니다. 일련의 데이터 포인트가 주어지면 클러스터링 알고리즘을 사용하여 각 데이터 포인트를 특정 그룹으로 분류할 수 있습니다. 이론적으로 동일한 그룹에 속한 데이터 포인트는 비슷한 속성 및/또는 특성을 가져야 하지만, 다른 그룹에 속한 데이터 포인트는 매우 다른 속성 및/또는 특성을 가져야 합니다. 클러스터링(Clustering)은 비지도 학습(Unsupervised Learning) 방법이자 많은 분야에서 공통적으로 사용되는 통계 데이터 분석 기법이다.
K-평균은 아마도 가장 잘 알려진 클러스터링 알고리즘일 것입니다. 이는 많은 입문 데이터 과학 및 기계 학습 과정의 일부입니다. 코드로 이해하고 구현하기가 매우 쉽습니다! 아래 그림을 참조하십시오.
K-Means Clustering
먼저 일부 클래스/그룹을 선택하고 해당 중심점을 무작위로 초기화합니다. 사용할 클래스 수를 계산하려면 데이터를 빠르게 살펴보고 다양한 그룹을 식별해 보는 것이 좋습니다. 중심점은 각 데이터 포인트 벡터와 길이가 같은 위치로, 위 이미지에서 "X"로 표시됩니다.
데이터 포인트와 각 그룹의 중심 사이의 거리를 계산하여 각 포인트를 분류한 다음, 그룹 중심이 가장 가까운 그룹 내 포인트를 분류합니다.
이러한 분류 포인트를 기반으로 그룹 내 모든 벡터의 평균을 사용하여 그룹 중심을 다시 계산합니다.
특정 반복 횟수 동안 또는 각 반복 후 그룹 중심이 거의 변경되지 않을 때까지 이 단계를 반복합니다. 그룹 센터를 무작위로 몇 번 초기화한 다음 최상의 결과를 제공하는 것으로 보이는 실행을 선택할 수도 있습니다.
K-평균은 빠르다는 장점이 있습니다. 우리가 실제로 하는 일은 점과 그룹 중심 사이의 거리를 계산하는 것뿐이므로 계산이 거의 없습니다! 따라서 선형 복잡도는 O(n)입니다.
반면에 K-Means에는 몇 가지 단점이 있습니다. 먼저, 그룹/클래스 수를 선택해야 합니다. 이는 항상 신중하게 수행되는 것은 아니며 이상적으로는 클러스터링 알고리즘이 분류할 클래스 수 문제를 해결하는 데 도움이 되기를 원합니다. 그 목적은 데이터에서 통찰력을 얻는 것이기 때문입니다. K-평균은 무작위로 선택된 클러스터 중심에서 시작하므로 다른 알고리즘에서 다른 클러스터링 결과를 생성할 수 있습니다. 따라서 결과가 재현되지 않고 일관성이 부족할 수 있습니다. 다른 클러스터링 방법이 더 일관됩니다.
K-Medians는 평균을 사용하는 대신 그룹의 중앙값 벡터를 사용하여 그룹 중심을 다시 계산한다는 점을 제외하면 K-Means와 관련된 또 다른 클러스터링 알고리즘입니다. 이 방법은 중앙값이 사용되기 때문에 이상값에 민감하지 않지만, 중앙값 벡터를 계산할 때 각 반복마다 정렬이 필요하므로 대규모 데이터 세트의 경우 속도가 훨씬 느립니다.
평균 이동 클러스터링은 데이터 포인트의 밀집된 영역을 찾으려는 슬라이딩 윈도우 기반 알고리즘입니다. 이는 중심 기반 알고리즘으로, 각 그룹/클래스의 중심점을 찾는 것이 목표이며 중심점의 후보 지점을 슬라이딩 창 내 지점의 평균으로 업데이트하여 수행됩니다. 그런 다음 이러한 후보 창은 사후 처리 단계에서 필터링되어 거의 중복된 부분을 제거하고 최종 중심점 집합과 해당 그룹을 형성합니다. 아래 범례를 참조하세요.
단일 슬라이딩 윈도우에 대한 평균 이동 클러스터링
모든 슬라이딩 윈도우의 전체 과정은 처음부터 끝까지 아래에 나와 있습니다. 각 검은색 점은 슬라이딩 윈도우의 중심을 나타내고, 각 회색 점은 데이터 포인트를 나타냅니다.
평균 이동 클러스터링의 전체 과정
K-평균 클러스터링과 비교하여 이 방법은 평균 이동이 자동으로 이를 발견하므로 클러스터 수를 선택할 필요가 없습니다. 이것은 큰 장점입니다. 클러스터 중심이 최대 포인트 밀도를 향해 클러스터링된다는 사실도 매우 만족스럽습니다. 자연스러운 데이터 기반 의미를 이해하고 적응하는 것이 매우 직관적이기 때문입니다. 단점은 창 크기/반경 "r" 선택이 중요하지 않을 수 있다는 것입니다.
DBSCAN은 평균 이동과 유사하지만 몇 가지 중요한 장점이 있는 밀도 기반 클러스터링 알고리즘입니다. 아래에서 또 다른 재미있는 그래픽을 확인하고 시작해 보세요!
DBSCAN은 다른 클러스터링 알고리즘에 비해 많은 장점을 가지고 있습니다. 첫째, 고정된 수의 클러스터가 전혀 필요하지 않습니다. 또한 데이터 포인트가 매우 다르더라도 단순히 클러스터로 그룹화하는 평균 이동과 달리 이상치를 노이즈로 식별합니다. 또한 모든 크기와 모양의 클러스터를 매우 잘 찾을 수 있습니다.
DBSCAN의 가장 큰 단점은 클러스터의 밀도가 다를 때 다른 클러스터링 알고리즘만큼 성능을 발휘하지 못한다는 것입니다. 이는 밀도가 변경되면 인접 지점을 식별하는 데 사용되는 거리 임계값 ε 및 minPoints의 설정이 클러스터에 따라 변경되기 때문입니다. 이 단점은 거리 임계값 ε을 다시 추정하기 어려워지기 때문에 매우 고차원 데이터에서도 발생합니다.
K-평균의 주요 단점은 클러스터 중심 수단을 간단하게 사용한다는 것입니다. 아래 다이어그램에서 이것이 최선의 접근 방식이 아닌 이유를 확인할 수 있습니다. 왼쪽에는 동일한 평균을 중심으로 반지름이 다른 두 개의 원형 클러스터가 있음을 매우 명확하게 볼 수 있습니다. K-Means는 이러한 클러스터의 평균이 매우 가깝기 때문에 이 상황을 처리할 수 없습니다. K-평균은 평균을 군집 중심으로 사용하기 때문에 군집이 원형이 아닌 경우에도 실패합니다.
K-평균의 두 가지 실패 사례
가우스 혼합 모델(GMM)은 K-평균보다 더 많은 유연성을 제공합니다. GMM의 경우 데이터 포인트가 가우스 분포라고 가정합니다. 이는 평균을 사용하여 원형이라고 가정하는 것보다 덜 제한적인 가정입니다. 이런 식으로 클러스터의 모양을 설명하는 두 가지 매개변수인 평균과 표준편차를 갖게 됩니다! 2D를 예로 들면, 이는 클러스터가 모든 종류의 타원형 모양을 취할 수 있음을 의미합니다(x 및 y 방향 모두에서 표준 편차가 있으므로). 따라서 각 가우스 분포는 단일 클러스터에 할당됩니다.
각 클러스터의 가우스 매개변수(예: 평균 및 표준편차)를 찾기 위해 EM(Expectation Maximum)이라는 최적화 알고리즘을 사용합니다. 클러스터에 대한 가우스 적합의 예인 아래 다이어그램을 살펴보십시오. 그런 다음 GMM을 사용하여 최대 기대 클러스터링 프로세스를 계속할 수 있습니다.
GMM을 사용하면 두 가지 주요 이점이 있습니다. 첫째, GMM은 표준 편차 매개변수로 인해 클러스터 공분산 측면에서 K-평균보다 더 유연하며 클러스터는 원으로 제한되지 않고 타원형 모양을 취할 수 있습니다. K-평균은 실제로 각 클러스터의 공분산이 모든 차원에서 0에 가까운 GMM의 특수한 경우입니다. 둘째, GMM은 확률을 사용하기 때문에 데이터 포인트당 많은 클러스터가 있을 수 있습니다. 따라서 데이터 포인트가 두 개의 겹치는 클러스터 중간에 있는 경우 해당 데이터 포인트의 X%가 클래스 1에 속하고 Y%가 클래스 2에 속한다고 간단히 정의할 수 있습니다. 즉, GMM은 하이브리드 자격을 지원합니다.
계층적 클러스터링 알고리즘은 실제로 하향식 또는 상향식의 두 가지 범주로 나뉩니다. 상향식 알고리즘은 먼저 각 데이터 포인트를 단일 클러스터로 처리한 다음 모든 클러스터가 모든 데이터 포인트를 포함하는 단일 클러스터로 병합될 때까지 두 클러스터를 연속적으로 병합(또는 집계)합니다. 따라서 상향식 계층적 클러스터링을 응집 계층적 클러스터링 또는 HAC라고 합니다. 이 클러스터 계층 구조는 트리(또는 덴드로그램)로 표시됩니다. 트리의 루트는 모든 샘플을 수집하는 유일한 클러스터이고, 리프는 샘플이 하나만 있는 클러스터입니다. 알고리즘 단계를 시작하기 전에 아래 범례를 참조하세요.
집적 계층적 클러스터링
계층적 클러스터링에서는 클러스터 수를 지정할 필요가 없으며 트리를 구축하므로 가장 적합한 클러스터 수를 선택할 수도 있습니다. 또한 알고리즘은 거리 측정법 선택에 민감하지 않습니다. 모두 동일하게 성능을 발휘하는 반면, 다른 클러스터링 알고리즘의 경우 거리 측정법 선택이 중요합니다. 계층적 클러스터링 방법의 특히 좋은 예는 기본 데이터에 계층적 구조가 있고 계층을 복원하려는 경우입니다. 다른 클러스터링 알고리즘은 이를 수행할 수 없습니다. 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는 거리에 따라 그룹을 융합하는 것이 아니라 모듈성 변화에 따라 그룹을 융합합니다.
작동 방법은 다음과 같습니다.
커뮤니티 감지는 그래프 이론에서 인기 있는 연구 분야로, 일부 작은 클러스터를 무시하고 구조화된 그래프 모델에만 적용할 수 있다는 점에서 그 한계가 주로 반영됩니다. 그러나 이러한 유형의 알고리즘은 일반적인 구조화된 데이터와 실제 네트워크 데이터에서 매우 좋은 성능을 나타냅니다.
위는 데이터 과학자가 알아야 할 6가지 주요 클러스터링 알고리즘입니다! 다양한 알고리즘의 시각화를 보여드리며 이번 글을 마무리하겠습니다!
위 내용은 데이터 과학자가 알아야 할 6가지 클러스터링 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!