[algorithm] 고차원 데이터에서 가장 가까운 이웃?

I. 거리 측정법

첫째, 데이터 세트의 피처 (열) 수는 kNN에서 사용할 거리 메트릭을 선택하는 요소가 아닙니다. 이 질문에 관한 출판 된 연구는 꽤 많으며 일반적인 비교 근거는 다음과 같습니다.

• 데이터의 기본 통계 분포;

• 데이터를 구성하는 기능들 간의 관계 (독립적입니까? 과

• 데이터를 얻은 좌표 공간

당신이 분포 데이터가 샘플링되는 (들), 최소 (잘 설명하고 철저한) 하나의 사전 지식이 없다면 연구는 유클리드 거리가 최선의 선택이라고 결론 지었다.

YEuclidean 측정법은 대규모 웹 추천 엔진과 현재 학술 연구에 사용됩니다. 유클리드에 의해 계산 된 거리는 직관적 인 의미와 계산 척도를 가지고 있습니다. 즉, 두 점이 2 차원이든 21 차원 공간이든 유클리드 거리는 같은 방식으로 계산됩니다.

기본 (직교 좌표계) 좌표계가 잘못 선택되어 유클리드 거리가 실패했습니다. 예를 들어 미터법 공간이 체스 판일 때 미터법 공간이 지구이고 거리가 트랜스와 같이 유클리드보다 거리 경로 (거리)가 더 이상 추가되지 않기 때문에 일반적으로이를 인식합니다. -대륙 항공편, 극 좌표계에 적합한 거리 측정법은 좋은 생각입니다 (예 : 런던에서 비엔나까지는 2.5 시간, 비엔나에서 상트 페테르부르크까지는 같은 방향으로 약 3 시간, 런던에서 세인트까지) 피터스 버그는 대신 5.5 시간이 아니고 3 시간이 조금 넘습니다.)

그러나 데이터가 직교 좌표가 아닌 좌표계에 속하는 경우를 제외하고는 거리 측정법의 선택은 일반적으로 중요하지 않습니다. ( kNN 분류 자에 미치는 영향을 조사하여 여러 거리 측정 항목을 비교하는 CS 학생 의이 블로그 게시물 을 참조하십시오. -chi square는 최상의 결과를 제공하지만 그 차이는 크지 않습니다.보다 포괄적 인 연구는 학술 논문, 비교 연구 가장 가까운 이웃에 대한 거리 함수 –Mahalanobis (차원 공분산을 설명하기 위해 본질적으로 유클리드 정규화)가이 연구에서 최고였습니다.

중요한 한 가지 단서 : 거리 메트릭 계산이 의미가 있으려면 크기를 다시 조정 해야합니다.귀하의 데이터-드물게이를 수행하지 않고 정확한 예측을 생성하기 위해 kNN 모델을 구축 할 수 있습니다. 예를 들어 운동 성과를 예측하기 위해 kNN 모델을 작성하고 있고 예상 변수가 키 (cm), 체중 (kg), 체지방 (%) 및 휴식 펄스 (분당 비트) 인 경우 일반적인 데이터 포인트가 다음과 같이 보입니다 : [180.4, 66.1, 11.3, 71]. 분명히 거리 계산은 키에 의해 지배 될 것이고, 체지방 %에 의한 기여는 거의 무시할 수있을 것입니다. 달리 말하면, 데이터가 다르게보고되면 체중이 킬로그램이 아닌 그램으로 표시되고 원래 값인 86.1이 86,100이되어 결과에 큰 영향을 미치게됩니다. 원하지 않아요

X_new = (X_old - mu) / sigma

II. 데이터 구조

kd-tree 구조의 성능이 걱정된다면 Voronoi Tessellation 은 개념적으로 간단한 컨테이너이지만 kd-Tree보다 성능과 스케일이 크게 향상됩니다.

kNN 교육 데이터를 유지하는 가장 일반적인 방법은 아니지만 이러한 목적으로 VT를 적용하고 그에 따른 성능 이점을 잘 문서화 한 것입니다 (예 :이 Microsoft Research 보고서 참조 ). 이것의 실질적인 의미는 ‘주류’언어를 사용하는 경우 (예 : TIOBE Index에서 ) VT를 수행 할 라이브러리를 찾아야한다는 것입니다. 파이썬과 R에는 각 언어마다 여러 가지 옵션이 있습니다 (예 : CRAN에서 사용할 수있는 R 의 voronoi 패키지 )

kNN에 VT를 사용하면 다음과 같이 작동합니다.

데이터에서 무작위로 w 포인트를 선택하십시오.이 포인트는 Voronoi 센터입니다. 보로 노이 셀은 각 센터에 가장 가까운 모든 인접 지점을 캡슐화합니다. 각 보로 노이 중심에 서로 다른 색을 지정하여 주어진 중심에 지정된 각 점이 그 색으로 칠해 졌다고 상상해보십시오. 밀도가 충분하면 각 보로 노이 중심의 경계 (두 색상을 구분하는 경계)를 멋지게 표시합니다.

보로 노이 센터를 선택하는 방법? 나는 두 개의 직교 지침을 사용합니다. w 점을 무작위로 선택한 후 훈련 데이터의 VT를 계산하십시오. 그런 다음 각 Voronoi 센터에 할당 된 데이터 포인트 수를 확인합니다.이 값은 거의 같아야합니다 (데이터 공간에서 균일 한 포인트 밀도가 제공됨). 2 차원에서 이로 인해 같은 크기의 타일이있는 VT가 발생합니다. 이것이 첫 번째 규칙이고 두 번째 규칙입니다. 반복으로 w 선택-변수 매개 변수로 w를 사용하여 kNN 알고리즘을 실행하고 성능 (VT를 쿼리하여 예측을 리턴하는 데 필요한 시간)을 측정하십시오.

따라서 백만 개의 데이터 포인트가 있다고 상상해보십시오 .. 점이 일반적인 2D 데이터 구조 또는 kd 트리에서 지속되는 경우 각 포인트에 대해 평균 2 백만 거리 계산을 수행 합니다.반응 변수를 예측하려는 새로운 데이터 포인트. 물론 이러한 계산은 단일 데이터 세트에서 수행됩니다. V / T를 사용하면 가장 가까운 이웃 검색은 두 개의 서로 다른 데이터 집단 (보로 노이 센터에 대해)에 대해 수행 한 다음 가장 가까운 센터가 발견되면 셀 내부의 지점이 이 거리는 실제 가장 가까운 이웃을 찾기 위해 검색됩니다 (연속 거리 계산에 의해)이 두 조회는 단일 무차별 조회보다 훨씬 빠릅니다. 1M 데이터 포인트의 경우 250 개의 보로 노이 센터를 선택하여 데이터 공간을 테셀레이션한다고 가정 해 봅시다. 평균적으로 각 Voronoi 셀에는 4,000 개의 데이터 포인트가 있습니다. 따라서 평균 500,000 거리 계산 (브 루트 힘)을 수행하는 대신 평균 125 + 2,000으로 훨씬 적은 성능을 수행합니다.

III. 결과 계산 (예측 된 반응 변수)

kNN 트레이닝 데이터 세트에서 예측값을 계산하는 두 단계가 있습니다. 첫 번째는 n 또는 이 계산에 사용할 가장 가까운 이웃 수를 식별 하는 것입니다. 두 번째는 기여도 를 예측값 에 가중시키는 방법 입니다.

첫 번째 성분이없는 경우 최적화 문제 (최소 제곱 최적화와 매우 유사)를 해결하여 n의 최상의 값을 결정할 수 있습니다. 이것이 이론입니다. 실제로 대부분의 사람들은 n = 3을 사용합니다. 어쨌든 n = 1, n = 2, n = 3 등의 테스트 인스턴스 집합에 대해 kNN 알고리즘을 실행하고 (예측 된 값을 계산하기 위해) n의 함수로 오류를 플로팅하는 것은 간단합니다. n에 대한 적절한 값을 시작하려면 다시 n = 3을 사용하십시오.

두 번째 구성 요소는 각 이웃의 기여도를 가중하는 방법입니다 (n> 1 가정).

가장 간단한 가중치 기술은 각 이웃에 가중치 계수 (1 / (dist * K)) 또는 해당 이웃에서 테스트 인스턴스까지의 거리의 역수를 곱하고 경험적으로 파생 된 상수 K를 곱한 것입니다. 이 기술의 팬이 아닙니다. 가장 가까운 이웃을 과체중으로 (그리고 더 먼 거리의 무게를 과소하게 가중시키기 때문에); 이것의 중요성은 주어진 예측이 단일 이웃에 거의 전적으로 의존 할 수 있으며, 결과적으로 잡음에 대한 알고리즘의 감도가 증가한다는 것이다.

이 제한을 실질적으로 피하는 더 나은 가중 함수 는 파이썬에서 다음과 같이 보이는 가우스 함수입니다 .

def weight_gauss(dist, sig=2.0) :
    return math.e**(-dist**2/(2*sig**2))

kNN 코드를 사용하여 예측 값을 계산하려면 응답 변수를 예측하려는 데이터 포인트에서 가장 가까운 n 개의 이웃을 식별하고 ( ‘테스트 인스턴스’), n 개의 이웃 각각에 대해 weight_gauss 함수를 한 번 호출하여 전달합니다. 이 함수는 각 이웃에 대한 테스트 포인트 사이의 거리에서 각 이웃에 대한 가중치를 반환 한 다음 가중 평균 계산에서 해당 이웃의 계수로 사용됩니다.

---

답변