KNN優化

• 簡介
  • 最近一個CV的論文看到作者使用了Ball tree結構的近鄰算法，加上很久沒有寫關于傳統機器學習算法的內容了，這里稍微介紹一下近鄰算法的優化方法。
  • 一般而言，除了Brute Force這種高復雜度方法，目前的近鄰算法優化方式主要兩種，即K-D tree、Ball tree，這兩種方法都是基于查詢數據結構的優化（也就是鄰居搜索方式的優化）。
  • 本案例使用鳶尾花數據集，且本案例只重點關注搜索部分，KNN原理簡單，可以查看我之前的博客。
• 算法缺陷
  • KNN是基于實例的學習，其核心思想是當前樣本的標簽為訓練樣本中最接近它的樣本的標簽，也就是說模型需要存儲所有訓練集，這非常耗費存儲空間。
  • 由于需要判斷類別的M個樣本，每個都要與N個訓練樣本計算距離（若特征D維），這會使得計算量大。$O(N?M?D)$
  • 由于基于特征距離計算類別，對特征的數據尺度非常敏感。
• 代碼說明
  • 本篇文章重點在于理論敘述而不是編碼，所以均使用sklearn封裝模塊完成編碼，具體參考官方文檔。
• Brute Force
  • 計算復雜度
    • 對于N個樣本在D維特征空間，可以認為計算復雜度為$O(D?N)$。
  • 代碼
    • def test_accuracy():"""測試鄰居尋找準確率:return:"""x_train, y_train, x_test, y_test = get_dataset()nnb = NearestNeighbors(n_neighbors=3, algorithm='brute').fit(x_train)distance, index = nnb.kneighbors([x_test[0]])print("nearest distance", distance)print("nearest index", index)print("nearest label", y_train[index])def test_time():"""測試鄰居查找時間:return:"""x_train, y_train, x_test, y_test = get_dataset()nnb = NearestNeighbors(n_neighbors=3, algorithm='brute').fit(x_train)start_time = time.time()for sample in x_test:distance, index = nnb.kneighbors([sample])end_time = time.time()print("Spend:{} s".format(end_time-start_time))
  • 運行效果
    • 可以看到，準確率還不錯，運行全部測試樣本的計算，花費了0.0139秒。
• K-D tree
  • 概念
    • K指鄰居數目
    • D指特征維度
    • tree指二叉樹
  • 原理
    • 如果我們知道A與B很接近、B與C很接近，那么可以假定A與C很接近，不用具體計算其距離。
    • 基于這種思想，利用二叉樹結構進行鄰居查詢將是一種降低運算復雜度的不錯選擇。
  • 算法描述
    • 定義樹節點的信息
      • 分裂方式(split_method)
      • 分裂點(split_point)
      • 左子樹(left_tree)
      • 右子樹(right_tree)
    • 定義樹的生成方式（樹的生成過程就是數據空間的分割過程）
      • 根據當前下標區間[L,R]（如5個樣本則為[0-4]），計算樣本集在每個特征維度上的方差，取方差最大的那一維d作為分裂方式，并且將所有樣本按照d值進行排序，取中間的樣本點mid為當前分裂節點的分裂點，然后，以生成的當前節點為父節點，[L,mid-1]和[mid+1,R]為左右子樹建樹。如此遞歸，直到區間只有一個樣本點。
      • 經過這個過程，它將數據空間分割成很多小的空間，且每個空間只有一個樣本點。
      • 舉例
        • 舉個例子，當特征只有兩維，那么可視化啊就是一個平面被分割為了很多小的平面矩形，且每個矩形只包含一個樣本點。
    • 定義樹的查詢方式
      • 查詢，也就是要找這個樣本點應該在的子空間而已。
      • 每次在二叉樹上查找時，先看節點的分裂方式是什么，也就是分裂特征是多個特征中的哪一維的特征。如果測試樣本在那個特征上的值小于分裂點的值，就在左子樹上進行查詢；如果大于分裂點的值，就在右子樹上進行查詢。
      • 子樹查詢結束，回溯到根節點，判斷，以該點為圓心，目前得到的最小距離為半徑，產生的圓區域是否相交于區間分裂那一維的平面，若相交，則需要查詢分裂平面那一側的子樹，同時，判斷能否用根節點到該點的距離更新最近距離。
      • 為什么呢
      • 所以，由于每個分裂節點都可能查詢左右子樹，查詢的復雜度可能從$O(log(n))$變為$O(\sqrt{(n)})$。
  • 特點
    • 對參數空間沿著數據特征軸N進行劃分，很高效，因為劃分過程是在N上進行，而不用管樣本維數D。
    • 只有當D很小(D<20)的時候，運算塊，當D大即特征高維時，計算會慢不少。
  • 代碼實現
    • # -*-coding:utf-8-*-from sklearn.datasets import load_irisfrom sklearn.model_selection import train_test_splitfrom sklearn.neighbors import NearestNeighborsimport timedef get_dataset():"""獲取數據集:return:"""data = load_iris()x, y = data['data'], data['target']x_train_, x_test_, y_train_, y_test_ = train_test_split(x, y, test_size=0.2, random_state=2019) # 保證運行不變性return x_train_, y_train_, x_test_, y_test_def test_accuracy():"""測試準確率:return:"""x_train, y_train, x_test, y_test = get_dataset()nnb = NearestNeighbors(n_neighbors=3, algorithm='kd_tree').fit(x_train)distance, index = nnb.kneighbors([x_test[0]])print("nearest distance", distance)print("nearest index", index)print("true label", y_test[0])print("nearest label", y_train[index])def test_time():"""測試鄰居查找時間:return:"""x_train, y_train, x_test, y_test = get_dataset()nnb = NearestNeighbors(n_neighbors=3, algorithm='kd_tree').fit(x_train)start_time = time.time()for sample in x_test:distance, index = nnb.kneighbors([sample])end_time = time.time()print("Spend:{} s".format(end_time-start_time))if __name__ == '__main__':test_accuracy()test_time()
  • 運行結果
    • 可以看到，比起Brute，KDTree查找速度快了很多。
  • 計算復雜度
    • 最好$O(D?log(N))$，當D很大時效率不如Brute。
• Ball tree
  • 概述
    • 為了改進KDtree的二叉樹樹形結構，并且沿著笛卡爾坐標進行劃分的低效率，Ball tree將在一系列相嵌套的超球體上分割數據。
    • 不同于KD Tree使用超矩形劃分區域而是使用超球面劃分。這導致在構建數據結構的花費上大于KDtree，但是在高維甚至很高維特征的數據上都表現的很高效。
  • 原理
    • Ball tree遞歸地將數據劃分為由質心C和半徑r定義的節點，使得節點中的每個點都位于由r和C定義的超球內。通過使用三角不等式來減少鄰居搜索的候選點數量的$|x+y|\le |x|+|y|$。
  • 算法描述
    • 劃分方式
      • 選擇一個距離當前圓心最遠的訓練樣本點$i_1$和距離$i_1$最遠的訓練樣本點$i_2$，將圓中所有離這兩個點最近的訓練樣本點都賦給這兩個簇的中心，然后計算每一個簇的中心點和包含所有其所屬訓練樣本點的最小半徑。
      • 這各劃分方式是線性的。
    • 查詢方式
      • 使用Ball tree時，先自上而下找到包含目標的葉子結點$(c,r)$，從此結點中找到離它最近的訓練樣本點，這個距離就是最近鄰的距離的上界。
      • 檢查它的兄弟結點中是否包含比這個上界更小的訓練樣本點。檢查方式為：如果目標點距離兄弟結點的圓心的距離 > 兄弟節點所在的圓半徑 + 之前得到的上界的值，則這個兄弟結點不可能包含所要的訓練樣本點（可以理解為構成一個三角形，兩圓必定相交）。否則，檢查這個兄弟結點是否包含符合條件的訓練樣本點。
  • 計算復雜度
    • $O(D?log(N))$
  • 代碼實現
    • # -*-coding:utf-8-*-"""author: Zhou Chendatetime: 2019/6/20 20:29desc: the project"""# -*-coding:utf-8-*-from sklearn.datasets import load_irisfrom sklearn.model_selection import train_test_splitfrom sklearn.neighbors import NearestNeighborsimport timedef get_dataset():"""獲取數據集:return:"""data = load_iris()x, y = data['data'], data['target']x_train_, x_test_, y_train_, y_test_ = train_test_split(x, y, test_size=0.2, random_state=2019) # 保證運行不變性return x_train_, y_train_, x_test_, y_test_def test_accuracy():"""測試準確率:return:"""x_train, y_train, x_test, y_test = get_dataset()nnb = NearestNeighbors(n_neighbors=3, algorithm='ball_tree').fit(x_train)distance, index = nnb.kneighbors([x_test[0]])print("nearest distance", distance)print("nearest index", index)print("true label", y_test[0])print("nearest label", y_train[index])def test_time():"""測試鄰居查找時間:return:"""x_train, y_train, x_test, y_test = get_dataset()nnb = NearestNeighbors(n_neighbors=3, algorithm='ball_tree').fit(x_train)start_time = time.time()for sample in x_test:distance, index = nnb.kneighbors([sample])end_time = time.time()print("Spend:{} s".format(end_time-start_time))if __name__ == '__main__':test_accuracy()test_time()
  • 運行結果
    • 可以看到，zcqk這是效率最高的。
• 算法選擇
  • 究竟使用哪種構建和查詢更為高效視情況而定，sklearn提供了auto方式，可以自動選擇合適的算法。
  • 選擇的依據（sklearn也是這個依據）一般根據D(特征維度)和N(數據量)的維度大小決定，具體可以參見sklearn官方文檔。
  • 當D很大時Ball tree是最優選擇。
• 補充說明
  • 具體代碼見我的Github，歡迎star或者fork。

總結

以上是生活随笔為你收集整理的机器学习进阶-优化的近邻算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。