KNN

  • k nearest neighbors

  • k近邻算法

  • k表示个数

    • 你有几个好朋友？
    • 你有几个邻居？
    • 你有几个女朋友？

  • 邻居是什么样性质，类别，影响你，之所以成为了邻居，必然共性

    • 比如你的邻居是马云、马化腾、李嘉诚，你必然也是亿万富翁
    • 比如你的邻居是葛优、张国立、成龙，比必然也是明星
    • 比如你的邻居是习大大、毛爷爷、李克强总理，比必然也是为人民服务的公务人员

  • 根据这个特征，来对事物进行分类

  • 邻居，距离比较近

    • 问题，请问Xu这个点属于哪个类别呢？
    • 三个类别：红色、绿色、蓝色
    • 找Xu这个点的最近的5个邻居（5 == k，调大跳小）
    • 从图中直观看到，4个最近邻居是红色，1个最近的邻居是绿色
    • 人多力量大，投票决定，民主。4 > 1
    • 对人而言，投票
    • 对计算机而言，统计
    • 0.8 > 0.2
    • 从票数或者从概率上分类的话，得到这样的结论
    • Xu属于红色的类别！
    • KNN根据远近，进行类别划分的基本原理

  • 远近使用什么度量

    • 距离

    • 点A(1,2)，点B(4,6)，请问A和B之间的距离怎么计算

    • 欧式距离

    • distanceAB=(4−1)2+(6−2)2=32+42=5distance_{AB} = \sqrt{(4 - 1)^2 + (6-2)^2} = \sqrt{3^2 + 4^2} = 5

    • 点A(2,3,4)，点B(5,8,9):

    • distanceAB=(5−2)2+(8−3)2+(9−4)2distance_{AB} = \sqrt{(5-2)^2 + (8-3)^2 + (9-4)^2}

    • 点A(x1,x2,x3,x4,……xn)，B(y1,y2,y3,y4,……yn)：

    • distanceAB=∑i=1n(xi−yi)2distance_{AB} = \sqrt{\sum_{i=1}^n(x_i - y_i)^2}

    • 上面这个公式就是欧几里得距离公式

  • KNN算法的理论基础就是：

    • 欧式距离
    • 根据距离远近，选择邻居
    • 物以类聚人以群分
    • 这个算法不难！

  • KNN算法缺陷

    • k给多少比较好呢？
    • 请问绿色的点划归到红色类别，还是蓝色的类别？
    • 如果k = 3，找三个邻居，2个是红色，1个蓝色 投票，红色票数多，所以此时，绿色球划归到，红色的类别
    • 如果k = 5，找五个邻居，3个是蓝色，2个红色 投票，蓝色票数多，所以此时，绿色球划归到，蓝色的类别
    • 分歧，不一致，不稳定，给定的k值不同，结果可能会不同！

  • KNN算法怎么找到邻居的呢？

    • 电脑而言，给了一堆数据
    • 电脑，计算所有点的距离！
    • 然后排序！
    • 选择距离比较小的k个点！
    • 穷举
    • KNN算法，比较耗费时间，要求数据量不能太大，时间复杂度空间复杂度，比较大。

  • KNN这个算法，比较简单，但是，很多情况下，比较实用的。

    • 数据，都是存在规律，精确度要求不高，KNN这个算法，可以实现分类功能。

KNN的案例

  • 鸢尾花分类
  • 生长的环境不同，所以类别3类
  • 类别不同，性质不同：花萼长宽不一样，花瓣长宽不同了。
  • 植物学家，根据形状不同，进行分类
  • 分类算法使用流程：
    • 加载数据
    • 数据预处理，拆分
    • 声明算法，给定超参数
    • 训练算法，算法学习数据，归纳规律
    • 算法，通过数学，找到，数据和目标值之间的规律
    • 算法找到规律，应用
    • 实际使用了。

KNN超参数

  • 邻居
  • weights权重，话语权：uniform、distance
  • p = 1、2
  • metrics = minkowski
  • p = 1 曼哈顿距离
    • 这个距离表示远近方法
    • 红色的线就是曼哈顿距离
    • 蓝色和黄色等价曼哈顿距离
    • 绿色线就是欧式距离
  • p = 2 欧式距离

作业：

  • 使用KNN诊断是否患癌症
  • 早发现，提高治愈率
  • 体检，2000块钱，查一下癌症！