本文為英文版的機器翻譯版本，如內容有任何歧義或不一致之處，概以英文版為準。 # K 近鄰 (k-NN) 演算法 Amazon SageMaker AI k 近鄰 (k-NN) 演算法是以索引為基礎的演算法。它使用非參數方法處理分類或迴歸。針對分類問題，此演算法會查詢最鄰近範例點的 *k* 個點，傳回其類別最常用的標籤做為預估標籤。針對迴歸問題，此演算法會查詢最鄰近範例點的 *k* 個點，傳回其特徵值的平均做為預估值。 利用 k-NN 演算法的訓練有三個步驟：取樣、降維和建構索引。取樣會減少初始資料集的大小，以符合記憶體。針對降維，此演算法會減少資料的特徵維度以縮減記憶體和推論延遲中的 k-NN 模型規模。我們提供兩種降維方法：隨機投影和快速 Johnson-Lindenstrauss 轉換。一般而言，您針對高維度 (d > 1000) 資料集使用降維，避免隨著維度增加造成資料統計分析變得疏鬆的 “維度災難”。k-NN 訓練的主要目標是建構索引。索引可讓點與點間距離的查詢有效率，這些點的值或類別標籤尚未決定而 k 最近點用於推論。 **Topics** + [k-NN 演算法的輸入/輸出介面](#kNN-input_output) + [k-NN 範例筆記本](#kNN-sample-notebooks) + [k-NN 演算法的運作方式](kNN_how-it-works.md) + [適用於 k-NN 演算法的 EC2 執行個體建議](#kNN-instances) + [k-NN 超參數](kNN_hyperparameters.md) + [調校 k-NN 模型](kNN-tuning.md) + [k-NN 訓練輸入的資料格式](kNN-in-formats.md) + [k-NN 請求和回應格式](kNN-inference-formats.md) ## k-NN 演算法的輸入/輸出介面 SageMaker AI k-NN 支援訓練和測試資料通道。 + 使用*訓練通道*處理您想要取樣與建構成 k-NN 索引的資料。 + 使用*測試通道*在日誌檔發出分數。每個微型批次列一行分數：`classifier` 為準確性，`regressor` 為分數的均方誤差 (mse)。 針對訓練輸入，k-NN 支援 `text/csv` 和 `application/x-recordio-protobuf` 資料格式。針對輸入類型 `text/csv`，第一個 `label_size` 欄會轉譯為該資料列的標籤向量。您可以使用檔案模式或管道模式，以 `recordIO-wrapped-protobuf` 或 `CSV` 格式的資料來訓練模型。 針對推論輸入，k-NN 支援 `application/json`、`application/x-recordio-protobuf` 和 `text/csv` 資料格式。`text/csv` 格式接受 `label_size` 和編碼參數。它假設 `label_size` 為 0 和 UTF-8 編碼。 針對推論輸出，k-NN 支援 `application/json` 和 `application/x-recordio-protobuf` 資料格式。這兩種資料格式還支援詳細輸出模式。在詳細輸出模式中，API 提供從最小到最大的距離向量排序搜尋結果，以及標籤向量中的對應元素。 針對批次轉換，k-NN 的輸入和輸出都支援 `application/jsonlines` 資料格式。範例輸入如下： ``` content-type: application/jsonlines {"features": [1.5, 16.0, 14.0, 23.0]} {"data": {"features": {"values": [1.5, 16.0, 14.0, 23.0]}} ``` 範例輸出如下： ``` accept: application/jsonlines {"predicted_label": 0.0} {"predicted_label": 2.0} ``` 如需輸入和輸出檔案格式的詳細資訊，請參閱[k-NN 訓練輸入的資料格式](kNN-in-formats.md) (針對訓練)、[k-NN 請求和回應格式](kNN-inference-formats.md) (針對推論) 及[k-NN 範例筆記本](#kNN-sample-notebooks)。 ## k-NN 範例筆記本 如需使用 SageMaker AI k 近鄰演算法的範例筆記本，預測地質和林務局資料的荒野土地覆蓋類型，請參閱 [K 近鄰土地覆蓋類型](https://sagemaker-examples.readthedocs.io/en/latest/introduction_to_amazon_algorithms/k_nearest_neighbors_covtype/k_nearest_neighbors_covtype.html)。 在 SageMaker AI 中使用 Jupyter 筆記本執行個體來執行範例。若要了解如何在 SageMaker AI 中建立和開啟 Jupyter 筆記本執行個體，請參閱[Amazon SageMaker 筆記本執行個體](nbi.md)。在建立並開啟筆記本執行個體後，請選取 **SageMaker AI 範例**索引標籤，以查看所有 SageMaker AI 範例筆記本的清單。在 **Amazon 演算法簡介**一節中尋找 K 近鄰筆記本。若要開啟筆記本，請按一下其**使用**標籤，然後選取**建立複本**。 # k-NN 演算法的運作方式 Amazon SageMaker AI k 近鄰 (k-NN) 演算法遵循多步驟訓練程序，其中包括對輸入資料進行取樣、執行降維和建立索引。然後在推論過程中使用索引資料來有效地找到給定資料點的 k 近鄰，並根據相鄰的標籤或值進行預測。 ## 步驟 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 近鄰索引。根據參考點，演算法可建立分類或迴歸預測。它可以所提供的類別標籤或值為基礎建立預測。k-NN 提供三種不同類型的索引：一般索引、反轉索引和具產品量化的反轉索引。您要使用 `index_type` 參數指定類型。 ## 序列化模型 當 k-NN 演算法完成訓練後，會序列化三個檔案以準備推論。 + model\$1algo-1：包含序列化的索引以計算近鄰。 + model\$1algo-1.labels：包含序列化的標籤 (np.float32 二進位格式)，根據索引的查詢結果計算預估標籤。 + model\$1algo-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" } ``` ## 適用於 k-NN 演算法的 EC2 執行個體建議 建議您在 CPU 執行個體 (例如 ml.m5.2xlarge) 或 GPU 執行個體上進行訓練。k-NN 演算法可支援 P2、P3、G4dn 和 G5 GPU 執行個體系列，進行訓練和推論。 來自 CPU 的推論請求，其平均延遲通常低於來自 GPU 的請求，因為當您使用 GPU 硬體時，CPU 對 GPU 通訊有很重的負擔。不過，GPU 針對較大的批次通常會有更高的輸送量。 # k-NN 超參數 下表列出您可以為 Amazon SageMaker AI k 近鄰 (k-NN) 演算法設定的超參數。 | 參數名稱 | Description | | --- | --- | | feature\$1dim | 輸入資料中的特徵數量。 **必要** 有效值：正整數。 | | k | 近鄰的數量。 **必要** 有效值：正整數 | | predictor\$1type | 用於資料標籤的推論類型。 **必要** 有效值：用於分類的*分類器*或用於迴歸的*迴歸器*。 | | sample\$1size | 要從訓練資料集抽樣的資料點數量。 **必要** 有效值：正整數 | | dimension\$1reduction\$1target | 降低目標的目標維度。 當您指定 `dimension_reduction_type` 參數時，則為**必要項目**。 有效值：大於 0 且小於 `feature_dim` 的正整數。 | | dimension\$1reduction\$1type | 降維方法的類型。 **選用** 有效值：適用於隨機投影的 *sign* 或適用於快速 Johnson-Lindenstrauss 轉換的 *fjlt*。 預設值：不降維 | | faiss\$1index\$1ivf\$1nlists | 當 `index_type` 為 *faiss.IVFFlat* 或 *faiss.IVFPQ* 時，在索引中建構的質量中心數量。 **選用** 有效值：正整數 預設值：*auto*，會解析為 `sqrt(sample_size)`。 | | faiss\$1index\$1pq\$1m | 當 `index_type` 設為 *faiss.IVFPQ* 時，在索引中建構的向量子元件數量。 FaceBook AI 相似性搜尋 (FAISS) 程式庫需要 `faiss_index_pq_m` 的值是資料維度的除數。如果 `faiss_index_pq_m` 不是資料維度的除數，我們會將資料維度增加至可被 `faiss_index_pq_m` 整除的最小整數。如未套用任何降維，此演算法會新增零的填補。如果套用降維，此演算法會增加 `dimension_reduction_target` 超參數的值。 **選用** 有效值：下列正整數之一：1、2、3、4、8、12、16、20、24、28、32、40、48、56、64、96 | | index\$1metric | 尋找近鄰時，測量點與點間距離的指標。以 `index_type` 設為 `faiss.IVFPQ` 訓練時，不支援 `INNER_PRODUCT` 距離和 `COSINE` 相似度。 **選用** 有效值：*L2* 用於歐幾里德距離，*INNER\$1PRODUCT* 用於內部產品距離，*COSINE* 用於餘弦相似度。 預設值：*L2* | | index\$1type | 索引的類型。 **選用** 有效值：*faiss.Flat*、*faiss.IVFFlat*、*faiss.IVFPQ*。 預設值：*faiss.Flat* | | mini\$1batch\$1size | 資料反覆運算器每個微型批次的觀察項數量。 **選用** 有效值：正整數 預設值：5000 | # 調校 k-NN 模型 Amazon SageMaker AI k 近鄰演算法是監督式演算法。此演算法會使用測試資料集，發出有關分類任務準確性或迴歸任務均方錯誤的指標。這些準確性指標會比較其個別任務的模型預測和實證測試資料所提供的基本事實。若要尋找報告測試資料集之最高準確性或最低錯誤的最佳模型，請執行 k-NN 的超參數調校任務。 *自動模型調校*，又稱為超參數調校，會透過在您的資料集上，執行許多測試超參數範圍的任務，來尋找最佳版本的模型。您可以選擇可調校的超參數、每一個超參數的值範圍，及目標指標。您可以選擇適合演算法預測任務的目標指標。自動模型調校會搜尋所選擇的超參數，以找出產生之模型可最佳化目標指標的值組合。超參數僅能用於協助預估模型參數，不提供已訓練模型用於建立預測。 如需模型調校的詳細資訊，請參閱[使用 SageMaker AI 執行自動模型調校](automatic-model-tuning.md)。 ## 由 k-NN 演算法計算的指標 k 近鄰演算法會在訓練期間計算下表兩個指標之一，隨 `predictor_type` 超參數指定的任務類型而定。 + *分類器*會指定分類任務並計算 `test:accuracy` + *迴歸器*會指定迴歸任務並計算 `test:mse`。 選擇適合所執行任務類型的 `predictor_type` 值，以在調校模型時計算相關的目標指標。 | 指標名稱 | Description | 最佳化方向 | | --- | --- | --- | | test:accuracy | 當 `predictor_type` 設為*分類器*時，k-NN 會根據 k 近鄰標籤的平均值，比較預估標籤和測試通道資料所提供的基本事實。回報的準確性範圍從 0.0 (0%) 到 1.0 (100%)。 | 最大化 | | test:mse | 當 `predictor_type` 設為*迴歸器*時，k-NN 會根據 k 近鄰標籤的平均值，比較預估標籤和測試通道資料所提供的基本事實。均方錯誤是經由比較兩個標籤所計算得出。 | 最小化 | ## 可調校的 k-NN 超參數 使用下列超參數調校 Amazon SageMaker AI k 近鄰模型。 | 參數名稱 | 參數類型 | 建議範圍 | | --- | --- | --- | | k | IntegerParameterRanges | MinValue：1、MaxValue：1024 | | sample\$1size | IntegerParameterRanges | MinValue：256、MaxValue：20000000 | # k-NN 訓練輸入的資料格式 所有 Amazon SageMaker AI 內建的演算法，皆採用[常見的資料格式 - 訓練](https://docs.aws.amazon.com/sagemaker/latest/dg/cdf-training.html)中所述之常見輸入訓練格式。此主題包含 SageMaker AI k 近鄰演算法的可用輸入格式清單。 ## CSV 資料格式 content-type：text/csv; label\$1size=1 ``` 4,1.2,1.3,9.6,20.3 ``` 第一個 `label_size` 欄會轉譯為該資料列的標籤向量。 ## RECORDIO 資料格式 content-type：application/x-recordio-protobuf ``` [ Record = { features = { 'values': { values: [1.2, 1.3, 9.6, 20.3] # float32 } }, label = { 'values': { values: [4] # float32 } } } ] } ``` # k-NN 請求和回應格式 所有 Amazon SageMaker AI 內建的演算法，皆採用[常見的資料格式 - 推論](https://docs.aws.amazon.com/sagemaker/latest/dg/cdf-inference.html)中所述之常見輸入推論格式。此主題包含 SageMaker AI k 近鄰演算法的可用輸出格式清單。 ## 輸入：CSV 請求格式 content-type：text/csv ``` 1.2,1.3,9.6,20.3 ``` 這會接受 `label_size` 或編碼參數。它假設 `label_size` 為 0 和 UTF-8 編碼。 ## 輸入：JSON 請求格式 content-type：application/json ``` { "instances": [ {"data": {"features": {"values": [-3, -1, -4, 2]}}}, {"features": [3.0, 0.1, 0.04, 0.002]}] } ``` ## 輸入：JSONLINES 請求格式 content-type：application/jsonlines ``` {"features": [1.5, 16.0, 14.0, 23.0]} {"data": {"features": {"values": [1.5, 16.0, 14.0, 23.0]}} ``` ## 輸入：RECORDIO 請求格式 content-type：application/x-recordio-protobuf ``` [ Record = { features = { 'values': { values: [-3, -1, -4, 2] # float32 } }, label = {} }, Record = { features = { 'values': { values: [3.0, 0.1, 0.04, 0.002] # float32 } }, label = {} }, ] ``` ## 輸出：JSON 回應格式 accept：application/json ``` { "predictions": [ {"predicted_label": 0.0}, {"predicted_label": 2.0} ] } ``` ## 輸出：JSONLINES 回應格式 accept：application/jsonlines ``` {"predicted_label": 0.0} {"predicted_label": 2.0} ``` ## 輸出：VERBOSE JSON 回應格式 在詳細模式中，API 提供從最小到最大的距離向量排序搜尋結果，以及標籤向量中的對應元素。在這個範例中，k 設為 3。 accept：application/json; verbose=true ``` { "predictions": [ { "predicted_label": 0.0, "distances": [3.11792408, 3.89746071, 6.32548437], "labels": [0.0, 1.0, 0.0] }, { "predicted_label": 2.0, "distances": [1.08470316, 3.04917915, 5.25393973], "labels": [2.0, 2.0, 0.0] } ] } ``` ## 輸出：RECORDIO-PROTOBUF 回應格式 content-type：application/x-recordio-protobuf ``` [ Record = { features = {}, label = { 'predicted_label': { values: [0.0] # float32 } } }, Record = { features = {}, label = { 'predicted_label': { values: [2.0] # float32 } } } ] ``` ## 輸出：VERBOSE RECORDIO-PROTOBUF 回應格式 在詳細模式中，API 提供從最小到最大的距離向量排序搜尋結果，以及標籤向量中的對應元素。在這個範例中，k 設為 3。 accept：application/x-recordio-protobuf; verbose=true ``` [ Record = { features = {}, label = { 'predicted_label': { values: [0.0] # float32 }, 'distances': { values: [3.11792408, 3.89746071, 6.32548437] # float32 }, 'labels': { values: [0.0, 1.0, 0.0] # float32 } } }, Record = { features = {}, label = { 'predicted_label': { values: [0.0] # float32 }, 'distances': { values: [1.08470316, 3.04917915, 5.25393973] # float32 }, 'labels': { values: [2.0, 2.0, 0.0] # float32 } } } ] ``` ## k-NN 演算法的範例輸出 針對迴歸器任務： ``` [06/08/2018 20:15:33 INFO 140026520049408] #test_score (algo-1) : ('mse', 0.013333333333333334) ``` 針對分類器任務： ``` [06/08/2018 20:15:46 INFO 140285487171328] #test_score (algo-1) : ('accuracy', 0.98666666666666669) ```