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
    image.png
    首先划分kd tree,找到二分查找到叶节点
    向上回溯，比较兄弟节点
    例子：鸢尾花数据集

例子：鸢尾花数据集

image.png
鸢尾花数据集:其中一类与另两类线性可分， 而另两类直接不线性可分。
image.png

  1. iris = datasets.load_iris()
  2. # 导入数据和标签
  3. iris_X = iris.data  # 属性
  4. iris_y = iris.target  # 对应类别
  1. X_train, X_test, y_train, y_test = train_test_split(iris_X, iris_y, test_size=0.2,random_state=0xAAAA)  # 测试比例 ,随机种子
  1. # 设置knn分类器
  2. knn = KNeighborsClassifier()
  1. # 进行训练
  2. knn.fit(X_train, y_train)
  1. print(y_test)  # 真实值
  2. print(knn.predict(X_test))   # 预测值
  3. print(knn.score(X_test,y_test))