“近朱者赤，近墨者黑”
简介
k近邻法（k-nearest neighbor,k-NN）是一种基本 分类 与 回归 方法。
分类时，对新的实例，根据其 k 个最近邻的训练实例的类别，通过 多数表决 等方式进行预测。
回归任务中，可使用 平均法，还可基于距离远近进行 加权平均，距离越近的样本权重越大。
k值的选择、距离度量、分类决策 规则是k近邻法的三个基本要素。
K 近邻学习没有显示的训练过程，它是 “懒惰学习” 的著名代表。
分类模型
距离度量
特征空间中两个实例点的距离是相似程度的反映。不同的距离度量所确定的最近邻点是不同的。
上式中，
当 时，称为欧氏距离；
当 时，称为曼哈顿距离；
当 时，它是各个坐标距离的最大值。
k 值的选择
k 值的选择会对结果影响重大。
k 值的减小意味着整体模型变得复杂，容易发生过拟合；k 值的增大意味着整体的模型变简单。
在应用中，k 值一般取一个比较小的数值。通常采用交叉验证法来选取最优的 k 值。
分类决策规则
多数表决
算法实现
实现 k 近邻法时，当 特征空间的维数 与 训练数据容量大 时，主要考虑的问题是如何对训练数据进行快速 k 近邻搜索。
构造 kd 树
kd 树是二叉树，表示对 k 维空间的一个划分。
构造 kd 树相当于不断地用垂直于坐标轴的超平面将 k 维空间划分。具体步骤如下：
-
构造根节点（特征值第一维的中位数）
以为坐标轴，将训练集中所有实例的
-
依次构造深度为1的子节点
由根节点生成深度为1的左、右子节点：左子节点对应坐标 -
依次对子区域进行中位数切分（维数递增循环），直到两个子区域没有实例存在时停止。
from collections import namedtuple
from operator import itemgetter
from pprint import pformat
class Node(namedtuple('Node', 'location left_child right_child')):
def __repr__(self):
return pformat(tuple(self))
def kdtree(point_list, depth=0):
try:
k = len(point_list[0]) # assumes all points have the same dimension
except IndexError as e: # if not point_list:
return None
# Select axis based on depth so that axis cycles through all valid values
axis = depth % k
# Sort point list and choose median as pivot element
point_list.sort(key=itemgetter(axis))
median = len(point_list) // 2 # choose median
# Create node and construct subtrees
return Node(
location=point_list[median],
left_child=kdtree(point_list[:median], depth + 1),
right_child=kdtree(point_list[median + 1:], depth + 1)
)
def main():
"""Example usage"""
point_list = [(2,3), (5,4), (9,6), (4,7), (8,1), (7,2)]
tree = kdtree(point_list)
print(tree)
if __name__ == '__main__':
main()
搜索 kd 树
kd树搜索的平均计算复杂度是，N为训练实例数。
kd树更适用于训练实例数远大于空间维数时的k近邻搜索。
下面为 kd 树的最近邻搜索算法：
-
在kd树中找到包含目标点x的叶节点
从根节点出法，递归向下访问kd树。若目标点x当前维的坐标小于切分点的坐标，则移动到左子节点，否则移动到右子节点，直到子节点为叶结点为止。 -
将此叶结点标记为 “当前最近点”
-
递归向上回退，在每个结点进行以下操作：
- 如果该结点保存的实例点比当前最近点距离目标点更近，则以该实例为“当前最近点”。
- 当前最近点一定存在于该结点一个子结点对应的区域。检查该子结点的父结点的另一子结点对应的区域是否有更近的点。具体地，检查另一子结点对应的区域是否与以目标点为球心、以目标点与“当前最近点”间的距离为半径的超球体相交。
如果相交，可能在另一个子结点对应的区域内存在距目标点更近的点，移动到另一个子结点。接着，递归地进行最近邻搜索；
如果不相交，向上回退。
-
当回退到根结点时，搜索结束。最后的“当前最近点” 即为 x 的最近邻点。
from operator import itemgetter
class kdtree(object):
# 创建 kdtree
# point_list[0] 是一 tuple 的特征，point_list[1] 是类别
def __init__(self, point_list, depth=0, root=None):
if len(point_list)>0:
# 轮换按照树深度选择坐标轴
k = len(point_list[0][0])
axis = depth % k
# 选中位线，切
point_list.sort(key=lambda x:x[0][axis])
median = len(point_list) // 2
self.axis = axis
self.root = root
self.size = len(point_list)
# 造节点
self.node = point_list[median]
# 递归造左枝和右枝
if len(point_list[:median]) > 0:
self.left = kdtree(point_list[:median], depth+1, self)
else:
self.left = None
if len(point_list[median+1:]) > 0:
self.right = kdtree(point_list[median+1:], depth+1, self)
else:
self.right = None
else:
return None
# 在树上加一点(只追加到叶结点，不会替换子结点)
def insert(self, point):
self.size += 1
# 分析是左还是右，递归加在叶子上
if point[0][self.axis] < self.node[0][self.axis]:
if self.left!=None:
self.left.insert(point)
else:
self.left = kdtree([point], self.axis+1, self)
else:
if self.right != None:
self.right.insert(point)
else:
self.right = kdtree([point], self.axis+1, self)
# 输入一点
# 按切分寻找叶子（只能找到叶结点）
def find_leaf(self, point):
if self.left==None and self.right==None:
return self
elif self.left==None:
return self.right.find_leaf(point)
elif self.right==None:
return self.left.find_leaf(point)
elif point[self.axis]<self.node[0][self.axis]:
return self.left.find_leaf(point)
else:
return self.right.find_leaf(point)
# 查找最近的 k 个点，复杂度 O(DlogN)，D是维度，N是树的大小
# 输入一点、一距离函数、一k。距离函数默认是 L_2
def knearest(self, point, k=1, dist=lambda x,y: sum(map(lambda u,v:(u-v)**2,x,y))):
# 往下戳到最底叶
leaf = self.find_leaf(point)
# 从叶子网上爬
return leaf.k_down_up(point, k, dist, result=[], stop=self, visited=None)
# 从下往上爬函数，stop是到哪里去，visited是从哪里来
def k_down_up(self, point,k, dist, result=[], stop=None, visited=None):
# 选最长距离
if result==[]:
max_dist = 0
else:
max_dist = max([x[1] for x in result])
other_result=[]
# 如果离分界线的距离小于现有最大距离，或者数据点不够，就从另一边的树根开始刨
if (self.left==visited and self.node[0][self.axis]-point[self.axis]<max_dist and self.right!=None)\
or (len(result)<k and self.left==visited and self.right!=None):
other_result=self.right.knearest(point,k, dist)
if (self.right==visited and point[self.axis]-self.node[0][self.axis]<max_dist and self.left!=None)\
or (len(result)<k and self.right==visited and self.left!=None):
other_result=self.left.knearest(point, k, dist)
# 刨出来的点放一起，选前 k 个
result.append((self.node, dist(point, self.node[0])))
result = sorted(result+other_result, key=lambda pair: pair[1])[:k]
# 到停点就返回结果
if self==stop:
return result
# 没有就带着现有结果接着往上爬
else:
return self.root.k_down_up(point,k, dist, result, stop, self)
# 输入 特征、类别、k、距离函数
# 返回这个点属于该类别的概率
def kNN_prob(self, point, label, k, dist=lambda x,y: sum(map(lambda u,v:(u-v)**2,x,y))):
nearests = self.knearest(point, k, dist)
return float(len([pair for pair in nearests if pair[0][1]==label]))/float(len(nearests))
# 输入 特征、k、距离函数
# 返回该点概率最大的类别以及相对应的概率
def kNN(self, point, k, dist=lambda x,y: sum(map(lambda u,v:(u-v)**2,x,y))):
nearests = self.knearest(point, k , dist)
statistics = {}
for data in nearests:
label = data[0][1]
if label not in statistics:
statistics[label] = 1
else:
statistics[label] += 1
max_label = max(statistics.items(), key=itemgetter(1))[0]
return max_label, float(statistics[max_label])/float(len(nearests))
point_list = [[[2,3],1], [[5,4],1], [[9,6],1], [[4,7],-1], [[8,1],-1], [[7,2],-1]]
tree = kdtree(point_list)
print(tree.kNN([6,6], 3))
网友评论