学习
实践
活动
专区
工具
TVP
写文章

机器学习笔记(七)kd树实例 for k近邻法

(一)Python代码实例

具体讲解参见代码中注释。建议将代码拷贝到一个**.py的文件里进行阅读

#author:玖五乾元

#date:2018/02/06

#给定一个二维空间数据集,程序实现:以一个二维列表来表示

T_data = [[2,3], [5,4], [9,6], [4,7], [8,1], [7,2]]

layerNum =

#定义一个把二维数组inputList,按指定维index(取值0或1)排序

defmy_bubbleSort( inputList,index):

#打印输出入参

print("排序前= {}".format(inputList))

cnt =len(inputList)

#针以index指定的维为参考进行冒泡排序

forjinrange(cnt-1,-1,-1):

foriinrange(j):

tempList = inputList[i]

iftempList[index] > (inputList[i+1])[index] :

inputList[i] = inputList[i+1]

inputList[i+1] = tempList

print("排序后={}".format(inputList))

#制作kd数,输入排序之后的List,打印出kd数

#暂时未实现如何存储,暂未考虑算法优化(实现演示目的)

#通过弟归方式实现

defmy_makeKdTree(inputList,index):

print("*****************************递归信息*************************")

iflen(inputList) ==1:#如果只有一个元素,即是叶子节点,不再继续递归

print("叶子节点={}".format (inputList[]))

return

eliflen(inputList)

return;

#首先,对输入的List按某个维进行排序(从小到大)

my_bubbleSort (inputList, index)

#其次,对排序后的list取中间节点为切割点

rootNodeIndex =len(inputList)//2

roorNode=inputList[rootNodeIndex]

print("节点={}".format (roorNode))

#再次,取切割点左侧的元素形成新的LIST,下面进行递归调用,直到左侧只剩1个或0个元素

leftList=inputList[:rootNodeIndex]

print("左侧List={}".format(leftList))

#再次,取切割点右侧的元素形成新的LIST,下面进行递归调用,直到在侧只剩1个或0个元素

rightList = inputList[rootNodeIndex+1:len(inputList)]

print("右侧List={}".format (rightList))

# 对左侧List进行递归,这里指定了使用第1维(即第二个参数为0)进行排序后切割

iflen(leftList)>:

my_makeKdTree(leftList,)

# 对右侧List进行递归,这里指定了使用第2维(即第二个参数为1)进行排序后切割

iflen(rightList)>:

my_makeKdTree(rightList,1)

if__name__ =='__main__':

#先对我们的样例数据进行排序看看,以第一维元素进行排序

my_bubbleSort (T_data,)

# 先对我们的样例数据进行排序看看,以第二维元素进行排序

my_bubbleSort (T_data,1)

#注意!!上面调用my_bubbleSort会改变T_data的值!!

#构造kd树

my_makeKdTree(T_data,)

#注说明,在构造kd树时:

#1.选择不同的维作为切割依据形成的kd树会不同,

#2.当中间点可以选择两个时,选择哪一个都可以,但树会有不同。

#比如[[2, 3], [4, 7], [5, 4], [7, 2], [8, 1], [9, 6]],按第一维从小到大排后,中间点选择[5,4]或[7,2]都可以

(二)代码运行结果说明

对数据 [[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]]按第一维排序结果为[[2, 3], [4, 7], [5, 4], [7, 2], [8, 1], [9, 6]]。

对数据 [[2, 3], [4, 7], [5, 4], [7, 2], [8, 1], [9, 6]]按第二维排序结果为[[8, 1], [7, 2], [2, 3], [5, 4], [9, 6], [4, 7]]

按上述代码 对[[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]]构造的数输出为:

*********递归信息*********

排序前= [[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]]

排序后=[[2, 3], [4, 7], [5, 4], [7, 2], [8, 1], [9, 6]]

节点=[7, 2]

左侧List=[[2, 3], [4, 7], [5, 4]]

右侧List=[[8, 1], [9, 6]]

**********递归信息********

排序前= [[2, 3], [4, 7], [5, 4]]

排序后=[[2, 3], [4, 7], [5, 4]]

节点=[4, 7]

左侧List=[[2, 3]]

右侧List=[[5, 4]]

*********递归信息***********

叶子节点=[2, 3]

***********递归信息**********

叶子节点=[5, 4]

***********递归信息********

排序前= [[8, 1], [9, 6]]

排序后=[[8, 1], [9, 6]]

节点=[9, 6]

左侧List=[[8, 1]]

右侧List=[]

************递归信息**********

叶子节点=[8, 1]

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180207G000ER00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

关注

腾讯云开发者公众号
10元无门槛代金券
洞察腾讯核心技术
剖析业界实践案例
腾讯云开发者公众号二维码

扫码关注腾讯云开发者

领取腾讯云代金券