K近邻法

2019-03-15 本文已影响0人 sumpig

“近朱者赤，近墨者黑”

简介

k近邻法（k-nearest neighbor,k-NN）是一种基本分类与回归方法。

分类时，对新的实例，根据其 k 个最近邻的训练实例的类别，通过 多数表决 等方式进行预测。

回归任务中，可使用 平均法，还可基于距离远近进行 加权平均，距离越近的样本权重越大。

k值的选择、距离度量、分类决策 规则是k近邻法的三个基本要素。

K 近邻学习没有显示的训练过程，它是 “懒惰学习” 的著名代表。

分类模型

距离度量

特征空间中两个实例点的距离是相似程度的反映。不同的距离度量所确定的最近邻点是不同的。

$L_p(x_i,x_j)=(\sum^n_{l=1}|x^{(l)}_i-x^{(l)}_j|^p)^{\frac{1}{p}}$

上式中，
当 $p=2$ 时，称为欧氏距离；
当 $p=1$ 时，称为曼哈顿距离；
当 $p=\infty$ 时，它是各个坐标距离的最大值。

k 值的选择

k 值的选择会对结果影响重大。

k 值的减小意味着整体模型变得复杂，容易发生过拟合；k 值的增大意味着整体的模型变简单。

在应用中，k 值一般取一个比较小的数值。通常采用交叉验证法来选取最优的 k 值。

分类决策规则

多数表决

算法实现

实现 k 近邻法时，当特征空间的维数与训练数据容量大时，主要考虑的问题是如何对训练数据进行快速 k 近邻搜索。

构造 kd 树

kd 树是二叉树，表示对 k 维空间的一个划分。

构造 kd 树相当于不断地用垂直于坐标轴的超平面将 k 维空间划分。具体步骤如下：

构造根节点（特征值第一维的中位数）
以 $x^{(1)}$ 为坐标轴，将训练集中所有实例的 $x^{(1)}$ 坐标的 中位数 为切分点，将训练集分为两个子区域。切分由通过切分点并与坐标轴 $x^{(1)}$ 垂直的超平面实现。
依次构造深度为1的子节点
由根节点生成深度为1的左、右子节点：左子节点对应坐标 $x^{(1)}$ 小于切分点的子区域，右子节点对应于坐标 $x^{(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))