數據科學經典算法 KNN 已被嫌慢,ANN 比它快 380 倍

2021-01-07 電子發燒友
數據科學經典算法 KNN 已被嫌慢，ANN 比它快 380 倍

Marie Stephen Leo 發表於 2021-01-02 09:08:00

數據科學經典算法 KNN 已被嫌慢，ANN 比它快 380 倍。

 

在模式識別領域中，K - 近鄰算法（K-Nearest Neighbor， KNN）是一種用於分類和回歸的非參數統計方法。K - 近鄰算法非常簡單而有效，它的模型表示就是整個訓練數據集。就原理而言，對新數據點的預測結果是通過在整個訓練集上搜索與該數據點最相似的 K 個實例（近鄰）並且總結這 K 個實例的輸出變量而得出的。KNN 可能需要大量的內存或空間來存儲所有數據，並且使用距離或接近程度的度量方法可能會在維度非常高的情況下（有許多輸入變量）崩潰，這可能會對算法在你的問題上的性能產生負面影響。這就是所謂的維數災難。

近似最近鄰算法（Approximate Nearest Neighbor， ANN）則是一種通過犧牲精度來換取時間和空間的方式從大量樣本中獲取最近鄰的方法，並以其存儲空間少、查找效率高等優點引起了人們的廣泛關注。

近日，一家技術公司的數據科學主管 Marie Stephen Leo 撰文對 KNN 與 ANN 進行了比較，結果表明，在搜索到最近鄰的相似度為 99.3% 的情況下，ANN 比 sklearn 上的 KNN 快了 380 倍。

作者表示，幾乎每門數據科學課程中都會講授 KNN 算法，但它正在走向「淘汰」！

KNN 簡述

在機器學習社區中，找到給定項的「K」個相似項被稱為相似性搜索或最近鄰（NN）搜索。最廣為人知的 NN 搜索算法是 KNN 算法。在 KNN 中，給定諸如手機電商目錄之類的對象集合，則對於任何新的搜索查詢，我們都可以從整個目錄中找到少量（K 個）最近鄰。例如，在下面示例中，如果設置 K = 3，則每個「iPhone」的 3 個最近鄰是另一個「iPhone」。同樣，每個「Samsung」的 3 個最近鄰也都是「Samsung」。

KNN 存在的問題

儘管 KNN 擅長查找相似項，但它使用詳細的成對距離計算來查找鄰居。如果你的數據包含 1000 個項，如若找出新產品的 K=3 最近鄰，則算法需要對資料庫中所有其他產品執行 1000 次新產品距離計算。這還不算太糟糕，但是想像一下，現實世界中的客戶對客戶（Customer-to-Customer，C2C）市場，其中的資料庫包含數百萬種產品，每天可能會上傳數千種新產品。將每個新產品與全部數百萬種產品進行比較是不划算的，而且耗時良久，也就是說這種方法根本無法擴展。

解決方案

將最近鄰算法擴展至大規模數據的方法是徹底避開暴力距離計算，使用 ANN 算法。

近似最近距離算法（ANN）

嚴格地講，ANN 是一種在 NN 搜索過程中允許少量誤差的算法。但在實際的 C2C 市場中，真實的鄰居數量比被搜索的 K 近鄰數量要多。與暴力 KNN 相比，人工神經網絡可以在短時間內獲得卓越的準確性。ANN 算法有以下幾種：

Spotify 的 ANNOY

Google 的 ScaNN

Facebook 的 Faiss

HNSW

分層的可導航小世界（Hierarchical Navigable Small World， HNSW）

在 HNSW 中，作者描述了一種使用多層圖的 ANN 算法。在插入元素階段，通過指數衰減概率分布隨機選擇每個元素的最大層，逐步構建 HNSW 圖。這確保 layer=0 時有很多元素能夠實現精細搜索，而 layer=2 時支持粗放搜索的元素數量少了 e^-2。最近鄰搜索從最上層開始進行粗略搜索，然後逐步向下處理，直至最底層。使用貪心圖路徑算法遍歷圖，並找到所需鄰居數量。

HNSW 圖結構。最近鄰搜索從最頂層開始（粗放搜索），在最底層結束（精細搜索）。

HNSW Python 包

整個 HNSW 算法代碼已經用帶有 Python 綁定的 C++ 實現了，用戶可以通過鍵入以下命令將其安裝在機器上：pip install hnswlib。安裝並導入軟體包之後，創建 HNSW 圖需要執行一些步驟，這些步驟已經被封裝到了以下函數中：

importhnswlib importnumpy asnpdef fit_hnsw_index（features， ef= 100， M= 16， save_index_file= False）： # Convenience function to create HNSW graph # features ： list of lists containing the embeddings # ef， M： parameters to tune the HNSW algorithm num_elements = len（features） labels_index = np.arange（num_elements） EMBEDDING_SIZE = len（features［ 0］） # Declaring index # possible space options are l2， cosine or ip p = hnswlib.Index（space= 『l2』， dim=EMBEDDING_SIZE） # Initing index - the maximum number of elements should be known p.init_index（max_elements=num_elements， ef_construction=ef， M=M） # Element insertion int_labels = p.add_items（features， labels_index） # Controlling the recall by setting ef # ef should always be 》 k p.set_ef（ef） # If you want to save the graph to a file ifsave_index_file： p.save_index（save_index_file） returnp

創建 HNSW 索引後，查詢「K」個最近鄰就僅需以下這一行代碼：

ann_neighbor_indices， ann_distances = p.knn_query（features， k）

KNN 和 ANN 基準實驗

計劃

首先下載一個 500K + 行的大型數據集。然後將使用預訓練 fasttext 句子向量將文本列轉換為 300d 嵌入向量。然後將在不同長度的輸入數據 ［1000. 10000， 100000， len（data）］ 上訓練 KNN 和 HNSW ANN 模型，以度量數據大小對速度的影響。最後將查詢兩個模型中的 K=10 和 K=100 時的最近鄰，以度量「K」對速度的影響。首先導入必要的包和模型。這需要一些時間，因為需要從網絡上下載 fasttext 模型。

# Imports # For input data pre-processing importjson importgzip importpandas aspd importnumpy asnp importmatplotlib.pyplot asplt importfasttext.util fasttext.util.download_model（ 『en』， if_exists= 『ignore』） # English pre-trained model ft = fasttext.load_model（ 『cc.en.300.bin』） # For KNN vs ANN benchmarking fromdatetime importdatetime fromtqdm importtqdm fromsklearn.neighbors importNearestNeighbors importhnswlib

數據

使用亞［馬遜產品數據集］，其中包含「手機及配件」類別中的 527000 種產品。然後運行以下代碼將其轉換為數據框架。記住僅需要產品 title 列，因為將使用它來搜索相似的產品。

# Data： http://deepyeti.ucsd.edu/jianmo/amazon/ data = ［］ withgzip.open（ 『meta_Cell_Phones_and_Accessories.json.gz』） asf： forl inf： data.append（json.loads（l.strip）） # Pre-Processing： https://colab.research.google.com/drive/1Zv6MARGQcrBbLHyjPVVMZVnRWsRnVMpV#scrollTo=LgWrDtZ94w89 # Convert list into pandas dataframe df = pd.DataFrame.from_dict（ data） df.fillna（ 『』， inplace= True） # Filter unformatted rows df = df［~df.title.str.contains（ 『getTime』）］ # Restrict to just 『Cell Phones and Accessories』 df = df［df［ 『main_cat』］== 『Cell Phones & Accessories』］ # Reset index df.reset_index（inplace= True， drop= True） # Only keep the title columns df = df［［ 『title』］］ # Check the df print（df.shape） df.head

如果全部都可以運行精細搜索，你將看到如下輸出：

亞馬遜產品數據集。

嵌入

要對文本數據進行相似性搜索，則必須首先將其轉換為數字向量。一種快速便捷的方法是使用經過預訓練的網絡嵌入層，例如 Facebook ［FastText］ 提供的嵌入層。由於希望所有行都具有相同的長度向量，而與 title 中的單詞數目無關，所以將在 df 中的 title 列調用 get_sentence_vector 方法。

嵌入完成後，將 emb 列作為一個 list 輸入到 NN 算法中。理想情況下可以在此步驟之前進行一些文本清理預處理。同樣，使用微調的嵌入模型也是一個好主意。

# Title Embedding using FastText Sentence Embedding df［ 『emb』］ = df［ 『title』］.apply（ft.get_sentence_vector） # Extract out the embeddings column as a list of lists for input to our NN algos X = ［item.tolist foritem indf［ 『emb』］.values］

基準

有了算法的輸入，下一步進行基準測試。具體而言，在搜索空間中的產品數量和正在搜索的 K 個最近鄰之間進行循環測試。在每次迭代中，除了記錄每種算法的耗時以外，還要檢查 pct_overlap，因為一定比例的 KNN 最近鄰也被挑選為 ANN 最近鄰。

注意整個測試在一臺全天候運行的 8 核、30GB RAM 機器上運行大約 6 天，這有些耗時。理想情況下，你可以通過多進程來加快運行速度，因為每次運行都相互獨立。

# Number of products for benchmark loop n_products = ［ 1000， 10000， 100000， len（X）］ # Number of neighbors for benchmark loop n_neighbors = ［ 10， 100］ # Dictionary to save metric results for each iteration metrics = { 『products』：［］， 『k』：［］， 『knn_time』：［］， 『ann_time』：［］， 『pct_overlap』：［］} forproducts intqdm（n_products）： # 「products」 number of products included in the search space features = X［ ：products］ fork intqdm（n_neighbors）： # 「K」 Nearest Neighbor search # KNN knn_start = datetime.now nbrs = NearestNeighbors（n_neighbors=k， metric= 『euclidean』）.fit（features） knn_distances， knn_neighbor_indices = nbrs.kneighbors（X） knn_end = datetime.now metrics［ 『knn_time』］.append（（knn_end - knn_start）.total_seconds） # HNSW ANN ann_start = datetime.now p = fit_hnsw_index（features， ef=k* 10） ann_neighbor_indices， ann_distances = p.knn_query（features， k） ann_end = datetime.now metrics［ 『ann_time』］.append（（ann_end - ann_start）.total_seconds） # Average Percent Overlap in Nearest Neighbors across all 「products」 metrics［ 『pct_overlap』］.append（np.mean（［len（np.intersect1d（knn_neighbor_indices［i］， ann_neighbor_indices［i］））/k fori inrange（len（features））］）） metrics［ 『products』］.append（products） metrics［ 『k』］.append（k） metrics_df = pd.DataFrame（metrics） metrics_df.to_csv（ 『metrics_df.csv』， index=False） metrics_df

運行結束時輸出如下所示。從表中已經能夠看出，HNSW ANN 完全超越了 KNN。

以表格形式呈現的結果。

結果

以圖表的形式查看基準測試的結果，以真正了解二者之間的差異，其中使用標準的 matplotlib 代碼來繪製這些圖表。這種差距是驚人的。根據查詢 K=10 和 K=100 最近鄰所需的時間，HNSW ANN 將 KNN 徹底淘汰。當搜索空間包含約 50 萬個產品時，在 ANN 上搜索 100 個最近鄰的速度是 KNN 的 380 倍，同時兩者搜索到最近鄰的相似度為 99.3%。

在搜索空間包含 500K 個元素，搜索空間中每個元素找到 K=100 最近鄰時，HNSW ANN 的速度比 Sklearn 的 KNN 快 380 倍。

在搜索空間包含 500K 個元素，搜索空間中每個元素找到 K=100 最近鄰時，HNSW ANN 和 KNN 搜索到最近鄰的相似度為 99.3%。

基於以上結果，作者認為可以大膽地說：「KNN 已死」。

責任編輯：PSY

打開APP閱讀更多精彩內容

聲明：本文內容及配圖由入駐作者撰寫或者入駐合作網站授權轉載。文章觀點僅代表作者本人，不代表電子發燒友網立場。文章及其配圖僅供工程師學習之用，如有內容圖片侵權或者其他問題，請聯繫本站作侵刪。 侵權投訴

相關焦點

  • 比KNN快380倍!我們有了新選擇
    接下來將使用大型的【Amazon product dataset】，其中包含『手機&配件』分類中的527000個產品，以此來證明HNSW的速度非常快（準確說是快380倍），同時還能得到與sklearn的KNN百分之99.3相同的結果。在HNSW中【paper @ arxiv】，作者使用多層圖來描述ANN算法。
  • 有人斷言KNN面臨淘汰,更快更強的ANN將取而代之
    在模式識別領域中，K - 近鄰算法（K-Nearest Neighbor, KNN）是一種用於分類和回歸的非參數統計方法。近日，一家技術公司的數據科學主管 Marie Stephen Leo 撰文對 KNN 與 ANN 進行了比較，結果表明，在搜索到最近鄰的相似度為 99.3% 的情況下，ANN 比 sklearn 上的 KNN 快了 380 倍。
  • 速度數百倍之差,有人斷言KNN面臨淘汰,更快更強的ANN將取而代之
    選自towardsdatascience作者：Marie Stephen Leo機器之心編譯編輯：小舟、杜偉數據科學經典算法 KNN 已被嫌慢，ANN 比它快 380 倍。
  • KNN算法中的K有多重要
    K-最近鄰（KNN）是一種有監督的機器學習算法，可用於解決分類和回歸問題。它基於一個非常簡單的想法，數據點的值由它周圍的數據點決定。考慮的數據點數量由k值確定。因此，k值是算法的核心。KNN分類器根據多數表決原則確定數據點的類別。如果k設置為5，則檢查5個最近點的類別。也可以根據多數類進行回歸預測，同樣，KNN回歸取5個最近點的平均值。
  • R語言--鄰近算法KNN
    ❝KNN(k鄰近算法)是機器學習算法中常見的用於分類或回歸的算法。它簡單，訓練數據快，對數據分布沒有要求，使它成為機器學習中使用頻率較高的算法，並且，在深度學習大行其道的今天，傳統可解釋的簡單模型在工業大數據領域的應用更為廣泛。本文介紹KNN算法的基本原理和用R代碼實現。
  • 數據驅動優化:如何利用 KNN 算法驅動產品優化?
    在網際網路行業中常常有利用數據分析或者數據挖掘的結論來應用到產品中，驅動產品的優化，提升產品的各項KPI 指標， 在數據挖掘和數據分析的背後會涉及到一些數據挖掘或者機器學習的算法。本文主要是knn算法原理的介紹，以及在它在網際網路行業中的具體應用，後續會介紹這個算法的具體實現(R 語言和python 語言)。
  • 機器學習(二)-------KNN算法的sklearn KNN實踐
    前面說到過，通過調整 K 值，算法會有不同的效果。- weights（權重）：最普遍的 KNN 算法無論距離如何，權重都一樣，但有時候我們想搞點特殊化，比如距離更近的點讓它更加重要。這時候就需要 weight 這個參數了，這個參數有三個可選參數的值，決定了如何分配權重。參數選項如下： • 'uniform'：不管遠近權重都一樣，就是最普通的 KNN 算法的形式。
  • 圖像識別之KNN算法的理解與應用
    KNN是最經典的機器學習算法之一。
  • 聚類(三):KNN算法(R語言)
    k最臨近（KNN）算法是最簡單的分類算法之一，屬於有監督的機器學習算法。
  • KNN算法(三)-sklearn實現
    上篇講到KNN算法的實例。在python中sklearn庫可直接實現KNN算法。本篇介紹運用sklearn庫實現KNN算法。
  • Sk-learn之KNN算法綜合實戰
    前面幾篇文章我們通過幾個小案例熟悉了在Python中使用sklearn模塊來用做機器學習項目的一般步驟，並通過機器學習中最簡單的KNN算法進行演示。下面我們就在來一遍聲明模型+訓練+預測並輸出算法在test數據集上的準確率。
  • 機器學習之KNN分類算法介紹: Stata和R同步實現(附數據和代碼)
    7機器學習和大數據計量經濟學, 你必須閱讀一下這篇，8機器學習與Econometrics的書籍推薦, 值得擁有的經典，9機器學習在微觀計量的應用最新趨勢: 大數據和因果推斷，10機器學習第一書, 數據挖掘, 推理和預測，11Top,
  • 圖像識別之KNN算法的理解與應用(2)
    如下圖所示，每個bin文件包含10000*3073個字節數據，在每個3073數據塊中，第一個字節是0~9的標籤，後面3072位元組則是彩色圖像的三通道數據：紅通道 --> 綠通道 --> 藍通道 (1024 --> 1024 --> 1024)。
  • R語言實現K最近鄰算法(KNN)
    例如西紅柿和四季豆之間的距離為：d(西紅柿,四季豆)=√(6−3)2+(4−7)2=4.2d(西紅柿,四季豆)=(6−3)2+(4−7)2=4.2根據以上算法，我們分別計算了西紅柿和葡萄、四季豆、堅果、橙子之間的距離，分別是2.2、4.2、3.6、1.4。我們發現西紅柿和橙子之間的距離最短，那麼我們據此認為西紅柿是一種水果。
  • 機器學習:基於Knn算法的用戶屬性判斷方案設計
    本文作者通過Knn算法進行了一次用戶判斷預測的流程，文章為作者根據自身經驗所做出的總結，希望通過此文能夠加深你對Knn算法的認識。knn算法簡介K最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。
  • kNN算法量化交易初試
    這一篇簡單地聊一聊kNN算法在股票選擇上的一些應用。kNN算是一個簡單易用的監督學習分類算法，可以比較容易地用在一些特徵矩陣維度不高的數據集上來對target variable進行分類。最近因為在面試一個風控策略算法的崗位，複習了一下分類問題的算法，於是突發奇想拿kNN來分類股票策略，發現 Google 和知網上早就有了相關的paper。
  • 機器學習之KNN檢測惡意流量
    概念算法分類解決什麼問題分類算法是什麼回歸算法是多少聚類算法怎麼分數據降維怎麼壓強化學習怎麼做目的通過機器學習的方式識別惡意流量特徵工程使用sklearn的TFIDF、2ngram進行分詞什麼是TF-IDFTF-IDF是一種統計方法，用以評估一字詞對於一個文件集或一個語料庫中的其中一份文件的重要程度。
  • 基於KNN和Kmeans算法利用MNIST數據集實現手寫數字識別
    在KNN中我們的目的是求前K大的或者前K小的元素，實際上有一個比較好的算法，叫做BFPTR算法，又稱為中位數的中位數算法，它的最壞時間複雜度為O(n)，它是由Blum、Floyd、Pratt、Tarjan、Rivest 提出。該算法的思想是修改快速選擇算法的主元選取方法，提高算法在最壞情況下的時間複雜度。
  • 如何選擇最佳的最近鄰算法
    ，在自定義數據集上選擇最快，最準確的ANN算法KNN相比，具有380倍的速度，同時提供了99.3％的相同結果。為了測試更多的算法，我們整理了幾種ANN算法，例如作為數據科學家，我我們這裡將制定一個數據驅動型決策來決定那種算法適合我們的數據。
  • 教你學Python26-knn臨近算法
    工作原理： 存在一個樣本數據集合，也稱作為訓練樣本集，並且樣本集中每個數據都存在標籤，即我們知道樣本集中每一個數據與所屬分類的對應關係。輸入沒有標籤的新數據後，將新的數據的每個特徵與樣本集中數據對應的特徵進行比較，然後算法提取樣本最相似數據(最近鄰)的分類標籤。一般來說，我們只選擇樣本數據集中前k個最相似的數據，這就是k-近鄰算法中k的出處，通常k是不大於20的整數。