python K近鄰算法的kd樹實(shí)現(xiàn)
k近鄰算法的介紹
k近鄰算法是一種基本的分類和回歸方法,這里只實(shí)現(xiàn)分類的k近鄰算法。
k近鄰算法的輸入為實(shí)例的特征向量,對(duì)應(yīng)特征空間的點(diǎn);輸出為實(shí)例的類別,可以取多類。
k近鄰算法不具有顯式的學(xué)習(xí)過程,實(shí)際上k近鄰算法是利用訓(xùn)練數(shù)據(jù)集對(duì)特征向量空間進(jìn)行劃分。將劃分的空間模型作為其分類模型。
k近鄰算法的三要素
- k值的選擇:即分類決策時(shí)選擇k個(gè)最近鄰實(shí)例;
- 距離度量:即預(yù)測(cè)實(shí)例點(diǎn)和訓(xùn)練實(shí)例點(diǎn)間的距離,一般使用L2距離即歐氏距離;
- 分類決策規(guī)則。
下面對(duì)三要素進(jìn)行一下說明:
1.歐氏距離即歐幾里得距離,高中數(shù)學(xué)中用來計(jì)算點(diǎn)和點(diǎn)間的距離公式;
2.k值選擇:k值選擇會(huì)對(duì)k近鄰法結(jié)果產(chǎn)生重大影響,如果選擇較小的k值,相當(dāng)于在較小的鄰域中訓(xùn)練實(shí)例進(jìn)行預(yù)測(cè),這樣有點(diǎn)是“近似誤差”會(huì)減小,即只與輸入實(shí)例較近(相似)的訓(xùn)練實(shí)例才會(huì)起作用,缺點(diǎn)是“估計(jì)誤差”會(huì)增大,即對(duì)近鄰的實(shí)例點(diǎn)很敏感。而k值過大則相反。實(shí)際中取較小的k值通過交叉驗(yàn)證的方法取最優(yōu)k值。
3.k近鄰法的分類決策規(guī)則往往采用多數(shù)表決的方式,這等價(jià)于“經(jīng)驗(yàn)風(fēng)險(xiǎn)最小化”。
k近鄰算法的實(shí)現(xiàn):kd樹
實(shí)現(xiàn)k近鄰法是要考慮的主要問題是如何退訓(xùn)練數(shù)據(jù)進(jìn)行快速的k近鄰搜索,當(dāng)訓(xùn)練實(shí)例數(shù)很大是顯然通過一般的線性搜索方式效率低下,因此為了提高搜索效率,需要構(gòu)造特殊的數(shù)據(jù)結(jié)構(gòu)對(duì)訓(xùn)練實(shí)例進(jìn)行存儲(chǔ)。kd樹就是一種不錯(cuò)的數(shù)據(jù)結(jié)構(gòu),可以大大提高搜索效率。
本質(zhì)商kd樹是對(duì)k維空間的一個(gè)劃分,構(gòu)造kd樹相當(dāng)與使用垂直于坐標(biāo)軸的超平面將k維空間進(jìn)行切分,構(gòu)造一系列的超矩形,kd樹的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)這樣的超矩形。
kd樹本質(zhì)上是一棵二叉樹,當(dāng)通過一定規(guī)則構(gòu)造是他是平衡的。
下面是過早kd樹的算法:
- 開始:構(gòu)造根結(jié)點(diǎn),根節(jié)點(diǎn)對(duì)應(yīng)包含所有訓(xùn)練實(shí)例的k為空間。 選擇第1維為坐標(biāo)軸,以所有訓(xùn)練實(shí)例的第一維數(shù)據(jù)的中位數(shù)為切分點(diǎn),將根結(jié)點(diǎn)對(duì)應(yīng)的超矩形切分為兩個(gè)子區(qū)域。由根結(jié)點(diǎn)生成深度為1的左右子結(jié)點(diǎn),左結(jié)點(diǎn)對(duì)應(yīng)第一維坐標(biāo)小于切分點(diǎn)的子區(qū)域,右子結(jié)點(diǎn)對(duì)應(yīng)第一位坐標(biāo)大于切分點(diǎn)的子區(qū)域。
- 重復(fù):對(duì)深度為j的結(jié)點(diǎn)選擇第l維為切分坐標(biāo)軸,l=j(modk)+1,以該區(qū)域中所有訓(xùn)練實(shí)例的第l維的中位數(shù)為切分點(diǎn),重復(fù)第一步。
- 直到兩個(gè)子區(qū)域沒有實(shí)例存在時(shí)停止。形成kd樹。
以下是kd樹的python實(shí)現(xiàn)
準(zhǔn)備工作
#讀取數(shù)據(jù)準(zhǔn)備 def file2matrix(filename): fr = open(filename) returnMat = [] #樣本數(shù)據(jù)矩陣 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 #將數(shù)據(jù)歸一化,避免數(shù)據(jù)各維度間的差異過大 def autoNorm(data): #將data數(shù)據(jù)和類別拆分 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函數(shù)將變量?jī)?nèi)容復(fù)制成輸入矩陣同樣大小的矩陣 normDataSet = data - np.tile(minVals,(m,1)) normDataSet = normDataSet/np.tile(ranges,(m,1)) #拼接 normDataSet = np.hstack((normDataSet,label)) return normDataSet
//數(shù)據(jù)實(shí)例 40920 8.326976 0.953952 3 14488 7.153469 1.673904 2 26052 1.441871 0.805124 1 75136 13.147394 0.428964 1 38344 1.669788 0.134296 1 72993 10.141740 1.032955 1 35948 6.830792 1.213192 3 42666 13.276369 0.543880 3 67497 8.631577 0.749278 1 35483 12.273169 1.508053 3 //每一行是一個(gè)數(shù)據(jù)實(shí)例,前三維是數(shù)據(jù)值,第四維是類別標(biāo)記
樹結(jié)構(gòu)定義
#構(gòu)建kdTree將特征空間劃分 class kd_tree: """ 定義結(jié)點(diǎn) value:節(jié)點(diǎn)值 dimension:當(dāng)前劃分的維數(shù) left:左子樹 right:右子樹 """ def __init__(self, value): self.value = value self.dimension = None #記錄劃分的維數(shù) self.left = None self.right = None def setValue(self, value): self.value = value #類似Java的toString()方法 def __str__(self): return str(self.value)
kd樹構(gòu)造
def creat_kdTree(dataIn, k, root, deep): """ data:要?jiǎng)澐值奶卣骺臻g(即數(shù)據(jù)集) k:表示要選擇k個(gè)近鄰 root:樹的根結(jié)點(diǎn) deep:結(jié)點(diǎn)的深度 """ #選擇x(l)(即為第l個(gè)特征)為坐標(biāo)軸進(jìn)行劃分,找到x(l)的中位數(shù)進(jìn)行劃分 # x_L = data[:,deep%k] #這里選取第L個(gè)特征的所有數(shù)據(jù)組成一個(gè)列表 #獲取特征值中位數(shù),這里是難點(diǎn)如果numpy沒有提供的話 if(dataIn.shape[0]>0): #如果該區(qū)域還有實(shí)例數(shù)據(jù)就繼續(xù) dataIn = dataIn[dataIn[:,int(deep%k)].argsort()] #numpy的array按照某列進(jìn)行排序 data1 = None; data2 = None #拿取根據(jù)xL排序的中位數(shù)的數(shù)據(jù)作為該子樹根結(jié)點(diǎn)的value if(dataIn.shape[0]%2 == 0): #該數(shù)據(jù)集有偶數(shù)個(gè)數(shù)據(jù) 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中,刪除放到根結(jié)點(diǎn)中 elif(dataIn.shape[0]%2 == 1): mid = int((dataIn.shape[0]+1)/2 - 1) #這里出現(xiàn)遞歸溢出,當(dāng)shape為(1,4)時(shí)出現(xiàn),原因是np.delete時(shí)沒有賦值給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中,刪除放到根結(jié)點(diǎn)中 #深度加一 deep+=1 #遞歸構(gòu)造子樹 #這里犯了嚴(yán)重錯(cuò)誤,遞歸調(diào)用是將root傳遞進(jìn)去,造成程序混亂,應(yīng)該給None root.left = creat_kdTree(data1, k, None, deep) root.right = creat_kdTree(data2, k, None, deep) return root
前序遍歷測(cè)試
#前序遍歷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近鄰搜索在此基礎(chǔ)上實(shí)現(xiàn)
原理:首先找到包含目標(biāo)點(diǎn)的葉節(jié)點(diǎn);然后從該也結(jié)點(diǎn)出發(fā),一次退回到父節(jié)點(diǎn),不斷查找與目標(biāo)點(diǎn)最近的結(jié)點(diǎn),當(dāng)確定不可能存在更近的結(jié)點(diǎn)是停止。
def findClosest(kdNode,closestPoint,x,minDis,i=0): """ 這里存在一個(gè)問題,當(dāng)傳遞普通的不可變對(duì)象minDis時(shí),遞歸退回第一次找到 最端距離前,minDis改變,最后結(jié)果混亂,這里傳遞一個(gè)可變對(duì)象進(jìn)來。 kdNode:是構(gòu)造好的kd樹。 closestPoint:是存儲(chǔ)最近點(diǎn)的可變對(duì)象,這里是array x:是要預(yù)測(cè)的實(shí)例 minDis:是當(dāng)前最近距離。 """ if kdNode == None: return #計(jì)算歐氏距離 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)) #遞歸查找葉節(jié)點(diǎn) if kdNode.value[kdNode.dimension] >= x[kdNode.dimension]: findClosest(kdNode.left,closestPoint,x,minDis,i) else: findClosest(kdNode.right, closestPoint, x, minDis,i) #計(jì)算測(cè)試點(diǎn)和分隔超平面的距離,如果相交進(jìn)入另一個(gè)葉節(jié)點(diǎn)重復(fù) 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)
測(cè)試:
data = file2matrix("datingTestSet2.txt") data = np.array(data) normDataSet = autoNorm(data) sys.setrecursionlimit(10000) #設(shè)置遞歸深度為10000 trainSet,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)
測(cè)試結(jié)果
[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近鄰搜索實(shí)現(xiàn)
在最近鄰的基礎(chǔ)上進(jìn)行改進(jìn)得到:
這里的closestPoint和minDis合并,一同處理
#k近鄰搜索 def findKNode(kdNode, closestPoints, x, k): """ k近鄰搜索,kdNode是要搜索的kd樹 closestPoints:是要搜索的k近鄰點(diǎn)集合,將minDis放入closestPoints最后一列合并 x:預(yù)測(cè)實(shí)例 minDis:是最近距離 k:是選擇k個(gè)近鄰 """ if kdNode == None: return #計(jì)算歐式距離 curDis = (sum((kdNode.value[0:3]-x[0:3])**2))**0.5 #將closestPoints按照minDis列排序,這里存在一個(gè)問題,排序后返回一個(gè)新對(duì)象 #不能將其直接賦值給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 #遞歸搜索葉結(jié)點(diǎn) if kdNode.value[kdNode.dimension] >= x[kdNode.dimension]: findKNode(kdNode.left, closestPoints, x, k) else: findKNode(kdNode.right, closestPoints, x, k) #計(jì)算測(cè)試點(diǎn)和分隔超平面的距離,如果相交進(jìn)入另一個(gè)葉節(jié)點(diǎn)重復(fù) 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)
測(cè)試
data = file2matrix("datingTestSet2.txt") data = np.array(data) normDataSet = autoNorm(data) sys.setrecursionlimit(10000) #設(shè)置遞歸深度為10000 trainSet,testSet = np.split(normDataSet,[900],axis=0) kdTree = creat_kdTree(trainSet, 3, None, 0) newData = testSet[1,0:3] print("預(yù)測(cè)實(shí)例點(diǎn):"+str(newData)) closestPoints = np.zeros((3,5)) #初始化參數(shù) closestPoints[:,4] = 10000.0 #給minDis列賦值 findKNode(kdTree, closestPoints, newData, 3) print("k近鄰結(jié)果:"+str(closestPoints))
測(cè)試結(jié)果
預(yù)測(cè)實(shí)例點(diǎn):[0.08959933 0.15442555 0.78527657]
k近鄰結(jié)果:[[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]]
以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
- python機(jī)器學(xué)習(xí)理論與實(shí)戰(zhàn)(一)K近鄰法
- python實(shí)現(xiàn)K近鄰回歸,采用等權(quán)重和不等權(quán)重的方法
- 用python實(shí)現(xiàn)k近鄰算法的示例代碼
- python實(shí)現(xiàn)KNN近鄰算法
- K最近鄰算法(KNN)---sklearn+python實(shí)現(xiàn)方式
- Python K最近鄰從原理到實(shí)現(xiàn)的方法
- python實(shí)現(xiàn)K最近鄰算法
- python機(jī)器學(xué)習(xí)案例教程——K最近鄰算法的實(shí)現(xiàn)
- python k-近鄰算法實(shí)例分享
- K近鄰法(KNN)相關(guān)知識(shí)總結(jié)以及如何用python實(shí)現(xiàn)
相關(guān)文章
python實(shí)現(xiàn)簡(jiǎn)單socket通信的方法
這篇文章主要介紹了python實(shí)現(xiàn)簡(jiǎn)單socket通信的方法,結(jié)合實(shí)例形式分析了socket通信服務(wù)端與客戶端的具體實(shí)現(xiàn)技巧,需要的朋友可以參考下2016-04-04Python requests模塊基礎(chǔ)使用方法實(shí)例及高級(jí)應(yīng)用(自動(dòng)登陸,抓取網(wǎng)頁源碼)實(shí)例詳解
這篇文章主要介紹了Python requests模塊基礎(chǔ)使用方法實(shí)例及高級(jí)應(yīng)用(自動(dòng)登陸,抓取網(wǎng)頁源碼,Cookies)實(shí)例詳解,需要的朋友可以參考下2020-02-02python自動(dòng)分箱,計(jì)算woe,iv的實(shí)例代碼
今天小編就為大家分享一篇python自動(dòng)分箱,計(jì)算woe,iv的實(shí)例代碼,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-11-11pycharm 2021.3最新激活碼有效期至2100年(親測(cè)可用)
這篇文章主要介紹了pycharm 2021.3最新激活碼有效期至2100年(親測(cè)可用)2021-02-02python opencv將圖片轉(zhuǎn)為灰度圖的方法示例
這篇文章主要介紹了python opencv將圖片轉(zhuǎn)為灰度圖的方法示例,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07Python中基本數(shù)據(jù)類型和常用語法歸納分享
這篇文章主要為大家整理記錄了Python中基本數(shù)據(jù)類型和常用語法的使用,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起了解一下2023-04-04python定時(shí)按日期備份MySQL數(shù)據(jù)并壓縮
這篇文章主要為大家詳細(xì)介紹了python定時(shí)按日期備份MySQL數(shù)據(jù)并壓縮,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-04-04