Python实现K近邻算法：基于KD树的优化搜索
本文详细解析K近邻算法的核心要素，包括k值选择、距离度量及分类决策规则。重点介绍利用KD树优化训练数据搜索效率的方法，涵盖KD树的构建原理、递归构造算法以及最近邻和K近邻搜索的具体实现。通过Python代码示例，展示了从数据预处理、KD树构建到预测结果输出的完整流程，帮助读者理解并掌握这一经典分类算法的高效实现。
K近邻算法概述
K近邻（K-Nearest Neighbors, KNN）是一种基础的分类与回归方法。本文主要聚焦于K近邻在分类任务中的具体实现。
该算法的输入是实例的特征向量，这些向量对应于特征空间中的点；输出则是实例所属的类别，类别数量可以是多个。
K近邻算法没有显式的训练学习过程，其实质是利用训练数据集对特征向量空间进行划分，并将这种空间划分模型直接作为分类模型。
K近邻算法的三个关键要素
- k值的选择：在分类决策时，选取距离最近的k个训练实例。
- 距离度量：计算预测实例与训练实例之间的距离，通常采用L2距离，即欧氏距离。
- 分类决策规则：确定如何根据近邻实例的类别做出最终预测。
接下来对上述三个要素进行详细说明：
1. 欧氏距离：即欧几里得距离，是高中数学中计算两点间距离的标准公式。
2. k值的选择：k值的选择对K近邻算法的结果有重大影响。若选择较小的k值，相当于在较小的邻域内进行预测，其优点是“近似误差”减小，即只有与输入实例较近（相似）的训练实例参与预测；缺点是“估计误差”增大，即预测结果对近邻实例点非常敏感。反之，k值过大则效果相反。在实际应用中，通常通过交叉验证法选取最优的较小k值。
3. K近邻法的分类决策规则通常采用多数表决方式，这在数学上等价于“经验风险最小化”。
K近邻算法的实现：KD树
实现K近邻法的关键问题在于如何快速搜索训练数据的k个最近邻。当训练实例数量庞大时，线性搜索效率极低。因此，为了提高搜索效率，需要构建特殊的数据结构来存储训练实例。KD树（K-Dimensional Tree）是一种高效的数据结构，能显著提升搜索效率。
KD树的本质是对k维空间的一种划分。构造KD树相当于使用垂直于坐标轴的超平面将k维空间切分为一系列超矩形，KD树的每个节点对应一个这样的超矩形。
KD树本质上是一棵二叉树，在按照特定规则构造时，它通常是平衡的。
以下是构建KD树的算法步骤：
- 开始：构造根节点，根节点对应包含所有训练实例的k维空间。选择第1维作为坐标轴，以所有训练实例在第1维数据的中位数作为切分点，将根节点对应的超矩形切分为两个子区域。由根节点生成深度为1的左右子节点，左子节点对应第1维坐标小于切分点的子区域，右子节点对应第1维坐标大于切分点的子区域。
- 重复：对深度为j的节点，选择第l维作为切分坐标轴，其中l=j(mod k)+1。以该区域中所有训练实例在第l维的中位数作为切分点，重复上述步骤。
- 直到两个子区域不再包含任何实例时停止，从而形成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 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 //每一行是一个数据实例，前三维是数据值，第四维是类别标记
树结构定义
#构建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) #设置递归深度为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)
测试结果
[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) #设置递归深度为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)) #初始化参数
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]]
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持本站。
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
