최근접이웃을 사용한 분류

쌍별(Pairwise) 거리 측정법

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

거리 측정법

mx개(1×n) 행 벡터 x₁, x₂, ..., x_mx로 처리되는 mx×n 데이터 행렬 X와 my개(1×n) 행 벡터 y₁, y₂, ...,y_my로 처리되는 my×n 데이터 행렬 Y가 주어진 경우, 벡터 x_s와 y_t 간의 다양한 거리는 다음과 같이 정의됩니다.

유클리드 거리(Euclidean Distance)
$d_{s t}^{2} = (x_{s} - y_{t}) (x_{s} - y_{t})^{'} .$
유클리드 거리는 p = 2인 민코프스키 거리의 특수한 사례입니다.
Distance 파라미터를 'euclidean'으로 설정하여 유클리드 거리를 지정합니다.
표준화된 유클리드 거리
$d_{s t}^{2} = (x_{s} - y_{t}) V^{- 1} (x_{s} - y_{t})^{'},$
여기서 V는 j번째 대각선 요소가 (S(j))²인 n×n 대각 행렬입니다. S는 각 차원의 스케일링 인자로 구성된 벡터입니다.
Distance 파라미터를 'seuclidean'으로 설정하여 표준화된 유클리드 거리를 지정합니다.
고속 유클리드 거리는 유클리드 거리와 동일하며, 예측 변수 개수가 10개 이상인 경우 시간을 줄여주는 대체 알고리즘을 사용하여 계산됩니다. 속도가 더 빠른 이 알고리즘은 정확도가 떨어질 수 있습니다. 희소 형식 데이터를 지원하지 않습니다. 고속 유클리드 거리 알고리즘 항목을 참조하십시오.
Distance 파라미터를 'fasteuclidean'으로 설정하여 고속 유클리드 거리를 지정합니다.
표준화된 고속 유클리드 거리는 표준화된 유클리드 거리와 동일하며, 예측 변수 개수가 10개 이상인 경우 시간을 줄여주는 대체 알고리즘을 사용하여 계산됩니다. 속도가 더 빠른 이 알고리즘은 정확도가 떨어질 수 있습니다. 희소 형식 데이터를 지원하지 않습니다. 고속 유클리드 거리 알고리즘 항목을 참조하십시오.
Distance 파라미터를 'fastseuclidean'으로 설정하여 고속 표준화된 유클리드 거리를 지정합니다.
마할라노비스 거리
$d_{s t}^{2} = (x_{s} - y_{t}) C^{- 1} (x_{s} - y_{t})^{'},$
여기서 C는 공분산 행렬입니다.
Distance 파라미터를 'mahalanobis'로 설정하여 마할라노비스 거리를 지정합니다.
도시 블록 거리
$d_{s t} = \sum_{j = 1}^{n} | x_{s j} - y_{t j} | .$
도시 블록 거리는 p = 1인 민코프스키 거리의 특수한 사례입니다.
Distance 파라미터를 'cityblock'으로 설정하여 도시 블록 거리를 지정합니다.
민코프스키 거리
$d_{s t} = \sqrt[p]{\sum_{j = 1}^{n} {| x_{s j} - y_{t j} |}^{p}} .$
p = 1인 특수한 사례에서 민코프스키 거리는 도시 블록 거리와 동일합니다. p = 2인 특수한 사례에서 민코프스키 거리는 유클리드 거리와 동일합니다. p = ∞인 특수한 사례에서 민코프스키 거리는 체비쇼프 거리와 동일합니다.
Distance 파라미터를 'minkowski'로 설정하여 민코프스키 거리를 지정합니다.
체비쇼프 거리
$d_{s t} = \max_{j} {| x_{s j} - y_{t j} |} .$
체비쇼프 거리는 p = ∞인 민코프스키 거리의 특수한 사례입니다.
Distance 파라미터를 'chebychev'로 설정하여 체비쇼프 거리를 지정합니다.
코사인 거리
$d_{s t} = (1 - \frac{x_{s} {y^{'}}_{t}}{\sqrt{(x_{s} {x^{'}}_{s}) (y_{t} {y^{'}}_{t})}}) .$
Distance 파라미터를 'cosine'으로 설정하여 코사인 거리를 지정합니다.
상관관계 거리
$d_{s t} = 1 - \frac{(x_{s} - {\bar{x}}_{s}) {(y_{t} - {\bar{y}}_{t})}^{'}}{\sqrt{(x_{s} - {\bar{x}}_{s}) {(x_{s} - {\bar{x}}_{s})}^{'}} \sqrt{(y_{t} - {\bar{y}}_{t}) {(y_{t} - {\bar{y}}_{t})}^{'}}},$
여기서
${\bar{x}}_{s} = \frac{1}{n} \sum_{j} x_{s j}$
및
${\bar{y}}_{t} = \frac{1}{n} \sum_{j} y_{t j} .$
Distance 파라미터를 'correlation'으로 설정하여 상관관계 거리를 지정합니다.
해밍 거리는 다음과 같이 서로 다른 좌표의 백분율입니다.
$d_{s t} = (# (x_{s j} \neq y_{t j}) / n) .$
Distance 파라미터를 'hamming'으로 설정하여 해밍 거리를 지정합니다.
자카드 거리는 0이 아닌 두 좌표의 값이 서로 다른 비율인 자카드 계수를 1에서 뺀 값입니다.
$d_{s t} = \frac{# [(x_{s j} \neq y_{t j}) \cap ((x_{s j} \neq 0) \cup (y_{t j} \neq 0))]}{# [(x_{s j} \neq 0) \cup (y_{t j} \neq 0)]} .$
Distance 파라미터를 'jaccard'로 설정하여 자카드 거리를 지정합니다.
스피어만 거리는 1에서 관측값 간 표본 스피어만의 순위 상관을 뺀 값입니다(일련의 값으로 처리됨).
$d_{s t} = 1 - \frac{(r_{s} - {\bar{r}}_{s}) {(r_{t} - {\bar{r}}_{t})}^{'}}{\sqrt{(r_{s} - {\bar{r}}_{s}) {(r_{s} - {\bar{r}}_{s})}^{'}} \sqrt{(r_{t} - {\bar{r}}_{t}) {(r_{t} - {\bar{r}}_{t})}^{'}}},$
여기서
- r_sj는 x_1j, x_2j, ...x_mx,j에 대해 얻은 x_sj의 순위로, tiedrank에 의해 계산됩니다.
- r_tj는 y_1j, y_2j, ...y_my,j에 대해 얻은 y_tj의 순위로, tiedrank에 의해 계산됩니다.
- r_s 및 r_t는 x_s와 y_t로 구성된 좌표별 순위 벡터입니다. 즉, r_s = (r_s₁, r_s₂, ... r_sn)이고 r_t = (r_t1, r_t2, ... r_tn)입니다.
- ${\bar{r}}_{s} = \frac{1}{n} \sum_{j} r_{s j} = \frac{(n + 1)}{2}$ .
- ${\bar{r}}_{t} = \frac{1}{n} \sum_{j} r_{t j} = \frac{(n + 1)}{2}$ .
Distance 파라미터를 'spearman'으로 설정하여 스피어만 거리를 지정합니다.

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

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

생물 정보학
영상 처리 및 데이터 압축
문서 검색
컴퓨터 비전
멀티미디어 데이터베이스
마케팅 데이터 분석

다음과 같은 다른 머신러닝 알고리즘에 kNN 탐색을 사용할 수 있습니다.

kNN 분류
국소 가중 회귀
누락된 데이터 대치 및 보간
밀도 추정

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

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

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

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

X의 열 개수가 10보다 큽니다.
X가 희소 형식입니다.
거리 측정법이 다음 중 하나입니다.
- 'seuclidean'
- 'mahalanobis'
- 'cosine'
- 'correlation'
- 'spearman'
- 'hamming'
- 'jaccard'
- 사용자 지정 거리 함수

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

3-nearest neighbors diagram. knnsearch computes the displayed distances by using the exhaustive search method.

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

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

X의 열 개수가 10보다 작습니다.
X가 희소 형식이 아닙니다.
거리 측정법이 다음 중 하나입니다.
- 'euclidean'(디폴트 값)
- 'cityblock'
- 'minkowski'
- 'chebychev'

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

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

Diagram of data divided into nodes by Kd-tree

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

쿼리 점이 속하는 노드를 결정합니다. 다음 예제에서 쿼리 점 (32,90)은 노드 4에 속합니다.
해당 노드 내에서 가장 가까운 k개 점을 찾고 쿼리 점까지의 거리를 구합니다. 다음 예제에서 빨간색 원으로 표시된 점들은 쿼리 점에서 등거리에 있으며 노드 4 내에서 쿼리 점과 가장 가까운 점들입니다.
쿼리 점에서 k번째로 가장 가까운 점까지 임의 방향으로 동일한 거리 내에 있는 영역을 포함하는 다른 모든 노드를 선택합니다. 이 예제에서 검은색 실선 원은 쿼리 점을 중심으로 하고 그 반지름이 노드 4 내의 가장 가까운 점과의 거리와 같은데, 이 원과 겹치는 노드는 오직 노드 3뿐입니다.
해당 범위 내에 있는 노드에서 쿼리 점에 더 가까이 있는 점들을 모두 탐색합니다. 다음 예제에서는 빨간색 정사각형으로 표시된 점이 노드 4 내에 있는 점보다 쿼리 점에 약간 더 가까이 있습니다.

Diagram of nodes and nearest neighbors

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

HNSW(Hierarchical Navigable Small Worlds) 알고리즘을 사용한 근사 KNN 탐색

데이터 세트가 클 경우 knnsearch는 시간과 메모리를 상당히 많이 사용합니다. 보다 효율적인(그러나 근사적인) 탐색을 수행하려면 hnswSearcher 모델 객체를 사용합니다. hnswSearcher 함수를 사용하거나, NSMethod="hnsw"를 지정하고 createns 함수를 사용하여 모델 객체를 만들 수 있습니다. 그런 다음, hnswSearcher 모델 객체와 함께 knnsearch를 사용합니다. 이렇게 하면 특히 데이터에 행과 열이 많을 경우 KDTreeSearcher 또는 ExhaustiveSearcher 객체보다 빠르게 실행됩니다.

참고

hnswSearcher 모델 객체를 만드는 데 필요한 시간 때문에 knnsearch를 호출하기 전에 객체부터 만들어야 합니다. 즉, knnsearch(X,NSMethod="hnsw")를 호출할 수 없습니다. 대신 knnsearch(Mdl,...)을 호출해야 합니다. 여기서 Mdl은 기존 hnswSearcher 모델 객체입니다.

HNSW 알고리즘은 여러 계층으로 구성된 최근접이웃 탐색을 위한 그래프를 만듭니다. 높은 계층일수록 낮은 계층보다 점을 더 적게 포함합니다. 각각의 낮은 계층은 높은 계층에 있는 모든 점과 추가적인 점을 포함합니다.

근사 KNN 탐색은 가장 높은 계층에서 시작하여 해당 계층에서 가장 가까운 점을 최대 일치(greedy) 방식으로 찾은 다음 하위 계층으로 이동하여 탐색합니다. 탐색은 계층 0에서 중지됩니다. 다음 그림은 탐색 과정을 보여줍니다.

Three layers of an HNSW graph showing an approximate nearest neighbor search

HNSW 알고리즘은 근사 최근접이웃 탐색기를 만들기 위해 다음 단계를 완료합니다.

임의의 계층 J에 데이터 점을 배치합니다. 여기서 레벨 J는 기하분포로부터 끌어옵니다.
해당 계층에서 데이터 점의 k-최근접이웃을 탐색합니다.
점을 계층 J – 1로 복사합니다.
점의 새로운 k-최근접이웃을 찾습니다.
계층 0까지 이 과정을 반복합니다.
동일한 과정을 사용하여 그다음 데이터 점(있는 경우)을 배치합니다.

Malkov와 Yashunin[1]에 자세히 설명되어 있는 HNSW 탐색기 생성 과정은 상대적으로 느립니다. HNSW 탐색기를 사용하면 새로운 데이터 점의 최근접이웃을 탐색하는 속도가 향상된다는 이점이 있습니다. HNSW를 사용한 KNN 탐색 절차가 실제 최근접이웃을 찾지 못할 수 있는데, 이는 탐색이 국소 최솟값에 머물 수 있기 때문입니다. 그러나 HNSW 탐색 과정은 일반적으로 다른 유형의 KNN 탐색보다 빠르기 때문에 실제 최근접이웃을 모두 찾을 필요가 없을 때 사용해 보십시오.

Malkov와 Yashunin[1]의 파라미터 M은 hnswSearcher의 MaxNumLinksPerNode 파라미터에 상응합니다. 소프트웨어는 [1]의 파라미터 M_L을 1/log(MaxNumLinksPerNode)로 설정합니다.

탐색 모델 객체란?

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

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

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

데이터 세트에 열이 많습니까(예: 10개 초과)? 이 경우 ExhaustiveSearcher 모델의 성능이 더 나을 수 있습니다. 행과 열이 많은 데이터의 경우 hnswSearcher는 다른 탐색 객체보다 훨씬 빠르게 실행되지만 정확한 결과보다는 근사값을 반환합니다.
데이터가 희소 형식입니까? 이 경우 ExhaustiveSearcher 모델을 사용하십시오.
다음 거리 측정법 중 하나를 사용하여 정확한 최근접이웃을 찾으려고 합니까? 이 경우 ExhaustiveSearcher 모델을 사용하십시오.
- 'seuclidean'
- 'mahalanobis'
- 'cosine'
- 'correlation'
- 'spearman'
- 'hamming'
- 'jaccard'
- 사용자 지정 거리 함수
데이터 세트가 크지만 열이 10개 미만입니까? 이 경우 KDTreeSearcher 모델을 사용하십시오. 데이터 세트가 크고 열이 많다면 hnswSearcher를 사용해 보십시오.
많은 쿼리 점에 대한 최근접이웃을 탐색하려고 합니까? KDTreeSearcher 또는 hnswSearcher를 사용하십시오.

쿼리 데이터 분류하기

라이브 스크립트 열기

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

Kd-트리 성장시키기
성장한 트리를 사용하여 k-최근접이웃 탐색 수행
관련 최근접이웃들 중 가장 높게 표현된 클래스를 각 쿼리 점에 할당

피셔(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]

Mdl은 KDTreeSearcher 모델입니다. 기본적으로, 이 모델이 이웃을 탐색하는 데 사용하는 거리 측정법은 유클리드 거리(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('Heterogeneous Data')

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

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

$χ (x, z) = \sqrt{\sum_{j = 1}^{J} w_{j} {(x_{j} - z_{j})}^{2}},$

여기서 $w_{j}$ 는 차원 j와 연결된 가중치입니다.

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

입력 인수로 X의 한 행(즉, x)과 행렬 Z를 받습니다.
x를 Z의 각 행과 비교합니다.
길이가 $n_{z}$ 인 벡터 D를 반환합니다. 여기서 $n_{z}$ 는 Z의 행 개수입니다. D의 각 요소는 x에 대응하는 관측값과 Z의 각 행에 대응하는 관측값 간의 거리입니다.

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

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

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

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

idx와 D는 4×3 행렬입니다.

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('Heterogeneous 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

디폴트 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

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

참고 문헌

[1] Malkov, Yu. A., and D. A. Yashunin. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. Available at https://arxiv.org/abs/1603.09320.

참고 항목

fitcknn | ClassificationKNN | ExhaustiveSearcher | KDTreeSearcher | hnswSearcher