k-NN 演算法的運作方式

步驟 1：範例

請使用 sample_size 參數指定要從訓練資料集採樣的資料點總數。例如，如果初始資料集有 1,000 個資料點，且 sample_size 設為 100，則當執行個體總數為 2 時，每個工作者的取樣點為 50。總共收集 100 個資料點。資料點抽樣依線性時間執行。

步驟 2：執行降維

k-NN 演算法目前的實作有兩種降維方法。您要在 dimension_reduction_type 超參數中指定方法。sign 方法指定隨機投影，使用利用隨機符號矩陣的線性投影，而 fjlt 方法指定以傅立葉轉換為基礎的快速 Johnson-Lindenstrauss 轉換。兩種方法都保留 L2 和內部產品距離。當目標維度很大且使用 CPU 推論有更好的效能時，應該使用 fjlt 方法。這些方法的運算複雜性各有不同。sign 方法需要 O (ndk) 時間，將維度 d 之一批 n 點的維度降到目標維度 k 的維度。fjlt 方法需要 O(nd log(d)) 時間，但涉及的常數較。使用降維會引進資料雜訊，而此雜訊會降低預測的準確性。

步驟 3：建立索引

在推論期間，演算法會查詢取樣點 k-nearest-neighbors 的索引。根據參考點，演算法可建立分類或迴歸預測。它可以所提供的類別標籤或值為基礎建立預測。k-NN 提供三種不同類型的索引：一般索引、反轉索引和具產品量化的反轉索引。您要使用 index_type 參數指定類型。

序列化模型

當 k-NN 演算法完成訓練後，會序列化三個檔案以準備推論。

• model_algo-1：包含序列化的索引以計算近鄰。

• model_algo-1.labels：包含序列化的標籤 (np.float32 二進位格式)，根據索引的查詢結果計算預估標籤。

• model_algo-1.json：包含 JSON 格式模型的中繼資料，存放來自訓練的 k 和 predictor_type 超參數以供推論，以及其他相關狀態。

透過 k-NN 目前的實作，您可以修改中繼資料檔案，變更計算預測的方式。例如，您可將 k 變更為 10，或將 predictor_type 變更為迴歸器。

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