Scikit Learn-K-Nearest Neighbors (KNN)
이 장은 Sklearn에서 가장 가까운 이웃 방법을 이해하는 데 도움이 될 것입니다.
이웃 기반 학습 방법은 두 가지 유형입니다. supervised 과 unsupervised. 지도 이웃 기반 학습은 분류 및 회귀 예측 문제 모두에 사용할 수 있지만 주로 산업의 분류 예측 문제에 사용됩니다.
이웃 기반 학습 방법에는 특수 훈련 단계가 없으며 분류하는 동안 모든 데이터를 훈련에 사용합니다. 또한 기본 데이터에 대해 아무것도 가정하지 않습니다. 이것이 그들이 본질적으로 게으르고 매개 변수가 아닌 이유입니다.
최근 접 이웃 방법의 기본 원리는 다음과 같습니다.
새 데이터 포인트와 거리가 먼 사전 정의 된 수의 훈련 샘플 클로짓을 찾으려면
이러한 수의 훈련 샘플에서 레이블을 예측합니다.
여기서 샘플 수는 K- 최근 접 이웃 학습과 같이 사용자 정의 상수이거나 반경 기반 이웃 학습과 같이 점의 국소 밀도에 따라 달라질 수 있습니다.
sklearn.neighbors 모듈
Scikit-learn은 sklearn.neighbors비지도 및지도 이웃 기반 학습 방법 모두에 대한 기능을 제공하는 모듈입니다. 입력으로이 모듈의 클래스는 NumPy 배열 또는scipy.sparse 행렬.
알고리즘 유형
이웃 기반 방법의 구현에 사용할 수있는 다양한 유형의 알고리즘은 다음과 같습니다.
무차별 대입
데이터 세트의 모든 포인트 쌍 사이의 거리를 무차별 대입하여 계산하면 가장 순진한 인접 검색 구현을 제공합니다. 수학적으로 D 차원의 N 개 샘플에 대해 무차별 대입 접근 방식은 다음과 같이 확장됩니다.0[DN2]
작은 데이터 샘플의 경우이 알고리즘은 매우 유용 할 수 있지만 샘플 수가 증가하면 실행 불가능 해집니다. 무차별 대입 이웃 검색은 키워드를 작성하여 활성화 할 수 있습니다.algorithm=’brute’.
KD 트리
무차별 대입 방식의 계산 비 효율성을 해결하기 위해 고안된 트리 기반 데이터 구조 중 하나는 KD 트리 데이터 구조입니다. 기본적으로 KD 트리는 K 차원 트리라고하는 이진 트리 구조입니다. 데이터 포인트가 채워지는 중첩 된 직교 영역으로 분할하여 데이터 축을 따라 매개 변수 공간을 재귀 적으로 분할합니다.
장점
다음은 KD 트리 알고리즘의 몇 가지 장점입니다.
Construction is fast − 파티셔닝은 데이터 축을 따라서 만 수행되므로 KD 트리의 구성이 매우 빠릅니다.
Less distance computations−이 알고리즘은 쿼리 포인트의 가장 가까운 이웃을 결정하는 데 매우 적은 거리 계산을 사용합니다. 소요됩니다[ ()] 거리 계산.
단점
Fast for only low-dimensional neighbor searches− 저 차원 (D <20) 이웃 검색의 경우 매우 빠르지 만 D가 증가하면 비효율적입니다. 파티셔닝은 데이터 축을 따라서 만 수행되므로
KD 트리 이웃 검색은 키워드를 작성하여 활성화 할 수 있습니다. algorithm=’kd_tree’.
볼 트리
KD Tree는 고차원에서 비효율적이라는 것을 알고 있으므로 KD Tree의 비 효율성을 해결하기 위해 Ball tree 데이터 구조를 개발했습니다. 수학적으로는 데이터를 중심 C와 반경 r로 정의 된 노드로 재귀 적으로 나눕니다. 즉, 노드의 각 점이 중심으로 정의 된 초구 내에 놓 이도록합니다.C 및 반경 r. 아래에 주어진 삼각형 부등식을 사용하여 인접 검색에 대한 후보 포인트 수를 줄입니다.
$$ \ arrowvert X + Y \ arrowvert \ leq \ arrowvert X \ arrowvert + \ arrowvert Y \ arrowvert $$장점
다음은 볼 트리 알고리즘의 몇 가지 장점입니다.
Efficient on highly structured data − 볼 트리가 일련의 중첩 하이퍼 스피어에 데이터를 분할하므로 고도로 구조화 된 데이터에 효율적입니다.
Out-performs KD-tree − 볼 트리는 볼 트리 노드의 구형 기하학을 가지고 있기 때문에 높은 차원에서 KD 트리보다 성능이 뛰어납니다.
단점
Costly − 데이터를 일련의 중첩 하이퍼 스피어로 분할하면 구성 비용이 매우 많이 듭니다.
볼 트리 이웃 검색은 키워드를 작성하여 활성화 할 수 있습니다. algorithm=’ball_tree’.
인접 이웃 알고리즘 선택
주어진 데이터 세트에 대한 최적의 알고리즘 선택은 다음 요인에 따라 달라집니다.
샘플 수 (N) 및 차원 (D)
Nearest Neighbor 알고리즘을 선택할 때 고려해야 할 가장 중요한 요소입니다. 아래에 주어진 이유 때문입니다-
Brute Force 알고리즘의 쿼리 시간은 O [DN]으로 증가합니다.
Ball tree 알고리즘의 질의 시간은 O [D log (N)]만큼 증가합니다.
KD 트리 알고리즘의 쿼리 시간은 특성화하기 매우 어려운 이상한 방식으로 D와 함께 변경됩니다. D <20 일 때 비용은 O [D log (N)]이고이 알고리즘은 매우 효율적입니다. 반면에 D> 20 인 경우 비용이 거의 O [DN]으로 증가하기 때문에 비효율적입니다.
데이터 구조
이러한 알고리즘의 성능에 영향을 미치는 또 다른 요소는 데이터의 고유 차원 또는 데이터의 희소성입니다. Ball tree와 KD tree 알고리즘의 질의 시간이 크게 영향을받을 수 있기 때문입니다. 반면에 Brute Force 알고리즘의 쿼리 시간은 데이터 구조에 의해 변경되지 않습니다. 일반적으로 볼 트리 및 KD 트리 알고리즘은 더 작은 고유 차원을 가진 희소 데이터에 이식 될 때 더 빠른 쿼리 시간을 생성합니다.
이웃 수 (k)
쿼리 포인트에 대해 요청 된 이웃 수 (k)는 볼 트리 및 KD 트리 알고리즘의 쿼리 시간에 영향을줍니다. 이웃 수 (k)가 증가하면 쿼리 시간이 느려집니다. Brute Force의 쿼리 시간은 k 값의 영향을받지 않습니다.
쿼리 포인트 수
구성 단계가 필요하기 때문에 쿼리 포인트가 많은 경우 KD 트리 및 볼 트리 알고리즘이 모두 효과적입니다. 반면에 쿼리 포인트 수가 적 으면 Brute Force 알고리즘이 KD 트리 및 볼 트리 알고리즘보다 성능이 좋습니다.