k近鄰算法的介紹
k近鄰算法是一種基本的分類和回歸方法，這里只實現分類的k近鄰算法。
k近鄰算法的輸入為實例的特征向量，對應特征空間的點；輸出為實例的類別，可以取多類。
k近鄰算法不具有顯式的學習過程，實際上k近鄰算法是利用訓練數據集對特征向量空間進行劃分。將劃分的空間模型作為其分類模型。
k近鄰算法的三要素
下面對三要素進行一下說明：
1.歐氏距離即歐幾里得距離，高中數學中用來計算點和點間的距離公式；
2.k值選擇：k值選擇會對k近鄰法結果產生重大影響，如果選擇較小的k值，相當于在較小的鄰域中訓練實例進行預測，這樣有點是“近似誤差”會減小，即只與輸入實例較近（相似）的訓練實例才會起作用，缺點是“估計誤差”會增大，即對近鄰的實例點很敏感。而k值過大則相反。實際中取較小的k值通過交叉驗證的方法取最優k值。
3.k近鄰法的分類決策規則往往采用多數表決的方式，這等價于“經驗風險最小化”。
k近鄰算法的實現：kd樹
實現k近鄰法是要考慮的主要問題是如何退訓練數據進行快速的k近鄰搜索，當訓練實例數很大是顯然通過一般的線性搜索方式效率低下，因此為了提高搜索效率，需要構造特殊的數據結構對訓練實例進行存儲。kd樹就是一種不錯的數據結構，可以大大提高搜索效率。
本質商kd樹是對k維空間的一個劃分，構造kd樹相當與使用垂直于坐標軸的超平面將k維空間進行切分，構造一系列的超矩形，kd樹的每一個結點對應一個這樣的超矩形。
kd樹本質上是一棵二叉樹，當通過一定規則構造是他是平衡的。
下面是過早kd樹的算法：
以下是kd樹的python實現
準備工作
#讀取數據準備def file2matrix(filename): fr = open(filename) returnMat = [] #樣本數據矩陣 for line in fr.readlines(): line = line.strip().split('/t') returnMat.append([float(line[0]),float(line[1]),float(line[2]),float(line[3])]) return returnMat #將數據歸一化，避免數據各維度間的差異過大def autoNorm(data): #將data數據和類別拆分 data,label = np.split(data,[3],axis=1) minVals = data.min(0) #data各列的最大值 maxVals = data.max(0) #data各列的最小值 ranges = maxVals - minVals normDataSet = np.zeros(np.shape(data)) m = data.shape[0] #tile函數將變量內容復制成輸入矩陣同樣大小的矩陣 normDataSet = data - np.tile(minVals,(m,1)) normDataSet = normDataSet/np.tile(ranges,(m,1)) #拼接 normDataSet = np.hstack((normDataSet,label)) return normDataSet//數據實例40920 8.326976 0.953952 314488 7.153469 1.673904 226052 1.441871 0.805124 175136 13.147394 0.428964 138344 1.669788 0.134296 172993 10.141740 1.032955 135948 6.830792 1.213192 342666 13.276369 0.543880 367497 8.631577 0.749278 135483 12.273169 1.508053 3//每一行是一個數據實例，前三維是數據值，第四維是類別標記
樹結構定義
#構建kdTree將特征空間劃分class kd_tree: """ 定義結點 value:節點值 dimension：當前劃分的維數 left:左子樹 right:右子樹 """ def __init__(self, value): self.value = value self.dimension = None #記錄劃分的維數 self.left = None self.right = None def setValue(self, value): self.value = value #類似Java的toString()方法 def __str__(self): return str(self.value)
kd樹構造
def creat_kdTree(dataIn, k, root, deep): """ data:要劃分的特征空間（即數據集） k:表示要選擇k個近鄰 root:樹的根結點 deep:結點的深度 """ #選擇x(l)(即為第l個特征)為坐標軸進行劃分，找到x(l)的中位數進行劃分# x_L = data[:,deep%k] #這里選取第L個特征的所有數據組成一個列表 #獲取特征值中位數，這里是難點如果numpy沒有提供的話 if(dataIn.shape[0]>0): #如果該區域還有實例數據就繼續 dataIn = dataIn[dataIn[:,int(deep%k)].argsort()] #numpy的array按照某列進行排序 data1 = None; data2 = None #拿取根據xL排序的中位數的數據作為該子樹根結點的value if(dataIn.shape[0]%2 == 0): #該數據集有偶數個數據 mid = int(dataIn.shape[0]/2) root = kd_tree(dataIn[mid,:]) root.dimension = deep%k dataIn = np.delete(dataIn,mid, axis = 0) data1,data2 = np.split(dataIn,[mid], axis=0) #mid行元素分到data2中，刪除放到根結點中 elif(dataIn.shape[0]%2 == 1): mid = int((dataIn.shape[0]+1)/2 - 1) #這里出現遞歸溢出，當shape為(1,4)時出現，原因是np.delete時沒有賦值給dataIn root = kd_tree(dataIn[mid,:]) root.dimension = deep%k dataIn = np.delete(dataIn,mid, axis = 0) data1,data2 = np.split(dataIn,[mid], axis=0) #mid行元素分到data1中，刪除放到根結點中 #深度加一 deep+=1 #遞歸構造子樹 #這里犯了嚴重錯誤，遞歸調用是將root傳遞進去，造成程序混亂，應該給None root.left = creat_kdTree(data1, k, None, deep) root.right = creat_kdTree(data2, k, None, deep) return root
前序遍歷測試
#前序遍歷kd樹def preorder(kd_tree,i): print(str(kd_tree.value)+" :"+str(kd_tree.dimension)+":"+str(i)) if kd_tree.left != None: preorder(kd_tree.left,i+1) if kd_tree.right != None: preorder(kd_tree.right,i+1)
kd樹的最近鄰搜索
最近鄰搜索算法，k近鄰搜索在此基礎上實現
原理：首先找到包含目標點的葉節點；然后從該也結點出發，一次退回到父節點，不斷查找與目標點最近的結點，當確定不可能存在更近的結點是停止。
def findClosest(kdNode,closestPoint,x,minDis,i=0): """ 這里存在一個問題，當傳遞普通的不可變對象minDis時，遞歸退回第一次找到 最端距離前，minDis改變，最后結果混亂，這里傳遞一個可變對象進來。 kdNode:是構造好的kd樹。 closestPoint：是存儲最近點的可變對象，這里是array x：是要預測的實例 minDis：是當前最近距離。 """ if kdNode == None: return #計算歐氏距離 curDis = (sum((kdNode.value[0:3]-x[0:3])**2))**0.5 if minDis[0] < 0 or curDis < minDis[0] : i+=1 minDis[0] = curDis closestPoint[0] = kdNode.value[0] closestPoint[1] = kdNode.value[1] closestPoint[2] = kdNode.value[2] closestPoint[3] = kdNode.value[3] print(str(closestPoint)+" : "+str(i)+" : "+str(minDis)) #遞歸查找葉節點 if kdNode.value[kdNode.dimension] >= x[kdNode.dimension]: findClosest(kdNode.left,closestPoint,x,minDis,i) else: findClosest(kdNode.right, closestPoint, x, minDis,i) #計算測試點和分隔超平面的距離，如果相交進入另一個葉節點重復 rang = abs(x[kdNode.dimension] - kdNode.value[kdNode.dimension]) if rang > minDis[0] : return if kdNode.value[kdNode.dimension] >= x[kdNode.dimension]: findClosest(kdNode.right,closestPoint,x,minDis,i) else: findClosest(kdNode.left, closestPoint, x, minDis,i)
測試：
data = file2matrix("datingTestSet2.txt")data = np.array(data)normDataSet = autoNorm(data)sys.setrecursionlimit(10000) #設置遞歸深度為10000trainSet,testSet = np.split(normDataSet,[900],axis=0) kdTree = creat_kdTree(trainSet, 3, None, 0)newData = testSet[1,0:3]closestPoint = np.zeros(4)minDis = np.array([-1.0])findClosest(kdTree, closestPoint, newData, minDis)print(closestPoint)print(testSet[1,:])print(minDis)測試結果
[0.35118819 0.43961918 0.67110669 3. ] : 1 : [0.40348346]
[0.11482037 0.13448927 0.48293309 2. ] : 2 : [0.30404792]
[0.12227055 0.07902201 0.57826697 2. ] : 3 : [0.22272422]
[0.0645755 0.10845299 0.83274698 2. ] : 4 : [0.07066192]
[0.10020488 0.15196271 0.76225551 2. ] : 5 : [0.02546591]
[0.10020488 0.15196271 0.76225551 2. ]
[0.08959933 0.15442555 0.78527657 2. ]
[0.02546591]
k近鄰搜索實現
在最近鄰的基礎上進行改進得到：
這里的closestPoint和minDis合并，一同處理
#k近鄰搜索def findKNode(kdNode, closestPoints, x, k): """ k近鄰搜索，kdNode是要搜索的kd樹 closestPoints:是要搜索的k近鄰點集合,將minDis放入closestPoints最后一列合并 x：預測實例 minDis：是最近距離 k:是選擇k個近鄰 """ if kdNode == None: return #計算歐式距離 curDis = (sum((kdNode.value[0:3]-x[0:3])**2))**0.5 #將closestPoints按照minDis列排序,這里存在一個問題，排序后返回一個新對象 #不能將其直接賦值給closestPoints tempPoints = closestPoints[closestPoints[:,4].argsort()] for i in range(k): closestPoints[i] = tempPoints[i] #每次取最后一行元素操作 if closestPoints[k-1][4] >=10000 or closestPoints[k-1][4] > curDis: closestPoints[k-1][4] = curDis closestPoints[k-1,0:4] = kdNode.value #遞歸搜索葉結點 if kdNode.value[kdNode.dimension] >= x[kdNode.dimension]: findKNode(kdNode.left, closestPoints, x, k) else: findKNode(kdNode.right, closestPoints, x, k) #計算測試點和分隔超平面的距離，如果相交進入另一個葉節點重復 rang = abs(x[kdNode.dimension] - kdNode.value[kdNode.dimension]) if rang > closestPoints[k-1][4]: return if kdNode.value[kdNode.dimension] >= x[kdNode.dimension]: findKNode(kdNode.right, closestPoints, x, k) else: findKNode(kdNode.left, closestPoints, x, k)
測試
data = file2matrix("datingTestSet2.txt")data = np.array(data)normDataSet = autoNorm(data)sys.setrecursionlimit(10000) #設置遞歸深度為10000trainSet,testSet = np.split(normDataSet,[900],axis=0) kdTree = creat_kdTree(trainSet, 3, None, 0)newData = testSet[1,0:3]print("預測實例點："+str(newData))closestPoints = np.zeros((3,5)) #初始化參數closestPoints[:,4] = 10000.0 #給minDis列賦值findKNode(kdTree, closestPoints, newData, 3)print("k近鄰結果："+str(closestPoints))測試結果
預測實例點：[0.08959933 0.15442555 0.78527657]
k近鄰結果：[[0.10020488 0.15196271 0.76225551 2. 0.02546591]
[0.10664709 0.13172159 0.83777837 2. 0.05968697]
[0.09616206 0.20475001 0.75047289 2. 0.06153793]]
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持VEVB武林網。
新聞熱點
疑難解答
