python K近邻算法的kd树实现

k近邻算法的介绍

k近邻算法是一种基本的分类和回归方法,这里只实现分类的k近邻算法。

k近邻算法的输入为实例的特征向量,对应特征空间的点;输出为实例的类别,可以取多类。

k近邻算法不具有显式的学习过程,实际上k近邻算法是利用训练数据集对特征向量空间进行划分。将划分的空间模型作为其分类模型。

k近邻算法的三要素

  • k值的选择:即分类决策时选择k个最近邻实例;
  • 距离度量:即预测实例点和训练实例点间的距离,一般使用L2距离即欧氏距离;
  • 分类决策规则。

下面对三要素进行一下说明:

1.欧氏距离即欧几里得距离,高中数学中用来计算点和点间的距离公式;

2.k值选择:k值选择会对k近邻法结果产生重大影响,如果选择较小的k值,相当于在较小的邻域中训练实例进行预测,这样有点是“近似误差”会减小,即只与输入实例较近(相似)的训练实例才会起作用,缺点是“估计误差”会增大,即对近邻的实例点很敏感。而k值过大则相反。实际中取较小的k值通过交叉验证的方法取最优k值。

3.k近邻法的分类决策规则往往采用多数表决的方式,这等价于“经验风险最小化”。

k近邻算法的实现:kd树

实现k近邻法是要考虑的主要问题是如何退训练数据进行快速的k近邻搜索,当训练实例数很大是显然通过一般的线性搜索方式效率低下,因此为了提高搜索效率,需要构造特殊的数据结构对训练实例进行存储。kd树就是一种不错的数据结构,可以大大提高搜索效率。

本质商kd树是对k维空间的一个划分,构造kd树相当与使用垂直于坐标轴的超平面将k维空间进行切分,构造一系列的超矩形,kd树的每一个结点对应一个这样的超矩形。

kd树本质上是一棵二叉树,当通过一定规则构造是他是平衡的。

下面是过早kd树的算法:

  • 开始:构造根结点,根节点对应包含所有训练实例的k为空间。 选择第1维为坐标轴,以所有训练实例的第一维数据的中位数为切分点,将根结点对应的超矩形切分为两个子区域。由根结点生成深度为1的左右子结点,左结点对应第一维坐标小于切分点的子区域,右子结点对应第一位坐标大于切分点的子区域。
  • 重复:对深度为j的结点选择第l维为切分坐标轴,l=j(modk)+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]]

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • python机器学习理论与实战(一)K近邻法

    机器学习分两大类,有监督学习(supervised learning)和无监督学习(unsupervised learning).有监督学习又可分两类:分类(classification.)和回归(regression),分类的任务就是把一个样本划为某个已知类别,每个样本的类别信息在训练时需要给定,比如人脸识别.行为识别.目标检测等都属于分类.回归的任务则是预测一个数值,比如给定房屋市场的数据(面积,位置等样本信息)来预测房价走势.而无监督学习也可以成两类:聚类(clustering)和密度估计

  • python K近邻算法的kd树实现

    k近邻算法的介绍 k近邻算法是一种基本的分类和回归方法,这里只实现分类的k近邻算法. k近邻算法的输入为实例的特征向量,对应特征空间的点:输出为实例的类别,可以取多类. k近邻算法不具有显式的学习过程,实际上k近邻算法是利用训练数据集对特征向量空间进行划分.将划分的空间模型作为其分类模型. k近邻算法的三要素 k值的选择:即分类决策时选择k个最近邻实例: 距离度量:即预测实例点和训练实例点间的距离,一般使用L2距离即欧氏距离: 分类决策规则. 下面对三要素进行一下说明: 1.欧氏距离即欧几里得距

  • Python语言描述KNN算法与Kd树

    最近邻法和k-近邻法 下面图片中只有三种豆,有三个豆是未知的种类,如何判定他们的种类? 提供一种思路,即:未知的豆离哪种豆最近就认为未知豆和该豆是同一种类.由此,我们引出最近邻算法的定义:为了判定未知样本的类别,以全部训练样本作为代表点,计算未知样本与所有训练样本的距离,并以最近邻者的类别作为决策未知样本类别的唯一依据.但是,最近邻算法明显是存在缺陷的,比如下面的例子:有一个未知形状(图中绿色的圆点),如何判断它是什么形状? 显然,最近邻算法的缺陷--对噪声数据过于敏感,为了解决这个问题,我们可

  • 用python实现k近邻算法的示例代码

    K近邻算法(或简称kNN)是易于理解和实现的算法,而且是你解决问题的强大工具. 什么是kNN kNN算法的模型就是整个训练数据集.当需要对一个未知数据实例进行预测时,kNN算法会在训练数据集中搜寻k个最相似实例.对k个最相似实例的属性进行归纳,将其作为对未知实例的预测. 相似性度量依赖于数据类型.对于实数,可以使用欧式距离来计算.其他类型的数据,如分类数据或二进制数据,可以用汉明距离. 对于回归问题,会返回k个最相似实例属性的平均值.对于分类问题,会返回k个最相似实例属性出现最多的属性. kNN

  • python机器学习基础K近邻算法详解KNN

    目录 一.k-近邻算法原理及API 1.k-近邻算法原理 2.k-近邻算法API 3.k-近邻算法特点 二.k-近邻算法案例分析案例信息概述 第一部分:处理数据 1.数据量缩小 2.处理时间 3.进一步处理时间 4.提取并构造时间特征 5.删除无用特征 6.签到数量少于3次的地点,删除 7.提取目标值y 8.数据分割 第二部分:特征工程 标准化 第三部分:进行算法流程 1.算法执行 2.预测结果 3.检验效果 一.k-近邻算法原理及API 1.k-近邻算法原理 如果一个样本在特征空间中的k个最相

  • Python数据结构与算法之字典树实现方法示例

    本文实例讲述了Python数据结构与算法之字典树实现方法.分享给大家供大家参考,具体如下: class TrieTree(): def __init__(self): self.root = {} def addNode(self,str): # 树中每个结点(除根节点),包含到该结点的单词数,以及该结点后面出现字母的键 nowdict = self.root for i in range(len(str)): if str[i] not in nowdict: # 发现新的组合方式 nowdi

  • GO语言利用K近邻算法实现小说鉴黄

    Usuage:   go run kNN.go --file="data.txt" 关键是向量点的选择和阈值的判定 样本数据来自国家新闻出版总署发布通知公布的<40部淫秽色情网络小说名单> package main import ( "bufio" "flag" "fmt" "io" "log" "math" "os" "pa

  • K最近邻算法(KNN)---sklearn+python实现方式

    k-近邻算法概述 简单地说,k近邻算法采用测量不同特征值之间的距离方法进行分类. k-近邻算法 优点:精度高.对异常值不敏感.无数据输入假定. 缺点:计算复杂度高.空间复杂度高. 适用数据范围:数值型和标称型. k-近邻算法(kNN),它的工作原理是:存在一个样本数据集合,也称作训练样本集,并且样本集中每个数据都存在标签,即我们知道样本集中每一数据与所属分类的对应关系.输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似数据(最近邻)的分类标

  • K近邻法(KNN)相关知识总结以及如何用python实现

    1.基本概念 K近邻法(K-nearest neighbors,KNN)既可以分类,也可以回归. KNN做回归和分类的区别在于最后预测时的决策方式. KNN做分类时,一般用多数表决法 KNN做回归时,一般用平均法.  基本概念如下:对待测实例,在训练数据集中找到与该实例最邻近的K个实例(也就是上面所说的K个邻居), 这K个实例的多数属于某个类,就把该输入实例分类到这个类中 2. KNN算法三要素 KNN算法主要考虑:k值的选取,距离度量方式,分类决策规则. 1) k值的选取.在应用中,k值一般选

  • Python KNN分类算法学习

    本文实例为大家分享了Python KNN分类算法的具体代码,供大家参考,具体内容如下 1.KNN分类算法 KNN分类算法(K-Nearest-Neighbors Classification),又叫K近邻算法,是一个概念极其简单,而分类效果又很优秀的分类算法. 他的核心思想就是,要确定测试样本属于哪一类,就寻找所有训练样本中与该测试样本"距离"最近的前K个样本,然后看这K个样本大部分属于哪一类,那么就认为这个测试样本也属于哪一类.简单的说就是让最相似的K个样本来投票决定. 这里所说的距

  • python实现kNN算法

    kNN(k-nearest neighbor)是一种基本的分类与回归的算法.这里我们先只讨论分类中的kNN算法. k邻近算法的输入为实例的特征向量,对对应于特征空间中的点:输出为实例的类别,可以取多类,k近邻法是建设给定一个训练数据集,其中的实例类别已定,分类时,对于新的实例,根据其k个最邻近的训练实例的类别,通过多数表决等方式进行预测.所以可以说,k近邻法不具有显示的学习过程.k临近算法实际上是利用训练数据集对特征向量空间进行划分,并作为其分类的"模型" k值的选择,距离的度量和分类

随机推荐