dbscan

잡음이 있는 응용 사례의 밀도 기반 공간 군집화(DBSCAN)

페이지 내 모두 축소

구문

idx = dbscan(X,epsilon,minpts)
idx = dbscan(X,epsilon,minpts,Name,Value)
idx = dbscan(D,epsilon,minpts,'Distance','precomputed')
[idx,corepts] = dbscan(___)

설명

idx = dbscan(X,epsilon,minpts)는 DBSCAN 알고리즘(알고리즘 참조)을 사용하여 n×p 데이터 행렬 X의 관측값을 군집으로 분할합니다. dbscan은 이웃 탐색 반경 epsilon에 대한 임계값과 핵심점을 식별하기 위해 필요한 최소 이웃 개수 minpts를 기준으로 관측값(점)을 군집화합니다. 이 함수는 각 관측값의 군집 인덱스를 포함하는 n×1 벡터(idx)를 반환합니다.

예제

idx = dbscan(X,epsilon,minpts,Name,Value)는 하나 이상의 이름-값 쌍의 인수를 사용하여 옵션을 추가로 지정합니다. 예를 들어, 'Distance','minkowski','P',3을 지정하면 DBSCAN 알고리즘에서 지수가 3인 민코프스키 거리 측정법을 사용할 수 있습니다.

예제

idx = dbscan(D,epsilon,minpts,'Distance','precomputed')는 관측값 간의 미리 계산된 쌍별 거리 D에 대한 군집 인덱스의 벡터를 반환합니다. D는 pdist 또는 pdist2의 출력값이거나, 각각 pdist 또는 pdist2의 출력값 형식을 따르는 더 일반적인 비유사성 벡터 또는 행렬일 수 있습니다.

예제

[idx,corepts] = dbscan(___)은 위에 열거된 구문에 나와 있는 입력 인수 조합을 사용하여 dbscan에 의해 식별된 핵심점을 포함하는 논리 벡터 corepts도 반환합니다.

예제

예제

모두 축소

라이브 스크립트 열기

DBSCAN을 디폴트 유클리드 거리 측정법과 함께 사용하여 2차원 원형 데이터 세트를 군집화합니다. 또한 이 데이터 세트를 DBSCAN과 제곱 유클리드 거리 측정법을 사용하여 군집화한 결과와, k-평균 군집화와 제곱 유클리드 거리 측정법을 사용하여 군집화한 결과를 비교합니다.

두 개의 잡음 있는 원을 포함하는 합성 데이터를 생성합니다.

rng('default') % For reproducibility

% Parameters for data generation
N = 300;  % Size of each cluster
r1 = 0.5; % Radius of first circle
r2 = 5;   % Radius of second circle
theta = linspace(0,2*pi,N)';

X1 = r1*[cos(theta),sin(theta)]+ rand(N,1); 
X2 = r2*[cos(theta),sin(theta)]+ rand(N,1);
X = [X1;X2]; % Noisy 2-D circular data set

데이터 세트를 시각화합니다.

scatter(X(:,1),X(:,2))

Figure contains an axes object. The axes object contains an object of type scatter.

이 플롯은 데이터 세트에 2개의 고유한 군집이 포함되어 있음을 나타냅니다.

데이터에 대해 DBSCAN 군집화를 수행합니다. epsilon 값을 1로 지정하고 minpts 값을 5로 지정합니다.

idx = dbscan(X,1,5); % The default distance metric is Euclidean distance

군집화를 시각화합니다.

gscatter(X(:,1),X(:,2),idx);
title('DBSCAN Using Euclidean Distance Metric')

Figure contains an axes object. The axes object with title DBSCAN Using Euclidean Distance Metric contains 2 objects of type line. One or more of the lines displays its values using only markers These objects represent 1, 2.

DBSCAN은 유클리드 거리 측정법을 사용하여 데이터 세트에서 2개의 군집을 올바르게 식별합니다.

제곱 유클리드 거리 측정법을 사용하여 DBSCAN 군집화를 수행합니다. epsilon 값을 1로 지정하고 minpts 값을 5로 지정합니다.

idx2 = dbscan(X,1,5,'Distance','squaredeuclidean');

군집화를 시각화합니다.

gscatter(X(:,1),X(:,2),idx2);
title('DBSCAN Using Squared Euclidean Distance Metric')

Figure contains an axes object. The axes object with title DBSCAN Using Squared Euclidean Distance Metric contains 2 objects of type line. One or more of the lines displays its values using only markers These objects represent 1, 2.

DBSCAN은 제곱 유클리드 거리 측정법을 사용하여 데이터 세트에서 2개의 군집을 올바르게 식별합니다.

제곱 유클리드 거리 측정법을 사용하여 k-평균 군집화를 수행합니다. k = 2로 군집 개수를 지정합니다.

kidx = kmeans(X,2); % The default distance metric is squared Euclidean distance

군집화를 시각화합니다.

gscatter(X(:,1),X(:,2),kidx);
title('K-Means Using Squared Euclidean Distance Metric')

Figure contains an axes object. The axes object with title K-Means Using Squared Euclidean Distance Metric contains 2 objects of type line. One or more of the lines displays its values using only markers These objects represent 1, 2.

k-평균 군집화는 제곱 유클리드 거리 측정법을 사용하면 데이터 세트에서 2개의 군집을 올바르게 식별하지 못합니다.

라이브 스크립트 열기

관측값 간의 쌍별 거리 행렬을 dbscan 함수의 입력값으로 사용하여 DBSCAN 군집화를 수행하고 이상값과 핵심점의 개수를 찾습니다. 데이터 세트는 차량 주변 물체의 좌표를 포함하는 라이다 스캔(3차원 점의 집합으로 저장됨)입니다.

물체의 x, y, z 좌표를 불러옵니다.

load('lidar_subset.mat') 
loc = lidar_subset;

차량 주위의 환경을 강조 표시하기 위해 관심 영역을 차량의 왼쪽과 오른쪽에 20m 및 차량의 앞과 뒤에 20m 간격을 갖는 도로의 표면 위 영역으로 설정합니다.

xBound = 20; % in meters
yBound = 20; % in meters
zLowerBound = 0; % in meters

데이터를 지정된 영역 내의 점만 포함하도록 자릅니다.

indices = loc(:,1) <= xBound & loc(:,1) >= -xBound ...
    & loc(:,2) <= yBound & loc(:,2) >= -yBound ...
    & loc(:,3) > zLowerBound;
loc = loc(indices,:);

데이터를 2차원 산점도 플롯으로 시각화합니다. 차량을 강조 표시하기 위해, 플롯에 주석을 추가합니다.

scatter(loc(:,1),loc(:,2),'.');
annotation('ellipse',[0.48 0.48 .1 .1],'Color','red')

Figure contains an axes object. The axes object contains an object of type scatter.

점 집합(빨간색 원)의 중심에는 차량의 지붕과 후드가 있습니다. 그 외 모든 점은 장애물입니다.

pdist2 함수를 사용하여 관측값 간의 쌍별 거리 행렬 D를 미리 계산합니다.

D = pdist2(loc,loc);

쌍별 거리와 함께 dbscan을 사용하여 데이터를 군집화합니다. epsilon 값을 2로 지정하고 minpts 값을 50으로 지정합니다.

[idx, corepts] = dbscan(D,2,50,'Distance','precomputed');

결과를 시각화하고 특정 군집을 강조 표시하기 위해 그림에 주석을 추가합니다.

numGroups = length(unique(idx));
gscatter(loc(:,1),loc(:,2),idx,hsv(numGroups));
annotation('ellipse',[0.54 0.41 .07 .07],'Color','red')
grid

Figure contains an axes object. The axes object contains 12 objects of type line. One or more of the lines displays its values using only markers These objects represent -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11.

산점도에서 볼 수 있듯이, dbscan은 11개의 군집을 식별하고 차량을 별도의 군집에 배치합니다.

dbscan이 빨간 원 안의 점 그룹(3,–4 중심)을 플롯의 남동쪽 사분면에 있는 점 그룹과 동일한 군집(그룹 7)에 할당했습니다. 원래 기대한 것은 이들 그룹이 서로 다른 군집에 배치되는 것이었습니다. 큰 군집을 나누고 점들을 더 세분화하려면 더 작은 epsilon 값을 사용해 볼 수 있습니다.

이 함수는 또한 데이터에서 일부 이상값(idx 값이 –1인 경우)을 식별합니다. dbscan이 이상값으로 식별하는 점의 개수를 구합니다.

sum(idx == -1)
ans = 
412

dbscan은 19,070개의 관측값 중 412개를 이상값으로 식별합니다.

dbscan이 핵심점으로 식별하는 점의 개수를 구합니다. corepts 값이 1이면 핵심점을 나타냅니다.

sum(corepts == 1)
ans = 
18446

dbscan은 18,446개의 관측값을 핵심점으로 식별합니다.

예제를 더 보려면 Determine Values for DBSCAN Parameters 항목을 참조하십시오.

입력 인수

모두 축소

입력 데이터로, n×p 숫자형 행렬로 지정됩니다. X의 행은 관측값(점)에 대응되고, 열은 변수에 대응됩니다.

데이터형: single | double

관측값 간 쌍별 거리로, pdist의 출력값인 숫자형 행 벡터, pdist2의 출력값인 숫자형 정사각 행렬, 논리형 행 벡터 또는 논리형 정사각 행렬로 지정됩니다. 또한 D는 각각 pdist 또는 pdist2의 출력값 형식을 따르는 더 일반적인 비유사성 벡터 또는 행렬일 수 있습니다.

앞서 언급한 지정 형식에 대해, 다음 표는 n개의 관측값(행)과 p개의 차원(열)을 갖는 입력 행렬 X가 주어졌을 때 D가 취할 수 있는 형식을 설명합니다.

지정형식
숫자형 행 벡터(pdist(X)의 출력값)

  • X의 관측값 쌍에 대응되는, 길이가 n(n – 1)/2인 행 벡터

  • (2,1), (3,1), ..., (n,1), (3,2), ..., (n,2), ..., (n,n – 1)) 순서로 정렬된 거리

숫자형 정사각 행렬(pdist2(X,X)의 출력)

  • n×n 행렬로, 여기서 D(i,j)는 X의 관측값 i와 관측값 j 간 거리입니다.

  • 대각 요소가 0인 대칭 행렬

논리형 행 벡터

  • X의 관측값 쌍에 대응되는, 길이가 n(n – 1)/2인 행 벡터

  • 각 요소가 epsilon보다 작거나 같은 거리를 나타내는 논리형 행 벡터

  • (2,1), (3,1), ..., (n,1), (3,2), ..., (n,2), ..., (n,n – 1)) 순서로 정렬된 D의 요소

논리형 정사각 행렬

  • n×n 행렬로, 여기서 D(i,j)는 X의 관측값 i와 관측값 j 간 거리가 epsilon보다 작거나 같은지를 나타냅니다.

참고

D가 논리형 벡터 또는 행렬인 경우 epsilon의 값은 비어 있어야 합니다(예: dbscan(D,[],5,'Distance','precomputed')).

데이터형: single | double | logical

점의 엡실론 이웃으로, 점 주변의 이웃 탐색 반경을 정의하는 숫자형 스칼라로 지정됩니다. 점의 엡실론 이웃에 최소한 minpts개 이웃이 포함되어 있으면 dbscan은 해당 점을 핵심점으로 식별합니다.

D가 논리형 벡터 또는 행렬인 경우 epsilon의 값은 비어 있어야 합니다([]).

예: dbscan(X,2.5,10)

예: 논리형 행렬 또는 벡터 D인 경우 dbscan(D,[],5,'Distance','precomputed')

데이터형: single | double

핵심점에 필요한 최소 이웃 개수로, 양의 정수로 지정됩니다. 군집에서 핵심점의 엡실론 이웃은 최소한 minpts개의 이웃을 포함해야 하는 반면, 경계점의 엡실론 이웃은 minpts보다 적은 수의 이웃을 포함할 수 있습니다.

예: dbscan(X,2.5,5)

데이터형: single | double

이름-값 인수

모두 축소

선택적 인수 쌍을 Name1=Value1,...,NameN=ValueN으로 지정합니다. 여기서 Name은 인수 이름이고 Value는 대응값입니다. 이름-값 인수는 다른 인수 뒤에 와야 하지만, 인수 쌍의 순서는 상관없습니다.

R2021a 이전 릴리스에서는 쉼표를 사용하여 각 이름과 값을 구분하고 Name을 따옴표로 묶으십시오.

예: dbscan(D,2.5,5,'Distance','precomputed')는 관측값 간 쌍별 거리가 미리 계산된 행렬 D, 엡실론 이웃 2.5, 최소 이웃 개수 5를 사용하는 DBSCAN 군집화를 지정합니다.

거리 측정법으로, 다음 표에 설명된 대로 'Distance'와 함께 문자형 벡터, string형 스칼라 또는 함수 핸들이 쉼표로 구분되어 지정됩니다.

값설명
'precomputed'

미리 계산된 거리입니다. dbscan의 첫 번째 입력값이 쌍별 거리 벡터 또는 행렬 D인 경우 이 옵션을 지정해야 합니다.

'euclidean'

유클리드 거리(디폴트 값)

'squaredeuclidean'

제곱 유클리드 거리입니다. (이 옵션은 효율성을 위해서만 제공됩니다. 삼각 부등식을 충족하지 않습니다.)

'seuclidean'

표준화된 유클리드 거리입니다. 관측값 간의 각 좌표 차이는 표준편차 S = std(X,'omitnan')의 대응 요소로 나누어져 스케일링됩니다. S에 다른 값을 지정하려면 Scale을 사용하십시오.

'mahalanobis'

마할라노비스 거리로, X의 표본 공분산 C = cov(X,'omitrows')를 사용하여 계산됩니다. C에 다른 값을 지정하려면 Cov를 사용하십시오. 여기서 행렬 C는 양의 정부호 대칭 행렬입니다.

'cityblock'

도시 블록 거리

'minkowski'

민코프스키 거리입니다. 디폴트 지수는 2입니다. 다른 지수를 지정하려면 P를 사용하십시오. 여기서 P는 양의 스칼라 값입니다.

'chebychev'

체비쇼프 거리(최대 좌표 차이)

'cosine'

1에서 점 간의 끼인각에 대한 코사인을 뺀 값(벡터로 처리됨)

'correlation'

1에서 점 간의 표본 상관을 뺀 값(일련의 값으로 처리됨)

'hamming'

해밍 거리로, 서로 다른 좌표의 비율

'jaccard'

0이 아닌 두 좌표의 값이 서로 다른 비율인 자카드 계수를 1에서 뺀 값

'spearman'

1에서 관측값 간 표본 스피어만의 순위 상관 계수를 뺀 값(일련의 값으로 처리됨)

@distfun

사용자 지정 거리 함수 핸들입니다. 거리 함수의 형식은 다음과 같습니다.

function D2 = distfun(ZI,ZJ)
% calculation of distance
...
여기서

  • ZI는 단일 관측값을 포함하는 1×n 벡터입니다.

  • ZJ는 여러 관측값을 포함하는 m2×n 행렬입니다. distfun은 임의 개수의 관측값을 갖는 행렬 ZJ를 받아야 합니다.

  • D2는 거리로 구성된 m2×1 벡터이고, D2(k)는 관측값 ZI와 ZJ(k,:) 간의 거리입니다.

데이터가 희소 형식이 아닌 경우 일반적으로 함수 핸들 대신 내장 거리를 사용하면 더 빠르게 거리를 계산할 수 있습니다.

정의는 거리 측정법 항목을 참조하십시오.

'seuclidean', 'minkowski' 또는 'mahalanobis' 거리 측정법을 사용하는 경우 이름-값 쌍 인수 'Scale', 'P' 또는 'Cov'를 각각 추가로 지정하여 거리 측정법을 제어할 수 있습니다.

예: dbscan(X,2.5,5,'Distance','minkowski','P',3)은 군집화 알고리즘을 수행할 때 엡실론 이웃을 2.5로, 군집을 확장시키기 위한 최소 이웃 개수를 5로 지정하며, 지수가 3인 민코프스키 거리 측정법을 사용하도록 지정합니다.

민코프스키 거리 측정법에 대한 지수로, 'P'와 함께 양의 스칼라가 쉼표로 구분되어 지정됩니다.

이 인수는 'Distance'가 'minkowski'인 경우에만 유효합니다.

예: 'P',3

데이터형: single | double

마할라노비스 거리 측정법에 대한 공분산 행렬로, 'Cov'와 함께 양의 정부호 숫자형 대칭 행렬이 쉼표로 구분되어 지정됩니다.

이 인수는 'Distance'가 'mahalanobis'인 경우에만 유효합니다.

데이터형: single | double

표준화된 유클리드 거리 측정법에 대한 스케일링 인자로, 'Scale'과 함께 양수 값의 숫자형 벡터가 쉼표로 구분되어 지정됩니다.

X의 각 차원(열)은 'Scale'의 대응값을 갖습니다. 따라서 'Scale'의 길이는 p(X의 열 개수)입니다. dbscan은 X의 각 차원에 대해 'Scale'의 대응값을 사용하여 X와 쿼리 점 간의 차이를 표준화합니다.

이 인수는 'Distance'가 'seuclidean'인 경우에만 유효합니다.

데이터형: single | double

출력 인수

모두 축소

군집 인덱스로, 숫자형 열 벡터로 반환됩니다. idx의 행은 n개이고, idx의 각 행은 X의 대응 관측값의 군집 할당을 나타냅니다. 인덱스 –1은 이상값(또는 잡음점)을 나타냅니다.

참고

DBSCAN 알고리즘을 사용한 군집 할당은 관측값 순서에 따라 달라집니다. 따라서 X의 행을 섞으면 관측값에 대한 군집 할당이 달라질 수 있습니다. 자세한 내용은 알고리즘 항목을 참조하십시오.

데이터형: double

핵심점을 나타내는 표시자로, dbscan에 의해 식별된 핵심점의 인덱스를 나타내는 n×1 논리형 벡터로 반환됩니다. corepts의 행에 있는 값 1은 X의 대응 관측값이 핵심점임을 나타냅니다. 그렇지 않은 경우 corepts는 핵심점이 아닌 관측값에 대응되는 행에 대해 0 값을 갖습니다.

데이터형: logical

세부 정보

모두 축소

팁

  • 다수의 epsilon 값을 반복 처리할 때 속도를 높이려면 D를 dbscan의 입력값으로 전달해 보십시오. 이 방식을 사용하면 함수가 반복의 모든 점에서 거리를 계산할 필요가 없습니다.

  • pdist2를 사용하여 D를 미리 계산하는 경우, pdist2의 'Smallest' 또는 'Largest' 이름-값 쌍 인수를 지정하여 D의 열을 선택하거나 정렬하지 마십시오. dbscan은 D가 정사각 행렬이어야 하기 때문에 n개보다 적은 거리를 선택하면 오류가 발생합니다. D의 각 열에서 거리를 정렬하면 D의 해석에 손실이 발생하고 dbscan 함수에서 사용할 경우 의미 없는 결과가 나올 수 있습니다.

  • 효율적인 메모리 사용을 위해, D가 클 경우에는 D를 숫자형 행렬이 아닌 논리형 행렬로 dbscan에 전달해 보십시오. 기본적으로, MATLAB®은 숫자형 행렬의 각 값은 8바이트(64비트)를 사용하여 저장하고, 논리형 행렬의 각 값은 1바이트(8비트)를 사용하여 저장합니다.

  • minpts의 값을 선택하려면 입력 데이터의 차원 수에 1을 더한 것보다 크거나 같은 값을 고려하십시오[1]. 예를 들어, n×p 행렬 X의 경우 'minpts'를 p+1과 같거나 더 큰 값을 설정합니다.

  • epsilon의 값을 선택할 때 가능한 한 가지 전략은 X에 대한 k-거리 그래프를 생성하는 것입니다. X의 각 점에 대해 k번째로 가까운 점까지의 거리를 구하고, 정렬된 점을 이 거리에 따라 플로팅합니다. 일반적으로 그래프에는 무릎(knee)이 포함됩니다. 무릎에 해당하는 거리는 점이 이상값(잡음) 영역으로 벗어나기 시작하는 영역이기 때문에 일반적으로 epsilon으로 선택하는 데 적합합니다[1].

알고리즘

  • DBSCAN은 데이터에서 군집과 잡음을 발견하도록 설계된 밀도 기반 군집화 알고리즘입니다. 알고리즘은 핵심점, 경계점, 잡음점이라는 세 종류의 점을 식별합니다[1]. dbscan 함수는 epsilon 및 minpts에 지정된 값에 따라 다음과 같이 알고리즘을 구현합니다.

    1. 입력 데이터 세트 X에서 첫 번째 레이블이 없는 관측값 x1을 현재 점으로 선택하고, 첫 번째 군집 레이블 C를 1로 초기화합니다.

    2. 현재 점의 엡실론 이웃 epsilon 내에 있는 점 집합을 구합니다. 이 점들이 이웃입니다.

      1. 이웃 개수가 minpts보다 적으면 현재 점을 잡음점(또는 이상값)으로 레이블 지정합니다. 4단계로 이동합니다.

        참고

        dbscan은 나중에 잡음점이 X의 다른 점에서 epsilon과 minpts로 설정된 제약 조건을 충족하면, 해당 잡음점을 군집에 재할당할 수 있습니다. 이렇게 점을 재할당하는 과정은 군집의 경계점에서 발생합니다.

      2. 그렇지 않으면, 현재 점을 군집 C에 속하는 핵심점으로 레이블 지정합니다.

    3. 각 이웃(새로운 현재 점)에 대해 반복 처리하고, 현재 군집 C에 속한다고 레이블 지정할 수 있는 새로운 이웃이 더 이상 발견되지 않을 때까지 2단계를 반복합니다.

    4. X에서 레이블 지정되어 있지 않는 다음 점을 현재 점으로 선택하고 군집 개수를 1만큼 늘립니다.

    5. X의 모든 점이 레이블 지정될 때까지 2~4단계를 반복합니다.

  • 두 군집이 서로 다른 밀도를 가지면서 가까이 있는 경우, 즉 두 경계점(각 군집에서 하나씩) 사이의 거리가 epsilon보다 작으면 dbscan은 두 군집을 하나로 병합할 수 있습니다.

  • 모든 유효한 군집이 언제나 최소 minpts개의 관측값을 포함하는 것은 아닙니다. 예를 들어, dbscan은 가까이 있는 두 군집에 속한 경계점을 식별할 수 있습니다. 이런 상황에서 알고리즘은 첫 번째로 발견된 군집에 경계점을 할당합니다. 결과적으로 두 번째 군집은 여전히 유효한 군집이지만, minpts개보다 적은 관측값을 가질 수 있습니다.

참고 문헌

[1] Ester, M., H.-P. Kriegel, J. Sander, and X. Xiaowei. “A density-based algorithm for discovering clusters in large spatial databases with noise.” In Proceedings of the Second International Conference on Knowledge Discovery in Databases and Data Mining, 226-231. Portland, OR: AAAI Press, 1996.

확장 기능

모두 확장

버전 내역

R2019a에 개발됨

참고 항목

| | | | |

도움말 항목

외부 웹사이트