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

최근접이웃을 사용한 분류

쌍별(Pairwise) 거리 측정법

훈련 데이터 세트에 포함된 점까지의 거리를 기준으로 쿼리 점을 분류하는 것은 새 점을 분류할 수 있는 단순하면서도 효율적인 방법이 될 수 있습니다. 다양한 측정법을 사용하여 거리를 결정할 수 있습니다. 이에 대해서는 다음에 설명되어 있습니다. pdist2를 사용하여 데이터 세트와 쿼리 점 간의 거리를 구합니다.

거리 측정법

mx개(1xn) 행 벡터 x1, x2, ..., xmx로 처리되는 mxxn 데이터 행렬 X와 my개(1xn) 행 벡터 y1, y2, ...,ymy로 처리되는 myxn 데이터 행렬 Y가 주어진 경우, 벡터 xs와 yt 간의 다양한 거리는 다음과 같이 정의됩니다.

  • 유클리드 거리(Euclidean Distance)

    dst2=(xsyt)(xsyt).

    유클리드 거리는 p = 2인 민코프스키 거리의 특수한 사례입니다.

  • 표준화된 유클리드 거리

    dst2=(xsyt)V1(xsyt),

    여기서 V는 j번째 대각선 요소가 (S(j))2인 nxn 대각 행렬입니다. S는 각 차원의 스케일링 인자로 구성된 벡터입니다.

  • 마할라노비스 거리

    dst2=(xsyt)C1(xsyt),

    여기서 C는 공분산 행렬입니다.

  • 도시 블록 거리

    dst=j=1n|xsjytj|.

    도시 블록 거리는 p = 1인 민코프스키 거리의 특수한 사례입니다.

  • 민코프스키 거리

    dst=j=1n|xsjytj|pp.

    p = 1인 특수한 사례에서 민코프스키 거리는 도시 블록 거리와 동일합니다. p = 2인 특수한 사례에서 민코프스키 거리는 유클리드 거리와 동일합니다. p = ∞인 특수한 사례에서 민코프스키 거리는 체비쇼프 거리와 동일합니다.

  • 체비쇼프 거리

    dst=maxj{|xsjytj|}.

    체비쇼프 거리는 p = ∞인 민코프스키 거리의 특수한 사례입니다.

  • 코사인 거리

    dst=(1xsyt(xsxs)(ytyt)).

  • 상관관계 거리

    dst=1(xsx¯s)(yty¯t)(xsx¯s)(xsx¯s)(yty¯t)(yty¯t),

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

    x¯s=1njxsj

    y¯t=1njytj.

  • 해밍 거리(Hamming Distance)

    dst=(#(xsjytj)/n).

  • 자카드 거리(Jaccard Distance)

    dst=#[(xsjytj)((xsj0)(ytj0))]#[(xsj0)(ytj0)].

  • 스피어만 거리(Spearman Distance)

    dst=1(rsr¯s)(rtr¯t)(rsr¯s)(rsr¯s)(rtr¯t)(rtr¯t),

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

    • rsj는 x1j, x2j, ...xmx,j에 대해 얻은 xsj의 순위로, tiedrank에 의해 계산됩니다.

    • rtj는 y1j, y2j, ...ymy,j에 대해 얻은 ytj의 순위로, tiedrank에 의해 계산됩니다.

    • rs 및 rt는 xs와 yt로 구성된 좌표별 순위 벡터입니다. 즉, rs = (rs1, rs2, ... rsn)이고 rt = (rt1, rt2, ... rtn입니다.

    • r¯s=1njrsj=(n+1)2.

    • r¯t=1njrtj=(n+1)2.

k-최근접이웃 탐색 및 반지름 탐색

n개 점으로 구성된 세트 X와 거리 함수가 주어진 경우, k-최근접이웃(kNN) 탐색을 통해 X에서 단일 쿼리 점 또는 점 세트 Y에 가장 가까운 k개의 최근접 점을 찾을 수 있습니다. kNN 탐색 기법 및 kNN 기반 알고리즘은 벤치마크 학습 규칙으로 널리 사용됩니다. kNN 탐색 기법은 상대적으로 단순하기 때문에 다른 분류 기법의 결과를 kNN 결과와 쉽게 비교할 수 있습니다. 이 기법은 다음과 같이 다양한 영역에 사용되고 있습니다.

  • 생물 정보학

  • 영상 처리 및 데이터 압축

  • 문서 검색

  • 컴퓨터 비전

  • 멀티미디어 데이터베이스

  • 마케팅 데이터 분석

다음과 같은 다른 기계 학습 알고리즘에 kNN 탐색을 사용할 수 있습니다.

  • kNN 분류

  • 국소 가중 회귀

  • 누락된 데이터 대치 및 보간

  • 밀도 추정

K-평균 군집화와 같은 여러 거리 기반 학습 함수와 함께 kNN 탐색을 사용할 수도 있습니다.

이와 반대로, 양의 실수 값 r에 대해 rangesearchY에 있는 각 점의 거리 r 이내에 있는 X의 모든 점을 찾습니다. 이 고정 반지름 탐색은 kNN 탐색과 밀접한 관련이 있습니다. 동일한 거리 측정법과 탐색 클래스를 지원하고 동일한 탐색 알고리즘을 사용하기 때문입니다.

완전 탐색을 사용한 k-최근접이웃 탐색

입력 데이터가 다음 조건 중 하나를 충족할 경우 knnsearch는 기본적으로 완전 탐색(exhaustive search) 방법을 사용하여 k-최근접이웃을 찾습니다.

  • X의 열 개수가 10보다 큽니다.

  • X가 희소 형식입니다.

  • 거리 측정법이 다음 중 하나입니다.

    • 'seuclidean'

    • 'mahalanobis'

    • 'cosine'

    • 'correlation'

    • 'spearman'

    • 'hamming'

    • 'jaccard'

    • 사용자 지정 거리 함수

knnsearch는 탐색 객체가 ExhaustiveSearcher 모델 객체인 경우에도 완전 탐색 방법을 사용합니다. 완전 탐색 방법은 각 쿼리 점에서 X에 포함된 모든 점까지의 거리를 구하고, 오름차순으로 이에 대한 순위를 매긴 후 거리가 가장 작은 k개 점을 반환합니다. 예를 들어, 다음 도식에서는 k = 3개 최근접이웃을 보여줍니다.

Kd-트리를 사용한 k-최근접이웃 탐색

입력 데이터가 다음 조건을 모두 충족할 경우 knnsearch는 기본적으로 Kd-트리를 생성하여 k-최근접이웃을 찾습니다.

  • X의 열 개수가 10보다 작습니다.

  • X가 희소 형식이 아닙니다.

  • 거리 측정법이 다음 중 하나입니다.

    • 'euclidean'(디폴트 값)

    • 'cityblock'

    • 'minkowski'

    • 'chebychev'

knnsearch는 탐색 객체가 KDTreeSearcher 모델 객체인 경우에도 Kd-트리를 사용합니다.

Kd-트리는 (범주와 반대로) 좌표를 기준으로, 가장 많은 경우 노드당 BucketSize(디폴트 값은 50임) 만큼의 점을 갖는 노드로 데이터를 분할합니다. 다음 도식에서는 patch 객체를 사용해 여러 “버킷”을 색으로 구분함으로써 이 개념을 보여줍니다.

지정된 쿼리 점에 대한 k-최근접이웃을 찾으려는 경우 knnsearch는 다음 작업을 수행합니다.

  1. 쿼리 점이 속하는 노드를 결정합니다. 다음 예제에서 쿼리 점 (32,90)은 노드 4에 속합니다.

  2. 해당 노드 내에서 가장 가까운 k개 점을 찾고 쿼리 점까지의 거리를 구합니다. 다음 예제에서 빨간색 원으로 표시된 점들은 쿼리 점에서 등거리에 있으며 노드 4 내에서 쿼리 점과 가장 가까운 점들입니다.

  3. 쿼리 점에서 k번째로 가장 가까운 점까지 임의 방향으로 동일한 거리 내에 있는 영역을 포함하는 다른 모든 노드를 선택합니다. 이 예제에서 검은색 실선 원은 쿼리 점을 중심으로 하고 그 반지름이 노드 4 내의 가장 가까운 점과의 거리와 같은데, 이 원과 겹치는 노드는 오직 노드 3뿐입니다.

  4. 해당 범위 내에 있는 노드에서 쿼리 점에 더 가까이 있는 점들을 모두 탐색합니다. 다음 예제에서는 빨간색 정사각형으로 표시된 점이 노드 4 내에 있는 점보다 쿼리 점에 약간 더 가까이 있습니다.

knnsearch는 거리의 서브셋만 계산하면 되므로 10보다 작은 차원(열)을 갖는 대규모 데이터 세트에 대해서는 Kd-트리를 사용하는 것이 완전 탐색 방법을 사용하는 것보다 훨씬 더 효율적일 수 있습니다. Kd-트리의 효율성을 극대화하려면 KDTreeSearcher 모델을 사용하십시오.

탐색 모델 객체란?

기본적으로 모델 객체는 정보를 저장할 수 있는 편리한 방법입니다. 지정한 탐색 방법과 관련된 값과 유형이 관련 모델에 같은 내용의 속성으로 저장되어 있습니다. 모델 내에 정보를 저장하는 것 외에도 모델에 대해 특정 작업을 수행할 수 있습니다.

knnsearch를 사용하여 탐색 모델에 대해 k-최근접이웃 탐색을 효율적으로 수행할 수 있습니다. 또는, 탐색 모델과 rangesearch를 사용하여 지정된 반지름 내에 있는 모든 이웃을 탐색할 수도 있습니다. 또한, 모델을 생성하거나 사용하지 않고 탐색을 수행하는 일반 knnsearch 함수와 rangesearch 함수도 있습니다.

데이터에 가장 적합한 모델 유형과 탐색 방법을 결정하기 위해서는 다음 사항을 고려해야 합니다.

  • 데이터에 열이 많습니까(예: 10개 초과)? 이 경우 ExhaustiveSearcher 모델의 성능이 더 나을 수 있습니다.

  • 데이터가 희소 형식입니까? 이 경우 ExhaustiveSearcher 모델을 사용하십시오.

  • 다음 거리 측정법 중 하나를 사용하여 최근접이웃을 찾으려고 합니까? 이 경우 ExhaustiveSearcher 모델을 사용하십시오.

    • 'seuclidean'

    • 'mahalanobis'

    • 'cosine'

    • 'correlation'

    • 'spearman'

    • 'hamming'

    • 'jaccard'

    • 사용자 지정 거리 함수

  • 데이터 세트가 큽니까(단, 10개 미만의 열을 가짐)? 이 경우 KDTreeSearcher 모델을 사용하십시오.

  • 많은 쿼리 점에 대한 최근접이웃을 탐색하려고 합니까? 이 경우 KDTreeSearcher 모델을 사용하십시오.

쿼리 데이터 분류하기

이 예제에서는 다음을 통해 쿼리 데이터를 분류하는 방법을 보여줍니다.

  1. Kd-트리 성장시키기

  2. 성장한 트리를 사용하여 k-최근접이웃 탐색 수행

  3. 관련 최근접이웃들 중 가장 높게 표현된 클래스를 각 쿼리 점에 할당

피셔(Fisher)의 붓꽃 데이터의 마지막 두 열을 기준으로 새 점을 분류합니다. 마지막 두 열만 사용하므로 플로팅하기가 더 쉽습니다.

load fisheriris
x = meas(:,3:4);
gscatter(x(:,1),x(:,2),species)
legend('Location','best')

새 점을 플로팅합니다.

newpoint = [5 1.45];
line(newpoint(1),newpoint(2),'marker','x','color','k',...
   'markersize',10,'linewidth',2)

Kd-트리 이웃 탐색기 모델을 준비합니다.

Mdl = KDTreeSearcher(x)
Mdl = 
  KDTreeSearcher with properties:

       BucketSize: 50
         Distance: 'euclidean'
    DistParameter: []
                X: [150x2 double]

MdlKDTreeSearcher 모델입니다. 기본적으로, 이 모델이 이웃을 탐색하는 데 사용하는 거리 측정법은 유클리드 거리(Euclidean Distance)입니다.

새 점에 가장 가까운 10개 표본 점을 찾습니다.

[n,d] = knnsearch(Mdl,newpoint,'k',10);
line(x(n,1),x(n,2),'color',[.5 .5 .5],'marker','o',...
    'linestyle','none','markersize',10)

knnsearch가 8개의 최근접이웃만 찾아낸 것처럼 보입니다. 사실, 이 특정 데이터 세트에는 중복된 값이 있습니다.

x(n,:)
ans = 10×2

    5.0000    1.5000
    4.9000    1.5000
    4.9000    1.5000
    5.1000    1.5000
    5.1000    1.6000
    4.8000    1.4000
    5.0000    1.7000
    4.7000    1.4000
    4.7000    1.4000
    4.7000    1.5000

계산된 거리가 플롯 축에서 뚜렷이 확인되는 거리에 대응되도록 축을 같게 만들고 이웃을 더 잘 확인할 수 있도록 확대합니다.

xlim([4.5 5.5]);
ylim([1 2]);
axis square

10개 이웃으로 구성된 종을 찾습니다.

tabulate(species(n))
       Value    Count   Percent
   virginica        2     20.00%
  versicolor        8     80.00%

10개 최근접이웃에 대한 다수결을 기준으로 하는 규칙을 사용하여 이 새 점을 versicolor로 분류할 수 있습니다.

이웃을 그룹으로 둘러싸는 원을 그려 이웃을 시각적으로 식별합니다. 새 점의 위치를 기준으로 원의 중심과 지름을 정의합니다.

ctr = newpoint - d(end);
diameter = 2*d(end);
% Draw a circle around the 10 nearest neighbors.
h = rectangle('position',[ctr,diameter,diameter],...
   'curvature',[1 1]);
h.LineStyle = ':';

같은 데이터 세트를 사용하여 3개의 새 점에 대한 최근접이웃 10개를 찾습니다.

figure 
newpoint2 = [5 1.45;6 2;2.75 .75];
gscatter(x(:,1),x(:,2),species)
legend('location','best')
[n2,d2] = knnsearch(Mdl,newpoint2,'k',10);
line(x(n2,1),x(n2,2),'color',[.5 .5 .5],'marker','o',...
   'linestyle','none','markersize',10)
line(newpoint2(:,1),newpoint2(:,2),'marker','x','color','k',...
   'markersize',10,'linewidth',2,'linestyle','none')

각각의 새 점에 대한 최근접이웃 10개로 구성된 종을 찾습니다.

tabulate(species(n2(1,:)))
       Value    Count   Percent
   virginica        2     20.00%
  versicolor        8     80.00%
tabulate(species(n2(2,:)))
      Value    Count   Percent
  virginica       10    100.00%
tabulate(species(n2(3,:)))
       Value    Count   Percent
  versicolor        7     70.00%
      setosa        3     30.00%

knnsearch 메서드 및 함수를 사용하는 추가 예제는 각각에 대한 함수 도움말 페이지를 참조하십시오.

사용자 지정 거리 측정법을 사용하여 최근접이웃 찾기

이 예제에서는 카이제곱 거리를 기준으로 Y에 포함된 각 관측값에 대해 X에 포함된 최근접 관측값 3개의 인덱스를 찾는 방법을 보여줍니다. 이 거리 측정법은 대응 분석, 특히 생태학적 응용 사례에 사용됩니다.

정규분포된 데이터를 갖는 행렬 두 개를 무작위로 생성합니다. 행 개수는 다를 수 있지만, 열 개수는 동일해야 합니다. 다음 예제는 2차원 데이터를 사용하여 플로팅합니다.

rng(1); % For reproducibility
X = randn(50,2);
Y = randn(4,2);

h = zeros(3,1);
figure;
h(1) = plot(X(:,1),X(:,2),'bx');
hold on;
h(2) = plot(Y(:,1),Y(:,2),'rs','MarkerSize',10);
title('Heterogenous Data')

XY의 행은 관측값에 해당하고, 열은 일반적으로 차원(예: 예측 변수)에 해당합니다.

j차원 점 xz 간의 카이제곱 거리는 다음과 같습니다.

χ(x,z)=j=1Jwj(xj-zj)2,

여기서 wj는 차원 j와 연결된 가중치입니다.

각 차원에 대한 가중치를 선택하고 카이제곱 거리 함수를 지정합니다. 거리 함수는 다음과 같아야 합니다.

  • 입력 인수로 X의 한 행(즉, x)과 행렬 Z를 받습니다.

  • xZ의 각 행과 비교합니다.

  • 길이가 nz인 벡터 D를 반환합니다. 여기서 nzZ의 행 개수입니다. D의 각 요소는 x에 대응하는 관측값과 Z의 각 행에 대응하는 관측값 간의 거리입니다.

w = [0.4; 0.6];
chiSqrDist = @(x,Z)sqrt((bsxfun(@minus,x,Z).^2)*w);

이 예제에서는 설명을 위해 임의의 가중치를 사용합니다.

Y에 포함된 각 관측값에 대해 X에 포함된 3개의 최근접 관측값에 대한 인덱스를 찾습니다.

k = 3;
[Idx,D] = knnsearch(X,Y,'Distance',chiSqrDist,'k',k);

idxD는 4x3 행렬입니다.

  • idx(j,1)Y의 관측값 j에 대해 X에 포함된 최근접 관측값의 행 인덱스이고, D(j,1)은 해당 거리입니다.

  • idx(j,2)Y의 관측값 j에 대해 X에 포함된 다음 최근접 관측값의 행 인덱스이고, D(j,2)는 해당 거리입니다.

  • 이런 식으로 진행됩니다.

플롯에서 최근접 관측값을 식별합니다.

for j = 1:k;
    h(3) = plot(X(Idx(:,j),1),X(Idx(:,j),2),'ko','MarkerSize',10);
end 
legend(h,{'\texttt{X}','\texttt{Y}','Nearest Neighbor'},'Interpreter','latex');
title('Heterogenous Data and Nearest Neighbors')
hold off;

Y의 여러 관측값은 최근접이웃을 공유합니다.

카이제곱 거리 측정법이 유클리드 거리(Euclidean Distance) 측정법과 동일하지만 선택적으로 스케일링 모수를 사용하는 것을 확인합니다.

[IdxE,DE] = knnsearch(X,Y,'Distance','seuclidean','k',k,...
    'Scale',1./(sqrt(w)));
AreDiffIdx = sum(sum(Idx ~= IdxE))
AreDiffIdx = 0
AreDiffDist = sum(sum(abs(D - DE) > eps))
AreDiffDist = 0

3개의 최근접이웃에 대한 두 가지 구현 간의 거리와 인덱스는 사실상 동일합니다.

지도 학습을 위한 K-최근접이웃 분류

ClassificationKNN 분류 모델을 통해 다음 작업을 수행할 수 있습니다.

지도 학습의 단계에 나와 있는 절차에 따라 분류에 사용할 데이터를 준비합니다. 그런 다음, fitcknn을 사용하여 분류기를 생성합니다.

KNN 분류기 생성하기

이 예제에서는 피셔(Fisher)의 붓꽃 데이터에 사용할 k-최근접이웃 분류기를 생성하는 방법을 보여줍니다.

피셔의 붓꽃 데이터를 불러옵니다.

load fisheriris
X = meas;    % Use all data for fitting
Y = species; % Response data

fitcknn을 사용하여 분류기를 생성합니다.

Mdl = fitcknn(X,Y)
Mdl = 
  ClassificationKNN
             ResponseName: 'Y'
    CategoricalPredictors: []
               ClassNames: {'setosa'  'versicolor'  'virginica'}
           ScoreTransform: 'none'
          NumObservations: 150
                 Distance: 'euclidean'
             NumNeighbors: 1


  Properties, Methods

디폴트 k-최근접이웃 분류기는 단일 최근접이웃만 사용합니다. 대개, 분류기는 이보다 더 많은 이웃을 사용할수록 더 강력합니다.

Mdl의 이웃 크기를 4로 변경합니다. 이는 Mdl 분류기가 4개의 최근접이웃을 사용한다는 것을 의미합니다.

Mdl.NumNeighbors = 4;

KNN 분류기의 품질 검토하기

이 예제에서는 재대입과 교차 검증을 사용하여 k-최근접이웃 분류기의 품질을 검토하는 방법을 보여줍니다.

KNN 분류기 생성하기에서와 같이 피셔의 붓꽃 데이터에 사용할 KNN 분류기를 생성합니다.

load fisheriris
X = meas;    
Y = species; 
rng(10); % For reproducibility
Mdl = fitcknn(X,Y,'NumNeighbors',4);

기본적으로 Mdl의 예측값에서 오분류가 차지하는 비율인 재대입 손실을 검토합니다. 디폴트가 아닌 비용, 가중치 또는 사전 확률은 loss 항목을 참조하십시오.

rloss = resubLoss(Mdl)
rloss = 0.0400

이 분류기는 훈련 데이터의 4%에 대해 잘못 예측합니다.

모델에서 교차 검증된 분류기를 생성합니다.

CVMdl = crossval(Mdl);

훈련에 사용되지 않은 데이터에 대한 예측을 수행하는 경우 각 교차 검증 모델의 평균 손실에 해당하는 교차 검증 손실을 검토합니다.

kloss = kfoldLoss(CVMdl)
kloss = 0.0333

교차 검증된 분류의 정확도는 재대입 정확도와 비슷합니다. 따라서, 새 데이터가 훈련 데이터와 거의 동일한 분포를 가진다고 가정할 경우 Mdl이 새 데이터의 약 4%를 오분류한다고 예상할 수 있습니다.

KNN 분류기를 사용한 분류 예측하기

이 예제에서는 k-최근접이웃 분류기의 분류를 예측하는 방법을 보여줍니다.

KNN 분류기 생성하기에서와 같이 피셔의 붓꽃 데이터에 사용할 KNN 분류기를 생성합니다.

load fisheriris
X = meas;    
Y = species; 
Mdl = fitcknn(X,Y,'NumNeighbors',4);

평균에 해당하는 꽃이 어떻게 분류되는지 예측합니다.

flwr = mean(X); % an average flower
flwrClass = predict(Mdl,flwr)
flwrClass = 1x1 cell array
    {'versicolor'}

KNN 분류기 수정하기

이 예제에서는 k-최근접이웃 분류기를 수정하는 방법을 보여줍니다.

KNN 분류기 생성하기에서와 같이 피셔의 붓꽃 데이터에 사용할 KNN 분류기를 생성합니다.

load fisheriris
X = meas;    
Y = species; 
Mdl = fitcknn(X,Y,'NumNeighbors',4);

디폴트 값인 하나의 최근접이웃을 사용하는 대신 3개의 최근접이웃을 사용하도록 모델을 수정합니다.

Mdl.NumNeighbors = 3;

새 이웃 수를 사용하여 재대입 예측값과 교차 검증 손실을 비교합니다.

loss = resubLoss(Mdl)
loss = 0.0400
rng(10); % For reproducibility
CVMdl = crossval(Mdl,'KFold',5);
kloss = kfoldLoss(CVMdl)
kloss = 0.0333

이 경우, 이웃이 3개인 모델은 이웃이 4개인 모델과 교차 검증 손실이 같습니다(KNN 분류기의 품질 검토하기 항목 참조).

디폴트 값 대신 코사인 거리를 사용하도록 모델을 수정하고 손실을 검토합니다. 코사인 거리를 사용하려면 완전 탐색 방법을 사용하여 모델을 재생성해야 합니다.

CMdl = fitcknn(X,Y,'NSMethod','exhaustive','Distance','cosine');
CMdl.NumNeighbors = 3;
closs = resubLoss(CMdl)
closs = 0.0200

이제, 분류기가 이전보다 낮은 재대입 오차를 가집니다.

새 모델의 교차 검증된 버전에 대한 품질을 검사합니다.

CVCMdl = crossval(CMdl);
kcloss = kfoldLoss(CVCMdl)
kcloss = 0.0200

CVCMdlCVMdl보다 더 나은 교차 검증 손실을 가집니다. 그러나, 일반적으로 재대입 오차를 개선해도 반드시 더 나은 검정-표본 예측값을 가지는 모델이 생성되는 것은 아닙니다.

참고 항목

| | |