클러스터링 알고리즘: 처음부터 최신 기술까지

데이터 과학자에게 지금은 나쁜 시기가 아닙니다. 대화를 "빅 데이터"로 돌리면 진지한 사람들이 당신에게 관심을 가질 수 있고, "인공 지능"과 "머신 러닝"을 언급하면 ​​나머지 파티 군중은 흥미를 가질 것입니다. Google조차도 당신이 나쁘지 않고 점점 더 나아지고 있다고 생각합니다. 데이터 사이언티스트가 마법을 부리는 데 도움이 되는 '스마트' 알고리즘이 많이 있습니다. 모든 것이 복잡해 보일 수 있지만 알고리즘을 조금 이해하고 구성하면 필요한 알고리즘을 찾아 적용하는 것도 그리 어렵지 않습니다.

데이터 마이닝 또는 기계 학습에 대한 과정은 일반적으로 클러스터링으로 시작합니다. 클러스터링은 간단하고 유용하기 때문입니다. 이것은 우리가 설명하려는 데이터에 레이블이 지정되지 않은 다소 넓은 비지도 학습 영역의 중요한 부분입니다. 대부분의 경우 이것은 사용자가 예상 출력에 대한 많은 정보를 제공하지 않은 경우입니다. 알고리즘은 데이터만 가지고 있으며 최선을 다해야 합니다. 우리의 경우 유사한 데이터 포인트를 포함하는 그룹(클러스터)으로 데이터를 분리하는 클러스터링을 수행해야 하며 그룹 간의 유사도는 최대한 높아야 합니다. 데이터 포인트는 고객과 같은 모든 것을 나타낼 수 있습니다. 예를 들어, 유사한 사용자를 그룹화한 다음 각 클러스터에서 서로 다른 마케팅 캠페인을 실행하려는 경우 클러스터링이 유용할 수 있습니다.

K-평균 클러스터링

필요한 소개 후에 데이터 마이닝 과정은 항상 K-Means로 계속됩니다. 효과적이고 널리 사용되는 만능 클러스터링 알고리즘. 실제로 실행하기 전에 데이터 포인트 간의 거리 함수(예: 공간에서 포인트를 클러스터링하려면 유클리드 거리)를 정의해야 하고 원하는 클러스터 수(k)를 설정해야 합니다.

알고리즘은 k 포인트를 시작 중심(클러스터의 '중심')으로 선택하여 시작합니다. k개의 임의의 점을 선택하거나 다른 접근 방식을 사용할 수 있지만 임의의 점을 선택하는 것이 좋은 시작입니다. 그런 다음 두 단계를 반복적으로 반복합니다.

1. 할당 단계: 데이터 세트의 각 m개 포인트는 k개의 중심 중 가장 가까운 것으로 표시되는 클러스터에 할당됩니다. 각 점에 대해 각 중심까지의 거리를 계산하고 가장 먼 거리를 선택하기만 하면 됩니다.

2. 업데이트 단계: 각 클러스터에 대해 새 중심이 클러스터의 모든 포인트 평균으로 계산됩니다. 이전 단계에서 클러스터에 할당된 포인트 세트가 있습니다. 이제 이러한 각 집합에 대해 클러스터의 새 중심을 선언하는 평균을 계산합니다.

각 반복 후에 중심은 천천히 움직이고 각 점에서 할당된 중심까지의 총 거리는 점점 낮아집니다. 두 단계는 클러스터 할당에 더 이상 변경 사항이 없을 때까지 수렴될 때까지 교대로 수행됩니다. 여러 번 반복한 후에 동일한 점 세트가 각 중심에 할당되어 다시 동일한 중심으로 이어집니다. K-Means는 지역 최적으로 수렴하도록 보장됩니다. 그러나 이것이 반드시 최상의 전체 솔루션(전역 최적)일 필요는 없습니다.

최종 클러스터링 결과는 초기 중심 선택에 따라 달라질 수 있으므로 이 문제에 대해 많은 생각을 했습니다. 한 가지 간단한 솔루션은 임의의 초기 할당으로 K-Means를 몇 번 실행하는 것입니다. 그런 다음 각 점에서 클러스터까지의 거리 합계가 최소인 결과를 선택하여 최상의 결과를 선택할 수 있습니다. 즉, 처음에 최소화하려는 오류 값입니다.

초기 점을 선택하는 다른 접근 방식은 먼 점을 선택하는 것에 의존할 수 있습니다. 이는 더 나은 결과로 이어질 수 있지만 일부 오류일 수 있는 "오프"인 드문 단독 포인트인 이상값에 문제가 있을 수 있습니다. 의미 있는 클러스터와는 거리가 멀기 때문에 이러한 각 포인트는 결국 자체 '클러스터'가 될 수 있습니다. 좋은 균형은 K-Means++ 변형[Arthur and Vassilvitskii, 2007]이며, 초기화는 여전히 임의의 점을 선택하지만 확률은 이전에 할당된 중심으로부터의 제곱 거리에 비례합니다. 더 멀리 떨어져 있는 포인트는 시작 중심으로 선택될 확률이 더 높습니다. 결과적으로 포인트 그룹이 있는 경우 해당 그룹의 포인트가 선택될 확률도 확률이 더해질수록 높아져 앞서 언급한 이상치 문제가 해결됩니다.

K-Means++는 Python의 Scikit-learn K-Means 구현을 위한 기본 초기화이기도 합니다. Python을 사용하는 경우 이 라이브러리를 선택할 수 있습니다. Java의 경우 Weka 라이브러리가 좋은 시작일 수 있습니다.

자바(Weka)

 // Load some data Instances data = DataSource.read("data.arff"); // Create the model SimpleKMeans kMeans = new SimpleKMeans(); // We want three clusters kMeans.setNumClusters(3); // Run K-Means kMeans.buildClusterer(data); // Print the centroids Instances centroids = kMeans.getClusterCentroids(); for (Instance centroid: centroids) { System.out.println(centroid); } // Print cluster membership for each instance for (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point)); }

파이썬(Scikit 학습)

 > >> from sklearn import cluster, datasets > >> iris = datasets.loadiris() > >> Xiris = iris.data > >> yiris = iris.target > >> kmeans = cluster.KMeans(nclusters=3) > >> kmeans.fit(Xiris) KMeans(copy_x=True, init='k-means++', ... > >> print(kmeans.labels[::10]) [1 1 1 1 1 0 0 0 0 0 2 2 2 2 2] > >> print(yiris[::10]) [0 0 0 0 0 1 1 1 1 1 2 2 2 2 2]

위의 Python 예제에서 우리는 세 가지 다른 종의 붓꽃에 대한 꽃잎과 꽃받침 치수를 포함하는 표준 예제 데이터 세트 'Iris'를 사용했습니다. 우리는 이들을 3개의 클러스터로 클러스터링하고 얻은 클러스터를 실제 종(목표)과 비교하여 완벽하게 일치하는지 확인했습니다.

이 경우, 우리는 세 개의 다른 클러스터(종)가 있다는 것을 알았고 K-Means는 함께 가는 클러스터를 올바르게 인식했습니다. 그러나 일반적으로 많은 수의 클러스터 k를 선택하는 방법은 무엇입니까? 이러한 종류의 질문은 기계 학습에서 매우 일반적입니다. 더 많은 클러스터를 요청하면 더 작아지므로 총 오류(포인트에서 할당된 클러스터까지의 총 거리)는 더 작아집니다. 그래서, 더 큰 k를 설정하는 것이 좋은 생각입니까? 우리는 k = m을 갖는 것으로 끝낼 수 있습니다. 즉, 각 점은 자신의 중심이고 각 클러스터는 단 하나의 점을 갖습니다. 예, 총 오류는 0이지만 데이터에 대한 더 간단한 설명을 얻지 못했고 나타날 수 있는 몇 가지 새로운 점을 다룰 만큼 일반적이지 않습니다. 이것을 과적합이라고 하며 우리는 그것을 원하지 않습니다.

이 문제를 처리하는 방법은 더 많은 수의 클러스터에 대해 약간의 패널티를 포함하는 것입니다. 그래서 이제 오류뿐만 아니라 오류 + 패널티 도 최소화하려고 합니다. 클러스터 수를 늘리면 오류가 0으로 수렴되지만 패널티는 커집니다. 어떤 시점에서는 다른 클러스터를 추가함으로써 얻는 이득이 도입된 페널티보다 적을 것이며 최적의 결과를 얻게 될 것입니다. 이를 위해 BIC(Bayesian Information Criterion)를 사용하는 솔루션을 X-Means라고 합니다[Pelleg and Moore, 2000].

우리가 적절하게 정의해야 하는 또 다른 것은 거리 함수입니다. 데이터의 특성을 감안할 때 논리적인 작업인 경우가 있습니다. 공간의 점에 대해 유클리드 거리는 명백한 솔루션이지만 다른 '단위'의 기능, 이산 변수 등에 대해서는 까다로울 수 있습니다. 이는 많은 도메인 지식이 필요할 수 있습니다. 또는 기계 학습에 도움을 요청할 수 있습니다. 우리는 실제로 거리 함수를 배우려고 시도할 수 있습니다. 그룹화 방법을 알고 있는 학습 포인트 세트(즉, 클러스터로 레이블이 지정된 포인트)가 있는 경우 지도 학습 기술을 사용하여 좋은 기능을 찾은 다음 아직 클러스터링되지 않은 목표 세트에 적용할 수 있습니다. .

K-Means에 사용된 방법은 두 단계가 번갈아 가며 EM(기대값-최대화) 방법과 유사합니다. 사실 EM의 아주 간단한 버전이라고 할 수 있습니다. 그러나 동일한 원리를 일부 공유하더라도 보다 정교한 EM 클러스터링 알고리즘과 혼동되어서는 안 됩니다.

EM 클러스터링

따라서 K-Means 클러스터링을 사용하면 각 포인트가 단일 클러스터에만 할당되고 클러스터는 중심으로만 설명됩니다. 클러스터가 겹치거나 원형이 아닌 클러스터에 문제가 있을 수 있으므로 이는 너무 유연하지 않습니다. EM 클러스터링을 사용하여 이제 한 단계 더 나아가 중심(평균), 공분산(타원형 클러스터를 가질 수 있도록) 및 가중치(클러스터 크기)로 각 클러스터를 설명할 수 있습니다. 포인트가 클러스터에 속할 확률은 이제 다변수 가우스 확률 분포(다변수 - 여러 변수에 따라 다름)로 지정됩니다. 이는 또한 포인트가 가우스 '종' 아래에 있을 확률, 즉 클러스터에 속하는 포인트의 확률을 계산할 수 있음을 의미합니다.

이제 각 포인트에 대해 현재 클러스터 각각에 속하는 확률을 계산하여 EM 절차를 시작합니다(다시 말하지만 처음에 무작위로 생성될 수 있음). E-스텝입니다. 하나의 클러스터가 포인트에 대한 정말 좋은 후보라면 1에 가까울 확률이 있습니다. 그러나 둘 이상의 클러스터가 허용 가능한 후보가 될 수 있으므로 포인트는 클러스터에 대한 확률 분포를 갖습니다. 하나의 클러스터에 국한되지 않는 포인트의 알고리즘 속성을 "소프트 클러스터링"이라고 합니다.

M-step은 이제 이전 클러스터 세트에 대한 포인트 할당을 사용하여 각 클러스터의 매개변수를 다시 계산합니다. 클러스터의 새로운 평균, 공분산 및 가중치를 계산하기 위해 각 포인트 데이터는 이전 단계에서 계산된 클러스터에 속할 확률에 따라 가중치가 부여됩니다.

이 두 단계를 교대로 수행하면 수렴될 때까지 총 로그 가능성이 증가합니다. 다시 말하지만, 최대값은 로컬일 수 있으므로 알고리즘을 여러 번 실행하여 더 나은 클러스터를 얻을 수 있습니다.

이제 각 점에 대해 단일 군집을 결정하려면 가장 가능성 있는 군집을 선택하면 됩니다. 확률 모델이 있으면 유사한 데이터를 생성하는 데 사용할 수도 있습니다. 즉, 관찰한 데이터와 유사한 더 많은 포인트를 샘플링하는 것입니다.

선호도 전파

AP(Affinity Propagation)는 2007년 Frey와 Dueck에 의해 발표되었으며 단순성, 일반적인 적용 가능성 및 성능으로 인해 점점 더 인기를 얻고 있습니다. 최첨단에서 사실상의 표준으로 위상을 바꾸고 있습니다.

K-Means 및 유사한 알고리즘의 주요 단점은 클러스터 수를 선택하고 초기 점 집합을 선택해야 한다는 것입니다. 대신에 Affinity Propagation은 데이터 포인트 쌍 간의 유사성에 대한 입력 측정값으로 사용하고 동시에 모든 데이터 포인트를 잠재적인 표본으로 간주합니다. 고품질의 예시 집합과 해당 클러스터가 점진적으로 나타날 때까지 데이터 포인트 간에 실제 값 메시지가 교환됩니다.

입력으로 알고리즘은 두 가지 데이터 세트를 제공해야 합니다.

1. 데이터 포인트 간의 유사성, 포인트가 다른 포인트의 모범이 되는 정도를 나타냅니다. 동일한 클러스터에 속할 수 없기 때문에 두 점 사이에 유사성이 없는 경우 구현에 따라 이 유사성을 생략하거나 -Infinity로 설정할 수 있습니다.

2. 각 데이터 포인트가 모범이 되기 위한 적합성을 나타내는 기본 설정. 우리는 이 역할에 대해 선호될 수 있는 몇 가지 선험적 정보를 가지고 있을 수 있으며 선호를 통해 이를 나타낼 수 있습니다.

유사성과 선호도는 종종 단일 행렬을 통해 표현되며, 여기서 주대각선의 값은 선호도를 나타냅니다. 행렬 표현은 밀도가 높은 데이터 세트에 적합합니다. 점 사이의 연결이 희박한 경우 전체 nxn 행렬을 메모리에 저장하지 않고 대신 연결된 점에 대한 유사성 목록을 유지하는 것이 더 실용적입니다. 무대 뒤에서 '포인트 간 메시지 교환'은 행렬을 조작하는 것과 동일하며 관점과 구현의 문제일 뿐입니다.

그런 다음 알고리즘은 수렴될 때까지 여러 번의 반복을 통해 실행됩니다. 각 반복에는 두 가지 메시지 전달 단계가 있습니다.

1. 책임 계산: 책임 r(i, k)는 점 i에 대한 다른 잠재적 모형을 고려하여 점 k가 점 i에 대한 모형 역할을 하는 데 얼마나 적합한지에 대한 축적된 증거를 반영합니다. 책임은 데이터 포인트 i에서 후보 표본 포인트 k로 전송됩니다.

2. 가용성 계산: 가용성 a(i, k)는 포인트 k가 예시여야 한다는 다른 지점의 지원을 고려하여 포인트 i가 포인트 k를 예시로 선택하는 것이 얼마나 적절한지에 대한 축적된 증거를 반영합니다. 가용성은 후보 예시 포인트 k에서 포인트 i로 전송됩니다.

책임을 계산하기 위해 알고리즘은 이전 반복에서 계산된 원래 유사성과 가용성을 사용합니다(초기에는 모든 가용성이 0으로 설정됨). 책임은 i 지점과 k 지점 사이의 입력 유사도에서 해당 표본으로 설정되며, i 지점과 다른 후보 표본 간의 유사성 및 가용성 합계에서 가장 큰 값을 뺍니다. 어떤 점이 표본에 얼마나 적합한지를 계산하는 논리는 초기의 선험적 선호도가 높을수록 선호도가 높지만 자신을 좋은 후보라고 생각하는 유사한 점이 있을 때 책임이 낮아진다는 것입니다. 몇 번의 반복으로 하나가 결정될 때까지 둘 사이의 경쟁'.

그런 다음 가용성을 계산할 때 계산된 책임을 각 후보자가 좋은 본보기가 될 것인지의 증거로 사용합니다. 가용성 a(i, k)는 자기 책임 r(k, k)에 후보 표본 k가 다른 지점에서 받는 긍정적 책임의 합으로 설정됩니다.

마지막으로 값의 변경이 일부 임계값 아래로 떨어지거나 최대 반복 횟수에 도달하는 경우와 같이 절차를 종료하기 위해 다른 중지 기준을 가질 수 있습니다. Affinity Propagation 절차를 통해 어느 지점에서든 책임(r) 및 가용성(a) 행렬을 합산하면 필요한 클러스터링 정보를 얻을 수 있습니다. 내가 모범이다. 또는 예제 세트가 필요한 경우 주 대각선을 스캔할 수 있습니다. r(i, i) + a(i, i) > 0인 경우 점 i는 예시입니다.

우리는 K-Means 및 유사한 알고리즘을 사용하여 클러스터 수를 결정하는 것이 까다로울 수 있음을 보았습니다. AP를 사용하면 명시적으로 지정할 필요가 없지만 최적이라고 생각하는 것보다 더 많거나 적은 클러스터를 얻으면 여전히 약간의 조정이 필요할 수 있습니다. 운 좋게도 기본 설정을 조정하면 클러스터 수를 줄이거나 늘릴 수 있습니다. 기본 설정을 더 높은 값으로 설정하면 더 많은 클러스터가 생성됩니다. 각 포인트는 모범이 되기 위한 적합성에 대해 '더 확실'하고 따라서 '이기고' 다른 포인트의 '지배' 아래에 포함하기가 더 어렵기 때문입니다. 반대로 더 낮은 기본 설정을 지정하면 클러스터가 더 적게 생성됩니다. 마치 그들이 "아니오, 아니요, 제발, 당신이 더 나은 본보기입니다. 당신의 클러스터에 합류하겠습니다"라고 말하는 것처럼. 일반적으로 모든 기본 설정을 중간에서 많은 수의 클러스터에 대한 중간 유사도로 설정하거나 적당한 수의 클러스터에 대해 가장 낮은 유사도로 설정할 수 있습니다. 그러나 우리의 요구에 정확히 맞는 결과를 얻으려면 기본 설정을 조정하는 몇 번의 실행이 필요할 수 있습니다.

계층적 선호도 전파(Hierarchical Affinity Propagation)는 데이터 세트를 두 개의 하위 집합으로 분할하고 개별적으로 클러스터링한 다음 두 번째 수준의 클러스터링을 수행하여 2차 복잡성을 처리하는 알고리즘의 변형으로 언급할 가치도 있습니다.

결국…

클러스터링 알고리즘에는 전체 범위가 있으며 각 알고리즘에는 사용하는 데이터 유형, 시간 복잡성, 약점 등에 대한 장단점이 있습니다. 더 많은 알고리즘을 언급하자면, 예를 들어 Hierarchical Agglomerative Clustering(또는 Linkage Clustering)이 있습니다. 이는 원형(또는 초구형) 클러스터가 필요하지 않고 클러스터의 수를 미리 알 수 없는 경우에 좋습니다. 각 포인트가 별도의 클러스터인 것으로 시작하여 모든 것이 하나의 큰 클러스터에 있을 때까지 각 단계에서 가장 가까운 두 클러스터를 결합하여 작동합니다.

Hierarchical Agglomerative Clustering을 사용하면 적절한 위치에서 덴드로그램(트리 다이어그램)을 수평으로 자르면 나중에 클러스터 수를 쉽게 결정할 수 있습니다. 또한 반복 가능하지만(동일한 데이터 세트에 대해 항상 동일한 답변을 제공함) 복잡성이 더 높습니다(2차).

그런 다음 DBSCAN(Density-Based Spatial Clustering of Applications with Noise)도 언급할 가치가 있는 알고리즘입니다. 촘촘하게 모여 있는 포인트를 그룹화하여 가까운 포인트가 있는 모든 방향으로 클러스터를 확장하여 다양한 클러스터 모양을 처리합니다.

이러한 알고리즘은 자체 기사를 받을 자격이 있으며 나중에 별도의 게시물에서 살펴볼 수 있습니다.

어떤 알고리즘을 사용해야 하는지 알기 위해서는 몇 가지 시행착오를 겪은 경험이 필요합니다. 운 좋게도 우리는 다양한 프로그래밍 언어로 구현된 범위가 있으므로 이를 시도하려면 약간의 플레이 의지만 있으면 됩니다.