一、求最近鄰點：
- 題目： T = { ( 2 , 3 ) T ， ( 5 , 4 ) T ， ( 9 , 6 ) T ， ( 4 , 7 ) T ， ( 8 , 1 ) T ， ( 7 , 2 ) T } T=\begin{Bmatrix} (2,3)^T，(5,4)^T，(9,6)^T，(4,7)^T，(8,1)^T，(7,2)^T \end{Bmatrix} T={(2,3)T，(5,4)T，(9,6)T，(4,7)T，(8,1)T，(7,2)T}
03 k近鄰法——Python實作 - Python代碼：
# author yuxy
#方法一：采用坐标軸輪換方式搜尋
import numpy as np
class Node:
"""節點類：用來表示kd樹"""
def __init__(self, data, left_node, right_node):
self.data=data
self.left_tree=left_node
self.right_tree=right_node
class kdTree():
"""kd樹類：實作kd樹建立、kd樹搜尋"""
def __init__(self, dataSet, depth):
self.dataSet=dataSet
self.depth=depth
def create_tree(self, dataSet, depth):
"""kd樹建立方法：采用遞歸的方式"""
if len(dataSet)>0:
m,n=np.shape(dataSet) #m行，n列
middleIndex=int(m / 2)
axis=depth % n
sortedData=sorted(dataSet, key=lambda x:x[axis])
node=Node(sortedData[middleIndex],None,None)
left_data=sortedData[: middleIndex]
right_data=sortedData[middleIndex+1 :]
node.left_node=self.create_tree(left_data,depth+1)
node.right_node=self.create_tree(right_data, depth+1)
return node
else:
return None
def show_tree(self, node):
"""輸出樹的節點資訊,采用遞歸的方法"""
if node != None:
print("---%s" % node.data)
print('left_node:')
self.show_tree(node.left_node)
print('right_node:')
self.show_tree(node.right_node)
else:
print("None")
def search_tree(self, kd_tree, x):
"""從kd樹中搜尋x的最近鄰點"""
self.resultNode=None
self.minDistance=0
def search(tree_node, depth=0):
if tree_node!=None:
n=len(x)
axis=depth % n
if x[axis]<tree_node.data[axis]:
search(tree_node.left_node, depth+1)
else:
search(tree_node.right_node, depth+1)
# 回溯，因為遞歸本身和棧的實作原理相同，先進後出，當葉子節點左右節點都為None時，就依次回溯，輸出父節點
distance=self.get_distance(x, tree_node.data)
if self.resultNode==None:
self.resultNode=tree_node
self.minDistance=distance
elif distance < self.minDistance:
self.resultNode = tree_node
self.minDistance = distance
print(tree_node.data, self.minDistance, x[axis], tree_node.data[axis])
# 判斷另一個子區域中是否存在更近鄰點
if self.minDistance>(abs(tree_node.data[axis]-x[axis])):
if x[axis]< tree_node.data[axis]:
search(tree_node.right_node, depth + 1)
else:
search(tree_node.left_node, depth + 1)
search(kd_tree)
return self.resultNode.data
def get_distance(self, x, y):
"""擷取x，y之間的歐氏距離"""
dis=((np.array(x)-np.array(y))**2).sum()**0.5
return dis
if __name__=='__main__':
tree_data = [[2, 3], [7, 2], [5, 4], [4, 7], [9, 6], [8, 1]]
depth=0
my_tree=kdTree(tree_data, depth)
my_node=my_tree.create_tree(tree_data, depth)
# my_tree.show_tree(my_node)
x=[3,4.5]
print('x[3,4.5]的最近鄰點為:%s' % my_tree.search_tree(my_node, x))
結果圖：
# author yuxy
#方法二：采用最大方差劃分實作最近鄰
import numpy as np
class Node:
"""節點類：用來表示kd樹"""
def __init__(self, data, left_node, right_node):
self.data=data
self.left_tree=left_node
self.right_tree=right_node
class kdTree():
"""kd樹類：實作kd樹建立、kd樹搜尋"""
def __init__(self, dataSet, depth):
self.dataSet=dataSet
self.depth=depth
def create_tree(self, dataSet, depth):
"""kd樹建立方法：采用遞歸的方式"""
if len(dataSet)>0:
m,n=np.shape(dataSet) #m行，n列
middleIndex=int(m / 2)
# axis=depth % n
axis=self.variance(dataSet)
sortedData=sorted(dataSet, key=lambda x:x[axis])
node=Node(sortedData[middleIndex],None,None)
left_data=sortedData[: middleIndex]
right_data=sortedData[middleIndex+1 :]
node.left_node=self.create_tree(left_data,depth+1)
node.right_node=self.create_tree(right_data, depth+1)
return node
else:
return None
def show_tree(self, node):
"""輸出樹的節點資訊,采用遞歸的方法"""
if node != None:
print("---%s" % node.data)
print('left_node:')
self.show_tree(node.left_node)
print('right_node:')
self.show_tree(node.right_node)
else:
print("None")
def search_tree(self, kd_tree, dataSet, x):
"""從kd樹中搜尋x的最近鄰點"""
self.resultNode=None
self.minDistance=0
def search(tree_node, dataSet, depth=0):
if tree_node!=None:
m, n = np.shape(dataSet) # m行，n列
middleIndex = int(m / 2)
axis = self.variance(dataSet)
sortedData = sorted(dataSet, key=lambda x: x[axis])
left_data = sortedData[: middleIndex]
right_data = sortedData[middleIndex + 1:]
if x[axis]<tree_node.data[axis]:
search(tree_node.left_node, left_data, depth+1)
else:
search(tree_node.right_node, right_data, depth+1)
# 回溯，因為遞歸本身和棧的實作原理相同，先進後出，當葉子節點左右節點都為None時，就依次回溯，輸出父節點
distance=self.get_distance(x, tree_node.data)
if self.resultNode==None:
self.resultNode=tree_node
self.minDistance=distance
elif distance < self.minDistance:
self.resultNode = tree_node
self.minDistance = distance
print(tree_node.data, self.minDistance, x[axis], tree_node.data[axis])
# 判斷另一個子區域中是否存在更近鄰點
if self.minDistance>(abs(tree_node.data[axis]-x[axis])):
if x[axis]< tree_node.data[axis]:
search(tree_node.right_node, right_data,depth + 1)
else:
search(tree_node.left_node, left_data, depth + 1)
search(kd_tree, dataSet)
return self.resultNode.data
def get_distance(self, x, y):
"""擷取x，y之間的歐氏距離"""
dis=((np.array(x)-np.array(y))**2).sum()**0.5
return dis
def variance(self, xList):
"""計算二維數組中每維的方差"""
x=0
y=1
coordinate=x
data_x=[]
data_y=[]
i=0
while i < len(xList):
data_x.append(xList[i][0])
data_y.append(xList[i][1])
i=i+1
#計算方差
avg_x=self.get_average(data_x)
avg_y=self.get_average(data_y)
#計算方差
j=0
va_x=0
va_y=0
while j < len(xList):
va_x=va_x+(abs(data_x[j] - avg_x) ** 2)
va_y= va_y + (abs(data_y[j] - avg_y) ** 2)
j = j+1
if va_x > va_y:
coordinate=x
else:
coordinate=y
return coordinate
def get_average(self, data):
"""計算數組元素的平均值"""
i=0
sum=0
while i < len(data):
sum=sum+data[i]
i=i+1
avg=(1.0 * sum) / len(data)
return avg
if __name__=='__main__':
tree_data = [[2, 3], [7, 2], [5, 4], [4, 7], [9, 6], [8, 1]]
depth=0
my_tree=kdTree(tree_data, depth)
my_node=my_tree.create_tree(tree_data, depth)
# my_tree.show_tree(my_node)
x=[3,4.5]
print('x[3,4.5]的最近鄰點為:%s' % my_tree.search_tree(my_node, tree_data, x))
# print(my_node.data)
二、求k近鄰點：
- 題目同上，查找 x = [ 3 , 4.5 ] x=[3,4.5] x=[3,4.5] 的 2 2 2 近鄰點。
-
算法思想：
輸入：已構造的kdkdkd樹，目标點xxx.
輸出：x的k近鄰.
（1）在 kd 樹中找出包含目标點 x 的葉結點：從根結點出發，遞歸地向下通路樹。若目标點 x目前維的坐标小于切分點的坐标，則移動到左子結點，否則移動到右子結點，直到子結點為葉結點為止；
（2）如果 “目前 K近鄰點集” 元素數量小于K或者葉節點距離小于 “目前 K近鄰點集” 中最遠點距離，那麼将葉節點插入 “目前 K近鄰點集”；
（3）遞歸地向上回退，在每個結點進行以下操作：
(a) 如果 “目前 K近鄰點集” 元素數量小于K或者目前節點距離小于 “目前 K近鄰點集” 中最遠點距離，那麼将該節點插入 “目前 K近鄰點集”；
(b) 檢查另一子結點對應的區域是否與以目标點為球心、以目标點與于 “目前 K近鄰點集” 中最遠點間的距離為半徑的超球體相交。
如果相交，可能在另一個子結點對應的區域記憶體在距目标點更近的點，移動到另一個子結點。接着，遞歸地進行最近鄰搜尋；
如果不相交，向上回退；
（4）當回退到根結點時，搜尋結束。最後的 “目前 K近鄰點集” 即為 x 的 K 近鄰點集。
- Python代碼：
# author yuxy
# 求k近鄰點
import numpy as np
class Node:
"""節點類：用來表示kd樹"""
def __init__(self, data, left_node, right_node):
self.data=data
self.left_tree=left_node
self.right_tree=right_node
class kdTree():
"""kd樹類：實作kd樹建立、kd樹搜尋"""
def __init__(self, dataSet, depth):
self.dataSet=dataSet
self.depth=depth
def create_tree(self, dataSet, depth):
"""kd樹建立方法：采用遞歸的方式"""
if len(dataSet)>0:
m,n=np.shape(dataSet) #m行，n列
middleIndex=int(m / 2)
axis=depth % n
sortedData=sorted(dataSet, key=lambda x:x[axis])
node=Node(sortedData[middleIndex],None,None)
left_data=sortedData[: middleIndex]
right_data=sortedData[middleIndex+1 :]
node.left_node=self.create_tree(left_data,depth+1)
node.right_node=self.create_tree(right_data, depth+1)
return node
else:
return None
def search_knn(self, dataSet, x, k, depth):
"""通過查找kd樹，查找k個近鄰點"""
self.listNode=[] #記錄k近鄰點序列
self.length=[] #記錄數組中距離目标點x的最遠距離
self.maxLength=[0,0] #0:最大值下标， 1：最大值
self.index=1
self.init=1
def search(node_tree, k, depth=0):
if node_tree!=None:
dimension=len(x)
axis=depth % dimension
if x[axis]< node_tree.data[axis]:
#移動到左子節點
search(node_tree.left_node, k, depth+1)
else:
search(node_tree.right_node, k, depth+1)
#回溯，退棧得到葉子節點、根節點
distance = self.get_distance(x, node_tree.data)
if self.init == 1: #第一次
self.listNode.append(node_tree.data)
self.length.append(distance)
self.maxLength[1]=distance
self.maxLength[0]=self.index
self.index=self.index+1
self.init=self.init+1
elif len(self.listNode)< k:
self.listNode.append(node_tree.data)
self.length.append(distance)
self.maxLength[1]=self.get_maxDistance(self.length)[1] #最大長度
self.maxLength[0]=self.get_maxDistance(self.length)[0] #最大長度的下标
self.index = self.index + 1
elif distance < self.maxLength[1]: #length數組已經滿了，需要根據長度值更新數組
self.listNode[self.maxLength[0]]=node_tree.data
self.length[self.maxLength[0]] = distance
self.maxLength[1] = self.get_maxDistance(self.length)[1] # 最大長度
self.maxLength[0] = self.get_maxDistance(self.length)[0] # 最大長度的下标
#進行遞歸操作了
# i=0
# while i < len(self.listNode):
print('listNode:%s length=%s' % (self.listNode, self.length))
# i=i+1
if abs(x[axis]-node_tree.data[axis])< self.maxLength[1]:
if x[axis]< node_tree.data[axis]:
search(node_tree.right_node, k, depth+1)
else:
search(node_tree.left_node, k, depth + 1)
search(dataSet, k)
return self.listNode
def get_maxDistance(self, length_list):
"""擷取最大距離和最大距離的下标"""
i=0
max=0
index=0
while i < len(length_list):
if length_list[i]> max:
max=length_list[i]
index=i
i=i+1
return [index, max]
def get_distance(self, x, y):
"""擷取x和y之間的歐氏距離"""
dis=((np.array(x)-np.array(y))**2).sum() **0.5
return dis
def show_tree(self, node):
"""輸出樹的節點資訊,采用遞歸的方法"""
if node != None:
print("---%s" % node.data)
print('left_node:')
self.show_tree(node.left_node)
print('right_node:')
self.show_tree(node.right_node)
else:
print("None")
if __name__=='__main__':
tree_data = [[2, 3], [7, 2], [5, 4], [4, 7], [9, 6], [8, 1]]
depth=0
my_tree=kdTree(tree_data, depth)
my_node=my_tree.create_tree(tree_data, depth)
# my_tree.show_tree(my_node)
x=[3,4.5]
k=2
print('x[3,4.5]的 %i 近鄰點為:%s' % (k, my_tree.search_knn(my_node, x, k, depth)))
- 運作結果： 【如若有問題，請留言交流！】
03 k近鄰法——Python實作