Nearest Neighbors

Scikit-Learn의 Nearest Neighbors를 공부하며 정리하였습니다.

• NN 알고리즘은 군집 및 Manifold 학습이 있는 비지도 학습과 분류 및 회귀 문제를 다루는 지도 학습으로 나눈다.
• 이 알고리즘은 훈련 샘플에서 새로운 점에서 거리를 측정하며 라벨을 붙이는 방식이다.
• 사용자가 정의하는 KNN이나 점의 밀집도를 기준으로 하는 Radius-Based NN이 존재한다.
• 거리는 일반적으로 l2 norm 처럼 유클리디안 거리를 사용한다.

Unsupervised Nearest Neighbors(기본)

• 기본적인 NN 알고리즘은 비지도 학습에 적용되어 BallTree, KDTree, Brute-force 알고리즘처럼 움직인다.
• 따라서, 파라미터 algoritm은 ['auto', 'ball_tree', 'kd_tree', 'brute'] 중 하나로 설정할 수 있다.

기본적인 형태

nbrs = NearestNeighbors(n_neighbors=2, algorithm='ball_tree').fit(X)
distances, indices = nbrs.kneighbors(X)

• 자기 자신을 가리키는 경우 거리가 0이 나타나게 된다.

기본적인 알고리즘

Brute force

• NN 알고리즘 중 가장 빠른 계산을 수행한다. 그리고 데이터셋의 모든 점의 쌍 사이에서의 거리를 모두 계산을 진행함
• N개의 샘플에 D 차원이면 시간은 O[DN^2]이다. 따라서, 작은 데이터 샘플에 대해서 적용하는 것이 좋고 큰 알고리즘의 경우에는 좋지 않다.

KD Tree

• 데이터 셋이 크면 비효율적인 Brute Force를 보완하기 위해 다양한 트리 기반의 데이터 구조를 만드는 것이 K-D Tree이다.
• 기본적인 아이디어는 A와 B가 가깝고 B와 C가 가까우면 A와 C도 가깝다는 논리구조로 계산 비용과정을 줄이는 방식이다.
• 시간복잡도는 O[DNlog(N)]이거나 더 빠르다.
• K 차원의 트리라고 해서 K-dimensional tree 즉, K-D Tree이다.
• 이 알고리즘은 이진탐색 트리 구조와 비슷해 각 데이터의 구조를 나누는데 매우 빠르다. 그러나 이는 오로지 D < 20인 경우에 빠르고 이보다 더 커지면 "차원의 저주"라고 불리는 비효율성이 발생하게 된다.

Ball Tree

• 높은 차원에서 KD Tree가 비효율적임을 극보하기 위해 제시된 알고리즘이 Ball Tree이다.
• Cartesian 축으로 구분하는 KD Tree와 달리 Ball Tree는 Nesting hyper-spheres로 데이터를 구분하기에 더 비용이 들지만 높은 차원의 데이터셋을 구분하는데 매우 효율적이다.
• 기본적인 아이디어는 중심 C와 지름 r이 있을 경우 아래의 수식을 기준으로 가까운 이웃을 찾게 된다.

최종 알고리즘을 선택하는 기준

Nearest Neighbors Classification

• NN 분류 방법은 KNN과 Radius-NN으로 나눠진다.
• KNN이 분류 방법에서 가장 흔하게 사용되는 방법으로 큰 k는 노이즈의 영향을 줄이고 분류 구분선을 구분하기 어렵게 한다.
• 획일화되어 있지 않은 샘플 데이터에서는 Radius-NN을 사용해 지름 r을 선택하는 것이 좋다. 그러나, 차원의 저주로 파라미터 공간이 큰 경우에는 비효율적이다.

• NN 분류 방법에서는 가까운 이웃이라는 계산을 수행할 때 가중치를 사용한다.
• 기본적인 값은 weights = 'uniform'이고 쿼리 수 반대에 비례해 할당하는 weights = 'distance'가 존재하고 있다.

Nearest Neighbors Regression

• 데이터가 분리되어 있기보다 연속적인 라벨로 형성되어 있을 때 NN 회기 방식을 사용한다.
• 회기 방법에도 KNN과 Radius-NN으로 나눠진다.

• 여기에도 기본적인 가중치를 설정해 사용할 수 있다.
• 기본적인 값은 weights = 'uniform'이고 weight='distance'로 나눠진다.