이 페이지의 최신 내용은 아직 번역되지 않았습니다. 최신 내용은 영문으로 볼 수 있습니다.

kmeans

k-평균 군집화

설명

예제

idx = kmeans(X,k)k-평균 군집화를 수행하여 nxp 데이터 행렬 X의 관측값을 k개 군집으로 분할한 후 각 관측값의 군집 인덱스를 포함하는 nx1 벡터(idx)를 반환합니다. X의 행은 점에 대응되고, 열은 변수에 대응됩니다.

기본적으로, kmeans는 군집 중심 초기화에 제곱 유클리드 거리 측정법과 k-평균++ 알고리즘을 사용합니다.

예제

idx = kmeans(X,k,Name,Value)는 하나 이상의 Name,Value 쌍 인수로 지정된 추가 옵션을 사용하여 군집 인덱스를 반환합니다.

예를 들어, 코사인 거리, 새 초기값을 사용하여 군집화를 반복할 횟수 또는 병렬 연산 사용 여부를 지정합니다.

예제

[idx,C] = kmeans(___)kxp 행렬 Ck개 군집 중심 위치를 반환합니다.

예제

[idx,C,sumd] = kmeans(___)는 점-중심 간 거리의 군집 내 합을 kx1 벡터 sumd로 반환합니다.

예제

[idx,C,sumd,D] = kmeans(___)는 각 점에서 모든 중심까지의 거리를 nxk 행렬 D로 반환합니다.

예제

모두 축소

k-평균 군집화를 사용하여 데이터를 군집화한 후 군집 영역을 플로팅합니다.

피셔(Fisher)의 붓꽃 데이터 세트를 불러옵니다. 꽃잎 길이와 너비를 예측 변수로 사용합니다.

load fisheriris
X = meas(:,3:4);

figure;
plot(X(:,1),X(:,2),'k*','MarkerSize',5);
title 'Fisher''s Iris Data';
xlabel 'Petal Lengths (cm)'; 
ylabel 'Petal Widths (cm)';

큰 쪽 군집은 낮은 분산 영역과 높은 분산 영역으로 분할되는 것처럼 보입니다. 이는 큰 쪽 군집이 2개의 겹치는 군집임을 뜻할 수 있습니다.

데이터를 군집화합니다. k = 3으로 군집 개수를 지정합니다.

rng(1); % For reproducibility
[idx,C] = kmeans(X,3);

kmeans는 기본적으로 중심 초기화에 k-평균++ 알고리즘을 사용하고 제곱 유클리드 거리를 사용합니다. 'Replicates' 이름-값 쌍의 인수를 설정하여 더 낮은 국소 최솟값을 구하는 것이 좋습니다.

idxX에 포함된 관측값에 대응되는 예측된 군집 인덱스로 구성된 벡터입니다. C는 최종 중심 위치를 포함하는 3x2 행렬입니다.

kmeans를 사용하여 각 중심에서 그리드의 점까지의 거리를 계산합니다. 이렇게 하려면 중심(C)과 그리드의 점을 kmeans에 전달하고 알고리즘의 1회 반복을 구현합니다.

x1 = min(X(:,1)):0.01:max(X(:,1));
x2 = min(X(:,2)):0.01:max(X(:,2));
[x1G,x2G] = meshgrid(x1,x2);
XGrid = [x1G(:),x2G(:)]; % Defines a fine grid on the plot

idx2Region = kmeans(XGrid,3,'MaxIter',1,'Start',C);
Warning: Failed to converge in 1 iterations.
    % Assigns each node in the grid to the closest centroid

kmeans가 알고리즘이 수렴되지 않았음을 나타내는 경고를 표시합니다. 이는 소프트웨어가 1회 반복만 구현했기 때문에 예상되는 동작입니다.

군집 영역을 플로팅합니다.

figure;
gscatter(XGrid(:,1),XGrid(:,2),idx2Region,...
    [0,0.75,0.75;0.75,0,0.75;0.75,0.75,0],'..');
hold on;
plot(X(:,1),X(:,2),'k*','MarkerSize',5);
title 'Fisher''s Iris Data';
xlabel 'Petal Lengths (cm)';
ylabel 'Petal Widths (cm)'; 
legend('Region 1','Region 2','Region 3','Data','Location','SouthEast');
hold off;

표본 데이터를 임의로 생성합니다.

rng default; % For reproducibility
X = [randn(100,2)*0.75+ones(100,2);
    randn(100,2)*0.5-ones(100,2)];

figure;
plot(X(:,1),X(:,2),'.');
title 'Randomly Generated Data';

데이터에 두 개의 군집이 있는 것처럼 보입니다.

데이터를 두 개 군집으로 분할하고 5개 초기화 중에서 최적의 배열을 선택합니다. 최종 출력값을 표시합니다.

opts = statset('Display','final');
[idx,C] = kmeans(X,2,'Distance','cityblock',...
    'Replicates',5,'Options',opts);
Replicate 1, 3 iterations, total sum of distances = 201.533.
Replicate 2, 5 iterations, total sum of distances = 201.533.
Replicate 3, 3 iterations, total sum of distances = 201.533.
Replicate 4, 3 iterations, total sum of distances = 201.533.
Replicate 5, 2 iterations, total sum of distances = 201.533.
Best total sum of distances = 201.533

기본적으로, 소프트웨어는 k-평균++를 사용하여 개별적으로 반복 실험을 초기화합니다.

군집과 군집 중심을 플로팅합니다.

figure;
plot(X(idx==1,1),X(idx==1,2),'r.','MarkerSize',12)
hold on
plot(X(idx==2,1),X(idx==2,2),'b.','MarkerSize',12)
plot(C(:,1),C(:,2),'kx',...
     'MarkerSize',15,'LineWidth',3) 
legend('Cluster 1','Cluster 2','Centroids',...
       'Location','NW')
title 'Cluster Assignments and Centroids'
hold off

idxsilhouette에 전달하여 군집이 얼마나 잘 분리되었는지 확인할 수 있습니다.

대규모 데이터 세트를 군집화하는 데는 시간이 걸릴 수 있으며, 특히 온라인 업데이트(기본적으로 설정됨)를 사용하는 경우 그렇습니다. Parallel Computing Toolbox ™ 라이선스가 있는 경우 병렬 연산에 사용할 옵션을 설정하면 kmeans가 병렬로 각 군집화 작업(또는 반복 실험)을 실행합니다. 그리고 Replicates > 1이면 병렬 연산이 수렴 시간을 줄여 줍니다.

가우스 혼합 모델에서 대규모 데이터 세트를 임의로 생성합니다.

Mu = bsxfun(@times,ones(20,30),(1:20)'); % Gaussian mixture mean
rn30 = randn(30,30);
Sigma = rn30'*rn30; % Symmetric and positive-definite covariance
Mdl = gmdistribution(Mu,Sigma); % Define the Gaussian mixture distribution

rng(1); % For reproducibility
X = random(Mdl,10000);

Mdl은 20개 성분을 포함하는 30차원 gmdistribution 모델입니다. XMdl에서 생성된 데이터로 구성된 10000x30 행렬입니다.

병렬 연산에 사용할 옵션을 지정합니다.

stream = RandStream('mlfg6331_64');  % Random number stream
options = statset('UseParallel',1,'UseSubstreams',1,...
    'Streams',stream);

RandStream의 입력 인수 'mlfg6331_64'는 승산식 시차 피보나치 수열(Multiplicative Lagged Fibonacci) 생성기 알고리즘을 사용하도록 지정합니다. options는 추정을 제어하는 옵션 지정 필드가 포함된 구조체형 배열입니다.

k-평균 군집화를 사용하여 데이터를 군집화합니다. 데이터에 20개 군집(k = 20)이 있다고 지정하고 반복 횟수를 늘립니다. 일반적으로, 목적 함수는 국소 최솟값을 포함합니다. 더 낮은 국소 최솟값을 구하는 데 도움이 되도록 10회 반복 실험을 지정합니다.

tic; % Start stopwatch timer
[idx,C,sumd,D] = kmeans(X,20,'Options',options,'MaxIter',10000,...
    'Display','final','Replicates',10);
Starting parallel pool (parpool) using the 'local' profile ...
connected to 6 workers.
Replicate 5, 72 iterations, total sum of distances = 7.73161e+06.
Replicate 1, 64 iterations, total sum of distances = 7.72988e+06.
Replicate 3, 68 iterations, total sum of distances = 7.72576e+06.
Replicate 4, 84 iterations, total sum of distances = 7.72696e+06.
Replicate 6, 82 iterations, total sum of distances = 7.73006e+06.
Replicate 7, 40 iterations, total sum of distances = 7.73451e+06.
Replicate 2, 194 iterations, total sum of distances = 7.72953e+06.
Replicate 9, 105 iterations, total sum of distances = 7.72064e+06.
Replicate 10, 125 iterations, total sum of distances = 7.72816e+06.
Replicate 8, 70 iterations, total sum of distances = 7.73188e+06.
Best total sum of distances = 7.72064e+06
toc % Terminate stopwatch timer
Elapsed time is 61.915955 seconds.

명령 창에 6개의 워커를 사용할 수 있다고 표시되어 있습니다. 워커의 개수는 시스템에 따라 다를 수 있습니다. 명령 창에 반복 횟수와 각 반복 실험에 대한 최종 목적 함수 값이 표시됩니다. 반복 실험 9가 가장 작은 거리 총합을 가지므로 출력 인수에는 이 반복 실험의 결과가 포함됩니다.

kmeansk-평균 군집화를 수행하여 데이터를 k개의 군집으로 분할합니다. 군집화를 수행할 새 데이터 세트가 있는 경우 kmeans를 사용하여 기존 데이터와 새 데이터를 포함하는 새 군집을 생성할 수 있습니다. kmeans 함수는 C/C++ 코드 생성을 지원하므로 훈련 데이터를 받아서 군집화 결과를 반환하는 코드를 생성한 다음 코드를 장치에 배포할 수 있습니다. 이 워크플로에서는 훈련 데이터를 전달해야 하는데, 그 크기가 상당히 클 수 있습니다. 장치의 메모리를 절약하기 위해 각각 kmeanspdist2를 사용하여 훈련과 예측을 분리할 수 있습니다.

kmeans를 사용하여 MATLAB®에서 군집을 생성하고 생성된 코드에서 pdist2를 사용하여 기존 군집에 새 데이터를 할당합니다. 코드 생성을 위해, 군집 중심 위치와 새 데이터 세트를 받아서 가장 가까운 군집의 인덱스를 반환하는 진입점 함수를 정의합니다. 그런 다음 진입점 함수에 대한 코드를 생성합니다.

C/C++ 코드를 생성하려면 MATLAB® Coder™가 필요합니다.

k-평균 군집화 수행하기

세 개의 분포를 사용하여 훈련 데이터 세트를 생성합니다.

rng('default') % For reproducibility
X = [randn(100,2)*0.75+ones(100,2);
    randn(100,2)*0.5-ones(100,2);
    randn(100,2)*0.75];

kmeans를 사용하여 훈련 데이터를 세 개 군집으로 분할합니다.

[idx,C] = kmeans(X,3);

군집과 군집 중심을 플로팅합니다.

figure
gscatter(X(:,1),X(:,2),idx,'bgm')
hold on
plot(C(:,1),C(:,2),'kx')
legend('Cluster 1','Cluster 2','Cluster 3','Cluster Centroid')

기존 군집에 새 데이터 할당하기

검정 데이터 세트를 생성합니다.

Xtest = [randn(10,2)*0.75+ones(10,2);
    randn(10,2)*0.5-ones(10,2);
    randn(10,2)*0.75];

기존 군집을 사용하여 검정 데이터 세트를 분류합니다. pdist2를 사용하여 각 검정 데이터 점에서 가장 가까운 중심을 구합니다.

[~,idx_test] = pdist2(C,Xtest,'euclidean','Smallest',1);

gscatter를 사용하여 검정 데이터를 플로팅하고 idx_test를 사용하여 검정 데이터에 레이블을 지정합니다.

gscatter(Xtest(:,1),Xtest(:,2),idx_test,'bgm','ooo')
legend('Cluster 1','Cluster 2','Cluster 3','Cluster Centroid', ...
    'Data classified to Cluster 1','Data classified to Cluster 2', ...
    'Data classified to Cluster 3')

코드 생성하기

기존 군집에 새 데이터를 할당하는 C 코드를 생성합니다. C/C++ 코드를 생성하려면 MATLAB® Coder™가 필요합니다.

중심 위치와 새 데이터를 받는 findNearestCentroid라는 이름의 진입점 함수를 정의한 다음 pdist2를 사용하여 가장 가까운 군집을 찾습니다.

진입점 함수의 함수 시그니처 뒤에 %#codegen 컴파일러 지시문(또는 pragma)을 추가하여 MATLAB 알고리즘을 위한 코드를 생성하고자 함을 표시합니다. 이 지시문을 추가하면 MATLAB 코드 분석기에 코드 생성 중에 오류를 유발할 수 있는 위반을 진단하여 수정할 수 있도록 지원해 달라는 명령을 내리게 됩니다.

type findNearestCentroid % Display contents of findNearestCentroid.m
function idx = findNearestCentroid(C,X) %#codegen
[~,idx] = pdist2(C,X,'euclidean','Smallest',1); % Find the nearest centroid

참고: 이 페이지의 오른쪽 위 섹션에 있는 버튼을 클릭하고 이 예제를 MATLAB®에서 열면 예제 폴더가 열립니다. 이 폴더에는 진입점 함수 파일이 포함되어 있습니다.

codegen을 사용하여 코드를 생성합니다. C와 C++는 정적 유형 언어이므로 컴파일 시점에 진입점 함수의 모든 변수의 속성을 결정해야 합니다. findNearestCentroid의 입력값 크기와 데이터형을 지정하려면 -args 옵션을 사용하여 특정 데이터형과 배열 크기를 포함하는 값 세트를 나타내는 MATLAB 표현식을 전달하십시오. 자세한 내용은 Specify Variable-Size Arguments for Code Generation 항목을 참조하십시오.

codegen findNearestCentroid -args {C,Xtest}

codegen은 플랫폼별 확장자를 갖는 MEX 함수 findNearestCentroid_mex를 생성합니다.

생성된 코드를 확인합니다.

myIndx = findNearestCentroid(C,Xtest);
myIndex_mex = findNearestCentroid_mex(C,Xtest);
verifyMEX = isequal(idx_test,myIndx,myIndex_mex)
verifyMEX = logical
   1

isequal이 논리값 1(true)을 반환합니다. 이는 모든 입력값이 동일하다는 의미입니다. 비교를 통해 pdist2 함수, findNearestCentroid 함수 및 MEX 함수가 동일한 인덱스를 반환함을 확인할 수 있습니다.

GPU Coder™를 사용하여 최적화된 CUDA® 코드를 생성할 수도 있습니다.

cfg = coder.gpuConfig('mex');
codegen -config cfg findNearestCentroid -args {C,Xtest}

코드 생성에 대한 자세한 내용은 General Code Generation Workflow 항목을 참조하십시오. GPU Coder에 대한 자세한 내용은 Getting Started with GPU Coder (GPU Coder) 항목과 Supported Functions (GPU Coder) 항목을 참조하십시오.

입력 인수

모두 축소

데이터로, 숫자형 행렬로 지정됩니다. X의 행은 관측값에 대응되고, 열은 변수에 대응됩니다.

X가 숫자형 벡터이면 kmeans는 벡터의 방향에 관계없이 이를 nx1 데이터 행렬로 처리합니다.

데이터형: single | double

데이터에 포함된 군집 개수로, 양의 정수로 지정됩니다.

데이터형: single | double

이름-값 쌍의 인수

선택적으로 Name,Value 인수가 쉼표로 구분되어 지정할 수 있습니다. 여기서 Name은 인수 이름이고 Value는 이에 대응하는 값입니다. Name은 따옴표로 묶어야 합니다. Name1,Value1,...,NameN,ValueN과 같이 여러 개의 이름-값 쌍의 인수를 원하는 순서로 지정할 수 있습니다.

예: 'Distance','cosine','Replicates',10,'Options',statset('UseParallel',1)은 코사인 거리를 지정하고, 서로 다른 시작 값에서 군집화 반복 실험을 10회 수행하도록 지정하고, 병렬 연산을 사용하도록 지정합니다.

명령 창에 표시할 출력 수준으로, 'Display'와 함께 다음 옵션 중 하나가 쉼표로 구분되어 지정됩니다.

  • 'final' — 최종 반복의 결과를 표시함

  • 'iter' — 각 반복의 결과를 표시함

  • 'off' — 아무 것도 표시하지 않음

예: 'Display','final'

p차원 공간에서 최소화에 사용되는 거리 측정법으로, 'Distance'와 함께 'sqeuclidean', 'cityblock', 'cosine', 'correlation' 또는 'hamming'이 쉼표로 구분되어 지정됩니다.

kmeans는 지원되는 여러 거리 측정법에 대해 각기 다르게 중심 군집을 계산합니다. 다음 표에는 사용 가능한 거리 측정법이 요약되어 있습니다. 공식에서 x는 관측값(즉, X의 행)이고 c는 중심(행 벡터)입니다.

거리 측정법설명공식
'sqeuclidean'

제곱 유클리드 거리입니다(디폴트 값). 각 중심은 해당 군집에 포함된 점의 평균입니다.

d(x,c)=(xc)(xc)

'cityblock'

절대 차이의 합입니다(즉, L1 거리). 각 중심은 해당 군집에 포함된 점의 성분별 중앙값입니다.

d(x,c)=j=1p|xjcj|

'cosine'

1에서 점 간의 끼인각에 대한 코사인을 뺀 값입니다(벡터로 처리됨). 각 중심은 해당 군집에 포함된 점을 단위 유클리드 길이로 정규화한 후에 구한 점의 평균입니다.

d(x,c)=1xc(xx)(cc)

'correlation'

1에서 점 간의 표본 상관을 뺀 값입니다(일련의 값으로 처리됨). 각 중심은 해당 군집에 포함된 점을 평균 0과 단위 표준편차로 정규화한 후에 구한 점의 성분별 평균입니다.

d(x,c)=1(xx¯)(cc¯)(xx¯)(xx¯)(cc¯)(cc¯),

여기서는 다음을 조건으로 합니다.

  • x¯=1p(j=1pxj)1p

  • c¯=1p(j=1pcj)1p

  • 1p는 p개의 1로 구성된 행 벡터입니다.

'hamming'

이 측정법은 이진 데이터에만 적합합니다.

이는 서로 다른 비트의 비율입니다. 각 중심은 해당 군집에 포함된 점의 성분별 중앙값입니다.

d(x,y)=1pj=1pI{xjyj},

여기서 I는 표시 함수입니다.

예: 'Distance','cityblock'

군집이 모든 멤버 관측값을 손실하는 경우 수행할 동작으로, 'EmptyAction'과 함께 다음 옵션 중 하나가 쉼표로 구분되어 지정됩니다.

설명
'error'

빈 군집을 오류로 처리합니다.

'drop'

비워지는 군집을 모두 제거합니다. kmeansCD에서 이에 대응되는 반환 값을 NaN으로 설정합니다.

'singleton'

중심에서 가장 먼 점 하나로 구성된 새 군집을 생성합니다(디폴트 값).

예: 'EmptyAction','error'

최대 반복 횟수로, 'MaxIter'와 함께 양의 정수가 쉼표로 구분되어 지정됩니다.

예: 'MaxIter',1000

데이터형: double | single

온라인 업데이트 플래그로, 'OnlinePhase'와 함께 'off' 또는 'on'이 쉼표로 구분되어 지정됩니다.

OnlinePhaseon이면 kmeans는 일괄 업데이트 단계 외에 온라인 업데이트 단계도 수행합니다. 온라인 단계는 데이터 세트가 클 경우 시간이 많이 소비될 수 있지만, 거리 기준의 국소 최솟값이 되는 해를 보장합니다. 즉, 소프트웨어는 임의의 점을 다른 군집으로 이동할 경우 거리의 총합이 증가하는 데이터의 분할을 구하게 됩니다.

예: 'OnlinePhase','on'

피팅 기준을 최소화하기 위해 반복 알고리즘을 제어하는 옵션으로, 'Options'와 함께 statset에서 반환되는 구조체형 배열이 쉼표로 구분되어 지정됩니다. 구조체형 배열의 지원되는 필드에는 반복 알고리즘을 제어하기 위한 옵션을 지정합니다.

다음 표에는 지원되는 필드가 요약되어 있습니다. 지원되는 필드를 사용하려면 Parallel Computing Toolbox™가 필요합니다.

필드설명
'Streams'

RandStream 객체 또는 이러한 객체로 구성된 셀형 배열. Streams를 지정하지 않으면 kmeans가 디폴트 스트림을 사용합니다. Streams를 지정하는 경우 다음의 모든 조건이 존재하는 경우를 제외하고는 단일 객체를 사용하십시오.

  • 열어 놓은 병렬 풀이 있습니다.

  • UseParalleltrue입니다.

  • UseSubstreamsfalse입니다.

이 경우에는 병렬 풀과 크기가 같은 셀형 배열을 사용하십시오. 병렬 풀이 열려 있지 않은 경우 Streams가 단일 난수 스트림을 제공해야 합니다.

'UseParallel'
  • true이고 Replicates > 1이면 kmeans가 각 반복 실험에 k-평균 알고리즘을 병렬로 구현합니다.

  • Parallel Computing Toolbox가 설치되어 있지 않은 경우 계산이 직렬 모드로 실행됩니다. 디폴트 값은 직렬 계산을 나타내는 false입니다.

'UseSubstreams'재현 가능한 방식으로 병렬로 계산하려면 true로 설정하십시오. 디폴트 값은 false입니다. 재현 가능한 방식으로 계산하려면 Streams를 서브스트림을 허용하는 유형인 'mlfg6331_64' 또는 'mrg32k3a'로 설정하십시오.

더욱 예측 가능한 결과를 얻으려면 kmeans를 불러오고 'Options',statset('UseParallel',1)을 설정하기 전에, parpool을 사용하고 병렬 풀을 명시적으로 생성해야 합니다.

예: 'Options',statset('UseParallel',1)

데이터형: struct

새 초기 군집 중심 위치를 사용하여 군집화를 반복할 횟수로, 'Replicates'와 함께 정수가 쉼표로 구분되어 지정됩니다. kmeans는 가장 작은 sumd를 갖는 해를 반환합니다.

3차원 배열을 'Start' 이름-값 쌍의 인수의 값으로 제공하여 'Replicates'를 암시적으로 설정할 수 있습니다.

예: 'Replicates',5

데이터형: double | single

초기 군집 중심 위치(즉, 시드값)를 선택하기 위한 방법으로, 'Start'와 함께 'cluster', 'plus', 'sample', 'uniform', 숫자형 행렬 또는 숫자형 배열이 쉼표로 구분되어 지정됩니다. 이 표에는 시드값을 선택하는 데 사용할 수 있는 옵션이 요약되어 있습니다.

설명
'cluster'

X의 임의 10% 부표본의 관측값 개수가 k보다 큰 경우 부표본에서 예비 군집화 단계를 수행합니다. 이 예비 단계는 'sample'을 사용하여 자체적으로 초기화됩니다.

임의 10% 부표본의 관측값 개수가 k보다 작은 경우 X에서 k개의 관측값이 무작위로 선택됩니다.

'plus'(디폴트 값)군집 중심 초기화를 위해 k-평균++ 알고리즘을 구현하여 k개 시드값을 선택합니다.
'sample'X에서 임의로 k개 관측값을 선택합니다.
'uniform'X 범위에서 임의로 균등하게 k개 점을 선택합니다. 해밍 거리에는 유효하지 않습니다.
숫자형 행렬중심 시작 위치로 구성된 kxp 행렬입니다. Start의 행은 시드값에 대응됩니다. 소프트웨어는 Start의 첫 번째 차원에서 k를 추론하므로 k에 대해 []을 전달할 수 있습니다.
숫자형 배열중심 시작 위치로 구성된 kxpxr 배열입니다. 각 페이지의 행은 시드값에 대응됩니다. 세 번째 차원은 군집화 루틴의 반복 실험을 호출합니다. 페이지 j는 반복 실험 j에 대한 시드값 세트를 포함합니다. 소프트웨어는 세 번째 차원의 크기에서 반복 실험의 횟수('Replicates' 이름-값 쌍의 인수로 지정됨)를 알아냅니다.

예: 'Start','sample'

데이터형: char | string | double | single

참고

소프트웨어는 NaN을 누락된 데이터로 처리하고 NaN을 하나 이상 포함하는 X의 행을 모두 제거합니다. X의 행을 제거하면 표본 크기가 줄어듭니다.

출력 인수

모두 축소

군집 인덱스로, 숫자형 열 벡터로 반환됩니다. idx의 행 개수는 X의 행 개수와 동일하고, 각 행은 대응되는 관측값의 군집 할당을 나타냅니다.

군집 중심 위치로, 숫자형 행렬로 반환됩니다. Ckxp 행렬이고, 여기서 행 j는 군집 j의 중심입니다.

점-중심 간 거리의 군집 내 합으로, 숫자형 열 벡터로 반환됩니다. sumdkx1 벡터이고, 여기서 요소 j는 군집 j 내 점-중심 간 거리의 합입니다.

각 점에서 모든 중심까지의 거리로, 숫자형 행렬로 반환됩니다. D는 nxk 행렬이고, 여기서 요소(j,m)는 관측값 j에서 중심 m까지의 거리입니다.

세부 정보

모두 축소

k-평균 군집화

k-평균 군집화, 즉 로이드의 알고리즘(Lloyd’s Algorithm) [2]은 n개의 관측값을 중심에서 정의된 k개 군집 중 정확히 하나에 할당하는 반복 데이터 분할 알고리즘입니다. 여기서 k는 알고리즘이 시작되기 전에 선택됩니다.

이 알고리즘은 다음과 같이 진행됩니다.

  1. k개 초기 군집 중심(중심)을 선택합니다. 예를 들어, k개 관측값을 임의로 선택하거나('Start','sample' 사용) 군집 중심 초기화에 k-평균 ++ 알고리즘을 사용합니다(디폴트 값).

  2. 각 중심에 대한 모든 관측값의 점-군집 중심 간 거리를 계산합니다.

  3. 여기에는 두 가지 진행 방법이 있습니다(OnlinePhase로 지정됨).

    • 일괄 업데이트 — 각 관측값을 가장 가까운 중심이 있는 군집에 할당합니다.

    • 온라인 업데이트 — 재할당 시 점-군집 중심 간 거리의 군집 내 제곱 합이 줄어드는 경우 관측값을 다른 중심에 개별적으로 할당합니다.

    자세한 내용은 알고리즘 항목을 참조하십시오.

  4. 각 군집에 포함된 관측값의 평균을 계산하여 k개의 새 중심 위치를 구합니다.

  5. 군집 할당이 변경되지 않거나 최대 반복 횟수에 도달할 때까지 2단계~4단계를 반복합니다.

k-평균++ 알고리즘

k-평균++ 알고리즘은 발견적(heuristic) 방식을 사용하여 k-평균 군집화에 사용할 중심 시드값을 구합니다. 아서(Arthur)와 바실비츠키(Vassilvitskii) [1]에 따르면 k-평균++는 로이드의 알고리즘의 실행 시간과 최종 해의 품질을 향상시킵니다.

k-평균++ 알고리즘은 군집 개수를 k라고 가정하고 다음과 같이 시드값을 선택합니다.

  1. 데이터 세트 X에서 임의로 균등하게 관측값을 선택합니다. 선택된 관측값은 첫 번째 중심이며 c1로 표시됩니다.

  2. 각 관측값에서 c1까지의 거리를 계산합니다. cj와 관측값 m 간의 거리를 d(xm,cj)로 나타냅니다.

  3. 다음과 같은 확률로 X에서 임의로 다음 중심 c2를 선택합니다.

    d2(xm,c1)j=1nd2(xj,c1).

  4. 다음을 수행하여 중심 j를 선택합니다.

    1. 각 관측값에서 각 중심까지의 거리를 계산하고 각 관측값을 가장 가까운 중심에 할당합니다.

    2. m = 1,...,n 및 p = 1,...,j – 1에 대해 다음 확률로 X에서 임의로 중심 j를 선택합니다.

      d2(xm,cp){h;xhCp}d2(xh,cp),

      여기서 Cp는 중심 cp에 가장 가까운 모든 관측값을 포함하는 세트이고 xm은 Cp에 속합니다.

      즉, 이미 선택한 가장 가까운 중심과의 거리에 비례하는 확률로 각 후속 중심을 선택합니다.

  5. k개 중심이 선택될 때까지 4번째 단계를 반복합니다.

아서(Arthur)와 바실비츠키(Vassilvitskii) [1]는 여러 군집 방향에 대한 시뮬레이션 연구를 사용하여 k-평균++가 로이드의 알고리즘보다 더 낮은, 점-군집 중심 간 거리의 군집 내 제곱 합으로 더 신속하게 수렴된다는 것을 입증했습니다.

알고리즘

  • kmeans는 두 단계의 반복 알고리즘을 사용하여 모든 k개 군집에 대해 합한 점-중심 간 거리의 합을 최소화합니다.

    1. 이 첫 번째 단계는 각 반복에서 가장 가까운 군집 중심으로 점을 한 번에 재할당한 후 군집 중심을 재계산하는 일괄 업데이트를 사용합니다. 이 단계는 경우에 따라 국소 최솟값으로 해가 수렴되지 않습니다. 즉, 단일 점을 다른 군집으로 이동할 경우 거리의 총합이 증가하는 데이터의 분할이 이에 해당합니다. 이는 작은 데이터 세트에서 발생할 가능성이 더 큽니다. 일괄 단계는 빠르지만, 잠재적으로 두 번째 단계의 시작점으로만 해의 근삿값을 구합니다.

    2. 이 두 번째 단계는 점을 재할당 때 거리의 합이 줄어드는 경우 점을 개별적으로 재할당하고 재할당이 수행된 후마다 군집 중심을 재계산하는 온라인 업데이트를 사용합니다. 이 단계 동안 수행되는 각 반복마다 모든 점을 한 번씩 거칩니다. 이 단계는 국소 최솟값으로 수렴됩니다. 하지만 거리 총합이 더 낮은 다른 국소 최솟값이 있을 수 있습니다. 일반적으로 전역 최솟값은 모든 점을 시작점으로 빠짐없이 선택하면 구해지지만, 보통은 임의의 시작점들을 사용해 수차례 반복 실험하는 것만으로도 전역 최솟값이 구해집니다.

  • Replicates = r > 1이고 Startplus(디폴트 값)이면 소프트웨어가 k-평균++ 알고리즘에 따라 시드값으로 구성된 r개의 가능한 다른 세트를 선택합니다.

  • Options에서 UseParallel 옵션을 활성화하고 Replicates > 1이면 각 워커가 시드값과 군집을 병렬로 선택합니다.

참고 문헌

[1] Arthur, David, and Sergi Vassilvitskii. “K-means++: The Advantages of Careful Seeding.” SODA ‘07: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. 2007, pp. 1027–1035.

[2] Lloyd, Stuart P. “Least Squares Quantization in PCM.” IEEE Transactions on Information Theory. Vol. 28, 1982, pp. 129–137.

[3] Seber, G. A. F. Multivariate Observations. Hoboken, NJ: John Wiley & Sons, Inc., 1984.

[4] Spath, H. Cluster Dissection and Analysis: Theory, FORTRAN Programs, Examples. Translated by J. Goldschmidt. New York: Halsted Press, 1985.

확장 기능

R2006a 이전에 개발됨