k-NN 알고리즘 작동 방법

Amazon SageMaker AI k-Nearest Neighbors(k-NN) 알고리즘은 입력 데이터 샘플링, 차원 감소 수행, 인덱스 구축을 포함하는 다단계 훈련 프로세스를 따릅니다. 그런 다음 추론 중에 인덱싱된 데이터를 사용하여 지정된 데이터 포인트에 대한 k-Nearest Neighbors(k-NN)를 효율적으로 찾고 인접 레이블 또는 값을 기반으로 예측합니다.

1단계: 샘플

훈련 데이터세트에서 샘플링할 데이터 포인트의 총 수를 지정하려면 sample_size 파라미터를 사용합니다. 예를 들어, 최초 데이터세트에 데이터 포인트가 1,000개 있고, sample_size가 100으로 설정되어 있으면(여기서 총 인스턴스 수는 2개임) 이 각 작업자는 포인트 50개를 샘플링합니다. 총 100개의 데이터 포인트 세트가 수집됩니다. 샘플링은 데이터 포인트 수를 기준으로 선형 시간으로 실행됩니다.

2단계: 차원 감소 수행

현재 구현된 k-NN 알고리즘에는 두 가지 차원 감소 방법이 있습니다. 이러한 메서드는 dimension_reduction_type 하이퍼파라미터에서 지정합니다. sign 메서드는 무작위 투영을 지정하는데, 이 투영은 임의 신호 매트릭스를 사용하는 선형 투영을 사용합니다. fjlt 메서드는 푸리에 변환을 기반으로 하는 방법인 빠른 Johnson-Lindenstrauss 변환을 지정합니다. 두 메서드 모두 L2 및 내적 거리를 보존합니다. fjlt 메서드는 대상 차원이 크고 CPU 추론과 관련해 성능이 보다 뛰어난 경우 사용해야 합니다. 메서드는 컴퓨팅 복잡성에 따라 달라집니다. 차원 d의 n개 포인트로 구성된 배치의 차원을 대상 차원 k로 줄이려면 sign 메서드에는 O(ndk) 시간이 필요합니다. fjlt 메서드에는 O(nd 로그(d)) 시간이 필요하지만 관련 상수가 더 클 수 있습니다. 차원 감소를 사용하면 데이터에 노이즈가 유입되고 이러한 노이즈는 예측 정확도를 떨어뜨릴 수 있습니다.

3단계: 인덱스 빌드

추론 중 이 알고리즘은 샘플 포인트의 k-nearest-neighbors에 대한 인덱스를 쿼리합니다. 포인트에 대한 추론을 기반으로 이 알고리즘은 분류 또는 회귀 예측을 수행합니다. 제공된 클래스 레이블 또는 값을 기반으로 예측합니다. k-NN은 플랫 인덱스, 반전 인덱스 및 프로덕트 양자화가 적용된 반전 인덱스, 이렇게 3가지 다른 유형의 인덱스가 있습니다. index_type 파라미터를 사용하여 유형을 지정합니다.

모델 직렬화

k-NN 알고리즘이 훈련을 마치면 추론을 준비하기 위해 파일 3개를 직렬화합니다.

• model_algo-1: 가장 가까운 아웃을 계산하기 위해 직렬화된 인덱스를 포함합니다.

• model_algo-1.labels: 인덱스의 쿼리 결과를 기반으로 예측 레이블을 계산하기 위해 직렬화된 레이블(np.float32 바이너리 형식)을 포함합니다.

• model_algo-1.json: 추론을 위한 훈련에서 k 및 predictor_type 하이퍼파라미터를 저장하는 JSON 형식 모델 메타데이터를 기타 관련 상태와 함께 포함합니다.

k-NN이 현재 구현을 사용하면 메타데이터 파일을 수정해 예측 계산 방식을 변경할 수 있습니다. 예를 들어, k를 10으로 변경하거나 predictor_type을 regressor로 변경할 수 있습니다.

{
  "k": 5,
  "predictor_type": "classifier",
  "dimension_reduction": {"type": "sign", "seed": 3, "target_dim": 10, "input_dim": 20},
  "normalize": False,
  "version": "1.0"
}