Main Content

이 번역 페이지는 최신 내용을 담고 있지 않습니다. 최신 내용을 영문으로 보려면 여기를 클릭하십시오.

knnsearch

입력 데이터를 사용하여 k-최근접이웃 찾기

설명

예제

Idx = knnsearch(X,Y)Y의 각 쿼리 점에 대해 X에서 최근접이웃을 찾은 후 Idx 열 벡터로 최근접이웃의 인덱스를 반환합니다. Idx의 행 개수는 Y와 같습니다.

예제

Idx = knnsearch(X,Y,Name,Value)는 하나 이상의 이름-값 쌍의 인수를 추가적으로 옵션으로 지정해 Idx를 반환합니다. 예를 들어, 탐색할 최근접이웃의 개수와 탐색에 사용되는 거리 측정법을 지정할 수 있습니다.

예제

[Idx,D] = knnsearch(___)는 위에 열거된 구문의 입력 인수를 사용하여 행렬 D를 추가로 반환합니다. DY의 각 관측값과 X에서 이에 대응되는 가장 가까운 관측값 간의 거리를 포함합니다.

예제

모두 축소

hospital 데이터 세트에서 연령과 체중을 기준으로 Y의 환자와 가장 유사한 환자를 찾습니다.

hospital 데이터 세트를 불러옵니다.

load hospital;
X = [hospital.Age hospital.Weight];
Y = [20 162; 30 169; 40 168; 50 170; 60 171];   % New patients

XY 간에 knnsearch를 수행하여 최근접이웃의 인덱스를 찾습니다.

Idx = knnsearch(X,Y);

X에서 연령과 체중을 기준으로 Y의 환자와 가장 근접한 환자를 찾습니다.

X(Idx,:)
ans = 5×2

    25   171
    25   171
    39   164
    49   170
    50   172

Y의 각 점에 가장 근접한 10개의 최근접이웃을 X에서 찾되, 먼저 민코프스키(Minkowski) 거리 측정법을 사용하여 찾아본 후 체비쇼프(Chebychev) 거리 측정법을 사용하여 찾아보겠습니다.

피셔(Fisher)의 붓꽃 데이터 세트를 불러옵니다.

load fisheriris
X = meas(:,3:4);    % Measurements of original flowers
Y = [5 1.45;6 2;2.75 .75];  % New flower data

민코프스키 거리 측정법과 체비쇼프 거리 측정법을 사용하여 X와 쿼리 점 Y 간에 knnsearch를 수행합니다.

[mIdx,mD] = knnsearch(X,Y,'K',10,'Distance','minkowski','P',5);
[cIdx,cD] = knnsearch(X,Y,'K',10,'Distance','chebychev');

두 개의 최근접이웃 탐색 결과를 시각화합니다. 훈련 데이터를 플로팅합니다. 마커 X로 쿼리 점을 플로팅합니다. 원을 사용하여 민코프스키 최근접이웃을 표시합니다. 펜타그램을 사용하여 체비쇼프 최근접이웃을 표시합니다.

gscatter(X(:,1),X(:,2),species)
line(Y(:,1),Y(:,2),'Marker','x','Color','k',...
   'Markersize',10,'Linewidth',2,'Linestyle','none')
line(X(mIdx,1),X(mIdx,2),'Color',[.5 .5 .5],'Marker','o',...
   'Linestyle','none','Markersize',10)
line(X(cIdx,1),X(cIdx,2),'Color',[.5 .5 .5],'Marker','p',...
   'Linestyle','none','Markersize',10)
legend('setosa','versicolor','virginica','query point',...
'minkowski','chebychev','Location','best')

Figure contains an axes object. The axes object contains 6 objects of type line. One or more of the lines displays its values using only markers These objects represent setosa, versicolor, virginica, query point, minkowski, chebychev.

2개의 큰 점 행렬을 만든 다음 knnsearch가 디폴트 "euclidean" 거리 측정법을 사용하여 실행에 소요한 시간을 측정합니다.

rng default % For reproducibility
N = 10000;
X = randn(N,1000);
Y = randn(N,1000);
Idx = knnsearch(X,Y); % Warm up function for more reliable timing information
tic
Idx = knnsearch(X,Y);
standard = toc
standard = 15.0846

다음으로, knnsearch"fasteuclidean" 거리 측정법을 사용하여 실행에 소요한 시간을 측정합니다. 캐시 크기를 100으로 지정합니다.

Idx2 = knnsearch(X,Y,Distance="fasteuclidean",CacheSize=100); % Warm up function
tic
Idx2 = knnsearch(X,Y,Distance="fasteuclidean",CacheSize=100);
accelerated = toc
accelerated = 2.3400

가속화된 계산이 표준과 비교하여 몇 배 더 빠른지 평가합니다.

standard/accelerated
ans = 6.4465

이 예제의 경우 가속화된 버전은 3배 이상 빠릅니다.

입력 인수

모두 축소

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

데이터형: single | double

쿼리 점으로, 숫자형 행렬로 지정됩니다. Y의 행은 관측값에 대응되고, 열은 변수에 대응됩니다. YX와 같은 개수의 열을 가져야 합니다.

데이터형: single | double

이름-값 인수

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

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

예: knnsearch(X,Y,'K',10,'IncludeTies',true,'Distance','cityblock')은 도시 블록 거리를 사용하여, 동순위를 포함하여 10개의 최근접이웃을 탐색합니다.

Y의 각 점에 대해 X에서 찾을 최근접이웃의 개수로, 'K'와 함께 양의 정수가 쉼표로 구분되어 지정됩니다.

예: 'K',10

데이터형: single | double

쿼리 점으로부터의 거리가 같은 모든 최근접이웃을 포함할지 여부를 나타내는 플래그로, 'IncludeTies'와 함께 false(0) 또는 true(1)가 쉼표로 구분되어 지정됩니다.

'IncludeTies'false인 경우, knnsearch는 쿼리 점으로부터의 거리가 같은 관측값 중에서 인덱스가 가장 작은 관측값을 선택합니다.

'IncludeTies'true이면 다음과 같습니다.

  • knnsearch에 출력 인수에서 k번째로 작은 거리와 거리가 같은 모든 최근접이웃이 포함됩니다. k를 지정하려면 'K' 이름-값 쌍의 인수를 사용하십시오.

  • IdxD는 m×1 크기의 셀형 배열이며 각각의 셀은 최소 k개의 인덱스와 거리로 구성된 벡터를 포함합니다. D의 각 벡터는 거리 값을 오름차순으로 정렬해 담고 있습니다. Idx의 각 행은 D의 거리에 대응되는 최근접이웃에 대한 인덱스를 포함합니다.

예: 'IncludeTies',true

최근접이웃 탐색 방법으로, 'NSMethod'와 함께 다음 값 중 하나가 쉼표로 구분되어 지정됩니다.

  • 'kdtree' — Kd-트리를 생성하고 사용하여 최근접이웃을 찾습니다. 'kdtree'X의 열 개수가 10보다 작거나 같고, X가 희소 행렬이 아니며, 거리 측정법이 'euclidean', 'cityblock', 'chebychev' 또는 'minkowski'인 경우 디폴트 값입니다. 그렇지 않은 경우 디폴트 값은 'exhaustive'입니다.

    'kdtree'는 거리 측정법이 위에 표시된 네 가지 측정법 중 하나인 경우에만 유효합니다.

  • 'exhaustive'X의 모든 점에서 Y의 각 점까지의 거리 값을 계산하는 완전 탐색 알고리즘을 사용합니다.

예: 'NSMethod','exhaustive'

knnsearch가 사용하는 거리 측정법으로, 다음 표에 나와 있는 값 중 하나 또는 함수 핸들로 지정됩니다.

설명
'euclidean'유클리드 거리(Euclidean Distance)
'seuclidean'표준화된 유클리드 거리입니다. X의 행과 쿼리 행렬 Y 간의 좌표 차이는 각각 X에서 계산된 표준편차의 대응 요소로 나누어져 스케일링됩니다. 다른 스케일링을 지정하려면 'Scale' 이름-값 인수를 사용하십시오.
'fasteuclidean'예측 변수 개수가 10개 이상인 경우 시간을 아끼는 대체 알고리즘을 사용하여 계산된 유클리드 거리입니다. 이는 더 빠른 알고리즘이며 경우에 따라 정확도를 떨어뜨릴 수 있습니다. 이 거리 측정법은 NSMethod'exhaustive'인 경우에만 사용할 수 있습니다. 'fast'로 시작하는 알고리즘은 희소 형식 데이터를 지원하지 않습니다. 자세한 내용은 알고리즘 항목을 참조하십시오.
'fastseuclidean'예측 변수 개수가 10개 이상인 경우 시간을 아끼는 대체 알고리즘을 사용하여 계산된 표준화된 유클리드 거리입니다. 이는 더 빠른 알고리즘이며 경우에 따라 정확도를 떨어뜨릴 수 있습니다. 이 거리 측정법은 NSMethod'exhaustive'인 경우에만 사용할 수 있습니다. 'fast'로 시작하는 알고리즘은 희소 형식 데이터를 지원하지 않습니다. 자세한 내용은 알고리즘 항목을 참조하십시오.
'cityblock'도시 블록 거리
'chebychev'체비쇼프 거리(최대 좌표 차이)
'minkowski'민코프스키 거리입니다. 디폴트 지수는 2입니다. 다른 지수를 지정하려면 'P' 이름-값 인수를 사용하십시오.
'mahalanobis'마할라노비스 거리로, 양의 정부호 공분산 행렬을 사용하여 계산됩니다. 공분산 행렬의 값을 변경하려면 'Cov' 이름-값 인수를 사용하십시오.
'cosine'1에서 관측값 간의 끼인각에 대한 코사인을 뺀 값(벡터로 처리됨)
'correlation'1에서 관측값 간의 표본 선형 상관관계를 뺀 값(일련의 값으로 처리됨)
'spearman'1에서 관측값 간 표본 스피어만의 순위 상관 계수를 뺀 값(일련의 값으로 처리됨)
'hamming'해밍 거리로, 서로 다른 좌표의 비율
'jaccard'1에서 서로 다른, 0이 아닌 좌표의 백분율인 자카드 계수를 뺀 값

또한 @을 사용하여(예: @distfun) 사용자 지정 거리 측정법에 대한 함수 핸들을 지정할 수도 있습니다. 사용자 지정 거리 함수는 다음과 같아야 합니다.

  • function D2 = distfun(ZI,ZJ) 형식이어야 합니다.

  • 인수로 다음을 받아야 합니다.

    • X의 단일 행 또는 쿼리 점 Y의 단일 행을 포함하는 1×n 벡터 ZI.

    • X 또는 Y의 여러 행을 포함하는 m2×n 행렬 ZJ.

  • 거리 D2로 구성된 m2×1 벡터를 반환합니다. 여기서 j번째 요소는 관측값 ZIZJ(j,:) 간의 거리입니다.

자세한 내용은 거리 측정법 항목을 참조하십시오.

예: 'Distance','chebychev'

데이터형: char | string | function_handle

메가바이트 단위의 그람 행렬 크기로, 양의 스칼라 또는 "maximal"로 지정됩니다. knnsearch 함수는 Distance 이름-값 인수가 fast로 시작하고 NSMethod 이름-값 인수가 'exhaustive'로 설정된 경우에만 CacheSize를 사용할 수 있습니다.

CacheSize"maximal"로 설정한 경우 knnsearch 함수는 크기가 MX×MY인 중간 행렬 전체에 대해 충분한 메모리를 할당하려고 시도합니다. 여기서 MX는 입력 데이터 X의 행 개수이며, MY는 입력 데이터 Y의 행 개수입니다. 캐시 크기는 중간 행렬 전체를 다 담을 만큼 크지 않아도 되지만 적어도 MX×1 벡터를 유지할 수 있을 만큼은 커야 합니다. 그렇지 않은 경우 knnsearch는 표준 알고리즘을 사용하여 유클리드 거리를 계산합니다.

Distance 인수의 값이 fast로 시작하고 NSMethod의 값이 'exhaustive'이고 CacheSize의 값이 너무 크거나 "maximal"인 경우, knnsearch는 사용 가능한 메모리를 초과하는 그람 행렬을 할당하려고 시도할 수 있습니다. 이 경우, MATLAB®에서 오류를 발생시킵니다.

예: CacheSize="maximal"

데이터형: double | char | string

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

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

예: 'P',3

데이터형: single | double

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

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

예: 'Cov',eye(4)

데이터형: single | double

표준화된 유클리드 거리 측정법에 대한 스케일 모수 값으로, 'Scale'과 함께 음수가 아닌 숫자형 벡터가 쉼표로 구분되어 지정됩니다. 'Scale'의 길이는 X의 열 개수와 같습니다. knnsearch가 표준화된 유클리드 거리를 계산할 때 X의 각 좌표는 각 쿼리 점과 마찬가지로 'Scale'의 대응 요소를 기준으로 스케일링됩니다. 이 인수는 'Distance''seuclidean'인 경우에만 유효합니다.

예: 'Scale',quantile(X,0.75) - quantile(X,0.25)

데이터형: single | double

Kd-트리의 리프 노드에 포함된 데이터 점의 최대 개수로, 'BucketSize'와 함께 양의 정수가 쉼표로 구분되어 지정됩니다. 이 인수는 NSMethod'kdtree'인 경우에만 유효합니다.

예: 'BucketSize',20

데이터형: single | double

반환된 인덱스를 거리에 따라 정렬할지를 나타내는 플래그로, 'SortIndices'와 함께 true(1) 또는 false (0)가 쉼표로 구분되어 지정됩니다.

다음이 참인 경우에는 SortIndicesfalse로 설정하여 속도를 높일 수 있습니다.

  • YX에 최근접이웃이 많이 있는 관측값을 많이 포함합니다.

  • NSMethod'kdtree'입니다.

  • IncludeTiesfalse입니다.

이 경우에 knnsearch는 최근접이웃의 인덱스를 특정한 순서 없이 반환합니다. SortIndicestrue인 경우 함수는 거리를 기준으로 최근접이웃 인덱스를 오름차순으로 정렬합니다.

SortIndices는 기본적으로 true입니다. NSMethod'exhaustive'이거나 IncludeTiestrue인 경우 함수는 항상 인덱스를 정렬합니다.

예: 'SortIndices',false

데이터형: logical

출력 인수

모두 축소

최근접이웃의 입력 데이터 인덱스로, 숫자형 행렬 또는 숫자형 벡터로 구성된 셀형 배열로 반환됩니다.

  • IncludeTies를 지정하지 않은 경우(기본적으로 false임) Idx는 m×k 숫자형 행렬입니다. 여기서 m은 Y의 행 개수이고 k는 탐색된 최근접이웃의 개수입니다. Idx(j,i)X(Idx(j,i),:)X에서 쿼리 점 Y(j,:)까지의 거리가 가장 가까운 k개의 관측값 중 하나임을 나타냅니다.

  • 'IncludeTies',true를 지정하는 경우, Idx는 m×1 셀형 배열이며, 셀 j(Idx{j})는 X에서 쿼리 점 Y(j,:)까지의 거리가 가장 가까운 최소 k개의 관측값에 대한 인덱스로 구성된 벡터를 포함합니다.

SortIndicestrue인 경우 knnsearch는 거리를 기준으로 인덱스를 오름차순으로 정렬합니다.

쿼리 점의 최근접이웃의 거리로, 숫자형 행렬 또는 숫자형 벡터로 구성된 셀형 배열로 반환됩니다.

  • IncludeTies를 지정하지 않는 경우(기본적으로 false임), D는 m×k 숫자형 행렬입니다. 여기서 m은 Y의 행 개수이고 k는 탐색된 최근접이웃의 개수입니다. D(j,i)는 거리 측정법에 따른 X(Idx(j,i),:)Y(j,:) 간의 거리입니다.

  • 'IncludeTies',true를 지정하는 경우, D는 m×1 셀형 배열입니다. 셀 j(D{j})는 X에서 쿼리 점 Y(j,:)까지의 거리가 가장 가까운 최소 k개의 관측값 거리로 구성된 벡터를 포함합니다.

SortIndicestrue인 경우 knnsearch는 거리를 오름차순으로 정렬합니다.

  • 고정된 양의 정수 k에 대해 knnsearch는 X에서 Y의 각 점에 가장 가까운 k개 점을 찾습니다. X에서 Y의 각 점으로부터 일정한 거리 내에 있는 모든 점을 찾으려면 rangesearch를 사용하십시오.

  • knnsearch는 탐색 객체를 저장하지 않습니다. 탐색 객체를 생성하려면 createns를 사용하십시오.

알고리즘

모두 축소

특정 탐색 알고리즘에 대한 자세한 내용은 k-최근접이웃 탐색 및 반지름 탐색 항목을 참조하십시오.

고속 유클리드 거리 알고리즘

fast로 시작하는 Distance 인수의 값(예: 'fasteuclidean''fastseuclidean')은 계산 시간을 아끼기 위해 추가 메모리를 사용하는 알고리즘을 사용해 유클리드 거리를 계산합니다. 이 알고리즘은 Albanie[1] 및 다른 문헌에서 "Euclidean Distance Matrix Trick"이라고 합니다. 내부 테스트에 따르면 이 알고리즘은 예측 변수 개수가 10개 이상인 경우 시간을 아끼는 것으로 나타났습니다. 'fast'로 시작하는 알고리즘은 희소 형식 데이터를 지원하지 않습니다.

각 xi가 n개의 변수를 갖는 모든 점 xi와 xj 간 거리의 행렬 D를 구하기 위해 알고리즘은 다음 수식의 마지막 줄을 사용하여 거리를 계산합니다.

Di,j2=xixj2=(xixj)T(xixj)=xi22xiTxj+xj2.

수식의 마지막 줄에 있는 행렬 xiTxj그람 행렬이라고 합니다. 제곱과 합으로 제곱 거리를 계산하는 대신 그람 행렬을 계산하고 사용하는 경우 일련의 제곱 거리를 계산하는 것이 더 빠르지만 수치적으로 약간 덜 안정적입니다. 자세한 내용은 Albanie[1]을 참조하십시오.

그람 행렬을 저장하기 위해 디폴트 크기가 1e3메가바이트인 캐시가 사용됩니다. CacheSize 이름-값 인수를 사용하여 캐시 크기를 설정할 수 있습니다. CacheSize의 값이 너무 크거나 "maximal"인 경우, knnsearch는 사용 가능한 메모리를 초과하는 그람 행렬을 할당하려고 시도할 수 있습니다. 이 경우, MATLAB에서 오류를 발생시킵니다.

참고 문헌

[1] Albanie, Samuel. Euclidean Distance Matrix Trick. June, 2019. Available at https://www.robots.ox.ac.uk/%7Ealbanie/notes/Euclidean_distance_trick.pdf.

대체 기능

knnsearch 함수의 'NSMethod' 이름-값 쌍의 인수를 적합한 값(완전 탐색 알고리즘의 경우 'exhaustive' 또는 Kd-트리 알고리즘의 경우 'kdtree'임)으로 설정하는 경우, 탐색 결과는 knnsearch 객체 함수를 사용하여 거리 탐색을 수행하여 구한 결과와 일치합니다. knnsearch 함수와 다르게 knnsearch 객체 함수를 사용하려면 ExhaustiveSearcher 모델 객체 또는 KDTreeSearcher 모델 객체가 필요합니다.

Simulink 블록

k-최근접이웃 탐색을 Simulink®에 통합하려면 Statistics and Machine Learning Toolbox™ 라이브러리의 KNN Search 블록을 사용하거나 MATLAB Function 블록에 knnsearch 함수를 사용할 수 있습니다. 예제는 Predict Class Labels Using MATLAB Function Block 항목을 참조하십시오.

어떤 접근법을 사용할지 결정할 때는 다음을 고려하십시오.

  • Statistics and Machine Learning Toolbox 라이브러리 블록을 사용하는 경우, 고정소수점 툴 (Fixed-Point Designer)을 사용하여 부동소수점 모델을 고정소수점 모델로 변환할 수 있습니다.

  • MATLAB Function 블록에 knnsearch 함수를 사용하려면 이 블록에 대해 가변 크기 배열 지원이 활성화되어 있어야 합니다.

참고 문헌

[1] Friedman, J. H., J. Bentley, and R. A. Finkel. “An Algorithm for Finding Best Matches in Logarithmic Expected Time.” ACM Transactions on Mathematical Software 3, no. 3 (1977): 209–226.

확장 기능

버전 내역

R2010a에 개발됨

모두 확장