机器学习笔记（七）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]