欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Python語言描述KNN算法與Kd樹

 更新時間:2017年12月13日 14:27:40   作者:冬木遠景  
這篇文章主要介紹了Python語言描述KNN算法與Kd樹,具有一定借鑒價值,需要的朋友可以參考下。

最近鄰法和k-近鄰法

下面圖片中只有三種豆,有三個豆是未知的種類,如何判定他們的種類?

提供一種思路,即:未知的豆離哪種豆最近就認為未知豆和該豆是同一種類。由此,我們引出最近鄰算法的定義:為了判定未知樣本的類別,以全部訓練樣本作為代表點,計算未知樣本與所有訓練樣本的距離,并以最近鄰者的類別作為決策未知樣本類別的唯一依據(jù)。但是,最近鄰算法明顯是存在缺陷的,比如下面的例子:有一個未知形狀(圖中綠色的圓點),如何判斷它是什么形狀?

顯然,最近鄰算法的缺陷——對噪聲數(shù)據(jù)過于敏感,為了解決這個問題,我們可以可以把未知樣本周邊的多個最近樣本計算在內(nèi),擴大參與決策的樣本量,以避免個別數(shù)據(jù)直接決定決策結果。由此,我們引進K-最近鄰算法。K-最近鄰算法是最近鄰算法的一個延伸?;舅悸肥牵哼x擇未知樣本一定范圍內(nèi)確定個數(shù)的K個樣本,該K個樣本大多數(shù)屬于某一類型,則未知樣本判定為該類型。如何選擇一個最佳的K值取決于數(shù)據(jù)。一般情況下,在分類時較大的K值能夠減小噪聲的影響,但會使類別之間的界限變得模糊。待測樣本(綠色圓圈)既可能分到紅色三角形類,也可能分到藍色正方形類。如果k取3,從圖可見,待測樣本的3個鄰居在實線的內(nèi)圓里,按多數(shù)投票結果,它屬于紅色三角形類。但是如果k取5,那么待測樣本的最鄰近的5個樣本在虛線的圓里,按表決法,它又屬于藍色正方形類。在實際應用中,K先取一個比較小的數(shù)值,再采用交叉驗證法來逐步調(diào)整K值,最終選擇適合該樣本的最優(yōu)的K值。

KNN算法實現(xiàn) 
算法基本步驟:

1)計算待分類點與已知類別的點之間的距離

2)按照距離遞增次序排序

3)選取與待分類點距離最小的k個點

4)確定前k個點所在類別的出現(xiàn)次數(shù)

5)返回前k個點出現(xiàn)次數(shù)最高的類別作為待分類點的預測分類

  下面是一個按照算法基本步驟用python實現(xiàn)的簡單例子,根據(jù)已分類的4個樣本點來預測未知點(圖中的灰點)的分類:

from numpy import * 

# create a dataset which contains 4 samples with 2 classes 
def createDataSet(): 
  # create a matrix: each row as a sample 
  group = array([[1.0, 0.9], [1.0, 1.0], [0.1, 0.2], [0.0, 0.1]]) 
  labels = ['A', 'A', 'B', 'B'] # four samples and two classes 
  return group, labels
# classify using kNN (k Nearest Neighbors ) 
# Input:   newInput: 1 x N
#       dataSet: M x N (M samples N, features)
#       labels:  1 x M  
#       k: number of neighbors to use for comparison 
# Output:   the most popular class label  
def kNNClassify(newInput, dataSet, labels, k): 
  numSamples = dataSet.shape[0] # shape[0] stands for the num of row 
  ## step 1: calculate Euclidean distance 
  # tile(A, reps): Construct an array by repeating A reps times 
  # the following copy numSamples rows for dataSet 
  diff = tile(newInput, (numSamples, 1)) - dataSet # Subtract element-wise 
  squaredDiff = diff ** 2 # squared for the subtract 
  squaredDist = sum(squaredDiff, axis = 1) # sum is performed by row 
  distance = squaredDist ** 0.5 
  ## step 2: sort the distance 
  # argsort() returns the indices that would sort an array in a ascending order 
  sortedDistIndices = argsort(distance) 
  classCount = {} # define a dictionary (can be append element) 
  for i in xrange(k): 
    ## step 3: choose the min k distance 
    voteLabel = labels[sortedDistIndices[i]] 
    ## step 4: count the times labels occur 
    # when the key voteLabel is not in dictionary classCount, get() 
    # will return 0 
    classCount[voteLabel] = classCount.get(voteLabel, 0) + 1 
  ## step 5: the max voted class will return 
  maxCount = 0 
  for key, value in classCount.items(): 
    if value > maxCount: 
      maxCount = value 
      maxIndex = key 
  return maxIndex  
  if __name__== "__main__":  
  dataSet, labels = createDataSet() 
  testX = array([1.2, 1.0]) 
  k = 3 
  outputLabel = kNNClassify(testX, dataSet, labels, 3) 
  print "Your input is:", testX, "and classified to class: ", outputLabel 
  testX = array([0.1, 0.3]) 
  outputLabel = kNNClassify(testX, dataSet, labels, 3) 
  print "Your input is:", testX, "and classified to class: ", outputLabel

結果如下:
Your input is: [ 1.2 1. ] and classified to class: A
Your input is: [ 0.1 0.3] and classified to class: B

  OpenCV中也提供了機器學習的相關算法,其中KNN算法的最基本例子如下

import numpy as np
import matplotlib.pyplot as plt
import cv2
# Feature set containing (x,y) values of 25 known/training data
trainData = np.random.randint(0,100,(25,2)).astype(np.float32)
# Labels each one either Red or Blue with numbers 0 and 1
responses = np.random.randint(0,2,(25,1)).astype(np.float32)
# Take Red families and plot them
red = trainData[responses.ravel()==0]
plt.scatter(red[:,0],red[:,1],80,'r','^')
# Take Blue families and plot them
blue = trainData[responses.ravel()==1]
plt.scatter(blue[:,0],blue[:,1],80,'b','s')
# Testing data
newcomer = np.random.randint(0,100,(1,2)).astype(np.float32)
plt.scatter(newcomer[:,0],newcomer[:,1],80,'g','o')
knn = cv2.KNearest()
knn.train(trainData,responses) # Trains the model
# Finds the neighbors and predicts responses for input vectors.
ret, results, neighbours ,dist = knn.find_nearest(newcomer, 3)
print "result: ", results,"\n"
print "neighbours: ", neighbours,"\n"
print "distance: ", dist
plt.show()

>>> 
result: [[ 0.]]
neighbours: [[ 0. 0. 0.]]
distance: [[ 65. 145. 178.]]

可以看到KNN算法將未知點分到第0組(紅色三角形組),從上圖中也可看出3個距離未知點最近的樣本都屬于第0組,因此算法返回分類標簽也為0。

KNN算法的缺陷

觀察下面的例子,我們看到對于樣本X,通過KNN算法,我們顯然可以得到X應屬于紅點,但對于樣本Y,通過KNN算法我們似乎得到了Y應屬于藍點的結論,而這個結論直觀來看并沒有說服力。

由上面的例子可見:該算法在分類時有個重要的不足是,當樣本不平衡時,即:一個類的樣本容量很大,而其他類樣本數(shù)量很小時,很有可能導致當輸入一個未知樣本時,該樣本的K個鄰居中大數(shù)量類的樣本占多數(shù)。 但是這類樣本并不接近目標樣本,而數(shù)量小的這類樣本很靠近目標樣本。這個時候,我們有理由認為該位置樣本屬于數(shù)量小的樣本所屬的一類,但是,KNN卻不關心這個問題,它只關心哪類樣本的數(shù)量最多,而不去把距離遠近考慮在內(nèi),因此,我們可以采用權值的方法來改進。和該樣本距離小的鄰居權值大,和該樣本距離大的鄰居權值則相對較小,由此,將距離遠近的因素也考慮在內(nèi),避免因一個樣本過大導致誤判的情況。

  從算法實現(xiàn)的過程可以發(fā)現(xiàn),該算法存兩個嚴重的問題,第一個是需要存儲全部的訓練樣本,第二個是計算量較大,因為對每一個待分類的樣本都要計算它到全體已知樣本的距離,才能求得它的K個最近鄰點。KNN算法的改進方法之一是分組快速搜索近鄰法。其基本思想是:將樣本集按近鄰關系分解成組,給出每組質(zhì)心的位置,以質(zhì)心作為代表點,和未知樣本計算距離,選出距離最近的一個或若干個組,再在組的范圍內(nèi)應用一般的KNN算法。由于并不是將未知樣本與所有樣本計算距離,故該改進算法可以減少計算量,但并不能減少存儲量。

KD樹

  實現(xiàn)k近鄰法時,主要考慮的問題是如何對訓練數(shù)據(jù)進行快速k近鄰搜索。這在特征空間的維數(shù)大及訓練數(shù)據(jù)容量大時尤其必要。k近鄰法最簡單的實現(xiàn)是線性掃描(窮舉搜索),即要計算輸入實例與每一個訓練實例的距離。計算并存儲好以后,再查找K近鄰。當訓練集很大時,計算非常耗時。為了提高kNN搜索的效率,可以考慮使用特殊的結構存儲訓練數(shù)據(jù),以減小計算距離的次數(shù)。

  kd樹(K-dimension tree)是一種對k維空間中的實例點進行存儲以便對其進行快速檢索的樹形數(shù)據(jù)結構。kd樹是是一種二叉樹,表示對k維空間的一個劃分,構造kd樹相當于不斷地用垂直于坐標軸的超平面將K維空間切分,構成一系列的K維超矩形區(qū)域。kd樹的每個結點對應于一個k維超矩形區(qū)域。利用kd樹可以省去對大部分數(shù)據(jù)點的搜索,從而減少搜索的計算量。

對一個三維空間,kd樹按照一定的劃分規(guī)則把這個三維空間劃分了多個空間,如下圖所示

類比“二分查找”:給出一組數(shù)據(jù):[9 1 4 7 2 5 0 3 8],要查找8。如果挨個查找(線性掃描),那么將會把數(shù)據(jù)集都遍歷一遍。而如果排一下序那數(shù)據(jù)集就變成了:[0 1 2 3 4 5 6 7 8 9],按前一種方式我們進行了很多沒有必要的查找,現(xiàn)在如果我們以5為分界點,那么數(shù)據(jù)集就被劃分為了左右兩個“簇” [0 1 2 3 4]和[6 7 8 9]。因此,根本久沒有必要進入第一個簇,可以直接進入第二個簇進行查找。把二分查找中的數(shù)據(jù)點換成k維數(shù)據(jù)點,這樣的劃分就變成了用超平面對k維空間的劃分??臻g劃分就是對數(shù)據(jù)點進行分類,“挨得近”的數(shù)據(jù)點就在一個空間里面。

  構造kd樹的方法如下:構造根結點,使根結點對應于K維空間中包含所有實例點的超矩形區(qū)域;通過下面的遞歸的方法,不斷地對k維空間進行切分,生成子結點。在超矩形區(qū)域上選擇一個坐標軸和在此坐標軸上的一個切分點,確定一個超平面,這個超平面通過選定的切分點并垂直于選定的坐標軸,將當前超矩形區(qū)域切分為左右兩個子區(qū)域(子結點);這時,實例被分到兩個子區(qū)域,這個過程直到子區(qū)域內(nèi)沒有實例時終止(終止時的結點為葉結點)。在此過程中,將實例保存在相應的結點上。通常,循環(huán)的擇坐標軸對空間切分,選擇訓練實例點在坐標軸上的中位數(shù)為切分點,這樣得到的kd樹是平衡的(平衡二叉樹:它是一棵空樹,或其左子樹和右子樹的深度之差的絕對值不超過1,且它的左子樹和右子樹都是平衡二叉樹)。 

  KD樹中每個節(jié)點是一個向量,和二叉樹按照數(shù)的大小劃分不同的是,KD樹每層需要選定向量中的某一維,然后根據(jù)這一維按左小右大的方式劃分數(shù)據(jù)。在構建KD樹時,關鍵需要解決2個問題:(1)選擇向量的哪一維進行劃分;(2)如何劃分數(shù)據(jù)。第一個問題簡單的解決方法可以是選擇隨機選擇某一維或按順序選擇,但是更好的方法應該是在數(shù)據(jù)比較分散的那一維進行劃分(分散的程度可以根據(jù)方差來衡量)。好的劃分方法可以使構建的樹比較平衡,可以每次選擇中位數(shù)來進行劃分,這樣問題2也得到了解決。

  構造平衡kd樹算法:

輸入:kk維空間數(shù)據(jù)集T={x1,x2,...,xN},其中

輸出:kd樹

(1)開始:構造根結點,根結點對應于包含T的k維空間的超矩形區(qū)域。選擇x(1)x(1)為坐標軸,以T中所有實例的x(1)x(1)坐標的中位數(shù)為切分點,將根結點對應的超矩形區(qū)域切分為兩個子區(qū)域。切分由通過切分點并與坐標軸x(1)x(1)垂直的超平面實現(xiàn)。由根結點生成深度為1的左、右子結點:左子結點對應坐標x(1)x(1)小于切分點的子區(qū)域,右子結點對應于坐標x(1)x(1)大于切分點的子區(qū)域。將落在切分超平面上的實例點保存在根結點。

(2)重復。對深度為j的結點,選擇x(l)x(l)為切分的坐標軸,l=j%k+1l=j%k+1,以該結點的區(qū)域中所有實例的x(l)x(l)坐標的中位數(shù)為切分點,將該結點對應的超矩形區(qū)域切分為兩個子區(qū)域。切分由通過切分點并與坐標軸x(l)x(l)垂直的超平面實現(xiàn)。由該結點生成深度為j+1的左、右子結點:左子結點對應坐標x(l)x(l)小于切分點的子區(qū)域,右子結點對應坐標x(l)x(l)大于切分點的子區(qū)域。將落在切分超平面上的實例點保存在該結點。

  下面用一個簡單的2維平面上的例子來進行說明。

  例. 給定一個二維空間數(shù)據(jù)集:T={(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)}T={(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},構造一個平衡kd樹。

  解:根結點對應包含數(shù)據(jù)集T的矩形,選擇x(1)x(1)軸,6個數(shù)據(jù)點的x(1)x(1)坐標中位數(shù)是6,這里選最接近的(7,2)點,以平面x(1)=7x(1)=7將空間分為左、右兩個子矩形(子結點);接著左矩形以x(2)=4x(2)=4分為兩個子矩形(左矩形中{(2,3),(5,4),(4,7)}點的x(2)x(2)坐標中位數(shù)正好為4),右矩形以x(2)=6x(2)=6分為兩個子矩形,如此遞歸,最后得到如下圖所示的特征空間劃分和kd樹。

下面的代碼用遞歸的方式構建了kd樹,通過前序遍歷可以進行驗證。這里只是簡單地采用坐標輪換方式選取分割軸,為了更高效的分割空間,也可以計算所有數(shù)據(jù)點在每個維度上的數(shù)值的方差,然后選擇方差最大的維度作為當前節(jié)點的劃分維度。方差越大,說明這個維度上的數(shù)據(jù)越不集中(稀疏、分散),也就說明了它們就越不可能屬于同一個空間,因此需要在這個維度上進行劃分。

# -*- coding: utf-8 -*-
#from operator import itemgetter
import sys
reload(sys)
sys.setdefaultencoding('utf8')
# kd-tree每個結點中主要包含的數(shù)據(jù)結構如下 
class KdNode(object):
  def __init__(self, dom_elt, split, left, right):
    self.dom_elt = dom_elt # k維向量節(jié)點(k維空間中的一個樣本點)
    self.split = split   # 整數(shù)(進行分割維度的序號)
    self.left = left    # 該結點分割超平面左子空間構成的kd-tree
    self.right = right   # 該結點分割超平面右子空間構成的kd-tree
class KdTree(object):
  def __init__(self, data):
    k = len(data[0]) # 數(shù)據(jù)維度
    
    def CreateNode(split, data_set): # 按第split維劃分數(shù)據(jù)集exset創(chuàng)建KdNode
      if not data_set:  # 數(shù)據(jù)集為空
        return None
      # key參數(shù)的值為一個函數(shù),此函數(shù)只有一個參數(shù)且返回一個值用來進行比較
      # operator模塊提供的itemgetter函數(shù)用于獲取對象的哪些維的數(shù)據(jù),參數(shù)為需要獲取的數(shù)據(jù)在對象中的序號
      #data_set.sort(key=itemgetter(split)) # 按要進行分割的那一維數(shù)據(jù)排序
      data_set.sort(key=lambda x: x[split])
      split_pos = len(data_set) // 2   # //為Python中的整數(shù)除法
      median = data_set[split_pos]    # 中位數(shù)分割點       
      split_next = (split + 1) % k    # cycle coordinates      
      # 遞歸的創(chuàng)建kd樹
      return KdNode(median, split, 
             CreateNode(split_next, data_set[:split_pos]),   # 創(chuàng)建左子樹
             CreateNode(split_next, data_set[split_pos + 1:])) # 創(chuàng)建右子樹                
    self.root = CreateNode(0, data)     # 從第0維分量開始構建kd樹,返回根節(jié)點
# KDTree的前序遍歷
def preorder(root): 
  print root.dom_elt 
  if root.left:   # 節(jié)點不為空
    preorder(root.left) 
  if root.right: 
    preorder(root.right) 
if __name__ == "__main__":
  data = [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]]
  kd = KdTree(data)
  preorder(kd.root)

進行前序遍歷(前序遍歷首先訪問根結點然后遍歷左子樹,最后遍歷右子樹)的結果如下,可見已經(jīng)正確構建了kd樹:

搜索kd樹

  利用kd樹可以省去對大部分數(shù)據(jù)點的搜索,從而減少搜索的計算量。下面以搜索最近鄰點為例加以敘述:給定一個目標點,搜索其最近鄰,首先找到包含目標點的葉節(jié)點;然后從該葉結點出發(fā),依次回退到父結點;不斷查找與目標點最近鄰的結點,當確定不可能存在更近的結點時終止。這樣搜索就被限制在空間的局部區(qū)域上,效率大為提高。

  用kd樹的最近鄰搜索:  
輸入: 已構造的kd樹;目標點xx;
輸出:xx的最近鄰。

(1) 在kd樹中找出包含目標點xx的葉結點:從根結點出發(fā),遞歸的向下訪問kd樹。若目標點當前維的坐標值小于切分點的坐標值,則移動到左子結點,否則移動到右子結點。直到子結點為葉結點為止;

(2) 以此葉結點為“當前最近點”;

(3) 遞歸的向上回退,在每個結點進行以下操作:

 ?。╝) 如果該結點保存的實例點比當前最近點距目標點更近,則以該實例點為“當前最近點”;

 ?。╞) 當前最近點一定存在于該結點一個子結點對應的區(qū)域。檢查該子結點的父結點的另一個子結點對應的區(qū)域是否有更近的點。具體的,檢查另一個子結點對應的區(qū)域是否與以目標點為球心、以目標點與“當前最近點”間的距離為半徑的超球體相交。如果相交,可能在另一個子結點對應的區(qū)域內(nèi)存在距離目標更近的點,移動到另一個子結點。接著,遞歸的進行最近鄰搜索。如果不相交,向上回退。

(4) 當回退到根結點時,搜索結束。最后的“當前最近點”即為xx的最近鄰點。

  以先前構建好的kd樹為例,查找目標點(3,4.5)的最近鄰點。同樣先進行二叉查找,先從(7,2)查找到(5,4)節(jié)點,在進行查找時是由y = 4為分割超平面的,由于查找點為y值為4.5,因此進入右子空間查找到(4,7),形成搜索路徑:(7,2)→(5,4)→(4,7),?。?,7)為當前最近鄰點。以目標查找點為圓心,目標查找點到當前最近點的距離2.69為半徑確定一個紅色的圓。然后回溯到(5,4),計算其與查找點之間的距離為2.06,則該結點比當前最近點距目標點更近,以(5,4)為當前最近點。用同樣的方法再次確定一個綠色的圓,可見該圓和y = 4超平面相交,所以需要進入(5,4)結點的另一個子空間進行查找。(2,3)結點與目標點距離為1.8,比當前最近點要更近,所以最近鄰點更新為(2,3),最近距離更新為1.8,同樣可以確定一個藍色的圓。接著根據(jù)規(guī)則回退到根結點(7,2),藍色圓與x=7的超平面不相交,因此不用進入(7,2)的右子空間進行查找。至此,搜索路徑回溯完,返回最近鄰點(2,3),最近距離1.8。

如果實例點是隨機分布的,kd樹搜索的平均計算復雜度是O(logN)O(logN),這里N是訓練實例數(shù)。kd樹更適用于訓練實例數(shù)遠大于空間維數(shù)時的k近鄰搜索。當空間維數(shù)接近訓練實例數(shù)時,它的效率會迅速下降,幾乎接近線性掃描。

下面的代碼對構建好的kd樹進行搜索,尋找與目標點最近的樣本點:

from math import sqrt
from collections import namedtuple
# 定義一個namedtuple,分別存放最近坐標點、最近距離和訪問過的節(jié)點數(shù)
result = namedtuple("Result_tuple", "nearest_point nearest_dist nodes_visited") 
def find_nearest(tree, point):
  k = len(point) # 數(shù)據(jù)維度
  def travel(kd_node, target, max_dist):
    if kd_node is None:   
      return result([0] * k, float("inf"), 0) # python中用float("inf")和float("-inf")表示正負無窮 
    nodes_visited = 1    
    s = kd_node.split    # 進行分割的維度
    pivot = kd_node.dom_elt # 進行分割的“軸”    
    if target[s] <= pivot[s]:      # 如果目標點第s維小于分割軸的對應值(目標離左子樹更近)
      nearer_node = kd_node.left   # 下一個訪問節(jié)點為左子樹根節(jié)點
      further_node = kd_node.right  # 同時記錄下右子樹
    else:                # 目標離右子樹更近
      nearer_node = kd_node.right  # 下一個訪問節(jié)點為右子樹根節(jié)點
      further_node = kd_node.left 
    temp1 = travel(nearer_node, target, max_dist) # 進行遍歷找到包含目標點的區(qū)域    
    nearest = temp1.nearest_point    # 以此葉結點作為“當前最近點”
    dist = temp1.nearest_dist      # 更新最近距離    
    nodes_visited += temp1.nodes_visited 
    if dist < max_dist:   
      max_dist = dist  # 最近點將在以目標點為球心,max_dist為半徑的超球體內(nèi)
    temp_dist = abs(pivot[s] - target[s])  # 第s維上目標點與分割超平面的距離
    if max_dist < temp_dist:        # 判斷超球體是否與超平面相交
      return result(nearest, dist, nodes_visited) # 不相交則可以直接返回,不用繼續(xù)判斷 
    #---------------------------------------------------------------------- 
    # 計算目標點與分割點的歐氏距離 
    temp_dist = sqrt(sum((p1 - p2) ** 2 for p1, p2 in zip(pivot, target)))   
    if temp_dist < dist:     # 如果“更近”
      nearest = pivot     # 更新最近點
      dist = temp_dist     # 更新最近距離
      max_dist = dist     # 更新超球體半徑
    
    # 檢查另一個子結點對應的區(qū)域是否有更近的點
    temp2 = travel(further_node, target, max_dist) 
    nodes_visited += temp2.nodes_visited
    if temp2.nearest_dist < dist:    # 如果另一個子結點內(nèi)存在更近距離
      nearest = temp2.nearest_point  # 更新最近點
      dist = temp2.nearest_dist    # 更新最近距離
    return result(nearest, dist, nodes_visited)
  return travel(tree.root, point, float("inf")) # 從根節(jié)點開始遞歸

下面結合前面寫的代碼來進行一下測試:

from time import clock
from random import random
# 產(chǎn)生一個k維隨機向量,每維分量值在0~1之間
def random_point(k):
  return [random() for _ in range(k)]
 # 產(chǎn)生n個k維隨機向量 
def random_points(k, n):
  return [random_point(k) for _ in range(n)]    
   if __name__ == "__main__":
  data = [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]] # samples
    kd = KdTree(data)
    ret = find_nearest(kd, [3,4.5])
  print ret
  N = 400000
  t0 = clock()
  kd2 = KdTree(random_points(3, N))      # 構建包含四十萬個3維空間樣本點的kd樹
  ret2 = find_nearest(kd2, [0.1,0.5,0.8])   # 四十萬個樣本點中尋找離目標最近的點
  t1 = clock()
  print "time: ",t1-t0, "s"
  print ret2

結果如下圖所示。先是測試了之前例子中距離(3,4.5)最近的點,可以看出正確返回了最近點(2,3)以及最近距離。然后隨機生成了四十萬個三維空間樣本點,并構建kd樹,然后搜索離(0.1,0.5,0.8)最近的樣本點,并測試用時。為了進行對比我先是使用numpy算出全部四十萬個距離后尋找最近點,結果耗時0.5s左右!?。≡趺茨苓@么快(⊙▽⊙),然后不用numpy自己在python中計算全部距離,結果耗時2s左右,還是比自己寫的KD樹要快得多...

可能是這種使用遞歸方式創(chuàng)建和搜索的kd樹本身效率就不是很高(知乎:為什么說遞歸效率低?)。而且深層遞歸一定要盡量避免,一是不安全,容易導致棧溢出;二是調(diào)用代價高(遞歸函數(shù)調(diào)用的代價)。可以考慮轉(zhuǎn)換為循環(huán)結構。循環(huán)結構的kd樹實現(xiàn)參考:KDTree example in scipy

總結

以上就是本文關于Python語言描述KNN算法與Kd樹的全部內(nèi)容,希望對大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關專題。如有不足之處,歡迎留言指出。感謝朋友們對本站的支持!

相關文章

  • Python Socket傳輸文件示例

    Python Socket傳輸文件示例

    這篇文章主要介紹了Python Socket傳輸文件示例,發(fā)送端可以不停的發(fā)送新文件,接收端可以不停的接收新文件。有興趣的可以了解一下。
    2017-01-01
  • python爬取淘寶商品銷量信息

    python爬取淘寶商品銷量信息

    這篇文章主要為大家詳細介紹了python爬取淘寶商品的銷量信息,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-11-11
  • 如何解決tensorflow恢復模型的特定值時出錯

    如何解決tensorflow恢復模型的特定值時出錯

    今天小編就為大家分享一篇如何解決tensorflow恢復模型的特定值時出錯,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-02-02
  • 詳解python中的生成器、迭代器、閉包、裝飾器

    詳解python中的生成器、迭代器、閉包、裝飾器

    這篇文章主要介紹了python中的生成器、迭代器、閉包、裝飾器的相關知識,非常不錯,具有一定的參考借鑒價值,需要的朋友可以參考下
    2019-08-08
  • Python閉包之返回函數(shù)的函數(shù)用法示例

    Python閉包之返回函數(shù)的函數(shù)用法示例

    這篇文章主要介紹了 Python閉包之返回函數(shù)的函數(shù)用法示例,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2018-01-01
  • Python模仿POST提交HTTP數(shù)據(jù)及使用Cookie值的方法

    Python模仿POST提交HTTP數(shù)據(jù)及使用Cookie值的方法

    這篇文章主要介紹了Python模仿POST提交HTTP數(shù)據(jù)及使用Cookie值的方法,通過兩種不同的實現(xiàn)方法較為詳細的講述了HTTP數(shù)據(jù)通信及cookie的具體用法,需要的朋友可以參考下
    2014-11-11
  • Django如何批量創(chuàng)建Model

    Django如何批量創(chuàng)建Model

    將測試數(shù)據(jù)全部敲入數(shù)據(jù)庫非常繁瑣,這篇文章主要介紹了Django如何批量創(chuàng)建Model,幫助大家快速錄入數(shù)據(jù),感興趣的朋友可以了解下
    2020-09-09
  • Python3中urlopen()的用法解讀

    Python3中urlopen()的用法解讀

    這篇文章主要介紹了Python3中urlopen()的用法解讀,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2023-03-03
  • python tkinter控件treeview的數(shù)據(jù)列表顯示的實現(xiàn)示例

    python tkinter控件treeview的數(shù)據(jù)列表顯示的實現(xiàn)示例

    本文主要介紹了python tkinter控件treeview的數(shù)據(jù)列表顯示的實現(xiàn)示例,文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-01-01
  • python中的信號通信 blinker的使用小結

    python中的信號通信 blinker的使用小結

    信號是一種通知或者說通信的方式,信號分為發(fā)送方和接收方,信號的特點就是發(fā)送端通知訂閱者發(fā)生了什么,今天通過本文給大家介紹python中的信號通信 blinker的相關知識,感興趣的朋友一起看看吧
    2021-10-10

最新評論