最近鄰法和k-近鄰法
　　下面圖片中只有三種豆，有三個豆是未知的種類，如何判定他們的種類？

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

顯然，最近鄰算法的缺陷——對噪聲數(shù)據(jù)過于敏感，為了解決這個問題，我們可以可以把未知樣本周邊的多個最近樣本計算在內(nèi)，擴大參與決策的樣本量，以避免個別數(shù)據(jù)直接決定決策結(jié)果。由此，我們引進K-最近鄰算法。K-最近鄰算法是最近鄰算法的一個延伸。
　　
基本思路是：
　　選擇未知樣本一定范圍內(nèi)確定個數(shù)的K個樣本，該K個樣本大多數(shù)屬于某一類型，則未知樣本判定為該類型。如何選擇一個最佳的K值取決于數(shù)據(jù)。一般情況下，在分類時較大的K值能夠減小噪聲的影響，但會使類別之間的界限變得模糊。待測樣本（綠色圓圈）既可能分到紅色三角形類，也可能分到藍色正方形類。如果k取3，從圖可見，待測樣本的3個鄰居在實線的內(nèi)圓里，按多數(shù)投票結(jié)果，它屬于紅色三角形類。但是如果k取5，那么待測樣本的最鄰近的5個樣本在虛線的圓里，按表決法，它又屬于藍色正方形類。在實際應(yīng)用中，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ù)最高的類別作為待分類點的預(yù)測分類

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

KNN.py代碼如下：

#-*- encoding:utf-8 -*- import sys reload(sys) sys.setdefaultencoding('utf-8') from numpy import * # create a dataset which contains 4 samples with 2 classes # # 算法基本步驟（☆☆☆☆☆☆☆☆）： # 1）計算待分類點與已知類別的點之間的距離 # 2）按照距離遞增次序排序 # 3）選取與待分類點（這個也就是測試集）距離最小的k個點 # 4）確定前k個點所在各自類別的出現(xiàn)次數(shù) # 5）返回前k個點出現(xiàn)次數(shù)最高的類別作為待分類點的預(yù)測分類 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'] # 這里是在給訓(xùn)練集打標簽 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): #labels是個列表print "dataSet=",dataSet#dataSet這里就是訓(xùn)練集print"newInput=",newInput#newInput這里就是測試集（這里比較特殊，只有一個數(shù)據(jù)）numSamples = dataSet.shape[0] # shape[0]用來讀取矩陣第一維的長度print"dataSet.shape[0]=",dataSet.shape[0] ## 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 # 測試數(shù)據(jù)與訓(xùn)練集中的每個點的差值的平方，這些平方組成的一個數(shù)組 print"-"*50print"squareDiff=",squaredDiffprint"-"*50squaredDist = sum(squaredDiff, axis = 1) # 將矩陣的每一行向量相加，也即是說x^2+y^2print"squaredDist=",squaredDistdistance = squaredDist ** 0.5 #這里是在計算平方根 print"distance=",distance## step 2: sort the distance # argsort() returns the indices that would sort an array in a ascending order sortedDistIndices = argsort(distance)print"sortedDistIndices=",sortedDistIndices#根據(jù)被測點與測試集中各個點的距離的不同進行排序。################################################################### classCount = {} # define a dictionary (can be append element) for i in xrange(k): #這里應(yīng)該是取得前面k個距離最近的點。## step 3: choose the min k distance voteLabel = labels[sortedDistIndices[i]] #遍歷sortedDistIndices的前面k個點，然后獲取這k個點的分類標簽print"voteLabel=",voteLabel ## 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 #對k個數(shù)據(jù)中，具備各種抱歉的數(shù)據(jù)進行統(tǒng)計，然后寫入#上面這句話中g(shù)et(voteLabel, 0)中之所以有個0的原因是：如果指定鍵的值不在字典中返回指定值0，#如果存在，那么就當(dāng)前的鍵值+1## step 5: the max voted class will return maxCount = 0 for key, value in classCount.items(): if value > maxCount: maxCount = valuemaxIndex = key return maxIndex#這個返回的就是最大類別。最后其實就是k個最近的點中，哪個類別多，那么就被判別為哪一類。（少數(shù)服從多數(shù)） if __name__== "__main__": dataSet, labels = createDataSet() ###############第1例測試testX = array([1.2, 1.0])#查找點（1.2,1.0）待會兒查下這個預(yù)測準確嗎？k = 3 outputLabel = kNNClassify(testX, dataSet, labels, 3) print "Your input is:", testX, "and classified to class: ", outputLabel ###############第2例測試 testX = array([0.1, 0.3])#查找點（0.1,0.3） outputLabel = kNNClassify(testX, dataSet, labels, 3) print "Your input is:", testX, "and classified to class: ", outputLabel

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

OpenCV中也提供了機器學(xué)習(xí)的相關(guān)算法，其中KNN算法的最基本例子opencv_KNN.py如下：

#-*- encoding:utf-8 -*- import sys reload(sys) sys.setdefaultencoding('utf-8') 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()python==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īng)屬于紅點，但對于樣本Y，通過KNN算法我們似乎得到了Y應(yīng)屬于藍點的結(jié)論，而這個結(jié)論直觀來看并沒有說服力。

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

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

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

kd樹(K-dimension tree)是一種對k維空間中的實例點進行存儲以便對其進行快速檢索的樹形數(shù)據(jù)結(jié)構(gòu)。kd樹是是一種二叉樹，表示對k維空間的一個劃分，構(gòu)造kd樹相當(dāng)于不斷地用垂直于坐標軸的超平面將K維空間切分，構(gòu)成一系列的K維超矩形區(qū)域。kd樹的每個結(jié)點對應(yīng)于一個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維空間的劃分。空間劃分就是對數(shù)據(jù)點進行分類，“挨得近”的數(shù)據(jù)點就在一個空間里面。

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

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

構(gòu)造平衡kd樹算法：
輸入：kk維空間數(shù)據(jù)集$T=\{x_1,x_2,...,x_N\}$，其中$x_i=(x_i^{(1)},x_i^{(2)},...,x_i^{(k)}),i=1,2,...,N;$
輸出：kd樹

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

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

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

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

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

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

KdTree.py

# -*- coding: utf-8 -*- #from operator import itemgetter import sys reload(sys) sys.setdefaultencoding('utf8')# kd-tree每個結(jié)點中主要包含的數(shù)據(jù)結(jié)構(gòu)如下 class KdNode(object):def __init__(self, dom_elt, split, left, right):self.dom_elt = dom_elt # k維向量節(jié)點(k維空間中的一個樣本點)self.split = split # 整數(shù)（進行分割維度的序號），奇數(shù)層根據(jù)x來比較，偶數(shù)層根據(jù)y來比較#這里所謂的分割維度其實就是指根據(jù)當(dāng)前根節(jié)點的第幾個坐標的值來進行比大小。self.left = left # 該結(jié)點分割超平面左子空間構(gòu)成的kd-treeself.right = right # 該結(jié)點分割超平面右子空間構(gòu)成的kd-treeclass KdTree(object):def __init__(self, data):k = len(data[0]) # 數(shù)據(jù)維度，這里其實就是2def CreateNode(split, data_set): # 按第split維劃分數(shù)據(jù)集exset創(chuàng)建KdNode#這里所謂的split維度，講人話就是(x,y)的第幾個坐標，二維的話，split的值分別是0和1if 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])#根據(jù)第split個坐標進行排序，然后選“中位數(shù)”作為下一級子二叉樹的根節(jié)點print"data_set=",data_setprint"*"*50split_pos = len(data_set) // 2 # //為Python中的整數(shù)除法print"split_pos=",split_posmedian = data_set[split_pos] # 中位數(shù)分割點 print"median=",median split_next = (split + 1) % k # cycle coordinates(循環(huán)坐標)#這里循環(huán)坐標的意思是，一開始split按照從左往右的方式繼續(xù)擰比較，從第一個坐標開始比較#當(dāng)split+1等于k的時候，split_next會重新恢復(fù)到0print"split_next=",split_nextprint"-"*50# 遞歸的創(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)建右子樹#上買的代碼中，一般split_next比split_pos大一，一輪循環(huán)結(jié)束后，那么會有split_next=0,split_pos在末尾坐標的情況。self.root = CreateNode(0, data) # 從第0維分量開始構(gòu)建kd樹,返回根節(jié)點#KdTree調(diào)用了KdNode# 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)print"*"*100preorder(kd.root)

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

搜索kd樹

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

用kd樹的最近鄰搜索：　　
輸入： 已構(gòu)造的kd樹；目標點xx；
輸出：xx的最近鄰。

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

（2） 以此葉結(jié)點為“當(dāng)前最近點”；

（3） 遞歸的向上回退，在每個結(jié)點進行以下操作：

（a） 如果該結(jié)點保存的實例點比當(dāng)前最近點距目標點更近，則以該實例點為“當(dāng)前最近點”；

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

（4） 當(dāng)回退到根結(jié)點時，搜索結(jié)束。最后的“當(dāng)前最近點”即為xx的最近鄰點。

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

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

下面的代碼KdTree_search.py對構(gòu)建好的kd樹進行搜索，尋找與目標點最近的樣本點：

#-*- encoding:utf-8 -*- import sys reload(sys) sys.setdefaultencoding('utf-8') from KdTree import * #這個代碼其實是采用kd tree實現(xiàn)的是1NN，不是KNNfrom math import sqrt from collections import namedtuple# 定義一個namedtuple,分別存放最近坐標點、最近距離和訪問過的節(jié)點數(shù) result = namedtuple("Result_tuple", "nearest_point nearest_dist nodes_visited")#就是一個可以塞進去各種類型的元組 #然后括號里面的這四個其實是對象中的成員變量名（例如nearest_point） #dist，max_dist,temp_dist#這里面的nodes_visited只是起到一個統(tǒng)計的作用，沒有其他的意義。#下面算法描述來自： #https://blog.csdn.net/liqiutuoyuan/article/details/77073689# 回溯查找： # 根據(jù)得到的搜索路徑棧，棧頂?shù)脑貫椤?dāng)前最近點’， # 將該元素出棧，并計算該點與x的距離d。對于當(dāng)前棧頂?shù)脑?#xff0c; # 首先將元素出棧，以x為圓心，d為半徑畫圓，如果與該元素對應(yīng)的分割超平面相交， # 計算該元素和x的距離，如果小于d，則將該元素更新為‘當(dāng)前最近點’，d也需要更新； # 如果不相交，則繼續(xù)對搜索路徑的棧頂元素重復(fù)相同的操作。 # 同時對元素的另一半子空間對應(yīng)的子樹進行步驟2，搜索的點加入搜索路徑。（這里對應(yīng)于temp2） # 直到搜索路徑棧為空。 # 此時得到的‘當(dāng)前最近點’即為x的最鄰近點，d為最鄰近距離。#注意：理解算法的時候，要把BST的一個分支理解為一個棧def find_nearest(tree, point):k = len(point) # 數(shù)據(jù)維度def travel(kd_node, target, max_dist):#這個的target就是測試數(shù)據(jù)if kd_node!=None:print "當(dāng)前訪問節(jié)點=",kd_node.dom_eltif kd_node is None:#這里是travel的遞歸結(jié)束處，當(dāng)kd_node為空的時候，結(jié)束遞歸，同時，這里的結(jié)果會賦值給temp1和temp2return result([0] * k, float("inf"), 0) # python中用float("inf")和float("-inf")表示正負無窮nodes_visited = 1#訪問節(jié)點數(shù)量統(tǒng)計，對于實現(xiàn)這個算法而言，沒啥用。s = kd_node.split # 進行分割的維度pivot = kd_node.dom_elt # 這個應(yīng)該是中位數(shù)，同時，pivot是個列表#注意，下面的比較是建立在kd樹已經(jīng)建立完成的基礎(chǔ)上的。#經(jīng)過比較來確定哪個節(jié)點離測試點target更近if target[s] <= pivot[s]: # 如果目標點第s維小于分割軸的對應(yīng)值(目標離左子樹更近)nearer_node = kd_node.left # 下一個訪問節(jié)點為左子樹根節(jié)點further_node = kd_node.right # 同時記錄下右子樹else: # 目標離右子樹更近nearer_node = kd_node.right # 下一個訪問節(jié)點為右子樹根節(jié)點further_node = kd_node.leftprint"#########進入temp1##########"temp1 = travel(nearer_node, target, max_dist) # 進行遍歷找到包含目標點的區(qū)域，這里就是畫一個圓了。print"##########離開temp1########"nearest = temp1.nearest_point # 以此葉結(jié)點作為“當(dāng)前最近點”#這里使用一個列表來保存一個坐標dist = temp1.nearest_dist # 更新最近距離,這里的這個nearest_dist來自上面的namedtuplenodes_visited += temp1.nodes_visited #####################以上是遍歷到最下面的葉節(jié)#################################################################if dist < max_dist: max_dist = dist # 最近點將在以目標點為球心，max_dist為半徑的超球體內(nèi)#一點點縮小max_dist的上限temp_dist = abs(pivot[s] - target[s]) # 第s維上目標點與分割超平面的距離if max_dist < temp_dist: # 判斷超球體是否與超平面相交return result(nearest, dist, nodes_visited) # 不相交則可以直接返回，不用繼續(xù)判斷#這里max_dist是球體半徑，temp_dist是超平面#判斷球體與超平面是否相割的那個超平面就是根節(jié)點的切割維所在的平面。#為什么這里一會兒是歐氏距離，一會兒又是僅僅計算某個維之間的差值呢（例如兩個點之間的xi之間的差值）？ #這是因為歐式距離在整個算法中是用來修正球的半徑的，而坐標系之差是用來判斷是否相割的。#---------------------------------------------------------------------- # 計算目標點target與分割點pivot的歐氏距離 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 # 更新超球體半徑# 檢查另一個子結(jié)點對應(yīng)的區(qū)域是否有更近的點print"☆☆☆☆☆☆☆☆進入temp2☆☆☆☆☆☆☆☆☆☆☆"temp2 = travel(further_node, target, max_dist) #print"☆☆☆☆☆☆☆☆離開temp2☆☆☆☆☆☆☆☆☆☆☆"nodes_visited += temp2.nodes_visited#訪問節(jié)點數(shù)量統(tǒng)計，沒什么用if temp2.nearest_dist < dist: # 如果另一個子結(jié)點內(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__": #測試案例2data = [[2,3],[5,4],[9,6],[4,7],[8,1],[7,2]] # sampleskd = KdTree(data)#先建立一個kd樹ret = find_nearest(kd, [3,4.5])#然后再在kd樹中尋找離該點最近的點#測試案例2# N = 40# t0 = clock()# kd2 = KdTree(random_points(3, N)) # 構(gòu)建包含四十個3維空間樣本點的kd樹# ret2 = find_nearest(kd2, [0.1,0.5,0.8]) # 四十萬個樣本點中尋找離目標最近的點# t1 = clock()# print "time: ",t1-t0, "s"# print ret2#可以參考以下鏈接來理解： #http://www.cnblogs.com/eyeszjwang/articles/2429382.html

下面結(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]] # sampleskd = KdTree(data)ret = find_nearest(kd, [3,4.5])print retN = 400000t0 = clock()kd2 = KdTree(random_points(3, N)) # 構(gòu)建包含四十萬個3維空間樣本點的kd樹ret2 = find_nearest(kd2, [0.1,0.5,0.8]) # 四十萬個樣本點中尋找離目標最近的點t1 = clock()print "time: ",t1-t0, "s"print ret2

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

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

參考：

Python手寫數(shù)字識別-knn算法應(yīng)用

機器學(xué)習(xí)算法與Python實踐之（一）k近鄰（KNN）

《統(tǒng)計學(xué)習(xí)方法》 李航 第3章 k近鄰法

k-d樹算法

Kd Tree算法原理和開源實現(xiàn)代碼

KD-tree的原理以及構(gòu)建與查詢操作的python實現(xiàn)

從K近鄰算法、距離度量談到KD樹、SIFT+BBF算法

KD樹詳解及KD樹最近鄰算法

KNN之KD樹實現(xiàn)

http://rosettacode.org/wiki/K-d_tree

http://www.cnblogs.com/chuxiuhong/p/5982580.html

#############################################################################################

文章閱讀總結(jié)：

kd樹來實現(xiàn)KNN，
總的來說就是：
KNN利用Kd樹來獲取離目標點最近的k個測試點，
然后少數(shù)服從多數(shù)原則，這k個測試點中，哪一類的類別數(shù)目最多，
就認為被測試點符合該類別。

這篇文章分別講了四個代碼：
KNN.py 一般KNN算法的思想
opencv_KNN.py opencv中的KNN包的使用
KdTree.py 樹的構(gòu)建
KdTree_search.py 根據(jù)構(gòu)建的樹來尋找最近的點，并沒有找最近的k個點

文章最后沒有把“建立kd樹-在kd樹中查找最近的k個點-根據(jù)標簽預(yù)測類別”整個流程串起來實現(xiàn)一遍，而是分開實現(xiàn)的。
也就是說，文章最后實現(xiàn)的是“最近鄰”（1NN），而不是k近鄰（KNN）

總結(jié)

以上是生活随笔為你收集整理的KNN算法与Kd树（转载+代码详细解释）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。