Come funziona l'algoritmo k-NN

L'algoritmo Amazon SageMaker AI k-Nearest Neighbors (k-NN) segue un processo di formazione in più fasi che include il campionamento dei dati di input, l'esecuzione della riduzione delle dimensioni e la creazione di un indice. I dati indicizzati vengono quindi utilizzati durante l'inferenza per trovare in modo efficiente i k-vicini più vicini per un determinato punto dati e fare previsioni basate sulle etichette o sui valori adiacenti.

Fase 1: campionamento

Per specificare il numero totale di punti di dati da campionare dal set di dati di addestramento, utilizza il parametro sample_size. Ad esempio, se il set di dati iniziale ha 1.000 punti dati e sample_size è impostato su 100, dove il numero totale di istanze è 2, ogni worker avrebbe 50 punti di campionamento. Verrebbe raccolto un totale di 100 punti dati. Il campionamento viene eseguito linearmente rispetto al numero di dati.

Fase 2: esecuzione della riduzione della dimensione

L'implementazione corrente dell'algoritmo k-NN ha due metodi di riduzione della dimensione. Devi specificare il metodo nell'iperparametro dimension_reduction_type. Il metodo sign specifica una proiezione casuale che utilizza una proiezione lineare con una matrice dei segni casuali e il metodo fjlt specifica una trasformazione veloce Johnson-Lindenstrauss, un metodo basato sulla trasformazione Fourier. Entrambi i metodi conservano le distanze del prodotto interne e L2. Il metodo fjlt deve essere utilizzato quando la dimensione di target è ampia e ha prestazioni migliori con l'inferenza della CPU. I metodi differiscono tra loro nella complessità di calcolo. Il metodo sign richiede il tempo O(ndk) per ridurre la dimensione di un batch di n punti di dimensione d in una dimensione target k. Il metodo fjlt richiede il tempo O(nd log(d)), ma le costanti coinvolte sono più grandi. L'uso della riduzione delle dimensioni introduce disturbo nei dati e questo disturbo può ridurre l'accuratezza della previsione.

Fase 3: creazione di un indice

Durante l'inferenza, l'algoritmo interroga l'indice per il punto di campionamento. k-nearest-neighbors Sulla base dei riferimenti ai punti, l'algoritmo effettua la previsione di regressione o classificazione. Rende la predizione basata sulle etichette di classe o sui valori forniti. k-NN fornisce tre diversi tipi di indici: un indice flat, un indice invertito e un indice invertito con quantizzazione del prodotto. Puoi specificare il tipo con il parametro index_type.

Serializzazione del modello

Quando l'algoritmo k-NN termina l’addestramento, serializza tre file per prepararsi all'inferenza.

• model_algo-1: contiene l'indice serializzato per calcolare i neighbors più vicini.

• model_algo-1.labels: contiene le etichette serializzate (formato binario np.float32) per calcolare l'etichetta prevista in base al risultato della query dell'indice.

• model_algo-1.json: contiene i metadati del modello con formattazione JSON che memorizza gli iperparametri k e predictor_type dell’addestramento per l'inferenza insieme ad altri stati rilevanti.

Con l'attuale implementazione di k-NN, puoi modificare il file dei metadati per cambiare il modo in cui le previsioni vengono calcolate. Ad esempio, puoi modificare k su 10 o predictor_type su regressor.

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