盤點高效的KNN實現算法

2021-02-19 NLP情報局

1967年，史丹福大學的兩位研究員Cover和Hart，以《戰國策》中 「物以類聚，人以群分」的思想，提出了一種實用的機器學習算法。它的基本思想是這樣的：某家餐廳新出了一款漢堡D，不知道如何定價。參考店裡已有的商品發現：漢堡A-18元，漢堡B-22元，漢堡C-38元，可樂A-8元，可樂B-9元，薯條A-12元...

根據常識，店家知道新漢堡應該參考已有的漢堡，而不是可樂、薯條的售價（相比可樂、薯條，漢堡D與同類漢堡A/B/C的特徵更接近）。於是，他們決定暫時把新漢堡的價格定為漢堡A/B/C的平均價，26元。
這就是被稱為數據挖掘10大算法之一的K近鄰算法（KNN），利用數據集對特徵向量空間進行劃分，並作為其分類的模型。
簡單的說，假設現在有100種食品（訓練集），多數屬於某個類，就把該實例分為這個類（漢堡）。下面我們簡單介紹KNN的三要素，重點關注它的實現方法。
01 距離度量當我們通過特徵工程或神經網絡獲得了數據集和新樣本的特徵後，首先需要確定一種距離度量策略，來衡量距離的遠近。
機器學習領域常用的距離度量方法有歐式距離、餘弦距離、曼哈頓距離、dot內積等等。其中，n維特徵的a、b向量的歐式距離體現數值上的絕對差異，餘弦距離體現方向上的相對差異。對向量經過歸一化處理後，兩者的效果基本是等價的。
更多距離度量方法，可以參考：https://zhuanlan.zhihu.com/p/33694613102 K值和決策規則有了距離度量方法後，我們需要確定參數k和最終的決策規則。如果選擇較小的k值，相當於只取少量的樣本進行預測，預測結果會對近鄰的樣本點非常敏感。換句話說，k值減小意味著整體模型變得複雜，容易發生過擬合。如果選擇較大的k值，預測的樣本會更多，與實例不太相似的樣本也會參與預測，意味著整體的模型變得簡單。極端情況下，無論輸入樣本是什麼，都粗暴地預測它屬於訓練樣本中最多的類，模型過於簡單，很明顯並不可取。所以實際應用中，我們一般先設一個較小的k值，通過交叉驗證選取最優的k。
至於決策規則，對於分類而言，一般採用多數表決規則，少數服從多數。對於回歸任務，可以採用平均法則。
如果不打算將該算法實際應用的讀者，讀到這兒就可以啦。相信今後看到KNN這個詞，一定不會陌生。想將該算法予以實踐的讀者，請瀏覽到最後哦！
03 KNN實現KNN的原理非常簡單，難點在於如何實現KNN算法。受並發、時延等條件限制，高效性往往是我們實際項目中「算法落地」要考慮的重要因素。
實際上，K近鄰的實現方法多達數十種，下面將拋磚引玉，介紹幾種常用的方法。
線性掃描即暴力法。將新樣本和訓練樣本逐一比對，最終挑選距離最接近的k個樣本，時間複雜度O(n)。對於樣本數量比較少的情況，這種方法簡單穩定，已經能有不錯的效果。但是數據規模較大時，時間開銷線性上升，無法接受。KD樹KD樹是二叉樹，核心思想是對 k 維特徵空間不斷切分（假設特徵維度是100，對於0-99中的每一個維度，以中值遞歸切分）構造的樹，每一個節點是一個超矩形，小於結點的樣本劃分到左子樹，大於結點的樣本劃分到右子樹。構造完畢後，檢索時（1）從根結點出發，遞歸向下訪問KD樹。若目標點 x 當前維的坐標小於切分點的坐標，移動到左子樹，否則移動到右子樹，直到葉結點；（2）以此葉結點為「最近點」，遞歸地向上回退，查找該結點的兄弟結點中是否存在更近的點，若存在，則更新「最近點」，否則回退；（3）未到達根結點時繼續執行（2）；（4）回退到根結點時，搜索結束。KD樹在特徵維度小於20時效率最高，一般適用於訓練樣本數遠大於空間維數時的k近鄰搜索。當空間維數接近訓練實例數時，效率會迅速下降，幾乎接近線形掃描。AnnoyAnnoy，全稱「Approximate Nearest Neighbors Oh Yeah」，是一種適合實際應用的快速相似查找算法。Annoy 同樣通過建立一個二叉樹，使得每個點查找時間複雜度是O(log n)。和KD樹不同的是，Annoy沒有對k維特徵進行切分。Annoy的每一次空間劃分，可以看作聚類數為2的KMeans過程。收斂後在產生的兩個聚類中心連線之間建立一條垂線（圖中的黑線），把數據空間劃分為兩部分。在劃分的子空間內不停的迭代劃分，直到每個子空間最多只剩下k個數據節點，劃分結束。最終生成的二叉樹具有類似如下結構，二叉樹底層是葉子節點，記錄原始數據；中間節點記錄的是分割超平面的信息。查詢過程和KD樹類似，先從根向葉子結點遞歸查找，再向上回溯即可。HNSW和前幾種算法不同，HNSW（Hierarchcal Navigable Small World graphs）是基於圖存儲的數據結構。

假設我們現在有13個2維數據向量，我們把這些向量放在了一個平面直角坐標系內，隱去坐標系刻度，它們的位置關係如上圖所示。

樸素查找法：把某些點和點之間連上線，構成一個查找圖，存儲備用；當我想查找與粉色點最近的一點時，我從任意一個黑色點出發，計算它和粉色點的距離，與這個任意黑色點有連接關係的點我們稱之為「友點」（直譯），然後我要計算這個黑色點的所有「友點」與粉色點的距離，從所有「友點」中選出與粉色點最近的一個點，把這個點作為下一個進入點，繼續按照上面的步驟查找下去。

如果當前黑色點對粉色點的距離比所有「友點」都近，終止查找，這個黑色點就是我們要找的離粉色點最近的點。

https://blog.csdn.net/u011233351/article/details/85116719為了達到快速搜索的目標，HNSW在構建圖時還至少要滿足如下要求：1）圖中每個點都有「友點」；2）相近的點都互為「友點」；3）圖中所有連線的數量最少；4）配有高速公路機制的構圖法。HNSW低配版——NSW論文中配了這樣一張圖，黑線是近鄰點連線，紅線是「高速公路」，如此可以大幅減少平均搜索的路徑長度。在NSW基礎之上，HNSW加入跳表結構做了進一步優化。最底層是所有數據點，每一個點都有50%概率進入上一層的有序鍊表。這樣可以保證表層是「高速通道」，底層是精細查找。通過層狀結構，將邊按特徵半徑進行分層，使每個頂點在所有層中平均度數變為常數，從而將NSW的計算複雜度由多重對數複雜度降到了對數複雜度。關於HNSW的詳細介紹可以參考原論文[2]和博客HNSW算法理論的來龍去脈[3]。04 實驗實驗在CLUE發布的今日頭條短文本分類數據集上進行，訓練集規模：53,360條短文本。
實驗環境：Ubuntu 16.04.6，CPU：126G/20核，python 3.6requirement：scikit-learn、annoy、hnswlib、bert-as-service
實驗中使用了肖涵博士開源的bert-as-service服務預先將文本編碼為768維度的特徵向量，作為輸入特徵。距離度量統一採用歐式距離。為了方便測試，我從驗證集中隨機抽取了200條樣本，使用不同的KNN實現方法統計top1-top3的查找準確率和時間開銷。具體如下：

我們發現，Annoy算法的Top準確率相差不大，200條樣本的批量查找速度卻從之前的15秒（75ms/條）降到了0.08秒（0.4ms/條），提升了100倍以上。HNSW算法預測200條樣本耗時0.05秒（0.25ms/條），略優於Annoy。
此外，同樣的53,360條特徵向量（768維度），保存為靜態索引文件後，ann索引的大小是227MB，hnsw索引是171MB，從這一點看hnsw也略勝一籌，可以節約部分內存。實驗部分代碼可以參考：https://zhuanlan.zhihu.com/p/152522906/05 總結本文介紹了K近鄰算法，重點關注其實現方式。通過理論介紹和實驗證明，Annoy和HNSW是可以在實際業務中落地的算法。其中Bert/Sentence-Bert+HNSW的組合會有不錯的（粗排）召回效果。K近鄰算法的實現方法其實還有很多，感興趣的同學可以閱讀相關論文進一步研究。在NLP情報局公眾號後臺回復「三件套」，即可獲取深度學習三件套：《PyTorch深度學習》，《Hands-on Machine Learning》，《Python深度學習》歡 迎 關 注 👇由於微信平臺算法改版，訂閱號內容將不再以時間排序展示，如果大家想第一時間看到我們的推送，強烈建議星標我們幫我們點【在看】。星標具體步驟：
（2）點擊右上角的小點點，在彈出頁面點擊「設為星標」，就可以啦參 考 文 獻[1] K近鄰算法哪家強？KDTree、Annoy、HNSW原理和使用方法介紹：https://zhuanlan.zhihu.com/p/152522906/edit[2] Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

[3] 一文看懂HNSW算法理論的來龍去脈：

https://blog.csdn.net/u011233351/article/details/85116719

[4] 快速計算距離Annoy算法原理及Python使用：

https://blog.csdn.net/m0_37850187/article/details/92712490

原創不易，有收穫的話請幫忙點擊分享、點讚、在看吧🙏‍‍‍‍

相關焦點

  • KNN算法(三)-sklearn實現
    上篇講到KNN算法的實例。在python中sklearn庫可直接實現KNN算法。本篇介紹運用sklearn庫實現KNN算法。
  • 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算法(R語言)
    k最臨近（KNN）算法是最簡單的分類算法之一，屬於有監督的機器學習算法。
  • KNN算法中的K有多重要
    K-最近鄰（KNN）是一種有監督的機器學習算法，可用於解決分類和回歸問題。它基於一個非常簡單的想法，數據點的值由它周圍的數據點決定。考慮的數據點數量由k值確定。因此，k值是算法的核心。KNN分類器根據多數表決原則確定數據點的類別。如果k設置為5，則檢查5個最近點的類別。也可以根據多數類進行回歸預測，同樣，KNN回歸取5個最近點的平均值。
  • 機器學習之KNN分類算法介紹: Stata和R同步實現(附數據和代碼)
    （4）基於測試數據做出預測，以評估學習算法模型的性能表現。1.4 KNN算法的優點（1）簡單但強大。邏輯簡單，無需參數進行估計；易於理解，容易實現。（2）用途較多。可以出了二分類和多分類問題，也可以處理回歸的問題。多分類預測中比另外一種常見的機器算法SVM（支持向量機）通常表現更好。（3）和樸素貝葉斯等算法相比，對異常值樣本點不敏感。
  • 機器學習(二)-------KNN算法的sklearn KNN實踐
    一.Skelarn KNN參數概述要使用sklearnKNN算法進行分類，我們需要先了解sklearnKNN算法的一些基本參數，那麼這節就先介紹這些內容吧。前面說到過，通過調整 K 值，算法會有不同的效果。- weights（權重）：最普遍的 KNN 算法無論距離如何，權重都一樣，但有時候我們想搞點特殊化，比如距離更近的點讓它更加重要。這時候就需要 weight 這個參數了，這個參數有三個可選參數的值，決定了如何分配權重。參數選項如下： • 'uniform'：不管遠近權重都一樣，就是最普通的 KNN 算法的形式。
  • 圖像識別之KNN算法的理解與應用
    該算法既可以用於數據分類，也可以用於數據回歸預測，其核心思路是在訓練樣本中尋找距離最接近待分類樣本的K個樣本。然後，如果目的是分類，則統計這K個樣本中的各個類別數量，數量最多的類別即認為是待分類樣本的類別；如果目的是回歸預測，則計算這K個樣本的平均值作為預測值。圖像識別，本質上也是數據分類，也即把每一張圖像歸類，因此KNN算法可以應用於圖像識別。
  • R語言--鄰近算法KNN
    ❝KNN(k鄰近算法)是機器學習算法中常見的用於分類或回歸的算法。它簡單，訓練數據快，對數據分布沒有要求，使它成為機器學習中使用頻率較高的算法，並且，在深度學習大行其道的今天，傳統可解釋的簡單模型在工業大數據領域的應用更為廣泛。本文介紹KNN算法的基本原理和用R代碼實現。
  • Sk-learn之KNN算法綜合實戰
    前面幾篇文章我們通過幾個小案例熟悉了在Python中使用sklearn模塊來用做機器學習項目的一般步驟，並通過機器學習中最簡單的KNN算法進行演示。模型怎麼實現的理論上我們不需要關注。這樣我們就可以把主要的精力放在思考如何提高模型的預測的精度這個問題上。    sklearn中也提供一些標準化的操作來提高模型精度，例如數據歸一化、GridsearchCV尋找最優參數等。這個就是我們下面的案例將要用到的技術。
  • 「人工智慧核心之機器學習(2)」——python 實現 KNN
    歡迎大家關注公眾號【哈希大數據】1、KNN算法基本介紹K-Nearest Neighbor（k最鄰近分類算法），簡稱KNN，是最簡單的一種有監督的機器學習算法。也是一種懶惰學習算法，即開始訓練僅僅是保存所有樣本集的信息，直到測試樣本到達才開始進行分類決策。
  • 圖像識別之KNN算法的理解與應用(2)
    在上一篇文章中，我們介紹了KNN算法的原理，並詳細闡述了使用Opencv的KNN算法模塊對手寫數字圖像進行識別，發現識別的準確率還是比較高的，達到
  • 機器學習:基於Knn算法的用戶屬性判斷方案設計
    本文作者通過Knn算法進行了一次用戶判斷預測的流程，文章為作者根據自身經驗所做出的總結，希望通過此文能夠加深你對Knn算法的認識。knn算法簡介K最近鄰(k-Nearest Neighbor，KNN)分類算法，是一個理論上比較成熟的方法，也是最簡單的機器學習算法之一。
  • 機器學習算法推導&實現——k近鄰和kd樹實現
    k近鄰的實現       在k近鄰的實現中，最簡單的實現方法是線性掃描，這時需要計算輸入實例與每一個訓練實例的距離，當訓練集很大時，計算非常耗時。k近鄰的思想很簡單，但是在實現上為了減少計算複雜度，有很多方法可以提高k近鄰搜索的效率。我們就介紹並實現kd樹（kd tree）方法。
  • kNN算法量化交易初試
    這一篇簡單地聊一聊kNN算法在股票選擇上的一些應用。kNN算是一個簡單易用的監督學習分類算法，可以比較容易地用在一些特徵矩陣維度不高的數據集上來對target variable進行分類。最近因為在面試一個風控策略算法的崗位，複習了一下分類問題的算法，於是突發奇想拿kNN來分類股票策略，發現 Google 和知網上早就有了相關的paper。
  • 9種常用的機器學習算法實現
    關於算法的原理知乎上有很多精彩的回答，這裡不會贅述，僅給出代碼的實現與可視化。具體原理參考：樸素貝葉斯算法原理小結 - 劉建平Pinard，下面給出代碼的實現。具體原理參考：深入淺出理解決策樹算法（一）-核心思想 - 憶臻的文章 - 知乎，下面給出代碼的實現。
  • 數據科學經典算法 KNN 已被嫌慢,ANN 比它快 380 倍
    解決方案 將最近鄰算法擴展至大規模數據的方法是徹底避開暴力距離計算，使用 ANN 算法。 近似最近距離算法（ANN） 嚴格地講，ANN 是一種在 NN 搜索過程中允許少量誤差的算法。但在實際的 C2C 市場中，真實的鄰居數量比被搜索的 K 近鄰數量要多。與暴力 KNN 相比，人工神經網絡可以在短時間內獲得卓越的準確性。
  • 標籤傳播算法(Label Propagation)及Python實現
    二、標籤傳播算法標籤傳播算法(label propagation)的核心思想非常簡單：相似的數據應該具有相同的label。LP算法包括兩大步驟：1)構造相似矩陣;2)勇敢的傳播吧。2.1、相似矩陣構建LP算法是基於Graph的，因此我們需要先構建一個圖。
  • 數據驅動優化:如何利用 KNN 算法驅動產品優化?
    在網際網路行業中常常有利用數據分析或者數據挖掘的結論來應用到產品中，驅動產品的優化，提升產品的各項KPI 指標， 在數據挖掘和數據分析的背後會涉及到一些數據挖掘或者機器學習的算法。本文主要是knn算法原理的介紹，以及在它在網際網路行業中的具體應用，後續會介紹這個算法的具體實現(R 語言和python 語言)。
  • 機器學習算法KNN簡介及實現
    算法簡介KNN(K近鄰算法)是一種不需要學習任何參數同時也非常簡單的機器學習算法，既可以用來解決分類問題也可以用來解決回歸問題。直觀解釋這個算法就是'近朱者赤，近墨者黑'，當輸入一個新樣本時，根據與其相近的樣本值來估計新輸入的樣本。如下圖所示新輸入的樣本會被分類為W1。影響算法的幾個因子在了解算法大體的思路後，其實還有幾個問題需要繼續深究:1、如何表達兩個樣本的距離(相似度)？ 2、KNN中的K值應該如何選取？
  • 基於KNN和Kmeans算法利用MNIST數據集實現手寫數字識別
    在KNN中我們的目的是求前K大的或者前K小的元素，實際上有一個比較好的算法，叫做BFPTR算法，又稱為中位數的中位數算法，它的最壞時間複雜度為O(n)，它是由Blum、Floyd、Pratt、Tarjan、Rivest 提出。該算法的思想是修改快速選擇算法的主元選取方法，提高算法在最壞情況下的時間複雜度。