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