image.png

算法流程

  1. 计算测试样本与训练集中每个样本的距离
    2. 按照距离的远近排序
    3. 选取与当前测试样本最近的k个训练样本，作为该测试样本的邻居
    4. 统计这k个样本的类别频次
    5. k个样本里频次最高的类别，即为测试样本的类别
    image.png

    K-D-Tree划分

    KD树

    对于二维数据(x, y)，如何构建查找树？

    KD树（k维空间）构造流程：

  2. 选择一个坐标轴（假设为K近邻（KNN） - 图3），以及在该坐标轴上的切分点，由此可将超矩形区域划分为
    左/右子区域。其中左子区域k1坐标轴均小于该切分点，右子区域均大于该切分点
    2. 在左/右子区域中，对除开K近邻（KNN） - 图4的其余维度执行以上步骤，直至所有节点已全部划分完毕
    切分轴的选择（方向）：选择方差最大的维度
    切分点的选择（位置）：在以上维度中，选择中点

    构造过程

    image.png
    image.png
    image.pngimage.png

    切分轴轮转

    image.png

    KD树搜索

    在KD树中寻找目标点x的最近邻

    image.png

    例子

    image.png

    递归向上回退

    image.png
    image.png
    image.png

    算法执行实例

    image.png
    image.png

    作业

    image.png