王东明父亲,黄海暗杀,菜包子的做法
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 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]]
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持移动技术网。
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
新手学习Python2和Python3中print不同的用法
Python基于os.environ从windows获取环境变量
网友评论